1 /*-
2 * Copyright 2006 Bob Jenkins
3 *
4 * Derived from public domain source, see
5 * <http://burtleburtle.net/bob/c/lookup3.c>:
6 *
7 * "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
8 *
9 * These are functions for producing 32-bit hashes for hash table lookup...
10 * ...You can use this free for any purpose. It's in the public domain.
11 * It has no warranty."
12 *
13 * Copyright (c) 2014-2016 Solarflare Communications Inc.
14 * All rights reserved.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions are met:
18 *
19 * 1. Redistributions of source code must retain the above copyright notice,
20 * this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright notice,
22 * this list of conditions and the following disclaimer in the documentation
23 * and/or other materials provided with the distribution.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
27 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
29 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
32 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
33 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
34 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
35 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * The views and conclusions contained in the software and documentation are
38 * those of the authors and should not be interpreted as representing official
39 * policies, either expressed or implied, of the FreeBSD Project.
40 */
41
42 #include <sys/cdefs.h>
43 #include "efx.h"
44 #include "efx_impl.h"
45
46 /* Hash initial value */
47 #define EFX_HASH_INITIAL_VALUE 0xdeadbeef
48
49 /*
50 * Rotate a 32-bit value left
51 *
52 * Allow platform to provide an intrinsic or optimised routine and
53 * fall-back to a simple shift based implementation.
54 */
55 #if EFSYS_HAS_ROTL_DWORD
56
57 #define EFX_HASH_ROTATE(_value, _shift) \
58 EFSYS_ROTL_DWORD(_value, _shift)
59
60 #else
61
62 #define EFX_HASH_ROTATE(_value, _shift) \
63 (((_value) << (_shift)) | ((_value) >> (32 - (_shift))))
64
65 #endif
66
67 /* Mix three 32-bit values reversibly */
68 #define EFX_HASH_MIX(_a, _b, _c) \
69 do { \
70 _a -= _c; \
71 _a ^= EFX_HASH_ROTATE(_c, 4); \
72 _c += _b; \
73 _b -= _a; \
74 _b ^= EFX_HASH_ROTATE(_a, 6); \
75 _a += _c; \
76 _c -= _b; \
77 _c ^= EFX_HASH_ROTATE(_b, 8); \
78 _b += _a; \
79 _a -= _c; \
80 _a ^= EFX_HASH_ROTATE(_c, 16); \
81 _c += _b; \
82 _b -= _a; \
83 _b ^= EFX_HASH_ROTATE(_a, 19); \
84 _a += _c; \
85 _c -= _b; \
86 _c ^= EFX_HASH_ROTATE(_b, 4); \
87 _b += _a; \
88 _NOTE(CONSTANTCONDITION) \
89 } while (B_FALSE)
90
91 /* Final mixing of three 32-bit values into one (_c) */
92 #define EFX_HASH_FINALISE(_a, _b, _c) \
93 do { \
94 _c ^= _b; \
95 _c -= EFX_HASH_ROTATE(_b, 14); \
96 _a ^= _c; \
97 _a -= EFX_HASH_ROTATE(_c, 11); \
98 _b ^= _a; \
99 _b -= EFX_HASH_ROTATE(_a, 25); \
100 _c ^= _b; \
101 _c -= EFX_HASH_ROTATE(_b, 16); \
102 _a ^= _c; \
103 _a -= EFX_HASH_ROTATE(_c, 4); \
104 _b ^= _a; \
105 _b -= EFX_HASH_ROTATE(_a, 14); \
106 _c ^= _b; \
107 _c -= EFX_HASH_ROTATE(_b, 24); \
108 _NOTE(CONSTANTCONDITION) \
109 } while (B_FALSE)
110
111 /* Produce a 32-bit hash from 32-bit aligned input */
112 __checkReturn uint32_t
efx_hash_dwords(__in_ecount (count)uint32_t const * input,__in size_t count,__in uint32_t init)113 efx_hash_dwords(
114 __in_ecount(count) uint32_t const *input,
115 __in size_t count,
116 __in uint32_t init)
117 {
118 uint32_t a;
119 uint32_t b;
120 uint32_t c;
121
122 /* Set up the initial internal state */
123 a = b = c = EFX_HASH_INITIAL_VALUE +
124 (((uint32_t)count) * sizeof (uint32_t)) + init;
125
126 /* Handle all but the last three dwords of the input */
127 while (count > 3) {
128 a += input[0];
129 b += input[1];
130 c += input[2];
131 EFX_HASH_MIX(a, b, c);
132
133 count -= 3;
134 input += 3;
135 }
136
137 /* Handle the left-overs */
138 switch (count) {
139 case 3:
140 c += input[2];
141 /* Fall-through */
142 case 2:
143 b += input[1];
144 /* Fall-through */
145 case 1:
146 a += input[0];
147 EFX_HASH_FINALISE(a, b, c);
148 break;
149
150 case 0:
151 /* Should only get here if count parameter was zero */
152 break;
153 }
154
155 return (c);
156 }
157
158 #if EFSYS_IS_BIG_ENDIAN
159
160 /* Produce a 32-bit hash from arbitrarily aligned input */
161 __checkReturn uint32_t
efx_hash_bytes(__in_ecount (length)uint8_t const * input,__in size_t length,__in uint32_t init)162 efx_hash_bytes(
163 __in_ecount(length) uint8_t const *input,
164 __in size_t length,
165 __in uint32_t init)
166 {
167 uint32_t a;
168 uint32_t b;
169 uint32_t c;
170
171 /* Set up the initial internal state */
172 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
173
174 /* Handle all but the last twelve bytes of the input */
175 while (length > 12) {
176 a += ((uint32_t)input[0]) << 24;
177 a += ((uint32_t)input[1]) << 16;
178 a += ((uint32_t)input[2]) << 8;
179 a += ((uint32_t)input[3]);
180 b += ((uint32_t)input[4]) << 24;
181 b += ((uint32_t)input[5]) << 16;
182 b += ((uint32_t)input[6]) << 8;
183 b += ((uint32_t)input[7]);
184 c += ((uint32_t)input[8]) << 24;
185 c += ((uint32_t)input[9]) << 16;
186 c += ((uint32_t)input[10]) << 8;
187 c += ((uint32_t)input[11]);
188 EFX_HASH_MIX(a, b, c);
189 length -= 12;
190 input += 12;
191 }
192
193 /* Handle the left-overs */
194 switch (length) {
195 case 12:
196 c += ((uint32_t)input[11]);
197 /* Fall-through */
198 case 11:
199 c += ((uint32_t)input[10]) << 8;
200 /* Fall-through */
201 case 10:
202 c += ((uint32_t)input[9]) << 16;
203 /* Fall-through */
204 case 9:
205 c += ((uint32_t)input[8]) << 24;
206 /* Fall-through */
207 case 8:
208 b += ((uint32_t)input[7]);
209 /* Fall-through */
210 case 7:
211 b += ((uint32_t)input[6]) << 8;
212 /* Fall-through */
213 case 6:
214 b += ((uint32_t)input[5]) << 16;
215 /* Fall-through */
216 case 5:
217 b += ((uint32_t)input[4]) << 24;
218 /* Fall-through */
219 case 4:
220 a += ((uint32_t)input[3]);
221 /* Fall-through */
222 case 3:
223 a += ((uint32_t)input[2]) << 8;
224 /* Fall-through */
225 case 2:
226 a += ((uint32_t)input[1]) << 16;
227 /* Fall-through */
228 case 1:
229 a += ((uint32_t)input[0]) << 24;
230 EFX_HASH_FINALISE(a, b, c);
231 break;
232
233 case 0:
234 /* Should only get here if length parameter was zero */
235 break;
236 }
237
238 return (c);
239 }
240
241 #elif EFSYS_IS_LITTLE_ENDIAN
242
243 /* Produce a 32-bit hash from arbitrarily aligned input */
244 __checkReturn uint32_t
efx_hash_bytes(__in_ecount (length)uint8_t const * input,__in size_t length,__in uint32_t init)245 efx_hash_bytes(
246 __in_ecount(length) uint8_t const *input,
247 __in size_t length,
248 __in uint32_t init)
249 {
250 uint32_t a;
251 uint32_t b;
252 uint32_t c;
253
254 /* Set up the initial internal state */
255 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
256
257 /* Handle all but the last twelve bytes of the input */
258 while (length > 12) {
259 a += ((uint32_t)input[0]);
260 a += ((uint32_t)input[1]) << 8;
261 a += ((uint32_t)input[2]) << 16;
262 a += ((uint32_t)input[3]) << 24;
263 b += ((uint32_t)input[4]);
264 b += ((uint32_t)input[5]) << 8;
265 b += ((uint32_t)input[6]) << 16;
266 b += ((uint32_t)input[7]) << 24;
267 c += ((uint32_t)input[8]);
268 c += ((uint32_t)input[9]) << 8;
269 c += ((uint32_t)input[10]) << 16;
270 c += ((uint32_t)input[11]) << 24;
271 EFX_HASH_MIX(a, b, c);
272 length -= 12;
273 input += 12;
274 }
275
276 /* Handle the left-overs */
277 switch (length) {
278 case 12:
279 c += ((uint32_t)input[11]) << 24;
280 /* Fall-through */
281 case 11:
282 c += ((uint32_t)input[10]) << 16;
283 /* Fall-through */
284 case 10:
285 c += ((uint32_t)input[9]) << 8;
286 /* Fall-through */
287 case 9:
288 c += ((uint32_t)input[8]);
289 /* Fall-through */
290 case 8:
291 b += ((uint32_t)input[7]) << 24;
292 /* Fall-through */
293 case 7:
294 b += ((uint32_t)input[6]) << 16;
295 /* Fall-through */
296 case 6:
297 b += ((uint32_t)input[5]) << 8;
298 /* Fall-through */
299 case 5:
300 b += ((uint32_t)input[4]);
301 /* Fall-through */
302 case 4:
303 a += ((uint32_t)input[3]) << 24;
304 /* Fall-through */
305 case 3:
306 a += ((uint32_t)input[2]) << 16;
307 /* Fall-through */
308 case 2:
309 a += ((uint32_t)input[1]) << 8;
310 /* Fall-through */
311 case 1:
312 a += ((uint32_t)input[0]);
313 EFX_HASH_FINALISE(a, b, c);
314 break;
315
316 case 0:
317 /* Should only get here if length parameter was zero */
318 break;
319 }
320
321 return (c);
322 }
323
324 #else
325
326 #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"
327
328 #endif
329