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 */
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 # error Unknown endian
69 #define hashsize(n) ((uint32_t)1<<(n))
70 #define hashmask(n) (hashsize(n)-1)
71 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
74 -------------------------------------------------------------------------------
75 mix -- mix 3 32-bit values reversibly.
77 This is reversible, so any information in (a,b,c) before mix() is
78 still in (a,b,c) after mix().
80 If four pairs of (a,b,c) inputs are run through mix(), or through
81 mix() in reverse, there are at least 32 bits of the output that
82 are sometimes the same for one pair and different for another pair.
84 * pairs that differed by one bit, by two bits, in any combination
85 of top bits of (a,b,c), or in any combination of bottom bits of
87 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
88 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
89 is commonly produced by subtraction) look like a single 1-bit
91 * the base values were pseudorandom, all zero but one bit set, or
92 all zero plus a counter that starts at zero.
94 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
99 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
100 for "differ" defined as + with a one-bit base and a two-bit delta. I
101 used http://burtleburtle.net/bob/hash/avalanche.html to choose
102 the operations, constants, and arrangements of the variables.
104 This does not achieve avalanche. There are input bits of (a,b,c)
105 that fail to affect some output bits of (a,b,c), especially of a. The
106 most thoroughly mixed value is c, but it doesn't really even achieve
109 This allows some parallelism. Read-after-writes are good at doubling
110 the number of bits affected, so the goal of mixing pulls in the opposite
111 direction as the goal of parallelism. I did what I could. Rotates
112 seem to cost as much as shifts on every machine I could lay my hands
113 on, and rotates are much kinder to the top and bottom bits, so I used
115 -------------------------------------------------------------------------------
119 a -= c; a ^= rot(c, 4); c += b; \
120 b -= a; b ^= rot(a, 6); a += c; \
121 c -= b; c ^= rot(b, 8); b += a; \
122 a -= c; a ^= rot(c,16); c += b; \
123 b -= a; b ^= rot(a,19); a += c; \
124 c -= b; c ^= rot(b, 4); b += a; \
128 -------------------------------------------------------------------------------
129 final -- final mixing of 3 32-bit values (a,b,c) into c
131 Pairs of (a,b,c) values differing in only a few bits will usually
132 produce values of c that look totally different. This was tested for
133 * pairs that differed by one bit, by two bits, in any combination
134 of top bits of (a,b,c), or in any combination of bottom bits of
136 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
137 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
138 is commonly produced by subtraction) look like a single 1-bit
140 * the base values were pseudorandom, all zero but one bit set, or
141 all zero plus a counter that starts at zero.
143 These constants passed:
146 and these came close:
150 -------------------------------------------------------------------------------
152 #define final(a,b,c) \
154 c ^= b; c -= rot(b,14); \
155 a ^= c; a -= rot(c,11); \
156 b ^= a; b -= rot(a,25); \
157 c ^= b; c -= rot(b,16); \
158 a ^= c; a -= rot(c,4); \
159 b ^= a; b -= rot(a,14); \
160 c ^= b; c -= rot(b,24); \
164 --------------------------------------------------------------------
165 This works on all machines. To be useful, it requires
166 -- that the key be an array of uint32_t's, and
167 -- that the length be the number of uint32_t's in the key
169 The function hash_word() is identical to hashlittle() on little-endian
170 machines, and identical to hashbig() on big-endian machines,
171 except that the length has to be measured in uint32_ts rather than in
172 bytes. hashlittle() is more complicated than hash_word() only because
173 hashlittle() has to dance around fitting the key bytes into registers.
174 --------------------------------------------------------------------
177 const uint32_t *k, /* the key, an array of uint32_t values */
178 size_t length, /* the length of the key, in uint32_ts */
179 uint32_t initval) /* the previous hash, or an arbitrary value */
183 /* Set up the internal state */
184 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
186 /*------------------------------------------------- handle most of the key */
197 /*------------------------------------------- handle the last 3 uint32_t's */
198 switch(length) /* all the case statements fall through */
204 case 0: /* case 0: nothing left to add */
207 /*------------------------------------------------------ report the result */
212 -------------------------------------------------------------------------------
213 hashlittle() -- hash a variable-length key into a 32-bit value
214 k : the key (the unaligned variable-length array of bytes)
215 length : the length of the key, counting by bytes
216 val2 : IN: can be any 4-byte value OUT: second 32 bit hash.
217 Returns a 32-bit value. Every bit of the key affects every bit of
218 the return value. Two keys differing by one or two bits will have
219 totally different hash values. Note that the return value is better
220 mixed than val2, so use that first.
222 The best hash table sizes are powers of 2. There is no need to do
223 mod a prime (mod is sooo slow!). If you need less than 32 bits,
224 use a bitmask. For example, if you need only 10 bits, do
225 h = (h & hashmask(10));
226 In which case, the hash table should have hashsize(10) elements.
228 If you are hashing n strings (uint8_t **)k, do it like this:
229 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
231 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
232 code any way you wish, private, educational, or commercial. It's free.
234 Use for hash table lookup, or anything where one collision in 2^^32 is
235 acceptable. Do NOT use for cryptographic purposes.
236 -------------------------------------------------------------------------------
239 static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 )
241 uint32_t a,b,c; /* internal state */
242 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
244 /* Set up the internal state */
245 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
248 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
249 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
254 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
265 /*----------------------------- handle the last (probably partial) block */
267 * "k[2]&0xffffff" actually reads beyond the end of the string, but
268 * then masks off the part it's not allowed to read. Because the
269 * string is aligned, the masked-off tail is in the same word as the
270 * rest of the string. Every machine with memory protection I've seen
271 * does it on word boundaries, so is OK with this. But VALGRIND will
272 * still catch it and complain. The masking trick does make the hash
273 * noticably faster for short strings (like English words).
279 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
280 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
281 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
282 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
283 case 8 : b+=k[1]; a+=k[0]; break;
284 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
285 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
286 case 5 : b+=k[1]&0xff; a+=k[0]; break;
287 case 4 : a+=k[0]; break;
288 case 3 : a+=k[0]&0xffffff; break;
289 case 2 : a+=k[0]&0xffff; break;
290 case 1 : a+=k[0]&0xff; break;
291 case 0 : return c; /* zero length strings require no mixing */
294 #else /* make valgrind happy */
296 k8 = (const uint8_t *)k;
299 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
300 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
301 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
302 case 9 : c+=k8[8]; /* fall through */
303 case 8 : b+=k[1]; a+=k[0]; break;
304 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
305 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
306 case 5 : b+=k8[4]; /* fall through */
307 case 4 : a+=k[0]; break;
308 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
309 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
310 case 1 : a+=k8[0]; break;
314 #endif /* !valgrind */
316 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
317 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
320 /*--------------- all but last block: aligned reads and different mixing */
323 a += k[0] + (((uint32_t)k[1])<<16);
324 b += k[2] + (((uint32_t)k[3])<<16);
325 c += k[4] + (((uint32_t)k[5])<<16);
331 /*----------------------------- handle the last (probably partial) block */
332 k8 = (const uint8_t *)k;
335 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
336 b+=k[2]+(((uint32_t)k[3])<<16);
337 a+=k[0]+(((uint32_t)k[1])<<16);
339 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
341 b+=k[2]+(((uint32_t)k[3])<<16);
342 a+=k[0]+(((uint32_t)k[1])<<16);
344 case 9 : c+=k8[8]; /* fall through */
345 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
346 a+=k[0]+(((uint32_t)k[1])<<16);
348 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
350 a+=k[0]+(((uint32_t)k[1])<<16);
352 case 5 : b+=k8[4]; /* fall through */
353 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
355 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
360 case 0 : return c; /* zero length requires no mixing */
363 } else { /* need to read the key one byte at a time */
364 const uint8_t *k = (const uint8_t *)key;
366 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
370 a += ((uint32_t)k[1])<<8;
371 a += ((uint32_t)k[2])<<16;
372 a += ((uint32_t)k[3])<<24;
374 b += ((uint32_t)k[5])<<8;
375 b += ((uint32_t)k[6])<<16;
376 b += ((uint32_t)k[7])<<24;
378 c += ((uint32_t)k[9])<<8;
379 c += ((uint32_t)k[10])<<16;
380 c += ((uint32_t)k[11])<<24;
386 /*-------------------------------- last block: affect all 32 bits of (c) */
387 switch(length) /* all the case statements fall through */
389 case 12: c+=((uint32_t)k[11])<<24;
390 case 11: c+=((uint32_t)k[10])<<16;
391 case 10: c+=((uint32_t)k[9])<<8;
393 case 8 : b+=((uint32_t)k[7])<<24;
394 case 7 : b+=((uint32_t)k[6])<<16;
395 case 6 : b+=((uint32_t)k[5])<<8;
397 case 4 : a+=((uint32_t)k[3])<<24;
398 case 3 : a+=((uint32_t)k[2])<<16;
399 case 2 : a+=((uint32_t)k[1])<<8;
413 * This is the same as hash_word() on big-endian machines. It is different
414 * from hashlittle() on all machines. hashbig() takes advantage of
415 * big-endian byte ordering.
417 static uint32_t hashbig( const void *key, size_t length, uint32_t *val2)
420 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
422 /* Set up the internal state */
423 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
426 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
427 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
432 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
443 /*----------------------------- handle the last (probably partial) block */
445 * "k[2]<<8" actually reads beyond the end of the string, but
446 * then shifts out the part it's not allowed to read. Because the
447 * string is aligned, the illegal read is in the same word as the
448 * rest of the string. Every machine with memory protection I've seen
449 * does it on word boundaries, so is OK with this. But VALGRIND will
450 * still catch it and complain. The masking trick does make the hash
451 * noticably faster for short strings (like English words).
457 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
458 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
459 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
460 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
461 case 8 : b+=k[1]; a+=k[0]; break;
462 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
463 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
464 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
465 case 4 : a+=k[0]; break;
466 case 3 : a+=k[0]&0xffffff00; break;
467 case 2 : a+=k[0]&0xffff0000; break;
468 case 1 : a+=k[0]&0xff000000; break;
469 case 0 : return c; /* zero length strings require no mixing */
472 #else /* make valgrind happy */
474 k8 = (const uint8_t *)k;
475 switch(length) /* all the case statements fall through */
477 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
478 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
479 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
480 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
481 case 8 : b+=k[1]; a+=k[0]; break;
482 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
483 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
484 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
485 case 4 : a+=k[0]; break;
486 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
487 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
488 case 1 : a+=((uint32_t)k8[0])<<24; break;
492 #endif /* !VALGRIND */
494 } else { /* need to read the key one byte at a time */
495 const uint8_t *k = (const uint8_t *)key;
497 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
500 a += ((uint32_t)k[0])<<24;
501 a += ((uint32_t)k[1])<<16;
502 a += ((uint32_t)k[2])<<8;
503 a += ((uint32_t)k[3]);
504 b += ((uint32_t)k[4])<<24;
505 b += ((uint32_t)k[5])<<16;
506 b += ((uint32_t)k[6])<<8;
507 b += ((uint32_t)k[7]);
508 c += ((uint32_t)k[8])<<24;
509 c += ((uint32_t)k[9])<<16;
510 c += ((uint32_t)k[10])<<8;
511 c += ((uint32_t)k[11]);
517 /*-------------------------------- last block: affect all 32 bits of (c) */
518 switch(length) /* all the case statements fall through */
521 case 11: c+=((uint32_t)k[10])<<8;
522 case 10: c+=((uint32_t)k[9])<<16;
523 case 9 : c+=((uint32_t)k[8])<<24;
525 case 7 : b+=((uint32_t)k[6])<<8;
526 case 6 : b+=((uint32_t)k[5])<<16;
527 case 5 : b+=((uint32_t)k[4])<<24;
529 case 3 : a+=((uint32_t)k[2])<<8;
530 case 2 : a+=((uint32_t)k[1])<<16;
531 case 1 : a+=((uint32_t)k[0])<<24;
542 /* I basically use hashlittle here, but use native endian within each
543 * element. This delivers least-surprise: hash such as "int arr[] = {
544 * 1, 2 }; hash_stable(arr, 2, 0);" will be the same on big and little
545 * endian machines, even though a bytewise hash wouldn't be. */
546 uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base)
548 const uint64_t *k = key;
551 /* Set up the internal state */
552 a = b = c = 0xdeadbeef + ((uint32_t)n*8) + (base >> 32) + base;
556 b += (uint32_t)(k[0] >> 32);
559 a += (uint32_t)(k[1] >> 32);
561 c += (uint32_t)(k[2] >> 32);
569 b += (uint32_t)(k[0] >> 32);
572 a += (uint32_t)(k[1] >> 32);
576 b += (uint32_t)(k[0] >> 32);
582 return ((uint64_t)b << 32) | c;
585 uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base)
587 const uint32_t *k = key;
590 /* Set up the internal state */
591 a = b = c = 0xdeadbeef + ((uint32_t)n*4) + (base >> 32) + base;
612 return ((uint64_t)b << 32) | c;
615 uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base)
617 const uint16_t *k = key;
620 /* Set up the internal state */
621 a = b = c = 0xdeadbeef + ((uint32_t)n*2) + (base >> 32) + base;
624 a += (uint32_t)k[0] + ((uint32_t)k[1] << 16);
625 b += (uint32_t)k[2] + ((uint32_t)k[3] << 16);
626 c += (uint32_t)k[4] + ((uint32_t)k[5] << 16);
637 b += ((uint32_t)k[3] << 16);
641 a += ((uint32_t)k[1] << 16);
649 return ((uint64_t)b << 32) | c;
652 uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base)
654 uint32_t b32 = base + (base >> 32);
655 uint32_t lower = hashlittle(key, n, &b32);
657 return ((uint64_t)b32 << 32) | lower;
660 uint32_t hash_any(const void *key, size_t length, uint32_t base)
663 return hashbig(key, length, &base);
665 return hashlittle(key, length, &base);
668 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base)
670 return hash64_stable_64(key, n, base);
673 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base)
675 return hash64_stable_32(key, n, base);
678 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base)
680 return hash64_stable_16(key, n, base);
683 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base)
685 return hashlittle(key, n, &base);
688 /* Jenkins' lookup8 is a 64 bit hash, but he says it's obsolete. Use
689 * the plain one and recombine into 64 bits. */
690 uint64_t hash64_any(const void *key, size_t length, uint64_t base)
692 uint32_t b32 = base + (base >> 32);
696 lower = hashbig(key, length, &b32);
698 lower = hashlittle(key, length, &b32);
700 return ((uint64_t)b32 << 32) | lower;
705 /* used for timings */
714 for (i=0; i<256; ++i) buf[i] = 'x';
717 h = hashlittle(&buf[0],1,h);
720 if (z-a > 0) printf("time %d %.8x\n", z-a, h);
723 /* check that every input bit changes every output bit half the time */
730 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
731 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
732 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
733 uint32_t x[HASHSTATE],y[HASHSTATE];
736 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
737 for (hlen=0; hlen < MAXLEN; ++hlen)
740 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
742 for (j=0; j<8; ++j) /*------------------------ for each input bit, */
744 for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
746 for (l=0; l<HASHSTATE; ++l)
747 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
749 /*---- check that every output bit is affected by that input bit */
750 for (k=0; k<MAXPAIR; k+=2)
753 /* keys have one bit different */
754 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
755 /* have a and b be two keys differing in only one bit */
758 c[0] = hashlittle(a, hlen, m);
760 b[i] ^= ((k+1)>>(8-j));
761 d[0] = hashlittle(b, hlen, m);
762 /* check every bit is 1, 0, set, and not set at least once */
763 for (l=0; l<HASHSTATE; ++l)
766 f[l] &= ~(c[l]^d[l]);
771 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
778 printf("Some bit didn't change: ");
779 printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
780 e[0],f[0],g[0],h[0],x[0],y[0]);
781 printf("i %d j %d m %d len %d\n", i, j, m, hlen);
783 if (z==MAXPAIR) goto done;
790 printf("Mix success %2d bytes %2d initvals ",i,m);
791 printf("required %d trials\n", z/2);
797 /* Check for reading beyond the end of the buffer and alignment problems */
800 uint8_t buf[MAXLEN+20], *b;
802 uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
804 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
806 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
808 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
812 printf("Endianness. These lines should all be the same (for values filled in):\n");
813 printf("%.8x %.8x %.8x\n",
814 hash_word((const uint32_t *)q, (sizeof(q)-1)/4, 13),
815 hash_word((const uint32_t *)q, (sizeof(q)-5)/4, 13),
816 hash_word((const uint32_t *)q, (sizeof(q)-9)/4, 13));
818 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
819 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
820 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
821 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
822 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
823 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
824 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
826 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
827 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
828 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
829 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
830 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
831 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
832 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
834 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
835 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
836 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
837 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
838 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
839 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
840 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
842 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
843 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
844 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
845 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
846 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
847 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
848 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
851 /* check that hashlittle2 and hashlittle produce the same results */
853 hashlittle2(q, sizeof(q), &i, &j);
854 if (hashlittle(q, sizeof(q), 47) != i)
855 printf("hashlittle2 and hashlittle mismatch\n");
857 /* check that hash_word2 and hash_word produce the same results */
860 hash_word2(&len, 1, &i, &j);
861 if (hash_word(&len, 1, 47) != i)
862 printf("hash_word2 and hash_word mismatch %x %x\n",
863 i, hash_word(&len, 1, 47));
865 /* check hashlittle doesn't read before or after the ends of the string */
866 for (h=0, b=buf+1; h<8; ++h, ++b)
868 for (i=0; i<MAXLEN; ++i)
871 for (j=0; j<i; ++j) *(b+j)=0;
873 /* these should all be equal */
874 ref = hashlittle(b, len, (uint32_t)1);
877 x = hashlittle(b, len, (uint32_t)1);
878 y = hashlittle(b, len, (uint32_t)1);
879 if ((ref != x) || (ref != y))
881 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
888 /* check for problems with nulls */
892 uint32_t h,i,state[HASHSTATE];
896 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
897 printf("These should all be different\n");
898 for (i=0, h=0; i<8; ++i)
900 h = hashlittle(buf, 0, h);
901 printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
908 driver1(); /* test that the key is hashed: used for timings */
909 driver2(); /* test that whole key is hashed thoroughly */
910 driver3(); /* test that nothing but the key is hashed */
911 driver4(); /* test hashing multiple buffers (all buffers are null) */
915 #endif /* SELF_TEST */