Meson WrapDB for Google's cityhash.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

city.cc 19KB

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