This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
hv_func.h, hv_macro.h: Rename compile-once guard
[perl5.git] / stadtx_hash.h
CommitLineData
9d5e3f1a
YO
1#ifndef STADTX_HASH_H
2#define STADTX_HASH_H
3
4#ifndef DEBUG_STADTX_HASH
5#define DEBUG_STADTX_HASH 0
6#endif
7
b41deab9 8#ifndef PERL_SEEN_HV_FUNC_H_
9d5e3f1a
YO
9
10#if !defined(U64)
11 #include <stdint.h>
12 #define U64 uint64_t
13#endif
14
15#if !defined(U32)
16 #define U32 uint32_t
17#endif
18
19#if !defined(U8)
20 #define U8 unsigned char
21#endif
22
23#if !defined(U16)
24 #define U16 uint16_t
25#endif
26
27#ifndef STRLEN
28#define STRLEN int
29#endif
d939098c 30
9d5e3f1a
YO
31#endif
32
33#ifndef STADTX_STATIC_INLINE
34#ifdef PERL_STATIC_INLINE
35#define STADTX_STATIC_INLINE PERL_STATIC_INLINE
36#else
37#define STADTX_STATIC_INLINE static inline
38#endif
39#endif
40
41#ifndef STMT_START
42#define STMT_START do
43#define STMT_END while(0)
44#endif
45
d939098c
YO
46/* Find best way to ROTL32/ROTL64 */
47#if defined(_MSC_VER)
48 #include <stdlib.h> /* Microsoft put _rotl declaration in here */
49 #define ROTL32(x,r) _rotl(x,r)
50 #define ROTR32(x,r) _rotr(x,r)
51 #define ROTL64(x,r) _rotl64(x,r)
52 #define ROTR64(x,r) _rotr64(x,r)
53#else
54 /* gcc recognises this code and generates a rotate instruction for CPUs with one */
55 #define ROTL32(x,r) (((U32)(x) << (r)) | ((U32)(x) >> (32 - (r))))
56 #define ROTR32(x,r) (((U32)(x) << (32 - (r))) | ((U32)(x) >> (r)))
57 #define ROTL64(x,r) ( ( (U64)(x) << (r) ) | ( (U64)(x) >> ( 64 - (r) ) ) )
58 #define ROTR64(x,r) ( ( (U64)(x) << ( 64 - (r) ) ) | ( (U64)(x) >> (r) ) )
59#endif
60
9d5e3f1a
YO
61
62/* do a marsaglia xor-shift permutation followed by a
63 * multiply by a prime (presumably large) and another
64 * marsaglia xor-shift permutation.
65 * One of these thoroughly changes the bits of the input.
66 * Two of these with different primes passes the Strict Avalanche Criteria
67 * in all the tests I did.
68 *
69 * Note that v cannot end up zero after a scramble64 unless it
70 * was zero in the first place.
71 */
72#define STADTX_SCRAMBLE64(v,prime) STMT_START { \
73 v ^= (v >> 13); \
74 v ^= (v << 35); \
75 v ^= (v >> 30); \
76 v *= prime; \
77 v ^= (v >> 19); \
78 v ^= (v << 15); \
79 v ^= (v >> 46); \
80} STMT_END
81
82
83STADTX_STATIC_INLINE void stadtx_seed_state (
84 const U8 *seed_ch,
85 U8 *state_ch
86) {
20e4c2ed 87 const U64 *seed= (const U64 *)seed_ch;
9d5e3f1a
YO
88 U64 *state= (U64 *)state_ch;
89 /* first we apply two masks to each word of the seed, this means that
90 * a) at least one of state[0] and state[2] is nonzero,
91 * b) at least one of state[1] and state[3] is nonzero
92 * c) that state[0] and state[2] are different
93 * d) that state[1] and state[3] are different
94 * e) that the replacement value for any zero's is a totally different from the seed value.
95 * (iow, if seed[0] is 0x43f6a8885a308d31UL then state[0] becomes 0, which is the replaced
96 * with 1, which is totally different.). */
97 /* hex expansion of pi, skipping first two digits. pi= 3.2[43f6...]*/
98 /* pi value in hex from here:
99 * http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html*/
d68aa7aa
JH
100 state[0]= seed[0] ^ UINT64_C(0x43f6a8885a308d31);
101 state[1]= seed[1] ^ UINT64_C(0x3198a2e03707344a);
102 state[2]= seed[0] ^ UINT64_C(0x4093822299f31d00);
103 state[3]= seed[1] ^ UINT64_C(0x82efa98ec4e6c894);
9d5e3f1a
YO
104 if (!state[0]) state[0]=1;
105 if (!state[1]) state[1]=2;
106 if (!state[2]) state[2]=4;
107 if (!state[3]) state[3]=8;
108 /* and now for good measure we double scramble all four -
109 * a double scramble guarantees a complete avalanche of all the
110 * bits in the seed - IOW, by the time we are hashing the
111 * four state vectors should be completely different and utterly
112 * uncognizable from the input seed bits */
d68aa7aa
JH
113 STADTX_SCRAMBLE64(state[0],UINT64_C(0x801178846e899d17));
114 STADTX_SCRAMBLE64(state[0],UINT64_C(0xdd51e5d1c9a5a151));
115 STADTX_SCRAMBLE64(state[1],UINT64_C(0x93a7d6c8c62e4835));
116 STADTX_SCRAMBLE64(state[1],UINT64_C(0x803340f36895c2b5));
117 STADTX_SCRAMBLE64(state[2],UINT64_C(0xbea9344eb7565eeb));
118 STADTX_SCRAMBLE64(state[2],UINT64_C(0xcd95d1e509b995cd));
119 STADTX_SCRAMBLE64(state[3],UINT64_C(0x9999791977e30c13));
120 STADTX_SCRAMBLE64(state[3],UINT64_C(0xaab8b6b05abfc6cd));
9d5e3f1a
YO
121}
122
d68aa7aa
JH
123#define STADTX_K0_U64 UINT64_C(0xb89b0f8e1655514f)
124#define STADTX_K1_U64 UINT64_C(0x8c6f736011bd5127)
125#define STADTX_K2_U64 UINT64_C(0x8f29bd94edce7b39)
126#define STADTX_K3_U64 UINT64_C(0x9c1b8e1e9628323f)
9d5e3f1a
YO
127
128#define STADTX_K2_U32 0x802910e3
129#define STADTX_K3_U32 0x819b13af
130#define STADTX_K4_U32 0x91cb27e5
131#define STADTX_K5_U32 0xc1a269c1
132
133STADTX_STATIC_INLINE U64 stadtx_hash_with_state(
134 const U8 *state_ch,
135 const U8 *key,
136 const STRLEN key_len
137) {
138 U64 *state= (U64 *)state_ch;
9995b99e 139 STRLEN len = key_len;
9d5e3f1a
YO
140 U64 v0= state[0] ^ ((key_len+1) * STADTX_K0_U64);
141 U64 v1= state[1] ^ ((key_len+2) * STADTX_K1_U64);
142 if (len < 32) {
143 switch(len >> 3) {
144 case 3:
145 v0 += U8TO64_LE(key) * STADTX_K3_U64;
146 v0= ROTR64(v0, 17) ^ v1;
147 v1= ROTR64(v1, 53) + v0;
148 key += 8;
b2733f8f 149 /* FALLTHROUGH */
9d5e3f1a
YO
150 case 2:
151 v0 += U8TO64_LE(key) * STADTX_K3_U64;
152 v0= ROTR64(v0, 17) ^ v1;
153 v1= ROTR64(v1, 53) + v0;
154 key += 8;
b2733f8f 155 /* FALLTHROUGH */
9d5e3f1a
YO
156 case 1:
157 v0 += U8TO64_LE(key) * STADTX_K3_U64;
158 v0= ROTR64(v0, 17) ^ v1;
159 v1= ROTR64(v1, 53) + v0;
160 key += 8;
b2733f8f 161 /* FALLTHROUGH */
9d5e3f1a
YO
162 case 0:
163 default: break;
164 }
165 switch ( len & 0x7 ) {
166 case 7: v0 += (U64)key[6] << 32;
b2733f8f 167 /* FALLTHROUGH */
9d5e3f1a 168 case 6: v1 += (U64)key[5] << 48;
b2733f8f 169 /* FALLTHROUGH */
9d5e3f1a 170 case 5: v0 += (U64)key[4] << 16;
b2733f8f 171 /* FALLTHROUGH */
9d5e3f1a
YO
172 case 4: v1 += (U64)U8TO32_LE(key);
173 break;
174 case 3: v0 += (U64)key[2] << 48;
b2733f8f 175 /* FALLTHROUGH */
9d5e3f1a
YO
176 case 2: v1 += (U64)U8TO16_LE(key);
177 break;
178 case 1: v0 += (U64)key[0];
b2733f8f 179 /* FALLTHROUGH */
9d5e3f1a
YO
180 case 0: v1 = ROTL64(v1, 32) ^ 0xFF;
181 break;
182 }
183 v1 ^= v0;
184 v0 = ROTR64(v0,33) + v1;
185 v1 = ROTL64(v1,17) ^ v0;
186 v0 = ROTL64(v0,43) + v1;
187 v1 = ROTL64(v1,31) - v0;
188 v0 = ROTL64(v0,13) ^ v1;
189 v1 -= v0;
190 v0 = ROTL64(v0,41) + v1;
191 v1 = ROTL64(v1,37) ^ v0;
192 v0 = ROTR64(v0,39) + v1;
193 v1 = ROTR64(v1,15) + v0;
194 v0 = ROTL64(v0,15) ^ v1;
195 v1 = ROTR64(v1, 5);
196 return v0 ^ v1;
197 } else {
198 U64 v2= state[2] ^ ((key_len+3) * STADTX_K2_U64);
199 U64 v3= state[3] ^ ((key_len+4) * STADTX_K3_U64);
200
201 do {
202 v0 += (U64)U8TO64_LE(key+ 0) * STADTX_K2_U32; v0= ROTL64(v0,57) ^ v3;
203 v1 += (U64)U8TO64_LE(key+ 8) * STADTX_K3_U32; v1= ROTL64(v1,63) ^ v2;
204 v2 += (U64)U8TO64_LE(key+16) * STADTX_K4_U32; v2= ROTR64(v2,47) + v0;
205 v3 += (U64)U8TO64_LE(key+24) * STADTX_K5_U32; v3= ROTR64(v3,11) - v1;
206 key += 32;
207 len -= 32;
208 } while ( len >= 32 );
209
210 switch ( len >> 3 ) {
211 case 3: v0 += ((U64)U8TO64_LE(key) * STADTX_K2_U32); key += 8; v0= ROTL64(v0,57) ^ v3;
b2733f8f 212 /* FALLTHROUGH */
9d5e3f1a 213 case 2: v1 += ((U64)U8TO64_LE(key) * STADTX_K3_U32); key += 8; v1= ROTL64(v1,63) ^ v2;
b2733f8f 214 /* FALLTHROUGH */
9d5e3f1a 215 case 1: v2 += ((U64)U8TO64_LE(key) * STADTX_K4_U32); key += 8; v2= ROTR64(v2,47) + v0;
b2733f8f 216 /* FALLTHROUGH */
9d5e3f1a 217 case 0: v3 = ROTR64(v3,11) - v1;
b2733f8f 218 /* FALLTHROUGH */
9d5e3f1a
YO
219 }
220 v0 ^= (len+1) * STADTX_K3_U64;
221 switch ( len & 0x7 ) {
222 case 7: v1 += (U64)key[6];
b2733f8f 223 /* FALLTHROUGH */
9d5e3f1a
YO
224 case 6: v2 += (U64)U8TO16_LE(key+4);
225 v3 += (U64)U8TO32_LE(key);
226 break;
227 case 5: v1 += (U64)key[4];
b2733f8f 228 /* FALLTHROUGH */
9d5e3f1a
YO
229 case 4: v2 += (U64)U8TO32_LE(key);
230 break;
231 case 3: v3 += (U64)key[2];
b2733f8f 232 /* FALLTHROUGH */
9d5e3f1a
YO
233 case 2: v1 += (U64)U8TO16_LE(key);
234 break;
235 case 1: v2 += (U64)key[0];
b2733f8f 236 /* FALLTHROUGH */
9d5e3f1a
YO
237 case 0: v3 = ROTL64(v3, 32) ^ 0xFF;
238 break;
239 }
240
241 v1 -= v2;
242 v0 = ROTR64(v0,19);
243 v1 -= v0;
244 v1 = ROTR64(v1,53);
245 v3 ^= v1;
246 v0 -= v3;
247 v3 = ROTL64(v3,43);
248 v0 += v3;
249 v0 = ROTR64(v0, 3);
250 v3 -= v0;
251 v2 = ROTR64(v2,43) - v3;
252 v2 = ROTL64(v2,55) ^ v0;
253 v1 -= v2;
254 v3 = ROTR64(v3, 7) - v2;
255 v2 = ROTR64(v2,31);
256 v3 += v2;
257 v2 -= v1;
258 v3 = ROTR64(v3,39);
259 v2 ^= v3;
260 v3 = ROTR64(v3,17) ^ v2;
261 v1 += v3;
262 v1 = ROTR64(v1, 9);
263 v2 ^= v1;
264 v2 = ROTL64(v2,24);
265 v3 ^= v2;
266 v3 = ROTR64(v3,59);
267 v0 = ROTR64(v0, 1) - v1;
268
269 return v0 ^ v1 ^ v2 ^ v3;
270 }
271}
272
273STADTX_STATIC_INLINE U64 stadtx_hash(
274 const U8 *seed_ch,
275 const U8 *key,
276 const STRLEN key_len
277) {
278 U64 state[4];
279 stadtx_seed_state(seed_ch,(U8*)state);
280 return stadtx_hash_with_state((U8*)state,key,key_len);
281}
282
283#endif