city-hash.cpp
Go to the documentation of this file.
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, 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 "config.h"
31 #include "city-hash.hpp"
32 #include <algorithm>
33 #include <string.h> // for memcpy and memset
34 
35 using namespace std;
36 
37 
38 static uint64 UNALIGNED_LOAD64(const char *p) {
39  uint64 result;
40  memcpy(&result, p, sizeof(result));
41  return result;
42 }
43 
44 static uint32 UNALIGNED_LOAD32(const char *p) {
45  uint32 result;
46  memcpy(&result, p, sizeof(result));
47  return result;
48 }
49 
50 #ifdef _MSC_VER
51 
52 #include <stdlib.h>
53 #define bswap_32(x) _byteswap_ulong(x)
54 #define bswap_64(x) _byteswap_uint64(x)
55 
56 #elif defined(__APPLE__)
57 
58 // Mac OS X / Darwin features
59 #include <libkern/OSByteOrder.h>
60 #define bswap_32(x) OSSwapInt32(x)
61 #define bswap_64(x) OSSwapInt64(x)
62 
63 #elif defined(__NetBSD__)
64 
65 #include <sys/types.h>
66 #include <machine/bswap.h>
67 #if defined(__BSWAP_RENAME) && !defined(__bswap_32)
68 #define bswap_32(x) bswap32(x)
69 #define bswap_64(x) bswap64(x)
70 #endif
71 
72 
73 #elif defined(__FreeBSD__)
74 
75 // Based on https://code.google.com/p/freebsd/source/browse/sys/ofed/include/byteswap.h?spec=svn38a8350a629d959c8c5509221cd07ffb891b5a77&r=38a8350a629d959c8c5509221cd07ffb891b5a77
76 
77 #include <sys/types.h>
78 #include <sys/endian.h>
79 #define bswap_16(x) bswap16(x)
80 #define bswap_32(x) bswap32(x)
81 #define bswap_64(x) bswap64(x)
82 
83 #else
84 
85 #include <byteswap.h>
86 
87 #endif
88 
89 #ifdef WORDS_BIGENDIAN
90 #define uint32_in_expected_order(x) (bswap_32(x))
91 #define uint64_in_expected_order(x) (bswap_64(x))
92 #else
93 #define uint32_in_expected_order(x) (x)
94 #define uint64_in_expected_order(x) (x)
95 #endif
96 
97 #if !defined(LIKELY)
98 #if HAVE_BUILTIN_EXPECT
99 #define LIKELY(x) (__builtin_expect(!!(x), 1))
100 #else
101 #define LIKELY(x) (x)
102 #endif
103 #endif
104 
105 static uint64 Fetch64(const char *p) {
107 }
108 
109 static uint32 Fetch32(const char *p) {
111 }
112 
113 // Some primes between 2^63 and 2^64 for various uses.
114 static const uint64 k0 = 0xc3a5c85c97cb3127ULL;
115 static const uint64 k1 = 0xb492b66fbe98f273ULL;
116 static const uint64 k2 = 0x9ae16a3b2f90404fULL;
117 
118 // Magic numbers for 32-bit hashing. Copied from Murmur3.
119 static const uint32_t c1 = 0xcc9e2d51;
120 static const uint32_t c2 = 0x1b873593;
121 
122 // A 32-bit to 32-bit integer hash copied from Murmur3.
123 static uint32 fmix(uint32 h)
124 {
125  h ^= h >> 16;
126  h *= 0x85ebca6b;
127  h ^= h >> 13;
128  h *= 0xc2b2ae35;
129  h ^= h >> 16;
130  return h;
131 }
132 
133 static uint32 Rotate32(uint32 val, int shift) {
134  // Avoid shifting by 32: doing so yields an undefined result.
135  return shift == 0 ? val : ((val >> shift) | (val << (32 - shift)));
136 }
137 
138 #undef PERMUTE3
139 #define PERMUTE3(a, b, c) do { std::swap(a, b); std::swap(a, c); } while (0)
140 
141 static uint32 Mur(uint32 a, uint32 h) {
142  // Helper from Murmur3 for combining two 32-bit values.
143  a *= c1;
144  a = Rotate32(a, 17);
145  a *= c2;
146  h ^= a;
147  h = Rotate32(h, 19);
148  return h * 5 + 0xe6546b64;
149 }
150 
151 static uint32 Hash32Len13to24(const char *s, size_t len) {
152  uint32 a = Fetch32(s - 4 + (len >> 1));
153  uint32 b = Fetch32(s + 4);
154  uint32 c = Fetch32(s + len - 8);
155  uint32 d = Fetch32(s + (len >> 1));
156  uint32 e = Fetch32(s);
157  uint32 f = Fetch32(s + len - 4);
158  uint32 h = len;
159 
160  return fmix(Mur(f, Mur(e, Mur(d, Mur(c, Mur(b, Mur(a, h)))))));
161 }
162 
163 static uint32 Hash32Len0to4(const char *s, size_t len) {
164  uint32 b = 0;
165  uint32 c = 9;
166  for (size_t i = 0; i < len; i++) {
167  signed char v = s[i];
168  b = b * c1 + v;
169  c ^= b;
170  }
171  return fmix(Mur(b, Mur(len, c)));
172 }
173 
174 static uint32 Hash32Len5to12(const char *s, size_t len) {
175  uint32 a = len, b = len * 5, c = 9, d = b;
176  a += Fetch32(s);
177  b += Fetch32(s + len - 4);
178  c += Fetch32(s + ((len >> 1) & 4));
179  return fmix(Mur(c, Mur(b, Mur(a, d))));
180 }
181 
182 uint32 CityHash32(const char *s, size_t len) {
183  if (len <= 24) {
184  return len <= 12 ?
185  (len <= 4 ? Hash32Len0to4(s, len) : Hash32Len5to12(s, len)) :
186  Hash32Len13to24(s, len);
187  }
188 
189  // len > 24
190  uint32 h = len, g = c1 * len, f = g;
191  uint32 a0 = Rotate32(Fetch32(s + len - 4) * c1, 17) * c2;
192  uint32 a1 = Rotate32(Fetch32(s + len - 8) * c1, 17) * c2;
193  uint32 a2 = Rotate32(Fetch32(s + len - 16) * c1, 17) * c2;
194  uint32 a3 = Rotate32(Fetch32(s + len - 12) * c1, 17) * c2;
195  uint32 a4 = Rotate32(Fetch32(s + len - 20) * c1, 17) * c2;
196  h ^= a0;
197  h = Rotate32(h, 19);
198  h = h * 5 + 0xe6546b64;
199  h ^= a2;
200  h = Rotate32(h, 19);
201  h = h * 5 + 0xe6546b64;
202  g ^= a1;
203  g = Rotate32(g, 19);
204  g = g * 5 + 0xe6546b64;
205  g ^= a3;
206  g = Rotate32(g, 19);
207  g = g * 5 + 0xe6546b64;
208  f += a4;
209  f = Rotate32(f, 19);
210  f = f * 5 + 0xe6546b64;
211  size_t iters = (len - 1) / 20;
212  do {
213  uint32 a0 = Rotate32(Fetch32(s) * c1, 17) * c2;
214  uint32 a1 = Fetch32(s + 4);
215  uint32 a2 = Rotate32(Fetch32(s + 8) * c1, 17) * c2;
216  uint32 a3 = Rotate32(Fetch32(s + 12) * c1, 17) * c2;
217  uint32 a4 = Fetch32(s + 16);
218  h ^= a0;
219  h = Rotate32(h, 18);
220  h = h * 5 + 0xe6546b64;
221  f += a1;
222  f = Rotate32(f, 19);
223  f = f * c1;
224  g += a2;
225  g = Rotate32(g, 18);
226  g = g * 5 + 0xe6546b64;
227  h ^= a3 + a1;
228  h = Rotate32(h, 19);
229  h = h * 5 + 0xe6546b64;
230  g ^= a4;
231  g = bswap_32(g) * 5;
232  h += a4 * 5;
233  h = bswap_32(h);
234  f += a0;
235  PERMUTE3(f, h, g);
236  s += 20;
237  } while (--iters != 0);
238  g = Rotate32(g, 11) * c1;
239  g = Rotate32(g, 17) * c1;
240  f = Rotate32(f, 11) * c1;
241  f = Rotate32(f, 17) * c1;
242  h = Rotate32(h + g, 19);
243  h = h * 5 + 0xe6546b64;
244  h = Rotate32(h, 17) * c1;
245  h = Rotate32(h + f, 19);
246  h = h * 5 + 0xe6546b64;
247  h = Rotate32(h, 17) * c1;
248  return h;
249 }
250 
251 // Bitwise right rotate. Normally this will compile to a single
252 // instruction, especially if the shift is a manifest constant.
253 static uint64 Rotate(uint64 val, int shift) {
254  // Avoid shifting by 64: doing so yields an undefined result.
255  return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
256 }
257 
258 static uint64 ShiftMix(uint64 val) {
259  return val ^ (val >> 47);
260 }
261 
263  return Hash128to64(uint128(u, v));
264 }
265 
266 static uint64 HashLen16(uint64 u, uint64 v, uint64 mul) {
267  // Murmur-inspired hashing.
268  uint64 a = (u ^ v) * mul;
269  a ^= (a >> 47);
270  uint64 b = (v ^ a) * mul;
271  b ^= (b >> 47);
272  b *= mul;
273  return b;
274 }
275 
276 static uint64 HashLen0to16(const char *s, size_t len) {
277  if (len >= 8) {
278  uint64 mul = k2 + len * 2;
279  uint64 a = Fetch64(s) + k2;
280  uint64 b = Fetch64(s + len - 8);
281  uint64 c = Rotate(b, 37) * mul + a;
282  uint64 d = (Rotate(a, 25) + b) * mul;
283  return HashLen16(c, d, mul);
284  }
285  if (len >= 4) {
286  uint64 mul = k2 + len * 2;
287  uint64 a = Fetch32(s);
288  return HashLen16(len + (a << 3), Fetch32(s + len - 4), mul);
289  }
290  if (len > 0) {
291  uint8 a = s[0];
292  uint8 b = s[len >> 1];
293  uint8 c = s[len - 1];
294  uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8);
295  uint32 z = len + (static_cast<uint32>(c) << 2);
296  return ShiftMix(y * k2 ^ z * k0) * k2;
297  }
298  return k2;
299 }
300 
301 // This probably works well for 16-byte strings as well, but it may be overkill
302 // in that case.
303 static uint64 HashLen17to32(const char *s, size_t len) {
304  uint64 mul = k2 + len * 2;
305  uint64 a = Fetch64(s) * k1;
306  uint64 b = Fetch64(s + 8);
307  uint64 c = Fetch64(s + len - 8) * mul;
308  uint64 d = Fetch64(s + len - 16) * k2;
309  return HashLen16(Rotate(a + b, 43) + Rotate(c, 30) + d,
310  a + Rotate(b + k2, 18) + c, mul);
311 }
312 
313 // Return a 16-byte hash for 48 bytes. Quick and dirty.
314 // Callers do best to use "random-looking" values for a and b.
315 static pair<uint64, uint64> WeakHashLen32WithSeeds(
316  uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) {
317  a += w;
318  b = Rotate(b + a + z, 21);
319  uint64 c = a;
320  a += x;
321  a += y;
322  b += Rotate(a, 44);
323  return make_pair(a + z, b + c);
324 }
325 
326 // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty.
327 static pair<uint64, uint64> WeakHashLen32WithSeeds(
328  const char* s, uint64 a, uint64 b) {
330  Fetch64(s + 8),
331  Fetch64(s + 16),
332  Fetch64(s + 24),
333  a,
334  b);
335 }
336 
337 // Return an 8-byte hash for 33 to 64 bytes.
338 static uint64 HashLen33to64(const char *s, size_t len) {
339  uint64 mul = k2 + len * 2;
340  uint64 a = Fetch64(s) * k2;
341  uint64 b = Fetch64(s + 8);
342  uint64 c = Fetch64(s + len - 24);
343  uint64 d = Fetch64(s + len - 32);
344  uint64 e = Fetch64(s + 16) * k2;
345  uint64 f = Fetch64(s + 24) * 9;
346  uint64 g = Fetch64(s + len - 8);
347  uint64 h = Fetch64(s + len - 16) * mul;
348  uint64 u = Rotate(a + g, 43) + (Rotate(b, 30) + c) * 9;
349  uint64 v = ((a + g) ^ d) + f + 1;
350  uint64 w = bswap_64((u + v) * mul) + h;
351  uint64 x = Rotate(e + f, 42) + c;
352  uint64 y = (bswap_64((v + w) * mul) + g) * mul;
353  uint64 z = e + f + c;
354  a = bswap_64((x + z) * mul + y) + b;
355  b = ShiftMix((z + a) * mul + d + h) * mul;
356  return b + x;
357 }
358 
359 uint64 CityHash64(const char *s, size_t len) {
360  if (len <= 32) {
361  if (len <= 16) {
362  return HashLen0to16(s, len);
363  } else {
364  return HashLen17to32(s, len);
365  }
366  } else if (len <= 64) {
367  return HashLen33to64(s, len);
368  }
369 
370  // For strings over 64 bytes we hash the end first, and then as we
371  // loop we keep 56 bytes of state: v, w, x, y, and z.
372  uint64 x = Fetch64(s + len - 40);
373  uint64 y = Fetch64(s + len - 16) + Fetch64(s + len - 56);
374  uint64 z = HashLen16(Fetch64(s + len - 48) + len, Fetch64(s + len - 24));
375  pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, z);
376  pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, y + k1, x);
377  x = x * k1 + Fetch64(s);
378 
379  // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
380  len = (len - 1) & ~static_cast<size_t>(63);
381  do {
382  x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
383  y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
384  x ^= w.second;
385  y += v.first + Fetch64(s + 40);
386  z = Rotate(z + w.first, 33) * k1;
387  v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
388  w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
389  std::swap(z, x);
390  s += 64;
391  len -= 64;
392  } while (len != 0);
393  return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,
394  HashLen16(v.second, w.second) + x);
395 }
396 
397 uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed) {
398  return CityHash64WithSeeds(s, len, k2, seed);
399 }
400 
401 uint64 CityHash64WithSeeds(const char *s, size_t len,
402  uint64 seed0, uint64 seed1) {
403  return HashLen16(CityHash64(s, len) - seed0, seed1);
404 }
405 
406 // A subroutine for CityHash128(). Returns a decent 128-bit hash for strings
407 // of any length representable in signed long. Based on City and Murmur.
408 static uint128 CityMurmur(const char *s, size_t len, uint128 seed) {
409  uint64 a = Uint128Low64(seed);
410  uint64 b = Uint128High64(seed);
411  uint64 c = 0;
412  uint64 d = 0;
413  signed long l = len - 16;
414  if (l <= 0) { // len <= 16
415  a = ShiftMix(a * k1) * k1;
416  c = b * k1 + HashLen0to16(s, len);
417  d = ShiftMix(a + (len >= 8 ? Fetch64(s) : c));
418  } else { // len > 16
419  c = HashLen16(Fetch64(s + len - 8) + k1, a);
420  d = HashLen16(b + len, c + Fetch64(s + len - 16));
421  a += d;
422  do {
423  a ^= ShiftMix(Fetch64(s) * k1) * k1;
424  a *= k1;
425  b ^= a;
426  c ^= ShiftMix(Fetch64(s + 8) * k1) * k1;
427  c *= k1;
428  d ^= c;
429  s += 16;
430  l -= 16;
431  } while (l > 0);
432  }
433  a = HashLen16(a, c);
434  b = HashLen16(d, b);
435  return uint128(a ^ b, HashLen16(b, a));
436 }
437 
438 uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) {
439  if (len < 128) {
440  return CityMurmur(s, len, seed);
441  }
442 
443  // We expect len >= 128 to be the common case. Keep 56 bytes of state:
444  // v, w, x, y, and z.
445  pair<uint64, uint64> v, w;
446  uint64 x = Uint128Low64(seed);
447  uint64 y = Uint128High64(seed);
448  uint64 z = len * k1;
449  v.first = Rotate(y ^ k1, 49) * k1 + Fetch64(s);
450  v.second = Rotate(v.first, 42) * k1 + Fetch64(s + 8);
451  w.first = Rotate(y + z, 35) * k1 + x;
452  w.second = Rotate(x + Fetch64(s + 88), 53) * k1;
453 
454  // This is the same inner loop as CityHash64(), manually unrolled.
455  do {
456  x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
457  y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
458  x ^= w.second;
459  y += v.first + Fetch64(s + 40);
460  z = Rotate(z + w.first, 33) * k1;
461  v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
462  w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
463  std::swap(z, x);
464  s += 64;
465  x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
466  y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
467  x ^= w.second;
468  y += v.first + Fetch64(s + 40);
469  z = Rotate(z + w.first, 33) * k1;
470  v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
471  w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
472  std::swap(z, x);
473  s += 64;
474  len -= 128;
475  } while (LIKELY(len >= 128));
476  x += Rotate(v.first + z, 49) * k0;
477  y = y * k0 + Rotate(w.second, 37);
478  z = z * k0 + Rotate(w.first, 27);
479  w.first *= 9;
480  v.first *= k0;
481  // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.
482  for (size_t tail_done = 0; tail_done < len; ) {
483  tail_done += 32;
484  y = Rotate(x + y, 42) * k0 + v.second;
485  w.first += Fetch64(s + len - tail_done + 16);
486  x = x * k0 + w.first;
487  z += w.second + Fetch64(s + len - tail_done);
488  w.second += v.first;
489  v = WeakHashLen32WithSeeds(s + len - tail_done, v.first + z, v.second);
490  v.first *= k0;
491  }
492  // At this point our 56 bytes of state should contain more than
493  // enough information for a strong 128-bit hash. We use two
494  // different 56-byte-to-8-byte hashes to get a 16-byte final result.
495  x = HashLen16(x, v.first);
496  y = HashLen16(y + z, w.first);
497  return uint128(HashLen16(x + v.second, w.second) + y,
498  HashLen16(x + w.second, y + v.second));
499 }
500 
501 uint128 CityHash128(const char *s, size_t len) {
502  return len >= 16 ?
503  CityHash128WithSeed(s + 16, len - 16,
504  uint128(Fetch64(s), Fetch64(s + 8) + k0)) :
505  CityHash128WithSeed(s, len, uint128(k0, k1));
506 }
507 
508 // NFD NOTE
509 // The following code block is commented out due to the following reasons.
510 // - It requires the "citycrc.h" header file, which is not included in the
511 // NFD code base.
512 // - The functions defined below are not used by the current NFD
513 // implementation.
514 // The header file "citycrc.h" is available at
515 // https://code.google.com/p/cityhash/source/browse/trunk/src/citycrc.h
516 
517 /*
518 #ifdef __SSE4_2__
519 #include <citycrc.h>
520 #include <nmmintrin.h>
521 
522 // Requires len >= 240.
523 static void CityHashCrc256Long(const char *s, size_t len,
524  uint32 seed, uint64 *result) {
525  uint64 a = Fetch64(s + 56) + k0;
526  uint64 b = Fetch64(s + 96) + k0;
527  uint64 c = result[0] = HashLen16(b, len);
528  uint64 d = result[1] = Fetch64(s + 120) * k0 + len;
529  uint64 e = Fetch64(s + 184) + seed;
530  uint64 f = 0;
531  uint64 g = 0;
532  uint64 h = c + d;
533  uint64 x = seed;
534  uint64 y = 0;
535  uint64 z = 0;
536 
537  // 240 bytes of input per iter.
538  size_t iters = len / 240;
539  len -= iters * 240;
540  do {
541 #undef CHUNK
542 #define CHUNK(r) \
543  PERMUTE3(x, z, y); \
544  b += Fetch64(s); \
545  c += Fetch64(s + 8); \
546  d += Fetch64(s + 16); \
547  e += Fetch64(s + 24); \
548  f += Fetch64(s + 32); \
549  a += b; \
550  h += f; \
551  b += c; \
552  f += d; \
553  g += e; \
554  e += z; \
555  g += x; \
556  z = _mm_crc32_u64(z, b + g); \
557  y = _mm_crc32_u64(y, e + h); \
558  x = _mm_crc32_u64(x, f + a); \
559  e = Rotate(e, r); \
560  c += e; \
561  s += 40
562 
563  CHUNK(0); PERMUTE3(a, h, c);
564  CHUNK(33); PERMUTE3(a, h, f);
565  CHUNK(0); PERMUTE3(b, h, f);
566  CHUNK(42); PERMUTE3(b, h, d);
567  CHUNK(0); PERMUTE3(b, h, e);
568  CHUNK(33); PERMUTE3(a, h, e);
569  } while (--iters > 0);
570 
571  while (len >= 40) {
572  CHUNK(29);
573  e ^= Rotate(a, 20);
574  h += Rotate(b, 30);
575  g ^= Rotate(c, 40);
576  f += Rotate(d, 34);
577  PERMUTE3(c, h, g);
578  len -= 40;
579  }
580  if (len > 0) {
581  s = s + len - 40;
582  CHUNK(33);
583  e ^= Rotate(a, 43);
584  h += Rotate(b, 42);
585  g ^= Rotate(c, 41);
586  f += Rotate(d, 40);
587  }
588  result[0] ^= h;
589  result[1] ^= g;
590  g += h;
591  a = HashLen16(a, g + z);
592  x += y << 32;
593  b += x;
594  c = HashLen16(c, z) + h;
595  d = HashLen16(d, e + result[0]);
596  g += e;
597  h += HashLen16(x, f);
598  e = HashLen16(a, d) + g;
599  z = HashLen16(b, c) + a;
600  y = HashLen16(g, h) + c;
601  result[0] = e + z + y + x;
602  a = ShiftMix((a + y) * k0) * k0 + b;
603  result[1] += a + result[0];
604  a = ShiftMix(a * k0) * k0 + c;
605  result[2] = a + result[1];
606  a = ShiftMix((a + e) * k0) * k0;
607  result[3] = a + result[2];
608 }
609 
610 // Requires len < 240.
611 static void CityHashCrc256Short(const char *s, size_t len, uint64 *result) {
612  char buf[240];
613  memcpy(buf, s, len);
614  memset(buf + len, 0, 240 - len);
615  CityHashCrc256Long(buf, 240, ~static_cast<uint32>(len), result);
616 }
617 
618 void CityHashCrc256(const char *s, size_t len, uint64 *result) {
619  if (LIKELY(len >= 240)) {
620  CityHashCrc256Long(s, len, 0, result);
621  } else {
622  CityHashCrc256Short(s, len, result);
623  }
624 }
625 
626 uint128 CityHashCrc128WithSeed(const char *s, size_t len, uint128 seed) {
627  if (len <= 900) {
628  return CityHash128WithSeed(s, len, seed);
629  } else {
630  uint64 result[4];
631  CityHashCrc256(s, len, result);
632  uint64 u = Uint128High64(seed) + result[0];
633  uint64 v = Uint128Low64(seed) + result[1];
634  return uint128(HashLen16(u, v + result[2]),
635  HashLen16(Rotate(v, 32), u * k0 + result[3]));
636  }
637 }
638 
639 uint128 CityHashCrc128(const char *s, size_t len) {
640  if (len <= 900) {
641  return CityHash128(s, len);
642  } else {
643  uint64 result[4];
644  CityHashCrc256(s, len, result);
645  return uint128(result[2], result[3]);
646  }
647 }
648 
649 #endif
650 */
static uint32 fmix(uint32 h)
Definition: city-hash.cpp:123
static uint64 ShiftMix(uint64 val)
Definition: city-hash.cpp:258
static const uint64 k1
Definition: city-hash.cpp:115
static uint128 CityMurmur(const char *s, size_t len, uint128 seed)
Definition: city-hash.cpp:408
static const uint32_t c1
Definition: city-hash.cpp:119
static uint32 Hash32Len0to4(const char *s, size_t len)
Definition: city-hash.cpp:163
static uint64 HashLen33to64(const char *s, size_t len)
Definition: city-hash.cpp:338
uint32 CityHash32(const char *s, size_t len)
Definition: city-hash.cpp:182
static uint64 HashLen16(uint64 u, uint64 v)
Definition: city-hash.cpp:262
#define PERMUTE3(a, b, c)
Definition: city-hash.cpp:139
static const uint64 k2
Definition: city-hash.cpp:116
static const uint32_t c2
Definition: city-hash.cpp:120
static uint64 HashLen17to32(const char *s, size_t len)
Definition: city-hash.cpp:303
static uint32 Fetch32(const char *p)
Definition: city-hash.cpp:109
static pair< uint64, uint64 > WeakHashLen32WithSeeds(uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b)
Definition: city-hash.cpp:315
static uint64 UNALIGNED_LOAD64(const char *p)
Definition: city-hash.cpp:38
static uint32 UNALIGNED_LOAD32(const char *p)
Definition: city-hash.cpp:44
uint64 CityHash64WithSeeds(const char *s, size_t len, uint64 seed0, uint64 seed1)
Definition: city-hash.cpp:401
uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed)
Definition: city-hash.cpp:438
static uint64 Rotate(uint64 val, int shift)
Definition: city-hash.cpp:253
static uint32 Mur(uint32 a, uint32 h)
Definition: city-hash.cpp:141
static const uint64 k0
Definition: city-hash.cpp:114
uint64 CityHash64(const char *s, size_t len)
Definition: city-hash.cpp:359
static uint64 Fetch64(const char *p)
Definition: city-hash.cpp:105
uint128 CityHash128(const char *s, size_t len)
Definition: city-hash.cpp:501
static uint32 Rotate32(uint32 val, int shift)
Definition: city-hash.cpp:133
static uint64 HashLen0to16(const char *s, size_t len)
Definition: city-hash.cpp:276
static uint32 Hash32Len5to12(const char *s, size_t len)
Definition: city-hash.cpp:174
#define uint32_in_expected_order(x)
Definition: city-hash.cpp:93
#define uint64_in_expected_order(x)
Definition: city-hash.cpp:94
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed)
Definition: city-hash.cpp:397
static uint32 Hash32Len13to24(const char *s, size_t len)
Definition: city-hash.cpp:151
#define LIKELY(x)
Definition: city-hash.cpp:101
uint64 Uint128High64(const uint128 &x)
Definition: city-hash.hpp:75
uint64 Uint128Low64(const uint128 &x)
Definition: city-hash.hpp:74
uint64 Hash128to64(const uint128 &x)
Definition: city-hash.hpp:101
uint8_t uint8
Definition: city-hash.hpp:69
std::pair< uint64, uint64 > uint128
Definition: city-hash.hpp:72
uint64_t uint64
Definition: city-hash.hpp:71
uint32_t uint32
Definition: city-hash.hpp:70