1 /* SPDX-License-Identifier: BSD-3-Clause
2 *
3 * Based on lookup3.c, by Bob Jenkins, May 2006, Public Domain.
4 * http://www.burtleburtle.net/bob/c/lookup3.c
5 *
6 * These functions for producing 32-bit hashes for has table lookup.
7 * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
8 * are externally useful functions. Routines to test the hash are included
9 * if SELF_TEST is defined. You can use this free for any purpose. It is in
10 * the public domain. It has no warranty.
11 */
12
13 #ifndef _LOOKUP3_H_
14 #define _LOOKUP3_H_
15
16 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
17
18 /** -------------------------------------------------------------------------
19 * This is reversible, so any information in (a,b,c) before mix() is
20 * still in (a,b,c) after mix().
21 *
22 * If four pairs of (a,b,c) inputs are run through mix(), or through
23 * mix() in reverse, there are at least 32 bits of the output that
24 * are sometimes the same for one pair and different for another pair.
25 * This was tested for:
26 * pairs that differed by one bit, by two bits, in any combination
27 * of top bits of (a,b,c), or in any combination of bottom bits of
28 * (a,b,c).
29 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
30 * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
31 * is commonly produced by subtraction) look like a single 1-bit
32 * difference.
33 * the base values were pseudorandom, all zero but one bit set, or
34 * all zero plus a counter that starts at zero.
35 *
36 * Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
37 * satisfy this are
38 * 4 6 8 16 19 4
39 * 9 15 3 18 27 15
40 * 14 9 3 7 17 3
41 * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
42 * for "differ" defined as + with a one-bit base and a two-bit delta. I
43 * used http://burtleburtle.net/bob/hash/avalanche.html to choose
44 * the operations, constants, and arrangements of the variables.
45 *
46 * This does not achieve avalanche. There are input bits of (a,b,c)
47 * that fail to affect some output bits of (a,b,c), especially of a. The
48 * most thoroughly mixed value is c, but it doesn't really even achieve
49 * avalanche in c.
50 *
51 * This allows some parallelism. Read-after-writes are good at doubling
52 * the number of bits affected, so the goal of mixing pulls in the opposite
53 * direction as the goal of parallelism. I did what I could. Rotates
54 * seem to cost as much as shifts on every machine I could lay my hands
55 * on, and rotates are much kinder to the top and bottom bits, so I used
56 * rotates.
57 * --------------------------------------------------------------------------
58 */
59 #define mix(a, b, c) \
60 { \
61 (a) -= (c); (a) ^= rot((c), 4); (c) += b; \
62 (b) -= (a); (b) ^= rot((a), 6); (a) += c; \
63 (c) -= (b); (c) ^= rot((b), 8); (b) += a; \
64 (a) -= (c); (a) ^= rot((c), 16); (c) += b; \
65 (b) -= (a); (b) ^= rot((a), 19); (a) += c; \
66 (c) -= (b); (c) ^= rot((b), 4); (b) += a; \
67 }
68
69 /** --------------------------------------------------------------------------
70 * final -- final mixing of 3 32-bit values (a,b,c) into c
71 *
72 * Pairs of (a,b,c) values differing in only a few bits will usually
73 * produce values of c that look totally different. This was tested for
74 * pairs that differed by one bit, by two bits, in any combination
75 * of top bits of (a,b,c), or in any combination of bottom bits of
76 * (a,b,c).
77 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
78 * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
79 * is commonly produced by subtraction) look like a single 1-bit
80 * difference.
81 * the base values were pseudorandom, all zero but one bit set, or
82 * all zero plus a counter that starts at zero.
83 *
84 * These constants passed:
85 * 14 11 25 16 4 14 24
86 * 12 14 25 16 4 14 24
87 * and these came close:
88 * 4 8 15 26 3 22 24
89 * 10 8 15 26 3 22 24
90 * 11 8 15 26 3 22 24
91 * --------------------------------------------------------------------------
92 */
93 #define final(a, b, c) \
94 { \
95 (c) ^= (b); (c) -= rot((b), 14); \
96 (a) ^= (c); (a) -= rot((c), 11); \
97 (b) ^= (a); (b) -= rot((a), 25); \
98 (c) ^= (b); (c) -= rot((b), 16); \
99 (a) ^= (c); (a) -= rot((c), 4); \
100 (b) ^= (a); (b) -= rot((a), 14); \
101 (c) ^= (b); (c) -= rot((b), 24); \
102 }
103
104 /** --------------------------------------------------------------------
105 * This works on all machines. To be useful, it requires
106 * -- that the key be an array of uint32_t's, and
107 * -- that the length be the number of uint32_t's in the key
108
109 * The function hashword() is identical to hashlittle() on little-endian
110 * machines, and identical to hashbig() on big-endian machines,
111 * except that the length has to be measured in uint32_ts rather than in
112 * bytes. hashlittle() is more complicated than hashword() only because
113 * hashlittle() has to dance around fitting the key bytes into registers.
114 *
115 * Input Parameters:
116 * key: an array of uint32_t values
117 * length: the length of the key, in uint32_ts
118 * initval: the previous hash, or an arbitrary value
119 * --------------------------------------------------------------------
120 */
hashword(const uint32_t * k,size_t length,uint32_t initval)121 static inline uint32_t hashword(const uint32_t *k,
122 size_t length,
123 uint32_t initval) {
124 uint32_t a, b, c;
125 int index = length - 1;
126
127 /* Set up the internal state */
128 a = 0xdeadbeef + (((uint32_t)length) << 2) + initval;
129 b = a;
130 c = a;
131
132 /*-------------------------------------------- handle most of the key */
133 while (length > 3) {
134 a += k[index];
135 b += k[index - 1];
136 c += k[index - 2];
137 mix(a, b, c);
138 length -= 3;
139 index -= 3;
140 }
141
142 /*-------------------------------------- handle the last 3 uint32_t's */
143 switch (length) { /* all the case statements fall through */
144 case 3:
145 c += k[index - 2];
146 /* Falls through. */
147 case 2:
148 b += k[index - 1];
149 /* Falls through. */
150 case 1:
151 a += k[index];
152 final(a, b, c);
153 /* Falls through. */
154 case 0: /* case 0: nothing left to add */
155 break;
156 }
157 /*------------------------------------------------- report the result */
158 return c;
159 }
160 #endif /* _LOOKUP3_H_ */
161