sprintf2.t: mark TODO bad denorm values under g++
[perl.git] / zaphod32_hash.h
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 #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
85 #endif
86 #endif
87
88 #ifndef U8TO32_LE
89 #if ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
90 #define U8TO32_LE(ptr)  (*((const U32 *)(ptr)))
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
99 #endif
100
101 #ifndef U8TO16_LE
102 #if ZAPHOD32_ALLOW_UNALIGNED_AND_LITTLE_ENDIAN
103 #define U8TO16_LE(ptr)  (*((const U16 *)(ptr)))
104 #else
105 #define U8TO16_LE(ptr)  (\
106     (U16)(ptr)[1] << 8  | \
107     (U16)(ptr)[0]         \
108 )
109 #endif
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 ) {
168     const U32 *seed= (const U32 *)seed_ch;
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);
188
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);
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");
207
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;
218     STRLEN len = key_len;
219     U32 v0= state[0];
220     U32 v1= state[1];
221     U32 v2= state[2] ^ (0xC41A7AB1 * ((U32)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;
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);
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
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     {
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) {
294         case 3: v2 += (U32)key[2];          /* FALLTHROUGH */
295         case 2: v0 += (U32)U8TO16_LE(key);
296                 break;
297         case 1: v0 += (U32)key[0];
298                 break;
299         case 0: v2 ^= 0xFF;
300                 break;
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 ) {
317     U32 state[3];
318     zaphod32_seed_state(seed_ch,(U8*)state);
319     return zaphod32_hash_with_state((U8*)state,key,key_len);
320 }
321
322 #endif