2 * Seccomp Library hash code
4 * Release under the Public Domain
5 * Author: Bob Jenkins <bob_jenkins@burtleburtle.net>
9 * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
11 * These are functions for producing 32-bit hashes for hash table lookup.
12 * jhash_word(), jhash_le(), jhash_be(), mix(), and final() are externally useful
13 * functions. Routines to test the hash are included if SELF_TEST is defined.
14 * You can use this free for any purpose. It's in the public domain. It has
17 * You probably want to use jhash_le(). jhash_le() and jhash_be() hash byte
18 * arrays. jhash_le() is is faster than jhash_be() on little-endian machines.
19 * Intel and AMD are little-endian machines.
21 * If you want to find a hash of, say, exactly 7 integers, do
22 * a = i1; b = i2; c = i3;
24 * a += i4; b += i5; c += i6;
29 * then use c as the hash value. If you have a variable length array of
30 * 4-byte integers to hash, use jhash_word(). If you have a byte array (like
31 * a character string), use jhash_le(). If you have several byte arrays, or
32 * a mix of things, see the comments above jhash_le().
34 * Why is this so big? I read 12 bytes at a time into 3 4-byte integers, then
35 * mix those integers. This is fast (you can do a lot more thorough mixing
36 * with 12*3 instructions on 3 integers than you can with 3 instructions on 1
37 * byte), but shoehorning those bytes into integers efficiently is messy.
45 #define hashsize(n) ((uint32_t)1<<(n))
46 #define hashmask(n) (hashsize(n)-1)
47 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
50 * Mix 3 32-bit values reversibly
51 * @param a 32-bit value
52 * @param b 32-bit value
53 * @param c 32-bit value
55 * This is reversible, so any information in (a,b,c) before mix() is still
56 * in (a,b,c) after mix().
58 * If four pairs of (a,b,c) inputs are run through mix(), or through mix() in
59 * reverse, there are at least 32 bits of the output that are sometimes the
60 * same for one pair and different for another pair.
62 * This was tested for:
63 * - pairs that differed by one bit, by two bits, in any combination of top
64 * bits of (a,b,c), or in any combination of bottom bits of (a,b,c).
65 * - "differ" is defined as +, -, ^, or ~^. For + and -, I transformed the
66 * output delta to a Gray code (a^(a>>1)) so a string of 1's (as is commonly
67 * produced by subtraction) look like a single 1-bit difference.
68 * - the base values were pseudorandom, all zero but one bit set, or all zero
69 * plus a counter that starts at zero.
71 * Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
77 * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing for "differ"
78 * defined as + with a one-bit base and a two-bit delta. I used
79 * http://burtleburtle.net/bob/hash/avalanche.html to choose the operations,
80 * constants, and arrangements of the variables.
82 * This does not achieve avalanche. There are input bits of (a,b,c) that fail
83 * to affect some output bits of (a,b,c), especially of a. The most thoroughly
84 * mixed value is c, but it doesn't really even achieve avalanche in c.
86 * This allows some parallelism. Read-after-writes are good at doubling the
87 * number of bits affected, so the goal of mixing pulls in the opposite
88 * direction as the goal of parallelism. I did what I could. Rotates seem to
89 * cost as much as shifts on every machine I could lay my hands on, and rotates
90 * are much kinder to the top and bottom bits, so I used rotates.
95 a -= c; a ^= rot(c, 4); c += b; \
96 b -= a; b ^= rot(a, 6); a += c; \
97 c -= b; c ^= rot(b, 8); b += a; \
98 a -= c; a ^= rot(c,16); c += b; \
99 b -= a; b ^= rot(a,19); a += c; \
100 c -= b; c ^= rot(b, 4); b += a; \
104 * Final mixing of 3 32-bit values (a,b,c) into c
105 * @param a 32-bit value
106 * @param b 32-bit value
107 * @param c 32-bit value
109 * Pairs of (a,b,c) values differing in only a few bits will usually produce
110 * values of c that look totally different. This was tested for:
111 * - pairs that differed by one bit, by two bits, in any combination of top
112 * bits of (a,b,c), or in any combination of bottom bits of (a,b,c).
113 * - "differ" is defined as +, -, ^, or ~^. For + and -, I transformed the
114 * output delta to a Gray code (a^(a>>1)) so a string of 1's (as is commonly
115 * produced by subtraction) look like a single 1-bit difference.
116 * - the base values were pseudorandom, all zero but one bit set, or all zero
117 * plus a counter that starts at zero.
119 * These constants passed:
120 * 14 11 25 16 4 14 24
121 * 12 14 25 16 4 14 24
122 * and these came close:
128 #define final(a,b,c) \
130 c ^= b; c -= rot(b,14); \
131 a ^= c; a -= rot(c,11); \
132 b ^= a; b -= rot(a,25); \
133 c ^= b; c -= rot(b,16); \
134 a ^= c; a -= rot(c,4); \
135 b ^= a; b -= rot(a,14); \
136 c ^= b; c -= rot(b,24); \
140 * Hash an array of 32-bit values
141 * @param k the key, an array of uint32_t values
142 * @param length the number of array elements
143 * @param initval the previous hash, or an arbitrary value
145 * This works on all machines. To be useful, it requires:
146 * - that the key be an array of uint32_t's, and
147 * - that the length be the number of uint32_t's in the key
149 * The function jhash_word() is identical to jhash_le() on little-endian
150 * machines, and identical to jhash_be() on big-endian machines, except that
151 * the length has to be measured in uint32_ts rather than in bytes. jhash_le()
152 * is more complicated than jhash_word() only because jhash_le() has to dance
153 * around fitting the key bytes into registers.
156 static uint32_t jhash_word(const uint32_t *k
, size_t length
, uint32_t initval
)
160 /* set up the internal state */
161 a
= b
= c
= 0xdeadbeef + (((uint32_t)length
) << 2) + initval
;
163 /* handle most of the key */
173 /* handle the last 3 uint32_t's */
183 /* nothing left to add */
191 * Hash a variable-length key into a 32-bit value
192 * @param key the key (the unaligned variable-length array of bytes)
193 * @param length the length of the key, counting by bytes
194 * @param initval can be any 4-byte value
196 * Returns a 32-bit value. Every bit of the key affects every bit of the
197 * return value. Two keys differing by one or two bits will have totally
198 * different hash values.
200 * The best hash table sizes are powers of 2. There is no need to do mod a
201 * prime (mod is sooo slow!). If you need less than 32 bits, use a bitmask.
202 * For example, if you need only 10 bits, do:
203 * h = (h & hashmask(10));
204 * In which case, the hash table should have hashsize(10) elements.
206 * If you are hashing n strings (uint8_t **)k, do it like this:
207 * for (i=0, h=0; i<n; ++i) h = jhash_le( k[i], len[i], h);
210 static uint32_t jhash_le(const void *key
, size_t length
, uint32_t initval
)
216 } u
; /* needed for Mac Powerbook G4 */
218 /* set up the internal state */
219 a
= b
= c
= 0xdeadbeef + ((uint32_t)length
) + initval
;
222 if ((arch_def_native
->endian
== ARCH_ENDIAN_LITTLE
) &&
223 ((u
.i
& 0x3) == 0)) {
224 /* read 32-bit chunks */
225 const uint32_t *k
= (const uint32_t *)key
;
227 while (length
> 12) {
236 /* "k[2]&0xffffff" actually reads beyond the end of the string,
237 * but then masks off the part it's not allowed to read.
238 * Because the string is aligned, the masked-off tail is in the
239 * same word as the rest of the string. Every machine with
240 * memory protection I've seen does it on word boundaries, so
241 * is OK with this. But VALGRIND will still catch it and
242 * complain. The masking trick does make the hash noticably
243 * faster for short strings (like English words). */
253 c
+= k
[2] & 0xffffff;
272 b
+= k
[1] & 0xffffff;
287 a
+= k
[0] & 0xffffff;
296 /* zero length strings require no mixing */
300 #else /* make valgrind happy */
302 k8
= (const uint8_t *)k
;
310 c
+= ((uint32_t)k8
[10]) << 16;
312 c
+= ((uint32_t)k8
[9]) << 8;
320 b
+= ((uint32_t)k8
[6]) << 16;
322 b
+= ((uint32_t)k8
[5]) << 8;
329 a
+= ((uint32_t)k8
[2]) << 16;
331 a
+= ((uint32_t)k8
[1]) << 8;
339 #endif /* !valgrind */
341 } else if ((arch_def_native
->endian
== ARCH_ENDIAN_LITTLE
) &&
342 ((u
.i
& 0x1) == 0)) {
343 /* read 16-bit chunks */
344 const uint16_t *k
= (const uint16_t *)key
;
347 while (length
> 12) {
348 a
+= k
[0] + (((uint32_t)k
[1]) << 16);
349 b
+= k
[2] + (((uint32_t)k
[3]) << 16);
350 c
+= k
[4] + (((uint32_t)k
[5]) << 16);
356 k8
= (const uint8_t *)k
;
359 c
+= k
[4] + (((uint32_t)k
[5]) << 16);
360 b
+= k
[2] + (((uint32_t)k
[3]) << 16);
361 a
+= k
[0] + (((uint32_t)k
[1]) << 16);
364 c
+= ((uint32_t)k8
[10]) << 16;
367 b
+= k
[2] + (((uint32_t)k
[3]) << 16);
368 a
+= k
[0] + (((uint32_t)k
[1]) << 16);
373 b
+= k
[2] + (((uint32_t)k
[3]) << 16);
374 a
+= k
[0] + (((uint32_t)k
[1]) << 16);
377 b
+= ((uint32_t)k8
[6]) << 16;
380 a
+= k
[0] + (((uint32_t)k
[1]) << 16);
385 a
+= k
[0] + (((uint32_t)k
[1]) << 16);
388 a
+= ((uint32_t)k8
[2]) << 16;
396 /* zero length requires no mixing */
401 /* need to read the key one byte at a time */
402 const uint8_t *k
= (const uint8_t *)key
;
404 while (length
> 12) {
406 a
+= ((uint32_t)k
[1]) << 8;
407 a
+= ((uint32_t)k
[2]) << 16;
408 a
+= ((uint32_t)k
[3]) << 24;
410 b
+= ((uint32_t)k
[5]) << 8;
411 b
+= ((uint32_t)k
[6]) << 16;
412 b
+= ((uint32_t)k
[7]) << 24;
414 c
+= ((uint32_t)k
[9]) << 8;
415 c
+= ((uint32_t)k
[10]) << 16;
416 c
+= ((uint32_t)k
[11]) << 24;
424 c
+= ((uint32_t)k
[11]) << 24;
426 c
+= ((uint32_t)k
[10]) << 16;
428 c
+= ((uint32_t)k
[9]) << 8;
432 b
+= ((uint32_t)k
[7]) << 24;
434 b
+= ((uint32_t)k
[6]) << 16;
436 b
+= ((uint32_t)k
[5]) << 8;
440 a
+= ((uint32_t)k
[3]) << 24;
442 a
+= ((uint32_t)k
[2]) << 16;
444 a
+= ((uint32_t)k
[1]) << 8;
458 * Hash a variable-length key into a 32-bit value
459 * @param key the key (the unaligned variable-length array of bytes)
460 * @param length the length of the key, counting by bytes
461 * @param initval can be any 4-byte value
463 * This is the same as jhash_word() on big-endian machines. It is different
464 * from jhash_le() on all machines. jhash_be() takes advantage of big-endian
468 static uint32_t jhash_be( const void *key
, size_t length
, uint32_t initval
)
474 } u
; /* to cast key to (size_t) happily */
476 /* set up the internal state */
477 a
= b
= c
= 0xdeadbeef + ((uint32_t)length
) + initval
;
480 if ((arch_def_native
->endian
== ARCH_ENDIAN_BIG
) &&
481 ((u
.i
& 0x3) == 0)) {
482 /* read 32-bit chunks */
483 const uint32_t *k
= (const uint32_t *)key
;
485 while (length
> 12) {
494 /* "k[2]<<8" actually reads beyond the end of the string, but
495 * then shifts out the part it's not allowed to read. Because
496 * the string is aligned, the illegal read is in the same word
497 * as the rest of the string. Every machine with memory
498 * protection I've seen does it on word boundaries, so is OK
499 * with this. But VALGRIND will still catch it and complain.
500 * The masking trick does make the hash noticably faster for
501 * short strings (like English words). */
511 c
+= k
[2] & 0xffffff00;
516 c
+= k
[2] & 0xffff0000;
521 c
+= k
[2] & 0xff000000;
530 b
+= k
[1] & 0xffffff00;
534 b
+= k
[1] & 0xffff0000;
538 b
+= k
[1] & 0xff000000;
545 a
+= k
[0] & 0xffffff00;
548 a
+= k
[0] & 0xffff0000;
551 a
+= k
[0] & 0xff000000;
554 /* zero length strings require no mixing */
558 #else /* make valgrind happy */
560 k8
= (const uint8_t *)k
;
568 c
+= ((uint32_t)k8
[10]) << 8;
570 c
+= ((uint32_t)k8
[9]) << 16;
572 c
+= ((uint32_t)k8
[8]) << 24;
578 b
+= ((uint32_t)k8
[6]) << 8;
580 b
+= ((uint32_t)k8
[5]) << 16;
582 b
+= ((uint32_t)k8
[4]) << 24;
587 a
+= ((uint32_t)k8
[2]) << 8;
589 a
+= ((uint32_t)k8
[1]) << 16;
591 a
+= ((uint32_t)k8
[0]) << 24;
597 #endif /* !VALGRIND */
600 /* need to read the key one byte at a time */
601 const uint8_t *k
= (const uint8_t *)key
;
603 while (length
> 12) {
604 a
+= ((uint32_t)k
[0]) << 24;
605 a
+= ((uint32_t)k
[1]) << 16;
606 a
+= ((uint32_t)k
[2]) << 8;
607 a
+= ((uint32_t)k
[3]);
608 b
+= ((uint32_t)k
[4]) << 24;
609 b
+= ((uint32_t)k
[5]) << 16;
610 b
+= ((uint32_t)k
[6]) << 8;
611 b
+= ((uint32_t)k
[7]);
612 c
+= ((uint32_t)k
[8]) << 24;
613 c
+= ((uint32_t)k
[9]) << 16;
614 c
+= ((uint32_t)k
[10]) << 8;
615 c
+= ((uint32_t)k
[11]);
625 c
+= ((uint32_t)k
[10]) << 8;
627 c
+= ((uint32_t)k
[9]) << 16;
629 c
+= ((uint32_t)k
[8]) << 24;
633 b
+= ((uint32_t)k
[6]) << 8;
635 b
+= ((uint32_t)k
[5]) << 16;
637 b
+= ((uint32_t)k
[4]) << 24;
641 a
+= ((uint32_t)k
[2]) << 8;
643 a
+= ((uint32_t)k
[1]) << 16;
645 a
+= ((uint32_t)k
[0]) << 24;
657 * Hash a variable-length key into a 32-bit value
658 * @param key the key (the unaligned variable-length array of bytes)
659 * @param length the length of the key, counting by bytes
660 * @param initval can be any 4-byte value
662 * A small wrapper function that selects the proper hash function based on the
663 * native machine's byte-ordering.
666 uint32_t jhash(const void *key
, size_t length
, uint32_t initval
)
668 if (length
% sizeof(uint32_t) == 0)
669 return jhash_word(key
, (length
/ sizeof(uint32_t)), initval
);
670 else if (arch_def_native
->endian
== ARCH_ENDIAN_BIG
)
671 return jhash_be(key
, length
, initval
);
673 return jhash_le(key
, length
, initval
);
This page took 0.041664 seconds and 4 git commands to generate.