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 /* 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      *
 138      * PI value in hex from here:
 139      *
 140      * http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/pibases.html
 141      *
 142      * Ensure that the three state vectors are nonzero regardless of
 143      * the seed. The idea of these two steps is to ensure that the 0
 144      * state comes from a seed utterly unlike that of the value we
 145      * replace it with.
 146      */
 147     state[0]= seed[0] ^ 0x43f6a888;
 148     state[1]= seed[1] ^ 0x5a308d31;
 149     state[2]= seed[2] ^ 0x3198a2e0;
 150     if (!state[0]) state[0] = 1;
 151     if (!state[1]) state[1] = 2;
 152     if (!state[2]) state[2] = 4;
 153     /* these are pseudo-randomly selected primes between 2**31 and 2**32
 154      * (I generated a big list and then randomly chose some from the list) */
 155     ZAPHOD32_SCRAMBLE32(state[0],0x9fade23b);
 156     ZAPHOD32_SCRAMBLE32(state[1],0xaa6f908d);
 157     ZAPHOD32_SCRAMBLE32(state[2],0xcdf6b72d);
 158
 159     /* now that we have scrambled we do some mixing to avalanche the
 160      * state bits to gether */
 161     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 1/4");
 162     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 2/4");
 163     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 3/4");
 164     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE A 4/4");
 165
 166     /* and then scramble them again with different primes */
 167     ZAPHOD32_SCRAMBLE32(state[0],0xc95d22a9);
 168     ZAPHOD32_SCRAMBLE32(state[1],0x8497242b);
 169     ZAPHOD32_SCRAMBLE32(state[2],0x9c5cc4e9);
 170
 171     /* and a thorough final mix */
 172     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 1/5");
 173     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 2/5");
 174     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 3/5");
 175     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 4/5");
 176     ZAPHOD32_MIX(state[0],state[1],state[2],"ZAPHOD32 SEED-STATE B 5/5");
 177
 178 }
 179
 180 ZAPHOD32_STATIC_INLINE
 181 U32 zaphod32_hash_with_state(
 182     const U8 *state_ch,
 183     const U8 *key,
 184     const STRLEN key_len
 185 ) {
 186     const U32 *state= (const U32 *)state_ch;
 187     const U8 *end;
 188     STRLEN len = key_len;
 189     U32 v0= state[0];
 190     U32 v1= state[1];
 191     U32 v2= state[2] ^ (0xC41A7AB1 * ((U32)key_len + 1));
 192
 193     ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x ln=%08x HASH START\n",
 194             (unsigned int)state[0], (unsigned int)state[1],
 195             (unsigned int)state[2], (unsigned int)key_len);
 196     {
 197         switch (len) {
 198             default: goto zaphod32_read8;
 199             case 12: v2 += (U32)key[11] << 24;  /* FALLTHROUGH */
 200             case 11: v2 += (U32)key[10] << 16;  /* FALLTHROUGH */
 201             case 10: v2 += (U32)U8TO16_LE(key+8);
 202                      v1 -= U8TO32_LE(key+4);
 203                      v0 += U8TO32_LE(key+0);
 204                      goto zaphod32_finalize;
 205             case 9: v2 += (U32)key[8];          /* FALLTHROUGH */
 206             case 8: v1 -= U8TO32_LE(key+4);
 207                     v0 += U8TO32_LE(key+0);
 208                     goto zaphod32_finalize;
 209             case 7: v2 += (U32)key[6];          /* FALLTHROUGH */
 210             case 6: v0 += (U32)U8TO16_LE(key+4);
 211                     v1 -= U8TO32_LE(key+0);
 212                     goto zaphod32_finalize;
 213             case 5: v0 += (U32)key[4];          /* FALLTHROUGH */
 214             case 4: v1 -= U8TO32_LE(key+0);
 215                     goto zaphod32_finalize;
 216             case 3: v2 += (U32)key[2];          /* FALLTHROUGH */
 217             case 2: v0 += (U32)U8TO16_LE(key);
 218                     break;
 219             case 1: v0 += (U32)key[0];
 220                     break;
 221             case 0: v2 ^= 0xFF;
 222                     break;
 223
 224         }
 225         v0 -= v2;
 226         v2 = ROTL32(v2, 8) ^ v0;
 227         v0 = ROTR32(v0,16) + v2;
 228         v2 += v0;
 229         v0 += v0 >> 9;
 230         v0 += v2;
 231         v2 ^= v0;
 232         v2 += v2 << 4;
 233         v0 -= v2;
 234         v2 = ROTR32(v2, 8) ^ v0;
 235         v0 = ROTL32(v0,16) ^ v2;
 236         v2 = ROTL32(v2,10) + v0;
 237         v0 = ROTR32(v0,30) + v2;
 238         v2 = ROTR32(v2,12);
 239         return v0 ^ v2;
 240     }
 241
 242 /*  if (len >= 8) */ /* this block is only reached by a goto above, so this condition
 243                         is commented out, but if the above block is removed it would
 244                         be necessary to use this. */
 245     {
 246 zaphod32_read8:
 247         len = key_len & 0x7;
 248         end = key + key_len - len;
 249         do {
 250             v1 -= U8TO32_LE(key+0);
 251             v0 += U8TO32_LE(key+4);
 252             ZAPHOD32_MIX(v0,v1,v2,"MIX 2-WORDS A");
 253             key += 8;
 254         } while ( key < end );
 255     }
 256
 257     if ( len >= 4 ) {
 258         v1 -= U8TO32_LE(key);
 259         key += 4;
 260     }
 261
 262     v0 += (U32)(key_len) << 24;
 263     switch (len & 0x3) {
 264         case 3: v2 += (U32)key[2];          /* FALLTHROUGH */
 265         case 2: v0 += (U32)U8TO16_LE(key);
 266                 break;
 267         case 1: v0 += (U32)key[0];
 268                 break;
 269         case 0: v2 ^= 0xFF;
 270                 break;
 271     }
 272 zaphod32_finalize:
 273     ZAPHOD32_FINALIZE(v0,v1,v2);
 274
 275     ZAPHOD32_WARN4("v0=%08x v1=%08x v2=%08x hh=%08x - FINAL\n\n",
 276             (unsigned int)v0, (unsigned int)v1, (unsigned int)v2,
 277             (unsigned int)v0 ^ v1 ^ v2);
 278
 279     return v0 ^ v1 ^ v2;
 280 }
 281
 282 ZAPHOD32_STATIC_INLINE U32 zaphod32_hash(
 283     const U8 *seed_ch,
 284     const U8 *key,
 285     const STRLEN key_len
 286 ) {
 287     U32 state[3];
 288     zaphod32_seed_state(seed_ch,(U8*)state);
 289     return zaphod32_hash_with_state((U8*)state,key,key_len);
 290 }
 291
 292 #endif