// Copyright (c) 2014 Google, Inc. // // Permission is hereby granted, free of charge, to any person obtaining a copy // of this software and associated documentation files (the "Software"), to deal // in the Software without restriction, including without limitation the rights // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell // copies of the Software, and to permit persons to whom the Software is // furnished to do so, subject to the following conditions: // // The above copyright notice and this permission notice shall be included in // all copies or substantial portions of the Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN // THE SOFTWARE. // // FarmHash, by Geoff Pike // clang-format off #include <folly/external/farmhash/farmhash.h> #include <exception> // FARMHASH ASSUMPTIONS: Modify as needed, or use -DFARMHASH_ASSUME_SSE42 etc. // Note that if you use -DFARMHASH_ASSUME_SSE42 you likely need -msse42 // (or its equivalent for your compiler); if you use -DFARMHASH_ASSUME_AESNI // you likely need -maes (or its equivalent for your compiler). #ifdef FARMHASH_ASSUME_SSSE3 #undef FARMHASH_ASSUME_SSSE3 #define FARMHASH_ASSUME_SSSE3 … #endif #ifdef FARMHASH_ASSUME_SSE41 #undef FARMHASH_ASSUME_SSE41 #define FARMHASH_ASSUME_SSE41 … #endif #ifdef FARMHASH_ASSUME_SSE42 #undef FARMHASH_ASSUME_SSE42 #define FARMHASH_ASSUME_SSE42 … #endif #ifdef FARMHASH_ASSUME_AESNI #undef FARMHASH_ASSUME_AESNI #define FARMHASH_ASSUME_AESNI … #endif #ifdef FARMHASH_ASSUME_AVX #undef FARMHASH_ASSUME_AVX #define FARMHASH_ASSUME_AVX … #endif #if !defined(FARMHASH_CAN_USE_CXX11) && defined(LANG_CXX11) #define FARMHASH_CAN_USE_CXX11 … #else #undef FARMHASH_CAN_USE_CXX11 #define FARMHASH_CAN_USE_CXX11 … #endif // FARMHASH PORTABILITY LAYER: Runtime error if misconfigured #ifndef FARMHASH_DIE_IF_MISCONFIGURED #define FARMHASH_DIE_IF_MISCONFIGURED … #endif // FARMHASH PORTABILITY LAYER: "static inline" or similar #ifndef STATIC_INLINE #define STATIC_INLINE … #endif // FARMHASH PORTABILITY LAYER: LIKELY and UNLIKELY #if !defined(LIKELY) #if defined(FARMHASH_NO_BUILTIN_EXPECT) || (defined(FARMHASH_OPTIONAL_BUILTIN_EXPECT) && !defined(HAVE_BUILTIN_EXPECT)) || !defined(__GNUC__) #define LIKELY … #else #define LIKELY(x) … #endif #endif #undef UNLIKELY #define UNLIKELY(x) … // FARMHASH PORTABILITY LAYER: endianness and byteswapping functions #ifdef WORDS_BIGENDIAN #undef FARMHASH_BIG_ENDIAN #define FARMHASH_BIG_ENDIAN … #endif #if defined(FARMHASH_LITTLE_ENDIAN) && defined(FARMHASH_BIG_ENDIAN) #error #endif #if !defined(FARMHASH_LITTLE_ENDIAN) && !defined(FARMHASH_BIG_ENDIAN) #define FARMHASH_UNKNOWN_ENDIAN … #endif #if !defined(bswap_32) || !defined(bswap_64) #undef bswap_32 #undef bswap_64 #if defined(HAVE_BUILTIN_BSWAP) || defined(__clang__) || \ (defined(__GNUC__) && ((__GNUC__ == 4 && __GNUC_MINOR__ >= 8) || \ __GNUC__ >= 5)) // Easy case for bswap: no header file needed. #define bswap_32(x) … #define bswap_64(x) … #endif #endif #if defined(FARMHASH_UNKNOWN_ENDIAN) || !defined(bswap_64) #ifdef _MSC_VER #undef bswap_32 #undef bswap_64 #define bswap_32 … #define bswap_64 … #elif defined(__APPLE__) // Mac OS X / Darwin features #include <libkern/OSByteOrder.h> #undef bswap_32 #undef bswap_64 #define bswap_32(x) … #define bswap_64(x) … #elif defined(__sun) || defined(sun) #include <sys/byteorder.h> #undef bswap_32 #undef bswap_64 #define bswap_32 … #define bswap_64 … #elif defined(__FreeBSD__) #include <sys/endian.h> #undef bswap_32 #undef bswap_64 #define bswap_32 … #define bswap_64 … #elif defined(__OpenBSD__) #include <sys/types.h> #undef bswap_32 #undef bswap_64 #define bswap_32 … #define bswap_64 … #elif defined(__NetBSD__) #include <sys/types.h> #include <machine/bswap.h> #if defined(__BSWAP_RENAME) && !defined(__bswap_32) #undef bswap_32 #undef bswap_64 #define bswap_32 … #define bswap_64 … #endif #else #undef bswap_32 #undef bswap_64 #include <byteswap.h> #endif #ifdef WORDS_BIGENDIAN #define FARMHASH_BIG_ENDIAN … #endif #endif #ifdef FARMHASH_BIG_ENDIAN #define uint32_in_expected_order … #define uint64_in_expected_order … #else #define uint32_in_expected_order(x) … #define uint64_in_expected_order(x) … #endif namespace folly { namespace external { namespace farmhash { namespace test { bool returnZeroIfMisconfigured = …; } STATIC_INLINE uint64_t Fetch64(const char *p) { … } STATIC_INLINE uint32_t Fetch32(const char *p) { … } STATIC_INLINE uint32_t Bswap32(uint32_t val) { … } STATIC_INLINE uint64_t Bswap64(uint64_t val) { … } // FARMHASH PORTABILITY LAYER: bitwise rot STATIC_INLINE uint32_t BasicRotate32(uint32_t val, int shift) { … } STATIC_INLINE uint64_t BasicRotate64(uint64_t val, int shift) { … } #if defined(_MSC_VER) && defined(FARMHASH_ROTR) STATIC_INLINE uint32_t Rotate32(uint32_t val, int shift) { return sizeof(unsigned long) == sizeof(val) ? _lrotr(val, shift) : BasicRotate32(val, shift); } STATIC_INLINE uint64_t Rotate64(uint64_t val, int shift) { return sizeof(unsigned long) == sizeof(val) ? _lrotr(val, shift) : BasicRotate64(val, shift); } #else STATIC_INLINE uint32_t Rotate32(uint32_t val, int shift) { … } STATIC_INLINE uint64_t Rotate64(uint64_t val, int shift) { … } #endif } // namespace farmhash } // namespace external } // namespace folly // FARMHASH PORTABILITY LAYER: debug mode or max speed? // One may use -DFARMHASH_DEBUG=1 or -DFARMHASH_DEBUG=0 to force the issue. #if !defined(FARMHASH_DEBUG) && (!defined(NDEBUG) || defined(_DEBUG)) #define FARMHASH_DEBUG … #endif #undef debug_mode #if FARMHASH_DEBUG #define debug_mode … #else #define debug_mode … #endif // PLATFORM-SPECIFIC FUNCTIONS AND MACROS #undef x86_64 #if defined (__x86_64) || defined (__x86_64__) #define x86_64 … #else #define x86_64 … #endif #undef x86 #if defined(__i386__) || defined(__i386) || defined(__X86__) #define x86 … #else #define x86 … #endif #if !defined(is_64bit) #define is_64bit … #endif #undef can_use_ssse3 #if defined(__SSSE3__) || defined(FARMHASH_ASSUME_SSSE3) #include <immintrin.h> #define can_use_ssse3 … // Now we can use _mm_hsub_epi16 and so on. #else #define can_use_ssse3 … #endif #undef can_use_sse41 #if defined(__SSE4_1__) || defined(FARMHASH_ASSUME_SSE41) #include <immintrin.h> #define can_use_sse41 … // Now we can use _mm_insert_epi64 and so on. #else #define can_use_sse41 … #endif #undef can_use_sse42 #if defined(__SSE4_2__) || defined(FARMHASH_ASSUME_SSE42) #include <nmmintrin.h> #define can_use_sse42 … // Now we can use _mm_crc32_u{32,16,8}. And on 64-bit platforms, _mm_crc32_u64. #else #define can_use_sse42 … #endif #undef can_use_aesni #if defined(__AES__) || defined(FARMHASH_ASSUME_AESNI) #include <wmmintrin.h> #define can_use_aesni … // Now we can use _mm_aesimc_si128 and so on. #else #define can_use_aesni … #endif #undef can_use_avx #if defined(__AVX__) || defined(FARMHASH_ASSUME_AVX) #include <immintrin.h> #define can_use_avx … #else #define can_use_avx … #endif #if can_use_sse42 || (can_use_sse41 && x86_64) STATIC_INLINE __m128i Fetch128(const char* s) { return _mm_loadu_si128(reinterpret_cast<const __m128i*>(s)); } #endif // Building blocks for hash functions // std::swap() was in <algorithm> but is in <utility> from C++11 on. #if !FARMHASH_CAN_USE_CXX11 #include <algorithm> #endif #undef PERMUTE3 #define PERMUTE3(a, b, c) … namespace folly { namespace external { namespace farmhash { // Some primes between 2^63 and 2^64 for various uses. static const uint64_t k0 = …; static const uint64_t k1 = …; static const uint64_t k2 = …; // Magic numbers for 32-bit hashing. Copied from Murmur3. static const uint32_t c1 = …; static const uint32_t c2 = …; // A 32-bit to 32-bit integer hash copied from Murmur3. STATIC_INLINE uint32_t fmix(uint32_t h) { … } STATIC_INLINE uint32_t Mur(uint32_t a, uint32_t h) { … } template <typename T> STATIC_INLINE T DebugTweak(T x) { … } template <> uint128_t DebugTweak(uint128_t x) { … } usingnamespacestd; namespace farmhashna { #undef Fetch #define Fetch … #undef Rotate #define Rotate … #undef Bswap #define Bswap … STATIC_INLINE uint64_t ShiftMix(uint64_t val) { … } STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v) { … } STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { … } STATIC_INLINE uint64_t HashLen0to16(const char *s, size_t len) { … } // This probably works well for 16-byte strings as well, but it may be overkill // in that case. STATIC_INLINE uint64_t HashLen17to32(const char *s, size_t len) { … } // Return a 16-byte hash for 48 bytes. Quick and dirty. // Callers do best to use "random-looking" values for a and b. STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds( uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) { … } // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds( const char* s, uint64_t a, uint64_t b) { … } // Return an 8-byte hash for 33 to 64 bytes. STATIC_INLINE uint64_t HashLen33to64(const char *s, size_t len) { … } uint64_t Hash64(const char *s, size_t len) { … } uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1); uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { … } uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) { … } } // namespace farmhashna namespace farmhashuo { #undef Fetch #define Fetch … #undef Rotate #define Rotate … STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r) { … } uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) { … } uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { … } uint64_t Hash64(const char *s, size_t len) { … } } // namespace farmhashuo namespace farmhashxo { #undef Fetch #define Fetch … #undef Rotate #define Rotate … STATIC_INLINE uint64_t H32(const char *s, size_t len, uint64_t mul, uint64_t seed0 = 0, uint64_t seed1 = 0) { … } // Return an 8-byte hash for 33 to 64 bytes. STATIC_INLINE uint64_t HashLen33to64(const char *s, size_t len) { … } // Return an 8-byte hash for 65 to 96 bytes. STATIC_INLINE uint64_t HashLen65to96(const char *s, size_t len) { … } uint64_t Hash64(const char *s, size_t len) { … } uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) { … } uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { … } } // namespace farmhashxo namespace farmhashte { #if !can_use_sse41 || !x86_64 uint64_t Hash64(const char *s, size_t len) { … } uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { … } uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) { … } #else #undef Fetch #define Fetch … #undef Rotate #define Rotate … #undef Bswap #define Bswap … // Helpers for data-parallel operations (1x 128 bits or 2x 64 or 4x 32). STATIC_INLINE __m128i Add(__m128i x, __m128i y) { return _mm_add_epi64(x, y); } STATIC_INLINE __m128i Xor(__m128i x, __m128i y) { return _mm_xor_si128(x, y); } STATIC_INLINE __m128i Mul(__m128i x, __m128i y) { return _mm_mullo_epi32(x, y); } STATIC_INLINE __m128i Shuf(__m128i x, __m128i y) { return _mm_shuffle_epi8(y, x); } // Requires n >= 256. Requires SSE4.1. Should be slightly faster if the // compiler uses AVX instructions (e.g., use the -mavx flag with GCC). STATIC_INLINE uint64_t Hash64Long(const char* s, size_t n, uint64_t seed0, uint64_t seed1) { const __m128i kShuf = _mm_set_epi8(4, 11, 10, 5, 8, 15, 6, 9, 12, 2, 14, 13, 0, 7, 3, 1); const __m128i kMult = _mm_set_epi8(0xbd, 0xd6, 0x33, 0x39, 0x45, 0x54, 0xfa, 0x03, 0x34, 0x3e, 0x33, 0xed, 0xcc, 0x9e, 0x2d, 0x51); uint64_t seed2 = (seed0 + 113) * (seed1 + 9); uint64_t seed3 = (Rotate(seed0, 23) + 27) * (Rotate(seed1, 30) + 111); __m128i d0 = _mm_cvtsi64_si128(seed0); __m128i d1 = _mm_cvtsi64_si128(seed1); __m128i d2 = Shuf(kShuf, d0); __m128i d3 = Shuf(kShuf, d1); __m128i d4 = Xor(d0, d1); __m128i d5 = Xor(d1, d2); __m128i d6 = Xor(d2, d4); __m128i d7 = _mm_set1_epi32(seed2 >> 32); __m128i d8 = Mul(kMult, d2); __m128i d9 = _mm_set1_epi32(seed3 >> 32); __m128i d10 = _mm_set1_epi32(seed3); __m128i d11 = Add(d2, _mm_set1_epi32(seed2)); const char* end = s + (n & ~static_cast<size_t>(255)); do { __m128i z; z = Fetch128(s); d0 = Add(d0, z); d1 = Shuf(kShuf, d1); d2 = Xor(d2, d0); d4 = Xor(d4, z); d4 = Xor(d4, d1); std::swap(d0, d6); z = Fetch128(s + 16); d5 = Add(d5, z); d6 = Shuf(kShuf, d6); d8 = Shuf(kShuf, d8); d7 = Xor(d7, d5); d0 = Xor(d0, z); d0 = Xor(d0, d6); std::swap(d5, d11); z = Fetch128(s + 32); d1 = Add(d1, z); d2 = Shuf(kShuf, d2); d4 = Shuf(kShuf, d4); d5 = Xor(d5, z); d5 = Xor(d5, d2); std::swap(d10, d4); z = Fetch128(s + 48); d6 = Add(d6, z); d7 = Shuf(kShuf, d7); d0 = Shuf(kShuf, d0); d8 = Xor(d8, d6); d1 = Xor(d1, z); d1 = Add(d1, d7); z = Fetch128(s + 64); d2 = Add(d2, z); d5 = Shuf(kShuf, d5); d4 = Add(d4, d2); d6 = Xor(d6, z); d6 = Xor(d6, d11); std::swap(d8, d2); z = Fetch128(s + 80); d7 = Xor(d7, z); d8 = Shuf(kShuf, d8); d1 = Shuf(kShuf, d1); d0 = Add(d0, d7); d2 = Add(d2, z); d2 = Add(d2, d8); std::swap(d1, d7); z = Fetch128(s + 96); d4 = Shuf(kShuf, d4); d6 = Shuf(kShuf, d6); d8 = Mul(kMult, d8); d5 = Xor(d5, d11); d7 = Xor(d7, z); d7 = Add(d7, d4); std::swap(d6, d0); z = Fetch128(s + 112); d8 = Add(d8, z); d0 = Shuf(kShuf, d0); d2 = Shuf(kShuf, d2); d1 = Xor(d1, d8); d10 = Xor(d10, z); d10 = Xor(d10, d0); std::swap(d11, d5); z = Fetch128(s + 128); d4 = Add(d4, z); d5 = Shuf(kShuf, d5); d7 = Shuf(kShuf, d7); d6 = Add(d6, d4); d8 = Xor(d8, z); d8 = Xor(d8, d5); std::swap(d4, d10); z = Fetch128(s + 144); d0 = Add(d0, z); d1 = Shuf(kShuf, d1); d2 = Add(d2, d0); d4 = Xor(d4, z); d4 = Xor(d4, d1); z = Fetch128(s + 160); d5 = Add(d5, z); d6 = Shuf(kShuf, d6); d8 = Shuf(kShuf, d8); d7 = Xor(d7, d5); d0 = Xor(d0, z); d0 = Xor(d0, d6); std::swap(d2, d8); z = Fetch128(s + 176); d1 = Add(d1, z); d2 = Shuf(kShuf, d2); d4 = Shuf(kShuf, d4); d5 = Mul(kMult, d5); d5 = Xor(d5, z); d5 = Xor(d5, d2); std::swap(d7, d1); z = Fetch128(s + 192); d6 = Add(d6, z); d7 = Shuf(kShuf, d7); d0 = Shuf(kShuf, d0); d8 = Add(d8, d6); d1 = Xor(d1, z); d1 = Xor(d1, d7); std::swap(d0, d6); z = Fetch128(s + 208); d2 = Add(d2, z); d5 = Shuf(kShuf, d5); d4 = Xor(d4, d2); d6 = Xor(d6, z); d6 = Xor(d6, d9); std::swap(d5, d11); z = Fetch128(s + 224); d7 = Add(d7, z); d8 = Shuf(kShuf, d8); d1 = Shuf(kShuf, d1); d0 = Xor(d0, d7); d2 = Xor(d2, z); d2 = Xor(d2, d8); std::swap(d10, d4); z = Fetch128(s + 240); d3 = Add(d3, z); d4 = Shuf(kShuf, d4); d6 = Shuf(kShuf, d6); d7 = Mul(kMult, d7); d5 = Add(d5, d3); d7 = Xor(d7, z); d7 = Xor(d7, d4); std::swap(d3, d9); s += 256; } while (s != end); d6 = Add(Mul(kMult, d6), _mm_cvtsi64_si128(n)); if (n % 256 != 0) { d7 = Add(_mm_shuffle_epi32(d8, (0 << 6) + (3 << 4) + (2 << 2) + (1 << 0)), d7); d8 = Add(Mul(kMult, d8), _mm_cvtsi64_si128(farmhashxo::Hash64(s, n % 256))); } __m128i t[8]; d0 = Mul(kMult, Shuf(kShuf, Mul(kMult, d0))); d3 = Mul(kMult, Shuf(kShuf, Mul(kMult, d3))); d9 = Mul(kMult, Shuf(kShuf, Mul(kMult, d9))); d1 = Mul(kMult, Shuf(kShuf, Mul(kMult, d1))); d0 = Add(d11, d0); d3 = Xor(d7, d3); d9 = Add(d8, d9); d1 = Add(d10, d1); d4 = Add(d3, d4); d5 = Add(d9, d5); d6 = Xor(d1, d6); d2 = Add(d0, d2); t[0] = d0; t[1] = d3; t[2] = d9; t[3] = d1; t[4] = d4; t[5] = d5; t[6] = d6; t[7] = d2; return farmhashxo::Hash64(reinterpret_cast<const char*>(t), sizeof(t)); } uint64_t Hash64(const char *s, size_t len) { // Empirically, farmhashxo seems faster until length 512. return len >= 512 ? Hash64Long(s, len, k2, k1) : farmhashxo::Hash64(s, len); } uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { return len >= 512 ? Hash64Long(s, len, k1, seed) : farmhashxo::Hash64WithSeed(s, len, seed); } uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) { return len >= 512 ? Hash64Long(s, len, seed0, seed1) : farmhashxo::Hash64WithSeeds(s, len, seed0, seed1); } #endif } // namespace farmhashte namespace farmhashnt { #if !can_use_sse41 || !x86_64 uint32_t Hash32(const char *s, size_t len) { … } uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { … } #else uint32_t Hash32(const char *s, size_t len) { return static_cast<uint32_t>(farmhashte::Hash64(s, len)); } uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { return static_cast<uint32_t>(farmhashte::Hash64WithSeed(s, len, seed)); } #endif } // namespace farmhashnt namespace farmhashmk { #undef Fetch #define Fetch … #undef Rotate #define Rotate … #undef Bswap #define Bswap … STATIC_INLINE uint32_t Hash32Len13to24(const char *s, size_t len, uint32_t seed = 0) { … } STATIC_INLINE uint32_t Hash32Len0to4(const char *s, size_t len, uint32_t seed = 0) { … } STATIC_INLINE uint32_t Hash32Len5to12(const char *s, size_t len, uint32_t seed = 0) { … } uint32_t Hash32(const char *s, size_t len) { … } uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { … } } // namespace farmhashmk namespace farmhashsu { #if !can_use_sse42 || !can_use_aesni uint32_t Hash32(const char *s, size_t len) { … } uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { … } #else #undef Fetch #define Fetch … #undef Rotate #define Rotate … #undef Bswap #define Bswap … // Helpers for data-parallel operations (4x 32-bits). STATIC_INLINE __m128i Add(__m128i x, __m128i y) { return _mm_add_epi32(x, y); } STATIC_INLINE __m128i Xor(__m128i x, __m128i y) { return _mm_xor_si128(x, y); } STATIC_INLINE __m128i Or(__m128i x, __m128i y) { return _mm_or_si128(x, y); } STATIC_INLINE __m128i Mul(__m128i x, __m128i y) { return _mm_mullo_epi32(x, y); } STATIC_INLINE __m128i Mul5(__m128i x) { return Add(x, _mm_slli_epi32(x, 2)); } STATIC_INLINE __m128i RotateLeft(__m128i x, int c) { return Or(_mm_slli_epi32(x, c), _mm_srli_epi32(x, 32 - c)); } STATIC_INLINE __m128i Rol17(__m128i x) { return RotateLeft(x, 17); } STATIC_INLINE __m128i Rol19(__m128i x) { return RotateLeft(x, 19); } STATIC_INLINE __m128i Shuffle0321(__m128i x) { return _mm_shuffle_epi32(x, (0 << 6) + (3 << 4) + (2 << 2) + (1 << 0)); } uint32_t Hash32(const char *s, size_t len) { const uint32_t seed = 81; if (len <= 24) { return len <= 12 ? (len <= 4 ? farmhashmk::Hash32Len0to4(s, len) : farmhashmk::Hash32Len5to12(s, len)) : farmhashmk::Hash32Len13to24(s, len); } if (len < 40) { uint32_t a = len, b = seed * c2, c = a + b; a += Fetch(s + len - 4); b += Fetch(s + len - 20); c += Fetch(s + len - 16); uint32_t d = a; a = folly::external::farmhash::Rotate32(a, 21); a = Mur(a, Mur(b, _mm_crc32_u32(c, d))); a += Fetch(s + len - 12); b += Fetch(s + len - 8); d += a; a += d; b = Mur(b, d) * c2; a = _mm_crc32_u32(a, b + c); return farmhashmk::Hash32Len13to24(s, (len + 1) / 2, a) + b; } #undef Mulc1 #define Mulc1 … #undef Mulc2 #define Mulc2 … #undef Murk #define Murk … const __m128i cc1 = _mm_set1_epi32(c1); const __m128i cc2 = _mm_set1_epi32(c2); __m128i h = _mm_set1_epi32(seed); __m128i g = _mm_set1_epi32(c1 * seed); __m128i f = g; __m128i k = _mm_set1_epi32(0xe6546b64); __m128i q; if (len < 80) { __m128i a = Fetch128(s); __m128i b = Fetch128(s + 16); __m128i c = Fetch128(s + (len - 15) / 2); __m128i d = Fetch128(s + len - 32); __m128i e = Fetch128(s + len - 16); h = Add(h, a); g = Add(g, b); q = g; g = Shuffle0321(g); f = Add(f, c); __m128i be = Add(b, Mulc1(e)); h = Add(h, f); f = Add(f, h); h = Add(Murk(d, h), e); k = Xor(k, _mm_shuffle_epi8(g, f)); g = Add(Xor(c, g), a); f = Add(Xor(be, f), d); k = Add(k, be); k = Add(k, _mm_shuffle_epi8(f, h)); f = Add(f, g); g = Add(g, f); g = Add(_mm_set1_epi32(len), Mulc1(g)); } else { // len >= 80 // The following is loosely modelled after farmhashmk::Hash32. size_t iters = (len - 1) / 80; len -= iters * 80; #undef Chunk #define Chunk … q = g; while (iters-- != 0) { Chunk(); s += 80; } if (len != 0) { h = Add(h, _mm_set1_epi32(len)); s = s + len - 80; Chunk(); } } g = Shuffle0321(g); k = Xor(k, g); k = Xor(k, q); h = Xor(h, q); f = Mulc1(f); k = Mulc2(k); g = Mulc1(g); h = Mulc2(h); k = Add(k, _mm_shuffle_epi8(g, f)); h = Add(h, f); f = Add(f, h); g = Add(g, k); k = Add(k, g); k = Xor(k, _mm_shuffle_epi8(f, h)); __m128i buf[4]; buf[0] = f; buf[1] = g; buf[2] = k; buf[3] = h; s = reinterpret_cast<char*>(buf); uint32_t x = Fetch(s); uint32_t y = Fetch(s+4); uint32_t z = Fetch(s+8); x = _mm_crc32_u32(x, Fetch(s+12)); y = _mm_crc32_u32(y, Fetch(s+16)); z = _mm_crc32_u32(z * c1, Fetch(s+20)); x = _mm_crc32_u32(x, Fetch(s+24)); y = _mm_crc32_u32(y * c1, Fetch(s+28)); uint32_t o = y; z = _mm_crc32_u32(z, Fetch(s+32)); x = _mm_crc32_u32(x * c1, Fetch(s+36)); y = _mm_crc32_u32(y, Fetch(s+40)); z = _mm_crc32_u32(z * c1, Fetch(s+44)); x = _mm_crc32_u32(x, Fetch(s+48)); y = _mm_crc32_u32(y * c1, Fetch(s+52)); z = _mm_crc32_u32(z, Fetch(s+56)); x = _mm_crc32_u32(x, Fetch(s+60)); return (o - x + y - z) * c1; } #undef Chunk #undef Murk #undef Mulc2 #undef Mulc1 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { if (len <= 24) { if (len >= 13) return farmhashmk::Hash32Len13to24(s, len, seed * c1); else if (len >= 5) return farmhashmk::Hash32Len5to12(s, len, seed); else return farmhashmk::Hash32Len0to4(s, len, seed); } uint32_t h = farmhashmk::Hash32Len13to24(s, 24, seed ^ len); return _mm_crc32_u32(Hash32(s + 24, len - 24) + seed, h); } #endif } // namespace farmhashsu namespace farmhashsa { #if !can_use_sse42 uint32_t Hash32(const char *s, size_t len) { … } uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { … } #else #undef Fetch #define Fetch … #undef Rotate #define Rotate … #undef Bswap #define Bswap … // Helpers for data-parallel operations (4x 32-bits). STATIC_INLINE __m128i Add(__m128i x, __m128i y) { return _mm_add_epi32(x, y); } STATIC_INLINE __m128i Xor(__m128i x, __m128i y) { return _mm_xor_si128(x, y); } STATIC_INLINE __m128i Or(__m128i x, __m128i y) { return _mm_or_si128(x, y); } STATIC_INLINE __m128i Mul(__m128i x, __m128i y) { return _mm_mullo_epi32(x, y); } STATIC_INLINE __m128i Mul5(__m128i x) { return Add(x, _mm_slli_epi32(x, 2)); } STATIC_INLINE __m128i Rotate(__m128i x, int c) { return Or(_mm_slli_epi32(x, c), _mm_srli_epi32(x, 32 - c)); } STATIC_INLINE __m128i Rot17(__m128i x) { return Rotate(x, 17); } STATIC_INLINE __m128i Rot19(__m128i x) { return Rotate(x, 19); } STATIC_INLINE __m128i Shuffle0321(__m128i x) { return _mm_shuffle_epi32(x, (0 << 6) + (3 << 4) + (2 << 2) + (1 << 0)); } uint32_t Hash32(const char *s, size_t len) { const uint32_t seed = 81; if (len <= 24) { return len <= 12 ? (len <= 4 ? farmhashmk::Hash32Len0to4(s, len) : farmhashmk::Hash32Len5to12(s, len)) : farmhashmk::Hash32Len13to24(s, len); } if (len < 40) { uint32_t a = len, b = seed * c2, c = a + b; a += Fetch(s + len - 4); b += Fetch(s + len - 20); c += Fetch(s + len - 16); uint32_t d = a; a = folly::external::farmhash::Rotate32(a, 21); a = Mur(a, Mur(b, Mur(c, d))); a += Fetch(s + len - 12); b += Fetch(s + len - 8); d += a; a += d; b = Mur(b, d) * c2; a = _mm_crc32_u32(a, b + c); return farmhashmk::Hash32Len13to24(s, (len + 1) / 2, a) + b; } #undef Mulc1 #define Mulc1 … #undef Mulc2 #define Mulc2 … #undef Murk #define Murk … const __m128i cc1 = _mm_set1_epi32(c1); const __m128i cc2 = _mm_set1_epi32(c2); __m128i h = _mm_set1_epi32(seed); __m128i g = _mm_set1_epi32(c1 * seed); __m128i f = g; __m128i k = _mm_set1_epi32(0xe6546b64); if (len < 80) { __m128i a = Fetch128(s); __m128i b = Fetch128(s + 16); __m128i c = Fetch128(s + (len - 15) / 2); __m128i d = Fetch128(s + len - 32); __m128i e = Fetch128(s + len - 16); h = Add(h, a); g = Add(g, b); g = Shuffle0321(g); f = Add(f, c); __m128i be = Add(b, Mulc1(e)); h = Add(h, f); f = Add(f, h); h = Add(Murk(d, h), e); k = Xor(k, _mm_shuffle_epi8(g, f)); g = Add(Xor(c, g), a); f = Add(Xor(be, f), d); k = Add(k, be); k = Add(k, _mm_shuffle_epi8(f, h)); f = Add(f, g); g = Add(g, f); g = Add(_mm_set1_epi32(len), Mulc1(g)); } else { // len >= 80 // The following is loosely modelled after farmhashmk::Hash32. size_t iters = (len - 1) / 80; len -= iters * 80; #undef Chunk #define Chunk … while (iters-- != 0) { Chunk(); s += 80; } if (len != 0) { h = Add(h, _mm_set1_epi32(len)); s = s + len - 80; Chunk(); } } g = Shuffle0321(g); k = Xor(k, g); f = Mulc1(f); k = Mulc2(k); g = Mulc1(g); h = Mulc2(h); k = Add(k, _mm_shuffle_epi8(g, f)); h = Add(h, f); f = Add(f, h); g = Add(g, k); k = Add(k, g); k = Xor(k, _mm_shuffle_epi8(f, h)); __m128i buf[4]; buf[0] = f; buf[1] = g; buf[2] = k; buf[3] = h; s = reinterpret_cast<char*>(buf); uint32_t x = Fetch(s); uint32_t y = Fetch(s+4); uint32_t z = Fetch(s+8); x = _mm_crc32_u32(x, Fetch(s+12)); y = _mm_crc32_u32(y, Fetch(s+16)); z = _mm_crc32_u32(z * c1, Fetch(s+20)); x = _mm_crc32_u32(x, Fetch(s+24)); y = _mm_crc32_u32(y * c1, Fetch(s+28)); uint32_t o = y; z = _mm_crc32_u32(z, Fetch(s+32)); x = _mm_crc32_u32(x * c1, Fetch(s+36)); y = _mm_crc32_u32(y, Fetch(s+40)); z = _mm_crc32_u32(z * c1, Fetch(s+44)); x = _mm_crc32_u32(x, Fetch(s+48)); y = _mm_crc32_u32(y * c1, Fetch(s+52)); z = _mm_crc32_u32(z, Fetch(s+56)); x = _mm_crc32_u32(x, Fetch(s+60)); return (o - x + y - z) * c1; } #undef Chunk #undef Murk #undef Mulc2 #undef Mulc1 uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { if (len <= 24) { if (len >= 13) return farmhashmk::Hash32Len13to24(s, len, seed * c1); else if (len >= 5) return farmhashmk::Hash32Len5to12(s, len, seed); else return farmhashmk::Hash32Len0to4(s, len, seed); } uint32_t h = farmhashmk::Hash32Len13to24(s, 24, seed ^ len); return _mm_crc32_u32(Hash32(s + 24, len - 24) + seed, h); } #endif } // namespace farmhashsa namespace farmhashcc { // This file provides a 32-bit hash equivalent to CityHash32 (v1.1.1) // and a 128-bit hash equivalent to CityHash128 (v1.1.1). It also provides // a seeded 32-bit hash function similar to CityHash32. #undef Fetch #define Fetch … #undef Rotate #define Rotate … #undef Bswap #define Bswap … STATIC_INLINE uint32_t Hash32Len13to24(const char *s, size_t len) { … } STATIC_INLINE uint32_t Hash32Len0to4(const char *s, size_t len) { … } STATIC_INLINE uint32_t Hash32Len5to12(const char *s, size_t len) { … } uint32_t Hash32(const char *s, size_t len) { … } uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { … } #undef Fetch #define Fetch … #undef Rotate #define Rotate … #undef Bswap #define Bswap … STATIC_INLINE uint64_t ShiftMix(uint64_t val) { … } STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v) { … } STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { … } STATIC_INLINE uint64_t HashLen0to16(const char *s, size_t len) { … } // Return a 16-byte hash for 48 bytes. Quick and dirty. // Callers do best to use "random-looking" values for a and b. STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds( uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) { … } // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds( const char* s, uint64_t a, uint64_t b) { … } // A subroutine for CityHash128(). Returns a decent 128-bit hash for strings // of any length representable in signed long. Based on City and Murmur. STATIC_INLINE uint128_t CityMurmur(const char *s, size_t len, uint128_t seed) { … } uint128_t CityHash128WithSeed(const char *s, size_t len, uint128_t seed) { … } STATIC_INLINE uint128_t CityHash128(const char *s, size_t len) { … } uint128_t Fingerprint128(const char* s, size_t len) { … } } // namespace farmhashcc // BASIC STRING HASHING // Hash function for a byte array. See also Hash(), below. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. uint32_t Hash32(const char* s, size_t len) { … } // Hash function for a byte array. For convenience, a 32-bit seed is also // hashed into the result. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. uint32_t Hash32WithSeed(const char* s, size_t len, uint32_t seed) { … } // Hash function for a byte array. For convenience, a 64-bit seed is also // hashed into the result. See also Hash(), below. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. uint64_t Hash64(const char* s, size_t len) { … } // Hash function for a byte array. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. size_t Hash(const char* s, size_t len) { … } // Hash function for a byte array. For convenience, a 64-bit seed is also // hashed into the result. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. uint64_t Hash64WithSeed(const char* s, size_t len, uint64_t seed) { … } // Hash function for a byte array. For convenience, two seeds are also // hashed into the result. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. uint64_t Hash64WithSeeds(const char* s, size_t len, uint64_t seed0, uint64_t seed1) { … } // Hash function for a byte array. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. uint128_t Hash128(const char* s, size_t len) { … } // Hash function for a byte array. For convenience, a 128-bit seed is also // hashed into the result. // May change from time to time, may differ on different platforms, may differ // depending on NDEBUG. uint128_t Hash128WithSeed(const char* s, size_t len, uint128_t seed) { … } // BASIC NON-STRING HASHING // FINGERPRINTING (i.e., good, portable, forever-fixed hash functions) // Fingerprint function for a byte array. Most useful in 32-bit binaries. uint32_t Fingerprint32(const char* s, size_t len) { … } // Fingerprint function for a byte array. uint64_t Fingerprint64(const char* s, size_t len) { … } // Fingerprint function for a byte array. uint128_t Fingerprint128(const char* s, size_t len) { … } // Older and still available but perhaps not as fast as the above: // farmhashns::Hash32{,WithSeed}() } // namespace farmhash } // namespace external } // namespace folly
Codebase Browser
folly