10      removed include of stdint - config.h takes care of platform independence.
15 -------------------------------------------------------------------------------
18 These are functions for producing 32-bit hashes for hash table lookup.
19 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 
26 little-endian machines.  Intel and AMD are little-endian machines.
28 hashlittle() except it returns two 32-bit hashes for the price of one.  
33   mix(a,b,c);
35   mix(a,b,c);
39 4-byte integers to hash, use hashword().  If you have a byte array (like
41 a mix of things, see the comments above hashlittle().  
43 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
44 then mix those integers.  This is fast (you can do a lot more thorough
47 -------------------------------------------------------------------------------
86    * My best guess at if you are big-endian or little-endian.  This may
117 #define hashmask(n) (hashsize(n)-1)
118 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
130 -------------------------------------------------------------------------------
131 mix -- mix 3 32-bit values reversibly.
133 This is reversible, so any information in (a,b,c) before mix() is
134 still in (a,b,c) after mix().
136 If four pairs of (a,b,c) inputs are run through mix(), or through
137 mix() in reverse, there are at least 32 bits of the output that
143 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
145   is commonly produced by subtraction) look like a single 1-bit
150 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
156 for "differ" defined as + with a one-bit base and a two-bit delta.  I
165 This allows some parallelism.  Read-after-writes are good at doubling
171 -------------------------------------------------------------------------------
173 #define mix(a,b,c) \  macro
175   a -= c;  a ^= rot(c, 4);  c += b; \
176   b -= a;  b ^= rot(a, 6);  a += c; \
177   c -= b;  c ^= rot(b, 8);  b += a; \
178   a -= c;  a ^= rot(c,16);  c += b; \
179   b -= a;  b ^= rot(a,19);  a += c; \
180   c -= b;  c ^= rot(b, 4);  b += a; \
184 -------------------------------------------------------------------------------
185 final -- final mixing of 3 32-bit values (a,b,c) into c
192 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
194   is commonly produced by subtraction) look like a single 1-bit
206 -------------------------------------------------------------------------------
210   c ^= b; c -= rot(b,14); \
211   a ^= c; a -= rot(c,11); \
212   b ^= a; b -= rot(a,25); \
213   c ^= b; c -= rot(b,16); \
214   a ^= c; a -= rot(c,4);  \
215   b ^= a; b -= rot(a,14); \
216   c ^= b; c -= rot(b,24); \
220 --------------------------------------------------------------------
222  -- that the key be an array of uint32_t's, and
223  -- that the length be the number of uint32_t's in the key
225  The function hashword() is identical to hashlittle() on little-endian
226  machines, and identical to hashbig() on big-endian machines,
230 --------------------------------------------------------------------
242   /*------------------------------------------------- handle most of the key */  in hashword()
248     mix(a,b,c);  in hashword()
249     length -= 3;  in hashword()
253   /*------------------------------------------- handle the last 3 uint32_t's */  in hashword()
269   /*------------------------------------------------------ report the result */  in hashword()
277 --------------------------------------------------------------------
278 hashword2() -- same as hashword(), but take two seeds and return two
279 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
282 --------------------------------------------------------------------
296   /*------------------------------------------------- handle most of the key */  in hashword2()
302     mix(a,b,c);  in hashword2()
303     length -= 3;  in hashword2()
307   /*------------------------------------------- handle the last 3 uint32_t's */  in hashword2()
323   /*------------------------------------------------------ report the result */  in hashword2()
330 -------------------------------------------------------------------------------
331 hashlittle() -- hash a variable-length key into a 32-bit value
332   k       : the key (the unaligned variable-length array of bytes)
334   initval : can be any 4-byte value
335 Returns a 32-bit value.  Every bit of the key affects every bit of
353 -------------------------------------------------------------------------------
366     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in hashlittle()
371     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */  in hashlittle()
377       mix(a,b,c);  in hashlittle()
378       length -= 12;  in hashlittle()
382     /*----------------------------- handle the last (probably partial) block */  in hashlittle()
386      * string is aligned, the masked-off tail is in the same word as the  in hashlittle()
450     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */  in hashlittle()
453     /*--------------- all but last block: aligned reads and different mixing */  in hashlittle()
459       mix(a,b,c);  in hashlittle()
460       length -= 12;  in hashlittle()
464     /*----------------------------- handle the last (probably partial) block */  in hashlittle()
509     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */  in hashlittle()
524       mix(a,b,c);  in hashlittle()
525       length -= 12;  in hashlittle()
529     /*-------------------------------- last block: affect all 32 bits of (c) */  in hashlittle()
578  * hashlittle2: return 2 32-bit hash values
580  * This is identical to hashlittle(), except it returns two 32-bit hash
583  * happy with the first, or if you want a probably-unique 64-bit ID for
585  * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
602     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in hashlittle2()
607     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */  in hashlittle2()
613       mix(a,b,c);  in hashlittle2()
614       length -= 12;  in hashlittle2()
618     /*----------------------------- handle the last (probably partial) block */  in hashlittle2()
622      * string is aligned, the masked-off tail is in the same word as the  in hashlittle2()
686     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */  in hashlittle2()
689     /*--------------- all but last block: aligned reads and different mixing */  in hashlittle2()
695       mix(a,b,c);  in hashlittle2()
696       length -= 12;  in hashlittle2()
700     /*----------------------------- handle the last (probably partial) block */  in hashlittle2()
745     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */  in hashlittle2()
760       mix(a,b,c);  in hashlittle2()
761       length -= 12;  in hashlittle2()
765     /*-------------------------------- last block: affect all 32 bits of (c) */  in hashlittle2()
817  * This is the same as hashword() on big-endian machines.  It is different
819  * big-endian byte ordering. 
831     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
836     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
842       mix(a,b,c);
843       length -= 12;
847     /*----------------------------- handle the last (probably partial) block */
917     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
932       mix(a,b,c);
933       length -= 12;
937     /*-------------------------------- last block: affect all 32 bits of (c) */
1002   if (z-a > 0) printf("time %d %.8x\n", z-a, h);  in driver1()
1022     for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */  in driver2()
1024       for (j=0; j<8; ++j)   /*------------------------ for each input bit, */  in driver2()
1026 	for (m=1; m<8; ++m) /*------------ for several possible initvals, */  in driver2()
1031       	  /*---- check that every output bit is affected by that input bit */  in driver2()
1039 	    a[i] ^= (k>>(8-j));  in driver2()
1042 	    b[i] ^= ((k+1)>>(8-j));  in driver2()
1072       printf("Mix success  %2d bytes  %2d initvals  ",i,m);  in driver2()
1096          hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),  in driver3()
1097          hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),  in driver3()
1098          hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));  in driver3()
1101          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1102          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1103          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1104          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1105          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1106          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1109          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1110          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1111          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1112          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1113          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1114          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1117          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1118          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1119          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1120          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1121          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1122          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1125          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1126          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1127          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1128          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1129          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1130          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1158       *(b-1)=(uint8_t)~0;  in driver3()
1183     printf("%2ld  0-byte strings, hash is  %.8x\n", i, h);  in driver4()