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