1 | /* |
2 | * Copyright (c) 2011-2022 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | /* |
30 | * http://code.google.com/p/smhasher/ |
31 | * |
32 | * Copyright (c) 2009-2011 Austin Appleby. |
33 | * |
34 | * MurmurHash3 was written by Austin Appleby, and is placed in the public |
35 | * domain. The author hereby disclaims copyright to this source code. |
36 | */ |
37 | |
38 | /* |
39 | * http://burtleburtle.net/bob/hash/ |
40 | * |
41 | * lookup3.c, by Bob Jenkins, May 2006, Public Domain. |
42 | * |
43 | * You can use this free for any purpose. It's in the public domain. |
44 | * It has no warranty. |
45 | */ |
46 | |
47 | #include <stdbool.h> |
48 | #include <sys/types.h> |
49 | #include <machine/endian.h> |
50 | #include <net/flowhash.h> |
51 | #include <os/base.h> |
52 | |
53 | static inline u_int32_t getblock32(const u_int32_t *, int); |
54 | static inline u_int64_t getblock64(const u_int64_t *, int); |
55 | static inline u_int32_t mh3_fmix32(u_int32_t); |
56 | static inline u_int64_t mh3_fmix64(u_int64_t); |
57 | |
58 | #define ALIGNED16(v) ((((uintptr_t)(v)) & 1) == 0) |
59 | #define ALIGNED32(v) ((((uintptr_t)(v)) & 3) == 0) |
60 | #define ALIGNED64(v) ((((uintptr_t)(v)) & 7) == 0) |
61 | |
62 | #define ROTL32(x, r) (((x) << (r)) | ((x) >> (32 - (r)))) |
63 | #define ROTL64(x, r) (((x) << (r)) | ((x) >> (64 - (r)))) |
64 | |
65 | /* |
66 | * The following hash algorithms are selected based on performance: |
67 | * |
68 | * 64-bit: MurmurHash3_x64_128 |
69 | * 32-bit: JHash |
70 | */ |
71 | #if defined(__LP64__) |
72 | net_flowhash_fn_t *net_flowhash = net_flowhash_mh3_x64_128; |
73 | #else /* !__LP64__ */ |
74 | net_flowhash_fn_t *net_flowhash = net_flowhash_jhash; |
75 | #endif /* !__LP64__ */ |
76 | |
77 | #if defined(__i386__) || defined(__x86_64__) || defined(__arm64__) |
78 | static inline u_int32_t |
79 | getblock32(const u_int32_t *p, int i) |
80 | { |
81 | return p[i]; |
82 | } |
83 | |
84 | static inline u_int64_t |
85 | getblock64(const u_int64_t *p, int i) |
86 | { |
87 | return p[i]; |
88 | } |
89 | #else /* !__i386__ && !__x86_64__ && !__arm64__*/ |
90 | static inline u_int32_t |
91 | getblock32(const u_int32_t *p, int i) |
92 | { |
93 | const u_int8_t *bytes = (u_int8_t *)(void *)(uintptr_t)(p + i); |
94 | u_int32_t value; |
95 | |
96 | if (ALIGNED32(p)) { |
97 | value = p[i]; |
98 | } else { |
99 | #if BYTE_ORDER == BIG_ENDIAN |
100 | value = |
101 | (((u_int32_t)bytes[0]) << 24) | |
102 | (((u_int32_t)bytes[1]) << 16) | |
103 | (((u_int32_t)bytes[2]) << 8) | |
104 | ((u_int32_t)bytes[3]); |
105 | #else /* LITTLE_ENDIAN */ |
106 | value = |
107 | (((u_int32_t)bytes[3]) << 24) | |
108 | (((u_int32_t)bytes[2]) << 16) | |
109 | (((u_int32_t)bytes[1]) << 8) | |
110 | ((u_int32_t)bytes[0]); |
111 | #endif /* LITTLE_ENDIAN */ |
112 | } |
113 | return value; |
114 | } |
115 | |
116 | static inline u_int64_t |
117 | getblock64(const u_int64_t *p, int i) |
118 | { |
119 | const u_int8_t *bytes = (const u_int8_t *)(void *)(uintptr_t)(p + i); |
120 | u_int64_t value; |
121 | |
122 | if (ALIGNED64(p)) { |
123 | value = p[i]; |
124 | } else { |
125 | #if BYTE_ORDER == BIG_ENDIAN |
126 | value = |
127 | (((u_int64_t)bytes[0]) << 56) | |
128 | (((u_int64_t)bytes[1]) << 48) | |
129 | (((u_int64_t)bytes[2]) << 40) | |
130 | (((u_int64_t)bytes[3]) << 32) | |
131 | (((u_int64_t)bytes[4]) << 24) | |
132 | (((u_int64_t)bytes[5]) << 16) | |
133 | (((u_int64_t)bytes[6]) << 8) | |
134 | ((u_int64_t)bytes[7]); |
135 | #else /* LITTLE_ENDIAN */ |
136 | value = |
137 | (((u_int64_t)bytes[7]) << 56) | |
138 | (((u_int64_t)bytes[6]) << 48) | |
139 | (((u_int64_t)bytes[5]) << 40) | |
140 | (((u_int64_t)bytes[4]) << 32) | |
141 | (((u_int64_t)bytes[3]) << 24) | |
142 | (((u_int64_t)bytes[2]) << 16) | |
143 | (((u_int64_t)bytes[1]) << 8) | |
144 | ((u_int64_t)bytes[0]); |
145 | #endif /* LITTLE_ENDIAN */ |
146 | } |
147 | return value; |
148 | } |
149 | #endif /* !__i386__ && !__x86_64 && !__arm64__ */ |
150 | |
151 | static inline u_int32_t |
152 | mh3_fmix32(u_int32_t h) |
153 | { |
154 | h ^= h >> 16; |
155 | h *= 0x85ebca6b; |
156 | h ^= h >> 13; |
157 | h *= 0xc2b2ae35; |
158 | h ^= h >> 16; |
159 | |
160 | return h; |
161 | } |
162 | |
163 | static inline u_int64_t |
164 | mh3_fmix64(u_int64_t k) |
165 | { |
166 | k ^= k >> 33; |
167 | k *= 0xff51afd7ed558ccdLLU; |
168 | k ^= k >> 33; |
169 | k *= 0xc4ceb9fe1a85ec53LLU; |
170 | k ^= k >> 33; |
171 | |
172 | return k; |
173 | } |
174 | |
175 | /* |
176 | * MurmurHash3_x86_32 |
177 | */ |
178 | #define MH3_X86_32_C1 0xcc9e2d51 |
179 | #define MH3_X86_32_C2 0x1b873593 |
180 | |
181 | u_int32_t |
182 | net_flowhash_mh3_x86_32(const void *key, u_int32_t len, const u_int32_t seed) |
183 | { |
184 | const u_int8_t *data = (const u_int8_t *)key; |
185 | const u_int32_t nblocks = len / 4; |
186 | const u_int32_t *blocks; |
187 | const u_int8_t *tail; |
188 | u_int32_t h1 = seed, k1; |
189 | int i; |
190 | |
191 | /* body */ |
192 | blocks = (const u_int32_t *)(const void *)(data + nblocks * 4); |
193 | |
194 | for (i = -nblocks; i; i++) { |
195 | k1 = getblock32(p: blocks, i); |
196 | |
197 | k1 *= MH3_X86_32_C1; |
198 | k1 = ROTL32(k1, 15); |
199 | k1 *= MH3_X86_32_C2; |
200 | |
201 | h1 ^= k1; |
202 | h1 = ROTL32(h1, 13); |
203 | h1 = h1 * 5 + 0xe6546b64; |
204 | } |
205 | |
206 | /* tail */ |
207 | tail = (const u_int8_t *)(const void *)(data + nblocks * 4); |
208 | k1 = 0; |
209 | |
210 | switch (len & 3) { |
211 | case 3: |
212 | k1 ^= tail[2] << 16; |
213 | OS_FALLTHROUGH; |
214 | case 2: |
215 | k1 ^= tail[1] << 8; |
216 | OS_FALLTHROUGH; |
217 | case 1: |
218 | k1 ^= tail[0]; |
219 | k1 *= MH3_X86_32_C1; |
220 | k1 = ROTL32(k1, 15); |
221 | k1 *= MH3_X86_32_C2; |
222 | h1 ^= k1; |
223 | } |
224 | ; |
225 | |
226 | /* finalization */ |
227 | h1 ^= len; |
228 | |
229 | h1 = mh3_fmix32(h: h1); |
230 | |
231 | return h1; |
232 | } |
233 | |
234 | /* |
235 | * MurmurHash3_x64_128 |
236 | */ |
237 | #define MH3_X64_128_C1 0x87c37b91114253d5LLU |
238 | #define MH3_X64_128_C2 0x4cf5ad432745937fLLU |
239 | |
240 | u_int32_t |
241 | net_flowhash_mh3_x64_128(const void *key, u_int32_t len, const u_int32_t seed) |
242 | { |
243 | const u_int8_t *data = (const u_int8_t *)key; |
244 | const u_int32_t nblocks = len / 16; |
245 | const u_int64_t *blocks; |
246 | const u_int8_t *tail; |
247 | u_int64_t h1 = seed, k1; |
248 | u_int64_t h2 = seed, k2; |
249 | u_int32_t i; |
250 | |
251 | /* body */ |
252 | blocks = (const u_int64_t *)(const void *)data; |
253 | |
254 | for (i = 0; i < nblocks; i++) { |
255 | k1 = getblock64(p: blocks, i: i * 2 + 0); |
256 | k2 = getblock64(p: blocks, i: i * 2 + 1); |
257 | |
258 | k1 *= MH3_X64_128_C1; |
259 | #if defined(__x86_64__) |
260 | __asm__ ( "rol $31, %[k1]\n\t" :[k1] "+r" (k1) : :); |
261 | #elif defined(__arm64__) |
262 | __asm__ ( "ror %[k1], %[k1], #(64-31)\n\t" :[k1] "+r" (k1) : :); |
263 | #else /* !__x86_64__ && !__arm64__ */ |
264 | k1 = ROTL64(k1, 31); |
265 | #endif /* !__x86_64__ && !__arm64__ */ |
266 | k1 *= MH3_X64_128_C2; |
267 | h1 ^= k1; |
268 | |
269 | #if defined(__x86_64__) |
270 | __asm__ ( "rol $27, %[h1]\n\t" :[h1] "+r" (h1) : :); |
271 | #elif defined(__arm64__) |
272 | __asm__ ( "ror %[h1], %[h1], #(64-27)\n\t" :[h1] "+r" (h1) : :); |
273 | #else /* !__x86_64__ && !__arm64__ */ |
274 | h1 = ROTL64(h1, 27); |
275 | #endif /* !__x86_64__ && !__arm64__ */ |
276 | h1 += h2; |
277 | h1 = h1 * 5 + 0x52dce729; |
278 | |
279 | k2 *= MH3_X64_128_C2; |
280 | #if defined(__x86_64__) |
281 | __asm__ ( "rol $33, %[k2]\n\t" :[k2] "+r" (k2) : :); |
282 | #elif defined(__arm64__) |
283 | __asm__ ( "ror %[k2], %[k2], #(64-33)\n\t" :[k2] "+r" (k2) : :); |
284 | #else /* !__x86_64__ && !__arm64__ */ |
285 | k2 = ROTL64(k2, 33); |
286 | #endif /* !__x86_64__ && !__arm64__ */ |
287 | k2 *= MH3_X64_128_C1; |
288 | h2 ^= k2; |
289 | |
290 | #if defined(__x86_64__) |
291 | __asm__ ( "rol $31, %[h2]\n\t" :[h2] "+r" (h2) : :); |
292 | #elif defined(__arm64__) |
293 | __asm__ ( "ror %[h2], %[h2], #(64-31)\n\t" :[h2] "+r" (h2) : :); |
294 | #else /* !__x86_64__ && !__arm64__ */ |
295 | h2 = ROTL64(h2, 31); |
296 | #endif /* !__x86_64__ && !__arm64__ */ |
297 | h2 += h1; |
298 | h2 = h2 * 5 + 0x38495ab5; |
299 | } |
300 | |
301 | /* tail */ |
302 | tail = (const u_int8_t *)(const void *)(data + nblocks * 16); |
303 | k1 = 0; |
304 | k2 = 0; |
305 | |
306 | switch (len & 15) { |
307 | case 15: |
308 | k2 ^= ((u_int64_t)tail[14]) << 48; |
309 | OS_FALLTHROUGH; |
310 | case 14: |
311 | k2 ^= ((u_int64_t)tail[13]) << 40; |
312 | OS_FALLTHROUGH; |
313 | case 13: |
314 | k2 ^= ((u_int64_t)tail[12]) << 32; |
315 | OS_FALLTHROUGH; |
316 | case 12: |
317 | k2 ^= ((u_int64_t)tail[11]) << 24; |
318 | OS_FALLTHROUGH; |
319 | case 11: |
320 | k2 ^= ((u_int64_t)tail[10]) << 16; |
321 | OS_FALLTHROUGH; |
322 | case 10: |
323 | k2 ^= ((u_int64_t)tail[9]) << 8; |
324 | OS_FALLTHROUGH; |
325 | case 9: |
326 | k2 ^= ((u_int64_t)tail[8]) << 0; |
327 | k2 *= MH3_X64_128_C2; |
328 | #if defined(__x86_64__) |
329 | __asm__ ( "rol $33, %[k2]\n\t" :[k2] "+r" (k2) : :); |
330 | #elif defined(__arm64__) |
331 | __asm__ ( "ror %[k2], %[k2], #(64-33)\n\t" :[k2] "+r" (k2) : :); |
332 | #else /* !__x86_64__ && !__arm64__ */ |
333 | k2 = ROTL64(k2, 33); |
334 | #endif /* !__x86_64__ && !__arm64__ */ |
335 | k2 *= MH3_X64_128_C1; |
336 | h2 ^= k2; |
337 | OS_FALLTHROUGH; |
338 | case 8: |
339 | k1 ^= ((u_int64_t)tail[7]) << 56; |
340 | OS_FALLTHROUGH; |
341 | case 7: |
342 | k1 ^= ((u_int64_t)tail[6]) << 48; |
343 | OS_FALLTHROUGH; |
344 | case 6: |
345 | k1 ^= ((u_int64_t)tail[5]) << 40; |
346 | OS_FALLTHROUGH; |
347 | case 5: |
348 | k1 ^= ((u_int64_t)tail[4]) << 32; |
349 | OS_FALLTHROUGH; |
350 | case 4: |
351 | k1 ^= ((u_int64_t)tail[3]) << 24; |
352 | OS_FALLTHROUGH; |
353 | case 3: |
354 | k1 ^= ((u_int64_t)tail[2]) << 16; |
355 | OS_FALLTHROUGH; |
356 | case 2: |
357 | k1 ^= ((u_int64_t)tail[1]) << 8; |
358 | OS_FALLTHROUGH; |
359 | case 1: |
360 | k1 ^= ((u_int64_t)tail[0]) << 0; |
361 | k1 *= MH3_X64_128_C1; |
362 | #if defined(__x86_64__) |
363 | __asm__ ( "rol $31, %[k1]\n\t" :[k1] "+r" (k1) : :); |
364 | #elif defined(__arm64__) |
365 | __asm__ ( "ror %[k1], %[k1], #(64-31)\n\t" :[k1] "+r" (k1) : :); |
366 | #else /* !__x86_64__ && !__arm64__ */ |
367 | k1 = ROTL64(k1, 31); |
368 | #endif /* !__x86_64__ && !__arm64__ */ |
369 | k1 *= MH3_X64_128_C2; |
370 | h1 ^= k1; |
371 | } |
372 | ; |
373 | |
374 | /* finalization */ |
375 | h1 ^= len; |
376 | h2 ^= len; |
377 | |
378 | h1 += h2; |
379 | h2 += h1; |
380 | |
381 | h1 = mh3_fmix64(k: h1); |
382 | h2 = mh3_fmix64(k: h2); |
383 | |
384 | h1 += h2; |
385 | h2 += h1; |
386 | |
387 | /* throw all but lowest 32-bit */ |
388 | return h1 & 0xffffffff; |
389 | } |
390 | |
391 | #define JHASH_INIT 0xdeadbeef |
392 | |
393 | #define JHASH_MIX(a, b, c) { \ |
394 | a -= c; a ^= ROTL32(c, 4); c += b; \ |
395 | b -= a; b ^= ROTL32(a, 6); a += c; \ |
396 | c -= b; c ^= ROTL32(b, 8); b += a; \ |
397 | a -= c; a ^= ROTL32(c, 16); c += b; \ |
398 | b -= a; b ^= ROTL32(a, 19); a += c; \ |
399 | c -= b; c ^= ROTL32(b, 4); b += a; \ |
400 | } |
401 | |
402 | #define JHASH_FINAL(a, b, c) { \ |
403 | c ^= b; c -= ROTL32(b, 14); \ |
404 | a ^= c; a -= ROTL32(c, 11); \ |
405 | b ^= a; b -= ROTL32(a, 25); \ |
406 | c ^= b; c -= ROTL32(b, 16); \ |
407 | a ^= c; a -= ROTL32(c, 4); \ |
408 | b ^= a; b -= ROTL32(a, 14); \ |
409 | c ^= b; c -= ROTL32(b, 24); \ |
410 | } |
411 | |
412 | #if BYTE_ORDER == BIG_ENDIAN |
413 | /* |
414 | * hashbig() |
415 | */ |
416 | u_int32_t |
417 | net_flowhash_jhash(const void *key, u_int32_t len, const u_int32_t seed) |
418 | { |
419 | u_int32_t a, b, c; |
420 | |
421 | /* Set up the internal state */ |
422 | a = b = c = JHASH_INIT + len + seed; |
423 | |
424 | if (ALIGNED32(key)) { |
425 | /* read 32-bit chunks */ |
426 | const u_int32_t *k = (const u_int32_t *)key; |
427 | |
428 | /* |
429 | * all but last block: |
430 | * aligned reads and affect 32 bits of (a,b,c) |
431 | */ |
432 | while (len > 12) { |
433 | a += k[0]; |
434 | b += k[1]; |
435 | c += k[2]; |
436 | JHASH_MIX(a, b, c); |
437 | len -= 12; |
438 | k += 3; |
439 | } |
440 | |
441 | /* |
442 | * handle the last (probably partial) block |
443 | * |
444 | * "k[2] << 8" actually reads beyond the end of the string, |
445 | * but then shifts out the part it's not allowed to read. |
446 | * Because the string is aligned, the illegal read is in |
447 | * the same word as the rest of the string. The masking |
448 | * trick does make the hash noticably faster for short |
449 | * strings (like English words). |
450 | */ |
451 | switch (len) { |
452 | case 12: |
453 | c += k[2]; |
454 | b += k[1]; |
455 | a += k[0]; |
456 | break; |
457 | |
458 | case 11: |
459 | c += k[2] & 0xffffff00; |
460 | b += k[1]; |
461 | a += k[0]; |
462 | break; |
463 | |
464 | case 10: |
465 | c += k[2] & 0xffff0000; |
466 | b += k[1]; |
467 | a += k[0]; |
468 | break; |
469 | |
470 | case 9: |
471 | c += k[2] & 0xff000000; |
472 | b += k[1]; |
473 | a += k[0]; |
474 | break; |
475 | |
476 | case 8: |
477 | b += k[1]; |
478 | a += k[0]; |
479 | break; |
480 | |
481 | case 7: |
482 | b += k[1] & 0xffffff00; |
483 | a += k[0]; |
484 | break; |
485 | |
486 | case 6: |
487 | b += k[1] & 0xffff0000; |
488 | a += k[0]; |
489 | break; |
490 | |
491 | case 5: |
492 | b += k[1] & 0xff000000; |
493 | a += k[0]; |
494 | break; |
495 | |
496 | case 4: |
497 | a += k[0]; |
498 | break; |
499 | |
500 | case 3: |
501 | a += k[0] & 0xffffff00; |
502 | break; |
503 | |
504 | case 2: |
505 | a += k[0] & 0xffff0000; |
506 | break; |
507 | |
508 | case 1: |
509 | a += k[0] & 0xff000000; |
510 | break; |
511 | |
512 | case 0: |
513 | /* zero length requires no mixing */ |
514 | return c; |
515 | } |
516 | |
517 | JHASH_FINAL(a, b, c); |
518 | |
519 | return c; |
520 | } |
521 | |
522 | /* need to read the key one byte at a time */ |
523 | const u_int8_t *k = (const u_int8_t *)key; |
524 | |
525 | /* all but the last block: affect some 32 bits of (a,b,c) */ |
526 | while (len > 12) { |
527 | a += ((u_int32_t)k[0]) << 24; |
528 | a += ((u_int32_t)k[1]) << 16; |
529 | a += ((u_int32_t)k[2]) << 8; |
530 | a += ((u_int32_t)k[3]); |
531 | b += ((u_int32_t)k[4]) << 24; |
532 | b += ((u_int32_t)k[5]) << 16; |
533 | b += ((u_int32_t)k[6]) << 8; |
534 | b += ((u_int32_t)k[7]); |
535 | c += ((u_int32_t)k[8]) << 24; |
536 | c += ((u_int32_t)k[9]) << 16; |
537 | c += ((u_int32_t)k[10]) << 8; |
538 | c += ((u_int32_t)k[11]); |
539 | JHASH_MIX(a, b, c); |
540 | len -= 12; |
541 | k += 12; |
542 | } |
543 | |
544 | /* last block: affect all 32 bits of (c) */ |
545 | switch (len) { |
546 | case 12: |
547 | c += k[11]; |
548 | OS_FALLTHROUGH; |
549 | case 11: |
550 | c += ((u_int32_t)k[10]) << 8; |
551 | OS_FALLTHROUGH; |
552 | case 10: |
553 | c += ((u_int32_t)k[9]) << 16; |
554 | OS_FALLTHROUGH; |
555 | case 9: |
556 | c += ((u_int32_t)k[8]) << 24; |
557 | OS_FALLTHROUGH; |
558 | case 8: |
559 | b += k[7]; |
560 | OS_FALLTHROUGH; |
561 | case 7: |
562 | b += ((u_int32_t)k[6]) << 8; |
563 | OS_FALLTHROUGH; |
564 | case 6: |
565 | b += ((u_int32_t)k[5]) << 16; |
566 | OS_FALLTHROUGH; |
567 | case 5: |
568 | b += ((u_int32_t)k[4]) << 24; |
569 | OS_FALLTHROUGH; |
570 | case 4: |
571 | a += k[3]; |
572 | OS_FALLTHROUGH; |
573 | case 3: |
574 | a += ((u_int32_t)k[2]) << 8; |
575 | OS_FALLTHROUGH; |
576 | case 2: |
577 | a += ((u_int32_t)k[1]) << 16; |
578 | OS_FALLTHROUGH; |
579 | case 1: |
580 | a += ((u_int32_t)k[0]) << 24; |
581 | break; |
582 | |
583 | case 0: |
584 | /* zero length requires no mixing */ |
585 | return c; |
586 | } |
587 | |
588 | JHASH_FINAL(a, b, c); |
589 | |
590 | return c; |
591 | } |
592 | #else /* LITTLE_ENDIAN */ |
593 | /* |
594 | * hashlittle() |
595 | */ |
596 | u_int32_t |
597 | net_flowhash_jhash(const void *key, u_int32_t len, const u_int32_t seed) |
598 | { |
599 | u_int32_t a, b, c; |
600 | |
601 | /* Set up the internal state */ |
602 | a = b = c = JHASH_INIT + len + seed; |
603 | |
604 | #if defined(__i386__) || defined(__x86_64__) |
605 | /* |
606 | * On i386/x86_64, it is faster to read 32-bit chunks if the key |
607 | * is aligned 32-bit OR not 16-bit, and perform 16-bit reads if it |
608 | * is aligned 16-bit. |
609 | */ |
610 | if (ALIGNED32(key) || !ALIGNED16(key)) { |
611 | #else /* !defined(__i386__) && !defined(__x86_64__) */ |
612 | if (ALIGNED32(key)) { |
613 | #endif /* !defined(__i386__) && !defined(__x86_64__) */ |
614 | /* read 32-bit chunks */ |
615 | const u_int32_t *k = (const u_int32_t *)key; |
616 | const u_int16_t *k16 = (const u_int16_t *)key; |
617 | const u_int8_t *k8 = (const u_int8_t *)key; |
618 | |
619 | /* |
620 | * all but last block: |
621 | * aligned reads and affect 32 bits of (a,b,c) |
622 | */ |
623 | while (len > 12) { |
624 | a += k[0]; |
625 | b += k[1]; |
626 | c += k[2]; |
627 | JHASH_MIX(a, b, c); |
628 | len -= 12; |
629 | k += 3; |
630 | } |
631 | |
632 | /* handle the last (probably partial) block */ |
633 | switch (len) { |
634 | case 12: |
635 | c += k[2]; |
636 | b += k[1]; |
637 | a += k[0]; |
638 | break; |
639 | |
640 | case 11: |
641 | c += ((u_int32_t)k8[10]) << 16; |
642 | c += k16[4]; |
643 | b += k[1]; |
644 | a += k[0]; |
645 | break; |
646 | |
647 | case 10: |
648 | c += k16[4]; |
649 | b += k[1]; |
650 | a += k[0]; |
651 | break; |
652 | |
653 | case 9: |
654 | c += k8[8]; |
655 | b += k[1]; |
656 | a += k[0]; |
657 | break; |
658 | |
659 | case 8: |
660 | b += k[1]; |
661 | a += k[0]; |
662 | break; |
663 | |
664 | case 7: |
665 | b += ((u_int32_t)k8[6]) << 16; |
666 | b += k16[2]; |
667 | a += k[0]; |
668 | break; |
669 | |
670 | case 6: |
671 | b += k16[2]; |
672 | a += k[0]; |
673 | break; |
674 | |
675 | case 5: |
676 | b += k8[4]; |
677 | a += k[0]; |
678 | break; |
679 | |
680 | case 4: |
681 | a += k[0]; |
682 | break; |
683 | |
684 | case 3: |
685 | a += ((u_int32_t)k8[2]) << 16; |
686 | a += k16[0]; |
687 | break; |
688 | |
689 | case 2: |
690 | a += k16[0]; |
691 | break; |
692 | |
693 | case 1: |
694 | a += k8[0]; |
695 | break; |
696 | |
697 | case 0: |
698 | /* zero length requires no mixing */ |
699 | return c; |
700 | } |
701 | |
702 | JHASH_FINAL(a, b, c); |
703 | |
704 | return c; |
705 | } |
706 | #if !defined(__i386__) && !defined(__x86_64__) |
707 | else if (ALIGNED16(key)) { |
708 | #endif /* !defined(__i386__) && !defined(__x86_64__) */ |
709 | /* read 16-bit chunks */ |
710 | const u_int16_t *k = (const u_int16_t *)key; |
711 | const u_int8_t *k8; |
712 | |
713 | /* all but last block: aligned reads and different mixing */ |
714 | while (len > 12) { |
715 | a += k[0] + (((u_int32_t)k[1]) << 16); |
716 | b += k[2] + (((u_int32_t)k[3]) << 16); |
717 | c += k[4] + (((u_int32_t)k[5]) << 16); |
718 | JHASH_MIX(a, b, c); |
719 | len -= 12; |
720 | k += 6; |
721 | } |
722 | |
723 | /* handle the last (probably partial) block */ |
724 | k8 = (const u_int8_t *)k; |
725 | switch (len) { |
726 | case 12: |
727 | c += k[4] + (((u_int32_t)k[5]) << 16); |
728 | b += k[2] + (((u_int32_t)k[3]) << 16); |
729 | a += k[0] + (((u_int32_t)k[1]) << 16); |
730 | break; |
731 | |
732 | case 11: |
733 | c += ((u_int32_t)k8[10]) << 16; |
734 | OS_FALLTHROUGH; |
735 | case 10: |
736 | c += k[4]; |
737 | b += k[2] + (((u_int32_t)k[3]) << 16); |
738 | a += k[0] + (((u_int32_t)k[1]) << 16); |
739 | break; |
740 | |
741 | case 9: |
742 | c += k8[8]; |
743 | OS_FALLTHROUGH; |
744 | case 8: |
745 | b += k[2] + (((u_int32_t)k[3]) << 16); |
746 | a += k[0] + (((u_int32_t)k[1]) << 16); |
747 | break; |
748 | |
749 | case 7: |
750 | b += ((u_int32_t)k8[6]) << 16; |
751 | OS_FALLTHROUGH; |
752 | case 6: |
753 | b += k[2]; |
754 | a += k[0] + (((u_int32_t)k[1]) << 16); |
755 | break; |
756 | |
757 | case 5: |
758 | b += k8[4]; |
759 | OS_FALLTHROUGH; |
760 | case 4: |
761 | a += k[0] + (((u_int32_t)k[1]) << 16); |
762 | break; |
763 | |
764 | case 3: |
765 | a += ((u_int32_t)k8[2]) << 16; |
766 | OS_FALLTHROUGH; |
767 | case 2: |
768 | a += k[0]; |
769 | break; |
770 | |
771 | case 1: |
772 | a += k8[0]; |
773 | break; |
774 | |
775 | case 0: |
776 | /* zero length requires no mixing */ |
777 | return c; |
778 | } |
779 | |
780 | JHASH_FINAL(a, b, c); |
781 | |
782 | return c; |
783 | #if !defined(__i386__) && !defined(__x86_64__) |
784 | } |
785 | |
786 | /* need to read the key one byte at a time */ |
787 | const u_int8_t *k = (const u_int8_t *)key; |
788 | |
789 | /* all but the last block: affect some 32 bits of (a,b,c) */ |
790 | while (len > 12) { |
791 | a += k[0]; |
792 | a += ((u_int32_t)k[1]) << 8; |
793 | a += ((u_int32_t)k[2]) << 16; |
794 | a += ((u_int32_t)k[3]) << 24; |
795 | b += k[4]; |
796 | b += ((u_int32_t)k[5]) << 8; |
797 | b += ((u_int32_t)k[6]) << 16; |
798 | b += ((u_int32_t)k[7]) << 24; |
799 | c += k[8]; |
800 | c += ((u_int32_t)k[9]) << 8; |
801 | c += ((u_int32_t)k[10]) << 16; |
802 | c += ((u_int32_t)k[11]) << 24; |
803 | JHASH_MIX(a, b, c); |
804 | len -= 12; |
805 | k += 12; |
806 | } |
807 | |
808 | /* last block: affect all 32 bits of (c) */ |
809 | switch (len) { |
810 | case 12: |
811 | c += ((u_int32_t)k[11]) << 24; |
812 | OS_FALLTHROUGH; |
813 | case 11: |
814 | c += ((u_int32_t)k[10]) << 16; |
815 | OS_FALLTHROUGH; |
816 | case 10: |
817 | c += ((u_int32_t)k[9]) << 8; |
818 | OS_FALLTHROUGH; |
819 | case 9: |
820 | c += k[8]; |
821 | OS_FALLTHROUGH; |
822 | case 8: |
823 | b += ((u_int32_t)k[7]) << 24; |
824 | OS_FALLTHROUGH; |
825 | case 7: |
826 | b += ((u_int32_t)k[6]) << 16; |
827 | OS_FALLTHROUGH; |
828 | case 6: |
829 | b += ((u_int32_t)k[5]) << 8; |
830 | OS_FALLTHROUGH; |
831 | case 5: |
832 | b += k[4]; |
833 | OS_FALLTHROUGH; |
834 | case 4: |
835 | a += ((u_int32_t)k[3]) << 24; |
836 | OS_FALLTHROUGH; |
837 | case 3: |
838 | a += ((u_int32_t)k[2]) << 16; |
839 | OS_FALLTHROUGH; |
840 | case 2: |
841 | a += ((u_int32_t)k[1]) << 8; |
842 | OS_FALLTHROUGH; |
843 | case 1: |
844 | a += k[0]; |
845 | break; |
846 | |
847 | case 0: |
848 | /* zero length requires no mixing */ |
849 | return c; |
850 | } |
851 | |
852 | JHASH_FINAL(a, b, c); |
853 | |
854 | return c; |
855 | #endif /* !defined(__i386__) && !defined(__x86_64__) */ |
856 | } |
857 | #endif /* LITTLE_ENDIAN */ |
858 | |