1 #ifndef DEBUG_ZAPHOD32_HASH
2 #define DEBUG_ZAPHOD32_HASH 0
4 #if DEBUG_ZAPHOD32_HASH == 1
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)
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)
28 /* Find best way to ROTL32/ROTL64 */
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)
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)))
41 #ifndef PERL_SEEN_HV_FUNC_H
52 #define U8 unsigned char
64 #ifndef ZAPHOD32_STATIC_INLINE
65 #ifdef PERL_STATIC_INLINE
66 #define ZAPHOD32_STATIC_INLINE PERL_STATIC_INLINE
68 #define ZAPHOD32_STATIC_INLINE static inline
74 #define STMT_END while(0)
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.
81 #ifdef U32_ALIGNMENT_REQUIRED
82 #define ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 0
84 #define ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN 1
89 #if ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
90 #define U8TO32_LE(ptr) (*((const U32 *)(ptr)))
92 #define U8TO32_LE(ptr) (\
93 (U32)(ptr)[3] << 24 | \
94 (U32)(ptr)[2] << 16 | \
95 (U32)(ptr)[1] << 8 | \
102 #if ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
103 #define U8TO16_LE(ptr) (*((const U16 *)(ptr)))
105 #define U8TO16_LE(ptr) (\
106 (U16)(ptr)[1] << 8 | \
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 { \
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); \
130 v1 = ROTL32(v1, 6); \
132 v2 = ROTL32(v2, 28); \
135 v1 = ROTL32(v1, 24); \
137 v2 = ROTL32(v2, 18) + v1; \
139 v0 = ROTL32(v0, 20); \
143 v0 = ROTL32(v0, 5); \
145 v2 = ROTL32(v2, 22); \
148 v1 = ROTL32(v1, 17); \
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; \
163 ZAPHOD32_STATIC_INLINE
164 void zaphod32_seed_state (
168 const U32 *seed= (const U32 *)seed_ch;
169 U32 *state= (U32 *)state_ch;
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);
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");
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);
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");
210 ZAPHOD32_STATIC_INLINE
211 U32 zaphod32_hash_with_state(
216 U32 *state= (U32 *)state_ch;
218 STRLEN len = key_len;
221 U32 v2= state[2] ^ (0xC41A7AB1 * (key_len + 1));
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);
228 default: goto zaphod32_read8;
229 case 12: v2 += (U32)key[11] << 24; /* FALLTHROUGH */
230 case 11: v2 += (U32)key[10] << 16; /* FALLTHROUGH */
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;
235 case 9: v2 += (U32)key[8]; /* FALLTHROUGH */
236 case 8: v1 -= U8TO32_LE(key+4);
237 v0 += U8TO32_LE(key+0);
238 goto zaphod32_finalize;
239 case 7: v2 += (U32)key[6]; /* FALLTHROUGH */
240 case 6: v0 += (U32)U8TO16_LE(key+4);
241 v1 -= U8TO32_LE(key+0);
242 goto zaphod32_finalize;
243 case 5: v0 += (U32)key[4]; /* FALLTHROUGH */
244 case 4: v1 -= U8TO32_LE(key+0);
245 goto zaphod32_finalize;
246 case 3: v2 += (U32)key[2]; /* FALLTHROUGH */
247 case 2: v0 += (U32)U8TO16_LE(key);
249 case 1: v0 += (U32)key[0];
256 v2 = ROTL32(v2, 8) ^ v0;
257 v0 = ROTR32(v0,16) + 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;
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. */
278 end = key + key_len - len;
280 v1 -= U8TO32_LE(key+0);
281 v0 += U8TO32_LE(key+4);
282 ZAPHOD32_MIX(v0,v1,v2,"MIX 2-WORDS A");
284 } while ( key < end );
288 v1 -= U8TO32_LE(key);
292 v0 += (U32)(key_len) << 24;
294 case 3: v2 += (U32)key[2]; /* FALLTHROUGH */
295 case 2: v0 += (U32)U8TO16_LE(key);
297 case 1: v0 += (U32)key[0];
303 ZAPHOD32_FINALIZE(v0,v1,v2);
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);
312 ZAPHOD32_STATIC_INLINE U32 zaphod32_hash(
318 zaphod32_seed_state(seed_ch,(U8*)state);
319 return zaphod32_hash_with_state((U8*)state,key,key_len);