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, uint32_t base)
548 const uint64_t *k = key;
551 /* Set up the internal state */
552 a = b = c = 0xdeadbeef + ((uint32_t)n*8) + 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, uint32_t base)
587 const uint32_t *k = key;
590 /* Set up the internal state */
591 a = b = c = 0xdeadbeef + ((uint32_t)n*4) + base;
612 return ((uint64_t)b << 32) | c;
615 uint64_t hash64_stable_16(const void *key, size_t n, uint32_t base)
617 const uint16_t *k = key;
620 /* Set up the internal state */
621 a = b = c = 0xdeadbeef + ((uint32_t)n*2) + 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, uint32_t base)
654 uint32_t lower = hashlittle(key, n, &base);
656 return ((uint64_t)base << 32) | lower;
659 uint32_t hash_any(const void *key, size_t length, uint32_t base)
662 return hashbig(key, length, &base);
664 return hashlittle(key, length, &base);
667 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base)
669 return hash64_stable_64(key, n, base);
672 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base)
674 return hash64_stable_32(key, n, base);
677 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base)
679 return hash64_stable_16(key, n, base);
682 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base)
684 return hashlittle(key, n, &base);
687 /* Jenkins' lookup8 is a 64 bit hash, but he says it's obsolete. Use
688 * the plain one and recombine into 64 bits. */
689 uint64_t hash64_any(const void *key, size_t length, uint32_t base)
694 lower = hashbig(key, length, &base);
696 lower = hashlittle(key, length, &base);
698 return ((uint64_t)base << 32) | lower;
703 /* used for timings */
712 for (i=0; i<256; ++i) buf[i] = 'x';
715 h = hashlittle(&buf[0],1,h);
718 if (z-a > 0) printf("time %d %.8x\n", z-a, h);
721 /* check that every input bit changes every output bit half the time */
728 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
729 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
730 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
731 uint32_t x[HASHSTATE],y[HASHSTATE];
734 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
735 for (hlen=0; hlen < MAXLEN; ++hlen)
738 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
740 for (j=0; j<8; ++j) /*------------------------ for each input bit, */
742 for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
744 for (l=0; l<HASHSTATE; ++l)
745 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
747 /*---- check that every output bit is affected by that input bit */
748 for (k=0; k<MAXPAIR; k+=2)
751 /* keys have one bit different */
752 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
753 /* have a and b be two keys differing in only one bit */
756 c[0] = hashlittle(a, hlen, m);
758 b[i] ^= ((k+1)>>(8-j));
759 d[0] = hashlittle(b, hlen, m);
760 /* check every bit is 1, 0, set, and not set at least once */
761 for (l=0; l<HASHSTATE; ++l)
764 f[l] &= ~(c[l]^d[l]);
769 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
776 printf("Some bit didn't change: ");
777 printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
778 e[0],f[0],g[0],h[0],x[0],y[0]);
779 printf("i %d j %d m %d len %d\n", i, j, m, hlen);
781 if (z==MAXPAIR) goto done;
788 printf("Mix success %2d bytes %2d initvals ",i,m);
789 printf("required %d trials\n", z/2);
795 /* Check for reading beyond the end of the buffer and alignment problems */
798 uint8_t buf[MAXLEN+20], *b;
800 uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
802 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
804 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
806 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
810 printf("Endianness. These lines should all be the same (for values filled in):\n");
811 printf("%.8x %.8x %.8x\n",
812 hash_word((const uint32_t *)q, (sizeof(q)-1)/4, 13),
813 hash_word((const uint32_t *)q, (sizeof(q)-5)/4, 13),
814 hash_word((const uint32_t *)q, (sizeof(q)-9)/4, 13));
816 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
817 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
818 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
819 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
820 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
821 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
822 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
824 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
825 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
826 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
827 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
828 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
829 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
830 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
832 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
833 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
834 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
835 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
836 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
837 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
838 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
840 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
841 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
842 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
843 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
844 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
845 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
846 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
849 /* check that hashlittle2 and hashlittle produce the same results */
851 hashlittle2(q, sizeof(q), &i, &j);
852 if (hashlittle(q, sizeof(q), 47) != i)
853 printf("hashlittle2 and hashlittle mismatch\n");
855 /* check that hash_word2 and hash_word produce the same results */
858 hash_word2(&len, 1, &i, &j);
859 if (hash_word(&len, 1, 47) != i)
860 printf("hash_word2 and hash_word mismatch %x %x\n",
861 i, hash_word(&len, 1, 47));
863 /* check hashlittle doesn't read before or after the ends of the string */
864 for (h=0, b=buf+1; h<8; ++h, ++b)
866 for (i=0; i<MAXLEN; ++i)
869 for (j=0; j<i; ++j) *(b+j)=0;
871 /* these should all be equal */
872 ref = hashlittle(b, len, (uint32_t)1);
875 x = hashlittle(b, len, (uint32_t)1);
876 y = hashlittle(b, len, (uint32_t)1);
877 if ((ref != x) || (ref != y))
879 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
886 /* check for problems with nulls */
890 uint32_t h,i,state[HASHSTATE];
894 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
895 printf("These should all be different\n");
896 for (i=0, h=0; i<8; ++i)
898 h = hashlittle(buf, 0, h);
899 printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
906 driver1(); /* test that the key is hashed: used for timings */
907 driver2(); /* test that whole key is hashed thoroughly */
908 driver3(); /* test that nothing but the key is hashed */
909 driver4(); /* test hashing multiple buffers (all buffers are null) */
913 #endif /* SELF_TEST */