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