1 /* SPDX-License-Identifier: BSD-3-Clause
3 * Copyright 2006 Bob Jenkins
5 * Derived from public domain source, see
6 * <http://burtleburtle.net/bob/c/lookup3.c>:
8 * "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
10 * These are functions for producing 32-bit hashes for hash table lookup...
11 * ...You can use this free for any purpose. It's in the public domain.
12 * It has no warranty."
14 * Copyright (c) 2014-2018 Solarflare Communications Inc.
15 * All rights reserved.
21 /* Hash initial value */
22 #define EFX_HASH_INITIAL_VALUE 0xdeadbeef
25 * Rotate a 32-bit value left
27 * Allow platform to provide an intrinsic or optimised routine and
28 * fall-back to a simple shift based implementation.
30 #if EFSYS_HAS_ROTL_DWORD
32 #define EFX_HASH_ROTATE(_value, _shift) \
33 EFSYS_ROTL_DWORD(_value, _shift)
37 #define EFX_HASH_ROTATE(_value, _shift) \
38 (((_value) << (_shift)) | ((_value) >> (32 - (_shift))))
42 /* Mix three 32-bit values reversibly */
43 #define EFX_HASH_MIX(_a, _b, _c) \
46 _a ^= EFX_HASH_ROTATE(_c, 4); \
49 _b ^= EFX_HASH_ROTATE(_a, 6); \
52 _c ^= EFX_HASH_ROTATE(_b, 8); \
55 _a ^= EFX_HASH_ROTATE(_c, 16); \
58 _b ^= EFX_HASH_ROTATE(_a, 19); \
61 _c ^= EFX_HASH_ROTATE(_b, 4); \
63 _NOTE(CONSTANTCONDITION) \
66 /* Final mixing of three 32-bit values into one (_c) */
67 #define EFX_HASH_FINALISE(_a, _b, _c) \
70 _c -= EFX_HASH_ROTATE(_b, 14); \
72 _a -= EFX_HASH_ROTATE(_c, 11); \
74 _b -= EFX_HASH_ROTATE(_a, 25); \
76 _c -= EFX_HASH_ROTATE(_b, 16); \
78 _a -= EFX_HASH_ROTATE(_c, 4); \
80 _b -= EFX_HASH_ROTATE(_a, 14); \
82 _c -= EFX_HASH_ROTATE(_b, 24); \
83 _NOTE(CONSTANTCONDITION) \
87 /* Produce a 32-bit hash from 32-bit aligned input */
88 __checkReturn uint32_t
90 __in_ecount(count) uint32_t const *input,
98 /* Set up the initial internal state */
99 a = b = c = EFX_HASH_INITIAL_VALUE +
100 (((uint32_t)count) * sizeof (uint32_t)) + init;
102 /* Handle all but the last three dwords of the input */
107 EFX_HASH_MIX(a, b, c);
113 /* Handle the left-overs */
123 EFX_HASH_FINALISE(a, b, c);
127 /* Should only get here if count parameter was zero */
134 #if EFSYS_IS_BIG_ENDIAN
136 /* Produce a 32-bit hash from arbitrarily aligned input */
137 __checkReturn uint32_t
139 __in_ecount(length) uint8_t const *input,
147 /* Set up the initial internal state */
148 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
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);
169 /* Handle the left-overs */
172 c += ((uint32_t)input[11]);
175 c += ((uint32_t)input[10]) << 8;
178 c += ((uint32_t)input[9]) << 16;
181 c += ((uint32_t)input[8]) << 24;
184 b += ((uint32_t)input[7]);
187 b += ((uint32_t)input[6]) << 8;
190 b += ((uint32_t)input[5]) << 16;
193 b += ((uint32_t)input[4]) << 24;
196 a += ((uint32_t)input[3]);
199 a += ((uint32_t)input[2]) << 8;
202 a += ((uint32_t)input[1]) << 16;
205 a += ((uint32_t)input[0]) << 24;
206 EFX_HASH_FINALISE(a, b, c);
210 /* Should only get here if length parameter was zero */
217 #elif EFSYS_IS_LITTLE_ENDIAN
219 /* Produce a 32-bit hash from arbitrarily aligned input */
220 __checkReturn uint32_t
222 __in_ecount(length) uint8_t const *input,
230 /* Set up the initial internal state */
231 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
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);
252 /* Handle the left-overs */
255 c += ((uint32_t)input[11]) << 24;
258 c += ((uint32_t)input[10]) << 16;
261 c += ((uint32_t)input[9]) << 8;
264 c += ((uint32_t)input[8]);
267 b += ((uint32_t)input[7]) << 24;
270 b += ((uint32_t)input[6]) << 16;
273 b += ((uint32_t)input[5]) << 8;
276 b += ((uint32_t)input[4]);
279 a += ((uint32_t)input[3]) << 24;
282 a += ((uint32_t)input[2]) << 16;
285 a += ((uint32_t)input[1]) << 8;
288 a += ((uint32_t)input[0]);
289 EFX_HASH_FINALISE(a, b, c);
293 /* Should only get here if length parameter was zero */
302 #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"