| 1 |
|
| /* CityHash128, v1.0.2 ("cityhash102"). Ported from Google CityHash |
| 2 |
|
| * v1.0.2 (Geoff Pike, Jyrki Alakuijala; MIT license), the same revision |
| 3 |
|
| * ClickHouse keeps under contrib/cityhash102/ and uses for its |
| 4 |
|
| * compressed-block 16-byte checksum. |
| 5 |
|
| * |
| 6 |
|
| * This file only implements CityHash128 (without seed) - the seeded |
| 7 |
|
| * helpers, CityHash64, and the CRC32-accelerated CityHashCrc128 are |
| 8 |
|
| * all skipped because the only ClickHouse-Encoder caller is the |
| 9 |
|
| * CompressedReadBuffer / CompressedWriteBuffer block-prefix hash. */ |
| 10 |
|
| |
| 11 |
|
| #include <stdint.h> |
| 12 |
|
| #include <string.h> |
| 13 |
|
| #include <stddef.h> |
| 14 |
|
| |
| 15 |
|
| #include "cityhash.h" |
| 16 |
|
| |
| 17 |
|
| /* Magic constants from CityHash v1.0.2. */ |
| 18 |
|
| static const uint64_t k0 = 0xc3a5c85c97cb3127ULL; |
| 19 |
|
| static const uint64_t k1 = 0xb492b66fbe98f273ULL; |
| 20 |
|
| static const uint64_t k2 = 0x9ae16a3b2f90404fULL; |
| 21 |
|
| static const uint64_t k3 = 0xc949d7c7509e6557ULL; |
| 22 |
|
| |
| 23 |
|
| /* Little-endian byte loads via memcpy. On LE hosts the compiler |
| 24 |
|
| * collapses these to a single load; on BE hosts we explicitly byte- |
| 25 |
|
| * swap so the algorithm sees identical integer values across hosts. */ |
| 26 |
3831 |
| static inline uint64_t Fetch64(const char *p) { |
| 27 |
|
| uint64_t v; |
| 28 |
3831 |
| memcpy(&v, p, 8); |
| 29 |
|
| #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ |
| 30 |
|
| v = ((v & 0x00000000000000ffULL) << 56) |
| 31 |
|
| | ((v & 0x000000000000ff00ULL) << 40) |
| 32 |
|
| | ((v & 0x0000000000ff0000ULL) << 24) |
| 33 |
|
| | ((v & 0x00000000ff000000ULL) << 8) |
| 34 |
|
| | ((v & 0x000000ff00000000ULL) >> 8) |
| 35 |
|
| | ((v & 0x0000ff0000000000ULL) >> 24) |
| 36 |
|
| | ((v & 0x00ff000000000000ULL) >> 40) |
| 37 |
|
| | ((v & 0xff00000000000000ULL) >> 56); |
| 38 |
|
| #endif |
| 39 |
3831 |
| return v; |
| 40 |
|
| } |
| 41 |
|
| |
| 42 |
8 |
| static inline uint32_t Fetch32(const char *p) { |
| 43 |
|
| uint32_t v; |
| 44 |
8 |
| memcpy(&v, p, 4); |
| 45 |
|
| #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ |
| 46 |
|
| v = ((v & 0x000000ffU) << 24) |
| 47 |
|
| | ((v & 0x0000ff00U) << 8) |
| 48 |
|
| | ((v & 0x00ff0000U) >> 8) |
| 49 |
|
| | ((v & 0xff000000U) >> 24); |
| 50 |
|
| #endif |
| 51 |
8 |
| return v; |
| 52 |
|
| } |
| 53 |
|
| |
| 54 |
2632 |
| static inline uint64_t Rotate(uint64_t v, int n) { |
| 55 |
|
| /* Reference impl returns `v` unchanged when n == 0 (avoiding UB |
| 56 |
|
| * from `v >> 64`). All call sites pass n in 1..63, but mirror the |
| 57 |
|
| * guard so a future-added caller doesn't trip on it. */ |
| 58 |
2632 |
▶ | return n == 0 ? v : ((v >> n) | (v << (64 - n))); |
Branch: 1 branch
| Branch | True | False | Total |
| return n == 0 ? v : ((v >> n) | (v << (64 - n))); |
2632 |
0 |
2632 |
|
| 59 |
|
| } |
| 60 |
|
| |
| 61 |
10 |
| static inline uint64_t RotateByAtLeast1(uint64_t v, int n) { |
| 62 |
10 |
| return (v >> n) | (v << (64 - n)); |
| 63 |
|
| } |
| 64 |
|
| |
| 65 |
95 |
| static inline uint64_t ShiftMix(uint64_t v) { |
| 66 |
95 |
| return v ^ (v >> 47); |
| 67 |
|
| } |
| 68 |
|
| |
| 69 |
267 |
| static inline uint64_t Hash128to64(uint64_t low, uint64_t high) { |
| 70 |
|
| static const uint64_t kMul = 0x9ddfea08eb382d69ULL; |
| 71 |
267 |
| uint64_t a = (low ^ high) * kMul; |
| 72 |
267 |
| a ^= (a >> 47); |
| 73 |
267 |
| uint64_t b = (high ^ a) * kMul; |
| 74 |
267 |
| b ^= (b >> 47); |
| 75 |
267 |
| b *= kMul; |
| 76 |
267 |
| return b; |
| 77 |
|
| } |
| 78 |
|
| |
| 79 |
267 |
| static inline uint64_t HashLen16(uint64_t u, uint64_t v) { |
| 80 |
267 |
| return Hash128to64(u, v); |
| 81 |
|
| } |
| 82 |
|
| |
| 83 |
16 |
| static uint64_t HashLen0to16(const char *s, size_t len) { |
| 84 |
16 |
▶ | if (len > 8) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (len > 8) { |
10 |
6 |
16 |
|
| 85 |
10 |
| uint64_t a = Fetch64(s); |
| 86 |
10 |
| uint64_t b = Fetch64(s + len - 8); |
| 87 |
10 |
| return HashLen16(a, RotateByAtLeast1(b + len, (int)len)) ^ b; |
| 88 |
|
| } |
| 89 |
6 |
▶ | if (len >= 4) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (len >= 4) { |
4 |
2 |
6 |
|
| 90 |
4 |
| uint64_t a = (uint64_t)Fetch32(s); |
| 91 |
4 |
| return HashLen16(len + (a << 3), |
| 92 |
4 |
| (uint64_t)Fetch32(s + len - 4)); |
| 93 |
|
| } |
| 94 |
2 |
▶ | if (len > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (len > 0) { |
1 |
1 |
2 |
|
| 95 |
1 |
| uint8_t a = (uint8_t)s[0]; |
| 96 |
1 |
| uint8_t b = (uint8_t)s[len >> 1]; |
| 97 |
1 |
| uint8_t c = (uint8_t)s[len - 1]; |
| 98 |
1 |
| uint32_t y = (uint32_t)a + ((uint32_t)b << 8); |
| 99 |
1 |
| uint32_t z = (uint32_t)len + ((uint32_t)c << 2); |
| 100 |
1 |
| return ShiftMix((uint64_t)y * k2 ^ (uint64_t)z * k3) * k2; |
| 101 |
|
| } |
| 102 |
1 |
| return k2; |
| 103 |
|
| } |
| 104 |
|
| |
| 105 |
|
| /* Return a 16-byte hash for 32 bytes plus two seed words. |
| 106 |
|
| * Out is written as out[0] = low, out[1] = high. */ |
| 107 |
700 |
| static void WeakHashLen32WithSeeds_raw( |
| 108 |
|
| uint64_t w, uint64_t x, uint64_t y, uint64_t z, |
| 109 |
|
| uint64_t a, uint64_t b, uint64_t out[2]) { |
| 110 |
700 |
| a += w; |
| 111 |
700 |
| b = Rotate(b + a + z, 21); |
| 112 |
700 |
| uint64_t c = a; |
| 113 |
700 |
| a += x; |
| 114 |
700 |
| a += y; |
| 115 |
700 |
| b += Rotate(a, 44); |
| 116 |
700 |
| out[0] = a + z; |
| 117 |
700 |
| out[1] = b + c; |
| 118 |
700 |
| } |
| 119 |
|
| |
| 120 |
700 |
| static inline void WeakHashLen32WithSeeds( |
| 121 |
|
| const char *s, uint64_t a, uint64_t b, uint64_t out[2]) { |
| 122 |
700 |
| WeakHashLen32WithSeeds_raw(Fetch64(s), |
| 123 |
|
| Fetch64(s + 8), |
| 124 |
|
| Fetch64(s + 16), |
| 125 |
|
| Fetch64(s + 24), |
| 126 |
|
| a, b, out); |
| 127 |
700 |
| } |
| 128 |
|
| |
| 129 |
|
| /* CityMurmur: handles len < 128 inside CityHash128WithSeed. */ |
| 130 |
37 |
| static void CityMurmur(const char *s, size_t len, |
| 131 |
|
| uint64_t seed_low, uint64_t seed_high, |
| 132 |
|
| uint64_t out[2]) { |
| 133 |
37 |
| uint64_t a = seed_low; |
| 134 |
37 |
| uint64_t b = seed_high; |
| 135 |
37 |
| uint64_t c = 0; |
| 136 |
37 |
| uint64_t d = 0; |
| 137 |
|
| /* The reference uses `signed long l = len - 16` then `if (l <= 0)` |
| 138 |
|
| * to bifurcate; with `size_t` we test `len <= 16` directly. */ |
| 139 |
37 |
▶ | if (len <= 16) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (len <= 16) { |
16 |
21 |
37 |
|
| 140 |
16 |
| a = ShiftMix(a * k1) * k1; |
| 141 |
16 |
| c = b * k1 + HashLen0to16(s, len); |
| 142 |
16 |
▶ | d = ShiftMix(a + (len >= 8 ? Fetch64(s) : c)); |
Branch: 1 branch
| Branch | True | False | Total |
| d = ShiftMix(a + (len >= 8 ? Fetch64(s) : c)); |
12 |
4 |
16 |
|
| 143 |
|
| } else { |
| 144 |
21 |
| c = HashLen16(Fetch64(s + len - 8) + k1, a); |
| 145 |
21 |
| d = HashLen16(b + len, c + Fetch64(s + len - 16)); |
| 146 |
21 |
| a += d; |
| 147 |
21 |
| size_t l = len - 16; |
| 148 |
|
| do { |
| 149 |
31 |
| a ^= ShiftMix(Fetch64(s) * k1) * k1; |
| 150 |
31 |
| a *= k1; |
| 151 |
31 |
| b ^= a; |
| 152 |
31 |
| c ^= ShiftMix(Fetch64(s + 8) * k1) * k1; |
| 153 |
31 |
| c *= k1; |
| 154 |
31 |
| d ^= c; |
| 155 |
31 |
| s += 16; |
| 156 |
31 |
| l = (l > 16) ? (l - 16) : 0; |
| 157 |
31 |
▶ | } while (l > 0); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (l > 0); |
10 |
21 |
31 |
|
| 158 |
|
| } |
| 159 |
37 |
| a = HashLen16(a, c); |
| 160 |
37 |
| b = HashLen16(d, b); |
| 161 |
37 |
| out[0] = a ^ b; |
| 162 |
37 |
| out[1] = HashLen16(b, a); |
| 163 |
37 |
| } |
| 164 |
|
| |
| 165 |
62 |
| static void CityHash128WithSeed(const char *s, size_t len, |
| 166 |
|
| uint64_t seed_low, uint64_t seed_high, |
| 167 |
|
| uint64_t out[2]) { |
| 168 |
62 |
▶ | if (len < 128) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (len < 128) { |
37 |
25 |
62 |
|
| 169 |
37 |
| CityMurmur(s, len, seed_low, seed_high, out); |
| 170 |
37 |
| return; |
| 171 |
|
| } |
| 172 |
|
| /* Long-input path: 56 bytes of rolling state, eats input in |
| 173 |
|
| * 128-byte chunks (two 64-byte halves per loop iteration). */ |
| 174 |
|
| uint64_t v[2], w[2]; |
| 175 |
25 |
| uint64_t x = seed_low; |
| 176 |
25 |
| uint64_t y = seed_high; |
| 177 |
25 |
| uint64_t z = len * k1; |
| 178 |
25 |
| v[0] = Rotate(y ^ k1, 49) * k1 + Fetch64(s); |
| 179 |
25 |
| v[1] = Rotate(v[0], 42) * k1 + Fetch64(s + 8); |
| 180 |
25 |
| w[0] = Rotate(y + z, 35) * k1 + x; |
| 181 |
25 |
| w[1] = Rotate(x + Fetch64(s + 88), 53) * k1; |
| 182 |
|
| |
| 183 |
|
| do { |
| 184 |
159 |
| x = Rotate(x + y + v[0] + Fetch64(s + 16), 37) * k1; |
| 185 |
159 |
| y = Rotate(y + v[1] + Fetch64(s + 48), 42) * k1; |
| 186 |
159 |
| x ^= w[1]; |
| 187 |
159 |
| y ^= v[0]; |
| 188 |
159 |
| z = Rotate(z ^ w[0], 33); |
| 189 |
159 |
| WeakHashLen32WithSeeds(s, v[1] * k1, x + w[0], v); |
| 190 |
159 |
| WeakHashLen32WithSeeds(s + 32, z + w[1], y, w); |
| 191 |
159 |
| { uint64_t t = z; z = x; x = t; } |
| 192 |
159 |
| s += 64; |
| 193 |
159 |
| x = Rotate(x + y + v[0] + Fetch64(s + 16), 37) * k1; |
| 194 |
159 |
| y = Rotate(y + v[1] + Fetch64(s + 48), 42) * k1; |
| 195 |
159 |
| x ^= w[1]; |
| 196 |
159 |
| y ^= v[0]; |
| 197 |
159 |
| z = Rotate(z ^ w[0], 33); |
| 198 |
159 |
| WeakHashLen32WithSeeds(s, v[1] * k1, x + w[0], v); |
| 199 |
159 |
| WeakHashLen32WithSeeds(s + 32, z + w[1], y, w); |
| 200 |
159 |
| { uint64_t t = z; z = x; x = t; } |
| 201 |
159 |
| s += 64; |
| 202 |
159 |
| len -= 128; |
| 203 |
159 |
▶ | } while (len >= 128); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (len >= 128); |
134 |
25 |
159 |
|
| 204 |
|
| |
| 205 |
25 |
| y += Rotate(w[0], 37) * k0 + z; |
| 206 |
25 |
| x += Rotate(v[0] + z, 49) * k0; |
| 207 |
|
| /* If 0 < len < 128, hash the tail in 32-byte chunks from the END |
| 208 |
|
| * of the input. tail_done starts at 0 and grows by 32 each iter. */ |
| 209 |
|
| { |
| 210 |
25 |
| size_t tail_done = 0; |
| 211 |
89 |
▶ | while (tail_done < len) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (tail_done < len) { |
64 |
25 |
89 |
|
| 212 |
64 |
| tail_done += 32; |
| 213 |
64 |
| y = Rotate(y - x, 42) * k0 + v[1]; |
| 214 |
64 |
| w[0] += Fetch64(s + len - tail_done + 16); |
| 215 |
64 |
| x = Rotate(x, 49) * k0 + w[0]; |
| 216 |
64 |
| w[0] += v[0]; |
| 217 |
64 |
| WeakHashLen32WithSeeds(s + len - tail_done, |
| 218 |
|
| v[0], v[1], v); |
| 219 |
|
| } |
| 220 |
|
| } |
| 221 |
|
| /* Final mix. */ |
| 222 |
25 |
| x = HashLen16(x, v[0]); |
| 223 |
25 |
| y = HashLen16(y, w[0]); |
| 224 |
25 |
| out[0] = HashLen16(x + v[1], w[1]) + y; |
| 225 |
25 |
| out[1] = HashLen16(x + w[1], y + v[1]); |
| 226 |
|
| } |
| 227 |
|
| |
| 228 |
62 |
| void cityhash128_v102(const char *s, size_t len, unsigned char out[16]) { |
| 229 |
|
| uint64_t hash[2]; |
| 230 |
62 |
▶ | if (len >= 16) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (len >= 16) { |
60 |
2 |
62 |
|
| 231 |
120 |
| CityHash128WithSeed(s + 16, len - 16, |
| 232 |
60 |
| Fetch64(s) ^ k3, Fetch64(s + 8), |
| 233 |
|
| hash); |
| 234 |
2 |
▶ | } else if (len >= 8) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (len >= 8) { |
0 |
2 |
2 |
|
| 235 |
0 |
| CityHash128WithSeed(NULL, 0, |
| 236 |
0 |
| Fetch64(s) ^ ((uint64_t)len * k0), |
| 237 |
0 |
| Fetch64(s + len - 8) ^ k1, |
| 238 |
|
| hash); |
| 239 |
|
| } else { |
| 240 |
2 |
| CityHash128WithSeed(s, len, k0, k1, hash); |
| 241 |
|
| } |
| 242 |
|
| /* Pack low half then high half as 16 little-endian bytes. */ |
| 243 |
|
| int i; |
| 244 |
558 |
▶ | for (i = 0; i < 8; i++) out[i] = (unsigned char)(hash[0] >> (i * 8)); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 8; i++) out[i] = (unsigned char)(hash[0] >> (i * 8)); |
496 |
62 |
558 |
|
| 245 |
558 |
▶ | for (i = 0; i < 8; i++) out[8 + i] = (unsigned char)(hash[1] >> (i * 8)); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 8; i++) out[8 + i] = (unsigned char)(hash[1] >> (i * 8)); |
496 |
62 |
558 |
|
| 246 |
62 |
| } |