Debian Codegraph @

libdrgn/cityhash.h

raw
1 // Copyright (c) Meta Platforms, Inc. and affiliates.
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3
4 #ifndef DRGN_CITYHASH_H
5 #define DRGN_CITYHASH_H
6
7 #include <byteswap.h>
8 #include <stddef.h>
9 #include <stdint.h>
10
11 static inline uint32_t cityhash_fetch32(const uint8_t *p)
12 {
13 return ((uint32_t)p[0] |
14 ((uint32_t)p[1] << 8) |
15 ((uint32_t)p[2] << 16) |
16 ((uint32_t)p[3] << 24));
17 }
18
19 static inline uint64_t cityhash_fetch64(const uint8_t *p)
20 {
21 return ((uint64_t)p[0] |
22 ((uint64_t)p[1] << 8) |
23 ((uint64_t)p[2] << 16) |
24 ((uint64_t)p[3] << 24) |
25 ((uint64_t)p[4] << 32) |
26 ((uint64_t)p[5] << 40) |
27 ((uint64_t)p[6] << 48) |
28 ((uint64_t)p[7] << 56));
29 }
30
31 #define cityhash_c1 UINT32_C(0xcc9e2d51)
32 #define cityhash_c2 UINT32_C(0x1b873593)
33 #define cityhash_c3 UINT32_C(0xe6546b64)
34
35 static uint32_t cityhash_fmix(uint32_t h)
36 {
37 h ^= h >> 16;
38 h *= UINT32_C(0x85ebca6b);
39 h ^= h >> 13;
40 h *= UINT32_C(0xc2b2ae35);
41 h ^= h >> 16;
42 return h;
43 }
44
45 static uint32_t cityhash_rotate32(uint32_t x, int b) {
46 return b == 0 ? x : (x >> b) | (x << (32 - b));
47 }
48
49 static uint32_t cityhash_mur(uint32_t a, uint32_t h) {
50 a *= cityhash_c1;
51 a = cityhash_rotate32(a, 17);
52 a *= cityhash_c2;
53 h ^= a;
54 h = cityhash_rotate32(h, 19);
55 return h * 5 + cityhash_c3;
56 }
57
58 static uint32_t cityhash32_len_13to24(const uint8_t *s, size_t len) {
59 uint32_t a = cityhash_fetch32(s - 4 + (len >> 1));
60 uint32_t b = cityhash_fetch32(s + 4);
61 uint32_t c = cityhash_fetch32(s + len - 8);
62 uint32_t d = cityhash_fetch32(s + (len >> 1));
63 uint32_t e = cityhash_fetch32(s);
64 uint32_t f = cityhash_fetch32(s + len - 4);
65 uint32_t h = len;
66
67 return cityhash_fmix(cityhash_mur(f, cityhash_mur(e, cityhash_mur(d, cityhash_mur(c, cityhash_mur(b, cityhash_mur(a, h)))))));
68 }
69
70 static uint32_t cityhash32_len_0to4(const uint8_t *s, size_t len) {
71 uint32_t b = 0;
72 uint32_t c = 9;
73 for (size_t i = 0; i < len; i++) {
74 signed char v = s[i];
75 b = b * cityhash_c1 + v;
76 c ^= b;
77 }
78 return cityhash_fmix(cityhash_mur(b, cityhash_mur(len, c)));
79 }
80
81 static uint32_t cityhash32_len_5to12(const uint8_t *s, size_t len) {
82 uint32_t a = len, b = len * 5, c = 9, d = b;
83 a += cityhash_fetch32(s);
84 b += cityhash_fetch32(s + len - 4);
85 c += cityhash_fetch32(s + ((len >> 1) & 4));
86 return cityhash_fmix(cityhash_mur(c, cityhash_mur(b, cityhash_mur(a, d))));
87 }
88
89 __attribute__((__unused__))
90 static uint32_t cityhash32(const void *data, size_t len) {
91 const uint8_t *s = data;
92
93 if (len <= 4)
94 return cityhash32_len_0to4(s, len);
95 else if (len <= 12)
96 return cityhash32_len_5to12(s, len);
97 else if (len <= 24)
98 return cityhash32_len_13to24(s, len);
99
100 uint32_t h = len, g = cityhash_c1 * len, f = g;
101 uint32_t a0 = cityhash_rotate32(cityhash_fetch32(s + len - 4) * cityhash_c1, 17) * cityhash_c2;
102 uint32_t a1 = cityhash_rotate32(cityhash_fetch32(s + len - 8) * cityhash_c1, 17) * cityhash_c2;
103 uint32_t a2 = cityhash_rotate32(cityhash_fetch32(s + len - 16) * cityhash_c1, 17) * cityhash_c2;
104 uint32_t a3 = cityhash_rotate32(cityhash_fetch32(s + len - 12) * cityhash_c1, 17) * cityhash_c2;
105 uint32_t a4 = cityhash_rotate32(cityhash_fetch32(s + len - 20) * cityhash_c1, 17) * cityhash_c2;
106 h ^= a0;
107 h = cityhash_rotate32(h, 19);
108 h = h * 5 + cityhash_c3;
109 h ^= a2;
110 h = cityhash_rotate32(h, 19);
111 h = h * 5 + cityhash_c3;
112 g ^= a1;
113 g = cityhash_rotate32(g, 19);
114 g = g * 5 + cityhash_c3;
115 g ^= a3;
116 g = cityhash_rotate32(g, 19);
117 g = g * 5 + cityhash_c3;
118 f += a4;
119 f = cityhash_rotate32(f, 19);
120 f = f * 5 + cityhash_c3;
121 size_t iters = (len - 1) / 20;
122 do {
123 a0 = cityhash_rotate32(cityhash_fetch32(s) * cityhash_c1, 17) * cityhash_c2;
124 a1 = cityhash_fetch32(s + 4);
125 a2 = cityhash_rotate32(cityhash_fetch32(s + 8) * cityhash_c1, 17) * cityhash_c2;
126 a3 = cityhash_rotate32(cityhash_fetch32(s + 12) * cityhash_c1, 17) * cityhash_c2;
127 a4 = cityhash_fetch32(s + 16);
128 h ^= a0;
129 h = cityhash_rotate32(h, 18);
130 h = h * 5 + cityhash_c3;
131 f += a1;
132 f = cityhash_rotate32(f, 19);
133 f = f * cityhash_c1;
134 g += a2;
135 g = cityhash_rotate32(g, 18);
136 g = g * 5 + cityhash_c3;
137 h ^= a3 + a1;
138 h = cityhash_rotate32(h, 19);
139 h = h * 5 + cityhash_c3;
140 g ^= a4;
141 g = bswap_32(g) * 5;
142 h += a4 * 5;
143 h = bswap_32(h);
144 f += a0;
145 uint32_t tmp;
146 tmp = f;
147 f = g;
148 g = h;
149 h = tmp;
150 s += 20;
151 } while (--iters != 0);
152 g = cityhash_rotate32(g, 11) * cityhash_c1;
153 g = cityhash_rotate32(g, 17) * cityhash_c1;
154 f = cityhash_rotate32(f, 11) * cityhash_c1;
155 f = cityhash_rotate32(f, 17) * cityhash_c1;
156 h = cityhash_rotate32(h + g, 19);
157 h = h * 5 + cityhash_c3;
158 h = cityhash_rotate32(h, 17) * cityhash_c1;
159 h = cityhash_rotate32(h + f, 19);
160 h = h * 5 + cityhash_c3;
161 h = cityhash_rotate32(h, 17) * cityhash_c1;
162 return h;
163 }
164
165 struct cityhash_pair {
166 uint64_t first;
167 uint64_t second;
168 };
169
170 #define cityhash_k0 UINT64_C(0xc3a5c85c97cb3127)
171 #define cityhash_k1 UINT64_C(0xb492b66fbe98f273)
172 #define cityhash_k2 UINT64_C(0x9ae16a3b2f90404f)
173
174 static inline uint64_t cityhash_rotate(uint64_t x, int b)
175 {
176 return b == 0 ? x : (x >> b) | (x << (64 - b));
177 }
178
179 static inline uint64_t cityhash_shiftmix(uint64_t val)
180 {
181 return val ^ (val >> 47);
182 }
183
184 static inline uint64_t cityhash_128_to_64(uint64_t lo, uint64_t hi) {
185 static const uint64_t mul = UINT64_C(0x9ddfea08eb382d69);
186 uint64_t a = (lo ^ hi) * mul;
187 a ^= (a >> 47);
188 uint64_t b = (hi ^ a) * mul;
189 b ^= (b >> 47);
190 b *= mul;
191 return b;
192 }
193
194 static inline uint64_t cityhash_len_16(uint64_t u, uint64_t v, uint64_t mul)
195 {
196 uint64_t a = (u ^ v) * mul;
197 a ^= (a >> 47);
198 uint64_t b = (v ^ a) * mul;
199 b ^= (b >> 47);
200 b *= mul;
201 return b;
202 }
203
204 static uint64_t cityhash_len_0to16(const uint8_t *s, size_t len)
205 {
206 if (len == 0) {
207 return cityhash_k2;
208 } else if (len < 4) {
209 uint8_t a = s[0];
210 uint8_t b = s[len >> 1];
211 uint8_t c = s[len - 1];
212 uint32_t y = (uint32_t)a + ((uint32_t)b << 8);
213 uint32_t z = len + ((uint32_t)c << 2);
214 return cityhash_shiftmix(y * cityhash_k2 ^ z * cityhash_k0) * cityhash_k2;
215 } else if (len < 8) {
216 uint64_t mul = cityhash_k2 + len * 2;
217 uint64_t a = cityhash_fetch32(s);
218 return cityhash_len_16(len + (a << 3),
219 cityhash_fetch32(s + len - 4), mul);
220 } else {
221 uint64_t mul = cityhash_k2 + len * 2;
222 uint64_t a = cityhash_fetch64(s) + cityhash_k2;
223 uint64_t b = cityhash_fetch64(s + len - 8);
224 uint64_t c = cityhash_rotate(b, 37) * mul + a;
225 uint64_t d = (cityhash_rotate(a, 25) + b) * mul;
226 return cityhash_len_16(c, d, mul);
227 }
228 }
229
230 static uint64_t cityhash_len_17to32(const uint8_t *s, size_t len)
231 {
232 uint64_t mul = cityhash_k2 + len * 2;
233 uint64_t a = cityhash_fetch64(s) * cityhash_k1;
234 uint64_t b = cityhash_fetch64(s + 8);
235 uint64_t c = cityhash_fetch64(s + len - 8) * mul;
236 uint64_t d = cityhash_fetch64(s + len - 16) * cityhash_k2;
237 return cityhash_len_16(cityhash_rotate(a + b, 43) +
238 cityhash_rotate(c, 30) + d,
239 a + cityhash_rotate(b + cityhash_k2, 18) + c,
240 mul);
241 }
242
243 static struct cityhash_pair cityhash_weak_len_32_with_seeds(const uint8_t *s,
244 uint64_t a,
245 uint64_t b)
246 {
247 uint64_t w = cityhash_fetch64(s);
248 uint64_t x = cityhash_fetch64(s + 8);
249 uint64_t y = cityhash_fetch64(s + 16);
250 uint64_t z = cityhash_fetch64(s + 24);
251 a += w;
252 b = cityhash_rotate(b + a + z, 21);
253 uint64_t c = a;
254 a += x;
255 a += y;
256 b += cityhash_rotate(a, 44);
257 return (struct cityhash_pair){a + z, b + c};
258 }
259
260 static uint64_t cityhash_len_33to64(const uint8_t *s, size_t len)
261 {
262 uint64_t mul = cityhash_k2 + len * 2;
263 uint64_t a = cityhash_fetch64(s) * cityhash_k2;
264 uint64_t b = cityhash_fetch64(s + 8);
265 uint64_t c = cityhash_fetch64(s + len - 24);
266 uint64_t d = cityhash_fetch64(s + len - 32);
267 uint64_t e = cityhash_fetch64(s + 16) * cityhash_k2;
268 uint64_t f = cityhash_fetch64(s + 24) * 9;
269 uint64_t g = cityhash_fetch64(s + len - 8);
270 uint64_t h = cityhash_fetch64(s + len - 16) * mul;
271 uint64_t u = cityhash_rotate(a + g, 43) + (cityhash_rotate(b, 30) + c) * 9;
272 uint64_t v = ((a + g) ^ d) + f + 1;
273 uint64_t w = bswap_64((u + v) * mul) + h;
274 uint64_t x = cityhash_rotate(e + f, 42) + c;
275 uint64_t y = (bswap_64((v + w) * mul) + g) * mul;
276 uint64_t z = e + f + c;
277 a = bswap_64((x + z) * mul + y) + b;
278 b = cityhash_shiftmix((z + a) * mul + d + h) * mul;
279 return b + x;
280 }
281
282 __attribute__((__unused__))
283 static uint64_t cityhash64(const void *data, size_t len)
284 {
285 const uint8_t *s = data;
286
287 if (len <= 16)
288 return cityhash_len_0to16(s, len);
289 else if (len <= 32)
290 return cityhash_len_17to32(s, len);
291 else if (len <= 64)
292 return cityhash_len_33to64(s, len);
293
294 uint64_t x = cityhash_fetch64(s + len - 40);
295 uint64_t y = (cityhash_fetch64(s + len - 16) +
296 cityhash_fetch64(s + len - 56));
297 uint64_t z = cityhash_128_to_64(cityhash_fetch64(s + len - 48) + len,
298 cityhash_fetch64(s + len - 24));
299 struct cityhash_pair v =
300 cityhash_weak_len_32_with_seeds(s + len - 64, len, z);
301 struct cityhash_pair w =
302 cityhash_weak_len_32_with_seeds(s + len - 32, y + cityhash_k1,
303 x);
304 x = x * cityhash_k1 + cityhash_fetch64(s);
305
306 len = (len - 1) & ~(size_t)63;
307 do {
308 x = (cityhash_rotate(x + y + v.first +
309 cityhash_fetch64(s + 8), 37) *
310 cityhash_k1);
311 y = (cityhash_rotate(y + v.second +
312 cityhash_fetch64(s + 48), 42) *
313 cityhash_k1);
314 x ^= w.second;
315 y += v.first + cityhash_fetch64(s + 40);
316 z = cityhash_rotate(z + w.first, 33) * cityhash_k1;
317 v = cityhash_weak_len_32_with_seeds(s, v.second * cityhash_k1,
318 x + w.first);
319 w = cityhash_weak_len_32_with_seeds(s + 32, z + w.second,
320 y + cityhash_fetch64(s + 16));
321 uint64_t tmp = z;
322 z = x;
323 x = tmp;
324 s += 64;
325 len -= 64;
326 } while (len != 0);
327 return cityhash_128_to_64(cityhash_128_to_64(v.first, w.first) + cityhash_shiftmix(y) * cityhash_k1 + z,
328 cityhash_128_to_64(v.second, w.second) + x);
329 }
330
331 static inline size_t cityhash_size_t(const void *data, size_t len)
332 {
333 if (sizeof(size_t) == sizeof(uint32_t))
334 return cityhash32(data, len);
335 else
336 return cityhash64(data, len);
337 }
338
339 #endif /* DRGN_CITYHASH_H */