1// SPDX-License-Identifier: GPL-2.0
2// Copyright (c) 2019 Facebook
3#include <features.h>
4
5typedef unsigned int u32;
6
7static __always_inline u32 rol32(u32 word, unsigned int shift)
8{
9 return (word << shift) | (word >> ((-shift) & 31));
10}
11
12#define __jhash_mix(a, b, c) \
13{ \
14 a -= c; a ^= rol32(c, 4); c += b; \
15 b -= a; b ^= rol32(a, 6); a += c; \
16 c -= b; c ^= rol32(b, 8); b += a; \
17 a -= c; a ^= rol32(c, 16); c += b; \
18 b -= a; b ^= rol32(a, 19); a += c; \
19 c -= b; c ^= rol32(b, 4); b += a; \
20}
21
22#define __jhash_final(a, b, c) \
23{ \
24 c ^= b; c -= rol32(b, 14); \
25 a ^= c; a -= rol32(c, 11); \
26 b ^= a; b -= rol32(a, 25); \
27 c ^= b; c -= rol32(b, 16); \
28 a ^= c; a -= rol32(c, 4); \
29 b ^= a; b -= rol32(a, 14); \
30 c ^= b; c -= rol32(b, 24); \
31}
32
33#define JHASH_INITVAL 0xdeadbeef
34
35static ATTR
36u32 jhash(const void *key, u32 length, u32 initval)
37{
38 u32 a, b, c;
39 const unsigned char *k = key;
40
41 a = b = c = JHASH_INITVAL + length + initval;
42
43 while (length > 12) {
44 a += *(volatile u32 *)(k);
45 b += *(volatile u32 *)(k + 4);
46 c += *(volatile u32 *)(k + 8);
47 __jhash_mix(a, b, c);
48 length -= 12;
49 k += 12;
50 }
51 switch (length) {
52 case 12: c += (u32)k[11]<<24;
53 case 11: c += (u32)k[10]<<16;
54 case 10: c += (u32)k[9]<<8;
55 case 9: c += k[8];
56 case 8: b += (u32)k[7]<<24;
57 case 7: b += (u32)k[6]<<16;
58 case 6: b += (u32)k[5]<<8;
59 case 5: b += k[4];
60 case 4: a += (u32)k[3]<<24;
61 case 3: a += (u32)k[2]<<16;
62 case 2: a += (u32)k[1]<<8;
63 case 1: a += k[0];
64 c ^= a;
65 __jhash_final(a, b, c);
66 case 0: /* Nothing left to add */
67 break;
68 }
69
70 return c;
71}
72
73static __always_inline u32 jhash2(const u32 *k, u32 length, u32 initval)
74{
75 u32 a, b, c;
76
77 /* Set up the internal state */
78 a = b = c = JHASH_INITVAL + (length<<2) + initval;
79
80 /* Handle most of the key */
81 while (length > 3) {
82 a += k[0];
83 b += k[1];
84 c += k[2];
85 __jhash_mix(a, b, c);
86 length -= 3;
87 k += 3;
88 }
89
90 /* Handle the last 3 u32's */
91 switch (length) {
92 case 3: c += k[2];
93 case 2: b += k[1];
94 case 1: a += k[0];
95 __jhash_final(a, b, c);
96 break;
97 case 0: /* Nothing left to add */
98 break;
99 }
100
101 return c;
102}
103

source code of linux/tools/testing/selftests/bpf/progs/test_jhash.h