src/tests/city.cc

   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 #define UNALIGNED_LOAD64(p) (*(const uint64*)(p))
  37 #define UNALIGNED_LOAD32(p) (*(const uint32*)(p))
  38
  39 #if !defined(LIKELY)
  40 #if defined(__GNUC__)
  41 #define LIKELY(x) (__builtin_expect(!!(x), 1))
  42 #else
  43 #define LIKELY(x) (x)
  44 #endif
  45 #endif
  46
  47 // Some primes between 2^63 and 2^64 for various uses.
  48 static const uint64 k0 = 0xc3a5c85c97cb3127ULL;
  49 static const uint64 k1 = 0xb492b66fbe98f273ULL;
  50 static const uint64 k2 = 0x9ae16a3b2f90404fULL;
  51 static const uint64 k3 = 0xc949d7c7509e6557ULL;
  52
  53 // Bitwise right rotate.  Normally this will compile to a single
  54 // instruction, especially if the shift is a manifest constant.
  55 static uint64 Rotate(uint64 val, int shift) {
  56   // Avoid shifting by 64: doing so yields an undefined result.
  57   return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
  58 }
  59
  60 // Equivalent to Rotate(), but requires the second arg to be non-zero.
  61 // On x86-64, and probably others, it's possible for this to compile
  62 // to a single instruction if both args are already in registers.
  63 static uint64 RotateByAtLeast1(uint64 val, int shift) {
  64   return (val >> shift) | (val << (64 - shift));
  65 }
  66
  67 static uint64 ShiftMix(uint64 val) {
  68   return val ^ (val >> 47);
  69 }
  70
  71 static uint64 HashLen16(uint64 u, uint64 v) {
  72   return Hash128to64(uint128(u, v));
  73 }
  74
  75 static uint64 HashLen0to16(const char *s, size_t len) {
  76   if (len > 8) {
  77     uint64 a = UNALIGNED_LOAD64(s);
  78     uint64 b = UNALIGNED_LOAD64(s + len - 8);
  79     return HashLen16(a, RotateByAtLeast1(b + len, len)) ^ b;
  80   }
  81   if (len >= 4) {
  82     uint64 a = UNALIGNED_LOAD32(s);
  83     return HashLen16(len + (a << 3), UNALIGNED_LOAD32(s + len - 4));
  84   }
  85   if (len > 0) {
  86     uint8 a = s[0];
  87     uint8 b = s[len >> 1];
  88     uint8 c = s[len - 1];
  89     uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8);
  90     uint32 z = len + (static_cast<uint32>(c) << 2);
  91     return ShiftMix(y * k2 ^ z * k3) * k2;
  92   }
  93   return k2;
  94 }
  95
  96 // This probably works well for 16-byte strings as well, but it may be overkill
  97 // in that case.
  98 static uint64 HashLen17to32(const char *s, size_t len) {
  99   uint64 a = UNALIGNED_LOAD64(s) * k1;
 100   uint64 b = UNALIGNED_LOAD64(s + 8);
 101   uint64 c = UNALIGNED_LOAD64(s + len - 8) * k2;
 102   uint64 d = UNALIGNED_LOAD64(s + len - 16) * k0;
 103   return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d,
 104                    a + Rotate(b ^ k3, 20) - c + len);
 105 }
 106
 107 // Return a 16-byte hash for 48 bytes.  Quick and dirty.
 108 // Callers do best to use "random-looking" values for a and b.
 109 static pair<uint64, uint64> WeakHashLen32WithSeeds(
 110     uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) {
 111   a += w;
 112   b = Rotate(b + a + z, 21);
 113   uint64 c = a;
 114   a += x;
 115   a += y;
 116   b += Rotate(a, 44);
 117   return make_pair(a + z, b + c);
 118 }
 119
 120 // Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
 121 static pair<uint64, uint64> WeakHashLen32WithSeeds(
 122     const char* s, uint64 a, uint64 b) {
 123   return WeakHashLen32WithSeeds(UNALIGNED_LOAD64(s),
 124                                 UNALIGNED_LOAD64(s + 8),
 125                                 UNALIGNED_LOAD64(s + 16),
 126                                 UNALIGNED_LOAD64(s + 24),
 127                                 a,
 128                                 b);
 129 }
 130
 131 // Return an 8-byte hash for 33 to 64 bytes.
 132 static uint64 HashLen33to64(const char *s, size_t len) {
 133   uint64 z = UNALIGNED_LOAD64(s + 24);
 134   uint64 a = UNALIGNED_LOAD64(s) + (len + UNALIGNED_LOAD64(s + len - 16)) * k0;
 135   uint64 b = Rotate(a + z, 52);
 136   uint64 c = Rotate(a, 37);
 137   a += UNALIGNED_LOAD64(s + 8);
 138   c += Rotate(a, 7);
 139   a += UNALIGNED_LOAD64(s + 16);
 140   uint64 vf = a + z;
 141   uint64 vs = b + Rotate(a, 31) + c;
 142   a = UNALIGNED_LOAD64(s + 16) + UNALIGNED_LOAD64(s + len - 32);
 143   z = UNALIGNED_LOAD64(s + len - 8);
 144   b = Rotate(a + z, 52);
 145   c = Rotate(a, 37);
 146   a += UNALIGNED_LOAD64(s + len - 24);
 147   c += Rotate(a, 7);
 148   a += UNALIGNED_LOAD64(s + len - 16);
 149   uint64 wf = a + z;
 150   uint64 ws = b + Rotate(a, 31) + c;
 151   uint64 r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0);
 152   return ShiftMix(r * k0 + vs) * k2;
 153 }
 154
 155 uint64 CityHash64(const char *s, size_t len) {
 156   if (len <= 32) {
 157     if (len <= 16) {
 158       return HashLen0to16(s, len);
 159     } else {
 160       return HashLen17to32(s, len);
 161     }
 162   } else if (len <= 64) {
 163     return HashLen33to64(s, len);
 164   }
 165
 166   // For strings over 64 bytes we hash the end first, and then as we
 167   // loop we keep 56 bytes of state: v, w, x, y, and z.
 168   uint64 x = UNALIGNED_LOAD64(s);
 169   uint64 y = UNALIGNED_LOAD64(s + len - 16) ^ k1;
 170   uint64 z = UNALIGNED_LOAD64(s + len - 56) ^ k0;
 171   pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, y);
 172   pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, len * k1, k0);
 173   z += ShiftMix(v.second) * k1;
 174   x = Rotate(z + x, 39) * k1;
 175   y = Rotate(y, 33) * k1;
 176
 177   // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
 178   len = (len - 1) & ~static_cast<size_t>(63);
 179   do {
 180     x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;
 181     y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;
 182     x ^= w.second;
 183     y ^= v.first;
 184     z = Rotate(z ^ w.first, 33);
 185     v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
 186     w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
 187     std::swap(z, x);
 188     s += 64;
 189     len -= 64;
 190   } while (len != 0);
 191   return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,
 192                    HashLen16(v.second, w.second) + x);
 193 }
 194
 195 uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed) {
 196   return CityHash64WithSeeds(s, len, k2, seed);
 197 }
 198
 199 uint64 CityHash64WithSeeds(const char *s, size_t len,
 200                            uint64 seed0, uint64 seed1) {
 201   return HashLen16(CityHash64(s, len) - seed0, seed1);
 202 }
 203
 204 // A subroutine for CityHash128().  Returns a decent 128-bit hash for strings
 205 // of any length representable in ssize_t.  Based on City and Murmur.
 206 static uint128 CityMurmur(const char *s, size_t len, uint128 seed) {
 207   uint64 a = Uint128Low64(seed);
 208   uint64 b = Uint128High64(seed);
 209   uint64 c = 0;
 210   uint64 d = 0;
 211   ssize_t l = len - 16;
 212   if (l <= 0) {  // len <= 16
 213     c = b * k1 + HashLen0to16(s, len);
 214     d = Rotate(a + (len >= 8 ? UNALIGNED_LOAD64(s) : c), 32);
 215   } else {  // len > 16
 216     c = HashLen16(UNALIGNED_LOAD64(s + len - 8) + k1, a);
 217     d = HashLen16(b + len, c + UNALIGNED_LOAD64(s + len - 16));
 218     a += d;
 219     do {
 220       a ^= ShiftMix(UNALIGNED_LOAD64(s) * k1) * k1;
 221       a *= k1;
 222       b ^= a;
 223       c ^= ShiftMix(UNALIGNED_LOAD64(s + 8) * k1) * k1;
 224       c *= k1;
 225       d ^= c;
 226       s += 16;
 227       l -= 16;
 228     } while (l > 0);
 229   }
 230   a = HashLen16(a, c);
 231   b = HashLen16(d, b);
 232   return uint128(a ^ b, HashLen16(b, a));
 233 }
 234
 235 uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) {
 236   if (len < 128) {
 237     return CityMurmur(s, len, seed);
 238   }
 239
 240   // We expect len >= 128 to be the common case.  Keep 56 bytes of state:
 241   // v, w, x, y, and z.
 242   pair<uint64, uint64> v, w;
 243   uint64 x = Uint128Low64(seed);
 244   uint64 y = Uint128High64(seed);
 245   uint64 z = len * k1;
 246   v.first = Rotate(y ^ k1, 49) * k1 + UNALIGNED_LOAD64(s);
 247   v.second = Rotate(v.first, 42) * k1 + UNALIGNED_LOAD64(s + 8);
 248   w.first = Rotate(y + z, 35) * k1 + x;
 249   w.second = Rotate(x + UNALIGNED_LOAD64(s + 88), 53) * k1;
 250
 251   // This is the same inner loop as CityHash64(), manually unrolled.
 252   do {
 253     x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;
 254     y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;
 255     x ^= w.second;
 256     y ^= v.first;
 257     z = Rotate(z ^ w.first, 33);
 258     v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
 259     w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
 260     std::swap(z, x);
 261     s += 64;
 262     x = Rotate(x + y + v.first + UNALIGNED_LOAD64(s + 16), 37) * k1;
 263     y = Rotate(y + v.second + UNALIGNED_LOAD64(s + 48), 42) * k1;
 264     x ^= w.second;
 265     y ^= v.first;
 266     z = Rotate(z ^ w.first, 33);
 267     v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
 268     w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
 269     std::swap(z, x);
 270     s += 64;
 271     len -= 128;
 272   } while (LIKELY(len >= 128));
 273   y += Rotate(w.first, 37) * k0 + z;
 274   x += Rotate(v.first + z, 49) * k0;
 275   // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.
 276   for (size_t tail_done = 0; tail_done < len; ) {
 277     tail_done += 32;
 278     y = Rotate(y - x, 42) * k0 + v.second;
 279     w.first += UNALIGNED_LOAD64(s + len - tail_done + 16);
 280     x = Rotate(x, 49) * k0 + w.first;
 281     w.first += v.first;
 282     v = WeakHashLen32WithSeeds(s + len - tail_done, v.first, v.second);
 283   }
 284   // At this point our 48 bytes of state should contain more than
 285   // enough information for a strong 128-bit hash.  We use two
 286   // different 48-byte-to-8-byte hashes to get a 16-byte final result.
 287   x = HashLen16(x, v.first);
 288   y = HashLen16(y, w.first);
 289   return uint128(HashLen16(x + v.second, w.second) + y,
 290                  HashLen16(x + w.second, y + v.second));
 291 }
 292
 293 uint128 CityHash128(const char *s, size_t len) {
 294   if (len >= 16) {
 295     return CityHash128WithSeed(s + 16,
 296                                len - 16,
 297                                uint128(UNALIGNED_LOAD64(s) ^ k3,
 298                                        UNALIGNED_LOAD64(s + 8)));
 299   } else if (len >= 8) {
 300     return CityHash128WithSeed(NULL,
 301                                0,
 302                                uint128(UNALIGNED_LOAD64(s) ^ (len * k0),
 303                                        UNALIGNED_LOAD64(s + len - 8) ^ k1));
 304   } else {
 305     return CityHash128WithSeed(s, len, uint128(k0, k1));
 306   }
 307 }