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