libyasm/phash.c

   1 /* Modified for use with yasm by Peter Johnson. */
   2 #include "util.h"
   3
   4 /*
   5 --------------------------------------------------------------------
   6 lookupa.c, by Bob Jenkins, December 1996.  Same as lookup2.c
   7 Use this code however you wish.  Public Domain.  No warranty.
   8 Source is http://burtleburtle.net/bob/c/lookupa.c
   9 --------------------------------------------------------------------
  10 */
  11 #include "phash.h"
  12
  13 #define ub4 unsigned long
  14
  15 #define hashsize(n) ((ub4)1<<(n))
  16 #define hashmask(n) (hashsize(n)-1)
  17
  18 /*
  19 --------------------------------------------------------------------
  20 mix -- mix 3 32-bit values reversibly.
  21 For every delta with one or two bit set, and the deltas of all three
  22   high bits or all three low bits, whether the original value of a,b,c
  23   is almost all zero or is uniformly distributed,
  24 * If mix() is run forward or backward, at least 32 bits in a,b,c
  25   have at least 1/4 probability of changing.
  26 * If mix() is run forward, every bit of c will change between 1/3 and
  27   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
  28 mix() was built out of 36 single-cycle latency instructions in a
  29   structure that could supported 2x parallelism, like so:
  30       a -= b;
  31       a -= c; x = (c>>13);
  32       b -= c; a ^= x;
  33       b -= a; x = (a<<8);
  34       c -= a; b ^= x;
  35       c -= b; x = (b>>13);
  36       ...
  37   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
  38   of that parallelism.  They've also turned some of those single-cycle
  39   latency instructions into multi-cycle latency instructions.  Still,
  40   this is the fastest good hash I could find.  There were about 2^^68
  41   to choose from.  I only looked at a billion or so.
  42 --------------------------------------------------------------------
  43 */
  44 #define mix(a,b,c) \
  45 { \
  46     a -= b; a -= c; a ^= (c>>13); \
  47     a &= 0xffffffff; \
  48     b -= c; b -= a; b ^= (a<<8); \
  49     b &= 0xffffffff; \
  50     c -= a; c -= b; c ^= (b>>13); \
  51     c &= 0xffffffff; \
  52     a -= b; a -= c; a ^= (c>>12);  \
  53     a &= 0xffffffff; \
  54     b -= c; b -= a; b ^= (a<<16); \
  55     b &= 0xffffffff; \
  56     c -= a; c -= b; c ^= (b>>5); \
  57     c &= 0xffffffff; \
  58     a -= b; a -= c; a ^= (c>>3);  \
  59     a &= 0xffffffff; \
  60     b -= c; b -= a; b ^= (a<<10); \
  61     b &= 0xffffffff; \
  62     c -= a; c -= b; c ^= (b>>15); \
  63     c &= 0xffffffff; \
  64 }
  65
  66 /*
  67 --------------------------------------------------------------------
  68 lookup() -- hash a variable-length key into a 32-bit value
  69   k     : the key (the unaligned variable-length array of bytes)
  70   len   : the length of the key, counting by bytes
  71   level : can be any 4-byte value
  72 Returns a 32-bit value.  Every bit of the key affects every bit of
  73 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
  74 About 6len+35 instructions.
  75
  76 The best hash table sizes are powers of 2.  There is no need to do
  77 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
  78 use a bitmask.  For example, if you need only 10 bits, do
  79   h = (h & hashmask(10));
  80 In which case, the hash table should have hashsize(10) elements.
  81
  82 If you are hashing n strings (ub1 **)k, do it like this:
  83   for (i=0, h=0; i<n; ++i) h = lookup( k[i], len[i], h);
  84
  85 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
  86 code any way you wish, private, educational, or commercial.
  87
  88 See http://burtleburtle.net/bob/hash/evahash.html
  89 Use for hash table lookup, or anything where one collision in 2^32 is
  90 acceptable.  Do NOT use for cryptographic purposes.
  91 --------------------------------------------------------------------
  92 */
  93
  94 unsigned long
  95 phash_lookup(
  96     register const char *sk, /* the key */
  97     register size_t length,   /* the length of the key */
  98     register unsigned long level) /* the previous hash, or an arbitrary value */
  99 {
 100     register unsigned long a,b,c;
 101     register size_t len;
 102     register const unsigned char *k = (const unsigned char *)sk;
 103
 104     /* Set up the internal state */
 105     len = length;
 106     a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 107     c = level;           /* the previous hash value */
 108
 109     /*---------------------------------------- handle most of the key */
 110     while (len >= 12)
 111     {
 112         a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
 113         a &= 0xffffffff;
 114         b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
 115         b &= 0xffffffff;
 116         c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
 117         c &= 0xffffffff;
 118         mix(a,b,c);
 119         k += 12; len -= 12;
 120     }
 121
 122     /*------------------------------------- handle the last 11 bytes */
 123     c += (ub4)length;
 124     switch(len)              /* all the case statements fall through */
 125     {
 126         case 11: c+=((ub4)k[10]<<24);
 127         case 10: c+=((ub4)k[9]<<16);
 128         case 9 : c+=((ub4)k[8]<<8);
 129                  c &= 0xffffffff;
 130             /* the first byte of c is reserved for the length */
 131         case 8 : b+=((ub4)k[7]<<24);
 132         case 7 : b+=((ub4)k[6]<<16);
 133         case 6 : b+=((ub4)k[5]<<8);
 134         case 5 : b+=k[4];
 135                  b &= 0xffffffff;
 136         case 4 : a+=((ub4)k[3]<<24);
 137         case 3 : a+=((ub4)k[2]<<16);
 138         case 2 : a+=((ub4)k[1]<<8);
 139         case 1 : a+=k[0];
 140                  a &= 0xffffffff;
 141         /* case 0: nothing left to add */
 142     }
 143     mix(a,b,c);
 144     /*-------------------------------------------- report the result */
 145     return c;
 146 }
 147
 148
 149 /*
 150 --------------------------------------------------------------------
 151 mixc -- mixc 8 4-bit values as quickly and thoroughly as possible.
 152 Repeating mix() three times achieves avalanche.
 153 Repeating mix() four times eliminates all funnels and all
 154   characteristics stronger than 2^{-11}.
 155 --------------------------------------------------------------------
 156 */
 157 #define mixc(a,b,c,d,e,f,g,h) \
 158 { \
 159     a^=b<<11; d+=a; b+=c; \
 160     b^=c>>2;  e+=b; c+=d; \
 161     c^=d<<8;  f+=c; d+=e; \
 162     d^=e>>16; g+=d; e+=f; \
 163     e^=f<<10; h+=e; f+=g; \
 164     f^=g>>4;  a+=f; g+=h; \
 165     g^=h<<8;  b+=g; h+=a; \
 166     h^=a>>9;  c+=h; a+=b; \
 167 }
 168
 169 /*
 170 --------------------------------------------------------------------
 171 checksum() -- hash a variable-length key into a 256-bit value
 172   k     : the key (the unaligned variable-length array of bytes)
 173   len   : the length of the key, counting by bytes
 174   state : an array of CHECKSTATE 4-byte values (256 bits)
 175 The state is the checksum.  Every bit of the key affects every bit of
 176 the state.  There are no funnels.  About 112+6.875len instructions.
 177
 178 If you are hashing n strings (ub1 **)k, do it like this:
 179   for (i=0; i<8; ++i) state[i] = 0x9e3779b9;
 180   for (i=0, h=0; i<n; ++i) checksum( k[i], len[i], state);
 181
 182 (c) Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 183 code any way you wish, private, educational, or commercial, as long
 184 as this whole comment accompanies it.
 185
 186 See http://burtleburtle.net/bob/hash/evahash.html
 187 Use to detect changes between revisions of documents, assuming nobody
 188 is trying to cause collisions.  Do NOT use for cryptography.
 189 --------------------------------------------------------------------
 190 */
 191 void
 192 phash_checksum(
 193     register const char *sk,
 194     register size_t len,
 195     register unsigned long *state)
 196 {
 197     register unsigned long a,b,c,d,e,f,g,h;
 198     register size_t length;
 199     register const unsigned char *k = (const unsigned char *)sk;
 200
 201     /* Use the length and level; add in the golden ratio. */
 202     length = len;
 203     a=state[0]; b=state[1]; c=state[2]; d=state[3];
 204     e=state[4]; f=state[5]; g=state[6]; h=state[7];
 205
 206     /*---------------------------------------- handle most of the key */
 207     while (len >= 32)
 208     {
 209         a += (k[0] +(k[1]<<8) +(k[2]<<16) +(k[3]<<24));
 210         b += (k[4] +(k[5]<<8) +(k[6]<<16) +(k[7]<<24));
 211         c += (k[8] +(k[9]<<8) +(k[10]<<16)+(k[11]<<24));
 212         d += (k[12]+(k[13]<<8)+(k[14]<<16)+(k[15]<<24));
 213         e += (k[16]+(k[17]<<8)+(k[18]<<16)+(k[19]<<24));
 214         f += (k[20]+(k[21]<<8)+(k[22]<<16)+(k[23]<<24));
 215         g += (k[24]+(k[25]<<8)+(k[26]<<16)+(k[27]<<24));
 216         h += (k[28]+(k[29]<<8)+(k[30]<<16)+(k[31]<<24));
 217         mixc(a,b,c,d,e,f,g,h);
 218         mixc(a,b,c,d,e,f,g,h);
 219         mixc(a,b,c,d,e,f,g,h);
 220         mixc(a,b,c,d,e,f,g,h);
 221         k += 32; len -= 32;
 222     }
 223
 224     /*------------------------------------- handle the last 31 bytes */
 225     h += (ub4)length;
 226     switch(len)
 227     {
 228         case 31: h+=(k[30]<<24);
 229         case 30: h+=(k[29]<<16);
 230         case 29: h+=(k[28]<<8);
 231         case 28: g+=(k[27]<<24);
 232         case 27: g+=(k[26]<<16);
 233         case 26: g+=(k[25]<<8);
 234         case 25: g+=k[24];
 235         case 24: f+=(k[23]<<24);
 236         case 23: f+=(k[22]<<16);
 237         case 22: f+=(k[21]<<8);
 238         case 21: f+=k[20];
 239         case 20: e+=(k[19]<<24);
 240         case 19: e+=(k[18]<<16);
 241         case 18: e+=(k[17]<<8);
 242         case 17: e+=k[16];
 243         case 16: d+=(k[15]<<24);
 244         case 15: d+=(k[14]<<16);
 245         case 14: d+=(k[13]<<8);
 246         case 13: d+=k[12];
 247         case 12: c+=(k[11]<<24);
 248         case 11: c+=(k[10]<<16);
 249         case 10: c+=(k[9]<<8);
 250         case 9 : c+=k[8];
 251         case 8 : b+=(k[7]<<24);
 252         case 7 : b+=(k[6]<<16);
 253         case 6 : b+=(k[5]<<8);
 254         case 5 : b+=k[4];
 255         case 4 : a+=(k[3]<<24);
 256         case 3 : a+=(k[2]<<16);
 257         case 2 : a+=(k[1]<<8);
 258         case 1 : a+=k[0];
 259     }
 260     mixc(a,b,c,d,e,f,g,h);
 261     mixc(a,b,c,d,e,f,g,h);
 262     mixc(a,b,c,d,e,f,g,h);
 263     mixc(a,b,c,d,e,f,g,h);
 264
 265     /*-------------------------------------------- report the result */
 266     state[0]=a; state[1]=b; state[2]=c; state[3]=d;
 267     state[4]=e; state[5]=f; state[6]=g; state[7]=h;
 268 }