| 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 |