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