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 323