2 May 2019(Wouter) patch to enable the valgrind clean implementation all the
3 time. This enables better security audit and checks, which is better
4 than the speedup. Git issue #30. Renamed the define ARRAY_CLEAN_ACCESS.
5 February 2013(Wouter) patch defines for BSD endianness, from Brad Smith.
6 January 2012(Wouter) added randomised initial value, fallout from 28c3.
7 March 2007(Wouter) adapted from lookup3.c original, add config.h include.
8 added #ifdef VALGRIND to remove 298,384,660 'unused variable k8' warnings.
9 added include of lookup3.h to check definitions match declarations.
10 removed include of stdint - config.h takes care of platform independence.
11 added fallthrough comments for new gcc warning suppression.
12 url http://burtleburtle.net/bob/hash/index.html.
15 -------------------------------------------------------------------------------
16 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
18 These are functions for producing 32-bit hashes for hash table lookup.
19 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
20 are externally useful functions. Routines to test the hash are included
21 if SELF_TEST is defined. You can use this free for any purpose. It's in
22 the public domain. It has no warranty.
24 You probably want to use hashlittle(). hashlittle() and hashbig()
25 hash byte arrays. hashlittle() is is faster than hashbig() on
26 little-endian machines. Intel and AMD are little-endian machines.
27 On second thought, you probably want hashlittle2(), which is identical to
28 hashlittle() except it returns two 32-bit hashes for the price of one.
29 You could implement hashbig2() if you wanted but I haven't bothered here.
31 If you want to find a hash of, say, exactly 7 integers, do
32 a = i1; b = i2; c = i3;
34 a += i4; b += i5; c += i6;
38 then use c as the hash value. If you have a variable length array of
39 4-byte integers to hash, use hashword(). If you have a byte array (like
40 a character string), use hashlittle(). If you have several byte arrays, or
41 a mix of things, see the comments above hashlittle().
43 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
44 then mix those integers. This is fast (you can do a lot more thorough
45 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
46 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
47 -------------------------------------------------------------------------------
49 /*#define SELF_TEST 1*/
50 #define ARRAY_CLEAN_ACCESS 1
53 #include "util/storage/lookup3.h"
54 #include <stdio.h> /* defines printf for tests */
55 #include <time.h> /* defines time_t for timings in the test */
56 /*#include <stdint.h> defines uint32_t etc (from config.h) */
57 #include <sys/param.h> /* attempt to define endianness */
58 #ifdef HAVE_SYS_TYPES_H
59 # include <sys/types.h> /* attempt to define endianness (solaris) */
61 #if defined(linux) || defined(__OpenBSD__)
63 # include <endian.h> /* attempt to define endianness */
65 # include <machine/endian.h> /* on older OpenBSD */
68 #if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__DragonFly__)
69 #include <sys/endian.h> /* attempt to define endianness */
72 /* random initial value */
73 static uint32_t raninit = (uint32_t)0xdeadbeef;
76 hash_set_raninit(uint32_t v)
82 * My best guess at if you are big-endian or little-endian. This may
85 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
86 __BYTE_ORDER == __LITTLE_ENDIAN) || \
87 (defined(i386) || defined(__i386__) || defined(__i486__) || \
88 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL) || defined(__x86))
89 # define HASH_LITTLE_ENDIAN 1
90 # define HASH_BIG_ENDIAN 0
91 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
92 __BYTE_ORDER == __BIG_ENDIAN) || \
93 (defined(sparc) || defined(__sparc) || defined(__sparc__) || defined(POWERPC) || defined(mc68000) || defined(sel))
94 # define HASH_LITTLE_ENDIAN 0
95 # define HASH_BIG_ENDIAN 1
96 #elif defined(_MACHINE_ENDIAN_H_)
97 /* test for machine_endian_h protects failure if some are empty strings */
98 # if defined(_BYTE_ORDER) && defined(_BIG_ENDIAN) && _BYTE_ORDER == _BIG_ENDIAN
99 # define HASH_LITTLE_ENDIAN 0
100 # define HASH_BIG_ENDIAN 1
102 # if defined(_BYTE_ORDER) && defined(_LITTLE_ENDIAN) && _BYTE_ORDER == _LITTLE_ENDIAN
103 # define HASH_LITTLE_ENDIAN 1
104 # define HASH_BIG_ENDIAN 0
105 # endif /* _MACHINE_ENDIAN_H_ */
107 # define HASH_LITTLE_ENDIAN 0
108 # define HASH_BIG_ENDIAN 0
111 #define hashsize(n) ((uint32_t)1<<(n))
112 #define hashmask(n) (hashsize(n)-1)
113 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
116 -------------------------------------------------------------------------------
117 mix -- mix 3 32-bit values reversibly.
119 This is reversible, so any information in (a,b,c) before mix() is
120 still in (a,b,c) after mix().
122 If four pairs of (a,b,c) inputs are run through mix(), or through
123 mix() in reverse, there are at least 32 bits of the output that
124 are sometimes the same for one pair and different for another pair.
126 * pairs that differed by one bit, by two bits, in any combination
127 of top bits of (a,b,c), or in any combination of bottom bits of
129 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
130 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
131 is commonly produced by subtraction) look like a single 1-bit
133 * the base values were pseudorandom, all zero but one bit set, or
134 all zero plus a counter that starts at zero.
136 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
141 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
142 for "differ" defined as + with a one-bit base and a two-bit delta. I
143 used http://burtleburtle.net/bob/hash/avalanche.html to choose
144 the operations, constants, and arrangements of the variables.
146 This does not achieve avalanche. There are input bits of (a,b,c)
147 that fail to affect some output bits of (a,b,c), especially of a. The
148 most thoroughly mixed value is c, but it doesn't really even achieve
151 This allows some parallelism. Read-after-writes are good at doubling
152 the number of bits affected, so the goal of mixing pulls in the opposite
153 direction as the goal of parallelism. I did what I could. Rotates
154 seem to cost as much as shifts on every machine I could lay my hands
155 on, and rotates are much kinder to the top and bottom bits, so I used
157 -------------------------------------------------------------------------------
161 a -= c; a ^= rot(c, 4); c += b; \
162 b -= a; b ^= rot(a, 6); a += c; \
163 c -= b; c ^= rot(b, 8); b += a; \
164 a -= c; a ^= rot(c,16); c += b; \
165 b -= a; b ^= rot(a,19); a += c; \
166 c -= b; c ^= rot(b, 4); b += a; \
170 -------------------------------------------------------------------------------
171 final -- final mixing of 3 32-bit values (a,b,c) into c
173 Pairs of (a,b,c) values differing in only a few bits will usually
174 produce values of c that look totally different. This was tested for
175 * pairs that differed by one bit, by two bits, in any combination
176 of top bits of (a,b,c), or in any combination of bottom bits of
178 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
179 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
180 is commonly produced by subtraction) look like a single 1-bit
182 * the base values were pseudorandom, all zero but one bit set, or
183 all zero plus a counter that starts at zero.
185 These constants passed:
188 and these came close:
192 -------------------------------------------------------------------------------
194 #define final(a,b,c) \
196 c ^= b; c -= rot(b,14); \
197 a ^= c; a -= rot(c,11); \
198 b ^= a; b -= rot(a,25); \
199 c ^= b; c -= rot(b,16); \
200 a ^= c; a -= rot(c,4); \
201 b ^= a; b -= rot(a,14); \
202 c ^= b; c -= rot(b,24); \
206 --------------------------------------------------------------------
207 This works on all machines. To be useful, it requires
208 -- that the key be an array of uint32_t's, and
209 -- that the length be the number of uint32_t's in the key
211 The function hashword() is identical to hashlittle() on little-endian
212 machines, and identical to hashbig() on big-endian machines,
213 except that the length has to be measured in uint32_ts rather than in
214 bytes. hashlittle() is more complicated than hashword() only because
215 hashlittle() has to dance around fitting the key bytes into registers.
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 initval) /* the previous hash, or an arbitrary value */
225 /* Set up the internal state */
226 a = b = c = raninit + (((uint32_t)length)<<2) + initval;
228 /*------------------------------------------------- handle most of the key */
239 /*------------------------------------------- handle the last 3 uint32_t's */
240 switch(length) /* all the case statements fall through */
248 case 0: /* case 0: nothing left to add */
251 /*------------------------------------------------------ report the result */
259 --------------------------------------------------------------------
260 hashword2() -- same as hashword(), but take two seeds and return two
261 32-bit values. pc and pb must both be nonnull, and *pc and *pb must
262 both be initialized with seeds. If you pass in (*pb)==0, the output
263 (*pc) will be the same as the return value from hashword().
264 --------------------------------------------------------------------
267 const uint32_t *k, /* the key, an array of uint32_t values */
268 size_t length, /* the length of the key, in uint32_ts */
269 uint32_t *pc, /* IN: seed OUT: primary hash value */
270 uint32_t *pb) /* IN: more seed OUT: secondary hash value */
274 /* Set up the internal state */
275 a = b = c = raninit + ((uint32_t)(length<<2)) + *pc;
278 /*------------------------------------------------- handle most of the key */
289 /*------------------------------------------- handle the last 3 uint32_t's */
290 switch(length) /* all the case statements fall through */
296 case 0: /* case 0: nothing left to add */
299 /*------------------------------------------------------ report the result */
303 #endif /* SELF_TEST */
306 -------------------------------------------------------------------------------
307 hashlittle() -- hash a variable-length key into a 32-bit value
308 k : the key (the unaligned variable-length array of bytes)
309 length : the length of the key, counting by bytes
310 initval : can be any 4-byte value
311 Returns a 32-bit value. Every bit of the key affects every bit of
312 the return value. Two keys differing by one or two bits will have
313 totally different hash values.
315 The best hash table sizes are powers of 2. There is no need to do
316 mod a prime (mod is sooo slow!). If you need less than 32 bits,
317 use a bitmask. For example, if you need only 10 bits, do
318 h = (h & hashmask(10));
319 In which case, the hash table should have hashsize(10) elements.
321 If you are hashing n strings (uint8_t **)k, do it like this:
322 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
324 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
325 code any way you wish, private, educational, or commercial. It's free.
327 Use for hash table lookup, or anything where one collision in 2^^32 is
328 acceptable. Do NOT use for cryptographic purposes.
329 -------------------------------------------------------------------------------
332 uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
334 uint32_t a,b,c; /* internal state */
335 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
337 /* Set up the internal state */
338 a = b = c = raninit + ((uint32_t)length) + initval;
341 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
342 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
343 #ifdef ARRAY_CLEAN_ACCESS
347 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
358 /*----------------------------- handle the last (probably partial) block */
360 * "k[2]&0xffffff" actually reads beyond the end of the string, but
361 * then masks off the part it's not allowed to read. Because the
362 * string is aligned, the masked-off tail is in the same word as the
363 * rest of the string. Every machine with memory protection I've seen
364 * does it on word boundaries, so is OK with this. But VALGRIND will
365 * still catch it and complain. The masking trick does make the hash
366 * noticeably faster for short strings (like English words).
368 #ifndef ARRAY_CLEAN_ACCESS
372 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
373 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
374 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
375 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
376 case 8 : b+=k[1]; a+=k[0]; break;
377 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
378 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
379 case 5 : b+=k[1]&0xff; a+=k[0]; break;
380 case 4 : a+=k[0]; break;
381 case 3 : a+=k[0]&0xffffff; break;
382 case 2 : a+=k[0]&0xffff; break;
383 case 1 : a+=k[0]&0xff; break;
384 case 0 : return c; /* zero length strings require no mixing */
387 #else /* make valgrind happy */
389 k8 = (const uint8_t *)k;
392 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
393 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
394 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
395 case 9 : c+=k8[8]; /* fall through */
396 case 8 : b+=k[1]; a+=k[0]; break;
397 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
398 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
399 case 5 : b+=k8[4]; /* fall through */
400 case 4 : a+=k[0]; break;
401 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
402 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
403 case 1 : a+=k8[0]; break;
407 #endif /* !valgrind */
409 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
410 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
413 /*--------------- all but last block: aligned reads and different mixing */
416 a += k[0] + (((uint32_t)k[1])<<16);
417 b += k[2] + (((uint32_t)k[3])<<16);
418 c += k[4] + (((uint32_t)k[5])<<16);
424 /*----------------------------- handle the last (probably partial) block */
425 k8 = (const uint8_t *)k;
428 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
429 b+=k[2]+(((uint32_t)k[3])<<16);
430 a+=k[0]+(((uint32_t)k[1])<<16);
432 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
434 b+=k[2]+(((uint32_t)k[3])<<16);
435 a+=k[0]+(((uint32_t)k[1])<<16);
437 case 9 : c+=k8[8]; /* fall through */
438 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
439 a+=k[0]+(((uint32_t)k[1])<<16);
441 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
443 a+=k[0]+(((uint32_t)k[1])<<16);
445 case 5 : b+=k8[4]; /* fall through */
446 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
448 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
453 case 0 : return c; /* zero length requires no mixing */
456 } else { /* need to read the key one byte at a time */
457 const uint8_t *k = (const uint8_t *)key;
459 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
463 a += ((uint32_t)k[1])<<8;
464 a += ((uint32_t)k[2])<<16;
465 a += ((uint32_t)k[3])<<24;
467 b += ((uint32_t)k[5])<<8;
468 b += ((uint32_t)k[6])<<16;
469 b += ((uint32_t)k[7])<<24;
471 c += ((uint32_t)k[9])<<8;
472 c += ((uint32_t)k[10])<<16;
473 c += ((uint32_t)k[11])<<24;
479 /*-------------------------------- last block: affect all 32 bits of (c) */
480 switch(length) /* all the case statements fall through */
482 case 12: c+=((uint32_t)k[11])<<24;
484 case 11: c+=((uint32_t)k[10])<<16;
486 case 10: c+=((uint32_t)k[9])<<8;
490 case 8 : b+=((uint32_t)k[7])<<24;
492 case 7 : b+=((uint32_t)k[6])<<16;
494 case 6 : b+=((uint32_t)k[5])<<8;
498 case 4 : a+=((uint32_t)k[3])<<24;
500 case 3 : a+=((uint32_t)k[2])<<16;
502 case 2 : a+=((uint32_t)k[1])<<8;
517 * hashlittle2: return 2 32-bit hash values
519 * This is identical to hashlittle(), except it returns two 32-bit hash
520 * values instead of just one. This is good enough for hash table
521 * lookup with 2^^64 buckets, or if you want a second hash if you're not
522 * happy with the first, or if you want a probably-unique 64-bit ID for
523 * the key. *pc is better mixed than *pb, so use *pc first. If you want
524 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
527 const void *key, /* the key to hash */
528 size_t length, /* length of the key */
529 uint32_t *pc, /* IN: primary initval, OUT: primary hash */
530 uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */
532 uint32_t a,b,c; /* internal state */
533 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
535 /* Set up the internal state */
536 a = b = c = raninit + ((uint32_t)length) + *pc;
540 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
541 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
546 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
557 /*----------------------------- handle the last (probably partial) block */
559 * "k[2]&0xffffff" actually reads beyond the end of the string, but
560 * then masks off the part it's not allowed to read. Because the
561 * string is aligned, the masked-off tail is in the same word as the
562 * rest of the string. Every machine with memory protection I've seen
563 * does it on word boundaries, so is OK with this. But VALGRIND will
564 * still catch it and complain. The masking trick does make the hash
565 * noticeably faster for short strings (like English words).
571 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
572 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
573 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
574 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
575 case 8 : b+=k[1]; a+=k[0]; break;
576 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
577 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
578 case 5 : b+=k[1]&0xff; a+=k[0]; break;
579 case 4 : a+=k[0]; break;
580 case 3 : a+=k[0]&0xffffff; break;
581 case 2 : a+=k[0]&0xffff; break;
582 case 1 : a+=k[0]&0xff; break;
583 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
586 #else /* make valgrind happy */
588 k8 = (const uint8_t *)k;
591 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
592 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
593 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
594 case 9 : c+=k8[8]; /* fall through */
595 case 8 : b+=k[1]; a+=k[0]; break;
596 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
597 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
598 case 5 : b+=k8[4]; /* fall through */
599 case 4 : a+=k[0]; break;
600 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
601 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
602 case 1 : a+=k8[0]; break;
603 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
606 #endif /* !valgrind */
608 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
609 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
612 /*--------------- all but last block: aligned reads and different mixing */
615 a += k[0] + (((uint32_t)k[1])<<16);
616 b += k[2] + (((uint32_t)k[3])<<16);
617 c += k[4] + (((uint32_t)k[5])<<16);
623 /*----------------------------- handle the last (probably partial) block */
624 k8 = (const uint8_t *)k;
627 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
628 b+=k[2]+(((uint32_t)k[3])<<16);
629 a+=k[0]+(((uint32_t)k[1])<<16);
631 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
633 b+=k[2]+(((uint32_t)k[3])<<16);
634 a+=k[0]+(((uint32_t)k[1])<<16);
636 case 9 : c+=k8[8]; /* fall through */
637 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
638 a+=k[0]+(((uint32_t)k[1])<<16);
640 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
642 a+=k[0]+(((uint32_t)k[1])<<16);
644 case 5 : b+=k8[4]; /* fall through */
645 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
647 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
652 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
655 } else { /* need to read the key one byte at a time */
656 const uint8_t *k = (const uint8_t *)key;
658 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
662 a += ((uint32_t)k[1])<<8;
663 a += ((uint32_t)k[2])<<16;
664 a += ((uint32_t)k[3])<<24;
666 b += ((uint32_t)k[5])<<8;
667 b += ((uint32_t)k[6])<<16;
668 b += ((uint32_t)k[7])<<24;
670 c += ((uint32_t)k[9])<<8;
671 c += ((uint32_t)k[10])<<16;
672 c += ((uint32_t)k[11])<<24;
678 /*-------------------------------- last block: affect all 32 bits of (c) */
679 switch(length) /* all the case statements fall through */
681 case 12: c+=((uint32_t)k[11])<<24;
682 case 11: c+=((uint32_t)k[10])<<16;
683 case 10: c+=((uint32_t)k[9])<<8;
685 case 8 : b+=((uint32_t)k[7])<<24;
686 case 7 : b+=((uint32_t)k[6])<<16;
687 case 6 : b+=((uint32_t)k[5])<<8;
689 case 4 : a+=((uint32_t)k[3])<<24;
690 case 3 : a+=((uint32_t)k[2])<<16;
691 case 2 : a+=((uint32_t)k[1])<<8;
694 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
702 #endif /* SELF_TEST */
704 #if 0 /* currently not used */
708 * This is the same as hashword() on big-endian machines. It is different
709 * from hashlittle() on all machines. hashbig() takes advantage of
710 * big-endian byte ordering.
712 uint32_t hashbig( const void *key, size_t length, uint32_t initval)
715 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
717 /* Set up the internal state */
718 a = b = c = raninit + ((uint32_t)length) + initval;
721 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
722 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
727 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
738 /*----------------------------- handle the last (probably partial) block */
740 * "k[2]<<8" actually reads beyond the end of the string, but
741 * then shifts out the part it's not allowed to read. Because the
742 * string is aligned, the illegal read is in the same word as the
743 * rest of the string. Every machine with memory protection I've seen
744 * does it on word boundaries, so is OK with this. But VALGRIND will
745 * still catch it and complain. The masking trick does make the hash
746 * noticeably faster for short strings (like English words).
752 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
753 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
754 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
755 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
756 case 8 : b+=k[1]; a+=k[0]; break;
757 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
758 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
759 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
760 case 4 : a+=k[0]; break;
761 case 3 : a+=k[0]&0xffffff00; break;
762 case 2 : a+=k[0]&0xffff0000; break;
763 case 1 : a+=k[0]&0xff000000; break;
764 case 0 : return c; /* zero length strings require no mixing */
767 #else /* make valgrind happy */
769 k8 = (const uint8_t *)k;
770 switch(length) /* all the case statements fall through */
772 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
773 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
774 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
775 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
776 case 8 : b+=k[1]; a+=k[0]; break;
777 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
778 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
779 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
780 case 4 : a+=k[0]; break;
781 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
782 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
783 case 1 : a+=((uint32_t)k8[0])<<24; break;
787 #endif /* !VALGRIND */
789 } else { /* need to read the key one byte at a time */
790 const uint8_t *k = (const uint8_t *)key;
792 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
795 a += ((uint32_t)k[0])<<24;
796 a += ((uint32_t)k[1])<<16;
797 a += ((uint32_t)k[2])<<8;
798 a += ((uint32_t)k[3]);
799 b += ((uint32_t)k[4])<<24;
800 b += ((uint32_t)k[5])<<16;
801 b += ((uint32_t)k[6])<<8;
802 b += ((uint32_t)k[7]);
803 c += ((uint32_t)k[8])<<24;
804 c += ((uint32_t)k[9])<<16;
805 c += ((uint32_t)k[10])<<8;
806 c += ((uint32_t)k[11]);
812 /*-------------------------------- last block: affect all 32 bits of (c) */
813 switch(length) /* all the case statements fall through */
816 case 11: c+=((uint32_t)k[10])<<8;
817 case 10: c+=((uint32_t)k[9])<<16;
818 case 9 : c+=((uint32_t)k[8])<<24;
820 case 7 : b+=((uint32_t)k[6])<<8;
821 case 6 : b+=((uint32_t)k[5])<<16;
822 case 5 : b+=((uint32_t)k[4])<<24;
824 case 3 : a+=((uint32_t)k[2])<<8;
825 case 2 : a+=((uint32_t)k[1])<<16;
826 case 1 : a+=((uint32_t)k[0])<<24;
836 #endif /* 0 == currently not used */
840 /* used for timings */
849 for (i=0; i<256; ++i) buf[i] = 'x';
852 h = hashlittle(&buf[0],1,h);
855 if (z-a > 0) printf("time %d %.8x\n", z-a, h);
858 /* check that every input bit changes every output bit half the time */
865 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
866 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
867 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
868 uint32_t x[HASHSTATE],y[HASHSTATE];
871 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
872 for (hlen=0; hlen < MAXLEN; ++hlen)
875 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
877 for (j=0; j<8; ++j) /*------------------------ for each input bit, */
879 for (m=1; m<8; ++m) /*------------ for several possible initvals, */
881 for (l=0; l<HASHSTATE; ++l)
882 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
884 /*---- check that every output bit is affected by that input bit */
885 for (k=0; k<MAXPAIR; k+=2)
888 /* keys have one bit different */
889 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
890 /* have a and b be two keys differing in only one bit */
893 c[0] = hashlittle(a, hlen, m);
895 b[i] ^= ((k+1)>>(8-j));
896 d[0] = hashlittle(b, hlen, m);
897 /* check every bit is 1, 0, set, and not set at least once */
898 for (l=0; l<HASHSTATE; ++l)
901 f[l] &= ~(c[l]^d[l]);
906 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
913 printf("Some bit didn't change: ");
914 printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
915 e[0],f[0],g[0],h[0],x[0],y[0]);
916 printf("i %d j %d m %d len %d\n", i, j, m, hlen);
918 if (z==MAXPAIR) goto done;
925 printf("Mix success %2d bytes %2d initvals ",i,m);
926 printf("required %d trials\n", z/2);
932 /* Check for reading beyond the end of the buffer and alignment problems */
935 uint8_t buf[MAXLEN+20], *b;
937 uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
939 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
941 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
943 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
947 printf("Endianness. These lines should all be the same (for values filled in):\n");
948 printf("%.8x %.8x %.8x\n",
949 hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
950 hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
951 hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
953 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
954 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
955 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
956 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
957 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
958 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
959 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
961 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
962 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
963 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
964 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
965 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
966 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
967 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
969 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
970 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
971 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
972 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
973 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
974 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
975 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
977 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
978 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
979 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
980 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
981 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
982 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
983 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
986 /* check that hashlittle2 and hashlittle produce the same results */
988 hashlittle2(q, sizeof(q), &i, &j);
989 if (hashlittle(q, sizeof(q), 47) != i)
990 printf("hashlittle2 and hashlittle mismatch\n");
992 /* check that hashword2 and hashword produce the same results */
995 hashword2(&len, 1, &i, &j);
996 if (hashword(&len, 1, 47) != i)
997 printf("hashword2 and hashword mismatch %x %x\n",
998 i, hashword(&len, 1, 47));
1000 /* check hashlittle doesn't read before or after the ends of the string */
1001 for (h=0, b=buf+1; h<8; ++h, ++b)
1003 for (i=0; i<MAXLEN; ++i)
1006 for (j=0; j<i; ++j) *(b+j)=0;
1008 /* these should all be equal */
1009 ref = hashlittle(b, len, (uint32_t)1);
1012 x = hashlittle(b, len, (uint32_t)1);
1013 y = hashlittle(b, len, (uint32_t)1);
1014 if ((ref != x) || (ref != y))
1016 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
1023 /* check for problems with nulls */
1027 uint32_t h,i,state[HASHSTATE];
1031 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
1032 printf("These should all be different\n");
1033 for (i=0, h=0; i<8; ++i)
1035 h = hashlittle(buf, 0, h);
1036 printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
1043 driver1(); /* test that the key is hashed: used for timings */
1044 driver2(); /* test that whole key is hashed thoroughly */
1045 driver3(); /* test that nothing but the key is hashed */
1046 driver4(); /* test hashing multiple buffers (all buffers are null) */
1050 #endif /* SELF_TEST */