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 hashword(), 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 hashword(). 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 */
44 # include <endian.h> /* attempt to define endianness */
48 * My best guess at if you are big-endian or little-endian. This may
51 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
52 __BYTE_ORDER == __LITTLE_ENDIAN) || \
53 (defined(i386) || defined(__i386__) || defined(__i486__) || \
54 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
55 # define HASH_LITTLE_ENDIAN 1
56 # define HASH_BIG_ENDIAN 0
57 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
58 __BYTE_ORDER == __BIG_ENDIAN) || \
59 (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
60 # define HASH_LITTLE_ENDIAN 0
61 # define HASH_BIG_ENDIAN 1
63 # define HASH_LITTLE_ENDIAN 0
64 # define HASH_BIG_ENDIAN 0
67 #define hashsize(n) ((uint32_t)1<<(n))
68 #define hashmask(n) (hashsize(n)-1)
69 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
72 -------------------------------------------------------------------------------
73 mix -- mix 3 32-bit values reversibly.
75 This is reversible, so any information in (a,b,c) before mix() is
76 still in (a,b,c) after mix().
78 If four pairs of (a,b,c) inputs are run through mix(), or through
79 mix() in reverse, there are at least 32 bits of the output that
80 are sometimes the same for one pair and different for another pair.
82 * pairs that differed by one bit, by two bits, in any combination
83 of top bits of (a,b,c), or in any combination of bottom bits of
85 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
86 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
87 is commonly produced by subtraction) look like a single 1-bit
89 * the base values were pseudorandom, all zero but one bit set, or
90 all zero plus a counter that starts at zero.
92 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
97 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
98 for "differ" defined as + with a one-bit base and a two-bit delta. I
99 used http://burtleburtle.net/bob/hash/avalanche.html to choose
100 the operations, constants, and arrangements of the variables.
102 This does not achieve avalanche. There are input bits of (a,b,c)
103 that fail to affect some output bits of (a,b,c), especially of a. The
104 most thoroughly mixed value is c, but it doesn't really even achieve
107 This allows some parallelism. Read-after-writes are good at doubling
108 the number of bits affected, so the goal of mixing pulls in the opposite
109 direction as the goal of parallelism. I did what I could. Rotates
110 seem to cost as much as shifts on every machine I could lay my hands
111 on, and rotates are much kinder to the top and bottom bits, so I used
113 -------------------------------------------------------------------------------
117 a -= c; a ^= rot(c, 4); c += b; \
118 b -= a; b ^= rot(a, 6); a += c; \
119 c -= b; c ^= rot(b, 8); b += a; \
120 a -= c; a ^= rot(c,16); c += b; \
121 b -= a; b ^= rot(a,19); a += c; \
122 c -= b; c ^= rot(b, 4); b += a; \
126 -------------------------------------------------------------------------------
127 final -- final mixing of 3 32-bit values (a,b,c) into c
129 Pairs of (a,b,c) values differing in only a few bits will usually
130 produce values of c that look totally different. This was tested for
131 * pairs that differed by one bit, by two bits, in any combination
132 of top bits of (a,b,c), or in any combination of bottom bits of
134 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
135 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
136 is commonly produced by subtraction) look like a single 1-bit
138 * the base values were pseudorandom, all zero but one bit set, or
139 all zero plus a counter that starts at zero.
141 These constants passed:
144 and these came close:
148 -------------------------------------------------------------------------------
150 #define final(a,b,c) \
152 c ^= b; c -= rot(b,14); \
153 a ^= c; a -= rot(c,11); \
154 b ^= a; b -= rot(a,25); \
155 c ^= b; c -= rot(b,16); \
156 a ^= c; a -= rot(c,4); \
157 b ^= a; b -= rot(a,14); \
158 c ^= b; c -= rot(b,24); \
162 --------------------------------------------------------------------
163 This works on all machines. To be useful, it requires
164 -- that the key be an array of uint32_t's, and
165 -- that the length be the number of uint32_t's in the key
167 The function hashword() is identical to hashlittle() on little-endian
168 machines, and identical to hashbig() on big-endian machines,
169 except that the length has to be measured in uint32_ts rather than in
170 bytes. hashlittle() is more complicated than hashword() only because
171 hashlittle() has to dance around fitting the key bytes into registers.
172 --------------------------------------------------------------------
175 const uint32_t *k, /* the key, an array of uint32_t values */
176 size_t length, /* the length of the key, in uint32_ts */
177 uint32_t initval) /* the previous hash, or an arbitrary value */
181 /* Set up the internal state */
182 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
184 /*------------------------------------------------- handle most of the key */
195 /*------------------------------------------- handle the last 3 uint32_t's */
196 switch(length) /* all the case statements fall through */
202 case 0: /* case 0: nothing left to add */
205 /*------------------------------------------------------ report the result */
211 --------------------------------------------------------------------
212 hashword2() -- same as hashword(), but take two seeds and return two
213 32-bit values. pc and pb must both be nonnull, and *pc and *pb must
214 both be initialized with seeds. If you pass in (*pb)==0, the output
215 (*pc) will be the same as the return value from hashword().
216 --------------------------------------------------------------------
219 const uint32_t *k, /* the key, an array of uint32_t values */
220 size_t length, /* the length of the key, in uint32_ts */
221 uint32_t *pc, /* IN: seed OUT: primary hash value */
222 uint32_t *pb) /* IN: more seed OUT: secondary hash value */
226 /* Set up the internal state */
227 a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
230 /*------------------------------------------------- handle most of the key */
241 /*------------------------------------------- handle the last 3 uint32_t's */
242 switch(length) /* all the case statements fall through */
248 case 0: /* case 0: nothing left to add */
251 /*------------------------------------------------------ report the result */
257 -------------------------------------------------------------------------------
258 hashlittle() -- hash a variable-length key into a 32-bit value
259 k : the key (the unaligned variable-length array of bytes)
260 length : the length of the key, counting by bytes
261 initval : can be any 4-byte value
262 Returns a 32-bit value. Every bit of the key affects every bit of
263 the return value. Two keys differing by one or two bits will have
264 totally different hash values.
266 The best hash table sizes are powers of 2. There is no need to do
267 mod a prime (mod is sooo slow!). If you need less than 32 bits,
268 use a bitmask. For example, if you need only 10 bits, do
269 h = (h & hashmask(10));
270 In which case, the hash table should have hashsize(10) elements.
272 If you are hashing n strings (uint8_t **)k, do it like this:
273 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
275 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
276 code any way you wish, private, educational, or commercial. It's free.
278 Use for hash table lookup, or anything where one collision in 2^^32 is
279 acceptable. Do NOT use for cryptographic purposes.
280 -------------------------------------------------------------------------------
283 uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
285 uint32_t a,b,c; /* internal state */
286 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
288 /* Set up the internal state */
289 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
292 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
293 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
296 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
307 /*----------------------------- handle the last (probably partial) block */
309 * "k[2]&0xffffff" actually reads beyond the end of the string, but
310 * then masks off the part it's not allowed to read. Because the
311 * string is aligned, the masked-off tail is in the same word as the
312 * rest of the string. Every machine with memory protection I've seen
313 * does it on word boundaries, so is OK with this. But VALGRIND will
314 * still catch it and complain. The masking trick does make the hash
315 * noticably faster for short strings (like English words).
321 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
322 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
323 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
324 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
325 case 8 : b+=k[1]; a+=k[0]; break;
326 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
327 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
328 case 5 : b+=k[1]&0xff; a+=k[0]; break;
329 case 4 : a+=k[0]; break;
330 case 3 : a+=k[0]&0xffffff; break;
331 case 2 : a+=k[0]&0xffff; break;
332 case 1 : a+=k[0]&0xff; break;
333 case 0 : return c; /* zero length strings require no mixing */
336 #else /* make valgrind happy */
338 k8 = (const uint8_t *)k;
341 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
342 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
343 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
344 case 9 : c+=k8[8]; /* fall through */
345 case 8 : b+=k[1]; a+=k[0]; break;
346 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
347 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
348 case 5 : b+=k8[4]; /* fall through */
349 case 4 : a+=k[0]; break;
350 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
351 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
352 case 1 : a+=k8[0]; break;
356 #endif /* !valgrind */
358 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
359 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
362 /*--------------- all but last block: aligned reads and different mixing */
365 a += k[0] + (((uint32_t)k[1])<<16);
366 b += k[2] + (((uint32_t)k[3])<<16);
367 c += k[4] + (((uint32_t)k[5])<<16);
373 /*----------------------------- handle the last (probably partial) block */
374 k8 = (const uint8_t *)k;
377 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
378 b+=k[2]+(((uint32_t)k[3])<<16);
379 a+=k[0]+(((uint32_t)k[1])<<16);
381 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
383 b+=k[2]+(((uint32_t)k[3])<<16);
384 a+=k[0]+(((uint32_t)k[1])<<16);
386 case 9 : c+=k8[8]; /* fall through */
387 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
388 a+=k[0]+(((uint32_t)k[1])<<16);
390 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
392 a+=k[0]+(((uint32_t)k[1])<<16);
394 case 5 : b+=k8[4]; /* fall through */
395 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
397 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
402 case 0 : return c; /* zero length requires no mixing */
405 } else { /* need to read the key one byte at a time */
406 const uint8_t *k = (const uint8_t *)key;
408 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
412 a += ((uint32_t)k[1])<<8;
413 a += ((uint32_t)k[2])<<16;
414 a += ((uint32_t)k[3])<<24;
416 b += ((uint32_t)k[5])<<8;
417 b += ((uint32_t)k[6])<<16;
418 b += ((uint32_t)k[7])<<24;
420 c += ((uint32_t)k[9])<<8;
421 c += ((uint32_t)k[10])<<16;
422 c += ((uint32_t)k[11])<<24;
428 /*-------------------------------- last block: affect all 32 bits of (c) */
429 switch(length) /* all the case statements fall through */
431 case 12: c+=((uint32_t)k[11])<<24;
432 case 11: c+=((uint32_t)k[10])<<16;
433 case 10: c+=((uint32_t)k[9])<<8;
435 case 8 : b+=((uint32_t)k[7])<<24;
436 case 7 : b+=((uint32_t)k[6])<<16;
437 case 6 : b+=((uint32_t)k[5])<<8;
439 case 4 : a+=((uint32_t)k[3])<<24;
440 case 3 : a+=((uint32_t)k[2])<<16;
441 case 2 : a+=((uint32_t)k[1])<<8;
454 * hashlittle2: return 2 32-bit hash values
456 * This is identical to hashlittle(), except it returns two 32-bit hash
457 * values instead of just one. This is good enough for hash table
458 * lookup with 2^^64 buckets, or if you want a second hash if you're not
459 * happy with the first, or if you want a probably-unique 64-bit ID for
460 * the key. *pc is better mixed than *pb, so use *pc first. If you want
461 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
464 const void *key, /* the key to hash */
465 size_t length, /* length of the key */
466 uint32_t *pc, /* IN: primary initval, OUT: primary hash */
467 uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */
469 uint32_t a,b,c; /* internal state */
470 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
472 /* Set up the internal state */
473 a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
477 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
478 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
481 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
492 /*----------------------------- handle the last (probably partial) block */
494 * "k[2]&0xffffff" actually reads beyond the end of the string, but
495 * then masks off the part it's not allowed to read. Because the
496 * string is aligned, the masked-off tail is in the same word as the
497 * rest of the string. Every machine with memory protection I've seen
498 * does it on word boundaries, so is OK with this. But VALGRIND will
499 * still catch it and complain. The masking trick does make the hash
500 * noticably faster for short strings (like English words).
506 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
507 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
508 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
509 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
510 case 8 : b+=k[1]; a+=k[0]; break;
511 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
512 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
513 case 5 : b+=k[1]&0xff; a+=k[0]; break;
514 case 4 : a+=k[0]; break;
515 case 3 : a+=k[0]&0xffffff; break;
516 case 2 : a+=k[0]&0xffff; break;
517 case 1 : a+=k[0]&0xff; break;
518 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
521 #else /* make valgrind happy */
523 k8 = (const uint8_t *)k;
526 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
527 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
528 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
529 case 9 : c+=k8[8]; /* fall through */
530 case 8 : b+=k[1]; a+=k[0]; break;
531 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
532 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
533 case 5 : b+=k8[4]; /* fall through */
534 case 4 : a+=k[0]; break;
535 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
536 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
537 case 1 : a+=k8[0]; break;
538 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
541 #endif /* !valgrind */
543 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
544 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
547 /*--------------- all but last block: aligned reads and different mixing */
550 a += k[0] + (((uint32_t)k[1])<<16);
551 b += k[2] + (((uint32_t)k[3])<<16);
552 c += k[4] + (((uint32_t)k[5])<<16);
558 /*----------------------------- handle the last (probably partial) block */
559 k8 = (const uint8_t *)k;
562 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
563 b+=k[2]+(((uint32_t)k[3])<<16);
564 a+=k[0]+(((uint32_t)k[1])<<16);
566 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
568 b+=k[2]+(((uint32_t)k[3])<<16);
569 a+=k[0]+(((uint32_t)k[1])<<16);
571 case 9 : c+=k8[8]; /* fall through */
572 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
573 a+=k[0]+(((uint32_t)k[1])<<16);
575 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
577 a+=k[0]+(((uint32_t)k[1])<<16);
579 case 5 : b+=k8[4]; /* fall through */
580 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
582 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
587 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
590 } else { /* need to read the key one byte at a time */
591 const uint8_t *k = (const uint8_t *)key;
593 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
597 a += ((uint32_t)k[1])<<8;
598 a += ((uint32_t)k[2])<<16;
599 a += ((uint32_t)k[3])<<24;
601 b += ((uint32_t)k[5])<<8;
602 b += ((uint32_t)k[6])<<16;
603 b += ((uint32_t)k[7])<<24;
605 c += ((uint32_t)k[9])<<8;
606 c += ((uint32_t)k[10])<<16;
607 c += ((uint32_t)k[11])<<24;
613 /*-------------------------------- last block: affect all 32 bits of (c) */
614 switch(length) /* all the case statements fall through */
616 case 12: c+=((uint32_t)k[11])<<24;
617 case 11: c+=((uint32_t)k[10])<<16;
618 case 10: c+=((uint32_t)k[9])<<8;
620 case 8 : b+=((uint32_t)k[7])<<24;
621 case 7 : b+=((uint32_t)k[6])<<16;
622 case 6 : b+=((uint32_t)k[5])<<8;
624 case 4 : a+=((uint32_t)k[3])<<24;
625 case 3 : a+=((uint32_t)k[2])<<16;
626 case 2 : a+=((uint32_t)k[1])<<8;
629 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
641 * This is the same as hashword() on big-endian machines. It is different
642 * from hashlittle() on all machines. hashbig() takes advantage of
643 * big-endian byte ordering.
645 uint32_t hashbig( const void *key, size_t length, uint32_t initval)
648 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
650 /* Set up the internal state */
651 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
654 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
655 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
658 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
669 /*----------------------------- handle the last (probably partial) block */
671 * "k[2]<<8" actually reads beyond the end of the string, but
672 * then shifts out the part it's not allowed to read. Because the
673 * string is aligned, the illegal read is in the same word as the
674 * rest of the string. Every machine with memory protection I've seen
675 * does it on word boundaries, so is OK with this. But VALGRIND will
676 * still catch it and complain. The masking trick does make the hash
677 * noticably faster for short strings (like English words).
683 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
684 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
685 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
686 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
687 case 8 : b+=k[1]; a+=k[0]; break;
688 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
689 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
690 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
691 case 4 : a+=k[0]; break;
692 case 3 : a+=k[0]&0xffffff00; break;
693 case 2 : a+=k[0]&0xffff0000; break;
694 case 1 : a+=k[0]&0xff000000; break;
695 case 0 : return c; /* zero length strings require no mixing */
698 #else /* make valgrind happy */
700 k8 = (const uint8_t *)k;
701 switch(length) /* all the case statements fall through */
703 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
704 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
705 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
706 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
707 case 8 : b+=k[1]; a+=k[0]; break;
708 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
709 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
710 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
711 case 4 : a+=k[0]; break;
712 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
713 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
714 case 1 : a+=((uint32_t)k8[0])<<24; break;
718 #endif /* !VALGRIND */
720 } else { /* need to read the key one byte at a time */
721 const uint8_t *k = (const uint8_t *)key;
723 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
726 a += ((uint32_t)k[0])<<24;
727 a += ((uint32_t)k[1])<<16;
728 a += ((uint32_t)k[2])<<8;
729 a += ((uint32_t)k[3]);
730 b += ((uint32_t)k[4])<<24;
731 b += ((uint32_t)k[5])<<16;
732 b += ((uint32_t)k[6])<<8;
733 b += ((uint32_t)k[7]);
734 c += ((uint32_t)k[8])<<24;
735 c += ((uint32_t)k[9])<<16;
736 c += ((uint32_t)k[10])<<8;
737 c += ((uint32_t)k[11]);
743 /*-------------------------------- last block: affect all 32 bits of (c) */
744 switch(length) /* all the case statements fall through */
747 case 11: c+=((uint32_t)k[10])<<8;
748 case 10: c+=((uint32_t)k[9])<<16;
749 case 9 : c+=((uint32_t)k[8])<<24;
751 case 7 : b+=((uint32_t)k[6])<<8;
752 case 6 : b+=((uint32_t)k[5])<<16;
753 case 5 : b+=((uint32_t)k[4])<<24;
755 case 3 : a+=((uint32_t)k[2])<<8;
756 case 2 : a+=((uint32_t)k[1])<<16;
757 case 1 : a+=((uint32_t)k[0])<<24;
770 /* used for timings */
779 for (i=0; i<256; ++i) buf[i] = 'x';
782 h = hashlittle(&buf[0],1,h);
785 if (z-a > 0) printf("time %d %.8x\n", z-a, h);
788 /* check that every input bit changes every output bit half the time */
795 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
796 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
797 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
798 uint32_t x[HASHSTATE],y[HASHSTATE];
801 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
802 for (hlen=0; hlen < MAXLEN; ++hlen)
805 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
807 for (j=0; j<8; ++j) /*------------------------ for each input bit, */
809 for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
811 for (l=0; l<HASHSTATE; ++l)
812 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
814 /*---- check that every output bit is affected by that input bit */
815 for (k=0; k<MAXPAIR; k+=2)
818 /* keys have one bit different */
819 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
820 /* have a and b be two keys differing in only one bit */
823 c[0] = hashlittle(a, hlen, m);
825 b[i] ^= ((k+1)>>(8-j));
826 d[0] = hashlittle(b, hlen, m);
827 /* check every bit is 1, 0, set, and not set at least once */
828 for (l=0; l<HASHSTATE; ++l)
831 f[l] &= ~(c[l]^d[l]);
836 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
843 printf("Some bit didn't change: ");
844 printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
845 e[0],f[0],g[0],h[0],x[0],y[0]);
846 printf("i %d j %d m %d len %d\n", i, j, m, hlen);
848 if (z==MAXPAIR) goto done;
855 printf("Mix success %2d bytes %2d initvals ",i,m);
856 printf("required %d trials\n", z/2);
862 /* Check for reading beyond the end of the buffer and alignment problems */
865 uint8_t buf[MAXLEN+20], *b;
867 uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
869 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
871 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
873 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
877 printf("Endianness. These lines should all be the same (for values filled in):\n");
878 printf("%.8x %.8x %.8x\n",
879 hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
880 hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
881 hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
883 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
884 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
885 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
886 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
887 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
888 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
889 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
891 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
892 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
893 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
894 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
895 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
896 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
897 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
899 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
900 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
901 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
902 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
903 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
904 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
905 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
907 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
908 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
909 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
910 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
911 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
912 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
913 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
916 /* check that hashlittle2 and hashlittle produce the same results */
918 hashlittle2(q, sizeof(q), &i, &j);
919 if (hashlittle(q, sizeof(q), 47) != i)
920 printf("hashlittle2 and hashlittle mismatch\n");
922 /* check that hashword2 and hashword produce the same results */
925 hashword2(&len, 1, &i, &j);
926 if (hashword(&len, 1, 47) != i)
927 printf("hashword2 and hashword mismatch %x %x\n",
928 i, hashword(&len, 1, 47));
930 /* check hashlittle doesn't read before or after the ends of the string */
931 for (h=0, b=buf+1; h<8; ++h, ++b)
933 for (i=0; i<MAXLEN; ++i)
936 for (j=0; j<i; ++j) *(b+j)=0;
938 /* these should all be equal */
939 ref = hashlittle(b, len, (uint32_t)1);
942 x = hashlittle(b, len, (uint32_t)1);
943 y = hashlittle(b, len, (uint32_t)1);
944 if ((ref != x) || (ref != y))
946 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
953 /* check for problems with nulls */
957 uint32_t h,i,state[HASHSTATE];
961 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
962 printf("These should all be different\n");
963 for (i=0, h=0; i<8; ++i)
965 h = hashlittle(buf, 0, h);
966 printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
973 b=0, c=0, hashlittle2("", 0, &c, &b);
974 printf("hash is %.8lx %.8lx\n", c, b); /* deadbeef deadbeef */
975 b=0xdeadbeef, c=0, hashlittle2("", 0, &c, &b);
976 printf("hash is %.8lx %.8lx\n", c, b); /* bd5b7dde deadbeef */
977 b=0xdeadbeef, c=0xdeadbeef, hashlittle2("", 0, &c, &b);
978 printf("hash is %.8lx %.8lx\n", c, b); /* 9c093ccd bd5b7dde */
979 b=0, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
980 printf("hash is %.8lx %.8lx\n", c, b); /* 17770551 ce7226e6 */
981 b=1, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
982 printf("hash is %.8lx %.8lx\n", c, b); /* e3607cae bd371de4 */
983 b=0, c=1, hashlittle2("Four score and seven years ago", 30, &c, &b);
984 printf("hash is %.8lx %.8lx\n", c, b); /* cd628161 6cbea4b3 */
985 c = hashlittle("Four score and seven years ago", 30, 0);
986 printf("hash is %.8lx\n", c); /* 17770551 */
987 c = hashlittle("Four score and seven years ago", 30, 1);
988 printf("hash is %.8lx\n", c); /* cd628161 */
994 driver1(); /* test that the key is hashed: used for timings */
995 driver2(); /* test that whole key is hashed thoroughly */
996 driver3(); /* test that nothing but the key is hashed */
997 driver4(); /* test hashing multiple buffers (all buffers are null) */
998 driver5(); /* test the hash against known vectors */
1002 #endif /* SELF_TEST */