APItest/t/utf8_warn_base.pl: Rename and modify test
[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 #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
132 ZAPHOD32_STATIC_INLINE
133 void 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);
157
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);
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");
176
177 }
178
179 ZAPHOD32_STATIC_INLINE
180 U32 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) {
242 zaphod32_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     }
267 zaphod32_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
277 ZAPHOD32_STATIC_INLINE U32 zaphod32_hash(
278     const U8 *seed_ch,
279     const U8 *key,
280     const STRLEN key_len
281 ) {
282     U32 state[3];
283     zaphod32_seed_state(seed_ch,(U8*)state);
284     return zaphod32_hash_with_state((U8*)state,key,key_len);
285 }
286
287 #endif