1 // Copyright (c) 2014 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 // FarmHash, by Geoff Pike
22
23 // clang-format off
24
25 #include <folly/external/farmhash/farmhash.h>
26
27 #include <exception>
28
29 // FARMHASH ASSUMPTIONS: Modify as needed, or use -DFARMHASH_ASSUME_SSE42 etc.
30 // Note that if you use -DFARMHASH_ASSUME_SSE42 you likely need -msse42
31 // (or its equivalent for your compiler); if you use -DFARMHASH_ASSUME_AESNI
32 // you likely need -maes (or its equivalent for your compiler).
33
34 #ifdef FARMHASH_ASSUME_SSSE3
35 #undef FARMHASH_ASSUME_SSSE3
36 #define FARMHASH_ASSUME_SSSE3 1
37 #endif
38
39 #ifdef FARMHASH_ASSUME_SSE41
40 #undef FARMHASH_ASSUME_SSE41
41 #define FARMHASH_ASSUME_SSE41 1
42 #endif
43
44 #ifdef FARMHASH_ASSUME_SSE42
45 #undef FARMHASH_ASSUME_SSE42
46 #define FARMHASH_ASSUME_SSE42 1
47 #endif
48
49 #ifdef FARMHASH_ASSUME_AESNI
50 #undef FARMHASH_ASSUME_AESNI
51 #define FARMHASH_ASSUME_AESNI 1
52 #endif
53
54 #ifdef FARMHASH_ASSUME_AVX
55 #undef FARMHASH_ASSUME_AVX
56 #define FARMHASH_ASSUME_AVX 1
57 #endif
58
59 #if !defined(FARMHASH_CAN_USE_CXX11) && defined(LANG_CXX11)
60 #define FARMHASH_CAN_USE_CXX11 1
61 #else
62 #undef FARMHASH_CAN_USE_CXX11
63 #define FARMHASH_CAN_USE_CXX11 0
64 #endif
65
66 // FARMHASH PORTABILITY LAYER: Runtime error if misconfigured
67
68 #ifndef FARMHASH_DIE_IF_MISCONFIGURED
69 #define FARMHASH_DIE_IF_MISCONFIGURED \
70 do { \
71 if (test::returnZeroIfMisconfigured) { \
72 return 0; \
73 } else { \
74 std::terminate(); \
75 } \
76 } while (0)
77 #endif
78
79 // FARMHASH PORTABILITY LAYER: "static inline" or similar
80
81 #ifndef STATIC_INLINE
82 #define STATIC_INLINE static inline
83 #endif
84
85 // FARMHASH PORTABILITY LAYER: LIKELY and UNLIKELY
86
87 #if !defined(LIKELY)
88 #if defined(FARMHASH_NO_BUILTIN_EXPECT) || (defined(FARMHASH_OPTIONAL_BUILTIN_EXPECT) && !defined(HAVE_BUILTIN_EXPECT)) || !defined(__GNUC__)
89 #define LIKELY(x) (x)
90 #else
91 #define LIKELY(x) (__builtin_expect(!!(x), 1))
92 #endif
93 #endif
94
95 #undef UNLIKELY
96 #define UNLIKELY(x) !LIKELY(!(x))
97
98 // FARMHASH PORTABILITY LAYER: endianness and byteswapping functions
99
100 #ifdef WORDS_BIGENDIAN
101 #undef FARMHASH_BIG_ENDIAN
102 #define FARMHASH_BIG_ENDIAN 1
103 #endif
104
105 #if defined(FARMHASH_LITTLE_ENDIAN) && defined(FARMHASH_BIG_ENDIAN)
106 #error
107 #endif
108
109 #if !defined(FARMHASH_LITTLE_ENDIAN) && !defined(FARMHASH_BIG_ENDIAN)
110 #define FARMHASH_UNKNOWN_ENDIAN 1
111 #endif
112
113 #if !defined(bswap_32) || !defined(bswap_64)
114 #undef bswap_32
115 #undef bswap_64
116
117 #if defined(HAVE_BUILTIN_BSWAP) || defined(__clang__) || \
118 (defined(__GNUC__) && ((__GNUC__ == 4 && __GNUC_MINOR__ >= 8) || \
119 __GNUC__ >= 5))
120 // Easy case for bswap: no header file needed.
121 #define bswap_32(x) __builtin_bswap32(x)
122 #define bswap_64(x) __builtin_bswap64(x)
123 #endif
124
125 #endif
126
127 #if defined(FARMHASH_UNKNOWN_ENDIAN) || !defined(bswap_64)
128
129 #ifdef _MSC_VER
130
131 #undef bswap_32
132 #undef bswap_64
133 #define bswap_32(x) _byteswap_ulong(x)
134 #define bswap_64(x) _byteswap_uint64(x)
135
136 #elif defined(__APPLE__)
137
138 // Mac OS X / Darwin features
139 #include <libkern/OSByteOrder.h>
140 #undef bswap_32
141 #undef bswap_64
142 #define bswap_32(x) OSSwapInt32(x)
143 #define bswap_64(x) OSSwapInt64(x)
144
145 #elif defined(__sun) || defined(sun)
146
147 #include <sys/byteorder.h>
148 #undef bswap_32
149 #undef bswap_64
150 #define bswap_32(x) BSWAP_32(x)
151 #define bswap_64(x) BSWAP_64(x)
152
153 #elif defined(__FreeBSD__) || defined(__DragonFly__)
154
155 #include <sys/endian.h>
156 #undef bswap_32
157 #undef bswap_64
158 #define bswap_32(x) bswap32(x)
159 #define bswap_64(x) bswap64(x)
160
161 #elif defined(__OpenBSD__)
162
163 #include <sys/types.h>
164 #undef bswap_32
165 #undef bswap_64
166 #define bswap_32(x) swap32(x)
167 #define bswap_64(x) swap64(x)
168
169 #elif defined(__NetBSD__)
170
171 #include <sys/types.h>
172 #include <machine/bswap.h>
173 #if defined(__BSWAP_RENAME) && !defined(__bswap_32)
174 #undef bswap_32
175 #undef bswap_64
176 #define bswap_32(x) bswap32(x)
177 #define bswap_64(x) bswap64(x)
178 #endif
179
180 #else
181
182 #undef bswap_32
183 #undef bswap_64
184 #include <byteswap.h>
185
186 #endif
187
188 #ifdef WORDS_BIGENDIAN
189 #define FARMHASH_BIG_ENDIAN 1
190 #endif
191
192 #endif
193
194 #ifdef FARMHASH_BIG_ENDIAN
195 #define uint32_in_expected_order(x) (bswap_32(x))
196 #define uint64_in_expected_order(x) (bswap_64(x))
197 #else
198 #define uint32_in_expected_order(x) (x)
199 #define uint64_in_expected_order(x) (x)
200 #endif
201
202 namespace folly {
203 namespace external {
204 namespace farmhash {
205
206 namespace test {
207 bool returnZeroIfMisconfigured = false;
208 }
209
Fetch64(const char * p)210 STATIC_INLINE uint64_t Fetch64(const char *p) {
211 uint64_t result;
212 memcpy(&result, p, sizeof(result));
213 return uint64_in_expected_order(result);
214 }
215
Fetch32(const char * p)216 STATIC_INLINE uint32_t Fetch32(const char *p) {
217 uint32_t result;
218 memcpy(&result, p, sizeof(result));
219 return uint32_in_expected_order(result);
220 }
221
Bswap32(uint32_t val)222 STATIC_INLINE uint32_t Bswap32(uint32_t val) { return bswap_32(val); }
Bswap64(uint64_t val)223 STATIC_INLINE uint64_t Bswap64(uint64_t val) { return bswap_64(val); }
224
225 // FARMHASH PORTABILITY LAYER: bitwise rot
226
BasicRotate32(uint32_t val,int shift)227 STATIC_INLINE uint32_t BasicRotate32(uint32_t val, int shift) {
228 // Avoid shifting by 32: doing so yields an undefined result.
229 return shift == 0 ? val : ((val >> shift) | (val << (32 - shift)));
230 }
231
BasicRotate64(uint64_t val,int shift)232 STATIC_INLINE uint64_t BasicRotate64(uint64_t val, int shift) {
233 // Avoid shifting by 64: doing so yields an undefined result.
234 return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
235 }
236
237 #if defined(_MSC_VER) && defined(FARMHASH_ROTR)
238
Rotate32(uint32_t val,int shift)239 STATIC_INLINE uint32_t Rotate32(uint32_t val, int shift) {
240 return sizeof(unsigned long) == sizeof(val) ?
241 _lrotr(val, shift) :
242 BasicRotate32(val, shift);
243 }
244
Rotate64(uint64_t val,int shift)245 STATIC_INLINE uint64_t Rotate64(uint64_t val, int shift) {
246 return sizeof(unsigned long) == sizeof(val) ?
247 _lrotr(val, shift) :
248 BasicRotate64(val, shift);
249 }
250
251 #else
252
Rotate32(uint32_t val,int shift)253 STATIC_INLINE uint32_t Rotate32(uint32_t val, int shift) {
254 return BasicRotate32(val, shift);
255 }
Rotate64(uint64_t val,int shift)256 STATIC_INLINE uint64_t Rotate64(uint64_t val, int shift) {
257 return BasicRotate64(val, shift);
258 }
259
260 #endif
261
262 } // namespace farmhash
263 } // namespace external
264 } // namespace folly
265
266 // FARMHASH PORTABILITY LAYER: debug mode or max speed?
267 // One may use -DFARMHASH_DEBUG=1 or -DFARMHASH_DEBUG=0 to force the issue.
268
269 #if !defined(FARMHASH_DEBUG) && (!defined(NDEBUG) || defined(_DEBUG))
270 #define FARMHASH_DEBUG 1
271 #endif
272
273 #undef debug_mode
274 #if FARMHASH_DEBUG
275 #define debug_mode 1
276 #else
277 #define debug_mode 0
278 #endif
279
280 // PLATFORM-SPECIFIC FUNCTIONS AND MACROS
281
282 #undef x86_64
283 #if defined (__x86_64) || defined (__x86_64__)
284 #define x86_64 1
285 #else
286 #define x86_64 0
287 #endif
288
289 #undef x86
290 #if defined(__i386__) || defined(__i386) || defined(__X86__)
291 #define x86 1
292 #else
293 #define x86 x86_64
294 #endif
295
296 #if !defined(is_64bit)
297 #define is_64bit (x86_64 || (sizeof(void*) == 8))
298 #endif
299
300 #undef can_use_ssse3
301 #if defined(__SSSE3__) || defined(FARMHASH_ASSUME_SSSE3)
302
303 #include <immintrin.h>
304 #define can_use_ssse3 1
305 // Now we can use _mm_hsub_epi16 and so on.
306
307 #else
308 #define can_use_ssse3 0
309 #endif
310
311 #undef can_use_sse41
312 #if defined(__SSE4_1__) || defined(FARMHASH_ASSUME_SSE41)
313
314 #include <immintrin.h>
315 #define can_use_sse41 1
316 // Now we can use _mm_insert_epi64 and so on.
317
318 #else
319 #define can_use_sse41 0
320 #endif
321
322 #undef can_use_sse42
323 #if defined(__SSE4_2__) || defined(FARMHASH_ASSUME_SSE42)
324
325 #include <nmmintrin.h>
326 #define can_use_sse42 1
327 // Now we can use _mm_crc32_u{32,16,8}. And on 64-bit platforms, _mm_crc32_u64.
328
329 #else
330 #define can_use_sse42 0
331 #endif
332
333 #undef can_use_aesni
334 #if defined(__AES__) || defined(FARMHASH_ASSUME_AESNI)
335
336 #include <wmmintrin.h>
337 #define can_use_aesni 1
338 // Now we can use _mm_aesimc_si128 and so on.
339
340 #else
341 #define can_use_aesni 0
342 #endif
343
344 #undef can_use_avx
345 #if defined(__AVX__) || defined(FARMHASH_ASSUME_AVX)
346
347 #include <immintrin.h>
348 #define can_use_avx 1
349
350 #else
351 #define can_use_avx 0
352 #endif
353
354 #if can_use_sse42 || (can_use_sse41 && x86_64)
Fetch128(const char * s)355 STATIC_INLINE __m128i Fetch128(const char* s) {
356 return _mm_loadu_si128(reinterpret_cast<const __m128i*>(s));
357 }
358 #endif
359 // Building blocks for hash functions
360
361 // std::swap() was in <algorithm> but is in <utility> from C++11 on.
362 #if !FARMHASH_CAN_USE_CXX11
363 #include <algorithm>
364 #endif
365
366 #undef PERMUTE3
367 #define PERMUTE3(a, b, c) do { std::swap(a, b); std::swap(a, c); } while (0)
368
369 namespace folly {
370 namespace external {
371 namespace farmhash {
372
373 // Some primes between 2^63 and 2^64 for various uses.
374 static const uint64_t k0 = 0xc3a5c85c97cb3127ULL;
375 static const uint64_t k1 = 0xb492b66fbe98f273ULL;
376 static const uint64_t k2 = 0x9ae16a3b2f90404fULL;
377
378 // Magic numbers for 32-bit hashing. Copied from Murmur3.
379 static const uint32_t c1 = 0xcc9e2d51;
380 static const uint32_t c2 = 0x1b873593;
381
382 // A 32-bit to 32-bit integer hash copied from Murmur3.
fmix(uint32_t h)383 STATIC_INLINE uint32_t fmix(uint32_t h)
384 {
385 h ^= h >> 16;
386 h *= 0x85ebca6b;
387 h ^= h >> 13;
388 h *= 0xc2b2ae35;
389 h ^= h >> 16;
390 return h;
391 }
392
Mur(uint32_t a,uint32_t h)393 STATIC_INLINE uint32_t Mur(uint32_t a, uint32_t h) {
394 // Helper from Murmur3 for combining two 32-bit values.
395 a *= c1;
396 a = Rotate32(a, 17);
397 a *= c2;
398 h ^= a;
399 h = Rotate32(h, 19);
400 return h * 5 + 0xe6546b64;
401 }
402
DebugTweak(T x)403 template <typename T> STATIC_INLINE T DebugTweak(T x) {
404 if (debug_mode) {
405 if (sizeof(x) == 4) {
406 x = ~Bswap32(x * c1);
407 } else {
408 x = ~Bswap64(x * k1);
409 }
410 }
411 return x;
412 }
413
DebugTweak(uint128_t x)414 template <> uint128_t DebugTweak(uint128_t x) {
415 if (debug_mode) {
416 uint64_t y = DebugTweak(Uint128Low64(x));
417 uint64_t z = DebugTweak(Uint128High64(x));
418 y += z;
419 z += y;
420 x = Uint128(y, z * k1);
421 }
422 return x;
423 }
424
425 using namespace std;
426
427 namespace farmhashna {
428 #undef Fetch
429 #define Fetch Fetch64
430
431 #undef Rotate
432 #define Rotate Rotate64
433
434 #undef Bswap
435 #define Bswap Bswap64
436
ShiftMix(uint64_t val)437 STATIC_INLINE uint64_t ShiftMix(uint64_t val) {
438 return val ^ (val >> 47);
439 }
440
HashLen16(uint64_t u,uint64_t v)441 STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v) {
442 return Hash128to64(Uint128(u, v));
443 }
444
HashLen16(uint64_t u,uint64_t v,uint64_t mul)445 STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) {
446 // Murmur-inspired hashing.
447 uint64_t a = (u ^ v) * mul;
448 a ^= (a >> 47);
449 uint64_t b = (v ^ a) * mul;
450 b ^= (b >> 47);
451 b *= mul;
452 return b;
453 }
454
HashLen0to16(const char * s,size_t len)455 STATIC_INLINE uint64_t HashLen0to16(const char *s, size_t len) {
456 if (len >= 8) {
457 uint64_t mul = k2 + len * 2;
458 uint64_t a = Fetch(s) + k2;
459 uint64_t b = Fetch(s + len - 8);
460 uint64_t c = Rotate(b, 37) * mul + a;
461 uint64_t d = (Rotate(a, 25) + b) * mul;
462 return HashLen16(c, d, mul);
463 }
464 if (len >= 4) {
465 uint64_t mul = k2 + len * 2;
466 uint64_t a = Fetch32(s);
467 return HashLen16(len + (a << 3), Fetch32(s + len - 4), mul);
468 }
469 if (len > 0) {
470 uint8_t a = s[0];
471 uint8_t b = s[len >> 1];
472 uint8_t c = s[len - 1];
473 uint32_t y = static_cast<uint32_t>(a) + (static_cast<uint32_t>(b) << 8);
474 uint32_t z = len + (static_cast<uint32_t>(c) << 2);
475 return ShiftMix(y * k2 ^ z * k0) * k2;
476 }
477 return k2;
478 }
479
480 // This probably works well for 16-byte strings as well, but it may be overkill
481 // in that case.
HashLen17to32(const char * s,size_t len)482 STATIC_INLINE uint64_t HashLen17to32(const char *s, size_t len) {
483 uint64_t mul = k2 + len * 2;
484 uint64_t a = Fetch(s) * k1;
485 uint64_t b = Fetch(s + 8);
486 uint64_t c = Fetch(s + len - 8) * mul;
487 uint64_t d = Fetch(s + len - 16) * k2;
488 return HashLen16(Rotate(a + b, 43) + Rotate(c, 30) + d,
489 a + Rotate(b + k2, 18) + c, mul);
490 }
491
492 // Return a 16-byte hash for 48 bytes. Quick and dirty.
493 // Callers do best to use "random-looking" values for a and b.
WeakHashLen32WithSeeds(uint64_t w,uint64_t x,uint64_t y,uint64_t z,uint64_t a,uint64_t b)494 STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
495 uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) {
496 a += w;
497 b = Rotate(b + a + z, 21);
498 uint64_t c = a;
499 a += x;
500 a += y;
501 b += Rotate(a, 44);
502 return make_pair(a + z, b + c);
503 }
504
505 // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty.
WeakHashLen32WithSeeds(const char * s,uint64_t a,uint64_t b)506 STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
507 const char* s, uint64_t a, uint64_t b) {
508 return WeakHashLen32WithSeeds(Fetch(s),
509 Fetch(s + 8),
510 Fetch(s + 16),
511 Fetch(s + 24),
512 a,
513 b);
514 }
515
516 // Return an 8-byte hash for 33 to 64 bytes.
HashLen33to64(const char * s,size_t len)517 STATIC_INLINE uint64_t HashLen33to64(const char *s, size_t len) {
518 uint64_t mul = k2 + len * 2;
519 uint64_t a = Fetch(s) * k2;
520 uint64_t b = Fetch(s + 8);
521 uint64_t c = Fetch(s + len - 8) * mul;
522 uint64_t d = Fetch(s + len - 16) * k2;
523 uint64_t y = Rotate(a + b, 43) + Rotate(c, 30) + d;
524 uint64_t z = HashLen16(y, a + Rotate(b + k2, 18) + c, mul);
525 uint64_t e = Fetch(s + 16) * mul;
526 uint64_t f = Fetch(s + 24);
527 uint64_t g = (y + Fetch(s + len - 32)) * mul;
528 uint64_t h = (z + Fetch(s + len - 24)) * mul;
529 return HashLen16(Rotate(e + f, 43) + Rotate(g, 30) + h,
530 e + Rotate(f + a, 18) + g, mul);
531 }
532
Hash64(const char * s,size_t len)533 uint64_t Hash64(const char *s, size_t len) {
534 const uint64_t seed = 81;
535 if (len <= 32) {
536 if (len <= 16) {
537 return HashLen0to16(s, len);
538 } else {
539 return HashLen17to32(s, len);
540 }
541 } else if (len <= 64) {
542 return HashLen33to64(s, len);
543 }
544
545 // For strings over 64 bytes we loop. Internal state consists of
546 // 56 bytes: v, w, x, y, and z.
547 uint64_t x = seed;
548 uint64_t y = seed * k1 + 113;
549 uint64_t z = ShiftMix(y * k2 + 113) * k2;
550 pair<uint64_t, uint64_t> v = make_pair(0, 0);
551 pair<uint64_t, uint64_t> w = make_pair(0, 0);
552 x = x * k2 + Fetch(s);
553
554 // Set end so that after the loop we have 1 to 64 bytes left to process.
555 const char* end = s + ((len - 1) / 64) * 64;
556 const char* last64 = end + ((len - 1) & 63) - 63;
557 assert(s + len - 64 == last64);
558 do {
559 x = Rotate(x + y + v.first + Fetch(s + 8), 37) * k1;
560 y = Rotate(y + v.second + Fetch(s + 48), 42) * k1;
561 x ^= w.second;
562 y += v.first + Fetch(s + 40);
563 z = Rotate(z + w.first, 33) * k1;
564 v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
565 w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16));
566 std::swap(z, x);
567 s += 64;
568 } while (s != end);
569 uint64_t mul = k1 + ((z & 0xff) << 1);
570 // Make s point to the last 64 bytes of input.
571 s = last64;
572 w.first += ((len - 1) & 63);
573 v.first += w.first;
574 w.first += v.first;
575 x = Rotate(x + y + v.first + Fetch(s + 8), 37) * mul;
576 y = Rotate(y + v.second + Fetch(s + 48), 42) * mul;
577 x ^= w.second * 9;
578 y += v.first * 9 + Fetch(s + 40);
579 z = Rotate(z + w.first, 33) * mul;
580 v = WeakHashLen32WithSeeds(s, v.second * mul, x + w.first);
581 w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16));
582 std::swap(z, x);
583 return HashLen16(HashLen16(v.first, w.first, mul) + ShiftMix(y) * k0 + z,
584 HashLen16(v.second, w.second, mul) + x,
585 mul);
586 }
587
588 uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1);
589
Hash64WithSeed(const char * s,size_t len,uint64_t seed)590 uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
591 return Hash64WithSeeds(s, len, k2, seed);
592 }
593
Hash64WithSeeds(const char * s,size_t len,uint64_t seed0,uint64_t seed1)594 uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) {
595 return HashLen16(Hash64(s, len) - seed0, seed1);
596 }
597 } // namespace farmhashna
598 namespace farmhashuo {
599 #undef Fetch
600 #define Fetch Fetch64
601
602 #undef Rotate
603 #define Rotate Rotate64
604
H(uint64_t x,uint64_t y,uint64_t mul,int r)605 STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r) {
606 uint64_t a = (x ^ y) * mul;
607 a ^= (a >> 47);
608 uint64_t b = (y ^ a) * mul;
609 return Rotate(b, r) * mul;
610 }
611
Hash64WithSeeds(const char * s,size_t len,uint64_t seed0,uint64_t seed1)612 uint64_t Hash64WithSeeds(const char *s, size_t len,
613 uint64_t seed0, uint64_t seed1) {
614 if (len <= 64) {
615 return farmhashna::Hash64WithSeeds(s, len, seed0, seed1);
616 }
617
618 // For strings over 64 bytes we loop. Internal state consists of
619 // 64 bytes: u, v, w, x, y, and z.
620 uint64_t x = seed0;
621 uint64_t y = seed1 * k2 + 113;
622 uint64_t z = farmhashna::ShiftMix(y * k2) * k2;
623 pair<uint64_t, uint64_t> v = make_pair(seed0, seed1);
624 pair<uint64_t, uint64_t> w = make_pair(0, 0);
625 uint64_t u = x - z;
626 x *= k2;
627 uint64_t mul = k2 + (u & 0x82);
628
629 // Set end so that after the loop we have 1 to 64 bytes left to process.
630 const char* end = s + ((len - 1) / 64) * 64;
631 const char* last64 = end + ((len - 1) & 63) - 63;
632 assert(s + len - 64 == last64);
633 do {
634 uint64_t a0 = Fetch(s);
635 uint64_t a1 = Fetch(s + 8);
636 uint64_t a2 = Fetch(s + 16);
637 uint64_t a3 = Fetch(s + 24);
638 uint64_t a4 = Fetch(s + 32);
639 uint64_t a5 = Fetch(s + 40);
640 uint64_t a6 = Fetch(s + 48);
641 uint64_t a7 = Fetch(s + 56);
642 x += a0 + a1;
643 y += a2;
644 z += a3;
645 v.first += a4;
646 v.second += a5 + a1;
647 w.first += a6;
648 w.second += a7;
649
650 x = Rotate(x, 26);
651 x *= 9;
652 y = Rotate(y, 29);
653 z *= mul;
654 v.first = Rotate(v.first, 33);
655 v.second = Rotate(v.second, 30);
656 w.first ^= x;
657 w.first *= 9;
658 z = Rotate(z, 32);
659 z += w.second;
660 w.second += z;
661 z *= 9;
662 std::swap(u, y);
663
664 z += a0 + a6;
665 v.first += a2;
666 v.second += a3;
667 w.first += a4;
668 w.second += a5 + a6;
669 x += a1;
670 y += a7;
671
672 y += v.first;
673 v.first += x - y;
674 v.second += w.first;
675 w.first += v.second;
676 w.second += x - y;
677 x += w.second;
678 w.second = Rotate(w.second, 34);
679 std::swap(u, z);
680 s += 64;
681 } while (s != end);
682 // Make s point to the last 64 bytes of input.
683 s = last64;
684 u *= 9;
685 v.second = Rotate(v.second, 28);
686 v.first = Rotate(v.first, 20);
687 w.first += ((len - 1) & 63);
688 u += y;
689 y += u;
690 x = Rotate(y - x + v.first + Fetch(s + 8), 37) * mul;
691 y = Rotate(y ^ v.second ^ Fetch(s + 48), 42) * mul;
692 x ^= w.second * 9;
693 y += v.first + Fetch(s + 40);
694 z = Rotate(z + w.first, 33) * mul;
695 v = farmhashna::WeakHashLen32WithSeeds(s, v.second * mul, x + w.first);
696 w = farmhashna::WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16));
697 return H(farmhashna::HashLen16(v.first + x, w.first ^ y, mul) + z - u,
698 H(v.second + y, w.second + z, k2, 30) ^ x,
699 k2,
700 31);
701 }
702
Hash64WithSeed(const char * s,size_t len,uint64_t seed)703 uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
704 return len <= 64 ? farmhashna::Hash64WithSeed(s, len, seed) :
705 Hash64WithSeeds(s, len, 0, seed);
706 }
707
Hash64(const char * s,size_t len)708 uint64_t Hash64(const char *s, size_t len) {
709 return len <= 64 ? farmhashna::Hash64(s, len) :
710 Hash64WithSeeds(s, len, 81, 0);
711 }
712 } // namespace farmhashuo
713 namespace farmhashxo {
714 #undef Fetch
715 #define Fetch Fetch64
716
717 #undef Rotate
718 #define Rotate Rotate64
719
H32(const char * s,size_t len,uint64_t mul,uint64_t seed0=0,uint64_t seed1=0)720 STATIC_INLINE uint64_t H32(const char *s, size_t len, uint64_t mul,
721 uint64_t seed0 = 0, uint64_t seed1 = 0) {
722 uint64_t a = Fetch(s) * k1;
723 uint64_t b = Fetch(s + 8);
724 uint64_t c = Fetch(s + len - 8) * mul;
725 uint64_t d = Fetch(s + len - 16) * k2;
726 uint64_t u = Rotate(a + b, 43) + Rotate(c, 30) + d + seed0;
727 uint64_t v = a + Rotate(b + k2, 18) + c + seed1;
728 a = farmhashna::ShiftMix((u ^ v) * mul);
729 b = farmhashna::ShiftMix((v ^ a) * mul);
730 return b;
731 }
732
733 // Return an 8-byte hash for 33 to 64 bytes.
HashLen33to64(const char * s,size_t len)734 STATIC_INLINE uint64_t HashLen33to64(const char *s, size_t len) {
735 uint64_t mul0 = k2 - 30;
736 uint64_t mul1 = k2 - 30 + 2 * len;
737 uint64_t h0 = H32(s, 32, mul0);
738 uint64_t h1 = H32(s + len - 32, 32, mul1);
739 return ((h1 * mul1) + h0) * mul1;
740 }
741
742 // Return an 8-byte hash for 65 to 96 bytes.
HashLen65to96(const char * s,size_t len)743 STATIC_INLINE uint64_t HashLen65to96(const char *s, size_t len) {
744 uint64_t mul0 = k2 - 114;
745 uint64_t mul1 = k2 - 114 + 2 * len;
746 uint64_t h0 = H32(s, 32, mul0);
747 uint64_t h1 = H32(s + 32, 32, mul1);
748 uint64_t h2 = H32(s + len - 32, 32, mul1, h0, h1);
749 return (h2 * 9 + (h0 >> 17) + (h1 >> 21)) * mul1;
750 }
751
Hash64(const char * s,size_t len)752 uint64_t Hash64(const char *s, size_t len) {
753 if (len <= 32) {
754 if (len <= 16) {
755 return farmhashna::HashLen0to16(s, len);
756 } else {
757 return farmhashna::HashLen17to32(s, len);
758 }
759 } else if (len <= 64) {
760 return HashLen33to64(s, len);
761 } else if (len <= 96) {
762 return HashLen65to96(s, len);
763 } else if (len <= 256) {
764 return farmhashna::Hash64(s, len);
765 } else {
766 return farmhashuo::Hash64(s, len);
767 }
768 }
769
Hash64WithSeeds(const char * s,size_t len,uint64_t seed0,uint64_t seed1)770 uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) {
771 return farmhashuo::Hash64WithSeeds(s, len, seed0, seed1);
772 }
773
Hash64WithSeed(const char * s,size_t len,uint64_t seed)774 uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
775 return farmhashuo::Hash64WithSeed(s, len, seed);
776 }
777 } // namespace farmhashxo
778 namespace farmhashte {
779 #if !can_use_sse41 || !x86_64
780
Hash64(const char * s,size_t len)781 uint64_t Hash64(const char *s, size_t len) {
782 FARMHASH_DIE_IF_MISCONFIGURED;
783 return s == NULL ? 0 : len;
784 }
785
Hash64WithSeed(const char * s,size_t len,uint64_t seed)786 uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
787 FARMHASH_DIE_IF_MISCONFIGURED;
788 return seed + Hash64(s, len);
789 }
790
Hash64WithSeeds(const char * s,size_t len,uint64_t seed0,uint64_t seed1)791 uint64_t Hash64WithSeeds(const char *s, size_t len,
792 uint64_t seed0, uint64_t seed1) {
793 FARMHASH_DIE_IF_MISCONFIGURED;
794 return seed0 + seed1 + Hash64(s, len);
795 }
796
797 #else
798
799 #undef Fetch
800 #define Fetch Fetch64
801
802 #undef Rotate
803 #define Rotate Rotate64
804
805 #undef Bswap
806 #define Bswap Bswap64
807
808 // Helpers for data-parallel operations (1x 128 bits or 2x 64 or 4x 32).
809 STATIC_INLINE __m128i Add(__m128i x, __m128i y) { return _mm_add_epi64(x, y); }
810 STATIC_INLINE __m128i Xor(__m128i x, __m128i y) { return _mm_xor_si128(x, y); }
811 STATIC_INLINE __m128i Mul(__m128i x, __m128i y) { return _mm_mullo_epi32(x, y); }
812 STATIC_INLINE __m128i Shuf(__m128i x, __m128i y) { return _mm_shuffle_epi8(y, x); }
813
814 // Requires n >= 256. Requires SSE4.1. Should be slightly faster if the
815 // compiler uses AVX instructions (e.g., use the -mavx flag with GCC).
816 STATIC_INLINE uint64_t Hash64Long(const char* s, size_t n,
817 uint64_t seed0, uint64_t seed1) {
818 const __m128i kShuf =
819 _mm_set_epi8(4, 11, 10, 5, 8, 15, 6, 9, 12, 2, 14, 13, 0, 7, 3, 1);
820 const __m128i kMult =
821 _mm_set_epi8(0xbd, 0xd6, 0x33, 0x39, 0x45, 0x54, 0xfa, 0x03,
822 0x34, 0x3e, 0x33, 0xed, 0xcc, 0x9e, 0x2d, 0x51);
823 uint64_t seed2 = (seed0 + 113) * (seed1 + 9);
824 uint64_t seed3 = (Rotate(seed0, 23) + 27) * (Rotate(seed1, 30) + 111);
825 __m128i d0 = _mm_cvtsi64_si128(seed0);
826 __m128i d1 = _mm_cvtsi64_si128(seed1);
827 __m128i d2 = Shuf(kShuf, d0);
828 __m128i d3 = Shuf(kShuf, d1);
829 __m128i d4 = Xor(d0, d1);
830 __m128i d5 = Xor(d1, d2);
831 __m128i d6 = Xor(d2, d4);
832 __m128i d7 = _mm_set1_epi32(seed2 >> 32);
833 __m128i d8 = Mul(kMult, d2);
834 __m128i d9 = _mm_set1_epi32(seed3 >> 32);
835 __m128i d10 = _mm_set1_epi32(seed3);
836 __m128i d11 = Add(d2, _mm_set1_epi32(seed2));
837 const char* end = s + (n & ~static_cast<size_t>(255));
838 do {
839 __m128i z;
840 z = Fetch128(s);
841 d0 = Add(d0, z);
842 d1 = Shuf(kShuf, d1);
843 d2 = Xor(d2, d0);
844 d4 = Xor(d4, z);
845 d4 = Xor(d4, d1);
846 std::swap(d0, d6);
847 z = Fetch128(s + 16);
848 d5 = Add(d5, z);
849 d6 = Shuf(kShuf, d6);
850 d8 = Shuf(kShuf, d8);
851 d7 = Xor(d7, d5);
852 d0 = Xor(d0, z);
853 d0 = Xor(d0, d6);
854 std::swap(d5, d11);
855 z = Fetch128(s + 32);
856 d1 = Add(d1, z);
857 d2 = Shuf(kShuf, d2);
858 d4 = Shuf(kShuf, d4);
859 d5 = Xor(d5, z);
860 d5 = Xor(d5, d2);
861 std::swap(d10, d4);
862 z = Fetch128(s + 48);
863 d6 = Add(d6, z);
864 d7 = Shuf(kShuf, d7);
865 d0 = Shuf(kShuf, d0);
866 d8 = Xor(d8, d6);
867 d1 = Xor(d1, z);
868 d1 = Add(d1, d7);
869 z = Fetch128(s + 64);
870 d2 = Add(d2, z);
871 d5 = Shuf(kShuf, d5);
872 d4 = Add(d4, d2);
873 d6 = Xor(d6, z);
874 d6 = Xor(d6, d11);
875 std::swap(d8, d2);
876 z = Fetch128(s + 80);
877 d7 = Xor(d7, z);
878 d8 = Shuf(kShuf, d8);
879 d1 = Shuf(kShuf, d1);
880 d0 = Add(d0, d7);
881 d2 = Add(d2, z);
882 d2 = Add(d2, d8);
883 std::swap(d1, d7);
884 z = Fetch128(s + 96);
885 d4 = Shuf(kShuf, d4);
886 d6 = Shuf(kShuf, d6);
887 d8 = Mul(kMult, d8);
888 d5 = Xor(d5, d11);
889 d7 = Xor(d7, z);
890 d7 = Add(d7, d4);
891 std::swap(d6, d0);
892 z = Fetch128(s + 112);
893 d8 = Add(d8, z);
894 d0 = Shuf(kShuf, d0);
895 d2 = Shuf(kShuf, d2);
896 d1 = Xor(d1, d8);
897 d10 = Xor(d10, z);
898 d10 = Xor(d10, d0);
899 std::swap(d11, d5);
900 z = Fetch128(s + 128);
901 d4 = Add(d4, z);
902 d5 = Shuf(kShuf, d5);
903 d7 = Shuf(kShuf, d7);
904 d6 = Add(d6, d4);
905 d8 = Xor(d8, z);
906 d8 = Xor(d8, d5);
907 std::swap(d4, d10);
908 z = Fetch128(s + 144);
909 d0 = Add(d0, z);
910 d1 = Shuf(kShuf, d1);
911 d2 = Add(d2, d0);
912 d4 = Xor(d4, z);
913 d4 = Xor(d4, d1);
914 z = Fetch128(s + 160);
915 d5 = Add(d5, z);
916 d6 = Shuf(kShuf, d6);
917 d8 = Shuf(kShuf, d8);
918 d7 = Xor(d7, d5);
919 d0 = Xor(d0, z);
920 d0 = Xor(d0, d6);
921 std::swap(d2, d8);
922 z = Fetch128(s + 176);
923 d1 = Add(d1, z);
924 d2 = Shuf(kShuf, d2);
925 d4 = Shuf(kShuf, d4);
926 d5 = Mul(kMult, d5);
927 d5 = Xor(d5, z);
928 d5 = Xor(d5, d2);
929 std::swap(d7, d1);
930 z = Fetch128(s + 192);
931 d6 = Add(d6, z);
932 d7 = Shuf(kShuf, d7);
933 d0 = Shuf(kShuf, d0);
934 d8 = Add(d8, d6);
935 d1 = Xor(d1, z);
936 d1 = Xor(d1, d7);
937 std::swap(d0, d6);
938 z = Fetch128(s + 208);
939 d2 = Add(d2, z);
940 d5 = Shuf(kShuf, d5);
941 d4 = Xor(d4, d2);
942 d6 = Xor(d6, z);
943 d6 = Xor(d6, d9);
944 std::swap(d5, d11);
945 z = Fetch128(s + 224);
946 d7 = Add(d7, z);
947 d8 = Shuf(kShuf, d8);
948 d1 = Shuf(kShuf, d1);
949 d0 = Xor(d0, d7);
950 d2 = Xor(d2, z);
951 d2 = Xor(d2, d8);
952 std::swap(d10, d4);
953 z = Fetch128(s + 240);
954 d3 = Add(d3, z);
955 d4 = Shuf(kShuf, d4);
956 d6 = Shuf(kShuf, d6);
957 d7 = Mul(kMult, d7);
958 d5 = Add(d5, d3);
959 d7 = Xor(d7, z);
960 d7 = Xor(d7, d4);
961 std::swap(d3, d9);
962 s += 256;
963 } while (s != end);
964 d6 = Add(Mul(kMult, d6), _mm_cvtsi64_si128(n));
965 if (n % 256 != 0) {
966 d7 = Add(_mm_shuffle_epi32(d8, (0 << 6) + (3 << 4) + (2 << 2) + (1 << 0)), d7);
967 d8 = Add(Mul(kMult, d8), _mm_cvtsi64_si128(farmhashxo::Hash64(s, n % 256)));
968 }
969 __m128i t[8];
970 d0 = Mul(kMult, Shuf(kShuf, Mul(kMult, d0)));
971 d3 = Mul(kMult, Shuf(kShuf, Mul(kMult, d3)));
972 d9 = Mul(kMult, Shuf(kShuf, Mul(kMult, d9)));
973 d1 = Mul(kMult, Shuf(kShuf, Mul(kMult, d1)));
974 d0 = Add(d11, d0);
975 d3 = Xor(d7, d3);
976 d9 = Add(d8, d9);
977 d1 = Add(d10, d1);
978 d4 = Add(d3, d4);
979 d5 = Add(d9, d5);
980 d6 = Xor(d1, d6);
981 d2 = Add(d0, d2);
982 t[0] = d0;
983 t[1] = d3;
984 t[2] = d9;
985 t[3] = d1;
986 t[4] = d4;
987 t[5] = d5;
988 t[6] = d6;
989 t[7] = d2;
990 return farmhashxo::Hash64(reinterpret_cast<const char*>(t), sizeof(t));
991 }
992
993 uint64_t Hash64(const char *s, size_t len) {
994 // Empirically, farmhashxo seems faster until length 512.
995 return len >= 512 ? Hash64Long(s, len, k2, k1) : farmhashxo::Hash64(s, len);
996 }
997
998 uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
999 return len >= 512 ? Hash64Long(s, len, k1, seed) :
1000 farmhashxo::Hash64WithSeed(s, len, seed);
1001 }
1002
1003 uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) {
1004 return len >= 512 ? Hash64Long(s, len, seed0, seed1) :
1005 farmhashxo::Hash64WithSeeds(s, len, seed0, seed1);
1006 }
1007
1008 #endif
1009 } // namespace farmhashte
1010 namespace farmhashnt {
1011 #if !can_use_sse41 || !x86_64
1012
Hash32(const char * s,size_t len)1013 uint32_t Hash32(const char *s, size_t len) {
1014 FARMHASH_DIE_IF_MISCONFIGURED;
1015 return s == NULL ? 0 : len;
1016 }
1017
Hash32WithSeed(const char * s,size_t len,uint32_t seed)1018 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1019 FARMHASH_DIE_IF_MISCONFIGURED;
1020 return seed + Hash32(s, len);
1021 }
1022
1023 #else
1024
1025 uint32_t Hash32(const char *s, size_t len) {
1026 return static_cast<uint32_t>(farmhashte::Hash64(s, len));
1027 }
1028
1029 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1030 return static_cast<uint32_t>(farmhashte::Hash64WithSeed(s, len, seed));
1031 }
1032
1033 #endif
1034 } // namespace farmhashnt
1035 namespace farmhashmk {
1036 #undef Fetch
1037 #define Fetch Fetch32
1038
1039 #undef Rotate
1040 #define Rotate Rotate32
1041
1042 #undef Bswap
1043 #define Bswap Bswap32
1044
Hash32Len13to24(const char * s,size_t len,uint32_t seed=0)1045 STATIC_INLINE uint32_t Hash32Len13to24(const char *s, size_t len, uint32_t seed = 0) {
1046 uint32_t a = Fetch(s - 4 + (len >> 1));
1047 uint32_t b = Fetch(s + 4);
1048 uint32_t c = Fetch(s + len - 8);
1049 uint32_t d = Fetch(s + (len >> 1));
1050 uint32_t e = Fetch(s);
1051 uint32_t f = Fetch(s + len - 4);
1052 uint32_t h = d * c1 + len + seed;
1053 a = Rotate(a, 12) + f;
1054 h = Mur(c, h) + a;
1055 a = Rotate(a, 3) + c;
1056 h = Mur(e, h) + a;
1057 a = Rotate(a + f, 12) + d;
1058 h = Mur(b ^ seed, h) + a;
1059 return fmix(h);
1060 }
1061
Hash32Len0to4(const char * s,size_t len,uint32_t seed=0)1062 STATIC_INLINE uint32_t Hash32Len0to4(const char *s, size_t len, uint32_t seed = 0) {
1063 uint32_t b = seed;
1064 uint32_t c = 9;
1065 for (size_t i = 0; i < len; i++) {
1066 signed char v = s[i];
1067 b = b * c1 + v;
1068 c ^= b;
1069 }
1070 return fmix(Mur(b, Mur(len, c)));
1071 }
1072
Hash32Len5to12(const char * s,size_t len,uint32_t seed=0)1073 STATIC_INLINE uint32_t Hash32Len5to12(const char *s, size_t len, uint32_t seed = 0) {
1074 uint32_t a = len, b = len * 5, c = 9, d = b + seed;
1075 a += Fetch(s);
1076 b += Fetch(s + len - 4);
1077 c += Fetch(s + ((len >> 1) & 4));
1078 return fmix(seed ^ Mur(c, Mur(b, Mur(a, d))));
1079 }
1080
Hash32(const char * s,size_t len)1081 uint32_t Hash32(const char *s, size_t len) {
1082 if (len <= 24) {
1083 return len <= 12 ?
1084 (len <= 4 ? Hash32Len0to4(s, len) : Hash32Len5to12(s, len)) :
1085 Hash32Len13to24(s, len);
1086 }
1087
1088 // len > 24
1089 uint32_t h = len, g = c1 * len, f = g;
1090 uint32_t a0 = Rotate(Fetch(s + len - 4) * c1, 17) * c2;
1091 uint32_t a1 = Rotate(Fetch(s + len - 8) * c1, 17) * c2;
1092 uint32_t a2 = Rotate(Fetch(s + len - 16) * c1, 17) * c2;
1093 uint32_t a3 = Rotate(Fetch(s + len - 12) * c1, 17) * c2;
1094 uint32_t a4 = Rotate(Fetch(s + len - 20) * c1, 17) * c2;
1095 h ^= a0;
1096 h = Rotate(h, 19);
1097 h = h * 5 + 0xe6546b64;
1098 h ^= a2;
1099 h = Rotate(h, 19);
1100 h = h * 5 + 0xe6546b64;
1101 g ^= a1;
1102 g = Rotate(g, 19);
1103 g = g * 5 + 0xe6546b64;
1104 g ^= a3;
1105 g = Rotate(g, 19);
1106 g = g * 5 + 0xe6546b64;
1107 f += a4;
1108 f = Rotate(f, 19) + 113;
1109 size_t iters = (len - 1) / 20;
1110 do {
1111 uint32_t a = Fetch(s);
1112 uint32_t b = Fetch(s + 4);
1113 uint32_t c = Fetch(s + 8);
1114 uint32_t d = Fetch(s + 12);
1115 uint32_t e = Fetch(s + 16);
1116 h += a;
1117 g += b;
1118 f += c;
1119 h = Mur(d, h) + e;
1120 g = Mur(c, g) + a;
1121 f = Mur(b + e * c1, f) + d;
1122 f += g;
1123 g += f;
1124 s += 20;
1125 } while (--iters != 0);
1126 g = Rotate(g, 11) * c1;
1127 g = Rotate(g, 17) * c1;
1128 f = Rotate(f, 11) * c1;
1129 f = Rotate(f, 17) * c1;
1130 h = Rotate(h + g, 19);
1131 h = h * 5 + 0xe6546b64;
1132 h = Rotate(h, 17) * c1;
1133 h = Rotate(h + f, 19);
1134 h = h * 5 + 0xe6546b64;
1135 h = Rotate(h, 17) * c1;
1136 return h;
1137 }
1138
Hash32WithSeed(const char * s,size_t len,uint32_t seed)1139 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1140 if (len <= 24) {
1141 if (len >= 13) return Hash32Len13to24(s, len, seed * c1);
1142 else if (len >= 5) return Hash32Len5to12(s, len, seed);
1143 else return Hash32Len0to4(s, len, seed);
1144 }
1145 uint32_t h = Hash32Len13to24(s, 24, seed ^ len);
1146 return Mur(Hash32(s + 24, len - 24) + seed, h);
1147 }
1148 } // namespace farmhashmk
1149 namespace farmhashsu {
1150 #if !can_use_sse42 || !can_use_aesni
1151
Hash32(const char * s,size_t len)1152 uint32_t Hash32(const char *s, size_t len) {
1153 FARMHASH_DIE_IF_MISCONFIGURED;
1154 return s == NULL ? 0 : len;
1155 }
1156
Hash32WithSeed(const char * s,size_t len,uint32_t seed)1157 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1158 FARMHASH_DIE_IF_MISCONFIGURED;
1159 return seed + Hash32(s, len);
1160 }
1161
1162 #else
1163
1164 #undef Fetch
1165 #define Fetch Fetch32
1166
1167 #undef Rotate
1168 #define Rotate Rotate32
1169
1170 #undef Bswap
1171 #define Bswap Bswap32
1172
1173 // Helpers for data-parallel operations (4x 32-bits).
1174 STATIC_INLINE __m128i Add(__m128i x, __m128i y) { return _mm_add_epi32(x, y); }
1175 STATIC_INLINE __m128i Xor(__m128i x, __m128i y) { return _mm_xor_si128(x, y); }
1176 STATIC_INLINE __m128i Or(__m128i x, __m128i y) { return _mm_or_si128(x, y); }
1177 STATIC_INLINE __m128i Mul(__m128i x, __m128i y) { return _mm_mullo_epi32(x, y); }
1178 STATIC_INLINE __m128i Mul5(__m128i x) { return Add(x, _mm_slli_epi32(x, 2)); }
1179 STATIC_INLINE __m128i RotateLeft(__m128i x, int c) {
1180 return Or(_mm_slli_epi32(x, c),
1181 _mm_srli_epi32(x, 32 - c));
1182 }
1183 STATIC_INLINE __m128i Rol17(__m128i x) { return RotateLeft(x, 17); }
1184 STATIC_INLINE __m128i Rol19(__m128i x) { return RotateLeft(x, 19); }
1185 STATIC_INLINE __m128i Shuffle0321(__m128i x) {
1186 return _mm_shuffle_epi32(x, (0 << 6) + (3 << 4) + (2 << 2) + (1 << 0));
1187 }
1188
1189 uint32_t Hash32(const char *s, size_t len) {
1190 const uint32_t seed = 81;
1191 if (len <= 24) {
1192 return len <= 12 ?
1193 (len <= 4 ?
1194 farmhashmk::Hash32Len0to4(s, len) :
1195 farmhashmk::Hash32Len5to12(s, len)) :
1196 farmhashmk::Hash32Len13to24(s, len);
1197 }
1198
1199 if (len < 40) {
1200 uint32_t a = len, b = seed * c2, c = a + b;
1201 a += Fetch(s + len - 4);
1202 b += Fetch(s + len - 20);
1203 c += Fetch(s + len - 16);
1204 uint32_t d = a;
1205 a = folly::external::farmhash::Rotate32(a, 21);
1206 a = Mur(a, Mur(b, _mm_crc32_u32(c, d)));
1207 a += Fetch(s + len - 12);
1208 b += Fetch(s + len - 8);
1209 d += a;
1210 a += d;
1211 b = Mur(b, d) * c2;
1212 a = _mm_crc32_u32(a, b + c);
1213 return farmhashmk::Hash32Len13to24(s, (len + 1) / 2, a) + b;
1214 }
1215
1216 #undef Mulc1
1217 #define Mulc1(x) Mul((x), cc1)
1218
1219 #undef Mulc2
1220 #define Mulc2(x) Mul((x), cc2)
1221
1222 #undef Murk
1223 #define Murk(a, h) \
1224 Add(k, \
1225 Mul5( \
1226 Rol19( \
1227 Xor( \
1228 Mulc2( \
1229 Rol17( \
1230 Mulc1(a))), \
1231 (h)))))
1232
1233 const __m128i cc1 = _mm_set1_epi32(c1);
1234 const __m128i cc2 = _mm_set1_epi32(c2);
1235 __m128i h = _mm_set1_epi32(seed);
1236 __m128i g = _mm_set1_epi32(c1 * seed);
1237 __m128i f = g;
1238 __m128i k = _mm_set1_epi32(0xe6546b64);
1239 __m128i q;
1240 if (len < 80) {
1241 __m128i a = Fetch128(s);
1242 __m128i b = Fetch128(s + 16);
1243 __m128i c = Fetch128(s + (len - 15) / 2);
1244 __m128i d = Fetch128(s + len - 32);
1245 __m128i e = Fetch128(s + len - 16);
1246 h = Add(h, a);
1247 g = Add(g, b);
1248 q = g;
1249 g = Shuffle0321(g);
1250 f = Add(f, c);
1251 __m128i be = Add(b, Mulc1(e));
1252 h = Add(h, f);
1253 f = Add(f, h);
1254 h = Add(Murk(d, h), e);
1255 k = Xor(k, _mm_shuffle_epi8(g, f));
1256 g = Add(Xor(c, g), a);
1257 f = Add(Xor(be, f), d);
1258 k = Add(k, be);
1259 k = Add(k, _mm_shuffle_epi8(f, h));
1260 f = Add(f, g);
1261 g = Add(g, f);
1262 g = Add(_mm_set1_epi32(len), Mulc1(g));
1263 } else {
1264 // len >= 80
1265 // The following is loosely modelled after farmhashmk::Hash32.
1266 size_t iters = (len - 1) / 80;
1267 len -= iters * 80;
1268
1269 #undef Chunk
1270 #define Chunk() do { \
1271 __m128i a = Fetch128(s); \
1272 __m128i b = Fetch128(s + 16); \
1273 __m128i c = Fetch128(s + 32); \
1274 __m128i d = Fetch128(s + 48); \
1275 __m128i e = Fetch128(s + 64); \
1276 h = Add(h, a); \
1277 g = Add(g, b); \
1278 g = Shuffle0321(g); \
1279 f = Add(f, c); \
1280 __m128i be = Add(b, Mulc1(e)); \
1281 h = Add(h, f); \
1282 f = Add(f, h); \
1283 h = Add(h, d); \
1284 q = Add(q, e); \
1285 h = Rol17(h); \
1286 h = Mulc1(h); \
1287 k = Xor(k, _mm_shuffle_epi8(g, f)); \
1288 g = Add(Xor(c, g), a); \
1289 f = Add(Xor(be, f), d); \
1290 std::swap(f, q); \
1291 q = _mm_aesimc_si128(q); \
1292 k = Add(k, be); \
1293 k = Add(k, _mm_shuffle_epi8(f, h)); \
1294 f = Add(f, g); \
1295 g = Add(g, f); \
1296 f = Mulc1(f); \
1297 } while (0)
1298
1299 q = g;
1300 while (iters-- != 0) {
1301 Chunk();
1302 s += 80;
1303 }
1304
1305 if (len != 0) {
1306 h = Add(h, _mm_set1_epi32(len));
1307 s = s + len - 80;
1308 Chunk();
1309 }
1310 }
1311
1312 g = Shuffle0321(g);
1313 k = Xor(k, g);
1314 k = Xor(k, q);
1315 h = Xor(h, q);
1316 f = Mulc1(f);
1317 k = Mulc2(k);
1318 g = Mulc1(g);
1319 h = Mulc2(h);
1320 k = Add(k, _mm_shuffle_epi8(g, f));
1321 h = Add(h, f);
1322 f = Add(f, h);
1323 g = Add(g, k);
1324 k = Add(k, g);
1325 k = Xor(k, _mm_shuffle_epi8(f, h));
1326 __m128i buf[4];
1327 buf[0] = f;
1328 buf[1] = g;
1329 buf[2] = k;
1330 buf[3] = h;
1331 s = reinterpret_cast<char*>(buf);
1332 uint32_t x = Fetch(s);
1333 uint32_t y = Fetch(s+4);
1334 uint32_t z = Fetch(s+8);
1335 x = _mm_crc32_u32(x, Fetch(s+12));
1336 y = _mm_crc32_u32(y, Fetch(s+16));
1337 z = _mm_crc32_u32(z * c1, Fetch(s+20));
1338 x = _mm_crc32_u32(x, Fetch(s+24));
1339 y = _mm_crc32_u32(y * c1, Fetch(s+28));
1340 uint32_t o = y;
1341 z = _mm_crc32_u32(z, Fetch(s+32));
1342 x = _mm_crc32_u32(x * c1, Fetch(s+36));
1343 y = _mm_crc32_u32(y, Fetch(s+40));
1344 z = _mm_crc32_u32(z * c1, Fetch(s+44));
1345 x = _mm_crc32_u32(x, Fetch(s+48));
1346 y = _mm_crc32_u32(y * c1, Fetch(s+52));
1347 z = _mm_crc32_u32(z, Fetch(s+56));
1348 x = _mm_crc32_u32(x, Fetch(s+60));
1349 return (o - x + y - z) * c1;
1350 }
1351
1352 #undef Chunk
1353 #undef Murk
1354 #undef Mulc2
1355 #undef Mulc1
1356
1357 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1358 if (len <= 24) {
1359 if (len >= 13) return farmhashmk::Hash32Len13to24(s, len, seed * c1);
1360 else if (len >= 5) return farmhashmk::Hash32Len5to12(s, len, seed);
1361 else return farmhashmk::Hash32Len0to4(s, len, seed);
1362 }
1363 uint32_t h = farmhashmk::Hash32Len13to24(s, 24, seed ^ len);
1364 return _mm_crc32_u32(Hash32(s + 24, len - 24) + seed, h);
1365 }
1366
1367 #endif
1368 } // namespace farmhashsu
1369 namespace farmhashsa {
1370 #if !can_use_sse42
1371
Hash32(const char * s,size_t len)1372 uint32_t Hash32(const char *s, size_t len) {
1373 FARMHASH_DIE_IF_MISCONFIGURED;
1374 return s == NULL ? 0 : len;
1375 }
1376
Hash32WithSeed(const char * s,size_t len,uint32_t seed)1377 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1378 FARMHASH_DIE_IF_MISCONFIGURED;
1379 return seed + Hash32(s, len);
1380 }
1381
1382 #else
1383
1384 #undef Fetch
1385 #define Fetch Fetch32
1386
1387 #undef Rotate
1388 #define Rotate Rotate32
1389
1390 #undef Bswap
1391 #define Bswap Bswap32
1392
1393 // Helpers for data-parallel operations (4x 32-bits).
1394 STATIC_INLINE __m128i Add(__m128i x, __m128i y) { return _mm_add_epi32(x, y); }
1395 STATIC_INLINE __m128i Xor(__m128i x, __m128i y) { return _mm_xor_si128(x, y); }
1396 STATIC_INLINE __m128i Or(__m128i x, __m128i y) { return _mm_or_si128(x, y); }
1397 STATIC_INLINE __m128i Mul(__m128i x, __m128i y) { return _mm_mullo_epi32(x, y); }
1398 STATIC_INLINE __m128i Mul5(__m128i x) { return Add(x, _mm_slli_epi32(x, 2)); }
1399 STATIC_INLINE __m128i Rotate(__m128i x, int c) {
1400 return Or(_mm_slli_epi32(x, c),
1401 _mm_srli_epi32(x, 32 - c));
1402 }
1403 STATIC_INLINE __m128i Rot17(__m128i x) { return Rotate(x, 17); }
1404 STATIC_INLINE __m128i Rot19(__m128i x) { return Rotate(x, 19); }
1405 STATIC_INLINE __m128i Shuffle0321(__m128i x) {
1406 return _mm_shuffle_epi32(x, (0 << 6) + (3 << 4) + (2 << 2) + (1 << 0));
1407 }
1408
1409 uint32_t Hash32(const char *s, size_t len) {
1410 const uint32_t seed = 81;
1411 if (len <= 24) {
1412 return len <= 12 ?
1413 (len <= 4 ?
1414 farmhashmk::Hash32Len0to4(s, len) :
1415 farmhashmk::Hash32Len5to12(s, len)) :
1416 farmhashmk::Hash32Len13to24(s, len);
1417 }
1418
1419 if (len < 40) {
1420 uint32_t a = len, b = seed * c2, c = a + b;
1421 a += Fetch(s + len - 4);
1422 b += Fetch(s + len - 20);
1423 c += Fetch(s + len - 16);
1424 uint32_t d = a;
1425 a = folly::external::farmhash::Rotate32(a, 21);
1426 a = Mur(a, Mur(b, Mur(c, d)));
1427 a += Fetch(s + len - 12);
1428 b += Fetch(s + len - 8);
1429 d += a;
1430 a += d;
1431 b = Mur(b, d) * c2;
1432 a = _mm_crc32_u32(a, b + c);
1433 return farmhashmk::Hash32Len13to24(s, (len + 1) / 2, a) + b;
1434 }
1435
1436 #undef Mulc1
1437 #define Mulc1(x) Mul((x), cc1)
1438
1439 #undef Mulc2
1440 #define Mulc2(x) Mul((x), cc2)
1441
1442 #undef Murk
1443 #define Murk(a, h) \
1444 Add(k, \
1445 Mul5( \
1446 Rot19( \
1447 Xor( \
1448 Mulc2( \
1449 Rot17( \
1450 Mulc1(a))), \
1451 (h)))))
1452
1453 const __m128i cc1 = _mm_set1_epi32(c1);
1454 const __m128i cc2 = _mm_set1_epi32(c2);
1455 __m128i h = _mm_set1_epi32(seed);
1456 __m128i g = _mm_set1_epi32(c1 * seed);
1457 __m128i f = g;
1458 __m128i k = _mm_set1_epi32(0xe6546b64);
1459 if (len < 80) {
1460 __m128i a = Fetch128(s);
1461 __m128i b = Fetch128(s + 16);
1462 __m128i c = Fetch128(s + (len - 15) / 2);
1463 __m128i d = Fetch128(s + len - 32);
1464 __m128i e = Fetch128(s + len - 16);
1465 h = Add(h, a);
1466 g = Add(g, b);
1467 g = Shuffle0321(g);
1468 f = Add(f, c);
1469 __m128i be = Add(b, Mulc1(e));
1470 h = Add(h, f);
1471 f = Add(f, h);
1472 h = Add(Murk(d, h), e);
1473 k = Xor(k, _mm_shuffle_epi8(g, f));
1474 g = Add(Xor(c, g), a);
1475 f = Add(Xor(be, f), d);
1476 k = Add(k, be);
1477 k = Add(k, _mm_shuffle_epi8(f, h));
1478 f = Add(f, g);
1479 g = Add(g, f);
1480 g = Add(_mm_set1_epi32(len), Mulc1(g));
1481 } else {
1482 // len >= 80
1483 // The following is loosely modelled after farmhashmk::Hash32.
1484 size_t iters = (len - 1) / 80;
1485 len -= iters * 80;
1486
1487 #undef Chunk
1488 #define Chunk() do { \
1489 __m128i a = Fetch128(s); \
1490 __m128i b = Fetch128(s + 16); \
1491 __m128i c = Fetch128(s + 32); \
1492 __m128i d = Fetch128(s + 48); \
1493 __m128i e = Fetch128(s + 64); \
1494 h = Add(h, a); \
1495 g = Add(g, b); \
1496 g = Shuffle0321(g); \
1497 f = Add(f, c); \
1498 __m128i be = Add(b, Mulc1(e)); \
1499 h = Add(h, f); \
1500 f = Add(f, h); \
1501 h = Add(Murk(d, h), e); \
1502 k = Xor(k, _mm_shuffle_epi8(g, f)); \
1503 g = Add(Xor(c, g), a); \
1504 f = Add(Xor(be, f), d); \
1505 k = Add(k, be); \
1506 k = Add(k, _mm_shuffle_epi8(f, h)); \
1507 f = Add(f, g); \
1508 g = Add(g, f); \
1509 f = Mulc1(f); \
1510 } while (0)
1511
1512 while (iters-- != 0) {
1513 Chunk();
1514 s += 80;
1515 }
1516
1517 if (len != 0) {
1518 h = Add(h, _mm_set1_epi32(len));
1519 s = s + len - 80;
1520 Chunk();
1521 }
1522 }
1523
1524 g = Shuffle0321(g);
1525 k = Xor(k, g);
1526 f = Mulc1(f);
1527 k = Mulc2(k);
1528 g = Mulc1(g);
1529 h = Mulc2(h);
1530 k = Add(k, _mm_shuffle_epi8(g, f));
1531 h = Add(h, f);
1532 f = Add(f, h);
1533 g = Add(g, k);
1534 k = Add(k, g);
1535 k = Xor(k, _mm_shuffle_epi8(f, h));
1536 __m128i buf[4];
1537 buf[0] = f;
1538 buf[1] = g;
1539 buf[2] = k;
1540 buf[3] = h;
1541 s = reinterpret_cast<char*>(buf);
1542 uint32_t x = Fetch(s);
1543 uint32_t y = Fetch(s+4);
1544 uint32_t z = Fetch(s+8);
1545 x = _mm_crc32_u32(x, Fetch(s+12));
1546 y = _mm_crc32_u32(y, Fetch(s+16));
1547 z = _mm_crc32_u32(z * c1, Fetch(s+20));
1548 x = _mm_crc32_u32(x, Fetch(s+24));
1549 y = _mm_crc32_u32(y * c1, Fetch(s+28));
1550 uint32_t o = y;
1551 z = _mm_crc32_u32(z, Fetch(s+32));
1552 x = _mm_crc32_u32(x * c1, Fetch(s+36));
1553 y = _mm_crc32_u32(y, Fetch(s+40));
1554 z = _mm_crc32_u32(z * c1, Fetch(s+44));
1555 x = _mm_crc32_u32(x, Fetch(s+48));
1556 y = _mm_crc32_u32(y * c1, Fetch(s+52));
1557 z = _mm_crc32_u32(z, Fetch(s+56));
1558 x = _mm_crc32_u32(x, Fetch(s+60));
1559 return (o - x + y - z) * c1;
1560 }
1561
1562 #undef Chunk
1563 #undef Murk
1564 #undef Mulc2
1565 #undef Mulc1
1566
1567 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1568 if (len <= 24) {
1569 if (len >= 13) return farmhashmk::Hash32Len13to24(s, len, seed * c1);
1570 else if (len >= 5) return farmhashmk::Hash32Len5to12(s, len, seed);
1571 else return farmhashmk::Hash32Len0to4(s, len, seed);
1572 }
1573 uint32_t h = farmhashmk::Hash32Len13to24(s, 24, seed ^ len);
1574 return _mm_crc32_u32(Hash32(s + 24, len - 24) + seed, h);
1575 }
1576
1577 #endif
1578 } // namespace farmhashsa
1579 namespace farmhashcc {
1580 // This file provides a 32-bit hash equivalent to CityHash32 (v1.1.1)
1581 // and a 128-bit hash equivalent to CityHash128 (v1.1.1). It also provides
1582 // a seeded 32-bit hash function similar to CityHash32.
1583
1584 #undef Fetch
1585 #define Fetch Fetch32
1586
1587 #undef Rotate
1588 #define Rotate Rotate32
1589
1590 #undef Bswap
1591 #define Bswap Bswap32
1592
Hash32Len13to24(const char * s,size_t len)1593 STATIC_INLINE uint32_t Hash32Len13to24(const char *s, size_t len) {
1594 uint32_t a = Fetch(s - 4 + (len >> 1));
1595 uint32_t b = Fetch(s + 4);
1596 uint32_t c = Fetch(s + len - 8);
1597 uint32_t d = Fetch(s + (len >> 1));
1598 uint32_t e = Fetch(s);
1599 uint32_t f = Fetch(s + len - 4);
1600 uint32_t h = len;
1601
1602 return fmix(Mur(f, Mur(e, Mur(d, Mur(c, Mur(b, Mur(a, h)))))));
1603 }
1604
Hash32Len0to4(const char * s,size_t len)1605 STATIC_INLINE uint32_t Hash32Len0to4(const char *s, size_t len) {
1606 uint32_t b = 0;
1607 uint32_t c = 9;
1608 for (size_t i = 0; i < len; i++) {
1609 signed char v = s[i];
1610 b = b * c1 + v;
1611 c ^= b;
1612 }
1613 return fmix(Mur(b, Mur(len, c)));
1614 }
1615
Hash32Len5to12(const char * s,size_t len)1616 STATIC_INLINE uint32_t Hash32Len5to12(const char *s, size_t len) {
1617 uint32_t a = len, b = len * 5, c = 9, d = b;
1618 a += Fetch(s);
1619 b += Fetch(s + len - 4);
1620 c += Fetch(s + ((len >> 1) & 4));
1621 return fmix(Mur(c, Mur(b, Mur(a, d))));
1622 }
1623
Hash32(const char * s,size_t len)1624 uint32_t Hash32(const char *s, size_t len) {
1625 if (len <= 24) {
1626 return len <= 12 ?
1627 (len <= 4 ? Hash32Len0to4(s, len) : Hash32Len5to12(s, len)) :
1628 Hash32Len13to24(s, len);
1629 }
1630
1631 // len > 24
1632 uint32_t h = len, g = c1 * len, f = g;
1633 {
1634 uint32_t a0 = Rotate(Fetch(s + len - 4) * c1, 17) * c2;
1635 uint32_t a1 = Rotate(Fetch(s + len - 8) * c1, 17) * c2;
1636 uint32_t a2 = Rotate(Fetch(s + len - 16) * c1, 17) * c2;
1637 uint32_t a3 = Rotate(Fetch(s + len - 12) * c1, 17) * c2;
1638 uint32_t a4 = Rotate(Fetch(s + len - 20) * c1, 17) * c2;
1639 h ^= a0;
1640 h = Rotate(h, 19);
1641 h = h * 5 + 0xe6546b64;
1642 h ^= a2;
1643 h = Rotate(h, 19);
1644 h = h * 5 + 0xe6546b64;
1645 g ^= a1;
1646 g = Rotate(g, 19);
1647 g = g * 5 + 0xe6546b64;
1648 g ^= a3;
1649 g = Rotate(g, 19);
1650 g = g * 5 + 0xe6546b64;
1651 f += a4;
1652 f = Rotate(f, 19);
1653 f = f * 5 + 0xe6546b64;
1654 }
1655 size_t iters = (len - 1) / 20;
1656 do {
1657 uint32_t a0 = Rotate(Fetch(s) * c1, 17) * c2;
1658 uint32_t a1 = Fetch(s + 4);
1659 uint32_t a2 = Rotate(Fetch(s + 8) * c1, 17) * c2;
1660 uint32_t a3 = Rotate(Fetch(s + 12) * c1, 17) * c2;
1661 uint32_t a4 = Fetch(s + 16);
1662 h ^= a0;
1663 h = Rotate(h, 18);
1664 h = h * 5 + 0xe6546b64;
1665 f += a1;
1666 f = Rotate(f, 19);
1667 f = f * c1;
1668 g += a2;
1669 g = Rotate(g, 18);
1670 g = g * 5 + 0xe6546b64;
1671 h ^= a3 + a1;
1672 h = Rotate(h, 19);
1673 h = h * 5 + 0xe6546b64;
1674 g ^= a4;
1675 g = Bswap(g) * 5;
1676 h += a4 * 5;
1677 h = Bswap(h);
1678 f += a0;
1679 PERMUTE3(f, h, g);
1680 s += 20;
1681 } while (--iters != 0);
1682 g = Rotate(g, 11) * c1;
1683 g = Rotate(g, 17) * c1;
1684 f = Rotate(f, 11) * c1;
1685 f = Rotate(f, 17) * c1;
1686 h = Rotate(h + g, 19);
1687 h = h * 5 + 0xe6546b64;
1688 h = Rotate(h, 17) * c1;
1689 h = Rotate(h + f, 19);
1690 h = h * 5 + 0xe6546b64;
1691 h = Rotate(h, 17) * c1;
1692 return h;
1693 }
1694
Hash32WithSeed(const char * s,size_t len,uint32_t seed)1695 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
1696 if (len <= 24) {
1697 if (len >= 13) return farmhashmk::Hash32Len13to24(s, len, seed * c1);
1698 else if (len >= 5) return farmhashmk::Hash32Len5to12(s, len, seed);
1699 else return farmhashmk::Hash32Len0to4(s, len, seed);
1700 }
1701 uint32_t h = farmhashmk::Hash32Len13to24(s, 24, seed ^ len);
1702 return Mur(Hash32(s + 24, len - 24) + seed, h);
1703 }
1704
1705 #undef Fetch
1706 #define Fetch Fetch64
1707
1708 #undef Rotate
1709 #define Rotate Rotate64
1710
1711 #undef Bswap
1712 #define Bswap Bswap64
1713
ShiftMix(uint64_t val)1714 STATIC_INLINE uint64_t ShiftMix(uint64_t val) {
1715 return val ^ (val >> 47);
1716 }
1717
HashLen16(uint64_t u,uint64_t v)1718 STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v) {
1719 return Hash128to64(Uint128(u, v));
1720 }
1721
HashLen16(uint64_t u,uint64_t v,uint64_t mul)1722 STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) {
1723 // Murmur-inspired hashing.
1724 uint64_t a = (u ^ v) * mul;
1725 a ^= (a >> 47);
1726 uint64_t b = (v ^ a) * mul;
1727 b ^= (b >> 47);
1728 b *= mul;
1729 return b;
1730 }
1731
HashLen0to16(const char * s,size_t len)1732 STATIC_INLINE uint64_t HashLen0to16(const char *s, size_t len) {
1733 if (len >= 8) {
1734 uint64_t mul = k2 + len * 2;
1735 uint64_t a = Fetch(s) + k2;
1736 uint64_t b = Fetch(s + len - 8);
1737 uint64_t c = Rotate(b, 37) * mul + a;
1738 uint64_t d = (Rotate(a, 25) + b) * mul;
1739 return HashLen16(c, d, mul);
1740 }
1741 if (len >= 4) {
1742 uint64_t mul = k2 + len * 2;
1743 uint64_t a = Fetch32(s);
1744 return HashLen16(len + (a << 3), Fetch32(s + len - 4), mul);
1745 }
1746 if (len > 0) {
1747 uint8_t a = s[0];
1748 uint8_t b = s[len >> 1];
1749 uint8_t c = s[len - 1];
1750 uint32_t y = static_cast<uint32_t>(a) + (static_cast<uint32_t>(b) << 8);
1751 uint32_t z = len + (static_cast<uint32_t>(c) << 2);
1752 return ShiftMix(y * k2 ^ z * k0) * k2;
1753 }
1754 return k2;
1755 }
1756
1757 // Return a 16-byte hash for 48 bytes. Quick and dirty.
1758 // Callers do best to use "random-looking" values for a and b.
WeakHashLen32WithSeeds(uint64_t w,uint64_t x,uint64_t y,uint64_t z,uint64_t a,uint64_t b)1759 STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
1760 uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) {
1761 a += w;
1762 b = Rotate(b + a + z, 21);
1763 uint64_t c = a;
1764 a += x;
1765 a += y;
1766 b += Rotate(a, 44);
1767 return make_pair(a + z, b + c);
1768 }
1769
1770 // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty.
WeakHashLen32WithSeeds(const char * s,uint64_t a,uint64_t b)1771 STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
1772 const char* s, uint64_t a, uint64_t b) {
1773 return WeakHashLen32WithSeeds(Fetch(s),
1774 Fetch(s + 8),
1775 Fetch(s + 16),
1776 Fetch(s + 24),
1777 a,
1778 b);
1779 }
1780
1781
1782
1783 // A subroutine for CityHash128(). Returns a decent 128-bit hash for strings
1784 // of any length representable in signed long. Based on City and Murmur.
CityMurmur(const char * s,size_t len,uint128_t seed)1785 STATIC_INLINE uint128_t CityMurmur(const char *s, size_t len, uint128_t seed) {
1786 uint64_t a = Uint128Low64(seed);
1787 uint64_t b = Uint128High64(seed);
1788 uint64_t c = 0;
1789 uint64_t d = 0;
1790 signed long l = len - 16;
1791 if (l <= 0) { // len <= 16
1792 a = ShiftMix(a * k1) * k1;
1793 c = b * k1 + HashLen0to16(s, len);
1794 d = ShiftMix(a + (len >= 8 ? Fetch(s) : c));
1795 } else { // len > 16
1796 c = HashLen16(Fetch(s + len - 8) + k1, a);
1797 d = HashLen16(b + len, c + Fetch(s + len - 16));
1798 a += d;
1799 do {
1800 a ^= ShiftMix(Fetch(s) * k1) * k1;
1801 a *= k1;
1802 b ^= a;
1803 c ^= ShiftMix(Fetch(s + 8) * k1) * k1;
1804 c *= k1;
1805 d ^= c;
1806 s += 16;
1807 l -= 16;
1808 } while (l > 0);
1809 }
1810 a = HashLen16(a, c);
1811 b = HashLen16(d, b);
1812 return Uint128(a ^ b, HashLen16(b, a));
1813 }
1814
CityHash128WithSeed(const char * s,size_t len,uint128_t seed)1815 uint128_t CityHash128WithSeed(const char *s, size_t len, uint128_t seed) {
1816 if (len < 128) {
1817 return CityMurmur(s, len, seed);
1818 }
1819
1820 // We expect len >= 128 to be the common case. Keep 56 bytes of state:
1821 // v, w, x, y, and z.
1822 pair<uint64_t, uint64_t> v, w;
1823 uint64_t x = Uint128Low64(seed);
1824 uint64_t y = Uint128High64(seed);
1825 uint64_t z = len * k1;
1826 v.first = Rotate(y ^ k1, 49) * k1 + Fetch(s);
1827 v.second = Rotate(v.first, 42) * k1 + Fetch(s + 8);
1828 w.first = Rotate(y + z, 35) * k1 + x;
1829 w.second = Rotate(x + Fetch(s + 88), 53) * k1;
1830
1831 // This is the same inner loop as CityHash64(), manually unrolled.
1832 do {
1833 x = Rotate(x + y + v.first + Fetch(s + 8), 37) * k1;
1834 y = Rotate(y + v.second + Fetch(s + 48), 42) * k1;
1835 x ^= w.second;
1836 y += v.first + Fetch(s + 40);
1837 z = Rotate(z + w.first, 33) * k1;
1838 v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
1839 w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16));
1840 std::swap(z, x);
1841 s += 64;
1842 x = Rotate(x + y + v.first + Fetch(s + 8), 37) * k1;
1843 y = Rotate(y + v.second + Fetch(s + 48), 42) * k1;
1844 x ^= w.second;
1845 y += v.first + Fetch(s + 40);
1846 z = Rotate(z + w.first, 33) * k1;
1847 v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
1848 w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16));
1849 std::swap(z, x);
1850 s += 64;
1851 len -= 128;
1852 } while (LIKELY(len >= 128));
1853 x += Rotate(v.first + z, 49) * k0;
1854 y = y * k0 + Rotate(w.second, 37);
1855 z = z * k0 + Rotate(w.first, 27);
1856 w.first *= 9;
1857 v.first *= k0;
1858 // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.
1859 for (size_t tail_done = 0; tail_done < len; ) {
1860 tail_done += 32;
1861 y = Rotate(x + y, 42) * k0 + v.second;
1862 w.first += Fetch(s + len - tail_done + 16);
1863 x = x * k0 + w.first;
1864 z += w.second + Fetch(s + len - tail_done);
1865 w.second += v.first;
1866 v = WeakHashLen32WithSeeds(s + len - tail_done, v.first + z, v.second);
1867 v.first *= k0;
1868 }
1869 // At this point our 56 bytes of state should contain more than
1870 // enough information for a strong 128-bit hash. We use two
1871 // different 56-byte-to-8-byte hashes to get a 16-byte final result.
1872 x = HashLen16(x, v.first);
1873 y = HashLen16(y + z, w.first);
1874 return Uint128(HashLen16(x + v.second, w.second) + y,
1875 HashLen16(x + w.second, y + v.second));
1876 }
1877
CityHash128(const char * s,size_t len)1878 STATIC_INLINE uint128_t CityHash128(const char *s, size_t len) {
1879 return len >= 16 ?
1880 CityHash128WithSeed(s + 16, len - 16,
1881 Uint128(Fetch(s), Fetch(s + 8) + k0)) :
1882 CityHash128WithSeed(s, len, Uint128(k0, k1));
1883 }
1884
Fingerprint128(const char * s,size_t len)1885 uint128_t Fingerprint128(const char* s, size_t len) {
1886 return CityHash128(s, len);
1887 }
1888 } // namespace farmhashcc
1889
1890 // BASIC STRING HASHING
1891
1892 // Hash function for a byte array. See also Hash(), below.
1893 // May change from time to time, may differ on different platforms, may differ
1894 // depending on NDEBUG.
Hash32(const char * s,size_t len)1895 uint32_t Hash32(const char* s, size_t len) {
1896 return DebugTweak(
1897 (can_use_sse41 & x86_64) ? farmhashnt::Hash32(s, len) :
1898 (can_use_sse42 & can_use_aesni) ? farmhashsu::Hash32(s, len) :
1899 can_use_sse42 ? farmhashsa::Hash32(s, len) :
1900 farmhashmk::Hash32(s, len));
1901 }
1902
1903 // Hash function for a byte array. For convenience, a 32-bit seed is also
1904 // hashed into the result.
1905 // May change from time to time, may differ on different platforms, may differ
1906 // depending on NDEBUG.
Hash32WithSeed(const char * s,size_t len,uint32_t seed)1907 uint32_t Hash32WithSeed(const char* s, size_t len, uint32_t seed) {
1908 return DebugTweak(
1909 (can_use_sse41 & x86_64) ? farmhashnt::Hash32WithSeed(s, len, seed) :
1910 (can_use_sse42 & can_use_aesni) ? farmhashsu::Hash32WithSeed(s, len, seed) :
1911 can_use_sse42 ? farmhashsa::Hash32WithSeed(s, len, seed) :
1912 farmhashmk::Hash32WithSeed(s, len, seed));
1913 }
1914
1915 // Hash function for a byte array. For convenience, a 64-bit seed is also
1916 // hashed into the result. See also Hash(), below.
1917 // May change from time to time, may differ on different platforms, may differ
1918 // depending on NDEBUG.
Hash64(const char * s,size_t len)1919 uint64_t Hash64(const char* s, size_t len) {
1920 return DebugTweak(
1921 (can_use_sse42 & x86_64) ?
1922 farmhashte::Hash64(s, len) :
1923 farmhashxo::Hash64(s, len));
1924 }
1925
1926 // Hash function for a byte array.
1927 // May change from time to time, may differ on different platforms, may differ
1928 // depending on NDEBUG.
Hash(const char * s,size_t len)1929 size_t Hash(const char* s, size_t len) {
1930 return sizeof(size_t) == 8 ? Hash64(s, len) : Hash32(s, len);
1931 }
1932
1933 // Hash function for a byte array. For convenience, a 64-bit seed is also
1934 // hashed into the result.
1935 // May change from time to time, may differ on different platforms, may differ
1936 // depending on NDEBUG.
Hash64WithSeed(const char * s,size_t len,uint64_t seed)1937 uint64_t Hash64WithSeed(const char* s, size_t len, uint64_t seed) {
1938 return DebugTweak(farmhashna::Hash64WithSeed(s, len, seed));
1939 }
1940
1941 // Hash function for a byte array. For convenience, two seeds are also
1942 // hashed into the result.
1943 // May change from time to time, may differ on different platforms, may differ
1944 // depending on NDEBUG.
Hash64WithSeeds(const char * s,size_t len,uint64_t seed0,uint64_t seed1)1945 uint64_t Hash64WithSeeds(const char* s, size_t len, uint64_t seed0, uint64_t seed1) {
1946 return DebugTweak(farmhashna::Hash64WithSeeds(s, len, seed0, seed1));
1947 }
1948
1949 // Hash function for a byte array.
1950 // May change from time to time, may differ on different platforms, may differ
1951 // depending on NDEBUG.
Hash128(const char * s,size_t len)1952 uint128_t Hash128(const char* s, size_t len) {
1953 return DebugTweak(farmhashcc::Fingerprint128(s, len));
1954 }
1955
1956 // Hash function for a byte array. For convenience, a 128-bit seed is also
1957 // hashed into the result.
1958 // May change from time to time, may differ on different platforms, may differ
1959 // depending on NDEBUG.
Hash128WithSeed(const char * s,size_t len,uint128_t seed)1960 uint128_t Hash128WithSeed(const char* s, size_t len, uint128_t seed) {
1961 return DebugTweak(farmhashcc::CityHash128WithSeed(s, len, seed));
1962 }
1963
1964 // BASIC NON-STRING HASHING
1965
1966 // FINGERPRINTING (i.e., good, portable, forever-fixed hash functions)
1967
1968 // Fingerprint function for a byte array. Most useful in 32-bit binaries.
Fingerprint32(const char * s,size_t len)1969 uint32_t Fingerprint32(const char* s, size_t len) {
1970 return farmhashmk::Hash32(s, len);
1971 }
1972
1973 // Fingerprint function for a byte array.
Fingerprint64(const char * s,size_t len)1974 uint64_t Fingerprint64(const char* s, size_t len) {
1975 return farmhashna::Hash64(s, len);
1976 }
1977
1978 // Fingerprint function for a byte array.
Fingerprint128(const char * s,size_t len)1979 uint128_t Fingerprint128(const char* s, size_t len) {
1980 return farmhashcc::Fingerprint128(s, len);
1981 }
1982
1983 // Older and still available but perhaps not as fast as the above:
1984 // farmhashns::Hash32{,WithSeed}()
1985
1986 } // namespace farmhash
1987 } // namespace external
1988 } // namespace folly
1989