applications/test/HashingSpeed/Test-HashingSpeed.C

   1 // code taken more-or-less from Paul Hsieh's tests
   2
   3 #include "Hasher.H"
   4
   5 #include <stdio.h>
   6 #include <time.h>
   7
   8 #ifndef CLOCKS_PER_SEC
   9 # ifdef CLK_TCK
  10 #  define CLOCKS_PER_SEC (CLK_TCK)
  11 # endif
  12 #endif
  13
  14 #undef mix
  15 #undef rot
  16
  17 /*
  18 -------------------------------------------------------------------------------
  19 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  20
  21 These are functions for producing 32-bit hashes for hash table lookup.
  22 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
  23 are externally useful functions.  Routines to test the hash are included
  24 if SELF_TEST is defined.  You can use this free for any purpose.  It's in
  25 the public domain.  It has no warranty.
  26
  27 You probably want to use hashlittle().  hashlittle() and hashbig()
  28 hash byte arrays.  hashlittle() is is faster than hashbig() on
  29 little-endian machines.  Intel and AMD are little-endian machines.
  30 On second thought, you probably want hashlittle2(), which is identical to
  31 hashlittle() except it returns two 32-bit hashes for the price of one.
  32 You could implement hashbig2() if you wanted but I haven't bothered here.
  33
  34 If you want to find a hash of, say, exactly 7 integers, do
  35   a = i1;  b = i2;  c = i3;
  36   mix(a,b,c);
  37   a += i4; b += i5; c += i6;
  38   mix(a,b,c);
  39   a += i7;
  40   final(a,b,c);
  41 then use c as the hash value.  If you have a variable length array of
  42 4-byte integers to hash, use hashword().  If you have a byte array (like
  43 a character string), use hashlittle().  If you have several byte arrays, or
  44 a mix of things, see the comments above hashlittle().
  45
  46 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
  47 then mix those integers.  This is fast (you can do a lot more thorough
  48 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
  49 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
  50 -------------------------------------------------------------------------------
  51 */
  52
  53 #include <stdio.h>      /* defines printf for tests */
  54 #include <time.h>       /* defines time_t for timings in the test */
  55 #include <stdint.h>     /* defines uint32_t etc */
  56 #include <sys/param.h>  /* attempt to define endianness */
  57 #ifdef linux
  58 # include <endian.h>    /* attempt to define endianness */
  59 #endif
  60
  61 /*
  62  * My best guess at if you are big-endian or little-endian.  This may
  63  * need adjustment.
  64  */
  65 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
  66      __BYTE_ORDER == __LITTLE_ENDIAN) || \
  67     (defined(i386) || defined(__i386__) || defined(__i486__) || \
  68      defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
  69 # define HASH_LITTLE_ENDIAN 1
  70 # define HASH_BIG_ENDIAN 0
  71 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
  72        __BYTE_ORDER == __BIG_ENDIAN) || \
  73       (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
  74 # define HASH_LITTLE_ENDIAN 0
  75 # define HASH_BIG_ENDIAN 1
  76 #else
  77 # define HASH_LITTLE_ENDIAN 0
  78 # define HASH_BIG_ENDIAN 0
  79 #endif
  80
  81 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
  82
  83 /*
  84 -------------------------------------------------------------------------------
  85 mix -- mix 3 32-bit values reversibly.
  86
  87 This is reversible, so any information in (a,b,c) before mix() is
  88 still in (a,b,c) after mix().
  89
  90 If four pairs of (a,b,c) inputs are run through mix(), or through
  91 mix() in reverse, there are at least 32 bits of the output that
  92 are sometimes the same for one pair and different for another pair.
  93 This was tested for:
  94 * pairs that differed by one bit, by two bits, in any combination
  95   of top bits of (a,b,c), or in any combination of bottom bits of
  96   (a,b,c).
  97 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  98   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  99   is commonly produced by subtraction) look like a single 1-bit
 100   difference.
 101 * the base values were pseudorandom, all zero but one bit set, or
 102   all zero plus a counter that starts at zero.
 103
 104 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
 105 satisfy this are
 106     4  6  8 16 19  4
 107     9 15  3 18 27 15
 108    14  9  3  7 17  3
 109 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
 110 for "differ" defined as + with a one-bit base and a two-bit delta.  I
 111 used http://burtleburtle.net/bob/hash/avalanche.html to choose
 112 the operations, constants, and arrangements of the variables.
 113
 114 This does not achieve avalanche.  There are input bits of (a,b,c)
 115 that fail to affect some output bits of (a,b,c), especially of a.  The
 116 most thoroughly mixed value is c, but it doesn't really even achieve
 117 avalanche in c.
 118
 119 This allows some parallelism.  Read-after-writes are good at doubling
 120 the number of bits affected, so the goal of mixing pulls in the opposite
 121 direction as the goal of parallelism.  I did what I could.  Rotates
 122 seem to cost as much as shifts on every machine I could lay my hands
 123 on, and rotates are much kinder to the top and bottom bits, so I used
 124 rotates.
 125 -------------------------------------------------------------------------------
 126 */
 127 #define mix(a,b,c) \
 128 { \
 129   a -= c;  a ^= rot(c, 4);  c += b; \
 130   b -= a;  b ^= rot(a, 6);  a += c; \
 131   c -= b;  c ^= rot(b, 8);  b += a; \
 132   a -= c;  a ^= rot(c,16);  c += b; \
 133   b -= a;  b ^= rot(a,19);  a += c; \
 134   c -= b;  c ^= rot(b, 4);  b += a; \
 135 }
 136
 137 /*
 138 -------------------------------------------------------------------------------
 139 final -- final mixing of 3 32-bit values (a,b,c) into c
 140
 141 Pairs of (a,b,c) values differing in only a few bits will usually
 142 produce values of c that look totally different.  This was tested for
 143 * pairs that differed by one bit, by two bits, in any combination
 144   of top bits of (a,b,c), or in any combination of bottom bits of
 145   (a,b,c).
 146 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 147   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 148   is commonly produced by subtraction) look like a single 1-bit
 149   difference.
 150 * the base values were pseudorandom, all zero but one bit set, or
 151   all zero plus a counter that starts at zero.
 152
 153 These constants passed:
 154  14 11 25 16 4 14 24
 155  12 14 25 16 4 14 24
 156 and these came close:
 157   4  8 15 26 3 22 24
 158  10  8 15 26 3 22 24
 159  11  8 15 26 3 22 24
 160 -------------------------------------------------------------------------------
 161 */
 162 #define final(a,b,c) \
 163 { \
 164     c ^= b; c -= rot(b, 14); \
 165     a ^= c; a -= rot(c, 11); \
 166     b ^= a; b -= rot(a, 25); \
 167     c ^= b; c -= rot(b, 16); \
 168     a ^= c; a -= rot(c, 4);  \
 169     b ^= a; b -= rot(a, 14); \
 170     c ^= b; c -= rot(b, 24); \
 171 }
 172
 173 /*
 174 --------------------------------------------------------------------
 175  This works on all machines.  To be useful, it requires
 176  -- that the key be an array of uint32_t's, and
 177  -- that the length be the number of uint32_t's in the key
 178
 179  The function hashword() is identical to hashlittle() on little-endian
 180  machines, and identical to hashbig() on big-endian machines,
 181  except that the length has to be measured in uint32_ts rather than in
 182  bytes.  hashlittle() is more complicated than hashword() only because
 183  hashlittle() has to dance around fitting the key bytes into registers.
 184 --------------------------------------------------------------------
 185 */
 186 uint32_t hashword(
 187 const uint32_t *k,                   /* the key, an array of uint32_t values */
 188 size_t          length,               /* the length of the key, in uint32_ts */
 189 uint32_t        initval)         /* the previous hash, or an arbitrary value */
 190 {
 191   uint32_t a,b,c;
 192
 193   /* Set up the internal state */
 194   a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
 195
 196   /*------------------------------------------------- handle most of the key */
 197   while (length > 3)
 198   {
 199     a += k[0];
 200     b += k[1];
 201     c += k[2];
 202     mix(a,b,c);
 203     length -= 3;
 204     k += 3;
 205   }
 206
 207   /*------------------------------------------- handle the last 3 uint32_t's */
 208   switch(length)                     /* all the case statements fall through */
 209   {
 210   case 3 : c+=k[2];
 211   case 2 : b+=k[1];
 212   case 1 : a+=k[0];
 213     final(a,b,c);
 214   case 0:     /* case 0: nothing left to add */
 215     break;
 216   }
 217   /*------------------------------------------------------ report the result */
 218   return c;
 219 }
 220
 221
 222 /*
 223 --------------------------------------------------------------------
 224 hashword2() -- same as hashword(), but take two seeds and return two
 225 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
 226 both be initialized with seeds.  If you pass in (*pb)==0, the output
 227 (*pc) will be the same as the return value from hashword().
 228 --------------------------------------------------------------------
 229 */
 230 void hashword2 (
 231 const uint32_t *k,                   /* the key, an array of uint32_t values */
 232 size_t          length,               /* the length of the key, in uint32_ts */
 233 uint32_t       *pc,                      /* IN: seed OUT: primary hash value */
 234 uint32_t       *pb)               /* IN: more seed OUT: secondary hash value */
 235 {
 236   uint32_t a,b,c;
 237
 238   /* Set up the internal state */
 239   a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
 240   c += *pb;
 241
 242   /*------------------------------------------------- handle most of the key */
 243   while (length > 3)
 244   {
 245     a += k[0];
 246     b += k[1];
 247     c += k[2];
 248     mix(a,b,c);
 249     length -= 3;
 250     k += 3;
 251   }
 252
 253   /*------------------------------------------- handle the last 3 uint32_t's */
 254   switch(length)                     /* all the case statements fall through */
 255   {
 256   case 3 : c+=k[2];
 257   case 2 : b+=k[1];
 258   case 1 : a+=k[0];
 259     final(a,b,c);
 260   case 0:     /* case 0: nothing left to add */
 261     break;
 262   }
 263   /*------------------------------------------------------ report the result */
 264   *pc=c; *pb=b;
 265 }
 266
 267
 268 /*
 269 -------------------------------------------------------------------------------
 270 hashlittle() -- hash a variable-length key into a 32-bit value
 271   k       : the key (the unaligned variable-length array of bytes)
 272   length  : the length of the key, counting by bytes
 273   initval : can be any 4-byte value
 274 Returns a 32-bit value.  Every bit of the key affects every bit of
 275 the return value.  Two keys differing by one or two bits will have
 276 totally different hash values.
 277
 278 The best hash table sizes are powers of 2.  There is no need to do
 279 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 280 use a bitmask.  For example, if you need only 10 bits, do
 281   h = (h & hashmask(10));
 282 In which case, the hash table should have hashsize(10) elements.
 283
 284 If you are hashing n strings (uint8_t **)k, do it like this:
 285   for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
 286
 287 By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
 288 code any way you wish, private, educational, or commercial.  It's free.
 289
 290 Use for hash table lookup, or anything where one collision in 2^^32 is
 291 acceptable.  Do NOT use for cryptographic purposes.
 292 -------------------------------------------------------------------------------
 293 */
 294
 295 uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
 296 {
 297   uint32_t a,b,c;                                          /* internal state */
 298   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
 299
 300   /* Set up the internal state */
 301   a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
 302
 303   u.ptr = key;
 304   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
 305     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 306     const uint8_t  *k8;
 307
 308     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 309     while (length > 12)
 310     {
 311       a += k[0];
 312       b += k[1];
 313       c += k[2];
 314       mix(a,b,c);
 315       length -= 12;
 316       k += 3;
 317     }
 318
 319     /*----------------------------- handle the last (probably partial) block */
 320
 321     k8 = (const uint8_t *)k;
 322     switch(length)
 323     {
 324     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 325     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
 326     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
 327     case 9 : c+=k8[8];                   /* fall through */
 328     case 8 : b+=k[1]; a+=k[0]; break;
 329     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
 330     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
 331     case 5 : b+=k8[4];                   /* fall through */
 332     case 4 : a+=k[0]; break;
 333     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
 334     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
 335     case 1 : a+=k8[0]; break;
 336     case 0 : return c;
 337     }
 338
 339   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
 340     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
 341     const uint8_t  *k8;
 342
 343     /*--------------- all but last block: aligned reads and different mixing */
 344     while (length > 12)
 345     {
 346       a += k[0] + (((uint32_t)k[1])<<16);
 347       b += k[2] + (((uint32_t)k[3])<<16);
 348       c += k[4] + (((uint32_t)k[5])<<16);
 349       mix(a,b,c);
 350       length -= 12;
 351       k += 6;
 352     }
 353
 354     /*----------------------------- handle the last (probably partial) block */
 355     k8 = (const uint8_t *)k;
 356     switch(length)
 357     {
 358     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
 359              b+=k[2]+(((uint32_t)k[3])<<16);
 360              a+=k[0]+(((uint32_t)k[1])<<16);
 361              break;
 362     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
 363     case 10: c+=k[4];
 364              b+=k[2]+(((uint32_t)k[3])<<16);
 365              a+=k[0]+(((uint32_t)k[1])<<16);
 366              break;
 367     case 9 : c+=k8[8];                      /* fall through */
 368     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
 369              a+=k[0]+(((uint32_t)k[1])<<16);
 370              break;
 371     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
 372     case 6 : b+=k[2];
 373              a+=k[0]+(((uint32_t)k[1])<<16);
 374              break;
 375     case 5 : b+=k8[4];                      /* fall through */
 376     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
 377              break;
 378     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
 379     case 2 : a+=k[0];
 380              break;
 381     case 1 : a+=k8[0];
 382              break;
 383     case 0 : return c;                     /* zero length requires no mixing */
 384     }
 385
 386   } else {                        /* need to read the key one byte at a time */
 387     const uint8_t *k = (const uint8_t *)key;
 388
 389     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
 390     while (length > 12)
 391     {
 392       a += k[0];
 393       a += ((uint32_t)k[1])<<8;
 394       a += ((uint32_t)k[2])<<16;
 395       a += ((uint32_t)k[3])<<24;
 396       b += k[4];
 397       b += ((uint32_t)k[5])<<8;
 398       b += ((uint32_t)k[6])<<16;
 399       b += ((uint32_t)k[7])<<24;
 400       c += k[8];
 401       c += ((uint32_t)k[9])<<8;
 402       c += ((uint32_t)k[10])<<16;
 403       c += ((uint32_t)k[11])<<24;
 404       mix(a,b,c);
 405       length -= 12;
 406       k += 12;
 407     }
 408
 409     /*-------------------------------- last block: affect all 32 bits of (c) */
 410     switch(length)                   /* all the case statements fall through */
 411     {
 412     case 12: c+=((uint32_t)k[11])<<24;
 413     case 11: c+=((uint32_t)k[10])<<16;
 414     case 10: c+=((uint32_t)k[9])<<8;
 415     case 9 : c+=k[8];
 416
 417     case 8 : b+=((uint32_t)k[7])<<24;
 418     case 7 : b+=((uint32_t)k[6])<<16;
 419     case 6 : b+=((uint32_t)k[5])<<8;
 420     case 5 : b+=k[4];
 421
 422     case 4 : a+=((uint32_t)k[3])<<24;
 423     case 3 : a+=((uint32_t)k[2])<<16;
 424     case 2 : a+=((uint32_t)k[1])<<8;
 425     case 1 : a+=k[0];
 426              break;
 427
 428     case 0 : return c;
 429     }
 430   }
 431
 432   final(a,b,c);
 433   return c;
 434 }
 435
 436
 437 /*
 438  * hashlittle2: return 2 32-bit hash values
 439  *
 440  * This is identical to hashlittle(), except it returns two 32-bit hash
 441  * values instead of just one.  This is good enough for hash table
 442  * lookup with 2^^64 buckets, or if you want a second hash if you're not
 443  * happy with the first, or if you want a probably-unique 64-bit ID for
 444  * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
 445  * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
 446  */
 447 void hashlittle2(
 448   const void *key,       /* the key to hash */
 449   size_t      length,    /* length of the key */
 450   uint32_t   *pc,        /* IN: primary initval, OUT: primary hash */
 451   uint32_t   *pb)        /* IN: secondary initval, OUT: secondary hash */
 452 {
 453   uint32_t a,b,c;                                          /* internal state */
 454   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
 455
 456   /* Set up the internal state */
 457   a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
 458   c += *pb;
 459
 460   u.ptr = key;
 461   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
 462     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 463     const uint8_t  *k8;
 464
 465     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 466     while (length > 12)
 467     {
 468       a += k[0];
 469       b += k[1];
 470       c += k[2];
 471       mix(a,b,c);
 472       length -= 12;
 473       k += 3;
 474     }
 475
 476     /*----------------------------- handle the last (probably partial) block */
 477
 478     k8 = (const uint8_t *)k;
 479     switch(length)
 480     {
 481     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 482     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
 483     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
 484     case 9 : c+=k8[8];                   /* fall through */
 485     case 8 : b+=k[1]; a+=k[0]; break;
 486     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
 487     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
 488     case 5 : b+=k8[4];                   /* fall through */
 489     case 4 : a+=k[0]; break;
 490     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
 491     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
 492     case 1 : a+=k8[0]; break;
 493     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
 494     }
 495
 496   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
 497     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
 498     const uint8_t  *k8;
 499
 500     /*--------------- all but last block: aligned reads and different mixing */
 501     while (length > 12)
 502     {
 503       a += k[0] + (((uint32_t)k[1])<<16);
 504       b += k[2] + (((uint32_t)k[3])<<16);
 505       c += k[4] + (((uint32_t)k[5])<<16);
 506       mix(a,b,c);
 507       length -= 12;
 508       k += 6;
 509     }
 510
 511     /*----------------------------- handle the last (probably partial) block */
 512     k8 = (const uint8_t *)k;
 513     switch(length)
 514     {
 515     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
 516              b+=k[2]+(((uint32_t)k[3])<<16);
 517              a+=k[0]+(((uint32_t)k[1])<<16);
 518              break;
 519     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
 520     case 10: c+=k[4];
 521              b+=k[2]+(((uint32_t)k[3])<<16);
 522              a+=k[0]+(((uint32_t)k[1])<<16);
 523              break;
 524     case 9 : c+=k8[8];                      /* fall through */
 525     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
 526              a+=k[0]+(((uint32_t)k[1])<<16);
 527              break;
 528     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
 529     case 6 : b+=k[2];
 530              a+=k[0]+(((uint32_t)k[1])<<16);
 531              break;
 532     case 5 : b+=k8[4];                      /* fall through */
 533     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
 534              break;
 535     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
 536     case 2 : a+=k[0];
 537              break;
 538     case 1 : a+=k8[0];
 539              break;
 540     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
 541     }
 542
 543   } else {                        /* need to read the key one byte at a time */
 544     const uint8_t *k = (const uint8_t *)key;
 545
 546     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
 547     while (length > 12)
 548     {
 549       a += k[0];
 550       a += ((uint32_t)k[1])<<8;
 551       a += ((uint32_t)k[2])<<16;
 552       a += ((uint32_t)k[3])<<24;
 553       b += k[4];
 554       b += ((uint32_t)k[5])<<8;
 555       b += ((uint32_t)k[6])<<16;
 556       b += ((uint32_t)k[7])<<24;
 557       c += k[8];
 558       c += ((uint32_t)k[9])<<8;
 559       c += ((uint32_t)k[10])<<16;
 560       c += ((uint32_t)k[11])<<24;
 561       mix(a,b,c);
 562       length -= 12;
 563       k += 12;
 564     }
 565
 566     /*-------------------------------- last block: affect all 32 bits of (c) */
 567     switch(length)                   /* all the case statements fall through */
 568     {
 569     case 12: c+=((uint32_t)k[11])<<24;
 570     case 11: c+=((uint32_t)k[10])<<16;
 571     case 10: c+=((uint32_t)k[9])<<8;
 572     case 9 : c+=k[8];
 573     case 8 : b+=((uint32_t)k[7])<<24;
 574     case 7 : b+=((uint32_t)k[6])<<16;
 575     case 6 : b+=((uint32_t)k[5])<<8;
 576     case 5 : b+=k[4];
 577     case 4 : a+=((uint32_t)k[3])<<24;
 578     case 3 : a+=((uint32_t)k[2])<<16;
 579     case 2 : a+=((uint32_t)k[1])<<8;
 580     case 1 : a+=k[0];
 581              break;
 582     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
 583     }
 584   }
 585
 586   final(a,b,c);
 587   *pc=c; *pb=b;
 588 }
 589
 590
 591
 592 /*
 593  * hashbig():
 594  * This is the same as hashword() on big-endian machines.  It is different
 595  * from hashlittle() on all machines.  hashbig() takes advantage of
 596  * big-endian byte ordering.
 597  */
 598 uint32_t hashbig( const void *key, size_t length, uint32_t initval)
 599 {
 600   uint32_t a,b,c;
 601   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
 602
 603   /* Set up the internal state */
 604   a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
 605
 606   u.ptr = key;
 607   if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
 608     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 609     const uint8_t  *k8;
 610
 611     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 612     while (length > 12)
 613     {
 614       a += k[0];
 615       b += k[1];
 616       c += k[2];
 617       mix(a,b,c);
 618       length -= 12;
 619       k += 3;
 620     }
 621
 622     /*----------------------------- handle the last (probably partial) block */
 623
 624     k8 = (const uint8_t *)k;
 625     switch(length)                   /* all the case statements fall through */
 626     {
 627     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 628     case 11: c+=((uint32_t)k8[10])<<8;  /* fall through */
 629     case 10: c+=((uint32_t)k8[9])<<16;  /* fall through */
 630     case 9 : c+=((uint32_t)k8[8])<<24;  /* fall through */
 631     case 8 : b+=k[1]; a+=k[0]; break;
 632     case 7 : b+=((uint32_t)k8[6])<<8;   /* fall through */
 633     case 6 : b+=((uint32_t)k8[5])<<16;  /* fall through */
 634     case 5 : b+=((uint32_t)k8[4])<<24;  /* fall through */
 635     case 4 : a+=k[0]; break;
 636     case 3 : a+=((uint32_t)k8[2])<<8;   /* fall through */
 637     case 2 : a+=((uint32_t)k8[1])<<16;  /* fall through */
 638     case 1 : a+=((uint32_t)k8[0])<<24; break;
 639     case 0 : return c;
 640     }
 641
 642   } else {                        /* need to read the key one byte at a time */
 643     const uint8_t *k = (const uint8_t *)key;
 644
 645     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
 646     while (length > 12)
 647     {
 648       a += ((uint32_t)k[0])<<24;
 649       a += ((uint32_t)k[1])<<16;
 650       a += ((uint32_t)k[2])<<8;
 651       a += ((uint32_t)k[3]);
 652       b += ((uint32_t)k[4])<<24;
 653       b += ((uint32_t)k[5])<<16;
 654       b += ((uint32_t)k[6])<<8;
 655       b += ((uint32_t)k[7]);
 656       c += ((uint32_t)k[8])<<24;
 657       c += ((uint32_t)k[9])<<16;
 658       c += ((uint32_t)k[10])<<8;
 659       c += ((uint32_t)k[11]);
 660       mix(a,b,c);
 661       length -= 12;
 662       k += 12;
 663     }
 664
 665     /*-------------------------------- last block: affect all 32 bits of (c) */
 666     switch(length)                   /* all the case statements fall through */
 667     {
 668     case 12: c+=k[11];
 669     case 11: c+=((uint32_t)k[10])<<8;
 670     case 10: c+=((uint32_t)k[9])<<16;
 671     case 9 : c+=((uint32_t)k[8])<<24;
 672     case 8 : b+=k[7];
 673     case 7 : b+=((uint32_t)k[6])<<8;
 674     case 6 : b+=((uint32_t)k[5])<<16;
 675     case 5 : b+=((uint32_t)k[4])<<24;
 676     case 4 : a+=k[3];
 677     case 3 : a+=((uint32_t)k[2])<<8;
 678     case 2 : a+=((uint32_t)k[1])<<16;
 679     case 1 : a+=((uint32_t)k[0])<<24;
 680              break;
 681     case 0 : return c;
 682     }
 683   }
 684
 685   final(a,b,c);
 686   return c;
 687 }
 688
 689
 690 uint32_t hashLookup3Orig (const char * k, int length) {
 691     return hashlittle (k, length, 0);
 692 }
 693
 694 uint32_t hashLookup3 (const char * k, int length) {
 695     return Foam::Hasher(k, length, 0);
 696 }
 697
 698
 699
 700 /* ======================================================================== */
 701
 702 static uint32_t crc_16_table[16] = {
 703   0x0000, 0xCC01, 0xD801, 0x1400, 0xF001, 0x3C00, 0x2800, 0xE401,
 704   0xA001, 0x6C00, 0x7800, 0xB401, 0x5000, 0x9C01, 0x8801, 0x4400
 705 };
 706
 707 /*
 708  *      This code was found at: http://wannabe.guru.org/alg/node191.html
 709  *  and still exists here: http://www.fearme.com/misc/alg/node191.html
 710  *
 711  *  this source code is based on Rex and Binstock which, in turn,
 712  *  acknowledges William James Hunt.
 713  *
 714  *      According to the site this CRC uses the polynomial x^16+x^5+x^2+1.
 715  *      Unfortunately, DOCSIS uses x^16+x^12+x^5+1.  D'oh!
 716  */
 717
 718 static uint32_t GetCRC16Update
 719 (
 720     uint32_t start_crc,
 721     const char * data_stream,
 722     int length
 723 ) {
 724 uint32_t crc = start_crc;
 725 uint32_t r;
 726
 727   /* while there is more data to process */
 728   while (length-- > 0) {
 729
 730     /* compute checksum of lower four bits of *data_stream */
 731     r = crc_16_table[crc & 0xF];
 732     crc = (crc >> 4) & 0x0FFF;
 733     crc ^= r ^ crc_16_table[*data_stream & 0xF];
 734
 735     /* now compute checksum of upper four bits of *data_stream */
 736     r = crc_16_table[crc & 0xF];
 737     crc = (crc >> 4) & 0x0FFF;
 738     crc ^= r ^ crc_16_table[(*data_stream >> 4) & 0xF];
 739
 740     /* next... */
 741     data_stream++;
 742   }
 743
 744   return crc;
 745 }
 746
 747 uint32_t GetCRC16 (const char * data_stream, int length) {
 748         return GetCRC16Update (0, data_stream, length);
 749 }
 750
 751 /* ======================================================================== */
 752
 753 static uint32_t crc_table[256];
 754
 755 /*  This code was found at:
 756  *  http://cell.onecall.net/cell-relay/publications/software/CRC/32bitCRC.c.html
 757  */
 758
 759 /*                                                                      */
 760 /* crc32h.c -- package to compute 32-bit CRC one byte at a time using   */
 761 /*             the high-bit first (Big-Endian) bit ordering convention  */
 762 /*                                                                      */
 763 /* Synopsis:                                                            */
 764 /*  gen_crc_table() -- generates a 256-word table containing all CRC    */
 765 /*                     remainders for every possible 8-bit byte.  It    */
 766 /*                     must be executed (once) before any CRC updates.  */
 767 /*                                                                      */
 768 /*  unsigned update_crc(crc_accum, data_blk_ptr, data_blk_size)         */
 769 /*           unsigned crc_accum; char *data_blk_ptr; int data_blk_size; */
 770 /*           Returns the updated value of the CRC accumulator after     */
 771 /*           processing each byte in the addressed block of data.       */
 772 /*                                                                      */
 773 /*  It is assumed that an unsigned long is at least 32 bits wide and    */
 774 /*  that the predefined type char occupies one 8-bit byte of storage.   */
 775 /*                                                                      */
 776 /*  The generator polynomial used for this version of the package is    */
 777 /*  x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+x^0 */
 778 /*  as specified in the Autodin/Ethernet/ADCCP protocol standards.      */
 779 /*  Other degree 32 polynomials may be substituted by re-defining the   */
 780 /*  symbol POLYNOMIAL below.  Lower degree polynomials must first be    */
 781 /*  multiplied by an appropriate power of x.  The representation used   */
 782 /*  is that the coefficient of x^0 is stored in the LSB of the 32-bit   */
 783 /*  word and the coefficient of x^31 is stored in the most significant  */
 784 /*  bit.  The CRC is to be appended to the data most significant byte   */
 785 /*  first.  For those protocols in which bytes are transmitted MSB      */
 786 /*  first and in the same order as they are encountered in the block    */
 787 /*  this convention results in the CRC remainder being transmitted with */
 788 /*  the coefficient of x^31 first and with that of x^0 last (just as    */
 789 /*  would be done by a hardware shift register mechanization).          */
 790 /*                                                                      */
 791 /*  The table lookup technique was adapted from the algorithm described */
 792 /*  by Avram Perez, Byte-wise CRC Calculations, IEEE Micro 3, 40 (1983).*/
 793
 794 /* generate the table of CRC remainders for all possible bytes */
 795
 796 #define CRC32POLYNOMIAL 0x04c11db7L
 797
 798 static void GenerateCRC32Table (void) {
 799 register int i, j;
 800 register uint32_t crc_accum;
 801
 802     for ( i = 0;  i < 256;  i++ ) {
 803         crc_accum = ( (unsigned long) i << 24 );
 804         for ( j = 0;  j < 8;  j++ ) {
 805             if ( crc_accum & 0x80000000L ) {
 806                 crc_accum = ( crc_accum << 1 ) ^ CRC32POLYNOMIAL;
 807             } else {
 808                 crc_accum = ( crc_accum << 1 );
 809             }
 810         }
 811         crc_table[i] = crc_accum;
 812     }
 813     return;
 814 }
 815
 816 /* update the CRC on the data block one byte at a time */
 817
 818 static uint32_t UpdateCRC32
 819 (
 820     uint32_t crc_accum,
 821     const char *data_blk_ptr,
 822     int data_blk_size
 823 ) {
 824 register int j;
 825 register uint8_t i;
 826
 827         for (j = 0; j < data_blk_size; j++) {
 828                 i = (crc_accum >> 24) ^ *data_blk_ptr++;
 829                 crc_accum = (crc_accum << 8) ^ crc_table[i];
 830         }
 831         return crc_accum;
 832 }
 833
 834 uint32_t GetCRC32 (const char * data_stream, int length) {
 835         return UpdateCRC32 (0, data_stream, length);
 836 }
 837
 838 /* ======================================================================== */
 839
 840 /* Performs two parallel CRC-32 on even and odd bytes of the input, then
 841    combines the two in a further CRC-32 calculation */
 842
 843 uint32_t GetCRC32PH (const char *data_blk_ptr, int data_blk_size) {
 844 int j;
 845 uint8_t i0, i1;
 846 uint32_t crc_accum0 = 0, crc_accum1 = 0x23456789u;
 847
 848         if (data_blk_size & 1) crc_accum0 ^= *data_blk_ptr++;
 849         for (j = 1; j < data_blk_size; j+=2) {
 850                 i0 = ((crc_accum0 >> 24) ^ *data_blk_ptr++);
 851                 i1 = ((crc_accum1 >> 24) ^ *data_blk_ptr++);
 852                 crc_accum0 = (crc_accum0 << 8) ^ crc_table[i0];
 853                 crc_accum1 = (crc_accum1 << 8) ^ crc_table[i1];
 854         }
 855         return crc_accum0 + crc_accum1;
 856 }
 857
 858 /* ======================================================================== */
 859
 860 /* Fowler / Noll / Vo (FNV) Hash
 861
 862    http://www.isthe.com/chongo/tech/comp/fnv/ */
 863
 864 uint32_t FNVHash (const char * data, int len) {
 865 int i;
 866 uint32_t hash;
 867
 868         hash = 2166136261u;
 869         for (i=0; i < len; i++) {
 870                 hash = (16777619u * hash) ^ data[i];
 871         }
 872         return hash;
 873 }
 874
 875 /* ======================================================================== */
 876
 877 /*
 878  * http://burtleburtle.net/bob/hash/doobs.html
 879  */
 880
 881 uint32_t oneAtATimeHash (const char * s, int len) {
 882 int32_t hash;
 883 int i;
 884
 885         for (hash = 0, i = 0; i < len; i++) {
 886                 hash += s[i];
 887                 hash += (hash << 10);
 888                 hash ^= (hash >>  6);   /* Non-portable due to ANSI C */
 889         }
 890         hash += (hash <<  3);
 891         hash ^= (hash >> 11);           /* Non-portable due to ANSI C */
 892         hash += (hash << 15);
 893         return (uint32_t) hash;
 894 }
 895
 896 /* ======================================================================== */
 897
 898 uint32_t oneAtATimeHashPH (const char * s, int len) {
 899 int32_t hash0 = 0, hash1 = 0x23456789;
 900 int i;
 901
 902         if (len & 1) hash1 ^= *s++;
 903
 904         for (i = 1; i < len; i+=2) {
 905                 hash0 += *s++;
 906                 hash1 += *s++;
 907                 hash0 += (hash0 << 10);
 908                 hash1 += (hash1 << 10);
 909                 hash0 ^= (hash0 >>  6); /* Non-portable due to ANSI C */
 910                 hash1 ^= (hash1 >>  6); /* Non-portable due to ANSI C */
 911         }
 912
 913         hash0 += hash1;
 914
 915         hash0 += (hash0 <<  3);
 916         hash0 ^= (hash0 >> 11);         /* Non-portable due to ANSI C */
 917         hash0 += (hash0 << 15);
 918         return (uint32_t) hash0;
 919 }
 920
 921 /* ======================================================================== */
 922
 923 /* By Paul Hsieh (C) 2004, 2005.  Covered under the Paul Hsieh derivative
 924    license. See:
 925    http://www.azillionmonkeys.com/qed/weblicense.html for license details.
 926
 927    http://www.azillionmonkeys.com/qed/hash.html */
 928
 929 #undef get16bits
 930 #if 0
 931 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
 932   || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
 933 #define get16bits(d) (*((const uint16_t *) (d)))
 934 #endif
 935 #endif
 936
 937 #if !defined (get16bits)
 938 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
 939                        +(uint32_t)(((const uint8_t *)(d))[0]) )
 940 #endif
 941
 942 uint32_t SuperFastHash (const char * data, int len)
 943 {
 944     uint32_t hash = 0;
 945
 946     if (len <= 0 || data == NULL) return 0;
 947
 948     unsigned rem = len & 3;
 949     len >>= 2;
 950
 951     /* Main loop */
 952     for (;len > 0; len--) {
 953         hash += get16bits(data);
 954         hash = (hash << 16) ^ ((get16bits(data+2) << 11) ^ hash);
 955         hash += hash >> 11;
 956         data += 2*sizeof(uint16_t);
 957     }
 958
 959     /* Handle end cases */
 960     switch (rem) {
 961         case 3 :
 962             hash += get16bits(data);
 963             hash ^= hash << 16;
 964             hash ^= data[sizeof (uint16_t)] << 18;
 965             hash += hash >> 11;
 966             break;
 967
 968         case 2 :
 969             hash += get16bits (data);
 970             hash ^= hash << 11;
 971             hash += hash >> 17;
 972             break;
 973
 974         case 1 : hash += *data;
 975             hash ^= hash << 10;
 976             hash += hash >> 1;
 977     }
 978
 979     /* Force "avalanching" of final 127 bits */
 980     hash ^= hash << 3;
 981     hash += hash >> 5;
 982     hash ^= hash << 4;
 983     hash += hash >> 17;
 984     hash ^= hash << 25;
 985     hash += hash >> 6;
 986
 987     return hash;
 988 }
 989
 990 /* ======================================================================== */
 991
 992 /* A hashing function that I believe was created by either Chris Torek or
 993    Dan Bernstein */
 994
 995 uint32_t alphaNumHash (const char * s, int len) {
 996 uint32_t h;
 997 int i;
 998
 999     for (h = 0, i = 0; i < len; i++) {
1000         h = (h << 5) + (h * 5) + (unsigned char) s[i];
1001     }
1002     return h;
1003 }
1004
1005 uint32_t bernstein (const char * s, int len) {
1006 uint32_t h;
1007 int i;
1008
1009     for (h = 0, i = 0; i < len; i++) {
1010         h = (h << 5) + h + (unsigned char) s[i];
1011     }
1012     return h;
1013 }
1014
1015
1016 // found somewhere in the 2nd addition
1017 uint32_t stroustrup (const char * s, int len) {
1018     uint32_t h;
1019     int i;
1020
1021     for (register int i=0; i < len; ++s, ++i)
1022     {
1023         h = (h << 1) ^ (unsigned char) s[i];
1024     }
1025
1026     return h;
1027 }
1028
1029
1030 /* ======================================================================== */
1031
1032 typedef uint32_t (* hashFn) (const char * s, int len);
1033
1034 #define BUFF_SZ (128*2)
1035 #define NTESTS 5000000
1036
1037 double test (hashFn hash) {
1038 static char buff[BUFF_SZ];
1039 clock_t c0, c1;
1040 int32_t i;
1041
1042         for (buff[0]=0, i=1; i < BUFF_SZ; i++) buff[i] = (char) (i + buff[i-1]);
1043
1044         c0 = clock ();
1045         for (i=0; i < NTESTS; i++) hash (buff, BUFF_SZ);
1046         c1 = clock ();
1047         return (c1 - c0)*(1.0 / (double)CLOCKS_PER_SEC);
1048 }
1049
1050 struct tagtest {
1051         double res;
1052         char * name;
1053         hashFn hash;
1054 } tests[] = {
1055 //      { 0.0, "CRC32\t\t", GetCRC32                  },
1056 //      { 0.0, "oneAtATimeHash\t", oneAtATimeHash     },
1057 //      { 0.0, "alphaNumHash\t",  alphaNumHash        },
1058         { 0.0, "FNVHash\t\t", FNVHash                 },
1059         { 0.0, "bernstein\t",  bernstein        },
1060         { 0.0, "stroustrup\t", stroustrup             },
1061         { 0.0, "hashLookup3\t", hashLookup3           },
1062         { 0.0, "hashLookup3Orig\t", hashLookup3Orig   },
1063         { 0.0, "SuperFastHash\t", SuperFastHash       },
1064         { 0.0, NULL, NULL                             }
1065 };
1066
1067 int main () {
1068 int i, j;
1069     GenerateCRC32Table ();
1070
1071     for (j=0; tests[j].name != NULL; j++) {
1072         for (i=0; i < 3; i++) {
1073             double res = test (tests[j].hash);
1074             if (tests[j].res == 0.0 || tests[j].res > res) tests[j].res = res;
1075         }
1076         printf ("%s:%8.4fs\n", tests[j].name, tests[j].res);
1077     }
1078
1079     return 0;
1080 }