Branch data Line data Source code
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 : : */
121 : 0 : static inline uint32_t hashword(const uint32_t *k,
122 : : size_t length,
123 : : uint32_t initval) {
124 : : uint32_t a, b, c;
125 : 0 : int index = length - 1;
126 : :
127 : : /* Set up the internal state */
128 : 0 : a = 0xdeadbeef + (((uint32_t)length) << 2) + initval;
129 : : b = a;
130 : : c = a;
131 : :
132 : : /*-------------------------------------------- handle most of the key */
133 [ # # ]: 0 : while (length > 3) {
134 : 0 : a += k[index];
135 : 0 : b += k[index - 1];
136 : 0 : c += k[index - 2];
137 : 0 : mix(a, b, c);
138 : 0 : length -= 3;
139 : 0 : index -= 3;
140 : : }
141 : :
142 : : /*-------------------------------------- handle the last 3 uint32_t's */
143 [ # # # # ]: 0 : switch (length) { /* all the case statements fall through */
144 : 0 : case 3:
145 : 0 : c += k[index - 2];
146 : : /* Falls through. */
147 : 0 : case 2:
148 : 0 : b += k[index - 1];
149 : : /* Falls through. */
150 : 0 : case 1:
151 : 0 : a += k[index];
152 : 0 : final(a, b, c);
153 : : /* Falls through. */
154 : : case 0: /* case 0: nothing left to add */
155 : : break;
156 : : }
157 : : /*------------------------------------------------- report the result */
158 : 0 : return c;
159 : : }
160 : : #endif /* _LOOKUP3_H_ */
|