applications/test/HashingSpeed/testHashingSpeed.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 (uint32_t start_crc, const char * data_stream, int length) {
 719 uint32_t crc = start_crc;
 720 uint32_t r;
 721
 722   /* while there is more data to process */
 723   while (length-- > 0) {
 724
 725     /* compute checksum of lower four bits of *data_stream */
 726     r = crc_16_table[crc & 0xF];
 727     crc = (crc >> 4) & 0x0FFF;
 728     crc ^= r ^ crc_16_table[*data_stream & 0xF];
 729
 730     /* now compute checksum of upper 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 >> 4) & 0xF];
 734
 735     /* next... */
 736     data_stream++;
 737   }
 738
 739   return crc;
 740 }
 741
 742 uint32_t GetCRC16 (const char * data_stream, int length) {
 743         return GetCRC16Update (0, data_stream, length);
 744 }
 745
 746 /* ======================================================================== */
 747
 748 static uint32_t crc_table[256];
 749
 750 /*  This code was found at:
 751  *  http://cell.onecall.net/cell-relay/publications/software/CRC/32bitCRC.c.html
 752  */
 753
 754 /*                                                                      */
 755 /* crc32h.c -- package to compute 32-bit CRC one byte at a time using   */
 756 /*             the high-bit first (Big-Endian) bit ordering convention  */
 757 /*                                                                      */
 758 /* Synopsis:                                                            */
 759 /*  gen_crc_table() -- generates a 256-word table containing all CRC    */
 760 /*                     remainders for every possible 8-bit byte.  It    */
 761 /*                     must be executed (once) before any CRC updates.  */
 762 /*                                                                      */
 763 /*  unsigned update_crc(crc_accum, data_blk_ptr, data_blk_size)         */
 764 /*           unsigned crc_accum; char *data_blk_ptr; int data_blk_size; */
 765 /*           Returns the updated value of the CRC accumulator after     */
 766 /*           processing each byte in the addressed block of data.       */
 767 /*                                                                      */
 768 /*  It is assumed that an unsigned long is at least 32 bits wide and    */
 769 /*  that the predefined type char occupies one 8-bit byte of storage.   */
 770 /*                                                                      */
 771 /*  The generator polynomial used for this version of the package is    */
 772 /*  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 */
 773 /*  as specified in the Autodin/Ethernet/ADCCP protocol standards.      */
 774 /*  Other degree 32 polynomials may be substituted by re-defining the   */
 775 /*  symbol POLYNOMIAL below.  Lower degree polynomials must first be    */
 776 /*  multiplied by an appropriate power of x.  The representation used   */
 777 /*  is that the coefficient of x^0 is stored in the LSB of the 32-bit   */
 778 /*  word and the coefficient of x^31 is stored in the most significant  */
 779 /*  bit.  The CRC is to be appended to the data most significant byte   */
 780 /*  first.  For those protocols in which bytes are transmitted MSB      */
 781 /*  first and in the same order as they are encountered in the block    */
 782 /*  this convention results in the CRC remainder being transmitted with */
 783 /*  the coefficient of x^31 first and with that of x^0 last (just as    */
 784 /*  would be done by a hardware shift register mechanization).          */
 785 /*                                                                      */
 786 /*  The table lookup technique was adapted from the algorithm described */
 787 /*  by Avram Perez, Byte-wise CRC Calculations, IEEE Micro 3, 40 (1983).*/
 788
 789 /* generate the table of CRC remainders for all possible bytes */
 790
 791 #define CRC32POLYNOMIAL 0x04c11db7L
 792
 793 static void GenerateCRC32Table (void) {
 794 register int i, j;
 795 register uint32_t crc_accum;
 796
 797         for ( i = 0;  i < 256;  i++ ) {
 798                 crc_accum = ( (unsigned long) i << 24 );
 799         for ( j = 0;  j < 8;  j++ ) {
 800                         if ( crc_accum & 0x80000000L ) {
 801                                 crc_accum = ( crc_accum << 1 ) ^ CRC32POLYNOMIAL;
 802                         } else {
 803                                 crc_accum = ( crc_accum << 1 );
 804                         }
 805                 }
 806                 crc_table[i] = crc_accum;
 807         }
 808         return;
 809 }
 810
 811 /* update the CRC on the data block one byte at a time */
 812
 813 static uint32_t UpdateCRC32 (uint32_t crc_accum, const char *data_blk_ptr, int data_blk_size) {
 814 register int j;
 815 register uint8_t i;
 816
 817         for (j = 0; j < data_blk_size; j++) {
 818                 i = (crc_accum >> 24) ^ *data_blk_ptr++;
 819                 crc_accum = (crc_accum << 8) ^ crc_table[i];
 820         }
 821         return crc_accum;
 822 }
 823
 824 uint32_t GetCRC32 (const char * data_stream, int length) {
 825         return UpdateCRC32 (0, data_stream, length);
 826 }
 827
 828 /* ======================================================================== */
 829
 830 /* Performs two parallel CRC-32 on even and odd bytes of the input, then
 831    combines the two in a further CRC-32 calculation */
 832
 833 uint32_t GetCRC32PH (const char *data_blk_ptr, int data_blk_size) {
 834 int j;
 835 uint8_t i0, i1;
 836 uint32_t crc_accum0 = 0, crc_accum1 = 0x23456789u;
 837
 838         if (data_blk_size & 1) crc_accum0 ^= *data_blk_ptr++;
 839         for (j = 1; j < data_blk_size; j+=2) {
 840                 i0 = ((crc_accum0 >> 24) ^ *data_blk_ptr++);
 841                 i1 = ((crc_accum1 >> 24) ^ *data_blk_ptr++);
 842                 crc_accum0 = (crc_accum0 << 8) ^ crc_table[i0];
 843                 crc_accum1 = (crc_accum1 << 8) ^ crc_table[i1];
 844         }
 845         return crc_accum0 + crc_accum1;
 846 }
 847
 848 /* ======================================================================== */
 849
 850 /* Fowler / Noll / Vo (FNV) Hash
 851
 852    http://www.isthe.com/chongo/tech/comp/fnv/ */
 853
 854 uint32_t FNVHash (const char * data, int len) {
 855 int i;
 856 uint32_t hash;
 857
 858         hash = 2166136261u;
 859         for (i=0; i < len; i++) {
 860                 hash = (16777619u * hash) ^ data[i];
 861         }
 862         return hash;
 863 }
 864
 865 /* ======================================================================== */
 866
 867 /*
 868  * http://burtleburtle.net/bob/hash/doobs.html
 869  */
 870
 871 uint32_t oneAtATimeHash (const char * s, int len) {
 872 int32_t hash;
 873 int i;
 874
 875         for (hash = 0, i = 0; i < len; i++) {
 876                 hash += s[i];
 877                 hash += (hash << 10);
 878                 hash ^= (hash >>  6);   /* Non-portable due to ANSI C */
 879         }
 880         hash += (hash <<  3);
 881         hash ^= (hash >> 11);           /* Non-portable due to ANSI C */
 882         hash += (hash << 15);
 883         return (uint32_t) hash;
 884 }
 885
 886 /* ======================================================================== */
 887
 888 uint32_t oneAtATimeHashPH (const char * s, int len) {
 889 int32_t hash0 = 0, hash1 = 0x23456789;
 890 int i;
 891
 892         if (len & 1) hash1 ^= *s++;
 893
 894         for (i = 1; i < len; i+=2) {
 895                 hash0 += *s++;
 896                 hash1 += *s++;
 897                 hash0 += (hash0 << 10);
 898                 hash1 += (hash1 << 10);
 899                 hash0 ^= (hash0 >>  6); /* Non-portable due to ANSI C */
 900                 hash1 ^= (hash1 >>  6); /* Non-portable due to ANSI C */
 901         }
 902
 903         hash0 += hash1;
 904
 905         hash0 += (hash0 <<  3);
 906         hash0 ^= (hash0 >> 11);         /* Non-portable due to ANSI C */
 907         hash0 += (hash0 << 15);
 908         return (uint32_t) hash0;
 909 }
 910
 911 /* ======================================================================== */
 912
 913 /* By Paul Hsieh (C) 2004, 2005.  Covered under the Paul Hsieh derivative
 914    license. See:
 915    http://www.azillionmonkeys.com/qed/weblicense.html for license details.
 916
 917    http://www.azillionmonkeys.com/qed/hash.html */
 918
 919 #undef get16bits
 920 #if 0
 921 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
 922   || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
 923 #define get16bits(d) (*((const uint16_t *) (d)))
 924 #endif
 925 #endif
 926
 927 #if !defined (get16bits)
 928 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
 929                        +(uint32_t)(((const uint8_t *)(d))[0]) )
 930 #endif
 931
 932 uint32_t SuperFastHash (const char * data, int len)
 933 {
 934     uint32_t hash = 0;
 935
 936     if (len <= 0 || data == NULL) return 0;
 937
 938     unsigned rem = len & 3;
 939     len >>= 2;
 940
 941     /* Main loop */
 942     for (;len > 0; len--) {
 943         hash += get16bits(data);
 944         hash = (hash << 16) ^ ((get16bits(data+2) << 11) ^ hash);
 945         hash += hash >> 11;
 946         data += 2*sizeof(uint16_t);
 947     }
 948
 949     /* Handle end cases */
 950     switch (rem) {
 951         case 3 :
 952             hash += get16bits(data);
 953             hash ^= hash << 16;
 954             hash ^= data[sizeof (uint16_t)] << 18;
 955             hash += hash >> 11;
 956             break;
 957
 958         case 2 :
 959             hash += get16bits (data);
 960             hash ^= hash << 11;
 961             hash += hash >> 17;
 962             break;
 963
 964         case 1 : hash += *data;
 965             hash ^= hash << 10;
 966             hash += hash >> 1;
 967     }
 968
 969     /* Force "avalanching" of final 127 bits */
 970     hash ^= hash << 3;
 971     hash += hash >> 5;
 972     hash ^= hash << 4;
 973     hash += hash >> 17;
 974     hash ^= hash << 25;
 975     hash += hash >> 6;
 976
 977     return hash;
 978 }
 979
 980 /* ======================================================================== */
 981
 982 /* A hashing function that I believe was created by either Chris Torek or
 983    Dan Bernstein */
 984
 985 uint32_t alphaNumHash (const char * s, int len) {
 986 uint32_t h;
 987 int i;
 988
 989     for (h = 0, i = 0; i < len; i++) {
 990         h = (h << 5) + (h * 5) + (unsigned char) s[i];
 991     }
 992     return h;
 993 }
 994
 995 uint32_t bernstein (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 + (unsigned char) s[i];
1001     }
1002     return h;
1003 }
1004
1005
1006 // found somewhere in the 2nd addition
1007 uint32_t stroustrup (const char * s, int len) {
1008     uint32_t h;
1009     int i;
1010
1011     for (register int i=0; i < len; ++s, ++i)
1012     {
1013         h = (h << 1) ^ (unsigned char) s[i];
1014     }
1015
1016     return h;
1017 }
1018
1019
1020 /* ======================================================================== */
1021
1022 typedef uint32_t (* hashFn) (const char * s, int len);
1023
1024 #define BUFF_SZ (128*2)
1025 #define NTESTS 5000000
1026
1027 double test (hashFn hash) {
1028 static char buff[BUFF_SZ];
1029 clock_t c0, c1;
1030 int32_t i;
1031
1032         for (buff[0]=0, i=1; i < BUFF_SZ; i++) buff[i] = (char) (i + buff[i-1]);
1033
1034         c0 = clock ();
1035         for (i=0; i < NTESTS; i++) hash (buff, BUFF_SZ);
1036         c1 = clock ();
1037         return (c1 - c0)*(1.0 / (double)CLOCKS_PER_SEC);
1038 }
1039
1040 struct tagtest {
1041         double res;
1042         char * name;
1043         hashFn hash;
1044 } tests[] = {
1045 //      { 0.0, "CRC32\t\t", GetCRC32                  },
1046 //      { 0.0, "oneAtATimeHash\t", oneAtATimeHash     },
1047 //      { 0.0, "alphaNumHash\t",  alphaNumHash        },
1048         { 0.0, "FNVHash\t\t", FNVHash                 },
1049         { 0.0, "bernstein\t",  bernstein        },
1050         { 0.0, "stroustrup\t", stroustrup             },
1051         { 0.0, "hashLookup3\t", hashLookup3           },
1052         { 0.0, "hashLookup3Orig\t", hashLookup3Orig   },
1053         { 0.0, "SuperFastHash\t", SuperFastHash       },
1054         { 0.0, NULL, NULL                             }
1055 };
1056
1057 int main () {
1058 int i, j;
1059         GenerateCRC32Table ();
1060
1061         for (j=0; tests[j].name != NULL; j++) {
1062                 for (i=0; i < 3; i++) {
1063                         double res = test (tests[j].hash);
1064                         if (tests[j].res == 0.0 || tests[j].res > res) tests[j].res = res;
1065                 }
1066                 printf ("%s:%8.4fs\n", tests[j].name, tests[j].res);
1067         }
1068
1069         return 0;
1070 }