1 /* SPDX-License-Identifier: BSD-3-Clause
2 *
3 * Copyright(c) 2019-2021 Xilinx, Inc.
4 * Copyright(c) 2014-2019 Solarflare Communications Inc.
5 *
6 * Copyright 2006 Bob Jenkins
7 *
8 * Derived from public domain source, see
9 * <http://burtleburtle.net/bob/c/lookup3.c>:
10 *
11 * "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
12 *
13 * These are functions for producing 32-bit hashes for hash table lookup...
14 * ...You can use this free for any purpose. It's in the public domain.
15 * It has no warranty."
16 */
17
18 #include "efx.h"
19 #include "efx_impl.h"
20
21 /* Hash initial value */
22 #define EFX_HASH_INITIAL_VALUE 0xdeadbeef
23
24 /*
25 * Rotate a 32-bit value left
26 *
27 * Allow platform to provide an intrinsic or optimised routine and
28 * fall-back to a simple shift based implementation.
29 */
30 #if EFSYS_HAS_ROTL_DWORD
31
32 #define EFX_HASH_ROTATE(_value, _shift) \
33 EFSYS_ROTL_DWORD(_value, _shift)
34
35 #else
36
37 #define EFX_HASH_ROTATE(_value, _shift) \
38 (((_value) << (_shift)) | ((_value) >> (32 - (_shift))))
39
40 #endif
41
42 /* Mix three 32-bit values reversibly */
43 #define EFX_HASH_MIX(_a, _b, _c) \
44 do { \
45 _a -= _c; \
46 _a ^= EFX_HASH_ROTATE(_c, 4); \
47 _c += _b; \
48 _b -= _a; \
49 _b ^= EFX_HASH_ROTATE(_a, 6); \
50 _a += _c; \
51 _c -= _b; \
52 _c ^= EFX_HASH_ROTATE(_b, 8); \
53 _b += _a; \
54 _a -= _c; \
55 _a ^= EFX_HASH_ROTATE(_c, 16); \
56 _c += _b; \
57 _b -= _a; \
58 _b ^= EFX_HASH_ROTATE(_a, 19); \
59 _a += _c; \
60 _c -= _b; \
61 _c ^= EFX_HASH_ROTATE(_b, 4); \
62 _b += _a; \
63 _NOTE(CONSTANTCONDITION) \
64 } while (B_FALSE)
65
66 /* Final mixing of three 32-bit values into one (_c) */
67 #define EFX_HASH_FINALISE(_a, _b, _c) \
68 do { \
69 _c ^= _b; \
70 _c -= EFX_HASH_ROTATE(_b, 14); \
71 _a ^= _c; \
72 _a -= EFX_HASH_ROTATE(_c, 11); \
73 _b ^= _a; \
74 _b -= EFX_HASH_ROTATE(_a, 25); \
75 _c ^= _b; \
76 _c -= EFX_HASH_ROTATE(_b, 16); \
77 _a ^= _c; \
78 _a -= EFX_HASH_ROTATE(_c, 4); \
79 _b ^= _a; \
80 _b -= EFX_HASH_ROTATE(_a, 14); \
81 _c ^= _b; \
82 _c -= EFX_HASH_ROTATE(_b, 24); \
83 _NOTE(CONSTANTCONDITION) \
84 } while (B_FALSE)
85
86
87 /* Produce a 32-bit hash from 32-bit aligned input */
88 __checkReturn uint32_t
efx_hash_dwords(__in_ecount (count)uint32_t const * input,__in size_t count,__in uint32_t init)89 efx_hash_dwords(
90 __in_ecount(count) uint32_t const *input,
91 __in size_t count,
92 __in uint32_t init)
93 {
94 uint32_t a;
95 uint32_t b;
96 uint32_t c;
97
98 /* Set up the initial internal state */
99 a = b = c = EFX_HASH_INITIAL_VALUE +
100 (((uint32_t)count) * sizeof (uint32_t)) + init;
101
102 /* Handle all but the last three dwords of the input */
103 while (count > 3) {
104 a += input[0];
105 b += input[1];
106 c += input[2];
107 EFX_HASH_MIX(a, b, c);
108
109 count -= 3;
110 input += 3;
111 }
112
113 /* Handle the left-overs */
114 switch (count) {
115 case 3:
116 c += input[2];
117 /* Fall-through */
118 case 2:
119 b += input[1];
120 /* Fall-through */
121 case 1:
122 a += input[0];
123 EFX_HASH_FINALISE(a, b, c);
124 break;
125
126 case 0:
127 /* Should only get here if count parameter was zero */
128 break;
129 }
130
131 return (c);
132 }
133
134 #if EFSYS_IS_BIG_ENDIAN
135
136 /* Produce a 32-bit hash from arbitrarily aligned input */
137 __checkReturn uint32_t
efx_hash_bytes(__in_ecount (length)uint8_t const * input,__in size_t length,__in uint32_t init)138 efx_hash_bytes(
139 __in_ecount(length) uint8_t const *input,
140 __in size_t length,
141 __in uint32_t init)
142 {
143 uint32_t a;
144 uint32_t b;
145 uint32_t c;
146
147 /* Set up the initial internal state */
148 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
149
150 /* Handle all but the last twelve bytes of the input */
151 while (length > 12) {
152 a += ((uint32_t)input[0]) << 24;
153 a += ((uint32_t)input[1]) << 16;
154 a += ((uint32_t)input[2]) << 8;
155 a += ((uint32_t)input[3]);
156 b += ((uint32_t)input[4]) << 24;
157 b += ((uint32_t)input[5]) << 16;
158 b += ((uint32_t)input[6]) << 8;
159 b += ((uint32_t)input[7]);
160 c += ((uint32_t)input[8]) << 24;
161 c += ((uint32_t)input[9]) << 16;
162 c += ((uint32_t)input[10]) << 8;
163 c += ((uint32_t)input[11]);
164 EFX_HASH_MIX(a, b, c);
165 length -= 12;
166 input += 12;
167 }
168
169 /* Handle the left-overs */
170 switch (length) {
171 case 12:
172 c += ((uint32_t)input[11]);
173 /* Fall-through */
174 case 11:
175 c += ((uint32_t)input[10]) << 8;
176 /* Fall-through */
177 case 10:
178 c += ((uint32_t)input[9]) << 16;
179 /* Fall-through */
180 case 9:
181 c += ((uint32_t)input[8]) << 24;
182 /* Fall-through */
183 case 8:
184 b += ((uint32_t)input[7]);
185 /* Fall-through */
186 case 7:
187 b += ((uint32_t)input[6]) << 8;
188 /* Fall-through */
189 case 6:
190 b += ((uint32_t)input[5]) << 16;
191 /* Fall-through */
192 case 5:
193 b += ((uint32_t)input[4]) << 24;
194 /* Fall-through */
195 case 4:
196 a += ((uint32_t)input[3]);
197 /* Fall-through */
198 case 3:
199 a += ((uint32_t)input[2]) << 8;
200 /* Fall-through */
201 case 2:
202 a += ((uint32_t)input[1]) << 16;
203 /* Fall-through */
204 case 1:
205 a += ((uint32_t)input[0]) << 24;
206 EFX_HASH_FINALISE(a, b, c);
207 break;
208
209 case 0:
210 /* Should only get here if length parameter was zero */
211 break;
212 }
213
214 return (c);
215 }
216
217 #elif EFSYS_IS_LITTLE_ENDIAN
218
219 /* Produce a 32-bit hash from arbitrarily aligned input */
220 __checkReturn uint32_t
efx_hash_bytes(__in_ecount (length)uint8_t const * input,__in size_t length,__in uint32_t init)221 efx_hash_bytes(
222 __in_ecount(length) uint8_t const *input,
223 __in size_t length,
224 __in uint32_t init)
225 {
226 uint32_t a;
227 uint32_t b;
228 uint32_t c;
229
230 /* Set up the initial internal state */
231 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
232
233 /* Handle all but the last twelve bytes of the input */
234 while (length > 12) {
235 a += ((uint32_t)input[0]);
236 a += ((uint32_t)input[1]) << 8;
237 a += ((uint32_t)input[2]) << 16;
238 a += ((uint32_t)input[3]) << 24;
239 b += ((uint32_t)input[4]);
240 b += ((uint32_t)input[5]) << 8;
241 b += ((uint32_t)input[6]) << 16;
242 b += ((uint32_t)input[7]) << 24;
243 c += ((uint32_t)input[8]);
244 c += ((uint32_t)input[9]) << 8;
245 c += ((uint32_t)input[10]) << 16;
246 c += ((uint32_t)input[11]) << 24;
247 EFX_HASH_MIX(a, b, c);
248 length -= 12;
249 input += 12;
250 }
251
252 /* Handle the left-overs */
253 switch (length) {
254 case 12:
255 c += ((uint32_t)input[11]) << 24;
256 /* Fall-through */
257 case 11:
258 c += ((uint32_t)input[10]) << 16;
259 /* Fall-through */
260 case 10:
261 c += ((uint32_t)input[9]) << 8;
262 /* Fall-through */
263 case 9:
264 c += ((uint32_t)input[8]);
265 /* Fall-through */
266 case 8:
267 b += ((uint32_t)input[7]) << 24;
268 /* Fall-through */
269 case 7:
270 b += ((uint32_t)input[6]) << 16;
271 /* Fall-through */
272 case 6:
273 b += ((uint32_t)input[5]) << 8;
274 /* Fall-through */
275 case 5:
276 b += ((uint32_t)input[4]);
277 /* Fall-through */
278 case 4:
279 a += ((uint32_t)input[3]) << 24;
280 /* Fall-through */
281 case 3:
282 a += ((uint32_t)input[2]) << 16;
283 /* Fall-through */
284 case 2:
285 a += ((uint32_t)input[1]) << 8;
286 /* Fall-through */
287 case 1:
288 a += ((uint32_t)input[0]);
289 EFX_HASH_FINALISE(a, b, c);
290 break;
291
292 case 0:
293 /* Should only get here if length parameter was zero */
294 break;
295 }
296
297 return (c);
298 }
299
300 #else
301
302 #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"
303
304 #endif
305