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
53static inline u_int32_t getblock32(const u_int32_t *, int);
54static inline u_int64_t getblock64(const u_int64_t *, int);
55static inline u_int32_t mh3_fmix32(u_int32_t);
56static 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__)
72net_flowhash_fn_t *net_flowhash = net_flowhash_mh3_x64_128;
73#else /* !__LP64__ */
74net_flowhash_fn_t *net_flowhash = net_flowhash_jhash;
75#endif /* !__LP64__ */
76
77#if defined(__i386__) || defined(__x86_64__) || defined(__arm64__)
78static inline u_int32_t
79getblock32(const u_int32_t *p, int i)
80{
81 return p[i];
82}
83
84static inline u_int64_t
85getblock64(const u_int64_t *p, int i)
86{
87 return p[i];
88}
89#else /* !__i386__ && !__x86_64__ && !__arm64__*/
90static inline u_int32_t
91getblock32(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
116static inline u_int64_t
117getblock64(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
151static inline u_int32_t
152mh3_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
163static inline u_int64_t
164mh3_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
181u_int32_t
182net_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
240u_int32_t
241net_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 */
416u_int32_t
417net_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 */
596u_int32_t
597net_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 */
787const u_int8_t *k = (const u_int8_t *)key;
788
789/* all but the last block: affect some 32 bits of (a,b,c) */
790while (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) */
809switch (len) {
810case 12:
811 c += ((u_int32_t)k[11]) << 24;
812 OS_FALLTHROUGH;
813case 11:
814 c += ((u_int32_t)k[10]) << 16;
815 OS_FALLTHROUGH;
816case 10:
817 c += ((u_int32_t)k[9]) << 8;
818 OS_FALLTHROUGH;
819case 9:
820 c += k[8];
821 OS_FALLTHROUGH;
822case 8:
823 b += ((u_int32_t)k[7]) << 24;
824 OS_FALLTHROUGH;
825case 7:
826 b += ((u_int32_t)k[6]) << 16;
827 OS_FALLTHROUGH;
828case 6:
829 b += ((u_int32_t)k[5]) << 8;
830 OS_FALLTHROUGH;
831case 5:
832 b += k[4];
833 OS_FALLTHROUGH;
834case 4:
835 a += ((u_int32_t)k[3]) << 24;
836 OS_FALLTHROUGH;
837case 3:
838 a += ((u_int32_t)k[2]) << 16;
839 OS_FALLTHROUGH;
840case 2:
841 a += ((u_int32_t)k[1]) << 8;
842 OS_FALLTHROUGH;
843case 1:
844 a += k[0];
845 break;
846
847case 0:
848 /* zero length requires no mixing */
849 return c;
850}
851
852JHASH_FINAL(a, b, c);
853
854return c;
855#endif /* !defined(__i386__) && !defined(__x86_64__) */
856}
857#endif /* LITTLE_ENDIAN */
858