1 // SPDX-License-Identifier: LGPL-2.1+
2 /*
3 * MurmurHash3 was written by Austin Appleby, and is placed in the public
4 * domain. The author hereby disclaims copyright to this source code.
5 *
6 * Adapted by John Wiele (jwiele@redhat.com).
7 */
8
9 #include "murmurhash3.h"
10
11 #include <linux/unaligned.h>
12
rotl64(u64 x,s8 r)13 static inline u64 rotl64(u64 x, s8 r)
14 {
15 return (x << r) | (x >> (64 - r));
16 }
17
18 #define ROTL64(x, y) rotl64(x, y)
19
20 /* Finalization mix - force all bits of a hash block to avalanche */
21
fmix64(u64 k)22 static __always_inline u64 fmix64(u64 k)
23 {
24 k ^= k >> 33;
25 k *= 0xff51afd7ed558ccdLLU;
26 k ^= k >> 33;
27 k *= 0xc4ceb9fe1a85ec53LLU;
28 k ^= k >> 33;
29
30 return k;
31 }
32
murmurhash3_128(const void * key,const int len,const u32 seed,void * out)33 void murmurhash3_128(const void *key, const int len, const u32 seed, void *out)
34 {
35 const u8 *data = key;
36 const int nblocks = len / 16;
37
38 u64 h1 = seed;
39 u64 h2 = seed;
40
41 const u64 c1 = 0x87c37b91114253d5LLU;
42 const u64 c2 = 0x4cf5ad432745937fLLU;
43
44 u64 *hash_out = out;
45
46 /* body */
47
48 const u64 *blocks = (const u64 *)(data);
49
50 int i;
51
52 for (i = 0; i < nblocks; i++) {
53 u64 k1 = get_unaligned_le64(&blocks[i * 2]);
54 u64 k2 = get_unaligned_le64(&blocks[i * 2 + 1]);
55
56 k1 *= c1;
57 k1 = ROTL64(k1, 31);
58 k1 *= c2;
59 h1 ^= k1;
60
61 h1 = ROTL64(h1, 27);
62 h1 += h2;
63 h1 = h1 * 5 + 0x52dce729;
64
65 k2 *= c2;
66 k2 = ROTL64(k2, 33);
67 k2 *= c1;
68 h2 ^= k2;
69
70 h2 = ROTL64(h2, 31);
71 h2 += h1;
72 h2 = h2 * 5 + 0x38495ab5;
73 }
74
75 /* tail */
76
77 {
78 const u8 *tail = (const u8 *)(data + nblocks * 16);
79
80 u64 k1 = 0;
81 u64 k2 = 0;
82
83 switch (len & 15) {
84 case 15:
85 k2 ^= ((u64)tail[14]) << 48;
86 fallthrough;
87 case 14:
88 k2 ^= ((u64)tail[13]) << 40;
89 fallthrough;
90 case 13:
91 k2 ^= ((u64)tail[12]) << 32;
92 fallthrough;
93 case 12:
94 k2 ^= ((u64)tail[11]) << 24;
95 fallthrough;
96 case 11:
97 k2 ^= ((u64)tail[10]) << 16;
98 fallthrough;
99 case 10:
100 k2 ^= ((u64)tail[9]) << 8;
101 fallthrough;
102 case 9:
103 k2 ^= ((u64)tail[8]) << 0;
104 k2 *= c2;
105 k2 = ROTL64(k2, 33);
106 k2 *= c1;
107 h2 ^= k2;
108 fallthrough;
109
110 case 8:
111 k1 ^= ((u64)tail[7]) << 56;
112 fallthrough;
113 case 7:
114 k1 ^= ((u64)tail[6]) << 48;
115 fallthrough;
116 case 6:
117 k1 ^= ((u64)tail[5]) << 40;
118 fallthrough;
119 case 5:
120 k1 ^= ((u64)tail[4]) << 32;
121 fallthrough;
122 case 4:
123 k1 ^= ((u64)tail[3]) << 24;
124 fallthrough;
125 case 3:
126 k1 ^= ((u64)tail[2]) << 16;
127 fallthrough;
128 case 2:
129 k1 ^= ((u64)tail[1]) << 8;
130 fallthrough;
131 case 1:
132 k1 ^= ((u64)tail[0]) << 0;
133 k1 *= c1;
134 k1 = ROTL64(k1, 31);
135 k1 *= c2;
136 h1 ^= k1;
137 break;
138 default:
139 break;
140 }
141 }
142 /* finalization */
143
144 h1 ^= len;
145 h2 ^= len;
146
147 h1 += h2;
148 h2 += h1;
149
150 h1 = fmix64(h1);
151 h2 = fmix64(h2);
152
153 h1 += h2;
154 h2 += h1;
155
156 put_unaligned_le64(h1, &hash_out[0]);
157 put_unaligned_le64(h2, &hash_out[1]);
158 }
159