xref: /illumos-gate/usr/src/uts/common/io/sfxge/common/efx_hash.c (revision 49ef7e0638c8b771d8a136eae78b1c0f99acc8e0)
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 "efx.h"
43 #include "efx_impl.h"
44 
45 /* Hash initial value */
46 #define	EFX_HASH_INITIAL_VALUE	0xdeadbeef
47 
48 /*
49  * Rotate a 32-bit value left
50  *
51  * Allow platform to provide an intrinsic or optimised routine and
52  * fall-back to a simple shift based implementation.
53  */
54 #if EFSYS_HAS_ROTL_DWORD
55 
56 #define	EFX_HASH_ROTATE(_value, _shift)					\
57 	EFSYS_ROTL_DWORD(_value, _shift)
58 
59 #else
60 
61 #define	EFX_HASH_ROTATE(_value, _shift)					\
62 	(((_value) << (_shift)) | ((_value) >> (32 - (_shift))))
63 
64 #endif
65 
66 /* Mix three 32-bit values reversibly */
67 #define	EFX_HASH_MIX(_a, _b, _c)					\
68 	do {								\
69 		_a -= _c;						\
70 		_a ^= EFX_HASH_ROTATE(_c, 4);				\
71 		_c += _b;						\
72 		_b -= _a;						\
73 		_b ^= EFX_HASH_ROTATE(_a, 6);				\
74 		_a += _c;						\
75 		_c -= _b;						\
76 		_c ^= EFX_HASH_ROTATE(_b, 8);				\
77 		_b += _a;						\
78 		_a -= _c;						\
79 		_a ^= EFX_HASH_ROTATE(_c, 16);				\
80 		_c += _b;						\
81 		_b -= _a;						\
82 		_b ^= EFX_HASH_ROTATE(_a, 19);				\
83 		_a += _c;						\
84 		_c -= _b;						\
85 		_c ^= EFX_HASH_ROTATE(_b, 4);				\
86 		_b += _a;						\
87 	_NOTE(CONSTANTCONDITION)					\
88 	} while (B_FALSE)
89 
90 /* Final mixing of three 32-bit values into one (_c) */
91 #define	EFX_HASH_FINALISE(_a, _b, _c)					\
92 	do {								\
93 		_c ^= _b;						\
94 		_c -= EFX_HASH_ROTATE(_b, 14);				\
95 		_a ^= _c;						\
96 		_a -= EFX_HASH_ROTATE(_c, 11);				\
97 		_b ^= _a;						\
98 		_b -= EFX_HASH_ROTATE(_a, 25);				\
99 		_c ^= _b;						\
100 		_c -= EFX_HASH_ROTATE(_b, 16);				\
101 		_a ^= _c;						\
102 		_a -= EFX_HASH_ROTATE(_c, 4);				\
103 		_b ^= _a;						\
104 		_b -= EFX_HASH_ROTATE(_a, 14);				\
105 		_c ^= _b;						\
106 		_c -= EFX_HASH_ROTATE(_b, 24);				\
107 	_NOTE(CONSTANTCONDITION)					\
108 	} while (B_FALSE)
109 
110 
111 /* Produce a 32-bit hash from 32-bit aligned input */
112 	__checkReturn		uint32_t
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 		/* FALLTHROUGH */
142 	case 2:
143 		b += input[1];
144 		/* FALLTHROUGH */
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
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
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 		/* FALLTHROUGH */
281 	case 11:
282 		c += ((uint32_t)input[10]) << 16;
283 		/* FALLTHROUGH */
284 	case 10:
285 		c += ((uint32_t)input[9]) << 8;
286 		/* FALLTHROUGH */
287 	case 9:
288 		c += ((uint32_t)input[8]);
289 		/* FALLTHROUGH */
290 	case 8:
291 		b += ((uint32_t)input[7]) << 24;
292 		/* FALLTHROUGH */
293 	case 7:
294 		b += ((uint32_t)input[6]) << 16;
295 		/* FALLTHROUGH */
296 	case 6:
297 		b += ((uint32_t)input[5]) << 8;
298 		/* FALLTHROUGH */
299 	case 5:
300 		b += ((uint32_t)input[4]);
301 		/* FALLTHROUGH */
302 	case 4:
303 		a += ((uint32_t)input[3]) << 24;
304 		/* FALLTHROUGH */
305 	case 3:
306 		a += ((uint32_t)input[2]) << 16;
307 		/* FALLTHROUGH */
308 	case 2:
309 		a += ((uint32_t)input[1]) << 8;
310 		/* FALLTHROUGH */
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