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(__x86_64) || \
58 defined(vax) || defined(MIPSEL))
59 # define HASH_LITTLE_ENDIAN 1
60 # define HASH_BIG_ENDIAN 0
61 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
62 __BYTE_ORDER == __BIG_ENDIAN) || \
63 (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
64 # define HASH_LITTLE_ENDIAN 0
65 # define HASH_BIG_ENDIAN 1
67 # error Unknown endian
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 */
213 -------------------------------------------------------------------------------
214 hashlittle() -- hash a variable-length key into a 32-bit value
215 k : the key (the unaligned variable-length array of bytes)
216 length : the length of the key, counting by bytes
217 val2 : IN: can be any 4-byte value OUT: second 32 bit hash.
218 Returns a 32-bit value. Every bit of the key affects every bit of
219 the return value. Two keys differing by one or two bits will have
220 totally different hash values. Note that the return value is better
221 mixed than val2, so use that first.
223 The best hash table sizes are powers of 2. There is no need to do
224 mod a prime (mod is sooo slow!). If you need less than 32 bits,
225 use a bitmask. For example, if you need only 10 bits, do
226 h = (h & hashmask(10));
227 In which case, the hash table should have hashsize(10) elements.
229 If you are hashing n strings (uint8_t **)k, do it like this:
230 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
232 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
233 code any way you wish, private, educational, or commercial. It's free.
235 Use for hash table lookup, or anything where one collision in 2^^32 is
236 acceptable. Do NOT use for cryptographic purposes.
237 -------------------------------------------------------------------------------
240 static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 )
242 uint32_t a,b,c; /* internal state */
243 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
245 /* Set up the internal state */
246 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
249 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
250 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
255 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
266 /*----------------------------- handle the last (probably partial) block */
268 * "k[2]&0xffffff" actually reads beyond the end of the string, but
269 * then masks off the part it's not allowed to read. Because the
270 * string is aligned, the masked-off tail is in the same word as the
271 * rest of the string. Every machine with memory protection I've seen
272 * does it on word boundaries, so is OK with this. But VALGRIND will
273 * still catch it and complain. The masking trick does make the hash
274 * noticably faster for short strings (like English words).
280 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
281 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
282 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
283 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
284 case 8 : b+=k[1]; a+=k[0]; break;
285 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
286 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
287 case 5 : b+=k[1]&0xff; a+=k[0]; break;
288 case 4 : a+=k[0]; break;
289 case 3 : a+=k[0]&0xffffff; break;
290 case 2 : a+=k[0]&0xffff; break;
291 case 1 : a+=k[0]&0xff; break;
292 case 0 : return c; /* zero length strings require no mixing */
295 #else /* make valgrind happy */
297 k8 = (const uint8_t *)k;
300 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
301 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
302 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
303 case 9 : c+=k8[8]; /* fall through */
304 case 8 : b+=k[1]; a+=k[0]; break;
305 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
306 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
307 case 5 : b+=k8[4]; /* fall through */
308 case 4 : a+=k[0]; break;
309 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
310 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
311 case 1 : a+=k8[0]; break;
315 #endif /* !valgrind */
317 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
318 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
321 /*--------------- all but last block: aligned reads and different mixing */
324 a += k[0] + (((uint32_t)k[1])<<16);
325 b += k[2] + (((uint32_t)k[3])<<16);
326 c += k[4] + (((uint32_t)k[5])<<16);
332 /*----------------------------- handle the last (probably partial) block */
333 k8 = (const uint8_t *)k;
336 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
337 b+=k[2]+(((uint32_t)k[3])<<16);
338 a+=k[0]+(((uint32_t)k[1])<<16);
340 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
342 b+=k[2]+(((uint32_t)k[3])<<16);
343 a+=k[0]+(((uint32_t)k[1])<<16);
345 case 9 : c+=k8[8]; /* fall through */
346 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
347 a+=k[0]+(((uint32_t)k[1])<<16);
349 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
351 a+=k[0]+(((uint32_t)k[1])<<16);
353 case 5 : b+=k8[4]; /* fall through */
354 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
356 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
361 case 0 : return c; /* zero length requires no mixing */
364 } else { /* need to read the key one byte at a time */
365 const uint8_t *k = (const uint8_t *)key;
367 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
371 a += ((uint32_t)k[1])<<8;
372 a += ((uint32_t)k[2])<<16;
373 a += ((uint32_t)k[3])<<24;
375 b += ((uint32_t)k[5])<<8;
376 b += ((uint32_t)k[6])<<16;
377 b += ((uint32_t)k[7])<<24;
379 c += ((uint32_t)k[9])<<8;
380 c += ((uint32_t)k[10])<<16;
381 c += ((uint32_t)k[11])<<24;
387 /*-------------------------------- last block: affect all 32 bits of (c) */
388 switch(length) /* all the case statements fall through */
390 case 12: c+=((uint32_t)k[11])<<24;
391 case 11: c+=((uint32_t)k[10])<<16;
392 case 10: c+=((uint32_t)k[9])<<8;
394 case 8 : b+=((uint32_t)k[7])<<24;
395 case 7 : b+=((uint32_t)k[6])<<16;
396 case 6 : b+=((uint32_t)k[5])<<8;
398 case 4 : a+=((uint32_t)k[3])<<24;
399 case 3 : a+=((uint32_t)k[2])<<16;
400 case 2 : a+=((uint32_t)k[1])<<8;
414 * This is the same as hash_word() on big-endian machines. It is different
415 * from hashlittle() on all machines. hashbig() takes advantage of
416 * big-endian byte ordering.
418 static uint32_t hashbig( const void *key, size_t length, uint32_t *val2)
421 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
423 /* Set up the internal state */
424 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
427 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
428 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
433 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
444 /*----------------------------- handle the last (probably partial) block */
446 * "k[2]<<8" actually reads beyond the end of the string, but
447 * then shifts out the part it's not allowed to read. Because the
448 * string is aligned, the illegal read is in the same word as the
449 * rest of the string. Every machine with memory protection I've seen
450 * does it on word boundaries, so is OK with this. But VALGRIND will
451 * still catch it and complain. The masking trick does make the hash
452 * noticably faster for short strings (like English words).
458 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
459 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
460 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
461 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
462 case 8 : b+=k[1]; a+=k[0]; break;
463 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
464 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
465 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
466 case 4 : a+=k[0]; break;
467 case 3 : a+=k[0]&0xffffff00; break;
468 case 2 : a+=k[0]&0xffff0000; break;
469 case 1 : a+=k[0]&0xff000000; break;
470 case 0 : return c; /* zero length strings require no mixing */
473 #else /* make valgrind happy */
475 k8 = (const uint8_t *)k;
476 switch(length) /* all the case statements fall through */
478 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
479 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
480 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
481 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
482 case 8 : b+=k[1]; a+=k[0]; break;
483 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
484 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
485 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
486 case 4 : a+=k[0]; break;
487 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
488 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
489 case 1 : a+=((uint32_t)k8[0])<<24; break;
493 #endif /* !VALGRIND */
495 } else { /* need to read the key one byte at a time */
496 const uint8_t *k = (const uint8_t *)key;
498 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
501 a += ((uint32_t)k[0])<<24;
502 a += ((uint32_t)k[1])<<16;
503 a += ((uint32_t)k[2])<<8;
504 a += ((uint32_t)k[3]);
505 b += ((uint32_t)k[4])<<24;
506 b += ((uint32_t)k[5])<<16;
507 b += ((uint32_t)k[6])<<8;
508 b += ((uint32_t)k[7]);
509 c += ((uint32_t)k[8])<<24;
510 c += ((uint32_t)k[9])<<16;
511 c += ((uint32_t)k[10])<<8;
512 c += ((uint32_t)k[11]);
518 /*-------------------------------- last block: affect all 32 bits of (c) */
519 switch(length) /* all the case statements fall through */
522 case 11: c+=((uint32_t)k[10])<<8;
523 case 10: c+=((uint32_t)k[9])<<16;
524 case 9 : c+=((uint32_t)k[8])<<24;
526 case 7 : b+=((uint32_t)k[6])<<8;
527 case 6 : b+=((uint32_t)k[5])<<16;
528 case 5 : b+=((uint32_t)k[4])<<24;
530 case 3 : a+=((uint32_t)k[2])<<8;
531 case 2 : a+=((uint32_t)k[1])<<16;
532 case 1 : a+=((uint32_t)k[0])<<24;
543 /* I basically use hashlittle here, but use native endian within each
544 * element. This delivers least-surprise: hash such as "int arr[] = {
545 * 1, 2 }; hash_stable(arr, 2, 0);" will be the same on big and little
546 * endian machines, even though a bytewise hash wouldn't be. */
547 uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base)
549 const uint64_t *k = key;
552 /* Set up the internal state */
553 a = b = c = 0xdeadbeef + ((uint32_t)n*8) + (base >> 32) + base;
557 b += (uint32_t)(k[0] >> 32);
560 a += (uint32_t)(k[1] >> 32);
562 c += (uint32_t)(k[2] >> 32);
570 b += (uint32_t)(k[0] >> 32);
573 a += (uint32_t)(k[1] >> 32);
577 b += (uint32_t)(k[0] >> 32);
583 return ((uint64_t)b << 32) | c;
586 uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base)
588 const uint32_t *k = key;
591 /* Set up the internal state */
592 a = b = c = 0xdeadbeef + ((uint32_t)n*4) + (base >> 32) + base;
613 return ((uint64_t)b << 32) | c;
616 uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base)
618 const uint16_t *k = key;
621 /* Set up the internal state */
622 a = b = c = 0xdeadbeef + ((uint32_t)n*2) + (base >> 32) + base;
625 a += (uint32_t)k[0] + ((uint32_t)k[1] << 16);
626 b += (uint32_t)k[2] + ((uint32_t)k[3] << 16);
627 c += (uint32_t)k[4] + ((uint32_t)k[5] << 16);
638 b += ((uint32_t)k[3] << 16);
642 a += ((uint32_t)k[1] << 16);
650 return ((uint64_t)b << 32) | c;
653 uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base)
655 uint32_t b32 = base + (base >> 32);
656 uint32_t lower = hashlittle(key, n, &b32);
658 return ((uint64_t)b32 << 32) | lower;
661 uint32_t hash_any(const void *key, size_t length, uint32_t base)
664 return hashbig(key, length, &base);
666 return hashlittle(key, length, &base);
669 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base)
671 return hash64_stable_64(key, n, base);
674 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base)
676 return hash64_stable_32(key, n, base);
679 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base)
681 return hash64_stable_16(key, n, base);
684 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base)
686 return hashlittle(key, n, &base);
689 /* Jenkins' lookup8 is a 64 bit hash, but he says it's obsolete. Use
690 * the plain one and recombine into 64 bits. */
691 uint64_t hash64_any(const void *key, size_t length, uint64_t base)
693 uint32_t b32 = base + (base >> 32);
697 lower = hashbig(key, length, &b32);
699 lower = hashlittle(key, length, &b32);
701 return ((uint64_t)b32 << 32) | lower;
706 /* used for timings */
715 for (i=0; i<256; ++i) buf[i] = 'x';
718 h = hashlittle(&buf[0],1,h);
721 if (z-a > 0) printf("time %d %.8x\n", z-a, h);
724 /* check that every input bit changes every output bit half the time */
731 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
732 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
733 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
734 uint32_t x[HASHSTATE],y[HASHSTATE];
737 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
738 for (hlen=0; hlen < MAXLEN; ++hlen)
741 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
743 for (j=0; j<8; ++j) /*------------------------ for each input bit, */
745 for (m=1; m<8; ++m) /*------------ for several possible initvals, */
747 for (l=0; l<HASHSTATE; ++l)
748 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
750 /*---- check that every output bit is affected by that input bit */
751 for (k=0; k<MAXPAIR; k+=2)
754 /* keys have one bit different */
755 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
756 /* have a and b be two keys differing in only one bit */
759 c[0] = hashlittle(a, hlen, m);
761 b[i] ^= ((k+1)>>(8-j));
762 d[0] = hashlittle(b, hlen, m);
763 /* check every bit is 1, 0, set, and not set at least once */
764 for (l=0; l<HASHSTATE; ++l)
767 f[l] &= ~(c[l]^d[l]);
772 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
779 printf("Some bit didn't change: ");
780 printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
781 e[0],f[0],g[0],h[0],x[0],y[0]);
782 printf("i %d j %d m %d len %d\n", i, j, m, hlen);
784 if (z==MAXPAIR) goto done;
791 printf("Mix success %2d bytes %2d initvals ",i,m);
792 printf("required %d trials\n", z/2);
798 /* Check for reading beyond the end of the buffer and alignment problems */
801 uint8_t buf[MAXLEN+20], *b;
803 uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
805 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
807 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
809 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
813 printf("Endianness. These lines should all be the same (for values filled in):\n");
814 printf("%.8x %.8x %.8x\n",
815 hash_word((const uint32_t *)q, (sizeof(q)-1)/4, 13),
816 hash_word((const uint32_t *)q, (sizeof(q)-5)/4, 13),
817 hash_word((const uint32_t *)q, (sizeof(q)-9)/4, 13));
819 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
820 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
821 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
822 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
823 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
824 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
825 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
827 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
828 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
829 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
830 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
831 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
832 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
833 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
835 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
836 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
837 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
838 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
839 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
840 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
841 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
843 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
844 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
845 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
846 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
847 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
848 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
849 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
852 /* check that hashlittle2 and hashlittle produce the same results */
854 hashlittle2(q, sizeof(q), &i, &j);
855 if (hashlittle(q, sizeof(q), 47) != i)
856 printf("hashlittle2 and hashlittle mismatch\n");
858 /* check that hash_word2 and hash_word produce the same results */
861 hash_word2(&len, 1, &i, &j);
862 if (hash_word(&len, 1, 47) != i)
863 printf("hash_word2 and hash_word mismatch %x %x\n",
864 i, hash_word(&len, 1, 47));
866 /* check hashlittle doesn't read before or after the ends of the string */
867 for (h=0, b=buf+1; h<8; ++h, ++b)
869 for (i=0; i<MAXLEN; ++i)
872 for (j=0; j<i; ++j) *(b+j)=0;
874 /* these should all be equal */
875 ref = hashlittle(b, len, (uint32_t)1);
878 x = hashlittle(b, len, (uint32_t)1);
879 y = hashlittle(b, len, (uint32_t)1);
880 if ((ref != x) || (ref != y))
882 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
889 /* check for problems with nulls */
893 uint32_t h,i,state[HASHSTATE];
897 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
898 printf("These should all be different\n");
899 for (i=0, h=0; i<8; ++i)
901 h = hashlittle(buf, 0, h);
902 printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
909 driver1(); /* test that the key is hashed: used for timings */
910 driver2(); /* test that whole key is hashed thoroughly */
911 driver3(); /* test that nothing but the key is hashed */
912 driver4(); /* test hashing multiple buffers (all buffers are null) */
916 #endif /* SELF_TEST */