9 -------------------------------------------------------------------------------
12 These are functions for producing 32-bit hashes for hash table lookup.
13 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 
20 little-endian machines.  Intel and AMD are little-endian machines.
22 hashlittle() except it returns two 32-bit hashes for the price of one.  
27   mix(a,b,c);
29   mix(a,b,c);
33 4-byte integers to hash, use hashword().  If you have a byte array (like
35 a mix of things, see the comments above hashlittle().  
37 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
38 then mix those integers.  This is fast (you can do a lot more thorough
41 -------------------------------------------------------------------------------
44 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
47 -------------------------------------------------------------------------------
48 mix -- mix 3 32-bit values reversibly.
50 This is reversible, so any information in (a,b,c) before mix() is
51 still in (a,b,c) after mix().
53 If four pairs of (a,b,c) inputs are run through mix(), or through
54 mix() in reverse, there are at least 32 bits of the output that
60 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
62   is commonly produced by subtraction) look like a single 1-bit
67 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
73 for "differ" defined as + with a one-bit base and a two-bit delta.  I
82 This allows some parallelism.  Read-after-writes are good at doubling
88 -------------------------------------------------------------------------------
90 #define mix(a,b,c) \  macro
92   a -= c;  a ^= rot(c, 4);  c += b; \
93   b -= a;  b ^= rot(a, 6);  a += c; \
94   c -= b;  c ^= rot(b, 8);  b += a; \
95   a -= c;  a ^= rot(c,16);  c += b; \
96   b -= a;  b ^= rot(a,19);  a += c; \
97   c -= b;  c ^= rot(b, 4);  b += a; \
101 -------------------------------------------------------------------------------
102 final -- final mixing of 3 32-bit values (a,b,c) into c
109 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
111   is commonly produced by subtraction) look like a single 1-bit
123 -------------------------------------------------------------------------------
127   c ^= b; c -= rot(b,14); \
128   a ^= c; a -= rot(c,11); \
129   b ^= a; b -= rot(a,25); \
130   c ^= b; c -= rot(b,16); \
131   a ^= c; a -= rot(c,4);  \
132   b ^= a; b -= rot(a,14); \
133   c ^= b; c -= rot(b,24); \
137 --------------------------------------------------------------------
139  -- that the key be an array of uint32_t's, and
140  -- that the length be the number of uint32_t's in the key
142  The function hashword() is identical to hashlittle() on little-endian
143  machines, and identical to hashbig() on big-endian machines,
147 --------------------------------------------------------------------
159   /*------------------------------------------------- handle most of the key */  in jenkins_hash32()
165     mix(a,b,c);  in jenkins_hash32()
166     length -= 3;  in jenkins_hash32()
170   /*------------------------------------------- handle the last 3 uint32_t's */  in jenkins_hash32()
180   /*------------------------------------------------------ report the result */  in jenkins_hash32()
186 -------------------------------------------------------------------------------
187 hashlittle() -- hash a variable-length key into a 32-bit value
188   k       : the key (the unaligned variable-length array of bytes)
190   initval : can be any 4-byte value
191 Returns a 32-bit value.  Every bit of the key affects every bit of
209 -------------------------------------------------------------------------------
222     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in jenkins_hash()
224     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */  in jenkins_hash()
230       mix(a,b,c);  in jenkins_hash()
231       length -= 12;  in jenkins_hash()
235     /*----------------------------- handle the last (probably partial) block */  in jenkins_hash()
239      * string is aligned, the masked-off tail is in the same word as the  in jenkins_hash()
264     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */  in jenkins_hash()
267     /*--------------- all but last block: aligned reads and different mixing */  in jenkins_hash()
273       mix(a,b,c);  in jenkins_hash()
274       length -= 12;  in jenkins_hash()
278     /*----------------------------- handle the last (probably partial) block */  in jenkins_hash()
313     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */  in jenkins_hash()
328       mix(a,b,c);  in jenkins_hash()
329       length -= 12;  in jenkins_hash()
333     /*-------------------------------- last block: affect all 32 bits of (c) */  in jenkins_hash()
361  * This is the same as hashword() on big-endian machines.  It is different
363  * big-endian byte ordering. 
375     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in jenkins_hash()
377     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */  in jenkins_hash()
383       mix(a,b,c);  in jenkins_hash()
384       length -= 12;  in jenkins_hash()
388     /*----------------------------- handle the last (probably partial) block */  in jenkins_hash()
419     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */  in jenkins_hash()
434       mix(a,b,c);  in jenkins_hash()
435       length -= 12;  in jenkins_hash()
439     /*-------------------------------- last block: affect all 32 bits of (c) */  in jenkins_hash()