Commit | Line | Data |
---|---|---|
9d5e3f1a YO |
1 | #ifndef STADTX_HASH_H |
2 | #define STADTX_HASH_H | |
3 | ||
4 | #ifndef DEBUG_STADTX_HASH | |
5 | #define DEBUG_STADTX_HASH 0 | |
6 | #endif | |
7 | ||
9d5e3f1a YO |
8 | #ifndef PERL_SEEN_HV_FUNC_H |
9 | ||
10 | #if !defined(U64) | |
11 | #include <stdint.h> | |
12 | #define U64 uint64_t | |
13 | #endif | |
14 | ||
15 | #if !defined(U32) | |
16 | #define U32 uint32_t | |
17 | #endif | |
18 | ||
19 | #if !defined(U8) | |
20 | #define U8 unsigned char | |
21 | #endif | |
22 | ||
23 | #if !defined(U16) | |
24 | #define U16 uint16_t | |
25 | #endif | |
26 | ||
27 | #ifndef STRLEN | |
28 | #define STRLEN int | |
29 | #endif | |
d939098c | 30 | |
9d5e3f1a YO |
31 | #endif |
32 | ||
33 | #ifndef STADTX_STATIC_INLINE | |
34 | #ifdef PERL_STATIC_INLINE | |
35 | #define STADTX_STATIC_INLINE PERL_STATIC_INLINE | |
36 | #else | |
37 | #define STADTX_STATIC_INLINE static inline | |
38 | #endif | |
39 | #endif | |
40 | ||
41 | #ifndef STMT_START | |
42 | #define STMT_START do | |
43 | #define STMT_END while(0) | |
44 | #endif | |
45 | ||
9995b99e | 46 | #ifndef STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN |
d939098c YO |
47 | /* STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN only matters if nothing has defined U8TO64_LE etc, |
48 | * and when built with Perl these should be defined before this file is loaded. | |
49 | */ | |
50 | #ifdef U32_ALIGNMENT_REQUIRED | |
51 | #define STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 0 | |
52 | #else | |
9995b99e | 53 | #define STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 1 |
9d5e3f1a | 54 | #endif |
d939098c YO |
55 | #endif |
56 | ||
57 | #ifndef U8TO64_LE | |
58 | #if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN | |
59 | #define U8TO64_LE(ptr) (*((const U64 *)(ptr))) | |
60 | #else | |
61 | #define U8TO64_LE(ptr) (\ | |
62 | (U64)(ptr)[7] << 56 | \ | |
63 | (U64)(ptr)[6] << 48 | \ | |
64 | (U64)(ptr)[5] << 40 | \ | |
65 | (U64)(ptr)[4] << 32 | \ | |
66 | (U64)(ptr)[3] << 24 | \ | |
67 | (U64)(ptr)[2] << 16 | \ | |
68 | (U64)(ptr)[1] << 8 | \ | |
69 | (U64)(ptr)[0] \ | |
70 | ) | |
71 | #endif | |
72 | #endif | |
9d5e3f1a | 73 | |
d939098c | 74 | #ifndef U8TO32_LE |
9d5e3f1a | 75 | #if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN |
d939098c | 76 | #define U8TO32_LE(ptr) (*((const U32 *)(ptr))) |
9d5e3f1a | 77 | #else |
d939098c YO |
78 | #define U8TO32_LE(ptr) (\ |
79 | (U32)(ptr)[3] << 24 | \ | |
80 | (U32)(ptr)[2] << 16 | \ | |
81 | (U32)(ptr)[1] << 8 | \ | |
82 | (U32)(ptr)[0] \ | |
83 | ) | |
9d5e3f1a | 84 | #endif |
d939098c YO |
85 | #endif |
86 | ||
87 | #ifndef U8TO16_LE | |
88 | #if STADTX_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN | |
89 | #define U8TO16_LE(ptr) (*((const U16 *)(ptr))) | |
90 | #else | |
91 | #define U8TO16_LE(ptr) (\ | |
92 | (U16)(ptr)[1] << 8 | \ | |
93 | (U16)(ptr)[0] \ | |
94 | ) | |
95 | #endif | |
96 | #endif | |
97 | ||
98 | /* Find best way to ROTL32/ROTL64 */ | |
99 | #if defined(_MSC_VER) | |
100 | #include <stdlib.h> /* Microsoft put _rotl declaration in here */ | |
101 | #define ROTL32(x,r) _rotl(x,r) | |
102 | #define ROTR32(x,r) _rotr(x,r) | |
103 | #define ROTL64(x,r) _rotl64(x,r) | |
104 | #define ROTR64(x,r) _rotr64(x,r) | |
105 | #else | |
106 | /* gcc recognises this code and generates a rotate instruction for CPUs with one */ | |
107 | #define ROTL32(x,r) (((U32)(x) << (r)) | ((U32)(x) >> (32 - (r)))) | |
108 | #define ROTR32(x,r) (((U32)(x) << (32 - (r))) | ((U32)(x) >> (r))) | |
109 | #define ROTL64(x,r) ( ( (U64)(x) << (r) ) | ( (U64)(x) >> ( 64 - (r) ) ) ) | |
110 | #define ROTR64(x,r) ( ( (U64)(x) << ( 64 - (r) ) ) | ( (U64)(x) >> (r) ) ) | |
111 | #endif | |
112 | ||
9d5e3f1a YO |
113 | |
114 | /* do a marsaglia xor-shift permutation followed by a | |
115 | * multiply by a prime (presumably large) and another | |
116 | * marsaglia xor-shift permutation. | |
117 | * One of these thoroughly changes the bits of the input. | |
118 | * Two of these with different primes passes the Strict Avalanche Criteria | |
119 | * in all the tests I did. | |
120 | * | |
121 | * Note that v cannot end up zero after a scramble64 unless it | |
122 | * was zero in the first place. | |
123 | */ | |
124 | #define STADTX_SCRAMBLE64(v,prime) STMT_START { \ | |
125 | v ^= (v >> 13); \ | |
126 | v ^= (v << 35); \ | |
127 | v ^= (v >> 30); \ | |
128 | v *= prime; \ | |
129 | v ^= (v >> 19); \ | |
130 | v ^= (v << 15); \ | |
131 | v ^= (v >> 46); \ | |
132 | } STMT_END | |
133 | ||
134 | ||
135 | STADTX_STATIC_INLINE void stadtx_seed_state ( | |
136 | const U8 *seed_ch, | |
137 | U8 *state_ch | |
138 | ) { | |
20e4c2ed | 139 | const U64 *seed= (const U64 *)seed_ch; |
9d5e3f1a YO |
140 | U64 *state= (U64 *)state_ch; |
141 | /* first we apply two masks to each word of the seed, this means that | |
142 | * a) at least one of state[0] and state[2] is nonzero, | |
143 | * b) at least one of state[1] and state[3] is nonzero | |
144 | * c) that state[0] and state[2] are different | |
145 | * d) that state[1] and state[3] are different | |
146 | * e) that the replacement value for any zero's is a totally different from the seed value. | |
147 | * (iow, if seed[0] is 0x43f6a8885a308d31UL then state[0] becomes 0, which is the replaced | |
148 | * with 1, which is totally different.). */ | |
149 | /* hex expansion of pi, skipping first two digits. pi= 3.2[43f6...]*/ | |
150 | /* pi value in hex from here: | |
151 | * http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html*/ | |
d68aa7aa JH |
152 | state[0]= seed[0] ^ UINT64_C(0x43f6a8885a308d31); |
153 | state[1]= seed[1] ^ UINT64_C(0x3198a2e03707344a); | |
154 | state[2]= seed[0] ^ UINT64_C(0x4093822299f31d00); | |
155 | state[3]= seed[1] ^ UINT64_C(0x82efa98ec4e6c894); | |
9d5e3f1a YO |
156 | if (!state[0]) state[0]=1; |
157 | if (!state[1]) state[1]=2; | |
158 | if (!state[2]) state[2]=4; | |
159 | if (!state[3]) state[3]=8; | |
160 | /* and now for good measure we double scramble all four - | |
161 | * a double scramble guarantees a complete avalanche of all the | |
162 | * bits in the seed - IOW, by the time we are hashing the | |
163 | * four state vectors should be completely different and utterly | |
164 | * uncognizable from the input seed bits */ | |
d68aa7aa JH |
165 | STADTX_SCRAMBLE64(state[0],UINT64_C(0x801178846e899d17)); |
166 | STADTX_SCRAMBLE64(state[0],UINT64_C(0xdd51e5d1c9a5a151)); | |
167 | STADTX_SCRAMBLE64(state[1],UINT64_C(0x93a7d6c8c62e4835)); | |
168 | STADTX_SCRAMBLE64(state[1],UINT64_C(0x803340f36895c2b5)); | |
169 | STADTX_SCRAMBLE64(state[2],UINT64_C(0xbea9344eb7565eeb)); | |
170 | STADTX_SCRAMBLE64(state[2],UINT64_C(0xcd95d1e509b995cd)); | |
171 | STADTX_SCRAMBLE64(state[3],UINT64_C(0x9999791977e30c13)); | |
172 | STADTX_SCRAMBLE64(state[3],UINT64_C(0xaab8b6b05abfc6cd)); | |
9d5e3f1a YO |
173 | } |
174 | ||
d68aa7aa JH |
175 | #define STADTX_K0_U64 UINT64_C(0xb89b0f8e1655514f) |
176 | #define STADTX_K1_U64 UINT64_C(0x8c6f736011bd5127) | |
177 | #define STADTX_K2_U64 UINT64_C(0x8f29bd94edce7b39) | |
178 | #define STADTX_K3_U64 UINT64_C(0x9c1b8e1e9628323f) | |
9d5e3f1a YO |
179 | |
180 | #define STADTX_K2_U32 0x802910e3 | |
181 | #define STADTX_K3_U32 0x819b13af | |
182 | #define STADTX_K4_U32 0x91cb27e5 | |
183 | #define STADTX_K5_U32 0xc1a269c1 | |
184 | ||
185 | STADTX_STATIC_INLINE U64 stadtx_hash_with_state( | |
186 | const U8 *state_ch, | |
187 | const U8 *key, | |
188 | const STRLEN key_len | |
189 | ) { | |
190 | U64 *state= (U64 *)state_ch; | |
9995b99e | 191 | STRLEN len = key_len; |
9d5e3f1a YO |
192 | U64 v0= state[0] ^ ((key_len+1) * STADTX_K0_U64); |
193 | U64 v1= state[1] ^ ((key_len+2) * STADTX_K1_U64); | |
194 | if (len < 32) { | |
195 | switch(len >> 3) { | |
196 | case 3: | |
197 | v0 += U8TO64_LE(key) * STADTX_K3_U64; | |
198 | v0= ROTR64(v0, 17) ^ v1; | |
199 | v1= ROTR64(v1, 53) + v0; | |
200 | key += 8; | |
b2733f8f | 201 | /* FALLTHROUGH */ |
9d5e3f1a YO |
202 | case 2: |
203 | v0 += U8TO64_LE(key) * STADTX_K3_U64; | |
204 | v0= ROTR64(v0, 17) ^ v1; | |
205 | v1= ROTR64(v1, 53) + v0; | |
206 | key += 8; | |
b2733f8f | 207 | /* FALLTHROUGH */ |
9d5e3f1a YO |
208 | case 1: |
209 | v0 += U8TO64_LE(key) * STADTX_K3_U64; | |
210 | v0= ROTR64(v0, 17) ^ v1; | |
211 | v1= ROTR64(v1, 53) + v0; | |
212 | key += 8; | |
b2733f8f | 213 | /* FALLTHROUGH */ |
9d5e3f1a YO |
214 | case 0: |
215 | default: break; | |
216 | } | |
217 | switch ( len & 0x7 ) { | |
218 | case 7: v0 += (U64)key[6] << 32; | |
b2733f8f | 219 | /* FALLTHROUGH */ |
9d5e3f1a | 220 | case 6: v1 += (U64)key[5] << 48; |
b2733f8f | 221 | /* FALLTHROUGH */ |
9d5e3f1a | 222 | case 5: v0 += (U64)key[4] << 16; |
b2733f8f | 223 | /* FALLTHROUGH */ |
9d5e3f1a YO |
224 | case 4: v1 += (U64)U8TO32_LE(key); |
225 | break; | |
226 | case 3: v0 += (U64)key[2] << 48; | |
b2733f8f | 227 | /* FALLTHROUGH */ |
9d5e3f1a YO |
228 | case 2: v1 += (U64)U8TO16_LE(key); |
229 | break; | |
230 | case 1: v0 += (U64)key[0]; | |
b2733f8f | 231 | /* FALLTHROUGH */ |
9d5e3f1a YO |
232 | case 0: v1 = ROTL64(v1, 32) ^ 0xFF; |
233 | break; | |
234 | } | |
235 | v1 ^= v0; | |
236 | v0 = ROTR64(v0,33) + v1; | |
237 | v1 = ROTL64(v1,17) ^ v0; | |
238 | v0 = ROTL64(v0,43) + v1; | |
239 | v1 = ROTL64(v1,31) - v0; | |
240 | v0 = ROTL64(v0,13) ^ v1; | |
241 | v1 -= v0; | |
242 | v0 = ROTL64(v0,41) + v1; | |
243 | v1 = ROTL64(v1,37) ^ v0; | |
244 | v0 = ROTR64(v0,39) + v1; | |
245 | v1 = ROTR64(v1,15) + v0; | |
246 | v0 = ROTL64(v0,15) ^ v1; | |
247 | v1 = ROTR64(v1, 5); | |
248 | return v0 ^ v1; | |
249 | } else { | |
250 | U64 v2= state[2] ^ ((key_len+3) * STADTX_K2_U64); | |
251 | U64 v3= state[3] ^ ((key_len+4) * STADTX_K3_U64); | |
252 | ||
253 | do { | |
254 | v0 += (U64)U8TO64_LE(key+ 0) * STADTX_K2_U32; v0= ROTL64(v0,57) ^ v3; | |
255 | v1 += (U64)U8TO64_LE(key+ 8) * STADTX_K3_U32; v1= ROTL64(v1,63) ^ v2; | |
256 | v2 += (U64)U8TO64_LE(key+16) * STADTX_K4_U32; v2= ROTR64(v2,47) + v0; | |
257 | v3 += (U64)U8TO64_LE(key+24) * STADTX_K5_U32; v3= ROTR64(v3,11) - v1; | |
258 | key += 32; | |
259 | len -= 32; | |
260 | } while ( len >= 32 ); | |
261 | ||
262 | switch ( len >> 3 ) { | |
263 | case 3: v0 += ((U64)U8TO64_LE(key) * STADTX_K2_U32); key += 8; v0= ROTL64(v0,57) ^ v3; | |
b2733f8f | 264 | /* FALLTHROUGH */ |
9d5e3f1a | 265 | case 2: v1 += ((U64)U8TO64_LE(key) * STADTX_K3_U32); key += 8; v1= ROTL64(v1,63) ^ v2; |
b2733f8f | 266 | /* FALLTHROUGH */ |
9d5e3f1a | 267 | case 1: v2 += ((U64)U8TO64_LE(key) * STADTX_K4_U32); key += 8; v2= ROTR64(v2,47) + v0; |
b2733f8f | 268 | /* FALLTHROUGH */ |
9d5e3f1a | 269 | case 0: v3 = ROTR64(v3,11) - v1; |
b2733f8f | 270 | /* FALLTHROUGH */ |
9d5e3f1a YO |
271 | } |
272 | v0 ^= (len+1) * STADTX_K3_U64; | |
273 | switch ( len & 0x7 ) { | |
274 | case 7: v1 += (U64)key[6]; | |
b2733f8f | 275 | /* FALLTHROUGH */ |
9d5e3f1a YO |
276 | case 6: v2 += (U64)U8TO16_LE(key+4); |
277 | v3 += (U64)U8TO32_LE(key); | |
278 | break; | |
279 | case 5: v1 += (U64)key[4]; | |
b2733f8f | 280 | /* FALLTHROUGH */ |
9d5e3f1a YO |
281 | case 4: v2 += (U64)U8TO32_LE(key); |
282 | break; | |
283 | case 3: v3 += (U64)key[2]; | |
b2733f8f | 284 | /* FALLTHROUGH */ |
9d5e3f1a YO |
285 | case 2: v1 += (U64)U8TO16_LE(key); |
286 | break; | |
287 | case 1: v2 += (U64)key[0]; | |
b2733f8f | 288 | /* FALLTHROUGH */ |
9d5e3f1a YO |
289 | case 0: v3 = ROTL64(v3, 32) ^ 0xFF; |
290 | break; | |
291 | } | |
292 | ||
293 | v1 -= v2; | |
294 | v0 = ROTR64(v0,19); | |
295 | v1 -= v0; | |
296 | v1 = ROTR64(v1,53); | |
297 | v3 ^= v1; | |
298 | v0 -= v3; | |
299 | v3 = ROTL64(v3,43); | |
300 | v0 += v3; | |
301 | v0 = ROTR64(v0, 3); | |
302 | v3 -= v0; | |
303 | v2 = ROTR64(v2,43) - v3; | |
304 | v2 = ROTL64(v2,55) ^ v0; | |
305 | v1 -= v2; | |
306 | v3 = ROTR64(v3, 7) - v2; | |
307 | v2 = ROTR64(v2,31); | |
308 | v3 += v2; | |
309 | v2 -= v1; | |
310 | v3 = ROTR64(v3,39); | |
311 | v2 ^= v3; | |
312 | v3 = ROTR64(v3,17) ^ v2; | |
313 | v1 += v3; | |
314 | v1 = ROTR64(v1, 9); | |
315 | v2 ^= v1; | |
316 | v2 = ROTL64(v2,24); | |
317 | v3 ^= v2; | |
318 | v3 = ROTR64(v3,59); | |
319 | v0 = ROTR64(v0, 1) - v1; | |
320 | ||
321 | return v0 ^ v1 ^ v2 ^ v3; | |
322 | } | |
323 | } | |
324 | ||
325 | STADTX_STATIC_INLINE U64 stadtx_hash( | |
326 | const U8 *seed_ch, | |
327 | const U8 *key, | |
328 | const STRLEN key_len | |
329 | ) { | |
330 | U64 state[4]; | |
331 | stadtx_seed_state(seed_ch,(U8*)state); | |
332 | return stadtx_hash_with_state((U8*)state,key,key_len); | |
333 | } | |
334 | ||
335 | #endif |