contrib/unbound/util/storage/lookup3.c

   1 /*
   2   February 2013(Wouter) patch defines for BSD endianness, from Brad Smith.
   3   January 2012(Wouter) added randomised initial value, fallout from 28c3.
   4   March 2007(Wouter) adapted from lookup3.c original, add config.h include.
   5      added #ifdef VALGRIND to remove 298,384,660 'unused variable k8' warnings.
   6      added include of lookup3.h to check definitions match declarations.
   7      removed include of stdint - config.h takes care of platform independence.
   8      added fallthrough comments for new gcc warning suppression.
   9   url http://burtleburtle.net/bob/hash/index.html.
  10 */
  11 /*
  12 -------------------------------------------------------------------------------
  13 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  14
  15 These are functions for producing 32-bit hashes for hash table lookup.
  16 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
  17 are externally useful functions.  Routines to test the hash are included
  18 if SELF_TEST is defined.  You can use this free for any purpose.  It's in
  19 the public domain.  It has no warranty.
  20
  21 You probably want to use hashlittle().  hashlittle() and hashbig()
  22 hash byte arrays.  hashlittle() is is faster than hashbig() on
  23 little-endian machines.  Intel and AMD are little-endian machines.
  24 On second thought, you probably want hashlittle2(), which is identical to
  25 hashlittle() except it returns two 32-bit hashes for the price of one.
  26 You could implement hashbig2() if you wanted but I haven't bothered here.
  27
  28 If you want to find a hash of, say, exactly 7 integers, do
  29   a = i1;  b = i2;  c = i3;
  30   mix(a,b,c);
  31   a += i4; b += i5; c += i6;
  32   mix(a,b,c);
  33   a += i7;
  34   final(a,b,c);
  35 then use c as the hash value.  If you have a variable length array of
  36 4-byte integers to hash, use hashword().  If you have a byte array (like
  37 a character string), use hashlittle().  If you have several byte arrays, or
  38 a mix of things, see the comments above hashlittle().
  39
  40 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
  41 then mix those integers.  This is fast (you can do a lot more thorough
  42 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
  43 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
  44 -------------------------------------------------------------------------------
  45 */
  46 /*#define SELF_TEST 1*/
  47
  48 #include "config.h"
  49 #include "util/storage/lookup3.h"
  50 #include <stdio.h>      /* defines printf for tests */
  51 #include <time.h>       /* defines time_t for timings in the test */
  52 /*#include <stdint.h>     defines uint32_t etc  (from config.h) */
  53 #include <sys/param.h>  /* attempt to define endianness */
  54 #ifdef HAVE_SYS_TYPES_H
  55 # include <sys/types.h> /* attempt to define endianness (solaris) */
  56 #endif
  57 #if defined(linux) || defined(__OpenBSD__)
  58 #  ifdef HAVE_ENDIAN_H
  59 #    include <endian.h>    /* attempt to define endianness */
  60 #  else
  61 #    include <machine/endian.h> /* on older OpenBSD */
  62 #  endif
  63 #endif
  64 #if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__DragonFly__)
  65 #include <sys/endian.h> /* attempt to define endianness */
  66 #endif
  67
  68 /* random initial value */
  69 static uint32_t raninit = (uint32_t)0xdeadbeef;
  70
  71 void
  72 hash_set_raninit(uint32_t v)
  73 {
  74         raninit = v;
  75 }
  76
  77 /*
  78  * My best guess at if you are big-endian or little-endian.  This may
  79  * need adjustment.
  80  */
  81 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
  82      __BYTE_ORDER == __LITTLE_ENDIAN) || \
  83     (defined(i386) || defined(__i386__) || defined(__i486__) || \
  84      defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL) || defined(__x86))
  85 # define HASH_LITTLE_ENDIAN 1
  86 # define HASH_BIG_ENDIAN 0
  87 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
  88        __BYTE_ORDER == __BIG_ENDIAN) || \
  89       (defined(sparc) || defined(__sparc) || defined(__sparc__) || defined(POWERPC) || defined(mc68000) || defined(sel))
  90 # define HASH_LITTLE_ENDIAN 0
  91 # define HASH_BIG_ENDIAN 1
  92 #elif defined(_MACHINE_ENDIAN_H_)
  93 /* test for machine_endian_h protects failure if some are empty strings */
  94 # if defined(_BYTE_ORDER) && defined(_BIG_ENDIAN) && _BYTE_ORDER == _BIG_ENDIAN
  95 #  define HASH_LITTLE_ENDIAN 0
  96 #  define HASH_BIG_ENDIAN 1
  97 # endif
  98 # if defined(_BYTE_ORDER) && defined(_LITTLE_ENDIAN) && _BYTE_ORDER == _LITTLE_ENDIAN
  99 #  define HASH_LITTLE_ENDIAN 1
 100 #  define HASH_BIG_ENDIAN 0
 101 # endif /* _MACHINE_ENDIAN_H_ */
 102 #else
 103 # define HASH_LITTLE_ENDIAN 0
 104 # define HASH_BIG_ENDIAN 0
 105 #endif
 106
 107 #define hashsize(n) ((uint32_t)1<<(n))
 108 #define hashmask(n) (hashsize(n)-1)
 109 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
 110
 111 /*
 112 -------------------------------------------------------------------------------
 113 mix -- mix 3 32-bit values reversibly.
 114
 115 This is reversible, so any information in (a,b,c) before mix() is
 116 still in (a,b,c) after mix().
 117
 118 If four pairs of (a,b,c) inputs are run through mix(), or through
 119 mix() in reverse, there are at least 32 bits of the output that
 120 are sometimes the same for one pair and different for another pair.
 121 This was tested for:
 122 * pairs that differed by one bit, by two bits, in any combination
 123   of top bits of (a,b,c), or in any combination of bottom bits of
 124   (a,b,c).
 125 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 126   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 127   is commonly produced by subtraction) look like a single 1-bit
 128   difference.
 129 * the base values were pseudorandom, all zero but one bit set, or
 130   all zero plus a counter that starts at zero.
 131
 132 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
 133 satisfy this are
 134     4  6  8 16 19  4
 135     9 15  3 18 27 15
 136    14  9  3  7 17  3
 137 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
 138 for "differ" defined as + with a one-bit base and a two-bit delta.  I
 139 used http://burtleburtle.net/bob/hash/avalanche.html to choose
 140 the operations, constants, and arrangements of the variables.
 141
 142 This does not achieve avalanche.  There are input bits of (a,b,c)
 143 that fail to affect some output bits of (a,b,c), especially of a.  The
 144 most thoroughly mixed value is c, but it doesn't really even achieve
 145 avalanche in c.
 146
 147 This allows some parallelism.  Read-after-writes are good at doubling
 148 the number of bits affected, so the goal of mixing pulls in the opposite
 149 direction as the goal of parallelism.  I did what I could.  Rotates
 150 seem to cost as much as shifts on every machine I could lay my hands
 151 on, and rotates are much kinder to the top and bottom bits, so I used
 152 rotates.
 153 -------------------------------------------------------------------------------
 154 */
 155 #define mix(a,b,c) \
 156 { \
 157   a -= c;  a ^= rot(c, 4);  c += b; \
 158   b -= a;  b ^= rot(a, 6);  a += c; \
 159   c -= b;  c ^= rot(b, 8);  b += a; \
 160   a -= c;  a ^= rot(c,16);  c += b; \
 161   b -= a;  b ^= rot(a,19);  a += c; \
 162   c -= b;  c ^= rot(b, 4);  b += a; \
 163 }
 164
 165 /*
 166 -------------------------------------------------------------------------------
 167 final -- final mixing of 3 32-bit values (a,b,c) into c
 168
 169 Pairs of (a,b,c) values differing in only a few bits will usually
 170 produce values of c that look totally different.  This was tested for
 171 * pairs that differed by one bit, by two bits, in any combination
 172   of top bits of (a,b,c), or in any combination of bottom bits of
 173   (a,b,c).
 174 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 175   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 176   is commonly produced by subtraction) look like a single 1-bit
 177   difference.
 178 * the base values were pseudorandom, all zero but one bit set, or
 179   all zero plus a counter that starts at zero.
 180
 181 These constants passed:
 182  14 11 25 16 4 14 24
 183  12 14 25 16 4 14 24
 184 and these came close:
 185   4  8 15 26 3 22 24
 186  10  8 15 26 3 22 24
 187  11  8 15 26 3 22 24
 188 -------------------------------------------------------------------------------
 189 */
 190 #define final(a,b,c) \
 191 { \
 192   c ^= b; c -= rot(b,14); \
 193   a ^= c; a -= rot(c,11); \
 194   b ^= a; b -= rot(a,25); \
 195   c ^= b; c -= rot(b,16); \
 196   a ^= c; a -= rot(c,4);  \
 197   b ^= a; b -= rot(a,14); \
 198   c ^= b; c -= rot(b,24); \
 199 }
 200
 201 /*
 202 --------------------------------------------------------------------
 203  This works on all machines.  To be useful, it requires
 204  -- that the key be an array of uint32_t's, and
 205  -- that the length be the number of uint32_t's in the key
 206
 207  The function hashword() is identical to hashlittle() on little-endian
 208  machines, and identical to hashbig() on big-endian machines,
 209  except that the length has to be measured in uint32_ts rather than in
 210  bytes.  hashlittle() is more complicated than hashword() only because
 211  hashlittle() has to dance around fitting the key bytes into registers.
 212 --------------------------------------------------------------------
 213 */
 214 uint32_t hashword(
 215 const uint32_t *k,                   /* the key, an array of uint32_t values */
 216 size_t          length,               /* the length of the key, in uint32_ts */
 217 uint32_t        initval)         /* the previous hash, or an arbitrary value */
 218 {
 219   uint32_t a,b,c;
 220
 221   /* Set up the internal state */
 222   a = b = c = raninit + (((uint32_t)length)<<2) + initval;
 223
 224   /*------------------------------------------------- handle most of the key */
 225   while (length > 3)
 226   {
 227     a += k[0];
 228     b += k[1];
 229     c += k[2];
 230     mix(a,b,c);
 231     length -= 3;
 232     k += 3;
 233   }
 234
 235   /*------------------------------------------- handle the last 3 uint32_t's */
 236   switch(length)                     /* all the case statements fall through */
 237   {
 238   case 3 : c+=k[2];
 239         /* fallthrough */
 240   case 2 : b+=k[1];
 241         /* fallthrough */
 242   case 1 : a+=k[0];
 243     final(a,b,c);
 244   case 0:     /* case 0: nothing left to add */
 245     break;
 246   }
 247   /*------------------------------------------------------ report the result */
 248   return c;
 249 }
 250
 251
 252 #ifdef SELF_TEST
 253
 254 /*
 255 --------------------------------------------------------------------
 256 hashword2() -- same as hashword(), but take two seeds and return two
 257 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
 258 both be initialized with seeds.  If you pass in (*pb)==0, the output
 259 (*pc) will be the same as the return value from hashword().
 260 --------------------------------------------------------------------
 261 */
 262 void hashword2 (
 263 const uint32_t *k,                   /* the key, an array of uint32_t values */
 264 size_t          length,               /* the length of the key, in uint32_ts */
 265 uint32_t       *pc,                      /* IN: seed OUT: primary hash value */
 266 uint32_t       *pb)               /* IN: more seed OUT: secondary hash value */
 267 {
 268   uint32_t a,b,c;
 269
 270   /* Set up the internal state */
 271   a = b = c = raninit + ((uint32_t)(length<<2)) + *pc;
 272   c += *pb;
 273
 274   /*------------------------------------------------- handle most of the key */
 275   while (length > 3)
 276   {
 277     a += k[0];
 278     b += k[1];
 279     c += k[2];
 280     mix(a,b,c);
 281     length -= 3;
 282     k += 3;
 283   }
 284
 285   /*------------------------------------------- handle the last 3 uint32_t's */
 286   switch(length)                     /* all the case statements fall through */
 287   {
 288   case 3 : c+=k[2];
 289   case 2 : b+=k[1];
 290   case 1 : a+=k[0];
 291     final(a,b,c);
 292   case 0:     /* case 0: nothing left to add */
 293     break;
 294   }
 295   /*------------------------------------------------------ report the result */
 296   *pc=c; *pb=b;
 297 }
 298
 299 #endif /* SELF_TEST */
 300
 301 /*
 302 -------------------------------------------------------------------------------
 303 hashlittle() -- hash a variable-length key into a 32-bit value
 304   k       : the key (the unaligned variable-length array of bytes)
 305   length  : the length of the key, counting by bytes
 306   initval : can be any 4-byte value
 307 Returns a 32-bit value.  Every bit of the key affects every bit of
 308 the return value.  Two keys differing by one or two bits will have
 309 totally different hash values.
 310
 311 The best hash table sizes are powers of 2.  There is no need to do
 312 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 313 use a bitmask.  For example, if you need only 10 bits, do
 314   h = (h & hashmask(10));
 315 In which case, the hash table should have hashsize(10) elements.
 316
 317 If you are hashing n strings (uint8_t **)k, do it like this:
 318   for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
 319
 320 By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
 321 code any way you wish, private, educational, or commercial.  It's free.
 322
 323 Use for hash table lookup, or anything where one collision in 2^^32 is
 324 acceptable.  Do NOT use for cryptographic purposes.
 325 -------------------------------------------------------------------------------
 326 */
 327
 328 uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
 329 {
 330   uint32_t a,b,c;                                          /* internal state */
 331   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
 332
 333   /* Set up the internal state */
 334   a = b = c = raninit + ((uint32_t)length) + initval;
 335
 336   u.ptr = key;
 337   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
 338     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 339 #ifdef VALGRIND
 340     const uint8_t  *k8;
 341 #endif
 342
 343     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 344     while (length > 12)
 345     {
 346       a += k[0];
 347       b += k[1];
 348       c += k[2];
 349       mix(a,b,c);
 350       length -= 12;
 351       k += 3;
 352     }
 353
 354     /*----------------------------- handle the last (probably partial) block */
 355     /*
 356      * "k[2]&0xffffff" actually reads beyond the end of the string, but
 357      * then masks off the part it's not allowed to read.  Because the
 358      * string is aligned, the masked-off tail is in the same word as the
 359      * rest of the string.  Every machine with memory protection I've seen
 360      * does it on word boundaries, so is OK with this.  But VALGRIND will
 361      * still catch it and complain.  The masking trick does make the hash
 362      * noticeably faster for short strings (like English words).
 363      */
 364 #ifndef VALGRIND
 365
 366     switch(length)
 367     {
 368     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 369     case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
 370     case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
 371     case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
 372     case 8 : b+=k[1]; a+=k[0]; break;
 373     case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
 374     case 6 : b+=k[1]&0xffff; a+=k[0]; break;
 375     case 5 : b+=k[1]&0xff; a+=k[0]; break;
 376     case 4 : a+=k[0]; break;
 377     case 3 : a+=k[0]&0xffffff; break;
 378     case 2 : a+=k[0]&0xffff; break;
 379     case 1 : a+=k[0]&0xff; break;
 380     case 0 : return c;              /* zero length strings require no mixing */
 381     }
 382
 383 #else /* make valgrind happy */
 384
 385     k8 = (const uint8_t *)k;
 386     switch(length)
 387     {
 388     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 389     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
 390     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
 391     case 9 : c+=k8[8];                   /* fall through */
 392     case 8 : b+=k[1]; a+=k[0]; break;
 393     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
 394     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
 395     case 5 : b+=k8[4];                   /* fall through */
 396     case 4 : a+=k[0]; break;
 397     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
 398     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
 399     case 1 : a+=k8[0]; break;
 400     case 0 : return c;
 401     }
 402
 403 #endif /* !valgrind */
 404
 405   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
 406     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
 407     const uint8_t  *k8;
 408
 409     /*--------------- all but last block: aligned reads and different mixing */
 410     while (length > 12)
 411     {
 412       a += k[0] + (((uint32_t)k[1])<<16);
 413       b += k[2] + (((uint32_t)k[3])<<16);
 414       c += k[4] + (((uint32_t)k[5])<<16);
 415       mix(a,b,c);
 416       length -= 12;
 417       k += 6;
 418     }
 419
 420     /*----------------------------- handle the last (probably partial) block */
 421     k8 = (const uint8_t *)k;
 422     switch(length)
 423     {
 424     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
 425              b+=k[2]+(((uint32_t)k[3])<<16);
 426              a+=k[0]+(((uint32_t)k[1])<<16);
 427              break;
 428     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
 429     case 10: c+=k[4];
 430              b+=k[2]+(((uint32_t)k[3])<<16);
 431              a+=k[0]+(((uint32_t)k[1])<<16);
 432              break;
 433     case 9 : c+=k8[8];                      /* fall through */
 434     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
 435              a+=k[0]+(((uint32_t)k[1])<<16);
 436              break;
 437     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
 438     case 6 : b+=k[2];
 439              a+=k[0]+(((uint32_t)k[1])<<16);
 440              break;
 441     case 5 : b+=k8[4];                      /* fall through */
 442     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
 443              break;
 444     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
 445     case 2 : a+=k[0];
 446              break;
 447     case 1 : a+=k8[0];
 448              break;
 449     case 0 : return c;                     /* zero length requires no mixing */
 450     }
 451
 452   } else {                        /* need to read the key one byte at a time */
 453     const uint8_t *k = (const uint8_t *)key;
 454
 455     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
 456     while (length > 12)
 457     {
 458       a += k[0];
 459       a += ((uint32_t)k[1])<<8;
 460       a += ((uint32_t)k[2])<<16;
 461       a += ((uint32_t)k[3])<<24;
 462       b += k[4];
 463       b += ((uint32_t)k[5])<<8;
 464       b += ((uint32_t)k[6])<<16;
 465       b += ((uint32_t)k[7])<<24;
 466       c += k[8];
 467       c += ((uint32_t)k[9])<<8;
 468       c += ((uint32_t)k[10])<<16;
 469       c += ((uint32_t)k[11])<<24;
 470       mix(a,b,c);
 471       length -= 12;
 472       k += 12;
 473     }
 474
 475     /*-------------------------------- last block: affect all 32 bits of (c) */
 476     switch(length)                   /* all the case statements fall through */
 477     {
 478     case 12: c+=((uint32_t)k[11])<<24;
 479         /* fallthrough */
 480     case 11: c+=((uint32_t)k[10])<<16;
 481         /* fallthrough */
 482     case 10: c+=((uint32_t)k[9])<<8;
 483         /* fallthrough */
 484     case 9 : c+=k[8];
 485         /* fallthrough */
 486     case 8 : b+=((uint32_t)k[7])<<24;
 487         /* fallthrough */
 488     case 7 : b+=((uint32_t)k[6])<<16;
 489         /* fallthrough */
 490     case 6 : b+=((uint32_t)k[5])<<8;
 491         /* fallthrough */
 492     case 5 : b+=k[4];
 493         /* fallthrough */
 494     case 4 : a+=((uint32_t)k[3])<<24;
 495         /* fallthrough */
 496     case 3 : a+=((uint32_t)k[2])<<16;
 497         /* fallthrough */
 498     case 2 : a+=((uint32_t)k[1])<<8;
 499         /* fallthrough */
 500     case 1 : a+=k[0];
 501              break;
 502     case 0 : return c;
 503     }
 504   }
 505
 506   final(a,b,c);
 507   return c;
 508 }
 509
 510 #ifdef SELF_TEST
 511
 512 /*
 513  * hashlittle2: return 2 32-bit hash values
 514  *
 515  * This is identical to hashlittle(), except it returns two 32-bit hash
 516  * values instead of just one.  This is good enough for hash table
 517  * lookup with 2^^64 buckets, or if you want a second hash if you're not
 518  * happy with the first, or if you want a probably-unique 64-bit ID for
 519  * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
 520  * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
 521  */
 522 void hashlittle2(
 523   const void *key,       /* the key to hash */
 524   size_t      length,    /* length of the key */
 525   uint32_t   *pc,        /* IN: primary initval, OUT: primary hash */
 526   uint32_t   *pb)        /* IN: secondary initval, OUT: secondary hash */
 527 {
 528   uint32_t a,b,c;                                          /* internal state */
 529   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
 530
 531   /* Set up the internal state */
 532   a = b = c = raninit + ((uint32_t)length) + *pc;
 533   c += *pb;
 534
 535   u.ptr = key;
 536   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
 537     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 538 #ifdef VALGRIND
 539     const uint8_t  *k8;
 540 #endif
 541
 542     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 543     while (length > 12)
 544     {
 545       a += k[0];
 546       b += k[1];
 547       c += k[2];
 548       mix(a,b,c);
 549       length -= 12;
 550       k += 3;
 551     }
 552
 553     /*----------------------------- handle the last (probably partial) block */
 554     /*
 555      * "k[2]&0xffffff" actually reads beyond the end of the string, but
 556      * then masks off the part it's not allowed to read.  Because the
 557      * string is aligned, the masked-off tail is in the same word as the
 558      * rest of the string.  Every machine with memory protection I've seen
 559      * does it on word boundaries, so is OK with this.  But VALGRIND will
 560      * still catch it and complain.  The masking trick does make the hash
 561      * noticeably faster for short strings (like English words).
 562      */
 563 #ifndef VALGRIND
 564
 565     switch(length)
 566     {
 567     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 568     case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
 569     case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
 570     case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
 571     case 8 : b+=k[1]; a+=k[0]; break;
 572     case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
 573     case 6 : b+=k[1]&0xffff; a+=k[0]; break;
 574     case 5 : b+=k[1]&0xff; a+=k[0]; break;
 575     case 4 : a+=k[0]; break;
 576     case 3 : a+=k[0]&0xffffff; break;
 577     case 2 : a+=k[0]&0xffff; break;
 578     case 1 : a+=k[0]&0xff; break;
 579     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
 580     }
 581
 582 #else /* make valgrind happy */
 583
 584     k8 = (const uint8_t *)k;
 585     switch(length)
 586     {
 587     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 588     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
 589     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
 590     case 9 : c+=k8[8];                   /* fall through */
 591     case 8 : b+=k[1]; a+=k[0]; break;
 592     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
 593     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
 594     case 5 : b+=k8[4];                   /* fall through */
 595     case 4 : a+=k[0]; break;
 596     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
 597     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
 598     case 1 : a+=k8[0]; break;
 599     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
 600     }
 601
 602 #endif /* !valgrind */
 603
 604   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
 605     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
 606     const uint8_t  *k8;
 607
 608     /*--------------- all but last block: aligned reads and different mixing */
 609     while (length > 12)
 610     {
 611       a += k[0] + (((uint32_t)k[1])<<16);
 612       b += k[2] + (((uint32_t)k[3])<<16);
 613       c += k[4] + (((uint32_t)k[5])<<16);
 614       mix(a,b,c);
 615       length -= 12;
 616       k += 6;
 617     }
 618
 619     /*----------------------------- handle the last (probably partial) block */
 620     k8 = (const uint8_t *)k;
 621     switch(length)
 622     {
 623     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
 624              b+=k[2]+(((uint32_t)k[3])<<16);
 625              a+=k[0]+(((uint32_t)k[1])<<16);
 626              break;
 627     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
 628     case 10: c+=k[4];
 629              b+=k[2]+(((uint32_t)k[3])<<16);
 630              a+=k[0]+(((uint32_t)k[1])<<16);
 631              break;
 632     case 9 : c+=k8[8];                      /* fall through */
 633     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
 634              a+=k[0]+(((uint32_t)k[1])<<16);
 635              break;
 636     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
 637     case 6 : b+=k[2];
 638              a+=k[0]+(((uint32_t)k[1])<<16);
 639              break;
 640     case 5 : b+=k8[4];                      /* fall through */
 641     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
 642              break;
 643     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
 644     case 2 : a+=k[0];
 645              break;
 646     case 1 : a+=k8[0];
 647              break;
 648     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
 649     }
 650
 651   } else {                        /* need to read the key one byte at a time */
 652     const uint8_t *k = (const uint8_t *)key;
 653
 654     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
 655     while (length > 12)
 656     {
 657       a += k[0];
 658       a += ((uint32_t)k[1])<<8;
 659       a += ((uint32_t)k[2])<<16;
 660       a += ((uint32_t)k[3])<<24;
 661       b += k[4];
 662       b += ((uint32_t)k[5])<<8;
 663       b += ((uint32_t)k[6])<<16;
 664       b += ((uint32_t)k[7])<<24;
 665       c += k[8];
 666       c += ((uint32_t)k[9])<<8;
 667       c += ((uint32_t)k[10])<<16;
 668       c += ((uint32_t)k[11])<<24;
 669       mix(a,b,c);
 670       length -= 12;
 671       k += 12;
 672     }
 673
 674     /*-------------------------------- last block: affect all 32 bits of (c) */
 675     switch(length)                   /* all the case statements fall through */
 676     {
 677     case 12: c+=((uint32_t)k[11])<<24;
 678     case 11: c+=((uint32_t)k[10])<<16;
 679     case 10: c+=((uint32_t)k[9])<<8;
 680     case 9 : c+=k[8];
 681     case 8 : b+=((uint32_t)k[7])<<24;
 682     case 7 : b+=((uint32_t)k[6])<<16;
 683     case 6 : b+=((uint32_t)k[5])<<8;
 684     case 5 : b+=k[4];
 685     case 4 : a+=((uint32_t)k[3])<<24;
 686     case 3 : a+=((uint32_t)k[2])<<16;
 687     case 2 : a+=((uint32_t)k[1])<<8;
 688     case 1 : a+=k[0];
 689              break;
 690     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
 691     }
 692   }
 693
 694   final(a,b,c);
 695   *pc=c; *pb=b;
 696 }
 697
 698 #endif /* SELF_TEST */
 699
 700 #if 0   /* currently not used */
 701
 702 /*
 703  * hashbig():
 704  * This is the same as hashword() on big-endian machines.  It is different
 705  * from hashlittle() on all machines.  hashbig() takes advantage of
 706  * big-endian byte ordering.
 707  */
 708 uint32_t hashbig( const void *key, size_t length, uint32_t initval)
 709 {
 710   uint32_t a,b,c;
 711   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
 712
 713   /* Set up the internal state */
 714   a = b = c = raninit + ((uint32_t)length) + initval;
 715
 716   u.ptr = key;
 717   if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
 718     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 719 #ifdef VALGRIND
 720     const uint8_t  *k8;
 721 #endif
 722
 723     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 724     while (length > 12)
 725     {
 726       a += k[0];
 727       b += k[1];
 728       c += k[2];
 729       mix(a,b,c);
 730       length -= 12;
 731       k += 3;
 732     }
 733
 734     /*----------------------------- handle the last (probably partial) block */
 735     /*
 736      * "k[2]<<8" actually reads beyond the end of the string, but
 737      * then shifts out the part it's not allowed to read.  Because the
 738      * string is aligned, the illegal read is in the same word as the
 739      * rest of the string.  Every machine with memory protection I've seen
 740      * does it on word boundaries, so is OK with this.  But VALGRIND will
 741      * still catch it and complain.  The masking trick does make the hash
 742      * noticeably faster for short strings (like English words).
 743      */
 744 #ifndef VALGRIND
 745
 746     switch(length)
 747     {
 748     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 749     case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
 750     case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
 751     case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
 752     case 8 : b+=k[1]; a+=k[0]; break;
 753     case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
 754     case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
 755     case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
 756     case 4 : a+=k[0]; break;
 757     case 3 : a+=k[0]&0xffffff00; break;
 758     case 2 : a+=k[0]&0xffff0000; break;
 759     case 1 : a+=k[0]&0xff000000; break;
 760     case 0 : return c;              /* zero length strings require no mixing */
 761     }
 762
 763 #else  /* make valgrind happy */
 764
 765     k8 = (const uint8_t *)k;
 766     switch(length)                   /* all the case statements fall through */
 767     {
 768     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 769     case 11: c+=((uint32_t)k8[10])<<8;  /* fall through */
 770     case 10: c+=((uint32_t)k8[9])<<16;  /* fall through */
 771     case 9 : c+=((uint32_t)k8[8])<<24;  /* fall through */
 772     case 8 : b+=k[1]; a+=k[0]; break;
 773     case 7 : b+=((uint32_t)k8[6])<<8;   /* fall through */
 774     case 6 : b+=((uint32_t)k8[5])<<16;  /* fall through */
 775     case 5 : b+=((uint32_t)k8[4])<<24;  /* fall through */
 776     case 4 : a+=k[0]; break;
 777     case 3 : a+=((uint32_t)k8[2])<<8;   /* fall through */
 778     case 2 : a+=((uint32_t)k8[1])<<16;  /* fall through */
 779     case 1 : a+=((uint32_t)k8[0])<<24; break;
 780     case 0 : return c;
 781     }
 782
 783 #endif /* !VALGRIND */
 784
 785   } else {                        /* need to read the key one byte at a time */
 786     const uint8_t *k = (const uint8_t *)key;
 787
 788     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
 789     while (length > 12)
 790     {
 791       a += ((uint32_t)k[0])<<24;
 792       a += ((uint32_t)k[1])<<16;
 793       a += ((uint32_t)k[2])<<8;
 794       a += ((uint32_t)k[3]);
 795       b += ((uint32_t)k[4])<<24;
 796       b += ((uint32_t)k[5])<<16;
 797       b += ((uint32_t)k[6])<<8;
 798       b += ((uint32_t)k[7]);
 799       c += ((uint32_t)k[8])<<24;
 800       c += ((uint32_t)k[9])<<16;
 801       c += ((uint32_t)k[10])<<8;
 802       c += ((uint32_t)k[11]);
 803       mix(a,b,c);
 804       length -= 12;
 805       k += 12;
 806     }
 807
 808     /*-------------------------------- last block: affect all 32 bits of (c) */
 809     switch(length)                   /* all the case statements fall through */
 810     {
 811     case 12: c+=k[11];
 812     case 11: c+=((uint32_t)k[10])<<8;
 813     case 10: c+=((uint32_t)k[9])<<16;
 814     case 9 : c+=((uint32_t)k[8])<<24;
 815     case 8 : b+=k[7];
 816     case 7 : b+=((uint32_t)k[6])<<8;
 817     case 6 : b+=((uint32_t)k[5])<<16;
 818     case 5 : b+=((uint32_t)k[4])<<24;
 819     case 4 : a+=k[3];
 820     case 3 : a+=((uint32_t)k[2])<<8;
 821     case 2 : a+=((uint32_t)k[1])<<16;
 822     case 1 : a+=((uint32_t)k[0])<<24;
 823              break;
 824     case 0 : return c;
 825     }
 826   }
 827
 828   final(a,b,c);
 829   return c;
 830 }
 831
 832 #endif /* 0 == currently not used */
 833
 834 #ifdef SELF_TEST
 835
 836 /* used for timings */
 837 void driver1(void)
 838 {
 839   uint8_t buf[256];
 840   uint32_t i;
 841   uint32_t h=0;
 842   time_t a,z;
 843
 844   time(&a);
 845   for (i=0; i<256; ++i) buf[i] = 'x';
 846   for (i=0; i<1; ++i)
 847   {
 848     h = hashlittle(&buf[0],1,h);
 849   }
 850   time(&z);
 851   if (z-a > 0) printf("time %d %.8x\n", z-a, h);
 852 }
 853
 854 /* check that every input bit changes every output bit half the time */
 855 #define HASHSTATE 1
 856 #define HASHLEN   1
 857 #define MAXPAIR 60
 858 #define MAXLEN  70
 859 void driver2(void)
 860 {
 861   uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
 862   uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
 863   uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
 864   uint32_t x[HASHSTATE],y[HASHSTATE];
 865   uint32_t hlen;
 866
 867   printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
 868   for (hlen=0; hlen < MAXLEN; ++hlen)
 869   {
 870     z=0;
 871     for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */
 872     {
 873       for (j=0; j<8; ++j)   /*------------------------ for each input bit, */
 874       {
 875         for (m=1; m<8; ++m) /*------------ for several possible initvals, */
 876         {
 877           for (l=0; l<HASHSTATE; ++l)
 878             e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
 879
 880           /*---- check that every output bit is affected by that input bit */
 881           for (k=0; k<MAXPAIR; k+=2)
 882           {
 883             uint32_t finished=1;
 884             /* keys have one bit different */
 885             for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
 886             /* have a and b be two keys differing in only one bit */
 887             a[i] ^= (k<<j);
 888             a[i] ^= (k>>(8-j));
 889              c[0] = hashlittle(a, hlen, m);
 890             b[i] ^= ((k+1)<<j);
 891             b[i] ^= ((k+1)>>(8-j));
 892              d[0] = hashlittle(b, hlen, m);
 893             /* check every bit is 1, 0, set, and not set at least once */
 894             for (l=0; l<HASHSTATE; ++l)
 895             {
 896               e[l] &= (c[l]^d[l]);
 897               f[l] &= ~(c[l]^d[l]);
 898               g[l] &= c[l];
 899               h[l] &= ~c[l];
 900               x[l] &= d[l];
 901               y[l] &= ~d[l];
 902               if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
 903             }
 904             if (finished) break;
 905           }
 906           if (k>z) z=k;
 907           if (k==MAXPAIR)
 908           {
 909              printf("Some bit didn't change: ");
 910              printf("%.8x %.8x %.8x %.8x %.8x %.8x  ",
 911                     e[0],f[0],g[0],h[0],x[0],y[0]);
 912              printf("i %d j %d m %d len %d\n", i, j, m, hlen);
 913           }
 914           if (z==MAXPAIR) goto done;
 915         }
 916       }
 917     }
 918    done:
 919     if (z < MAXPAIR)
 920     {
 921       printf("Mix success  %2d bytes  %2d initvals  ",i,m);
 922       printf("required  %d  trials\n", z/2);
 923     }
 924   }
 925   printf("\n");
 926 }
 927
 928 /* Check for reading beyond the end of the buffer and alignment problems */
 929 void driver3(void)
 930 {
 931   uint8_t buf[MAXLEN+20], *b;
 932   uint32_t len;
 933   uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
 934   uint32_t h;
 935   uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
 936   uint32_t i;
 937   uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
 938   uint32_t j;
 939   uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
 940   uint32_t ref,x,y;
 941   uint8_t *p;
 942
 943   printf("Endianness.  These lines should all be the same (for values filled in):\n");
 944   printf("%.8x                            %.8x                            %.8x\n",
 945          hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
 946          hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
 947          hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
 948   p = q;
 949   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
 950          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
 951          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
 952          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
 953          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
 954          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
 955          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
 956   p = &qq[1];
 957   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
 958          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
 959          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
 960          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
 961          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
 962          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
 963          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
 964   p = &qqq[2];
 965   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
 966          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
 967          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
 968          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
 969          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
 970          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
 971          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
 972   p = &qqqq[3];
 973   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
 974          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
 975          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
 976          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
 977          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
 978          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
 979          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
 980   printf("\n");
 981
 982   /* check that hashlittle2 and hashlittle produce the same results */
 983   i=47; j=0;
 984   hashlittle2(q, sizeof(q), &i, &j);
 985   if (hashlittle(q, sizeof(q), 47) != i)
 986     printf("hashlittle2 and hashlittle mismatch\n");
 987
 988   /* check that hashword2 and hashword produce the same results */
 989   len = raninit;
 990   i=47, j=0;
 991   hashword2(&len, 1, &i, &j);
 992   if (hashword(&len, 1, 47) != i)
 993     printf("hashword2 and hashword mismatch %x %x\n",
 994            i, hashword(&len, 1, 47));
 995
 996   /* check hashlittle doesn't read before or after the ends of the string */
 997   for (h=0, b=buf+1; h<8; ++h, ++b)
 998   {
 999     for (i=0; i<MAXLEN; ++i)
1000     {
1001       len = i;
1002       for (j=0; j<i; ++j) *(b+j)=0;
1003
1004       /* these should all be equal */
1005       ref = hashlittle(b, len, (uint32_t)1);
1006       *(b+i)=(uint8_t)~0;
1007       *(b-1)=(uint8_t)~0;
1008       x = hashlittle(b, len, (uint32_t)1);
1009       y = hashlittle(b, len, (uint32_t)1);
1010       if ((ref != x) || (ref != y))
1011       {
1012         printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
1013                h, i);
1014       }
1015     }
1016   }
1017 }
1018
1019 /* check for problems with nulls */
1020  void driver4(void)
1021 {
1022   uint8_t buf[1];
1023   uint32_t h,i,state[HASHSTATE];
1024
1025
1026   buf[0] = ~0;
1027   for (i=0; i<HASHSTATE; ++i) state[i] = 1;
1028   printf("These should all be different\n");
1029   for (i=0, h=0; i<8; ++i)
1030   {
1031     h = hashlittle(buf, 0, h);
1032     printf("%2ld  0-byte strings, hash is  %.8x\n", i, h);
1033   }
1034 }
1035
1036
1037 int main(void)
1038 {
1039   driver1();   /* test that the key is hashed: used for timings */
1040   driver2();   /* test that whole key is hashed thoroughly */
1041   driver3();   /* test that nothing but the key is hashed */
1042   driver4();   /* test hashing multiple buffers (all buffers are null) */
1043   return 1;
1044 }
1045
1046 #endif  /* SELF_TEST */