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
28 /* Find best way to ROTL32/ROTL64 */
29 #ifndef ROTL32
30 #if defined(_MSC_VER)
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)
34 #else
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)))
38 #endif
39 #endif
40
41 #ifndef PERL_SEEN_HV_FUNC_H_
42 #if !defined(U64)
43 #include <stdint.h>
44 #define U64 uint64_t
45 #endif
46
47 #if !defined(U32)
48 #define U32 uint32_t
49 #endif
50
51 #if !defined(U8)
52 #define U8 unsigned char
53 #endif
54
55 #if !defined(U16)
56 #define U16 uint16_t
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
77 /* This is two marsaglia xor-shift permutes, with a prime-multiple
78 * sandwiched inside. The end result of doing this twice with different
79 * primes is a completely avalanched v. */
80 #define ZAPHOD32_SCRAMBLE32(v,prime) STMT_START { \
81 v ^= (v>>9); \
82 v ^= (v<<21); \
83 v ^= (v>>16); \
84 v *= prime; \
85 v ^= (v>>17); \
86 v ^= (v<<15); \
87 v ^= (v>>23); \
88 } STMT_END
89
90 #define ZAPHOD32_FINALIZE(v0,v1,v2) STMT_START { \
91 ZAPHOD32_WARN3("v0=%08x v1=%08x v2=%08x - ZAPHOD32 FINALIZE\n", \
92 (unsigned int)v0, (unsigned int)v1, (unsigned int)v2); \
93 v2 += v0; \
94 v1 -= v2; \
95 v1 = ROTL32(v1, 6); \
96 v2 ^= v1; \
97 v2 = ROTL32(v2, 28); \
98 v1 ^= v2; \
99 v0 += v1; \
100 v1 = ROTL32(v1, 24); \
101 v2 += v1; \
102 v2 = ROTL32(v2, 18) + v1; \
103 v0 ^= v2; \
104 v0 = ROTL32(v0, 20); \
105 v2 += v0; \
106 v1 ^= v2; \
107 v0 += v1; \
108 v0 = ROTL32(v0, 5); \
109 v2 += v0; \
110 v2 = ROTL32(v2, 22); \
111 v0 -= v1; \
112 v1 -= v2; \
113 v1 = ROTL32(v1, 17); \
114 } STMT_END
115
116 #define ZAPHOD32_MIX(v0,v1,v2,text) STMT_START { \
117 ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x - ZAPHOD32 %s MIX\n", \
118 (unsigned int)v0,(unsigned int)v1,(unsigned int)v2, text ); \
119 v0 = ROTL32(v0,16) - v2; \
120 v1 = ROTR32(v1,13) ^ v2; \
121 v2 = ROTL32(v2,17) + v1; \
122 v0 = ROTR32(v0, 2) + v1; \
123 v1 = ROTR32(v1,17) - v0; \
124 v2 = ROTR32(v2, 7) ^ v0; \
125 } STMT_END
126
127
128 ZAPHOD32_STATIC_INLINE
zaphod32_seed_state(const U8 * seed_ch,U8 * state_ch)129 void zaphod32_seed_state (
130 const U8 *seed_ch,
131 U8 *state_ch
132 ) {
133 const U32 *seed= (const U32 *)seed_ch;
134 U32 *state= (U32 *)state_ch;
135
136 /* hex expansion of PI, skipping first two digits. PI= 3.2[43f6...]
137 *
138 * PI value in hex from here:
139 *
140 * http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html
141 *
142 * Ensure that the three state vectors are nonzero regardless of
143 * the seed. The idea of these two steps is to ensure that the 0
144 * state comes from a seed utterly unlike that of the value we
145 * replace it with.
146 */
147 state[0]= seed[0] ^ 0x43f6a888;
148 state[1]= seed[1] ^ 0x5a308d31;
149 state[2]= seed[2] ^ 0x3198a2e0;
150 if (!state[0]) state[0] = 1;
151 if (!state[1]) state[1] = 2;
152 if (!state[2]) state[2] = 4;
153 /* these are pseudo-randomly selected primes between 2**31 and 2**32
154 * (I generated a big list and then randomly chose some from the list) */
155 ZAPHOD32_SCRAMBLE32(state[0],0x9fade23b);
156 ZAPHOD32_SCRAMBLE32(state[1],0xaa6f908d);
157 ZAPHOD32_SCRAMBLE32(state[2],0xcdf6b72d);
158
159 /* now that we have scrambled we do some mixing to avalanche the
160 * state bits to gether */
161 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 1/4");
162 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 2/4");
163 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 3/4");
164 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 4/4");
165
166 /* and then scramble them again with different primes */
167 ZAPHOD32_SCRAMBLE32(state[0],0xc95d22a9);
168 ZAPHOD32_SCRAMBLE32(state[1],0x8497242b);
169 ZAPHOD32_SCRAMBLE32(state[2],0x9c5cc4e9);
170
171 /* and a thorough final mix */
172 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 1/5");
173 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 2/5");
174 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 3/5");
175 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 4/5");
176 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 5/5");
177
178 }
179
180 ZAPHOD32_STATIC_INLINE
zaphod32_hash_with_state(const U8 * state_ch,const U8 * key,const STRLEN key_len)181 U32 zaphod32_hash_with_state(
182 const U8 *state_ch,
183 const U8 *key,
184 const STRLEN key_len
185 ) {
186 const U32 *state= (const U32 *)state_ch;
187 const U8 *end;
188 STRLEN len = key_len;
189 U32 v0= state[0];
190 U32 v1= state[1];
191 U32 v2= state[2] ^ (0xC41A7AB1 * ((U32)key_len + 1));
192
193 ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x ln=%08x HASH START\n",
194 (unsigned int)state[0], (unsigned int)state[1],
195 (unsigned int)state[2], (unsigned int)key_len);
196 {
197 switch (len) {
198 default: goto zaphod32_read8;
199 case 12: v2 += (U32)key[11] << 24; /* FALLTHROUGH */
200 case 11: v2 += (U32)key[10] << 16; /* FALLTHROUGH */
201 case 10: v2 += (U32)U8TO16_LE(key+8);
202 v1 -= U8TO32_LE(key+4);
203 v0 += U8TO32_LE(key+0);
204 goto zaphod32_finalize;
205 case 9: v2 += (U32)key[8]; /* FALLTHROUGH */
206 case 8: v1 -= U8TO32_LE(key+4);
207 v0 += U8TO32_LE(key+0);
208 goto zaphod32_finalize;
209 case 7: v2 += (U32)key[6]; /* FALLTHROUGH */
210 case 6: v0 += (U32)U8TO16_LE(key+4);
211 v1 -= U8TO32_LE(key+0);
212 goto zaphod32_finalize;
213 case 5: v0 += (U32)key[4]; /* FALLTHROUGH */
214 case 4: v1 -= U8TO32_LE(key+0);
215 goto zaphod32_finalize;
216 case 3: v2 += (U32)key[2]; /* FALLTHROUGH */
217 case 2: v0 += (U32)U8TO16_LE(key);
218 break;
219 case 1: v0 += (U32)key[0];
220 break;
221 case 0: v2 ^= 0xFF;
222 break;
223
224 }
225 v0 -= v2;
226 v2 = ROTL32(v2, 8) ^ v0;
227 v0 = ROTR32(v0,16) + v2;
228 v2 += v0;
229 v0 += v0 >> 9;
230 v0 += v2;
231 v2 ^= v0;
232 v2 += v2 << 4;
233 v0 -= v2;
234 v2 = ROTR32(v2, 8) ^ v0;
235 v0 = ROTL32(v0,16) ^ v2;
236 v2 = ROTL32(v2,10) + v0;
237 v0 = ROTR32(v0,30) + v2;
238 v2 = ROTR32(v2,12);
239 return v0 ^ v2;
240 }
241
242 /* if (len >= 8) */ /* this block is only reached by a goto above, so this condition
243 is commented out, but if the above block is removed it would
244 be necessary to use this. */
245 {
246 zaphod32_read8:
247 len = key_len & 0x7;
248 end = key + key_len - len;
249 do {
250 v1 -= U8TO32_LE(key+0);
251 v0 += U8TO32_LE(key+4);
252 ZAPHOD32_MIX(v0,v1,v2,"MIX 2-WORDS A");
253 key += 8;
254 } while ( key < end );
255 }
256
257 if ( len >= 4 ) {
258 v1 -= U8TO32_LE(key);
259 key += 4;
260 }
261
262 v0 += (U32)(key_len) << 24;
263 switch (len & 0x3) {
264 case 3: v2 += (U32)key[2]; /* FALLTHROUGH */
265 case 2: v0 += (U32)U8TO16_LE(key);
266 break;
267 case 1: v0 += (U32)key[0];
268 break;
269 case 0: v2 ^= 0xFF;
270 break;
271 }
272 zaphod32_finalize:
273 ZAPHOD32_FINALIZE(v0,v1,v2);
274
275 ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x hh=%08x - FINAL\n\n",
276 (unsigned int)v0, (unsigned int)v1, (unsigned int)v2,
277 (unsigned int)v0 ^ v1 ^ v2);
278
279 return v0 ^ v1 ^ v2;
280 }
281
zaphod32_hash(const U8 * seed_ch,const U8 * key,const STRLEN key_len)282 ZAPHOD32_STATIC_INLINE U32 zaphod32_hash(
283 const U8 *seed_ch,
284 const U8 *key,
285 const STRLEN key_len
286 ) {
287 U32 state[3];
288 zaphod32_seed_state(seed_ch,(U8*)state);
289 return zaphod32_hash_with_state((U8*)state,key,key_len);
290 }
291
292 #endif
293