Back to index

libcitadel  8.12
lookup3.c
Go to the documentation of this file.
00001 /*
00002 -------------------------------------------------------------------------------
00003 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
00004 
00005 These are functions for producing 32-bit hashes for hash table lookup.
00006 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 
00007 are externally useful functions.  Routines to test the hash are included 
00008 if SELF_TEST is defined.  You can use this free for any purpose.  It's in
00009 the public domain.  It has no warranty.
00010 
00011 You probably want to use hashlittle().  hashlittle() and hashbig()
00012 hash byte arrays.  hashlittle() is is faster than hashbig() on
00013 little-endian machines.  Intel and AMD are little-endian machines.
00014 On second thought, you probably want hashlittle2(), which is identical to
00015 hashlittle() except it returns two 32-bit hashes for the price of one.  
00016 You could implement hashbig2() if you wanted but I haven't bothered here.
00017 
00018 If you want to find a hash of, say, exactly 7 integers, do
00019   a = i1;  b = i2;  c = i3;
00020   mix(a,b,c);
00021   a += i4; b += i5; c += i6;
00022   mix(a,b,c);
00023   a += i7;
00024   final(a,b,c);
00025 then use c as the hash value.  If you have a variable length array of
00026 4-byte integers to hash, use hashword().  If you have a byte array (like
00027 a character string), use hashlittle().  If you have several byte arrays, or
00028 a mix of things, see the comments above hashlittle().  
00029 
00030 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
00031 then mix those integers.  This is fast (you can do a lot more thorough
00032 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
00033 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
00034 -------------------------------------------------------------------------------
00035 */
00036 //#define SELF_TEST 1
00037 
00038 #include <stdio.h>      /* defines printf for tests */
00039 #include <time.h>       /* defines time_t for timings in the test */
00040 #include <stdint.h>     /* defines uint32_t etc */
00041 #include <sys/param.h>  /* attempt to define endianness */
00042 #ifdef linux
00043 # include <endian.h>    /* attempt to define endianness */
00044 #endif
00045 #include "lookup3.h"
00046 /*
00047  * My best guess at if you are big-endian or little-endian.  This may
00048  * need adjustment.
00049  */
00050 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
00051      __BYTE_ORDER == __LITTLE_ENDIAN) || \
00052     (defined(i386) || defined(__i386__) || defined(__i486__) || \
00053      defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
00054 # define HASH_LITTLE_ENDIAN 1
00055 # define HASH_BIG_ENDIAN 0
00056 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
00057        __BYTE_ORDER == __BIG_ENDIAN) || \
00058       (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
00059 # define HASH_LITTLE_ENDIAN 0
00060 # define HASH_BIG_ENDIAN 1
00061 #else
00062 # define HASH_LITTLE_ENDIAN 0
00063 # define HASH_BIG_ENDIAN 0
00064 #endif
00065 
00066 #define hashsize(n) ((uint32_t)1<<(n))
00067 #define hashmask(n) (hashsize(n)-1)
00068 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
00069 
00070 /*
00071 -------------------------------------------------------------------------------
00072 mix -- mix 3 32-bit values reversibly.
00073 
00074 This is reversible, so any information in (a,b,c) before mix() is
00075 still in (a,b,c) after mix().
00076 
00077 If four pairs of (a,b,c) inputs are run through mix(), or through
00078 mix() in reverse, there are at least 32 bits of the output that
00079 are sometimes the same for one pair and different for another pair.
00080 This was tested for:
00081 * pairs that differed by one bit, by two bits, in any combination
00082   of top bits of (a,b,c), or in any combination of bottom bits of
00083   (a,b,c).
00084 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
00085   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
00086   is commonly produced by subtraction) look like a single 1-bit
00087   difference.
00088 * the base values were pseudorandom, all zero but one bit set, or 
00089   all zero plus a counter that starts at zero.
00090 
00091 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
00092 satisfy this are
00093     4  6  8 16 19  4
00094     9 15  3 18 27 15
00095    14  9  3  7 17  3
00096 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
00097 for "differ" defined as + with a one-bit base and a two-bit delta.  I
00098 used http://burtleburtle.net/bob/hash/avalanche.html to choose 
00099 the operations, constants, and arrangements of the variables.
00100 
00101 This does not achieve avalanche.  There are input bits of (a,b,c)
00102 that fail to affect some output bits of (a,b,c), especially of a.  The
00103 most thoroughly mixed value is c, but it doesn't really even achieve
00104 avalanche in c.
00105 
00106 This allows some parallelism.  Read-after-writes are good at doubling
00107 the number of bits affected, so the goal of mixing pulls in the opposite
00108 direction as the goal of parallelism.  I did what I could.  Rotates
00109 seem to cost as much as shifts on every machine I could lay my hands
00110 on, and rotates are much kinder to the top and bottom bits, so I used
00111 rotates.
00112 -------------------------------------------------------------------------------
00113 */
00114 #define mix(a,b,c) \
00115 { \
00116   a -= c;  a ^= rot(c, 4);  c += b; \
00117   b -= a;  b ^= rot(a, 6);  a += c; \
00118   c -= b;  c ^= rot(b, 8);  b += a; \
00119   a -= c;  a ^= rot(c,16);  c += b; \
00120   b -= a;  b ^= rot(a,19);  a += c; \
00121   c -= b;  c ^= rot(b, 4);  b += a; \
00122 }
00123 
00124 /*
00125 -------------------------------------------------------------------------------
00126 final -- final mixing of 3 32-bit values (a,b,c) into c
00127 
00128 Pairs of (a,b,c) values differing in only a few bits will usually
00129 produce values of c that look totally different.  This was tested for
00130 * pairs that differed by one bit, by two bits, in any combination
00131   of top bits of (a,b,c), or in any combination of bottom bits of
00132   (a,b,c).
00133 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
00134   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
00135   is commonly produced by subtraction) look like a single 1-bit
00136   difference.
00137 * the base values were pseudorandom, all zero but one bit set, or 
00138   all zero plus a counter that starts at zero.
00139 
00140 These constants passed:
00141  14 11 25 16 4 14 24
00142  12 14 25 16 4 14 24
00143 and these came close:
00144   4  8 15 26 3 22 24
00145  10  8 15 26 3 22 24
00146  11  8 15 26 3 22 24
00147 -------------------------------------------------------------------------------
00148 */
00149 #define final(a,b,c) \
00150 { \
00151   c ^= b; c -= rot(b,14); \
00152   a ^= c; a -= rot(c,11); \
00153   b ^= a; b -= rot(a,25); \
00154   c ^= b; c -= rot(b,16); \
00155   a ^= c; a -= rot(c,4);  \
00156   b ^= a; b -= rot(a,14); \
00157   c ^= b; c -= rot(b,24); \
00158 }
00159 
00160 /*
00161 --------------------------------------------------------------------
00162  This works on all machines.  To be useful, it requires
00163  -- that the key be an array of uint32_t's, and
00164  -- that the length be the number of uint32_t's in the key
00165 
00166  The function hashword() is identical to hashlittle() on little-endian
00167  machines, and identical to hashbig() on big-endian machines,
00168  except that the length has to be measured in uint32_ts rather than in
00169  bytes.  hashlittle() is more complicated than hashword() only because
00170  hashlittle() has to dance around fitting the key bytes into registers.
00171 --------------------------------------------------------------------
00172 */
00173 #if 0 // libcitadel doesn't use this.
00174 uint32_t hashword(
00175 const uint32_t *k,                   /* the key, an array of uint32_t values */
00176 size_t          length,               /* the length of the key, in uint32_ts */
00177 uint32_t        initval)         /* the previous hash, or an arbitrary value */
00178 {
00179   uint32_t a,b,c;
00180 
00181   /* Set up the internal state */
00182   a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
00183 
00184   /*------------------------------------------------- handle most of the key */
00185   while (length > 3)
00186   {
00187     a += k[0];
00188     b += k[1];
00189     c += k[2];
00190     mix(a,b,c);
00191     length -= 3;
00192     k += 3;
00193   }
00194 
00195   /*------------------------------------------- handle the last 3 uint32_t's */
00196   switch(length)                     /* all the case statements fall through */
00197   { 
00198   case 3 : c+=k[2];
00199   case 2 : b+=k[1];
00200   case 1 : a+=k[0];
00201     final(a,b,c);
00202   case 0:     /* case 0: nothing left to add */
00203     break;
00204   }
00205   /*------------------------------------------------------ report the result */
00206   return c;
00207 }
00208 #endif 
00209 
00210 /*
00211 --------------------------------------------------------------------
00212 hashword2() -- same as hashword(), but take two seeds and return two
00213 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
00214 both be initialized with seeds.  If you pass in (*pb)==0, the output 
00215 (*pc) will be the same as the return value from hashword().
00216 --------------------------------------------------------------------
00217 */
00218 #if 0 // libcitadel doesn't use this.
00219 void hashword2 (
00220 const uint32_t *k,                   /* the key, an array of uint32_t values */
00221 size_t          length,               /* the length of the key, in uint32_ts */
00222 uint32_t       *pc,                      /* IN: seed OUT: primary hash value */
00223 uint32_t       *pb)               /* IN: more seed OUT: secondary hash value */
00224 {
00225   uint32_t a,b,c;
00226 
00227   /* Set up the internal state */
00228   a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
00229   c += *pb;
00230 
00231   /*------------------------------------------------- handle most of the key */
00232   while (length > 3)
00233   {
00234     a += k[0];
00235     b += k[1];
00236     c += k[2];
00237     mix(a,b,c);
00238     length -= 3;
00239     k += 3;
00240   }
00241 
00242   /*------------------------------------------- handle the last 3 uint32_t's */
00243   switch(length)                     /* all the case statements fall through */
00244   { 
00245   case 3 : c+=k[2];
00246   case 2 : b+=k[1];
00247   case 1 : a+=k[0];
00248     final(a,b,c);
00249   case 0:     /* case 0: nothing left to add */
00250     break;
00251   }
00252   /*------------------------------------------------------ report the result */
00253   *pc=c; *pb=b;
00254 }
00255 #endif
00256 
00257 /*
00258 -------------------------------------------------------------------------------
00259 hashlittle() -- hash a variable-length key into a 32-bit value
00260   k       : the key (the unaligned variable-length array of bytes)
00261   length  : the length of the key, counting by bytes
00262   initval : can be any 4-byte value
00263 Returns a 32-bit value.  Every bit of the key affects every bit of
00264 the return value.  Two keys differing by one or two bits will have
00265 totally different hash values.
00266 
00267 The best hash table sizes are powers of 2.  There is no need to do
00268 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
00269 use a bitmask.  For example, if you need only 10 bits, do
00270   h = (h & hashmask(10));
00271 In which case, the hash table should have hashsize(10) elements.
00272 
00273 If you are hashing n strings (uint8_t **)k, do it like this:
00274   for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
00275 
00276 By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
00277 code any way you wish, private, educational, or commercial.  It's free.
00278 
00279 Use for hash table lookup, or anything where one collision in 2^^32 is
00280 acceptable.  Do NOT use for cryptographic purposes.
00281 -------------------------------------------------------------------------------
00282 */
00283 
00284 uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
00285 {
00286   uint32_t a,b,c;                                          /* internal state */
00287   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
00288 
00289   /* Set up the internal state */
00290   a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
00291 
00292   u.ptr = key;
00293   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
00294     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
00295 #ifdef VALGRIND
00296     const uint8_t  *k8;
00297 #endif
00298     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
00299     while (length > 12)
00300     {
00301       a += k[0];
00302       b += k[1];
00303       c += k[2];
00304       mix(a,b,c);
00305       length -= 12;
00306       k += 3;
00307     }
00308 
00309     /*----------------------------- handle the last (probably partial) block */
00310     /* 
00311      * "k[2]&0xffffff" actually reads beyond the end of the string, but
00312      * then masks off the part it's not allowed to read.  Because the
00313      * string is aligned, the masked-off tail is in the same word as the
00314      * rest of the string.  Every machine with memory protection I've seen
00315      * does it on word boundaries, so is OK with this.  But VALGRIND will
00316      * still catch it and complain.  The masking trick does make the hash
00317      * noticably faster for short strings (like English words).
00318      */
00319 #ifndef VALGRIND
00320 
00321     switch(length)
00322     {
00323     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
00324     case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
00325     case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
00326     case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
00327     case 8 : b+=k[1]; a+=k[0]; break;
00328     case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
00329     case 6 : b+=k[1]&0xffff; a+=k[0]; break;
00330     case 5 : b+=k[1]&0xff; a+=k[0]; break;
00331     case 4 : a+=k[0]; break;
00332     case 3 : a+=k[0]&0xffffff; break;
00333     case 2 : a+=k[0]&0xffff; break;
00334     case 1 : a+=k[0]&0xff; break;
00335     case 0 : return c;              /* zero length strings require no mixing */
00336     }
00337 
00338 #else /* make valgrind happy */
00339 
00340     k8 = (const uint8_t *)k;
00341     switch(length)
00342     {
00343     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
00344     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
00345     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
00346     case 9 : c+=k8[8];                   /* fall through */
00347     case 8 : b+=k[1]; a+=k[0]; break;
00348     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
00349     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
00350     case 5 : b+=k8[4];                   /* fall through */
00351     case 4 : a+=k[0]; break;
00352     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
00353     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
00354     case 1 : a+=k8[0]; break;
00355     case 0 : return c;
00356     }
00357 
00358 #endif /* !valgrind */
00359 
00360   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
00361     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
00362     const uint8_t  *k8;
00363 
00364     /*--------------- all but last block: aligned reads and different mixing */
00365     while (length > 12)
00366     {
00367       a += k[0] + (((uint32_t)k[1])<<16);
00368       b += k[2] + (((uint32_t)k[3])<<16);
00369       c += k[4] + (((uint32_t)k[5])<<16);
00370       mix(a,b,c);
00371       length -= 12;
00372       k += 6;
00373     }
00374 
00375     /*----------------------------- handle the last (probably partial) block */
00376     k8 = (const uint8_t *)k;
00377     switch(length)
00378     {
00379     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
00380              b+=k[2]+(((uint32_t)k[3])<<16);
00381              a+=k[0]+(((uint32_t)k[1])<<16);
00382              break;
00383     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
00384     case 10: c+=k[4];
00385              b+=k[2]+(((uint32_t)k[3])<<16);
00386              a+=k[0]+(((uint32_t)k[1])<<16);
00387              break;
00388     case 9 : c+=k8[8];                      /* fall through */
00389     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
00390              a+=k[0]+(((uint32_t)k[1])<<16);
00391              break;
00392     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
00393     case 6 : b+=k[2];
00394              a+=k[0]+(((uint32_t)k[1])<<16);
00395              break;
00396     case 5 : b+=k8[4];                      /* fall through */
00397     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
00398              break;
00399     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
00400     case 2 : a+=k[0];
00401              break;
00402     case 1 : a+=k8[0];
00403              break;
00404     case 0 : return c;                     /* zero length requires no mixing */
00405     }
00406 
00407   } else {                        /* need to read the key one byte at a time */
00408     const uint8_t *k = (const uint8_t *)key;
00409 
00410     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
00411     while (length > 12)
00412     {
00413       a += k[0];
00414       a += ((uint32_t)k[1])<<8;
00415       a += ((uint32_t)k[2])<<16;
00416       a += ((uint32_t)k[3])<<24;
00417       b += k[4];
00418       b += ((uint32_t)k[5])<<8;
00419       b += ((uint32_t)k[6])<<16;
00420       b += ((uint32_t)k[7])<<24;
00421       c += k[8];
00422       c += ((uint32_t)k[9])<<8;
00423       c += ((uint32_t)k[10])<<16;
00424       c += ((uint32_t)k[11])<<24;
00425       mix(a,b,c);
00426       length -= 12;
00427       k += 12;
00428     }
00429 
00430     /*-------------------------------- last block: affect all 32 bits of (c) */
00431     switch(length)                   /* all the case statements fall through */
00432     {
00433     case 12: c+=((uint32_t)k[11])<<24;
00434     case 11: c+=((uint32_t)k[10])<<16;
00435     case 10: c+=((uint32_t)k[9])<<8;
00436     case 9 : c+=k[8];
00437     case 8 : b+=((uint32_t)k[7])<<24;
00438     case 7 : b+=((uint32_t)k[6])<<16;
00439     case 6 : b+=((uint32_t)k[5])<<8;
00440     case 5 : b+=k[4];
00441     case 4 : a+=((uint32_t)k[3])<<24;
00442     case 3 : a+=((uint32_t)k[2])<<16;
00443     case 2 : a+=((uint32_t)k[1])<<8;
00444     case 1 : a+=k[0];
00445              break;
00446     case 0 : return c;
00447     }
00448   }
00449 
00450   final(a,b,c);
00451   return c;
00452 }
00453 
00454 
00455 /*
00456  * hashlittle2: return 2 32-bit hash values
00457  *
00458  * This is identical to hashlittle(), except it returns two 32-bit hash
00459  * values instead of just one.  This is good enough for hash table
00460  * lookup with 2^^64 buckets, or if you want a second hash if you're not
00461  * happy with the first, or if you want a probably-unique 64-bit ID for
00462  * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
00463  * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
00464  */
00465 #if 0 // libcitadel doesn't use this.
00466 void hashlittle2( 
00467   const void *key,       /* the key to hash */
00468   size_t      length,    /* length of the key */
00469   uint32_t   *pc,        /* IN: primary initval, OUT: primary hash */
00470   uint32_t   *pb)        /* IN: secondary initval, OUT: secondary hash */
00471 {
00472   uint32_t a,b,c;                                          /* internal state */
00473   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
00474 
00475   /* Set up the internal state */
00476   a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
00477   c += *pb;
00478 
00479   u.ptr = key;
00480   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
00481     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
00482 #ifdef VALGRIND
00483     const uint8_t  *k8;
00484 #endif
00485 
00486     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
00487     while (length > 12)
00488     {
00489       a += k[0];
00490       b += k[1];
00491       c += k[2];
00492       mix(a,b,c);
00493       length -= 12;
00494       k += 3;
00495     }
00496 
00497     /*----------------------------- handle the last (probably partial) block */
00498     /* 
00499      * "k[2]&0xffffff" actually reads beyond the end of the string, but
00500      * then masks off the part it's not allowed to read.  Because the
00501      * string is aligned, the masked-off tail is in the same word as the
00502      * rest of the string.  Every machine with memory protection I've seen
00503      * does it on word boundaries, so is OK with this.  But VALGRIND will
00504      * still catch it and complain.  The masking trick does make the hash
00505      * noticably faster for short strings (like English words).
00506      */
00507 #ifndef VALGRIND
00508 
00509     switch(length)
00510     {
00511     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
00512     case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
00513     case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
00514     case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
00515     case 8 : b+=k[1]; a+=k[0]; break;
00516     case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
00517     case 6 : b+=k[1]&0xffff; a+=k[0]; break;
00518     case 5 : b+=k[1]&0xff; a+=k[0]; break;
00519     case 4 : a+=k[0]; break;
00520     case 3 : a+=k[0]&0xffffff; break;
00521     case 2 : a+=k[0]&0xffff; break;
00522     case 1 : a+=k[0]&0xff; break;
00523     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
00524     }
00525 
00526 #else /* make valgrind happy */
00527 
00528     k8 = (const uint8_t *)k;
00529     switch(length)
00530     {
00531     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
00532     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
00533     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
00534     case 9 : c+=k8[8];                   /* fall through */
00535     case 8 : b+=k[1]; a+=k[0]; break;
00536     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
00537     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
00538     case 5 : b+=k8[4];                   /* fall through */
00539     case 4 : a+=k[0]; break;
00540     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
00541     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
00542     case 1 : a+=k8[0]; break;
00543     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
00544     }
00545 
00546 #endif /* !valgrind */
00547 
00548   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
00549     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
00550     const uint8_t  *k8;
00551 
00552     /*--------------- all but last block: aligned reads and different mixing */
00553     while (length > 12)
00554     {
00555       a += k[0] + (((uint32_t)k[1])<<16);
00556       b += k[2] + (((uint32_t)k[3])<<16);
00557       c += k[4] + (((uint32_t)k[5])<<16);
00558       mix(a,b,c);
00559       length -= 12;
00560       k += 6;
00561     }
00562 
00563     /*----------------------------- handle the last (probably partial) block */
00564     k8 = (const uint8_t *)k;
00565     switch(length)
00566     {
00567     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
00568              b+=k[2]+(((uint32_t)k[3])<<16);
00569              a+=k[0]+(((uint32_t)k[1])<<16);
00570              break;
00571     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
00572     case 10: c+=k[4];
00573              b+=k[2]+(((uint32_t)k[3])<<16);
00574              a+=k[0]+(((uint32_t)k[1])<<16);
00575              break;
00576     case 9 : c+=k8[8];                      /* fall through */
00577     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
00578              a+=k[0]+(((uint32_t)k[1])<<16);
00579              break;
00580     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
00581     case 6 : b+=k[2];
00582              a+=k[0]+(((uint32_t)k[1])<<16);
00583              break;
00584     case 5 : b+=k8[4];                      /* fall through */
00585     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
00586              break;
00587     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
00588     case 2 : a+=k[0];
00589              break;
00590     case 1 : a+=k8[0];
00591              break;
00592     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
00593     }
00594 
00595   } else {                        /* need to read the key one byte at a time */
00596     const uint8_t *k = (const uint8_t *)key;
00597 
00598     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
00599     while (length > 12)
00600     {
00601       a += k[0];
00602       a += ((uint32_t)k[1])<<8;
00603       a += ((uint32_t)k[2])<<16;
00604       a += ((uint32_t)k[3])<<24;
00605       b += k[4];
00606       b += ((uint32_t)k[5])<<8;
00607       b += ((uint32_t)k[6])<<16;
00608       b += ((uint32_t)k[7])<<24;
00609       c += k[8];
00610       c += ((uint32_t)k[9])<<8;
00611       c += ((uint32_t)k[10])<<16;
00612       c += ((uint32_t)k[11])<<24;
00613       mix(a,b,c);
00614       length -= 12;
00615       k += 12;
00616     }
00617 
00618     /*-------------------------------- last block: affect all 32 bits of (c) */
00619     switch(length)                   /* all the case statements fall through */
00620     {
00621     case 12: c+=((uint32_t)k[11])<<24;
00622     case 11: c+=((uint32_t)k[10])<<16;
00623     case 10: c+=((uint32_t)k[9])<<8;
00624     case 9 : c+=k[8];
00625     case 8 : b+=((uint32_t)k[7])<<24;
00626     case 7 : b+=((uint32_t)k[6])<<16;
00627     case 6 : b+=((uint32_t)k[5])<<8;
00628     case 5 : b+=k[4];
00629     case 4 : a+=((uint32_t)k[3])<<24;
00630     case 3 : a+=((uint32_t)k[2])<<16;
00631     case 2 : a+=((uint32_t)k[1])<<8;
00632     case 1 : a+=k[0];
00633              break;
00634     case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
00635     }
00636   }
00637 
00638   final(a,b,c);
00639   *pc=c; *pb=b;
00640 }
00641 #endif
00642 
00643 
00644 /*
00645  * hashbig():
00646  * This is the same as hashword() on big-endian machines.  It is different
00647  * from hashlittle() on all machines.  hashbig() takes advantage of
00648  * big-endian byte ordering. 
00649  */
00650 #if 0 // libcitadel doesn't use this.
00651 uint32_t hashbig( const void *key, size_t length, uint32_t initval)
00652 {
00653   uint32_t a,b,c;
00654   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
00655 
00656   /* Set up the internal state */
00657   a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
00658 
00659   u.ptr = key;
00660   if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
00661     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
00662 #ifdef VALGRIND
00663     const uint8_t  *k8;
00664 #endif
00665     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
00666     while (length > 12)
00667     {
00668       a += k[0];
00669       b += k[1];
00670       c += k[2];
00671       mix(a,b,c);
00672       length -= 12;
00673       k += 3;
00674     }
00675 
00676     /*----------------------------- handle the last (probably partial) block */
00677     /* 
00678      * "k[2]<<8" actually reads beyond the end of the string, but
00679      * then shifts out the part it's not allowed to read.  Because the
00680      * string is aligned, the illegal read is in the same word as the
00681      * rest of the string.  Every machine with memory protection I've seen
00682      * does it on word boundaries, so is OK with this.  But VALGRIND will
00683      * still catch it and complain.  The masking trick does make the hash
00684      * noticably faster for short strings (like English words).
00685      */
00686 #ifndef VALGRIND
00687 
00688     switch(length)
00689     {
00690     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
00691     case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
00692     case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
00693     case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
00694     case 8 : b+=k[1]; a+=k[0]; break;
00695     case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
00696     case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
00697     case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
00698     case 4 : a+=k[0]; break;
00699     case 3 : a+=k[0]&0xffffff00; break;
00700     case 2 : a+=k[0]&0xffff0000; break;
00701     case 1 : a+=k[0]&0xff000000; break;
00702     case 0 : return c;              /* zero length strings require no mixing */
00703     }
00704 
00705 #else  /* make valgrind happy */
00706 
00707     k8 = (const uint8_t *)k;
00708     switch(length)                   /* all the case statements fall through */
00709     {
00710     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
00711     case 11: c+=((uint32_t)k8[10])<<8;  /* fall through */
00712     case 10: c+=((uint32_t)k8[9])<<16;  /* fall through */
00713     case 9 : c+=((uint32_t)k8[8])<<24;  /* fall through */
00714     case 8 : b+=k[1]; a+=k[0]; break;
00715     case 7 : b+=((uint32_t)k8[6])<<8;   /* fall through */
00716     case 6 : b+=((uint32_t)k8[5])<<16;  /* fall through */
00717     case 5 : b+=((uint32_t)k8[4])<<24;  /* fall through */
00718     case 4 : a+=k[0]; break;
00719     case 3 : a+=((uint32_t)k8[2])<<8;   /* fall through */
00720     case 2 : a+=((uint32_t)k8[1])<<16;  /* fall through */
00721     case 1 : a+=((uint32_t)k8[0])<<24; break;
00722     case 0 : return c;
00723     }
00724 
00725 #endif /* !VALGRIND */
00726 
00727   } else {                        /* need to read the key one byte at a time */
00728     const uint8_t *k = (const uint8_t *)key;
00729 
00730     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
00731     while (length > 12)
00732     {
00733       a += ((uint32_t)k[0])<<24;
00734       a += ((uint32_t)k[1])<<16;
00735       a += ((uint32_t)k[2])<<8;
00736       a += ((uint32_t)k[3]);
00737       b += ((uint32_t)k[4])<<24;
00738       b += ((uint32_t)k[5])<<16;
00739       b += ((uint32_t)k[6])<<8;
00740       b += ((uint32_t)k[7]);
00741       c += ((uint32_t)k[8])<<24;
00742       c += ((uint32_t)k[9])<<16;
00743       c += ((uint32_t)k[10])<<8;
00744       c += ((uint32_t)k[11]);
00745       mix(a,b,c);
00746       length -= 12;
00747       k += 12;
00748     }
00749 
00750     /*-------------------------------- last block: affect all 32 bits of (c) */
00751     switch(length)                   /* all the case statements fall through */
00752     {
00753     case 12: c+=k[11];
00754     case 11: c+=((uint32_t)k[10])<<8;
00755     case 10: c+=((uint32_t)k[9])<<16;
00756     case 9 : c+=((uint32_t)k[8])<<24;
00757     case 8 : b+=k[7];
00758     case 7 : b+=((uint32_t)k[6])<<8;
00759     case 6 : b+=((uint32_t)k[5])<<16;
00760     case 5 : b+=((uint32_t)k[4])<<24;
00761     case 4 : a+=k[3];
00762     case 3 : a+=((uint32_t)k[2])<<8;
00763     case 2 : a+=((uint32_t)k[1])<<16;
00764     case 1 : a+=((uint32_t)k[0])<<24;
00765              break;
00766     case 0 : return c;
00767     }
00768   }
00769 
00770   final(a,b,c);
00771   return c;
00772 }
00773 #endif
00774 
00775 #ifdef SELF_TEST
00776 
00777 /* used for timings */
00778 void driver1()
00779 {
00780   uint8_t buf[256];
00781   uint32_t i;
00782   uint32_t h=0;
00783   time_t a,z;
00784 
00785   time(&a);
00786   for (i=0; i<256; ++i) buf[i] = 'x';
00787   for (i=0; i<1; ++i) 
00788   {
00789     h = hashlittle(&buf[0],1,h);
00790   }
00791   time(&z);
00792   if (z-a > 0) printf("time %d %.8x\n", z-a, h);
00793 }
00794 
00795 /* check that every input bit changes every output bit half the time */
00796 #define HASHSTATE 1
00797 #define HASHLEN   1
00798 #define MAXPAIR 60
00799 #define MAXLEN  70
00800 void driver2()
00801 {
00802   uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
00803   uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
00804   uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
00805   uint32_t x[HASHSTATE],y[HASHSTATE];
00806   uint32_t hlen;
00807 
00808   printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
00809   for (hlen=0; hlen < MAXLEN; ++hlen)
00810   {
00811     z=0;
00812     for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */
00813     {
00814       for (j=0; j<8; ++j)   /*------------------------ for each input bit, */
00815       {
00816        for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
00817        {
00818          for (l=0; l<HASHSTATE; ++l)
00819            e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
00820 
00821          /*---- check that every output bit is affected by that input bit */
00822          for (k=0; k<MAXPAIR; k+=2)
00823          { 
00824            uint32_t finished=1;
00825            /* keys have one bit different */
00826            for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
00827            /* have a and b be two keys differing in only one bit */
00828            a[i] ^= (k<<j);
00829            a[i] ^= (k>>(8-j));
00830             c[0] = hashlittle(a, hlen, m);
00831            b[i] ^= ((k+1)<<j);
00832            b[i] ^= ((k+1)>>(8-j));
00833             d[0] = hashlittle(b, hlen, m);
00834            /* check every bit is 1, 0, set, and not set at least once */
00835            for (l=0; l<HASHSTATE; ++l)
00836            {
00837              e[l] &= (c[l]^d[l]);
00838              f[l] &= ~(c[l]^d[l]);
00839              g[l] &= c[l];
00840              h[l] &= ~c[l];
00841              x[l] &= d[l];
00842              y[l] &= ~d[l];
00843              if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
00844            }
00845            if (finished) break;
00846          }
00847          if (k>z) z=k;
00848          if (k==MAXPAIR) 
00849          {
00850             printf("Some bit didn't change: ");
00851             printf("%.8x %.8x %.8x %.8x %.8x %.8x  ",
00852                    e[0],f[0],g[0],h[0],x[0],y[0]);
00853             printf("i %d j %d m %d len %d\n", i, j, m, hlen);
00854          }
00855          if (z==MAXPAIR) goto done;
00856        }
00857       }
00858     }
00859    done:
00860     if (z < MAXPAIR)
00861     {
00862       printf("Mix success  %2d bytes  %2d initvals  ",i,m);
00863       printf("required  %d  trials\n", z/2);
00864     }
00865   }
00866   printf("\n");
00867 }
00868 
00869 /* Check for reading beyond the end of the buffer and alignment problems */
00870 void driver3()
00871 {
00872   uint8_t buf[MAXLEN+20], *b;
00873   uint32_t len;
00874   uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
00875   uint32_t h;
00876   uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
00877   uint32_t i;
00878   uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
00879   uint32_t j;
00880   uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
00881   uint32_t ref,x,y;
00882   uint8_t *p;
00883 
00884   printf("Endianness.  These lines should all be the same (for values filled in):\n");
00885   printf("%.8x                            %.8x                            %.8x\n",
00886          hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
00887          hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
00888          hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
00889   p = q;
00890   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00891          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
00892          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
00893          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
00894          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
00895          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
00896          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
00897   p = &qq[1];
00898   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00899          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
00900          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
00901          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
00902          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
00903          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
00904          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
00905   p = &qqq[2];
00906   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00907          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
00908          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
00909          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
00910          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
00911          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
00912          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
00913   p = &qqqq[3];
00914   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
00915          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
00916          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
00917          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
00918          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
00919          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
00920          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
00921   printf("\n");
00922 
00923   /* check that hashlittle2 and hashlittle produce the same results */
00924   i=47; j=0;
00925   hashlittle2(q, sizeof(q), &i, &j);
00926   if (hashlittle(q, sizeof(q), 47) != i)
00927     printf("hashlittle2 and hashlittle mismatch\n");
00928 
00929   /* check that hashword2 and hashword produce the same results */
00930   len = 0xdeadbeef;
00931   i=47, j=0;
00932   hashword2(&len, 1, &i, &j);
00933   if (hashword(&len, 1, 47) != i)
00934     printf("hashword2 and hashword mismatch %x %x\n", 
00935           i, hashword(&len, 1, 47));
00936 
00937   /* check hashlittle doesn't read before or after the ends of the string */
00938   for (h=0, b=buf+1; h<8; ++h, ++b)
00939   {
00940     for (i=0; i<MAXLEN; ++i)
00941     {
00942       len = i;
00943       for (j=0; j<i; ++j) *(b+j)=0;
00944 
00945       /* these should all be equal */
00946       ref = hashlittle(b, len, (uint32_t)1);
00947       *(b+i)=(uint8_t)~0;
00948       *(b-1)=(uint8_t)~0;
00949       x = hashlittle(b, len, (uint32_t)1);
00950       y = hashlittle(b, len, (uint32_t)1);
00951       if ((ref != x) || (ref != y)) 
00952       {
00953        printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
00954                h, i);
00955       }
00956     }
00957   }
00958 }
00959 
00960 /* check for problems with nulls */
00961  void driver4()
00962 {
00963   uint8_t buf[1];
00964   uint32_t h,i,state[HASHSTATE];
00965 
00966 
00967   buf[0] = ~0;
00968   for (i=0; i<HASHSTATE; ++i) state[i] = 1;
00969   printf("These should all be different\n");
00970   for (i=0, h=0; i<8; ++i)
00971   {
00972     h = hashlittle(buf, 0, h);
00973     printf("%2ld  0-byte strings, hash is  %.8x\n", i, h);
00974   }
00975 }
00976 
00977 
00978 int main()
00979 {
00980   driver1();   /* test that the key is hashed: used for timings */
00981   driver2();   /* test that whole key is hashed thoroughly */
00982   driver3();   /* test that nothing but the key is hashed */
00983   driver4();   /* test hashing multiple buffers (all buffers are null) */
00984   return 1;
00985 }
00986 
00987 #endif  /* SELF_TEST */