Branch data Line data Source code
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
89 : 0 : 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 : 0 : a = b = c = EFX_HASH_INITIAL_VALUE +
100 : 0 : (((uint32_t)count) * sizeof (uint32_t)) + init;
101 : :
102 : : /* Handle all but the last three dwords of the input */
103 [ # # ]: 0 : while (count > 3) {
104 : 0 : a += input[0];
105 : 0 : b += input[1];
106 : 0 : c += input[2];
107 : 0 : EFX_HASH_MIX(a, b, c);
108 : :
109 : 0 : count -= 3;
110 : 0 : input += 3;
111 : : }
112 : :
113 : : /* Handle the left-overs */
114 [ # # # # ]: 0 : switch (count) {
115 : 0 : case 3:
116 : 0 : c += input[2];
117 : : /* Fall-through */
118 : 0 : case 2:
119 : 0 : b += input[1];
120 : : /* Fall-through */
121 : 0 : case 1:
122 : 0 : a += input[0];
123 : 0 : EFX_HASH_FINALISE(a, b, c);
124 : 0 : break;
125 : :
126 : : case 0:
127 : : /* Should only get here if count parameter was zero */
128 : : break;
129 : : }
130 : :
131 : 0 : 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
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
221 : 0 : 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 : 0 : a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
232 : :
233 : : /* Handle all but the last twelve bytes of the input */
234 [ # # ]: 0 : while (length > 12) {
235 : 0 : a += ((uint32_t)input[0]);
236 : 0 : a += ((uint32_t)input[1]) << 8;
237 : 0 : a += ((uint32_t)input[2]) << 16;
238 : 0 : a += ((uint32_t)input[3]) << 24;
239 : 0 : b += ((uint32_t)input[4]);
240 : 0 : b += ((uint32_t)input[5]) << 8;
241 : 0 : b += ((uint32_t)input[6]) << 16;
242 : 0 : b += ((uint32_t)input[7]) << 24;
243 : 0 : c += ((uint32_t)input[8]);
244 : 0 : c += ((uint32_t)input[9]) << 8;
245 : 0 : c += ((uint32_t)input[10]) << 16;
246 : 0 : c += ((uint32_t)input[11]) << 24;
247 : 0 : EFX_HASH_MIX(a, b, c);
248 : 0 : length -= 12;
249 : 0 : input += 12;
250 : : }
251 : :
252 : : /* Handle the left-overs */
253 [ # # # # : 0 : switch (length) {
# # # # #
# # # # ]
254 : 0 : case 12:
255 : 0 : c += ((uint32_t)input[11]) << 24;
256 : : /* Fall-through */
257 : 0 : case 11:
258 : 0 : c += ((uint32_t)input[10]) << 16;
259 : : /* Fall-through */
260 : 0 : case 10:
261 : 0 : c += ((uint32_t)input[9]) << 8;
262 : : /* Fall-through */
263 : 0 : case 9:
264 : 0 : c += ((uint32_t)input[8]);
265 : : /* Fall-through */
266 : 0 : case 8:
267 : 0 : b += ((uint32_t)input[7]) << 24;
268 : : /* Fall-through */
269 : 0 : case 7:
270 : 0 : b += ((uint32_t)input[6]) << 16;
271 : : /* Fall-through */
272 : 0 : case 6:
273 : 0 : b += ((uint32_t)input[5]) << 8;
274 : : /* Fall-through */
275 : 0 : case 5:
276 : 0 : b += ((uint32_t)input[4]);
277 : : /* Fall-through */
278 : 0 : case 4:
279 : 0 : a += ((uint32_t)input[3]) << 24;
280 : : /* Fall-through */
281 : 0 : case 3:
282 : 0 : a += ((uint32_t)input[2]) << 16;
283 : : /* Fall-through */
284 : 0 : case 2:
285 : 0 : a += ((uint32_t)input[1]) << 8;
286 : : /* Fall-through */
287 : 0 : case 1:
288 : 0 : a += ((uint32_t)input[0]);
289 : 0 : EFX_HASH_FINALISE(a, b, c);
290 : 0 : break;
291 : :
292 : : case 0:
293 : : /* Should only get here if length parameter was zero */
294 : : break;
295 : : }
296 : :
297 : 0 : return (c);
298 : : }
299 : :
300 : : #else
301 : :
302 : : #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"
303 : :
304 : : #endif
|