1 | // SPDX-License-Identifier: GPL-2.0 |
2 | // Copyright (c) 2019 Facebook |
3 | #include <features.h> |
4 | |
5 | typedef unsigned int u32; |
6 | |
7 | static __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 | |
35 | static ATTR |
36 | u32 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 | |
73 | static __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 | |