2 -------------------------------------------------------------------------------
3 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
5 These are functions for producing 32-bit hashes for hash table lookup.
6 hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
7 are externally useful functions. Routines to test the hash are included
8 if SELF_TEST is defined. You can use this free for any purpose. It's in
9 the public domain. It has no warranty.
11 You probably want to use hashlittle(). hashlittle() and hashbig()
12 hash byte arrays. hashlittle() is is faster than hashbig() on
13 little-endian machines. Intel and AMD are little-endian machines.
14 On second thought, you probably want hashlittle2(), which is identical to
15 hashlittle() except it returns two 32-bit hashes for the price of one.
16 You could implement hashbig2() if you wanted but I haven't bothered here.
18 If you want to find a hash of, say, exactly 7 integers, do
19 a = i1; b = i2; c = i3;
21 a += i4; b += i5; c += i6;
25 then use c as the hash value. If you have a variable length array of
26 4-byte integers to hash, use hash_word(). If you have a byte array (like
27 a character string), use hashlittle(). If you have several byte arrays, or
28 a mix of things, see the comments above hashlittle().
30 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
31 then mix those integers. This is fast (you can do a lot more thorough
32 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
33 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
34 -------------------------------------------------------------------------------
39 #include <stdio.h> /* defines printf for tests */
40 #include <time.h> /* defines time_t for timings in the test */
41 #include <stdint.h> /* defines uint32_t etc */
42 #include <sys/param.h> /* attempt to define endianness */
45 #include "hash/hash.h"
47 # include <endian.h> /* attempt to define endianness */
51 * My best guess at if you are big-endian or little-endian. This may
54 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
55 __BYTE_ORDER == __LITTLE_ENDIAN) || \
56 (defined(i386) || defined(__i386__) || defined(__i486__) || \
57 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
58 # define HASH_LITTLE_ENDIAN 1
59 # define HASH_BIG_ENDIAN 0
60 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
61 __BYTE_ORDER == __BIG_ENDIAN) || \
62 (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
63 # define HASH_LITTLE_ENDIAN 0
64 # define HASH_BIG_ENDIAN 1
66 # define HASH_LITTLE_ENDIAN 0
67 # define HASH_BIG_ENDIAN 0
70 #define hashsize(n) ((uint32_t)1<<(n))
71 #define hashmask(n) (hashsize(n)-1)
72 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
75 -------------------------------------------------------------------------------
76 mix -- mix 3 32-bit values reversibly.
78 This is reversible, so any information in (a,b,c) before mix() is
79 still in (a,b,c) after mix().
81 If four pairs of (a,b,c) inputs are run through mix(), or through
82 mix() in reverse, there are at least 32 bits of the output that
83 are sometimes the same for one pair and different for another pair.
85 * pairs that differed by one bit, by two bits, in any combination
86 of top bits of (a,b,c), or in any combination of bottom bits of
88 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
89 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
90 is commonly produced by subtraction) look like a single 1-bit
92 * the base values were pseudorandom, all zero but one bit set, or
93 all zero plus a counter that starts at zero.
95 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
100 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
101 for "differ" defined as + with a one-bit base and a two-bit delta. I
102 used http://burtleburtle.net/bob/hash/avalanche.html to choose
103 the operations, constants, and arrangements of the variables.
105 This does not achieve avalanche. There are input bits of (a,b,c)
106 that fail to affect some output bits of (a,b,c), especially of a. The
107 most thoroughly mixed value is c, but it doesn't really even achieve
110 This allows some parallelism. Read-after-writes are good at doubling
111 the number of bits affected, so the goal of mixing pulls in the opposite
112 direction as the goal of parallelism. I did what I could. Rotates
113 seem to cost as much as shifts on every machine I could lay my hands
114 on, and rotates are much kinder to the top and bottom bits, so I used
116 -------------------------------------------------------------------------------
120 a -= c; a ^= rot(c, 4); c += b; \
121 b -= a; b ^= rot(a, 6); a += c; \
122 c -= b; c ^= rot(b, 8); b += a; \
123 a -= c; a ^= rot(c,16); c += b; \
124 b -= a; b ^= rot(a,19); a += c; \
125 c -= b; c ^= rot(b, 4); b += a; \
129 -------------------------------------------------------------------------------
130 final -- final mixing of 3 32-bit values (a,b,c) into c
132 Pairs of (a,b,c) values differing in only a few bits will usually
133 produce values of c that look totally different. This was tested for
134 * pairs that differed by one bit, by two bits, in any combination
135 of top bits of (a,b,c), or in any combination of bottom bits of
137 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
138 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
139 is commonly produced by subtraction) look like a single 1-bit
141 * the base values were pseudorandom, all zero but one bit set, or
142 all zero plus a counter that starts at zero.
144 These constants passed:
147 and these came close:
151 -------------------------------------------------------------------------------
153 #define final(a,b,c) \
155 c ^= b; c -= rot(b,14); \
156 a ^= c; a -= rot(c,11); \
157 b ^= a; b -= rot(a,25); \
158 c ^= b; c -= rot(b,16); \
159 a ^= c; a -= rot(c,4); \
160 b ^= a; b -= rot(a,14); \
161 c ^= b; c -= rot(b,24); \
165 --------------------------------------------------------------------
166 This works on all machines. To be useful, it requires
167 -- that the key be an array of uint32_t's, and
168 -- that the length be the number of uint32_t's in the key
170 The function hash_word() is identical to hashlittle() on little-endian
171 machines, and identical to hashbig() on big-endian machines,
172 except that the length has to be measured in uint32_ts rather than in
173 bytes. hashlittle() is more complicated than hash_word() only because
174 hashlittle() has to dance around fitting the key bytes into registers.
175 --------------------------------------------------------------------
178 const uint32_t *k, /* the key, an array of uint32_t values */
179 size_t length, /* the length of the key, in uint32_ts */
180 uint32_t initval) /* the previous hash, or an arbitrary value */
184 /* Set up the internal state */
185 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
187 /*------------------------------------------------- handle most of the key */
198 /*------------------------------------------- handle the last 3 uint32_t's */
199 switch(length) /* all the case statements fall through */
205 case 0: /* case 0: nothing left to add */
208 /*------------------------------------------------------ report the result */
215 --------------------------------------------------------------------
216 hash_word2() -- same as hash_word(), but take two seeds and return two
217 32-bit values. pc and pb must both be nonnull, and *pc and *pb must
218 both be initialized with seeds. If you pass in (*pb)==0, the output
219 (*pc) will be the same as the return value from hash_word().
220 --------------------------------------------------------------------
223 const uint32_t *k, /* the key, an array of uint32_t values */
224 size_t length, /* the length of the key, in uint32_ts */
225 uint32_t *pc, /* IN: seed OUT: primary hash value */
226 uint32_t *pb) /* IN: more seed OUT: secondary hash value */
230 /* Set up the internal state */
231 a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
234 /*------------------------------------------------- handle most of the key */
245 /*------------------------------------------- handle the last 3 uint32_t's */
246 switch(length) /* all the case statements fall through */
252 case 0: /* case 0: nothing left to add */
255 /*------------------------------------------------------ report the result */
261 -------------------------------------------------------------------------------
262 hashlittle() -- hash a variable-length key into a 32-bit value
263 k : the key (the unaligned variable-length array of bytes)
264 length : the length of the key, counting by bytes
265 initval : can be any 4-byte value
266 Returns a 32-bit value. Every bit of the key affects every bit of
267 the return value. Two keys differing by one or two bits will have
268 totally different hash values.
270 The best hash table sizes are powers of 2. There is no need to do
271 mod a prime (mod is sooo slow!). If you need less than 32 bits,
272 use a bitmask. For example, if you need only 10 bits, do
273 h = (h & hashmask(10));
274 In which case, the hash table should have hashsize(10) elements.
276 If you are hashing n strings (uint8_t **)k, do it like this:
277 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
279 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
280 code any way you wish, private, educational, or commercial. It's free.
282 Use for hash table lookup, or anything where one collision in 2^^32 is
283 acceptable. Do NOT use for cryptographic purposes.
284 -------------------------------------------------------------------------------
287 static uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
289 uint32_t a,b,c; /* internal state */
290 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
292 /* Set up the internal state */
293 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
296 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
297 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
302 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
313 /*----------------------------- handle the last (probably partial) block */
315 * "k[2]&0xffffff" actually reads beyond the end of the string, but
316 * then masks off the part it's not allowed to read. Because the
317 * string is aligned, the masked-off tail is in the same word as the
318 * rest of the string. Every machine with memory protection I've seen
319 * does it on word boundaries, so is OK with this. But VALGRIND will
320 * still catch it and complain. The masking trick does make the hash
321 * noticably faster for short strings (like English words).
327 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
328 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
329 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
330 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
331 case 8 : b+=k[1]; a+=k[0]; break;
332 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
333 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
334 case 5 : b+=k[1]&0xff; a+=k[0]; break;
335 case 4 : a+=k[0]; break;
336 case 3 : a+=k[0]&0xffffff; break;
337 case 2 : a+=k[0]&0xffff; break;
338 case 1 : a+=k[0]&0xff; break;
339 case 0 : return c; /* zero length strings require no mixing */
342 #else /* make valgrind happy */
344 k8 = (const uint8_t *)k;
347 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
348 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
349 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
350 case 9 : c+=k8[8]; /* fall through */
351 case 8 : b+=k[1]; a+=k[0]; break;
352 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
353 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
354 case 5 : b+=k8[4]; /* fall through */
355 case 4 : a+=k[0]; break;
356 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
357 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
358 case 1 : a+=k8[0]; break;
362 #endif /* !valgrind */
364 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
365 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
368 /*--------------- all but last block: aligned reads and different mixing */
371 a += k[0] + (((uint32_t)k[1])<<16);
372 b += k[2] + (((uint32_t)k[3])<<16);
373 c += k[4] + (((uint32_t)k[5])<<16);
379 /*----------------------------- handle the last (probably partial) block */
380 k8 = (const uint8_t *)k;
383 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
384 b+=k[2]+(((uint32_t)k[3])<<16);
385 a+=k[0]+(((uint32_t)k[1])<<16);
387 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
389 b+=k[2]+(((uint32_t)k[3])<<16);
390 a+=k[0]+(((uint32_t)k[1])<<16);
392 case 9 : c+=k8[8]; /* fall through */
393 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
394 a+=k[0]+(((uint32_t)k[1])<<16);
396 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
398 a+=k[0]+(((uint32_t)k[1])<<16);
400 case 5 : b+=k8[4]; /* fall through */
401 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
403 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
408 case 0 : return c; /* zero length requires no mixing */
411 } else { /* need to read the key one byte at a time */
412 const uint8_t *k = (const uint8_t *)key;
414 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
418 a += ((uint32_t)k[1])<<8;
419 a += ((uint32_t)k[2])<<16;
420 a += ((uint32_t)k[3])<<24;
422 b += ((uint32_t)k[5])<<8;
423 b += ((uint32_t)k[6])<<16;
424 b += ((uint32_t)k[7])<<24;
426 c += ((uint32_t)k[9])<<8;
427 c += ((uint32_t)k[10])<<16;
428 c += ((uint32_t)k[11])<<24;
434 /*-------------------------------- last block: affect all 32 bits of (c) */
435 switch(length) /* all the case statements fall through */
437 case 12: c+=((uint32_t)k[11])<<24;
438 case 11: c+=((uint32_t)k[10])<<16;
439 case 10: c+=((uint32_t)k[9])<<8;
441 case 8 : b+=((uint32_t)k[7])<<24;
442 case 7 : b+=((uint32_t)k[6])<<16;
443 case 6 : b+=((uint32_t)k[5])<<8;
445 case 4 : a+=((uint32_t)k[3])<<24;
446 case 3 : a+=((uint32_t)k[2])<<16;
447 case 2 : a+=((uint32_t)k[1])<<8;
460 * hashlittle2: return 2 32-bit hash values
462 * This is identical to hashlittle(), except it returns two 32-bit hash
463 * values instead of just one. This is good enough for hash table
464 * lookup with 2^^64 buckets, or if you want a second hash if you're not
465 * happy with the first, or if you want a probably-unique 64-bit ID for
466 * the key. *pc is better mixed than *pb, so use *pc first. If you want
467 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
470 const void *key, /* the key to hash */
471 size_t length, /* length of the key */
472 uint32_t *pc, /* IN: primary initval, OUT: primary hash */
473 uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */
475 uint32_t a,b,c; /* internal state */
476 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
478 /* Set up the internal state */
479 a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
483 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
484 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
487 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
498 /*----------------------------- handle the last (probably partial) block */
500 * "k[2]&0xffffff" actually reads beyond the end of the string, but
501 * then masks off the part it's not allowed to read. Because the
502 * string is aligned, the masked-off tail is in the same word as the
503 * rest of the string. Every machine with memory protection I've seen
504 * does it on word boundaries, so is OK with this. But VALGRIND will
505 * still catch it and complain. The masking trick does make the hash
506 * noticably faster for short strings (like English words).
512 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
513 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
514 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
515 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
516 case 8 : b+=k[1]; a+=k[0]; break;
517 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
518 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
519 case 5 : b+=k[1]&0xff; a+=k[0]; break;
520 case 4 : a+=k[0]; break;
521 case 3 : a+=k[0]&0xffffff; break;
522 case 2 : a+=k[0]&0xffff; break;
523 case 1 : a+=k[0]&0xff; break;
524 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
527 #else /* make valgrind happy */
529 k8 = (const uint8_t *)k;
532 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
533 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
534 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
535 case 9 : c+=k8[8]; /* fall through */
536 case 8 : b+=k[1]; a+=k[0]; break;
537 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
538 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
539 case 5 : b+=k8[4]; /* fall through */
540 case 4 : a+=k[0]; break;
541 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
542 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
543 case 1 : a+=k8[0]; break;
544 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
547 #endif /* !valgrind */
549 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
550 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
553 /*--------------- all but last block: aligned reads and different mixing */
556 a += k[0] + (((uint32_t)k[1])<<16);
557 b += k[2] + (((uint32_t)k[3])<<16);
558 c += k[4] + (((uint32_t)k[5])<<16);
564 /*----------------------------- handle the last (probably partial) block */
565 k8 = (const uint8_t *)k;
568 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
569 b+=k[2]+(((uint32_t)k[3])<<16);
570 a+=k[0]+(((uint32_t)k[1])<<16);
572 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
574 b+=k[2]+(((uint32_t)k[3])<<16);
575 a+=k[0]+(((uint32_t)k[1])<<16);
577 case 9 : c+=k8[8]; /* fall through */
578 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
579 a+=k[0]+(((uint32_t)k[1])<<16);
581 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
583 a+=k[0]+(((uint32_t)k[1])<<16);
585 case 5 : b+=k8[4]; /* fall through */
586 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
588 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
593 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
596 } else { /* need to read the key one byte at a time */
597 const uint8_t *k = (const uint8_t *)key;
599 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
603 a += ((uint32_t)k[1])<<8;
604 a += ((uint32_t)k[2])<<16;
605 a += ((uint32_t)k[3])<<24;
607 b += ((uint32_t)k[5])<<8;
608 b += ((uint32_t)k[6])<<16;
609 b += ((uint32_t)k[7])<<24;
611 c += ((uint32_t)k[9])<<8;
612 c += ((uint32_t)k[10])<<16;
613 c += ((uint32_t)k[11])<<24;
619 /*-------------------------------- last block: affect all 32 bits of (c) */
620 switch(length) /* all the case statements fall through */
622 case 12: c+=((uint32_t)k[11])<<24;
623 case 11: c+=((uint32_t)k[10])<<16;
624 case 10: c+=((uint32_t)k[9])<<8;
626 case 8 : b+=((uint32_t)k[7])<<24;
627 case 7 : b+=((uint32_t)k[6])<<16;
628 case 6 : b+=((uint32_t)k[5])<<8;
630 case 4 : a+=((uint32_t)k[3])<<24;
631 case 3 : a+=((uint32_t)k[2])<<16;
632 case 2 : a+=((uint32_t)k[1])<<8;
635 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
647 * This is the same as hash_word() on big-endian machines. It is different
648 * from hashlittle() on all machines. hashbig() takes advantage of
649 * big-endian byte ordering.
651 static uint32_t hashbig( const void *key, size_t length, uint32_t initval)
654 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
656 /* Set up the internal state */
657 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
660 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
661 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
666 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
677 /*----------------------------- handle the last (probably partial) block */
679 * "k[2]<<8" actually reads beyond the end of the string, but
680 * then shifts out the part it's not allowed to read. Because the
681 * string is aligned, the illegal read is in the same word as the
682 * rest of the string. Every machine with memory protection I've seen
683 * does it on word boundaries, so is OK with this. But VALGRIND will
684 * still catch it and complain. The masking trick does make the hash
685 * noticably faster for short strings (like English words).
691 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
692 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
693 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
694 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
695 case 8 : b+=k[1]; a+=k[0]; break;
696 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
697 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
698 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
699 case 4 : a+=k[0]; break;
700 case 3 : a+=k[0]&0xffffff00; break;
701 case 2 : a+=k[0]&0xffff0000; break;
702 case 1 : a+=k[0]&0xff000000; break;
703 case 0 : return c; /* zero length strings require no mixing */
706 #else /* make valgrind happy */
708 k8 = (const uint8_t *)k;
709 switch(length) /* all the case statements fall through */
711 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
712 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
713 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
714 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
715 case 8 : b+=k[1]; a+=k[0]; break;
716 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
717 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
718 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
719 case 4 : a+=k[0]; break;
720 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
721 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
722 case 1 : a+=((uint32_t)k8[0])<<24; break;
726 #endif /* !VALGRIND */
728 } else { /* need to read the key one byte at a time */
729 const uint8_t *k = (const uint8_t *)key;
731 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
734 a += ((uint32_t)k[0])<<24;
735 a += ((uint32_t)k[1])<<16;
736 a += ((uint32_t)k[2])<<8;
737 a += ((uint32_t)k[3]);
738 b += ((uint32_t)k[4])<<24;
739 b += ((uint32_t)k[5])<<16;
740 b += ((uint32_t)k[6])<<8;
741 b += ((uint32_t)k[7]);
742 c += ((uint32_t)k[8])<<24;
743 c += ((uint32_t)k[9])<<16;
744 c += ((uint32_t)k[10])<<8;
745 c += ((uint32_t)k[11]);
751 /*-------------------------------- last block: affect all 32 bits of (c) */
752 switch(length) /* all the case statements fall through */
755 case 11: c+=((uint32_t)k[10])<<8;
756 case 10: c+=((uint32_t)k[9])<<16;
757 case 9 : c+=((uint32_t)k[8])<<24;
759 case 7 : b+=((uint32_t)k[6])<<8;
760 case 6 : b+=((uint32_t)k[5])<<16;
761 case 5 : b+=((uint32_t)k[4])<<24;
763 case 3 : a+=((uint32_t)k[2])<<8;
764 case 2 : a+=((uint32_t)k[1])<<16;
765 case 1 : a+=((uint32_t)k[0])<<24;
775 uint32_t hash_any_stable(const void *key, size_t length, uint32_t base)
777 /* We use hashlittle as our stable hash. */
778 return hashlittle(key, length, base);
781 uint32_t hash_any(const void *key, size_t length, uint32_t base)
784 return hashbig(key, length, base);
786 /* We call hash_any_stable not hashlittle. This way we know
787 * that hashlittle will be inlined in hash_any_stable. */
788 return hash_any_stable(key, length, base);
793 /* used for timings */
802 for (i=0; i<256; ++i) buf[i] = 'x';
805 h = hashlittle(&buf[0],1,h);
808 if (z-a > 0) printf("time %d %.8x\n", z-a, h);
811 /* check that every input bit changes every output bit half the time */
818 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
819 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
820 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
821 uint32_t x[HASHSTATE],y[HASHSTATE];
824 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
825 for (hlen=0; hlen < MAXLEN; ++hlen)
828 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
830 for (j=0; j<8; ++j) /*------------------------ for each input bit, */
832 for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
834 for (l=0; l<HASHSTATE; ++l)
835 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
837 /*---- check that every output bit is affected by that input bit */
838 for (k=0; k<MAXPAIR; k+=2)
841 /* keys have one bit different */
842 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
843 /* have a and b be two keys differing in only one bit */
846 c[0] = hashlittle(a, hlen, m);
848 b[i] ^= ((k+1)>>(8-j));
849 d[0] = hashlittle(b, hlen, m);
850 /* check every bit is 1, 0, set, and not set at least once */
851 for (l=0; l<HASHSTATE; ++l)
854 f[l] &= ~(c[l]^d[l]);
859 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
866 printf("Some bit didn't change: ");
867 printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
868 e[0],f[0],g[0],h[0],x[0],y[0]);
869 printf("i %d j %d m %d len %d\n", i, j, m, hlen);
871 if (z==MAXPAIR) goto done;
878 printf("Mix success %2d bytes %2d initvals ",i,m);
879 printf("required %d trials\n", z/2);
885 /* Check for reading beyond the end of the buffer and alignment problems */
888 uint8_t buf[MAXLEN+20], *b;
890 uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
892 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
894 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
896 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
900 printf("Endianness. These lines should all be the same (for values filled in):\n");
901 printf("%.8x %.8x %.8x\n",
902 hash_word((const uint32_t *)q, (sizeof(q)-1)/4, 13),
903 hash_word((const uint32_t *)q, (sizeof(q)-5)/4, 13),
904 hash_word((const uint32_t *)q, (sizeof(q)-9)/4, 13));
906 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
907 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
908 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
909 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
910 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
911 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
912 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
914 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
915 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
916 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
917 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
918 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
919 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
920 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
922 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
923 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
924 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
925 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
926 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
927 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
928 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
930 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
931 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
932 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
933 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
934 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
935 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
936 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
939 /* check that hashlittle2 and hashlittle produce the same results */
941 hashlittle2(q, sizeof(q), &i, &j);
942 if (hashlittle(q, sizeof(q), 47) != i)
943 printf("hashlittle2 and hashlittle mismatch\n");
945 /* check that hash_word2 and hash_word produce the same results */
948 hash_word2(&len, 1, &i, &j);
949 if (hash_word(&len, 1, 47) != i)
950 printf("hash_word2 and hash_word mismatch %x %x\n",
951 i, hash_word(&len, 1, 47));
953 /* check hashlittle doesn't read before or after the ends of the string */
954 for (h=0, b=buf+1; h<8; ++h, ++b)
956 for (i=0; i<MAXLEN; ++i)
959 for (j=0; j<i; ++j) *(b+j)=0;
961 /* these should all be equal */
962 ref = hashlittle(b, len, (uint32_t)1);
965 x = hashlittle(b, len, (uint32_t)1);
966 y = hashlittle(b, len, (uint32_t)1);
967 if ((ref != x) || (ref != y))
969 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
976 /* check for problems with nulls */
980 uint32_t h,i,state[HASHSTATE];
984 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
985 printf("These should all be different\n");
986 for (i=0, h=0; i<8; ++i)
988 h = hashlittle(buf, 0, h);
989 printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
996 driver1(); /* test that the key is hashed: used for timings */
997 driver2(); /* test that whole key is hashed thoroughly */
998 driver3(); /* test that nothing but the key is hashed */
999 driver4(); /* test hashing multiple buffers (all buffers are null) */
1003 #endif /* SELF_TEST */