| 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 */ |