2 * Taken from http://burtleburtle.net/bob/c/lookup3.c
7 #include <machine/endian.h>
10 -------------------------------------------------------------------------------
11 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
13 These are functions for producing 32-bit hashes for hash table lookup.
14 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
15 are externally useful functions. Routines to test the hash are included
16 if SELF_TEST is defined. You can use this free for any purpose. It's in
17 the public domain. It has no warranty.
19 You probably want to use hashlittle(). hashlittle() and hashbig()
20 hash byte arrays. hashlittle() is faster than hashbig() on
21 little-endian machines. Intel and AMD are little-endian machines.
22 On second thought, you probably want hashlittle2(), which is identical to
23 hashlittle() except it returns two 32-bit hashes for the price of one.
24 You could implement hashbig2() if you wanted but I haven't bothered here.
26 If you want to find a hash of, say, exactly 7 integers, do
27 a = i1; b = i2; c = i3;
29 a += i4; b += i5; c += i6;
33 then use c as the hash value. If you have a variable length array of
34 4-byte integers to hash, use hashword(). If you have a byte array (like
35 a character string), use hashlittle(). If you have several byte arrays, or
36 a mix of things, see the comments above hashlittle().
38 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
39 then mix those integers. This is fast (you can do a lot more thorough
40 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
41 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
42 -------------------------------------------------------------------------------
45 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
48 -------------------------------------------------------------------------------
49 mix -- mix 3 32-bit values reversibly.
51 This is reversible, so any information in (a,b,c) before mix() is
52 still in (a,b,c) after mix().
54 If four pairs of (a,b,c) inputs are run through mix(), or through
55 mix() in reverse, there are at least 32 bits of the output that
56 are sometimes the same for one pair and different for another pair.
58 * pairs that differed by one bit, by two bits, in any combination
59 of top bits of (a,b,c), or in any combination of bottom bits of
61 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
62 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
63 is commonly produced by subtraction) look like a single 1-bit
65 * the base values were pseudorandom, all zero but one bit set, or
66 all zero plus a counter that starts at zero.
68 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
73 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
74 for "differ" defined as + with a one-bit base and a two-bit delta. I
75 used http://burtleburtle.net/bob/hash/avalanche.html to choose
76 the operations, constants, and arrangements of the variables.
78 This does not achieve avalanche. There are input bits of (a,b,c)
79 that fail to affect some output bits of (a,b,c), especially of a. The
80 most thoroughly mixed value is c, but it doesn't really even achieve
83 This allows some parallelism. Read-after-writes are good at doubling
84 the number of bits affected, so the goal of mixing pulls in the opposite
85 direction as the goal of parallelism. I did what I could. Rotates
86 seem to cost as much as shifts on every machine I could lay my hands
87 on, and rotates are much kinder to the top and bottom bits, so I used
89 -------------------------------------------------------------------------------
93 a -= c; a ^= rot(c, 4); c += b; \
94 b -= a; b ^= rot(a, 6); a += c; \
95 c -= b; c ^= rot(b, 8); b += a; \
96 a -= c; a ^= rot(c,16); c += b; \
97 b -= a; b ^= rot(a,19); a += c; \
98 c -= b; c ^= rot(b, 4); b += a; \
102 -------------------------------------------------------------------------------
103 final -- final mixing of 3 32-bit values (a,b,c) into c
105 Pairs of (a,b,c) values differing in only a few bits will usually
106 produce values of c that look totally different. This was tested for
107 * pairs that differed by one bit, by two bits, in any combination
108 of top bits of (a,b,c), or in any combination of bottom bits of
110 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
111 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
112 is commonly produced by subtraction) look like a single 1-bit
114 * the base values were pseudorandom, all zero but one bit set, or
115 all zero plus a counter that starts at zero.
117 These constants passed:
120 and these came close:
124 -------------------------------------------------------------------------------
126 #define final(a,b,c) \
128 c ^= b; c -= rot(b,14); \
129 a ^= c; a -= rot(c,11); \
130 b ^= a; b -= rot(a,25); \
131 c ^= b; c -= rot(b,16); \
132 a ^= c; a -= rot(c,4); \
133 b ^= a; b -= rot(a,14); \
134 c ^= b; c -= rot(b,24); \
138 --------------------------------------------------------------------
139 This works on all machines. To be useful, it requires
140 -- that the key be an array of uint32_t's, and
141 -- that the length be the number of uint32_t's in the key
143 The function hashword() is identical to hashlittle() on little-endian
144 machines, and identical to hashbig() on big-endian machines,
145 except that the length has to be measured in uint32_ts rather than in
146 bytes. hashlittle() is more complicated than hashword() only because
147 hashlittle() has to dance around fitting the key bytes into registers.
148 --------------------------------------------------------------------
150 uint32_t jenkins_hash32(
151 const uint32_t *k, /* the key, an array of uint32_t values */
152 size_t length, /* the length of the key, in uint32_ts */
153 uint32_t initval) /* the previous hash, or an arbitrary value */
157 /* Set up the internal state */
158 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
160 /*------------------------------------------------- handle most of the key */
171 /*------------------------------------------- handle the last 3 uint32_t's */
172 switch(length) /* all the case statements fall through */
178 case 0: /* case 0: nothing left to add */
181 /*------------------------------------------------------ report the result */
185 #if BYTE_ORDER == LITTLE_ENDIAN
187 -------------------------------------------------------------------------------
188 hashlittle() -- hash a variable-length key into a 32-bit value
189 k : the key (the unaligned variable-length array of bytes)
190 length : the length of the key, counting by bytes
191 initval : can be any 4-byte value
192 Returns a 32-bit value. Every bit of the key affects every bit of
193 the return value. Two keys differing by one or two bits will have
194 totally different hash values.
196 The best hash table sizes are powers of 2. There is no need to do
197 mod a prime (mod is sooo slow!). If you need less than 32 bits,
198 use a bitmask. For example, if you need only 10 bits, do
199 h = (h & hashmask(10));
200 In which case, the hash table should have hashsize(10) elements.
202 If you are hashing n strings (uint8_t **)k, do it like this:
203 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
205 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
206 code any way you wish, private, educational, or commercial. It's free.
208 Use for hash table lookup, or anything where one collision in 2^^32 is
209 acceptable. Do NOT use for cryptographic purposes.
210 -------------------------------------------------------------------------------
213 uint32_t jenkins_hash( const void *key, size_t length, uint32_t initval)
215 uint32_t a,b,c; /* internal state */
216 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
218 /* Set up the internal state */
219 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
222 if ((u.i & 0x3) == 0) {
223 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
225 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
236 /*----------------------------- handle the last (probably partial) block */
238 * "k[2]&0xffffff" actually reads beyond the end of the string, but
239 * then masks off the part it's not allowed to read. Because the
240 * string is aligned, the masked-off tail is in the same word as the
241 * rest of the string. Every machine with memory protection I've seen
242 * does it on word boundaries, so is OK with this. But VALGRIND will
243 * still catch it and complain. The masking trick does make the hash
244 * noticably faster for short strings (like English words).
249 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
250 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
251 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
252 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
253 case 8 : b+=k[1]; a+=k[0]; break;
254 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
255 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
256 case 5 : b+=k[1]&0xff; a+=k[0]; break;
257 case 4 : a+=k[0]; break;
258 case 3 : a+=k[0]&0xffffff; break;
259 case 2 : a+=k[0]&0xffff; break;
260 case 1 : a+=k[0]&0xff; break;
261 case 0 : return c; /* zero length strings require no mixing */
264 } else if ((u.i & 0x1) == 0) {
265 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
268 /*--------------- all but last block: aligned reads and different mixing */
271 a += k[0] + (((uint32_t)k[1])<<16);
272 b += k[2] + (((uint32_t)k[3])<<16);
273 c += k[4] + (((uint32_t)k[5])<<16);
279 /*----------------------------- handle the last (probably partial) block */
280 k8 = (const uint8_t *)k;
283 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
284 b+=k[2]+(((uint32_t)k[3])<<16);
285 a+=k[0]+(((uint32_t)k[1])<<16);
287 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
289 b+=k[2]+(((uint32_t)k[3])<<16);
290 a+=k[0]+(((uint32_t)k[1])<<16);
292 case 9 : c+=k8[8]; /* fall through */
293 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
294 a+=k[0]+(((uint32_t)k[1])<<16);
296 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
298 a+=k[0]+(((uint32_t)k[1])<<16);
300 case 5 : b+=k8[4]; /* fall through */
301 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
303 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
308 case 0 : return c; /* zero length requires no mixing */
311 } else { /* need to read the key one byte at a time */
312 const uint8_t *k = (const uint8_t *)key;
314 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
318 a += ((uint32_t)k[1])<<8;
319 a += ((uint32_t)k[2])<<16;
320 a += ((uint32_t)k[3])<<24;
322 b += ((uint32_t)k[5])<<8;
323 b += ((uint32_t)k[6])<<16;
324 b += ((uint32_t)k[7])<<24;
326 c += ((uint32_t)k[9])<<8;
327 c += ((uint32_t)k[10])<<16;
328 c += ((uint32_t)k[11])<<24;
334 /*-------------------------------- last block: affect all 32 bits of (c) */
335 switch(length) /* all the case statements fall through */
337 case 12: c+=((uint32_t)k[11])<<24;
338 case 11: c+=((uint32_t)k[10])<<16;
339 case 10: c+=((uint32_t)k[9])<<8;
341 case 8 : b+=((uint32_t)k[7])<<24;
342 case 7 : b+=((uint32_t)k[6])<<16;
343 case 6 : b+=((uint32_t)k[5])<<8;
345 case 4 : a+=((uint32_t)k[3])<<24;
346 case 3 : a+=((uint32_t)k[2])<<16;
347 case 2 : a+=((uint32_t)k[1])<<8;
358 #else /* !(BYTE_ORDER == LITTLE_ENDIAN) */
362 * This is the same as hashword() on big-endian machines. It is different
363 * from hashlittle() on all machines. hashbig() takes advantage of
364 * big-endian byte ordering.
366 uint32_t jenkins_hash( const void *key, size_t length, uint32_t initval)
369 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
371 /* Set up the internal state */
372 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
375 if ((u.i & 0x3) == 0) {
376 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
378 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
389 /*----------------------------- handle the last (probably partial) block */
391 * "k[2]<<8" actually reads beyond the end of the string, but
392 * then shifts out the part it's not allowed to read. Because the
393 * string is aligned, the illegal read is in the same word as the
394 * rest of the string. Every machine with memory protection I've seen
395 * does it on word boundaries, so is OK with this. But VALGRIND will
396 * still catch it and complain. The masking trick does make the hash
397 * noticably faster for short strings (like English words).
402 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
403 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
404 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
405 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
406 case 8 : b+=k[1]; a+=k[0]; break;
407 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
408 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
409 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
410 case 4 : a+=k[0]; break;
411 case 3 : a+=k[0]&0xffffff00; break;
412 case 2 : a+=k[0]&0xffff0000; break;
413 case 1 : a+=k[0]&0xff000000; break;
414 case 0 : return c; /* zero length strings require no mixing */
417 } else { /* need to read the key one byte at a time */
418 const uint8_t *k = (const uint8_t *)key;
420 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
423 a += ((uint32_t)k[0])<<24;
424 a += ((uint32_t)k[1])<<16;
425 a += ((uint32_t)k[2])<<8;
426 a += ((uint32_t)k[3]);
427 b += ((uint32_t)k[4])<<24;
428 b += ((uint32_t)k[5])<<16;
429 b += ((uint32_t)k[6])<<8;
430 b += ((uint32_t)k[7]);
431 c += ((uint32_t)k[8])<<24;
432 c += ((uint32_t)k[9])<<16;
433 c += ((uint32_t)k[10])<<8;
434 c += ((uint32_t)k[11]);
440 /*-------------------------------- last block: affect all 32 bits of (c) */
441 switch(length) /* all the case statements fall through */
444 case 11: c+=((uint32_t)k[10])<<8;
445 case 10: c+=((uint32_t)k[9])<<16;
446 case 9 : c+=((uint32_t)k[8])<<24;
448 case 7 : b+=((uint32_t)k[6])<<8;
449 case 6 : b+=((uint32_t)k[5])<<16;
450 case 5 : b+=((uint32_t)k[4])<<24;
452 case 3 : a+=((uint32_t)k[2])<<8;
453 case 2 : a+=((uint32_t)k[1])<<16;
454 case 1 : a+=((uint32_t)k[0])<<24;