city.cpp (11287B)
1 // Copyright (c) 2011 Google, Inc. 2 // 3 // Permission is hereby granted, free of charge, to any person obtaining a copy 4 // of this software and associated documentation files (the "Software"), to deal 5 // in the Software without restriction, including without limitation the rights 6 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 7 // copies of the Software, and to permit persons to whom the Software is 8 // furnished to do so, subject to the following conditions: 9 // 10 // The above copyright notice and this permission notice shall be included in 11 // all copies or substantial portions of the Software. 12 // 13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 19 // THE SOFTWARE. 20 // 21 // CityHash Version 1, by Geoff Pike and Jyrki Alakuijala 22 // 23 // This file provides CityHash64() and related functions. 24 // 25 // It's probably possible to create even faster hash functions by 26 // writing a program that systematically explores some of the space of 27 // possible hash functions, by using SIMD instructions, or by 28 // compromising on hash quality. 29 30 #include "city.h" 31 32 #include <algorithm> 33 34 using namespace std; 35 36 #if __sparc__ 37 #include <string.h> 38 static inline uint64 UNALIGNED_LOAD64(const char *p) { 39 uint64 val; 40 memcpy(&val, p, sizeof(uint64)); 41 return val; 42 } 43 44 static inline uint32 UNALIGNED_LOAD32(const char *p) { 45 uint32 val; 46 memcpy(&val, p, sizeof(uint32)); 47 return val; 48 } 49 #else 50 #define UNALIGNED_LOAD64(p) (*(const uint64*)(p)) 51 #define UNALIGNED_LOAD32(p) (*(const uint32*)(p)) 52 #endif 53 54 #if !defined(LIKELY) 55 #if defined(__GNUC__) 56 #define LIKELY(x) (__builtin_expect(!!(x), 1)) 57 #else 58 #define LIKELY(x) (x) 59 #endif 60 #endif 61 62 // Some primes between 2^63 and 2^64 for various uses. 63 static const uint64 k0 = 0xc3a5c85c97cb3127; 64 static const uint64 k1 = 0xb492b66fbe98f273; 65 static const uint64 k2 = 0x9ae16a3b2f90404f; 66 static const uint64 k3 = 0xc949d7c7509e6557; 67 68 // Bitwise right rotate. Normally this will compile to a single 69 // instruction, especially if the shift is a manifest constant. 70 static uint64 Rotate(uint64 val, int shift) { 71 // Avoid shifting by 64: doing so yields an undefined result. 72 return shift == 0 ? val : ((val >> shift) | (val << (64 - shift))); 73 } 74 75 // Equivalent to Rotate(), but requires the second arg to be non-zero. 76 // On x86-64, and probably others, it's possible for this to compile 77 // to a single instruction if both args are already in registers. 78 static uint64 RotateByAtLeast1(uint64 val, int shift) { 79 return (val >> shift) | (val << (64 - shift)); 80 } 81 82 static uint64 ShiftMix(uint64 val) { 83 return val ^ (val >> 47); 84 } 85 86 static uint64 HashLen16(uint64 u, uint64 v) { 87 return Hash128to64(uint128(u, v)); 88 } 89 90 static uint64 HashLen0to16(const char *s, size_t len) { 91 if (len > 8) { 92 uint64 a = UNALIGNED_LOAD64(s); 93 uint64 b = UNALIGNED_LOAD64(s + len - 8); 94 return HashLen16(a, RotateByAtLeast1(b + len, len)) ^ b; 95 } 96 if (len >= 4) { 97 uint64 a = UNALIGNED_LOAD32(s); 98 return HashLen16(len + (a << 3), UNALIGNED_LOAD32(s + len - 4)); 99 } 100 if (len > 0) { 101 uint8 a = s[0]; 102 uint8 b = s[len >> 1]; 103 uint8 c = s[len - 1]; 104 uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8); 105 uint32 z = len + (static_cast<uint32>(c) << 2); 106 return ShiftMix(y * k2 ^ z * k3) * k2; 107 } 108 return k2; 109 } 110 111 // This probably works well for 16-byte strings as well, but it may be overkill 112 // in that case. 113 static uint64 HashLen17to32(const char *s, size_t len) { 114 uint64 a = UNALIGNED_LOAD64(s) * k1; 115 uint64 b = UNALIGNED_LOAD64(s + 8); 116 uint64 c = UNALIGNED_LOAD64(s + len - 8) * k2; 117 uint64 d = UNALIGNED_LOAD64(s + len - 16) * k0; 118 return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d, 119 a + Rotate(b ^ k3, 20) - c + len); 120 } 121 122 // Return a 16-byte hash for 48 bytes. Quick and dirty. 123 // Callers do best to use "random-looking" values for a and b. 124 static pair<uint64, uint64> WeakHashLen32WithSeeds( 125 uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) { 126 a += w; 127 b = Rotate(b + a + z, 21); 128 uint64 c = a; 129 a += x; 130 a += y; 131 b += Rotate(a, 44); 132 return make_pair(a + z, b + c); 133 } 134 135 // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. 136 static pair<uint64, uint64> WeakHashLen32WithSeeds( 137 const char* s, uint64 a, uint64 b) { 138 return WeakHashLen32WithSeeds(UNALIGNED_LOAD64(s), 139 UNALIGNED_LOAD64(s + 8), 140 UNALIGNED_LOAD64(s + 16), 141 UNALIGNED_LOAD64(s + 24), 142 a, 143 b); 144 } 145 146 // Return an 8-byte hash for 33 to 64 bytes. 147 static uint64 HashLen33to64(const char *s, size_t len) { 148 uint64 z = UNALIGNED_LOAD64(s + 24); 149 uint64 a = UNALIGNED_LOAD64(s) + (len + UNALIGNED_LOAD64(s + len - 16)) * k0; 150 uint64 b = Rotate(a + z, 52); 151 uint64 c = Rotate(a, 37); 152 a += UNALIGNED_LOAD64(s + 8); 153 c += Rotate(a, 7); 154 a += UNALIGNED_LOAD64(s + 16); 155 uint64 vf = a + z; 156 uint64 vs = b + Rotate(a, 31) + c; 157 a = UNALIGNED_LOAD64(s + 16) + UNALIGNED_LOAD64(s + len - 32); 158 z = UNALIGNED_LOAD64(s + len - 8); 159 b = Rotate(a + z, 52); 160 c = Rotate(a, 37); 161 a += UNALIGNED_LOAD64(s + len - 24); 162 c += Rotate(a, 7); 163 a += UNALIGNED_LOAD64(s + len - 16); 164 uint64 wf = a + z; 165 uint64 ws = b + Rotate(a, 31) + c; 166 uint64 r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0); 167 return ShiftMix(r * k0 + vs) * k2; 168 } 169 170 uint64 CityHash64(const char *s, size_t len) { 171 if (len <= 32) { 172 if (len <= 16) { 173 return HashLen0to16(s, len); 174 } else { 175 return HashLen17to32(s, len); 176 } 177 } else if (len <= 64) { 178 return HashLen33to64(s, len); 179 } 180 181 // For strings over 64 bytes we hash the end first, and then as we 182 // loop we keep 56 bytes of state: v, w, x, y, and z. 183 uint64 x = UNALIGNED_LOAD64(s); 184 uint64 y = UNALIGNED_LOAD64(s + len - 16) ^ k1; 185 uint64 z = UNALIGNED_LOAD64(s + len - 56) ^ k0; 186 pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, y); 187 pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, len * k1, k0); 188 z += ShiftMix(v.second) * k1; 189 x = Rotate(z + x, 39) * k1; 190 y = Rotate(y, 33) * k1; 191 192 // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks. 193 len = (len - 1) & ~static_cast<size_t>(63); 194 do { 195 x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1; 196 y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1; 197 x ^= w.second; 198 y ^= v.first; 199 z = Rotate(z ^ w.first, 33); 200 v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); 201 w = WeakHashLen32WithSeeds(s + 32, z + w.second, y); 202 std::swap(z, x); 203 s += 64; 204 len -= 64; 205 } while (len != 0); 206 return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z, 207 HashLen16(v.second, w.second) + x); 208 } 209 210 uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed) { 211 return CityHash64WithSeeds(s, len, k2, seed); 212 } 213 214 uint64 CityHash64WithSeeds(const char *s, size_t len, 215 uint64 seed0, uint64 seed1) { 216 return HashLen16(CityHash64(s, len) - seed0, seed1); 217 } 218 219 // A subroutine for CityHash128(). Returns a decent 128-bit hash for strings 220 // of any length representable in an int. Based on City and Murmur. 221 static uint128 CityMurmur(const char *s, size_t len, uint128 seed) { 222 uint64 a = Uint128Low64(seed); 223 uint64 b = Uint128High64(seed); 224 uint64 c = 0; 225 uint64 d = 0; 226 int l = len - 16; 227 if (l <= 0) { // len <= 16 228 c = b * k1 + HashLen0to16(s, len); 229 d = Rotate(a + (len >= 8 ? UNALIGNED_LOAD64(s) : c), 32); 230 } else { // len > 16 231 c = HashLen16(UNALIGNED_LOAD64(s + len - 8) + k1, a); 232 d = HashLen16(b + len, c + UNALIGNED_LOAD64(s + len - 16)); 233 a += d; 234 do { 235 a ^= ShiftMix(UNALIGNED_LOAD64(s) * k1) * k1; 236 a *= k1; 237 b ^= a; 238 c ^= ShiftMix(UNALIGNED_LOAD64(s + 8) * k1) * k1; 239 c *= k1; 240 d ^= c; 241 s += 16; 242 l -= 16; 243 } while (l > 0); 244 } 245 a = HashLen16(a, c); 246 b = HashLen16(d, b); 247 return uint128(a ^ b, HashLen16(b, a)); 248 } 249 250 uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) { 251 if (len < 128) { 252 return CityMurmur(s, len, seed); 253 } 254 255 // We expect len >= 128 to be the common case. Keep 56 bytes of state: 256 // v, w, x, y, and z. 257 pair<uint64, uint64> v, w; 258 uint64 x = Uint128Low64(seed); 259 uint64 y = Uint128High64(seed); 260 uint64 z = len * k1; 261 v.first = Rotate(y ^ k1, 49) * k1 + UNALIGNED_LOAD64(s); 262 v.second = Rotate(v.first, 42) * k1 + UNALIGNED_LOAD64(s + 8); 263 w.first = Rotate(y + z, 35) * k1 + x; 264 w.second = Rotate(x + UNALIGNED_LOAD64(s + 88), 53) * k1; 265 266 // This is the same inner loop as CityHash64(), manually unrolled. 267 do { 268 x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1; 269 y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1; 270 x ^= w.second; 271 y ^= v.first; 272 z = Rotate(z ^ w.first, 33); 273 v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); 274 w = WeakHashLen32WithSeeds(s + 32, z + w.second, y); 275 std::swap(z, x); 276 s += 64; 277 x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1; 278 y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1; 279 x ^= w.second; 280 y ^= v.first; 281 z = Rotate(z ^ w.first, 33); 282 v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); 283 w = WeakHashLen32WithSeeds(s + 32, z + w.second, y); 284 std::swap(z, x); 285 s += 64; 286 len -= 128; 287 } while (LIKELY(len >= 128)); 288 y += Rotate(w.first, 37) * k0 + z; 289 x += Rotate(v.first + z, 49) * k0; 290 // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s. 291 for (size_t tail_done = 0; tail_done < len; ) { 292 tail_done += 32; 293 y = Rotate(y - x, 42) * k0 + v.second; 294 w.first += UNALIGNED_LOAD64(s + len - tail_done + 16); 295 x = Rotate(x, 49) * k0 + w.first; 296 w.first += v.first; 297 v = WeakHashLen32WithSeeds(s + len - tail_done, v.first, v.second); 298 } 299 // At this point our 48 bytes of state should contain more than 300 // enough information for a strong 128-bit hash. We use two 301 // different 48-byte-to-8-byte hashes to get a 16-byte final result. 302 x = HashLen16(x, v.first); 303 y = HashLen16(y, w.first); 304 return uint128(HashLen16(x + v.second, w.second) + y, 305 HashLen16(x + w.second, y + v.second)); 306 } 307 308 uint128 CityHash128(const char *s, size_t len) { 309 if (len >= 16) { 310 return CityHash128WithSeed(s + 16, 311 len - 16, 312 uint128(UNALIGNED_LOAD64(s) ^ k3, 313 UNALIGNED_LOAD64(s + 8))); 314 } else if (len >= 8) { 315 return CityHash128WithSeed(NULL, 316 0, 317 uint128(UNALIGNED_LOAD64(s) ^ (len * k0), 318 UNALIGNED_LOAD64(s + len - 8) ^ k1)); 319 } else { 320 return CityHash128WithSeed(s, len, uint128(k0, k1)); 321 } 322 }