xref: /freebsd/sys/dev/sfxge/common/efx_hash.c (revision 4436b51dff5736e74da464946049ea6899a88938)
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-2015 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 __FBSDID("$FreeBSD$");
44 
45 #include "efsys.h"
46 #include "efx.h"
47 #include "efx_types.h"
48 #include "efx_impl.h"
49 
50 /* Hash initial value */
51 #define	EFX_HASH_INITIAL_VALUE	0xdeadbeef
52 
53 /*
54  * Rotate a 32-bit value left
55  *
56  * Allow platform to provide an intrinsic or optimised routine and
57  * fall-back to a simple shift based implementation.
58  */
59 #if EFSYS_HAS_ROTL_DWORD
60 
61 #define	EFX_HASH_ROTATE(_value, _shift)					\
62 	EFSYS_ROTL_DWORD(_value, _shift)
63 
64 #else
65 
66 #define	EFX_HASH_ROTATE(_value, _shift)					\
67 	(((_value) << (_shift)) | ((_value) >> (32 - (_shift))))
68 
69 #endif
70 
71 /* Mix three 32-bit values reversibly */
72 #define	EFX_HASH_MIX(_a, _b, _c)					\
73 	do {								\
74 		_a -= _c;						\
75 		_a ^= EFX_HASH_ROTATE(_c, 4);				\
76 		_c += _b;						\
77 		_b -= _a;						\
78 		_b ^= EFX_HASH_ROTATE(_a, 6);				\
79 		_a += _c;						\
80 		_c -= _b;						\
81 		_c ^= EFX_HASH_ROTATE(_b, 8);				\
82 		_b += _a;						\
83 		_a -= _c;						\
84 		_a ^= EFX_HASH_ROTATE(_c, 16);				\
85 		_c += _b;						\
86 		_b -= _a;						\
87 		_b ^= EFX_HASH_ROTATE(_a, 19);				\
88 		_a += _c;						\
89 		_c -= _b;						\
90 		_c ^= EFX_HASH_ROTATE(_b, 4);				\
91 		_b += _a;						\
92 	_NOTE(CONSTANTCONDITION)					\
93 	} while (B_FALSE)
94 
95 /* Final mixing of three 32-bit values into one (_c) */
96 #define	EFX_HASH_FINALISE(_a, _b, _c)					\
97 	do {								\
98 		_c ^= _b;						\
99 		_c -= EFX_HASH_ROTATE(_b, 14);				\
100 		_a ^= _c;						\
101 		_a -= EFX_HASH_ROTATE(_c, 11);				\
102 		_b ^= _a;						\
103 		_b -= EFX_HASH_ROTATE(_a, 25);				\
104 		_c ^= _b;						\
105 		_c -= EFX_HASH_ROTATE(_b, 16);				\
106 		_a ^= _c;						\
107 		_a -= EFX_HASH_ROTATE(_c, 4);				\
108 		_b ^= _a;						\
109 		_b -= EFX_HASH_ROTATE(_a, 14);				\
110 		_c ^= _b;						\
111 		_c -= EFX_HASH_ROTATE(_b, 24);				\
112 	_NOTE(CONSTANTCONDITION)					\
113 	} while (B_FALSE)
114 
115 
116 /* Produce a 32-bit hash from 32-bit aligned input */
117 	__checkReturn		uint32_t
118 efx_hash_dwords(
119 	__in_ecount(count)	uint32_t const *input,
120 	__in			size_t count,
121 	__in			uint32_t init)
122 {
123 	uint32_t a;
124 	uint32_t b;
125 	uint32_t c;
126 
127 	/* Set up the initial internal state */
128 	a = b = c = EFX_HASH_INITIAL_VALUE +
129 		(((uint32_t)count) * sizeof (uint32_t)) + init;
130 
131 	/* Handle all but the last three dwords of the input */
132 	while (count > 3) {
133 		a += input[0];
134 		b += input[1];
135 		c += input[2];
136 		EFX_HASH_MIX(a, b, c);
137 
138 		count -= 3;
139 		input += 3;
140 	}
141 
142 	/* Handle the left-overs */
143 	switch (count) {
144 	case 3:
145 		c += input[2];
146 		/* Fall-through */
147 	case 2:
148 		b += input[1];
149 		/* Fall-through */
150 	case 1:
151 		a += input[0];
152 		EFX_HASH_FINALISE(a, b, c);
153 		break;
154 
155 	case 0:
156 		/* Should only get here if count parameter was zero */
157 		break;
158 	}
159 
160 	return (c);
161 }
162 
163 #if EFSYS_IS_BIG_ENDIAN
164 
165 /* Produce a 32-bit hash from arbitrarily aligned input */
166 	__checkReturn		uint32_t
167 efx_hash_bytes(
168 	__in_ecount(length)	uint8_t const *input,
169 	__in			size_t length,
170 	__in			uint32_t init)
171 {
172 	uint32_t a;
173 	uint32_t b;
174 	uint32_t c;
175 
176 	/* Set up the initial internal state */
177 	a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
178 
179 	/* Handle all but the last twelve bytes of the input */
180 	while (length > 12) {
181 		a += ((uint32_t)input[0]) << 24;
182 		a += ((uint32_t)input[1]) << 16;
183 		a += ((uint32_t)input[2]) << 8;
184 		a += ((uint32_t)input[3]);
185 		b += ((uint32_t)input[4]) << 24;
186 		b += ((uint32_t)input[5]) << 16;
187 		b += ((uint32_t)input[6]) << 8;
188 		b += ((uint32_t)input[7]);
189 		c += ((uint32_t)input[8]) << 24;
190 		c += ((uint32_t)input[9]) << 16;
191 		c += ((uint32_t)input[10]) << 8;
192 		c += ((uint32_t)input[11]);
193 		EFX_HASH_MIX(a, b, c);
194 		length -= 12;
195 		input += 12;
196 	}
197 
198 	/* Handle the left-overs */
199 	switch (length) {
200 	case 12:
201 		c += ((uint32_t)input[11]);
202 		/* Fall-through */
203 	case 11:
204 		c += ((uint32_t)input[10]) << 8;
205 		/* Fall-through */
206 	case 10:
207 		c += ((uint32_t)input[9]) << 16;
208 		/* Fall-through */
209 	case 9:
210 		c += ((uint32_t)input[8]) << 24;
211 		/* Fall-through */
212 	case 8:
213 		b += ((uint32_t)input[7]);
214 		/* Fall-through */
215 	case 7:
216 		b += ((uint32_t)input[6]) << 8;
217 		/* Fall-through */
218 	case 6:
219 		b += ((uint32_t)input[5]) << 16;
220 		/* Fall-through */
221 	case 5:
222 		b += ((uint32_t)input[4]) << 24;
223 		/* Fall-through */
224 	case 4:
225 		a += ((uint32_t)input[3]);
226 		/* Fall-through */
227 	case 3:
228 		a += ((uint32_t)input[2]) << 8;
229 		/* Fall-through */
230 	case 2:
231 		a += ((uint32_t)input[1]) << 16;
232 		/* Fall-through */
233 	case 1:
234 		a += ((uint32_t)input[0]) << 24;
235 		EFX_HASH_FINALISE(a, b, c);
236 		break;
237 
238 	case 0:
239 		/* Should only get here if length parameter was zero */
240 		break;
241 	}
242 
243 	return (c);
244 }
245 
246 #elif EFSYS_IS_LITTLE_ENDIAN
247 
248 /* Produce a 32-bit hash from arbitrarily aligned input */
249 	__checkReturn		uint32_t
250 efx_hash_bytes(
251 	__in_ecount(length)	uint8_t const *input,
252 	__in			size_t length,
253 	__in			uint32_t init)
254 {
255 	uint32_t a;
256 	uint32_t b;
257 	uint32_t c;
258 
259 	/* Set up the initial internal state */
260 	a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
261 
262 	/* Handle all but the last twelve bytes of the input */
263 	while (length > 12) {
264 		a += ((uint32_t)input[0]);
265 		a += ((uint32_t)input[1]) << 8;
266 		a += ((uint32_t)input[2]) << 16;
267 		a += ((uint32_t)input[3]) << 24;
268 		b += ((uint32_t)input[4]);
269 		b += ((uint32_t)input[5]) << 8;
270 		b += ((uint32_t)input[6]) << 16;
271 		b += ((uint32_t)input[7]) << 24;
272 		c += ((uint32_t)input[8]);
273 		c += ((uint32_t)input[9]) << 8;
274 		c += ((uint32_t)input[10]) << 16;
275 		c += ((uint32_t)input[11]) << 24;
276 		EFX_HASH_MIX(a, b, c);
277 		length -= 12;
278 		input += 12;
279 	}
280 
281 	/* Handle the left-overs */
282 	switch (length) {
283 	case 12:
284 		c += ((uint32_t)input[11]) << 24;
285 		/* Fall-through */
286 	case 11:
287 		c += ((uint32_t)input[10]) << 16;
288 		/* Fall-through */
289 	case 10:
290 		c += ((uint32_t)input[9]) << 8;
291 		/* Fall-through */
292 	case 9:
293 		c += ((uint32_t)input[8]);
294 		/* Fall-through */
295 	case 8:
296 		b += ((uint32_t)input[7]) << 24;
297 		/* Fall-through */
298 	case 7:
299 		b += ((uint32_t)input[6]) << 16;
300 		/* Fall-through */
301 	case 6:
302 		b += ((uint32_t)input[5]) << 8;
303 		/* Fall-through */
304 	case 5:
305 		b += ((uint32_t)input[4]);
306 		/* Fall-through */
307 	case 4:
308 		a += ((uint32_t)input[3]) << 24;
309 		/* Fall-through */
310 	case 3:
311 		a += ((uint32_t)input[2]) << 16;
312 		/* Fall-through */
313 	case 2:
314 		a += ((uint32_t)input[1]) << 8;
315 		/* Fall-through */
316 	case 1:
317 		a += ((uint32_t)input[0]);
318 		EFX_HASH_FINALISE(a, b, c);
319 		break;
320 
321 	case 0:
322 		/* Should only get here if length parameter was zero */
323 		break;
324 	}
325 
326 	return (c);
327 }
328 
329 #else
330 
331 #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"
332 
333 #endif
334