Commit | Line | Data |
---|---|---|
9d5e3f1a YO |
1 | #ifndef DEBUG_ZAPHOD32_HASH |
2 | #define DEBUG_ZAPHOD32_HASH 0 | |
3 | ||
4 | #if DEBUG_ZAPHOD32_HASH == 1 | |
5 | #include <stdio.h> | |
6 | #define ZAPHOD32_WARN6(pat,v0,v1,v2,v3,v4,v5) printf(pat, v0, v1, v2, v3, v4, v5) | |
7 | #define ZAPHOD32_WARN5(pat,v0,v1,v2,v3,v4) printf(pat, v0, v1, v2, v3, v4) | |
8 | #define ZAPHOD32_WARN4(pat,v0,v1,v2,v3) printf(pat, v0, v1, v2, v3) | |
9 | #define ZAPHOD32_WARN3(pat,v0,v1,v2) printf(pat, v0, v1, v2) | |
10 | #define ZAPHOD32_WARN2(pat,v0,v1) printf(pat, v0, v1) | |
11 | #define NOTE3(pat,v0,v1,v2) printf(pat, v0, v1, v2) | |
12 | #elif DEBUG_ZAPHOD32_HASH == 2 | |
13 | #define ZAPHOD32_WARN6(pat,v0,v1,v2,v3,v4,v5) | |
14 | #define ZAPHOD32_WARN5(pat,v0,v1,v2,v3,v4) | |
15 | #define ZAPHOD32_WARN4(pat,v0,v1,v2,v3) | |
16 | #define ZAPHOD32_WARN3(pat,v0,v1,v2) | |
17 | #define ZAPHOD32_WARN2(pat,v0,v1) | |
18 | #define NOTE3(pat,v0,v1,v2) printf(pat, v0, v1, v2) | |
19 | #else | |
20 | #define ZAPHOD32_WARN6(pat,v0,v1,v2,v3,v4,v5) | |
21 | #define ZAPHOD32_WARN5(pat,v0,v1,v2,v3,v4) | |
22 | #define ZAPHOD32_WARN4(pat,v0,v1,v2,v3) | |
23 | #define ZAPHOD32_WARN3(pat,v0,v1,v2) | |
24 | #define NOTE3(pat,v0,v1,v2) | |
25 | #define ZAPHOD32_WARN2(pat,v0,v1) | |
26 | #endif | |
27 | ||
d939098c | 28 | /* Find best way to ROTL32/ROTL64 */ |
9d5e3f1a | 29 | #ifndef ROTL32 |
d939098c | 30 | #if defined(_MSC_VER) |
f8a8fb6d YO |
31 | #include <stdlib.h> /* Microsoft put _rotl declaration in here */ |
32 | #define ROTL32(x,r) _rotl(x,r) | |
33 | #define ROTR32(x,r) _rotr(x,r) | |
d939098c | 34 | #else |
f8a8fb6d YO |
35 | /* gcc recognises this code and generates a rotate instruction for CPUs with one */ |
36 | #define ROTL32(x,r) (((U32)(x) << (r)) | ((U32)(x) >> (32 - (r)))) | |
37 | #define ROTR32(x,r) (((U32)(x) << (32 - (r))) | ((U32)(x) >> (r))) | |
d939098c | 38 | #endif |
9d5e3f1a YO |
39 | #endif |
40 | ||
41 | #ifndef PERL_SEEN_HV_FUNC_H | |
42 | #if !defined(U64) | |
f8a8fb6d YO |
43 | #include <stdint.h> |
44 | #define U64 uint64_t | |
9d5e3f1a YO |
45 | #endif |
46 | ||
47 | #if !defined(U32) | |
f8a8fb6d | 48 | #define U32 uint32_t |
9d5e3f1a YO |
49 | #endif |
50 | ||
51 | #if !defined(U8) | |
f8a8fb6d | 52 | #define U8 unsigned char |
9d5e3f1a YO |
53 | #endif |
54 | ||
55 | #if !defined(U16) | |
f8a8fb6d | 56 | #define U16 uint16_t |
9d5e3f1a YO |
57 | #endif |
58 | ||
59 | #ifndef STRLEN | |
60 | #define STRLEN int | |
61 | #endif | |
62 | #endif | |
63 | ||
64 | #ifndef ZAPHOD32_STATIC_INLINE | |
65 | #ifdef PERL_STATIC_INLINE | |
66 | #define ZAPHOD32_STATIC_INLINE PERL_STATIC_INLINE | |
67 | #else | |
68 | #define ZAPHOD32_STATIC_INLINE static inline | |
69 | #endif | |
70 | #endif | |
71 | ||
72 | #ifndef STMT_START | |
73 | #define STMT_START do | |
74 | #define STMT_END while(0) | |
75 | #endif | |
76 | ||
d939098c YO |
77 | #ifndef ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN |
78 | /* ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN only matters if nothing has defined U8TO64_LE etc, | |
79 | * and when built with Perl these should be defined before this file is loaded. | |
80 | */ | |
81 | #ifdef U32_ALIGNMENT_REQUIRED | |
82 | #define ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 0 | |
83 | #else | |
84 | #define ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 1 | |
9d5e3f1a | 85 | #endif |
d939098c YO |
86 | #endif |
87 | ||
9d5e3f1a | 88 | #ifndef U8TO32_LE |
d939098c | 89 | #if ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN |
9d5e3f1a | 90 | #define U8TO32_LE(ptr) (*((const U32 *)(ptr))) |
d939098c YO |
91 | #else |
92 | #define U8TO32_LE(ptr) (\ | |
93 | (U32)(ptr)[3] << 24 | \ | |
94 | (U32)(ptr)[2] << 16 | \ | |
95 | (U32)(ptr)[1] << 8 | \ | |
96 | (U32)(ptr)[0] \ | |
97 | ) | |
98 | #endif | |
9d5e3f1a | 99 | #endif |
d939098c | 100 | |
9d5e3f1a | 101 | #ifndef U8TO16_LE |
d939098c | 102 | #if ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN |
9d5e3f1a | 103 | #define U8TO16_LE(ptr) (*((const U16 *)(ptr))) |
d939098c YO |
104 | #else |
105 | #define U8TO16_LE(ptr) (\ | |
106 | (U16)(ptr)[1] << 8 | \ | |
107 | (U16)(ptr)[0] \ | |
108 | ) | |
109 | #endif | |
9d5e3f1a YO |
110 | #endif |
111 | ||
112 | /* This is two marsaglia xor-shift permutes, with a prime-multiple | |
113 | * sandwiched inside. The end result of doing this twice with different | |
114 | * primes is a completely avalanched v. */ | |
115 | #define ZAPHOD32_SCRAMBLE32(v,prime) STMT_START { \ | |
116 | v ^= (v>>9); \ | |
117 | v ^= (v<<21); \ | |
118 | v ^= (v>>16); \ | |
119 | v *= prime; \ | |
120 | v ^= (v>>17); \ | |
121 | v ^= (v<<15); \ | |
122 | v ^= (v>>23); \ | |
123 | } STMT_END | |
124 | ||
125 | #define ZAPHOD32_FINALIZE(v0,v1,v2) STMT_START { \ | |
126 | ZAPHOD32_WARN3("v0=%08x v1=%08x v2=%08x - ZAPHOD32 FINALIZE\n", \ | |
127 | (unsigned int)v0, (unsigned int)v1, (unsigned int)v2); \ | |
128 | v2 += v0; \ | |
129 | v1 -= v2; \ | |
130 | v1 = ROTL32(v1, 6); \ | |
131 | v2 ^= v1; \ | |
132 | v2 = ROTL32(v2, 28); \ | |
133 | v1 ^= v2; \ | |
134 | v0 += v1; \ | |
135 | v1 = ROTL32(v1, 24); \ | |
136 | v2 += v1; \ | |
137 | v2 = ROTL32(v2, 18) + v1; \ | |
138 | v0 ^= v2; \ | |
139 | v0 = ROTL32(v0, 20); \ | |
140 | v2 += v0; \ | |
141 | v1 ^= v2; \ | |
142 | v0 += v1; \ | |
143 | v0 = ROTL32(v0, 5); \ | |
144 | v2 += v0; \ | |
145 | v2 = ROTL32(v2, 22); \ | |
146 | v0 -= v1; \ | |
147 | v1 -= v2; \ | |
148 | v1 = ROTL32(v1, 17); \ | |
149 | } STMT_END | |
150 | ||
151 | #define ZAPHOD32_MIX(v0,v1,v2,text) STMT_START { \ | |
152 | ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x - ZAPHOD32 %s MIX\n", \ | |
153 | (unsigned int)v0,(unsigned int)v1,(unsigned int)v2, text ); \ | |
154 | v0 = ROTL32(v0,16) - v2; \ | |
155 | v1 = ROTR32(v1,13) ^ v2; \ | |
156 | v2 = ROTL32(v2,17) + v1; \ | |
157 | v0 = ROTR32(v0, 2) + v1; \ | |
158 | v1 = ROTR32(v1,17) - v0; \ | |
159 | v2 = ROTR32(v2, 7) ^ v0; \ | |
160 | } STMT_END | |
161 | ||
162 | ||
163 | ZAPHOD32_STATIC_INLINE | |
164 | void zaphod32_seed_state ( | |
165 | const U8 *seed_ch, | |
166 | U8 *state_ch | |
167 | ) { | |
20e4c2ed | 168 | const U32 *seed= (const U32 *)seed_ch; |
9d5e3f1a YO |
169 | U32 *state= (U32 *)state_ch; |
170 | ||
171 | /* hex expansion of pi, skipping first two digits. pi= 3.2[43f6...]*/ | |
172 | /* pi value in hex from here: | |
173 | * http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html*/ | |
174 | /* Ensure that the three state vectors are nonzero regardless of the seed. */ | |
175 | /* The idea of these two steps is to ensure that the 0 state comes from a seed | |
176 | * utterly unlike that of the value we replace it with.*/ | |
177 | state[0]= seed[0] ^ 0x43f6a888; | |
178 | state[1]= seed[1] ^ 0x5a308d31; | |
179 | state[2]= seed[2] ^ 0x3198a2e0; | |
180 | if (!state[0]) state[0] = 1; | |
181 | if (!state[1]) state[1] = 2; | |
182 | if (!state[2]) state[2] = 4; | |
183 | /* these are pseduo-randomly selected primes between 2**31 and 2**32 | |
184 | * (I generated a big list and then randomly chose some from the list) */ | |
185 | ZAPHOD32_SCRAMBLE32(state[0],0x9fade23b); | |
186 | ZAPHOD32_SCRAMBLE32(state[1],0xaa6f908d); | |
187 | ZAPHOD32_SCRAMBLE32(state[2],0xcdf6b72d); | |
3deca554 | 188 | |
9d5e3f1a YO |
189 | /* now that we have scrambled we do some mixing to avalanche the |
190 | * state bits to gether */ | |
191 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 1/4"); | |
192 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 2/4"); | |
193 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 3/4"); | |
194 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 4/4"); | |
195 | ||
196 | /* and then scramble them again with different primes */ | |
197 | ZAPHOD32_SCRAMBLE32(state[0],0xc95d22a9); | |
198 | ZAPHOD32_SCRAMBLE32(state[1],0x8497242b); | |
199 | ZAPHOD32_SCRAMBLE32(state[2],0x9c5cc4e9); | |
3deca554 YO |
200 | |
201 | /* and a thorough final mix */ | |
202 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 1/5"); | |
203 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 2/5"); | |
204 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 3/5"); | |
205 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 4/5"); | |
206 | ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 5/5"); | |
9d5e3f1a | 207 | |
9d5e3f1a YO |
208 | } |
209 | ||
210 | ZAPHOD32_STATIC_INLINE | |
211 | U32 zaphod32_hash_with_state( | |
212 | const U8 *state_ch, | |
213 | const U8 *key, | |
214 | const STRLEN key_len | |
215 | ) { | |
216 | U32 *state= (U32 *)state_ch; | |
217 | const U8 *end; | |
9995b99e | 218 | STRLEN len = key_len; |
9d5e3f1a YO |
219 | U32 v0= state[0]; |
220 | U32 v1= state[1]; | |
221 | U32 v2= state[2] ^ (0xC41A7AB1 * (key_len + 1)); | |
222 | ||
223 | ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x ln=%08x HASH START\n", | |
224 | (unsigned int)state[0], (unsigned int)state[1], | |
225 | (unsigned int)state[2], (unsigned int)key_len); | |
226 | { | |
227 | switch (len) { | |
228 | default: goto zaphod32_read8; | |
f8a8fb6d YO |
229 | case 12: v2 += (U32)key[11] << 24; /* FALLTHROUGH */ |
230 | case 11: v2 += (U32)key[10] << 16; /* FALLTHROUGH */ | |
9d5e3f1a YO |
231 | case 10: v2 += (U32)U8TO16_LE(key+8); |
232 | v1 -= U8TO32_LE(key+4); | |
233 | v0 += U8TO32_LE(key+0); | |
234 | goto zaphod32_finalize; | |
f8a8fb6d | 235 | case 9: v2 += (U32)key[8]; /* FALLTHROUGH */ |
9d5e3f1a YO |
236 | case 8: v1 -= U8TO32_LE(key+4); |
237 | v0 += U8TO32_LE(key+0); | |
238 | goto zaphod32_finalize; | |
f8a8fb6d | 239 | case 7: v2 += (U32)key[6]; /* FALLTHROUGH */ |
9d5e3f1a YO |
240 | case 6: v0 += (U32)U8TO16_LE(key+4); |
241 | v1 -= U8TO32_LE(key+0); | |
242 | goto zaphod32_finalize; | |
f8a8fb6d | 243 | case 5: v0 += (U32)key[4]; /* FALLTHROUGH */ |
9d5e3f1a YO |
244 | case 4: v1 -= U8TO32_LE(key+0); |
245 | goto zaphod32_finalize; | |
f8a8fb6d | 246 | case 3: v2 += (U32)key[2]; /* FALLTHROUGH */ |
9d5e3f1a YO |
247 | case 2: v0 += (U32)U8TO16_LE(key); |
248 | break; | |
249 | case 1: v0 += (U32)key[0]; | |
250 | break; | |
251 | case 0: v2 ^= 0xFF; | |
252 | break; | |
253 | ||
254 | } | |
255 | v0 -= v2; | |
256 | v2 = ROTL32(v2, 8) ^ v0; | |
257 | v0 = ROTR32(v0,16) + v2; | |
258 | v2 += v0; | |
259 | v0 += v0 >> 9; | |
260 | v0 += v2; | |
261 | v2 ^= v0; | |
262 | v2 += v2 << 4; | |
263 | v0 -= v2; | |
264 | v2 = ROTR32(v2, 8) ^ v0; | |
265 | v0 = ROTL32(v0,16) ^ v2; | |
266 | v2 = ROTL32(v2,10) + v0; | |
267 | v0 = ROTR32(v0,30) + v2; | |
268 | v2 = ROTR32(v2,12); | |
269 | return v0 ^ v2; | |
270 | } | |
271 | ||
9607fbb7 YO |
272 | /* if (len >= 8) */ /* this block is only reached by a goto above, so this condition |
273 | is commented out, but if the above block is removed it would | |
274 | be necessary to use this. */ | |
275 | { | |
9d5e3f1a YO |
276 | zaphod32_read8: |
277 | len = key_len & 0x7; | |
278 | end = key + key_len - len; | |
279 | do { | |
280 | v1 -= U8TO32_LE(key+0); | |
281 | v0 += U8TO32_LE(key+4); | |
282 | ZAPHOD32_MIX(v0,v1,v2,"MIX 2-WORDS A"); | |
283 | key += 8; | |
284 | } while ( key < end ); | |
285 | } | |
286 | ||
287 | if ( len >= 4 ) { | |
288 | v1 -= U8TO32_LE(key); | |
289 | key += 4; | |
290 | } | |
291 | ||
292 | v0 += (U32)(key_len) << 24; | |
293 | switch (len & 0x3) { | |
f8a8fb6d | 294 | case 3: v2 += (U32)key[2]; /* FALLTHROUGH */ |
9d5e3f1a YO |
295 | case 2: v0 += (U32)U8TO16_LE(key); |
296 | break; | |
297 | case 1: v0 += (U32)key[0]; | |
298 | break; | |
299 | case 0: v2 ^= 0xFF; | |
f8a8fb6d | 300 | break; |
9d5e3f1a YO |
301 | } |
302 | zaphod32_finalize: | |
303 | ZAPHOD32_FINALIZE(v0,v1,v2); | |
304 | ||
305 | ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x hh=%08x - FINAL\n\n", | |
306 | (unsigned int)v0, (unsigned int)v1, (unsigned int)v2, | |
307 | (unsigned int)v0 ^ v1 ^ v2); | |
308 | ||
309 | return v0 ^ v1 ^ v2; | |
310 | } | |
311 | ||
312 | ZAPHOD32_STATIC_INLINE U32 zaphod32_hash( | |
313 | const U8 *seed_ch, | |
314 | const U8 *key, | |
315 | const STRLEN key_len | |
316 | ) { | |
3deca554 | 317 | U32 state[3]; |
9d5e3f1a YO |
318 | zaphod32_seed_state(seed_ch,(U8*)state); |
319 | return zaphod32_hash_with_state((U8*)state,key,key_len); | |
320 | } | |
321 | ||
322 | #endif |