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 /* This is two marsaglia xor-shift permutes, with a prime-multiple 78 * sandwiched inside. The end result of doing this twice with different 79 * primes is a completely avalanched v. */ 80 #define ZAPHOD32_SCRAMBLE32(v,prime) STMT_START { \ 81 v ^= (v>>9); \ 82 v ^= (v<<21); \ 83 v ^= (v>>16); \ 84 v *= prime; \ 85 v ^= (v>>17); \ 86 v ^= (v<<15); \ 87 v ^= (v>>23); \ 88 } STMT_END 89 90 #define ZAPHOD32_FINALIZE(v0,v1,v2) STMT_START { \ 91 ZAPHOD32_WARN3("v0=%08x v1=%08x v2=%08x - ZAPHOD32 FINALIZE\n", \ 92 (unsigned int)v0, (unsigned int)v1, (unsigned int)v2); \ 93 v2 += v0; \ 94 v1 -= v2; \ 95 v1 = ROTL32(v1, 6); \ 96 v2 ^= v1; \ 97 v2 = ROTL32(v2, 28); \ 98 v1 ^= v2; \ 99 v0 += v1; \ 100 v1 = ROTL32(v1, 24); \ 101 v2 += v1; \ 102 v2 = ROTL32(v2, 18) + v1; \ 103 v0 ^= v2; \ 104 v0 = ROTL32(v0, 20); \ 105 v2 += v0; \ 106 v1 ^= v2; \ 107 v0 += v1; \ 108 v0 = ROTL32(v0, 5); \ 109 v2 += v0; \ 110 v2 = ROTL32(v2, 22); \ 111 v0 -= v1; \ 112 v1 -= v2; \ 113 v1 = ROTL32(v1, 17); \ 114 } STMT_END 115 116 #define ZAPHOD32_MIX(v0,v1,v2,text) STMT_START { \ 117 ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x - ZAPHOD32 %s MIX\n", \ 118 (unsigned int)v0,(unsigned int)v1,(unsigned int)v2, text ); \ 119 v0 = ROTL32(v0,16) - v2; \ 120 v1 = ROTR32(v1,13) ^ v2; \ 121 v2 = ROTL32(v2,17) + v1; \ 122 v0 = ROTR32(v0, 2) + v1; \ 123 v1 = ROTR32(v1,17) - v0; \ 124 v2 = ROTR32(v2, 7) ^ v0; \ 125 } STMT_END 126 127 128 ZAPHOD32_STATIC_INLINE 129 void zaphod32_seed_state ( 130 const U8 *seed_ch, 131 U8 *state_ch 132 ) { 133 const U32 *seed= (const U32 *)seed_ch; 134 U32 *state= (U32 *)state_ch; 135 136 /* hex expansion of pi, skipping first two digits. pi= 3.2[43f6...]*/ 137 /* pi value in hex from here: 138 * http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html*/ 139 /* Ensure that the three state vectors are nonzero regardless of the seed. */ 140 /* The idea of these two steps is to ensure that the 0 state comes from a seed 141 * utterly unlike that of the value we replace it with.*/ 142 state[0]= seed[0] ^ 0x43f6a888; 143 state[1]= seed[1] ^ 0x5a308d31; 144 state[2]= seed[2] ^ 0x3198a2e0; 145 if (!state[0]) state[0] = 1; 146 if (!state[1]) state[1] = 2; 147 if (!state[2]) state[2] = 4; 148 /* these are pseduo-randomly selected primes between 2**31 and 2**32 149 * (I generated a big list and then randomly chose some from the list) */ 150 ZAPHOD32_SCRAMBLE32(state[0],0x9fade23b); 151 ZAPHOD32_SCRAMBLE32(state[1],0xaa6f908d); 152 ZAPHOD32_SCRAMBLE32(state[2],0xcdf6b72d); 153 154 /* now that we have scrambled we do some mixing to avalanche the 155 * state bits to gether */ 156 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 1/4"); 157 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 2/4"); 158 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 3/4"); 159 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 4/4"); 160 161 /* and then scramble them again with different primes */ 162 ZAPHOD32_SCRAMBLE32(state[0],0xc95d22a9); 163 ZAPHOD32_SCRAMBLE32(state[1],0x8497242b); 164 ZAPHOD32_SCRAMBLE32(state[2],0x9c5cc4e9); 165 166 /* and a thorough final mix */ 167 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 1/5"); 168 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 2/5"); 169 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 3/5"); 170 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 4/5"); 171 ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 5/5"); 172 173 } 174 175 ZAPHOD32_STATIC_INLINE 176 U32 zaphod32_hash_with_state( 177 const U8 *state_ch, 178 const U8 *key, 179 const STRLEN key_len 180 ) { 181 U32 *state= (U32 *)state_ch; 182 const U8 *end; 183 STRLEN len = key_len; 184 U32 v0= state[0]; 185 U32 v1= state[1]; 186 U32 v2= state[2] ^ (0xC41A7AB1 * ((U32)key_len + 1)); 187 188 ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x ln=%08x HASH START\n", 189 (unsigned int)state[0], (unsigned int)state[1], 190 (unsigned int)state[2], (unsigned int)key_len); 191 { 192 switch (len) { 193 default: goto zaphod32_read8; 194 case 12: v2 += (U32)key[11] << 24; /* FALLTHROUGH */ 195 case 11: v2 += (U32)key[10] << 16; /* FALLTHROUGH */ 196 case 10: v2 += (U32)U8TO16_LE(key+8); 197 v1 -= U8TO32_LE(key+4); 198 v0 += U8TO32_LE(key+0); 199 goto zaphod32_finalize; 200 case 9: v2 += (U32)key[8]; /* FALLTHROUGH */ 201 case 8: v1 -= U8TO32_LE(key+4); 202 v0 += U8TO32_LE(key+0); 203 goto zaphod32_finalize; 204 case 7: v2 += (U32)key[6]; /* FALLTHROUGH */ 205 case 6: v0 += (U32)U8TO16_LE(key+4); 206 v1 -= U8TO32_LE(key+0); 207 goto zaphod32_finalize; 208 case 5: v0 += (U32)key[4]; /* FALLTHROUGH */ 209 case 4: v1 -= U8TO32_LE(key+0); 210 goto zaphod32_finalize; 211 case 3: v2 += (U32)key[2]; /* FALLTHROUGH */ 212 case 2: v0 += (U32)U8TO16_LE(key); 213 break; 214 case 1: v0 += (U32)key[0]; 215 break; 216 case 0: v2 ^= 0xFF; 217 break; 218 219 } 220 v0 -= v2; 221 v2 = ROTL32(v2, 8) ^ v0; 222 v0 = ROTR32(v0,16) + v2; 223 v2 += v0; 224 v0 += v0 >> 9; 225 v0 += v2; 226 v2 ^= v0; 227 v2 += v2 << 4; 228 v0 -= v2; 229 v2 = ROTR32(v2, 8) ^ v0; 230 v0 = ROTL32(v0,16) ^ v2; 231 v2 = ROTL32(v2,10) + v0; 232 v0 = ROTR32(v0,30) + v2; 233 v2 = ROTR32(v2,12); 234 return v0 ^ v2; 235 } 236 237 /* if (len >= 8) */ /* this block is only reached by a goto above, so this condition 238 is commented out, but if the above block is removed it would 239 be necessary to use this. */ 240 { 241 zaphod32_read8: 242 len = key_len & 0x7; 243 end = key + key_len - len; 244 do { 245 v1 -= U8TO32_LE(key+0); 246 v0 += U8TO32_LE(key+4); 247 ZAPHOD32_MIX(v0,v1,v2,"MIX 2-WORDS A"); 248 key += 8; 249 } while ( key < end ); 250 } 251 252 if ( len >= 4 ) { 253 v1 -= U8TO32_LE(key); 254 key += 4; 255 } 256 257 v0 += (U32)(key_len) << 24; 258 switch (len & 0x3) { 259 case 3: v2 += (U32)key[2]; /* FALLTHROUGH */ 260 case 2: v0 += (U32)U8TO16_LE(key); 261 break; 262 case 1: v0 += (U32)key[0]; 263 break; 264 case 0: v2 ^= 0xFF; 265 break; 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 288