Return-Path: X-Original-To: archive-asf-public-internal@cust-asf2.ponee.io Delivered-To: archive-asf-public-internal@cust-asf2.ponee.io Received: from cust-asf.ponee.io (cust-asf.ponee.io [163.172.22.183]) by cust-asf2.ponee.io (Postfix) with ESMTP id DE559200C0D for ; Tue, 31 Jan 2017 08:05:51 +0100 (CET) Received: by cust-asf.ponee.io (Postfix) id DCDC8160B5F; Tue, 31 Jan 2017 07:05:51 +0000 (UTC) Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by cust-asf.ponee.io (Postfix) with SMTP id 8EDAA160B46 for ; Tue, 31 Jan 2017 08:05:49 +0100 (CET) Received: (qmail 80932 invoked by uid 500); 31 Jan 2017 07:05:48 -0000 Mailing-List: contact commits-help@quickstep.incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@quickstep.incubator.apache.org Delivered-To: mailing list commits@quickstep.incubator.apache.org Received: (qmail 80913 invoked by uid 99); 31 Jan 2017 07:05:48 -0000 Received: from pnap-us-west-generic-nat.apache.org (HELO spamd4-us-west.apache.org) (209.188.14.142) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 31 Jan 2017 07:05:48 +0000 Received: from localhost (localhost [127.0.0.1]) by spamd4-us-west.apache.org (ASF Mail Server at spamd4-us-west.apache.org) with ESMTP id D4DADC05E9 for ; Tue, 31 Jan 2017 07:05:47 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at spamd4-us-west.apache.org X-Spam-Flag: NO X-Spam-Score: -7.019 X-Spam-Level: X-Spam-Status: No, score=-7.019 tagged_above=-999 required=6.31 tests=[KAM_LAZY_DOMAIN_SECURITY=1, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RP_MATCHES_RCVD=-2.999] autolearn=disabled Received: from mx1-lw-eu.apache.org ([10.40.0.8]) by localhost (spamd4-us-west.apache.org [10.40.0.11]) (amavisd-new, port 10024) with ESMTP id mEH4wKkNAONl for ; Tue, 31 Jan 2017 07:05:34 +0000 (UTC) Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx1-lw-eu.apache.org (ASF Mail Server at mx1-lw-eu.apache.org) with SMTP id 240B660D17 for ; Tue, 31 Jan 2017 07:05:07 +0000 (UTC) Received: (qmail 78114 invoked by uid 99); 31 Jan 2017 07:05:06 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 31 Jan 2017 07:05:06 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id D59A9DFD8C; Tue, 31 Jan 2017 07:05:06 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: jianqiao@apache.org To: commits@quickstep.incubator.apache.org Date: Tue, 31 Jan 2017 07:05:50 -0000 Message-Id: In-Reply-To: <6450fa76b8c94f83aa02167209e0ca60@git.apache.org> References: <6450fa76b8c94f83aa02167209e0ca60@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [45/62] [abbrv] [partial] incubator-quickstep git commit: Make the third party directory leaner. archived-at: Tue, 31 Jan 2017 07:05:52 -0000 http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/9661f956/third_party/farmhash/farmhash.cc ---------------------------------------------------------------------- diff --git a/third_party/farmhash/farmhash.cc b/third_party/farmhash/farmhash.cc deleted file mode 100644 index f4d90bd..0000000 --- a/third_party/farmhash/farmhash.cc +++ /dev/null @@ -1,11854 +0,0 @@ -// 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 - -#include "farmhash.h" -// 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 1 -#endif - -#ifdef FARMHASH_ASSUME_SSE41 -#undef FARMHASH_ASSUME_SSE41 -#define FARMHASH_ASSUME_SSE41 1 -#endif - -#ifdef FARMHASH_ASSUME_SSE42 -#undef FARMHASH_ASSUME_SSE42 -#define FARMHASH_ASSUME_SSE42 1 -#endif - -#ifdef FARMHASH_ASSUME_AESNI -#undef FARMHASH_ASSUME_AESNI -#define FARMHASH_ASSUME_AESNI 1 -#endif - -#ifdef FARMHASH_ASSUME_AVX -#undef FARMHASH_ASSUME_AVX -#define FARMHASH_ASSUME_AVX 1 -#endif - -#if !defined(FARMHASH_CAN_USE_CXX11) && defined(LANG_CXX11) -#define FARMHASH_CAN_USE_CXX11 1 -#else -#undef FARMHASH_CAN_USE_CXX11 -#define FARMHASH_CAN_USE_CXX11 0 -#endif - -// FARMHASH PORTABILITY LAYER: Runtime error if misconfigured - -#ifndef FARMHASH_DIE_IF_MISCONFIGURED -#define FARMHASH_DIE_IF_MISCONFIGURED do { *(char*)(len % 17) = 0; } while (0) -#endif - -// FARMHASH PORTABILITY LAYER: "static inline" or similar - -#ifndef STATIC_INLINE -#define STATIC_INLINE 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)) -#define LIKELY(x) (x) -#else -#define LIKELY(x) (__builtin_expect(!!(x), 1)) -#endif -#endif - -#undef UNLIKELY -#define UNLIKELY(x) !LIKELY(!(x)) - -// FARMHASH PORTABILITY LAYER: endianness and byteswapping functions - -#ifdef WORDS_BIGENDIAN -#undef FARMHASH_BIG_ENDIAN -#define FARMHASH_BIG_ENDIAN 1 -#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 1 -#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) __builtin_bswap32(x) -#define bswap_64(x) __builtin_bswap64(x) -#endif - -#endif - -#if defined(FARMHASH_UNKNOWN_ENDIAN) || !defined(bswap_64) - -#ifdef _MSC_VER - -#undef bswap_32 -#undef bswap_64 -#define bswap_32(x) _byteswap_ulong(x) -#define bswap_64(x) _byteswap_uint64(x) - -#elif defined(__APPLE__) - -// Mac OS X / Darwin features -#include -#undef bswap_32 -#undef bswap_64 -#define bswap_32(x) OSSwapInt32(x) -#define bswap_64(x) OSSwapInt64(x) - -#elif defined(__sun) || defined(sun) - -#include -#undef bswap_32 -#undef bswap_64 -#define bswap_32(x) BSWAP_32(x) -#define bswap_64(x) BSWAP_64(x) - -#elif defined(__FreeBSD__) - -#include -#undef bswap_32 -#undef bswap_64 -#define bswap_32(x) bswap32(x) -#define bswap_64(x) bswap64(x) - -#elif defined(__OpenBSD__) - -#include -#undef bswap_32 -#undef bswap_64 -#define bswap_32(x) swap32(x) -#define bswap_64(x) swap64(x) - -#elif defined(__NetBSD__) - -#include -#include -#if defined(__BSWAP_RENAME) && !defined(__bswap_32) -#undef bswap_32 -#undef bswap_64 -#define bswap_32(x) bswap32(x) -#define bswap_64(x) bswap64(x) -#endif - -#else - -#undef bswap_32 -#undef bswap_64 -#include - -#endif - -#ifdef WORDS_BIGENDIAN -#define FARMHASH_BIG_ENDIAN 1 -#endif - -#endif - -#ifdef FARMHASH_BIG_ENDIAN -#define uint32_in_expected_order(x) (bswap_32(x)) -#define uint64_in_expected_order(x) (bswap_64(x)) -#else -#define uint32_in_expected_order(x) (x) -#define uint64_in_expected_order(x) (x) -#endif - -namespace NAMESPACE_FOR_HASH_FUNCTIONS { - -STATIC_INLINE uint64_t Fetch64(const char *p) { - uint64_t result; - memcpy(&result, p, sizeof(result)); - return uint64_in_expected_order(result); -} - -STATIC_INLINE uint32_t Fetch32(const char *p) { - uint32_t result; - memcpy(&result, p, sizeof(result)); - return uint32_in_expected_order(result); -} - -STATIC_INLINE uint32_t Bswap32(uint32_t val) { return bswap_32(val); } -STATIC_INLINE uint64_t Bswap64(uint64_t val) { return bswap_64(val); } - -// FARMHASH PORTABILITY LAYER: bitwise rot - -STATIC_INLINE uint32_t BasicRotate32(uint32_t val, int shift) { - // Avoid shifting by 32: doing so yields an undefined result. - return shift == 0 ? val : ((val >> shift) | (val << (32 - shift))); -} - -STATIC_INLINE uint64_t BasicRotate64(uint64_t val, int shift) { - // Avoid shifting by 64: doing so yields an undefined result. - return shift == 0 ? val : ((val >> shift) | (val << (64 - 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) { - return BasicRotate32(val, shift); -} -STATIC_INLINE uint64_t Rotate64(uint64_t val, int shift) { - return BasicRotate64(val, shift); -} - -#endif - -} // namespace NAMESPACE_FOR_HASH_FUNCTIONS - -// 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 1 -#endif - -#undef debug_mode -#if FARMHASH_DEBUG -#define debug_mode 1 -#else -#define debug_mode 0 -#endif - -// PLATFORM-SPECIFIC FUNCTIONS AND MACROS - -#undef x86_64 -#if defined (__x86_64) || defined (__x86_64__) || defined(_M_X64) -#define x86_64 1 -#else -#define x86_64 0 -#endif - -#undef x86 -#if defined(__i386__) || defined(__i386) || defined(__X86__) || defined(_M_IX86) -#define x86 1 -#else -#define x86 x86_64 -#endif - -#if !defined(is_64bit) -#define is_64bit (x86_64 || (sizeof(void*) == 8)) -#endif - -#undef can_use_ssse3 -#if defined(__SSSE3__) || defined(FARMHASH_ASSUME_SSSE3) - -#include -#define can_use_ssse3 1 -// Now we can use _mm_hsub_epi16 and so on. - -#else -#define can_use_ssse3 0 -#endif - -#undef can_use_sse41 -#if defined(__SSE4_1__) || defined(FARMHASH_ASSUME_SSE41) - -#include -#define can_use_sse41 1 -// Now we can use _mm_insert_epi64 and so on. - -#else -#define can_use_sse41 0 -#endif - -#undef can_use_sse42 -#if defined(__SSE4_2__) || defined(FARMHASH_ASSUME_SSE42) - -#include -#define can_use_sse42 1 -// Now we can use _mm_crc32_u{32,16,8}. And on 64-bit platforms, _mm_crc32_u64. - -#else -#define can_use_sse42 0 -#endif - -#undef can_use_aesni -#if defined(__AES__) || defined(FARMHASH_ASSUME_AESNI) - -#include -#define can_use_aesni 1 -// Now we can use _mm_aesimc_si128 and so on. - -#else -#define can_use_aesni 0 -#endif - -#undef can_use_avx -#if defined(__AVX__) || defined(FARMHASH_ASSUME_AVX) - -#include -#define can_use_avx 1 - -#else -#define can_use_avx 0 -#endif - -#if can_use_ssse3 || can_use_sse41 || can_use_sse42 || can_use_aesni || can_use_avx -STATIC_INLINE __m128i Fetch128(const char* s) { - return _mm_loadu_si128(reinterpret_cast(s)); -} -#endif -// Building blocks for hash functions - -// std::swap() was in but is in from C++11 on. -#if !FARMHASH_CAN_USE_CXX11 -#include -#endif - -#undef PERMUTE3 -#define PERMUTE3(a, b, c) do { std::swap(a, b); std::swap(a, c); } while (0) - -namespace NAMESPACE_FOR_HASH_FUNCTIONS { - -// Some primes between 2^63 and 2^64 for various uses. -static const uint64_t k0 = 0xc3a5c85c97cb3127ULL; -static const uint64_t k1 = 0xb492b66fbe98f273ULL; -static const uint64_t k2 = 0x9ae16a3b2f90404fULL; - -// Magic numbers for 32-bit hashing. Copied from Murmur3. -static const uint32_t c1 = 0xcc9e2d51; -static const uint32_t c2 = 0x1b873593; - -// A 32-bit to 32-bit integer hash copied from Murmur3. -STATIC_INLINE uint32_t fmix(uint32_t h) -{ - h ^= h >> 16; - h *= 0x85ebca6b; - h ^= h >> 13; - h *= 0xc2b2ae35; - h ^= h >> 16; - return h; -} - -STATIC_INLINE uint32_t Mur(uint32_t a, uint32_t h) { - // Helper from Murmur3 for combining two 32-bit values. - a *= c1; - a = Rotate32(a, 17); - a *= c2; - h ^= a; - h = Rotate32(h, 19); - return h * 5 + 0xe6546b64; -} - -template STATIC_INLINE T DebugTweak(T x) { - if (debug_mode) { - if (sizeof(x) == 4) { - x = ~Bswap32(x * c1); - } else { - x = ~Bswap64(x * k1); - } - } - return x; -} - -template <> uint128_t DebugTweak(uint128_t x) { - if (debug_mode) { - uint64_t y = DebugTweak(Uint128Low64(x)); - uint64_t z = DebugTweak(Uint128High64(x)); - y += z; - z += y; - x = Uint128(y, z * k1); - } - return x; -} - -} // namespace NAMESPACE_FOR_HASH_FUNCTIONS - -using namespace std; -using namespace NAMESPACE_FOR_HASH_FUNCTIONS; -namespace farmhashna { -#undef Fetch -#define Fetch Fetch64 - -#undef Rotate -#define Rotate Rotate64 - -#undef Bswap -#define Bswap Bswap64 - -STATIC_INLINE uint64_t ShiftMix(uint64_t val) { - return val ^ (val >> 47); -} - -STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v) { - return Hash128to64(Uint128(u, v)); -} - -STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { - // Murmur-inspired hashing. - uint64_t a = (u ^ v) * mul; - a ^= (a >> 47); - uint64_t b = (v ^ a) * mul; - b ^= (b >> 47); - b *= mul; - return b; -} - -STATIC_INLINE uint64_t HashLen0to16(const char *s, size_t len) { - if (len >= 8) { - uint64_t mul = k2 + len * 2; - uint64_t a = Fetch(s) + k2; - uint64_t b = Fetch(s + len - 8); - uint64_t c = Rotate(b, 37) * mul + a; - uint64_t d = (Rotate(a, 25) + b) * mul; - return HashLen16(c, d, mul); - } - if (len >= 4) { - uint64_t mul = k2 + len * 2; - uint64_t a = Fetch32(s); - return HashLen16(len + (a << 3), Fetch32(s + len - 4), mul); - } - if (len > 0) { - uint8_t a = s[0]; - uint8_t b = s[len >> 1]; - uint8_t c = s[len - 1]; - uint32_t y = static_cast(a) + (static_cast(b) << 8); - uint32_t z = len + (static_cast(c) << 2); - return ShiftMix(y * k2 ^ z * k0) * k2; - } - return k2; -} - -// 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) { - uint64_t mul = k2 + len * 2; - uint64_t a = Fetch(s) * k1; - uint64_t b = Fetch(s + 8); - uint64_t c = Fetch(s + len - 8) * mul; - uint64_t d = Fetch(s + len - 16) * k2; - return HashLen16(Rotate(a + b, 43) + Rotate(c, 30) + d, - a + Rotate(b + k2, 18) + c, mul); -} - -// 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 WeakHashLen32WithSeeds( - uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) { - a += w; - b = Rotate(b + a + z, 21); - uint64_t c = a; - a += x; - a += y; - b += Rotate(a, 44); - return make_pair(a + z, b + c); -} - -// Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. -STATIC_INLINE pair WeakHashLen32WithSeeds( - const char* s, uint64_t a, uint64_t b) { - return WeakHashLen32WithSeeds(Fetch(s), - Fetch(s + 8), - Fetch(s + 16), - Fetch(s + 24), - a, - b); -} - -// Return an 8-byte hash for 33 to 64 bytes. -STATIC_INLINE uint64_t HashLen33to64(const char *s, size_t len) { - uint64_t mul = k2 + len * 2; - uint64_t a = Fetch(s) * k2; - uint64_t b = Fetch(s + 8); - uint64_t c = Fetch(s + len - 8) * mul; - uint64_t d = Fetch(s + len - 16) * k2; - uint64_t y = Rotate(a + b, 43) + Rotate(c, 30) + d; - uint64_t z = HashLen16(y, a + Rotate(b + k2, 18) + c, mul); - uint64_t e = Fetch(s + 16) * mul; - uint64_t f = Fetch(s + 24); - uint64_t g = (y + Fetch(s + len - 32)) * mul; - uint64_t h = (z + Fetch(s + len - 24)) * mul; - return HashLen16(Rotate(e + f, 43) + Rotate(g, 30) + h, - e + Rotate(f + a, 18) + g, mul); -} - -uint64_t Hash64(const char *s, size_t len) { - const uint64_t seed = 81; - if (len <= 32) { - if (len <= 16) { - return HashLen0to16(s, len); - } else { - return HashLen17to32(s, len); - } - } else if (len <= 64) { - return HashLen33to64(s, len); - } - - // For strings over 64 bytes we loop. Internal state consists of - // 56 bytes: v, w, x, y, and z. - uint64_t x = seed; - uint64_t y = seed * k1 + 113; - uint64_t z = ShiftMix(y * k2 + 113) * k2; - pair v = make_pair(0, 0); - pair w = make_pair(0, 0); - x = x * k2 + Fetch(s); - - // Set end so that after the loop we have 1 to 64 bytes left to process. - const char* end = s + ((len - 1) / 64) * 64; - const char* last64 = end + ((len - 1) & 63) - 63; - assert(s + len - 64 == last64); - do { - x = Rotate(x + y + v.first + Fetch(s + 8), 37) * k1; - y = Rotate(y + v.second + Fetch(s + 48), 42) * k1; - x ^= w.second; - y += v.first + Fetch(s + 40); - z = Rotate(z + w.first, 33) * k1; - v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); - w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16)); - std::swap(z, x); - s += 64; - } while (s != end); - uint64_t mul = k1 + ((z & 0xff) << 1); - // Make s point to the last 64 bytes of input. - s = last64; - w.first += ((len - 1) & 63); - v.first += w.first; - w.first += v.first; - x = Rotate(x + y + v.first + Fetch(s + 8), 37) * mul; - y = Rotate(y + v.second + Fetch(s + 48), 42) * mul; - x ^= w.second * 9; - y += v.first * 9 + Fetch(s + 40); - z = Rotate(z + w.first, 33) * mul; - v = WeakHashLen32WithSeeds(s, v.second * mul, x + w.first); - w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16)); - std::swap(z, x); - return HashLen16(HashLen16(v.first, w.first, mul) + ShiftMix(y) * k0 + z, - HashLen16(v.second, w.second, mul) + x, - mul); -} - -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) { - return Hash64WithSeeds(s, len, k2, seed); -} - -uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) { - return HashLen16(Hash64(s, len) - seed0, seed1); -} -} // namespace farmhashna -namespace farmhashuo { -#undef Fetch -#define Fetch Fetch64 - -#undef Rotate -#define Rotate Rotate64 - -STATIC_INLINE uint64_t H(uint64_t x, uint64_t y, uint64_t mul, int r) { - uint64_t a = (x ^ y) * mul; - a ^= (a >> 47); - uint64_t b = (y ^ a) * mul; - return Rotate(b, r) * mul; -} - -uint64_t Hash64WithSeeds(const char *s, size_t len, - uint64_t seed0, uint64_t seed1) { - if (len <= 64) { - return farmhashna::Hash64WithSeeds(s, len, seed0, seed1); - } - - // For strings over 64 bytes we loop. Internal state consists of - // 64 bytes: u, v, w, x, y, and z. - uint64_t x = seed0; - uint64_t y = seed1 * k2 + 113; - uint64_t z = farmhashna::ShiftMix(y * k2) * k2; - pair v = make_pair(seed0, seed1); - pair w = make_pair(0, 0); - uint64_t u = x - z; - x *= k2; - uint64_t mul = k2 + (u & 0x82); - - // Set end so that after the loop we have 1 to 64 bytes left to process. - const char* end = s + ((len - 1) / 64) * 64; - const char* last64 = end + ((len - 1) & 63) - 63; - assert(s + len - 64 == last64); - do { - uint64_t a0 = Fetch(s); - uint64_t a1 = Fetch(s + 8); - uint64_t a2 = Fetch(s + 16); - uint64_t a3 = Fetch(s + 24); - uint64_t a4 = Fetch(s + 32); - uint64_t a5 = Fetch(s + 40); - uint64_t a6 = Fetch(s + 48); - uint64_t a7 = Fetch(s + 56); - x += a0 + a1; - y += a2; - z += a3; - v.first += a4; - v.second += a5 + a1; - w.first += a6; - w.second += a7; - - x = Rotate(x, 26); - x *= 9; - y = Rotate(y, 29); - z *= mul; - v.first = Rotate(v.first, 33); - v.second = Rotate(v.second, 30); - w.first ^= x; - w.first *= 9; - z = Rotate(z, 32); - z += w.second; - w.second += z; - z *= 9; - std::swap(u, y); - - z += a0 + a6; - v.first += a2; - v.second += a3; - w.first += a4; - w.second += a5 + a6; - x += a1; - y += a7; - - y += v.first; - v.first += x - y; - v.second += w.first; - w.first += v.second; - w.second += x - y; - x += w.second; - w.second = Rotate(w.second, 34); - std::swap(u, z); - s += 64; - } while (s != end); - // Make s point to the last 64 bytes of input. - s = last64; - u *= 9; - v.second = Rotate(v.second, 28); - v.first = Rotate(v.first, 20); - w.first += ((len - 1) & 63); - u += y; - y += u; - x = Rotate(y - x + v.first + Fetch(s + 8), 37) * mul; - y = Rotate(y ^ v.second ^ Fetch(s + 48), 42) * mul; - x ^= w.second * 9; - y += v.first + Fetch(s + 40); - z = Rotate(z + w.first, 33) * mul; - v = farmhashna::WeakHashLen32WithSeeds(s, v.second * mul, x + w.first); - w = farmhashna::WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16)); - return H(farmhashna::HashLen16(v.first + x, w.first ^ y, mul) + z - u, - H(v.second + y, w.second + z, k2, 30) ^ x, - k2, - 31); -} - -uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { - return len <= 64 ? farmhashna::Hash64WithSeed(s, len, seed) : - Hash64WithSeeds(s, len, 0, seed); -} - -uint64_t Hash64(const char *s, size_t len) { - return len <= 64 ? farmhashna::Hash64(s, len) : - Hash64WithSeeds(s, len, 81, 0); -} -} // namespace farmhashuo -namespace farmhashxo { -#undef Fetch -#define Fetch Fetch64 - -#undef Rotate -#define Rotate Rotate64 - -STATIC_INLINE uint64_t H32(const char *s, size_t len, uint64_t mul, - uint64_t seed0 = 0, uint64_t seed1 = 0) { - uint64_t a = Fetch(s) * k1; - uint64_t b = Fetch(s + 8); - uint64_t c = Fetch(s + len - 8) * mul; - uint64_t d = Fetch(s + len - 16) * k2; - uint64_t u = Rotate(a + b, 43) + Rotate(c, 30) + d + seed0; - uint64_t v = a + Rotate(b + k2, 18) + c + seed1; - a = farmhashna::ShiftMix((u ^ v) * mul); - b = farmhashna::ShiftMix((v ^ a) * mul); - return b; -} - -// Return an 8-byte hash for 33 to 64 bytes. -STATIC_INLINE uint64_t HashLen33to64(const char *s, size_t len) { - uint64_t mul0 = k2 - 30; - uint64_t mul1 = k2 - 30 + 2 * len; - uint64_t h0 = H32(s, 32, mul0); - uint64_t h1 = H32(s + len - 32, 32, mul1); - return ((h1 * mul1) + h0) * mul1; -} - -// Return an 8-byte hash for 65 to 96 bytes. -STATIC_INLINE uint64_t HashLen65to96(const char *s, size_t len) { - uint64_t mul0 = k2 - 114; - uint64_t mul1 = k2 - 114 + 2 * len; - uint64_t h0 = H32(s, 32, mul0); - uint64_t h1 = H32(s + 32, 32, mul1); - uint64_t h2 = H32(s + len - 32, 32, mul1, h0, h1); - return (h2 * 9 + (h0 >> 17) + (h1 >> 21)) * mul1; -} - -uint64_t Hash64(const char *s, size_t len) { - if (len <= 32) { - if (len <= 16) { - return farmhashna::HashLen0to16(s, len); - } else { - return farmhashna::HashLen17to32(s, len); - } - } else if (len <= 64) { - return HashLen33to64(s, len); - } else if (len <= 96) { - return HashLen65to96(s, len); - } else if (len <= 256) { - return farmhashna::Hash64(s, len); - } else { - return farmhashuo::Hash64(s, len); - } -} - -uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) { - return farmhashuo::Hash64WithSeeds(s, len, seed0, seed1); -} - -uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { - return farmhashuo::Hash64WithSeed(s, len, seed); -} -} // namespace farmhashxo -namespace farmhashte { -#if !can_use_sse41 || !x86_64 - -uint64_t Hash64(const char *s, size_t len) { - FARMHASH_DIE_IF_MISCONFIGURED; - return s == NULL ? 0 : len; -} - -uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) { - FARMHASH_DIE_IF_MISCONFIGURED; - return seed + Hash64(s, len); -} - -uint64_t Hash64WithSeeds(const char *s, size_t len, - uint64_t seed0, uint64_t seed1) { - FARMHASH_DIE_IF_MISCONFIGURED; - return seed0 + seed1 + Hash64(s, len); -} - -#else - -#undef Fetch -#define Fetch Fetch64 - -#undef Rotate -#define Rotate Rotate64 - -#undef Bswap -#define Bswap Bswap64 - -// 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(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(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) { - FARMHASH_DIE_IF_MISCONFIGURED; - return s == NULL ? 0 : len; -} - -uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { - FARMHASH_DIE_IF_MISCONFIGURED; - return seed + Hash32(s, len); -} - -#else - -uint32_t Hash32(const char *s, size_t len) { - return static_cast(farmhashte::Hash64(s, len)); -} - -uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { - return static_cast(farmhashte::Hash64WithSeed(s, len, seed)); -} - -#endif -} // namespace farmhashnt -namespace farmhashmk { -#undef Fetch -#define Fetch Fetch32 - -#undef Rotate -#define Rotate Rotate32 - -#undef Bswap -#define Bswap Bswap32 - -STATIC_INLINE uint32_t Hash32Len13to24(const char *s, size_t len, uint32_t seed = 0) { - uint32_t a = Fetch(s - 4 + (len >> 1)); - uint32_t b = Fetch(s + 4); - uint32_t c = Fetch(s + len - 8); - uint32_t d = Fetch(s + (len >> 1)); - uint32_t e = Fetch(s); - uint32_t f = Fetch(s + len - 4); - uint32_t h = d * c1 + len + seed; - a = Rotate(a, 12) + f; - h = Mur(c, h) + a; - a = Rotate(a, 3) + c; - h = Mur(e, h) + a; - a = Rotate(a + f, 12) + d; - h = Mur(b ^ seed, h) + a; - return fmix(h); -} - -STATIC_INLINE uint32_t Hash32Len0to4(const char *s, size_t len, uint32_t seed = 0) { - uint32_t b = seed; - uint32_t c = 9; - for (size_t i = 0; i < len; i++) { - signed char v = s[i]; - b = b * c1 + v; - c ^= b; - } - return fmix(Mur(b, Mur(len, c))); -} - -STATIC_INLINE uint32_t Hash32Len5to12(const char *s, size_t len, uint32_t seed = 0) { - uint32_t a = len, b = len * 5, c = 9, d = b + seed; - a += Fetch(s); - b += Fetch(s + len - 4); - c += Fetch(s + ((len >> 1) & 4)); - return fmix(seed ^ Mur(c, Mur(b, Mur(a, d)))); -} - -uint32_t Hash32(const char *s, size_t len) { - if (len <= 24) { - return len <= 12 ? - (len <= 4 ? Hash32Len0to4(s, len) : Hash32Len5to12(s, len)) : - Hash32Len13to24(s, len); - } - - // len > 24 - uint32_t h = len, g = c1 * len, f = g; - uint32_t a0 = Rotate(Fetch(s + len - 4) * c1, 17) * c2; - uint32_t a1 = Rotate(Fetch(s + len - 8) * c1, 17) * c2; - uint32_t a2 = Rotate(Fetch(s + len - 16) * c1, 17) * c2; - uint32_t a3 = Rotate(Fetch(s + len - 12) * c1, 17) * c2; - uint32_t a4 = Rotate(Fetch(s + len - 20) * c1, 17) * c2; - h ^= a0; - h = Rotate(h, 19); - h = h * 5 + 0xe6546b64; - h ^= a2; - h = Rotate(h, 19); - h = h * 5 + 0xe6546b64; - g ^= a1; - g = Rotate(g, 19); - g = g * 5 + 0xe6546b64; - g ^= a3; - g = Rotate(g, 19); - g = g * 5 + 0xe6546b64; - f += a4; - f = Rotate(f, 19) + 113; - size_t iters = (len - 1) / 20; - do { - uint32_t a = Fetch(s); - uint32_t b = Fetch(s + 4); - uint32_t c = Fetch(s + 8); - uint32_t d = Fetch(s + 12); - uint32_t e = Fetch(s + 16); - h += a; - g += b; - f += c; - h = Mur(d, h) + e; - g = Mur(c, g) + a; - f = Mur(b + e * c1, f) + d; - f += g; - g += f; - s += 20; - } while (--iters != 0); - g = Rotate(g, 11) * c1; - g = Rotate(g, 17) * c1; - f = Rotate(f, 11) * c1; - f = Rotate(f, 17) * c1; - h = Rotate(h + g, 19); - h = h * 5 + 0xe6546b64; - h = Rotate(h, 17) * c1; - h = Rotate(h + f, 19); - h = h * 5 + 0xe6546b64; - h = Rotate(h, 17) * c1; - return h; -} - -uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { - if (len <= 24) { - if (len >= 13) return Hash32Len13to24(s, len, seed * c1); - else if (len >= 5) return Hash32Len5to12(s, len, seed); - else return Hash32Len0to4(s, len, seed); - } - uint32_t h = Hash32Len13to24(s, 24, seed ^ len); - return Mur(Hash32(s + 24, len - 24) + seed, h); -} -} // namespace farmhashmk -namespace farmhashsu { -#if !can_use_sse42 || !can_use_aesni - -uint32_t Hash32(const char *s, size_t len) { - FARMHASH_DIE_IF_MISCONFIGURED; - return s == NULL ? 0 : len; -} - -uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { - FARMHASH_DIE_IF_MISCONFIGURED; - return seed + Hash32(s, len); -} - -#else - -#undef Fetch -#define Fetch Fetch32 - -#undef Rotate -#define Rotate Rotate32 - -#undef Bswap -#define Bswap Bswap32 - -// 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 = NAMESPACE_FOR_HASH_FUNCTIONS::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(x) Mul((x), cc1) - -#undef Mulc2 -#define Mulc2(x) Mul((x), cc2) - -#undef Murk -#define Murk(a, h) \ - Add(k, \ - Mul5( \ - Rol19( \ - Xor( \ - Mulc2( \ - Rol17( \ - Mulc1(a))), \ - (h))))) - - 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() do { \ - __m128i a = Fetch128(s); \ - __m128i b = Fetch128(s + 16); \ - __m128i c = Fetch128(s + 32); \ - __m128i d = Fetch128(s + 48); \ - __m128i e = Fetch128(s + 64); \ - 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(h, d); \ - q = Add(q, e); \ - h = Rol17(h); \ - h = Mulc1(h); \ - k = Xor(k, _mm_shuffle_epi8(g, f)); \ - g = Add(Xor(c, g), a); \ - f = Add(Xor(be, f), d); \ - std::swap(f, q); \ - q = _mm_aesimc_si128(q); \ - k = Add(k, be); \ - k = Add(k, _mm_shuffle_epi8(f, h)); \ - f = Add(f, g); \ - g = Add(g, f); \ - f = Mulc1(f); \ -} while (0) - - 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(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) { - FARMHASH_DIE_IF_MISCONFIGURED; - return s == NULL ? 0 : len; -} - -uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) { - FARMHASH_DIE_IF_MISCONFIGURED; - return seed + Hash32(s, len); -} - -#else - -#undef Fetch -#define Fetch Fetch32 - -#undef Rotate -#define Rotate Rotate32 - -#undef Bswap -#define Bswap Bswap32 - -// 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 = NAMESPACE_FOR_HASH_FUNCTIONS::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(x) Mul((x), cc1) - -#undef Mulc2 -#define Mulc2(x) Mul((x), cc2) - -#undef Murk -#define Murk(a, h) \ - Add(k, \ - Mul5( \ - Rot19( \ - Xor( \ - Mulc2( \ - Rot17( \ - Mulc1(a))), \ - (h))))) - - 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() do { \ - __m128i a = Fetch128(s); \ - __m128i b = Fetch128(s + 16); \ - __m128i c = Fetch128(s + 32); \ - __m128i d = Fetch128(s + 48); \ - __m128i e = Fetch128(s + 64); \ - 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); \ - f = Mulc1(f); \ -} while (0) - - 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(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 Fetch32 - -#undef Rotate -#define Rotate Rotate32 - -#undef Bswap -#define Bswap Bswap32 - -STATIC_INLINE uint32_t Hash32Len13to24(const char *s, size_t len) { - uint32_t a = Fetch(s - 4 + (len >> 1)); - uint32_t b = Fetch(s + 4); - uint32_t c = Fetch(s + len - 8); - uint32_t d = Fetch(s + (len >> 1)); - uint32_t e = Fetch(s); - uint32_t f = Fetch(s + len - 4); - uint32_t h = len; - - return fmix(Mur(f, Mur(e, Mur(d, Mur(c, Mur(b, Mur(a, h))))))); -} - -STATIC_INLINE uint32_t Hash32Len0to4(const char *s, size_t len) { - uint32_t b = 0; - uint32_t c = 9; - for (size_t i = 0; i < len; i++) { - signed char v = s[i]; - b = b * c1 + v; - c ^= b; - } - return fmix(Mur(b, Mur(len, c))); -} - -STATIC_INLINE uint32_t Hash32Len5to12(const char *s, size_t len) { - uint32_t a = len, b = len * 5, c = 9, d = b; - a += Fetch(s); - b += Fetch(s + len - 4); - c += Fetch(s + ((len >> 1) & 4)); - return fmix(Mur(c, Mur(b, Mur(a, d)))); -} - -uint32_t Hash32(const char *s, size_t len) { - if (len <= 24) { - return len <= 12 ? - (len <= 4 ? Hash32Len0to4(s, len) : Hash32Len5to12(s, len)) : - Hash32Len13to24(s, len); - } - - // len > 24 - uint32_t h = len, g = c1 * len, f = g; - uint32_t a0 = Rotate(Fetch(s + len - 4) * c1, 17) * c2; - uint32_t a1 = Rotate(Fetch(s + len - 8) * c1, 17) * c2; - uint32_t a2 = Rotate(Fetch(s + len - 16) * c1, 17) * c2; - uint32_t a3 = Rotate(Fetch(s + len - 12) * c1, 17) * c2; - uint32_t a4 = Rotate(Fetch(s + len - 20) * c1, 17) * c2; - h ^= a0; - h = Rotate(h, 19); - h = h * 5 + 0xe6546b64; - h ^= a2; - h = Rotate(h, 19); - h = h * 5 + 0xe6546b64; - g ^= a1; - g = Rotate(g, 19); - g = g * 5 + 0xe6546b64; - g ^= a3; - g = Rotate(g, 19); - g = g * 5 + 0xe6546b64; - f += a4; - f = Rotate(f, 19); - f = f * 5 + 0xe6546b64; - size_t iters = (len - 1) / 20; - do { - uint32_t a0 = Rotate(Fetch(s) * c1, 17) * c2; - uint32_t a1 = Fetch(s + 4); - uint32_t a2 = Rotate(Fetch(s + 8) * c1, 17) * c2; - uint32_t a3 = Rotate(Fetch(s + 12) * c1, 17) * c2; - uint32_t a4 = Fetch(s + 16); - h ^= a0; - h = Rotate(h, 18); - h = h * 5 + 0xe6546b64; - f += a1; - f = Rotate(f, 19); - f = f * c1; - g += a2; - g = Rotate(g, 18); - g = g * 5 + 0xe6546b64; - h ^= a3 + a1; - h = Rotate(h, 19); - h = h * 5 + 0xe6546b64; - g ^= a4; - g = Bswap(g) * 5; - h += a4 * 5; - h = Bswap(h); - f += a0; - PERMUTE3(f, h, g); - s += 20; - } while (--iters != 0); - g = Rotate(g, 11) * c1; - g = Rotate(g, 17) * c1; - f = Rotate(f, 11) * c1; - f = Rotate(f, 17) * c1; - h = Rotate(h + g, 19); - h = h * 5 + 0xe6546b64; - h = Rotate(h, 17) * c1; - h = Rotate(h + f, 19); - h = h * 5 + 0xe6546b64; - h = Rotate(h, 17) * c1; - return h; -} - -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 Mur(Hash32(s + 24, len - 24) + seed, h); -} - -#undef Fetch -#define Fetch Fetch64 - -#undef Rotate -#define Rotate Rotate64 - -#undef Bswap -#define Bswap Bswap64 - -STATIC_INLINE uint64_t ShiftMix(uint64_t val) { - return val ^ (val >> 47); -} - -STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v) { - return Hash128to64(Uint128(u, v)); -} - -STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) { - // Murmur-inspired hashing. - uint64_t a = (u ^ v) * mul; - a ^= (a >> 47); - uint64_t b = (v ^ a) * mul; - b ^= (b >> 47); - b *= mul; - return b; -} - -STATIC_INLINE uint64_t HashLen0to16(const char *s, size_t len) { - if (len >= 8) { - uint64_t mul = k2 + len * 2; - uint64_t a = Fetch(s) + k2; - uint64_t b = Fetch(s + len - 8); - uint64_t c = Rotate(b, 37) * mul + a; - uint64_t d = (Rotate(a, 25) + b) * mul; - return HashLen16(c, d, mul); - } - if (len >= 4) { - uint64_t mul = k2 + len * 2; - uint64_t a = Fetch32(s); - return HashLen16(len + (a << 3), Fetch32(s + len - 4), mul); - } - if (len > 0) { - uint8_t a = s[0]; - uint8_t b = s[len >> 1]; - uint8_t c = s[len - 1]; - uint32_t y = static_cast(a) + (static_cast(b) << 8); - uint32_t z = len + (static_cast(c) << 2); - return ShiftMix(y * k2 ^ z * k0) * k2; - } - return k2; -} - -// 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 WeakHashLen32WithSeeds( - uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) { - a += w; - b = Rotate(b + a + z, 21); - uint64_t c = a; - a += x; - a += y; - b += Rotate(a, 44); - return make_pair(a + z, b + c); -} - -// Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. -STATIC_INLINE pair WeakHashLen32WithSeeds( - const char* s, uint64_t a, uint64_t b) { - return WeakHashLen32WithSeeds(Fetch(s), - Fetch(s + 8), - Fetch(s + 16), - Fetch(s + 24), - a, - 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) { - uint64_t a = Uint128Low64(seed); - uint64_t b = Uint128High64(seed); - uint64_t c = 0; - uint64_t d = 0; - signed long l = len - 16; - if (l <= 0) { // len <= 16 - a = ShiftMix(a * k1) * k1; - c = b * k1 + HashLen0to16(s, len); - d = ShiftMix(a + (len >= 8 ? Fetch(s) : c)); - } else { // len > 16 - c = HashLen16(Fetch(s + len - 8) + k1, a); - d = HashLen16(b + len, c + Fetch(s + len - 16)); - a += d; - do { - a ^= ShiftMix(Fetch(s) * k1) * k1; - a *= k1; - b ^= a; - c ^= ShiftMix(Fetch(s + 8) * k1) * k1; - c *= k1; - d ^= c; - s += 16; - l -= 16; - } while (l > 0); - } - a = HashLen16(a, c); - b = HashLen16(d, b); - return uint128_t(a ^ b, HashLen16(b, a)); -} - -uint128_t CityHash128WithSeed(const char *s, size_t len, uint128_t seed) { - if (len < 128) { - return CityMurmur(s, len, seed); - } - - // We expect len >= 128 to be the common case. Keep 56 bytes of state: - // v, w, x, y, and z. - pair v, w; - uint64_t x = Uint128Low64(seed); - uint64_t y = Uint128High64(seed); - uint64_t z = len * k1; - v.first = Rotate(y ^ k1, 49) * k1 + Fetch(s); - v.second = Rotate(v.first, 42) * k1 + Fetch(s + 8); - w.first = Rotate(y + z, 35) * k1 + x; - w.second = Rotate(x + Fetch(s + 88), 53) * k1; - - // This is the same inner loop as CityHash64(), manually unrolled. - do { - x = Rotate(x + y + v.first + Fetch(s + 8), 37) * k1; - y = Rotate(y + v.second + Fetch(s + 48), 42) * k1; - x ^= w.second; - y += v.first + Fetch(s + 40); - z = Rotate(z + w.first, 33) * k1; - v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); - w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16)); - std::swap(z, x); - s += 64; - x = Rotate(x + y + v.first + Fetch(s + 8), 37) * k1; - y = Rotate(y + v.second + Fetch(s + 48), 42) * k1; - x ^= w.second; - y += v.first + Fetch(s + 40); - z = Rotate(z + w.first, 33) * k1; - v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first); - w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16)); - std::swap(z, x); - s += 64; - len -= 128; - } while (LIKELY(len >= 128)); - x += Rotate(v.first + z, 49) * k0; - y = y * k0 + Rotate(w.second, 37); - z = z * k0 + Rotate(w.first, 27); - w.first *= 9; - v.first *= k0; - // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s. - for (size_t tail_done = 0; tail_done < len; ) { - tail_done += 32; - y = Rotate(x + y, 42) * k0 + v.second; - w.first += Fetch(s + len - tail_done + 16); - x = x * k0 + w.first; - z += w.second + Fetch(s + len - tail_done); - w.second += v.first; - v = WeakHashLen32WithSeeds(s + len - tail_done, v.first + z, v.second); - v.first *= k0; - } - // At this point our 56 bytes of state should contain more than - // enough information for a strong 128-bit hash. We use two - // different 56-byte-to-8-byte hashes to get a 16-byte final result. - x = HashLen16(x, v.first); - y = HashLen16(y + z, w.first); - return uint128_t(HashLen16(x + v.second, w.second) + y, - HashLen16(x + w.second, y + v.second)); -} - -STATIC_INLINE uint128_t CityHash128(const char *s, size_t len) { - return len >= 16 ? - CityHash128WithSeed(s + 16, len - 16, - uint128_t(Fetch(s), Fetch(s + 8) + k0)) : - CityHash128WithSeed(s, len, uint128_t(k0, k1)); -} - -uint128_t Fingerprint128(const char* s, size_t len) { - return CityHash128(s, len); -} -} // namespace farmhashcc -namespace NAMESPACE_FOR_HASH_FUNCTIONS { - -// 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) { - return DebugTweak( - (can_use_sse41 & x86_64) ? farmhashnt::Hash32(s, len) : - (can_use_sse42 & can_use_aesni) ? farmhashsu::Hash32(s, len) : - can_use_sse42 ? farmhashsa::Hash32(s, len) : - farmhashmk::Hash32(s, 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) { - return DebugTweak( - (can_use_sse41 & x86_64) ? farmhashnt::Hash32WithSeed(s, len, seed) : - (can_use_sse42 & can_use_aesni) ? farmhashsu::Hash32WithSeed(s, len, seed) : - can_use_sse42 ? farmhashsa::Hash32WithSeed(s, len, seed) : - farmhashmk::Hash32WithSeed(s, len, 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) { - return DebugTweak( - (can_use_sse42 & x86_64) ? - farmhashte::Hash64(s, len) : - farmhashxo::Hash64(s, 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) { - return sizeof(size_t) == 8 ? Hash64(s, len) : Hash32(s, 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) { - return DebugTweak(farmhashna::Hash64WithSeed(s, len, 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) { - return DebugTweak(farmhashna::Hash64WithSeeds(s, len, seed0, 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) { - return DebugTweak(farmhashcc::Fingerprint128(s, 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) { - return DebugTweak(farmhashcc::CityHash128WithSeed(s, len, 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) { - return farmhashmk::Hash32(s, len); -} - -// Fingerprint function for a byte array. -uint64_t Fingerprint64(const char* s, size_t len) { - return farmhashna::Hash64(s, len); -} - -// Fingerprint function for a byte array. -uint128_t Fingerprint128(const char* s, size_t len) { - return farmhashcc::Fingerprint128(s, len); -} - -// Older and still available but perhaps not as fast as the above: -// farmhashns::Hash32{,WithSeed}() - -} // namespace NAMESPACE_FOR_HASH_FUNCTIONS - -#if FARMHASHSELFTEST - -#ifndef FARMHASH_SELF_TEST_GUARD -#define FARMHASH_SELF_TEST_GUARD -#include -#include -#include - -using std::cout; -using std::cerr; -using std::endl; -using std::hex; - -static const uint64_t kSeed0 = 1234567; -static const uint64_t kSeed1 = k0; -static const int kDataSize = 1 << 20; -static const int kTestSize = 300; -#define kSeed128 Uint128(kSeed0, kSeed1) - -static char data[kDataSize]; - -static int completed_self_tests = 0; -static int errors = 0; - -// Initialize data to pseudorandom values. -void Setup() { - if (completed_self_tests == 0) { - uint64_t a = 9; - uint64_t b = 777; - for (int i = 0; i < kDataSize; i++) { - a += b; - b += a; - a = (a ^ (a >> 41)) * k0; - b = (b ^ (b >> 41)) * k0 + i; - uint8_t u = b >> 37; - memcpy(data + i, &u, 1); // uint8_t -> char - } - } -} - -int NoteErrors() { -#define NUM_SELF_TESTS 9 - if (++completed_self_tests == NUM_SELF_TESTS) - std::exit(errors > 0); - return errors; -} - -template inline bool IsNonZero(T x) { - return x != 0; -} - -template <> inline bool IsNonZero(uint128_t x) { - return x != Uint128(0, 0); -} - -#endif // FARMHASH_SELF_TEST_GUARD - -namespace farmhashccTest { - -uint32_t CreateSeed(int offset, int salt) { - uint32_t h = static_cast(salt & 0xffffffff); - h = h * c1; - h ^= (h >> 17); - h = h * c1; - h ^= (h >> 17); - h = h * c1; - h ^= (h >> 17); - h += static_cast(offset & 0xffffffff); - h = h * c1; - h ^= (h >> 17); - h = h * c1; - h ^= (h >> 17); - h = h * c1; - h ^= (h >> 17); - return h; -} - -#undef SEED -#undef SEED1 -#undef SEED0 -#define SEED CreateSeed(offset, -1) -#define SEED0 CreateSeed(offset, 0) -#define SEED1 CreateSeed(offset, 1) - -#undef TESTING -#define TESTING 1 -#if TESTING -uint32_t expected[] = { -4223616069u, -3696677242u, -1039179260u, 1690343979u, 1018511555u, 2464489001u, -20368522u, 2663783964u, 175201532u, 1619210592u, -4081014168u, -2576519988u, -3285042206u, 502478099u, 739479538u, 1500332790u, -13754768u, 3789353455u, 3473868058u, 1909255088u, -2212771159u, -1112731063u, -826915357u, 2893489933u, 118369799u, 1848668220u, -1308219822u, 249416982u, 64306364u, 4221800195u, -1020067935u, -3955445564u, -563346294u, 550236731u, 2339016688u, 1826259714u, -3872358639u, 2295981050u, 1870005390u, 4015628802u, -1451961420u, -653440099u, -1292493871u, 164377749u, 1717712483u, 463414587u, -3924343675u, 1050492084u, 3566618804u, 2046983362u, -31917516u, -2957164615u, -230718965u, 999595115u, 3534822176u, 2175709186u, -965707431u, 441796222u, 2481718051u, 1827777486u, -2590087362u, -3879448744u, -3515079898u, 1601433082u, 982764532u, 254808716u, -1293372530u, 4205605817u, 947001462u, 1138890052u, -176305566u, -2447367541u, -2973802542u, 4123621138u, 3083865840u, 1706367795u, -792114347u, 2880110657u, 440613768u, 195054868u, -1359016305u, -3363804638u, -649488537u, 1624045597u, 1441938215u, 3147758996u, -3199173578u, 2597283203u, 2191333609u, 3763129144u, -1117290165u, -1062549743u, -2565615889u, 1046361554u, 1581968261u, 1058773671u, -1123053168u, 3807622275u, 1486749916u, 3900816089u, -2437877004u, -1894455839u, -1912520953u, 1914997013u, 561048608u, 1643267444u, -3671572006u, 194811086u, 1468911468u, 2179206286u, -673206794u, -3486923651u, -3741426466u, 3292160512u, 697001377u, 1900763774u, -3726097344u, 629282039u, 3578723715u, 2868028489u, -3269862919u, -2303349487u, -3643953525u, 2307255916u, 849996280u, 732080434u, -909961480u, 3542445214u, 2628347095u, 4236856917u, -1380660650u, -2631821908u, -2007289004u, 3509705198u, 3788541675u, 789457322u, -3090670546u, 638977894u, 3503881773u, 947102987u, -1525325287u, -1816697045u, -2706647405u, 288763142u, 3505438495u, 481308609u, -2882636782u, 3745162621u, 3503467033u, 428247823u, -176408838u, -333551502u, -1001068721u, 1681483651u, 75380831u, 4191469679u, -3627361839u, 2736617386u, 3120737438u, 1297502456u, -864896482u, -85674920u, -2886047255u, 4119881331u, 2496990525u, 3442502055u, -1806582817u, 3186345024u, 4099591287u, 2560171465u, -3489229104u, -3065015872u, -2755089808u, 3098442882u, 378524719u, 2664097023u, -1771960725u, 2901182183u, 55258521u, 1266621443u, -581644891u, -37790450u, -1800731704u, 3601350920u, 53428754u, 2759476837u, -3391093099u, 1496510311u, 2511119507u, 2636877410u, -631613207u, -1573846064u, -260484875u, 1088212603u, 2369525206u, 322522428u, -3191396600u, 2076543340u, 1552496658u, 2739811558u, -3867875546u, -2051584261u, -2126250818u, 901517871u, 3651631165u, 1323139145u, -1521111765u, 477802997u, 3508559783u, 383954241u, -3804516756u, -4250206331u, -2655954340u, 2484996477u, 1417544845u, 1520282298u, -2745204366u, 2869345147u, 1872738335u, 2592877343u, -1619744564u, -1804962124u, -3458679890u, 423948620u, 273645618u, 4187865426u, -376057175u, 2943431463u, 3581950599u, 1035398331u, -1088213445u, -861988903u, -1323370244u, 777069428u, 506235917u, 369720851u, -2789995854u, 230915180u, 1505086948u, 940361236u, -3727873235u, -1159167499u, -1860302871u, 3456858862u, 3923555152u, 2131072714u, -2910461068u, 3671950363u, 2010742682u, 4088068851u, -3616470388u, -2087714788u, -221675509u, 1230154072u, 3450704646u, 1463226695u, -1998357699u, 266026801u, 619568740u, 3560427266u, -4148162586u, -3150417316u, -1356375822u, 2056097622u, 627905802u, 3881675638u, -2309738053u, 971916703u, 3447805361u, 1673575328u, -673084328u, -3317849401u, -2836362782u, 2377208890u, 3275350588u, 158350552u, -2553241779u, 2497264995u, 3262882649u, 3897937187u, -1598963653u, -3068514414u, -601541505u, 374517071u, 3380795976u, 235752573u, -284670003u, 2990192160u, 904937105u, 2306579150u, -2117362589u, -1635274830u, -3355572906u, 170799903u, 1226685528u, 664567688u, -413219134u, 878324258u, 4026159448u, 3620649295u, -1823625377u, -3175888439u, -1759344347u, 2640637095u, 3549558u, 2192984935u, -978623493u, 804017880u, 3877562323u, 3843116489u, -1641748342u, -1853539444u, -3001178468u, 3443560727u, 2685426077u, 1653064722u, -349231508u, 2726789654u, 3136215581u, 768402830u, -269384321u, -531936536u, -2592883487u, 1343156334u, 3628619802u, 1477143570u, -4269458419u, 3285611028u, 959104925u, 2712290710u, -3480237248u, -835796333u, -2020636251u, 1191914589u, 126521603u, 4288023938u, -3731699932u, 2136758855u, 985780142u, 193807575u, -1850544433u, -653947619u, -3929316796u, 381871169u, 950486363u, 1787262279u, -360480382u, 1800636585u, 1039258631u, 3682073259u, -1262819303u, -1786000319u, -1570627191u, 893065837u, 301304916u, 1478469809u, -623018819u, 2742232545u, 2058913014u, 1706060059u, -2421125401u, -1315829592u, -3208766775u, 1805586156u, 575853086u, 3085025513u, -4010908260u, 2344058256u, 3814407434u, 1458485673u, -2474514786u, -3581895658u, -2710719679u, 190812706u, 2135454262u, 2620080728u, -3400757986u, 1669914857u, 1559978393u, 1629811331u, -3096616493u, -1391424435u, -4158376003u, 1015657076u, 794783832u, 479952178u, -1150290207u, 2497437906u, 231815090u, 755078067u, -3832053281u, -63649475u, -2415822606u, 4105027719u, 1706992318u, 1106598740u, -3941945667u, 1271300761u, 505882259u, 760186809u, -2657183368u, -1925422058u, -1039773764u, 880219458u, 4275949176u, 1556833823u, -925882132u, 4216310340u, 757497522u, 461833914u, -3884002070u, -2790957660u, -2100050089u, 651959176u, 1380301291u, 1289124125u, -452314403u, 226156280u, 3306924715u, 1750807758u, -2290180542u, -1953760569u, -2253069096u, 3960924806u, 1786291620u, 60736185u, -2569018293u, 3870479674u, 2247005661u, 2239850953u, -4261808536u, -3282975782u, -780945879u, 3349849383u, 1579362556u, 2265045884u, -905088740u, 725212379u, 3156479246u, 2501620391u, -3062836263u, -4070422690u, -996797869u, 4082582315u, 976105756u, 303983602u, -1862104804u, 3864508254u, 3383979677u, 2835500286u, -2798364010u, -519359476u, -3447342725u, 194373889u, 3313466630u, 232399983u, -2841787856u, 1672751454u, 3345183154u, 1805381384u, -2226129336u, -2847829057u, -2350774567u, 2838540121u, 2757948482u, 1017002062u, -2329150951u, 2171488196u, 3668619047u, 3874977844u, -3287966998u, -262346753u, -2493054715u, 2298644430u, 2926101182u, 1528457638u, -598656233u, 2615845874u, 989110727u, 820441411u, -253617372u, -2201077208u, -2047569338u, 3114356329u, 3335563734u, 2967673540u, -768438341u, 1417708203u, 3873718246u, 1538441843u, -1279167650u, -3917966776u, -2218481734u, 1015935150u, 1957845042u, 1318150213u, -3146423971u, 4218994877u, 1162470863u, 1519718292u, -2594658906u, -665870414u, -3430347817u, 3933868731u, 1597041394u, 3138684682u, -3398212027u, 1064647658u, 1576321132u, 14792918u, -224938029u, -3706456050u, -847274786u, 2645698692u, 1743374687u, 2343133224u, -3066596790u, 2857270120u, 200596308u, 452055528u, -2319312082u, -3488655402u, -4146865894u, 608206438u, 2699777051u, 3687240713u, -327957508u, 3664730153u, 568134564u, 2993484554u, -4159860363u, -4274533921u, -1079994063u, 2360220210u, 3609597760u, 3639708902u, -2836180437u, 1069910270u, 1892427666u, 1874729790u, -1267712826u, -121886940u, -3572289214u, 2475945610u, 783779452u, 588827737u, -1531395014u, 2085084212u, 2219189792u, 3981444548u, -2218885336u, -1691622694u, -2053232885u, 1386558530u, 2182946189u, 2365247285u, -1871081313u, 2935751853u, 38413723u, 543465863u, -900691890u, -2899905665u, -575120562u, 93133904u, 457154948u, 2983705792u, -4232229200u, 2038565963u, 614693984u, 3405328302u, -4083090010u, -2088004171u, -244031209u, 1861889294u, 2417109253u, 3299562328u, -4158642443u, 4199064449u, 3161611046u, 885015950u, -3677904099u, -2969861785u, -772348805u, 1712263832u, 3219357614u, 484271305u, -3645706114u, 2059620251u, 409557488u, 2278896731u, -224475749u, -3523022952u, -2057140088u, 449131785u, 1149879244u, 4255363996u, -3602720135u, 1690010854u, 2503998822u, 2750828466u, -3340671802u, -1447583863u, -2649684943u, 2764747249u, 3046070595u, 3441726138u, -3840332559u, 3156747501u, 1288666680u, 1472744459u, -3452391933u, -1617542784u, -217869690u, 3718469527u, 348639731u, 590532355u, -43789787u, 22606314u, 1621559290u, 2231743261u, -2234620879u, -544748955u, -3169387920u, 203343594u, 3272552527u, 1078282365u, -809576321u, 854207584u, 3625491053u, 1193737267u, -1628966807u, -2661421060u, -2433442061u, 3886639039u, 2149304418u, 303000565u, -1432830882u, 137378235u, 1135974068u, 318705754u, -2491227157u, -2627534472u, -3520352233u, 2488397682u, 3969194920u, 3843962181u, -2135981459u, 2611933220u, 799460731u, 2300968851u, -3412851628u, -3070914013u, -3555224260u, 4125937572u, 240359903u, 722496673u, -2061023600u, 3843919221u, 2759960043u, 1191155322u, -1504041490u, -3735253656u, -1773124736u, 101110011u, 1627699578u, 2645634551u, -263603947u, 1388368439u, 677146538u, 1644201982u, -2625699644u, -2403862553u, -2426069017u, 3613511705u, 915141802u, 2981654265u, -3474818167u, 2611101773u, 627891434u, 762754924u, -2143021902u, -51067670u, -4017746573u, 2269879853u, 3037857950u, 2388899692u, -582729171u, 1886116725u, 2281219772u, 264704948u, -3509984037u, -4078683368u, -2172959411u, 1807195632u, 3357092302u, 2253764928u, -2320369390u, 3076335959u, 2623583210u, 168378015u, -1435562650u, -1100977467u, -3160490319u, 2550328495u, 2396855930u, 1347823908u, -1617990918u, 3849653099u, 3224111576u, 1681539821u, -4171542880u, -552200045u, -3562947778u, 1676237880u, 3747732307u, 2453332913u, -865530667u, 3566636849u, 3485502777u, 336779723u, -2535942410u, -1685000184u, -820545711u, 1893670486u, 1273910461u, 1193758569u, -970365241u, 381205962u, 3612810852u, 1160577445u, -541488143u, -4005031080u, -2333965236u, 2419855455u, 3484533538u, 3073937876u, -908466956u, 661391539u, 2342122412u, 1467049112u, -1785800827u, -135343033u, -139643209u, 2438375667u, 974654058u, 3216478230u, -3807620420u, 779043363u, 2812846449u, 333254784u, -1025244024u, -2242303095u, -2476683742u, 350018683u, 174652916u, 933097576u, -826905896u, 559603581u, 2777181260u, 164915169u, -4070353203u, -1459055748u, -297303985u, 3103837241u, 3812514233u, 232265137u, -2032819099u, 1523091376u, 3531238208u, 1403510182u, -2886832080u, -2599705941u, -2789695716u, 68437968u, 3823813791u, 1040994569u, -3024194990u, 2461740520u, 3735391266u, 2042207153u, -2461678616u, -3519231840u, -1344224923u, 411442756u, 1179779351u, 7661528u, -778352196u, 3288808867u, 589356197u, 2627504511u, -3374744599u, -3312172905u, -357423007u, 3539567796u, 4044452215u, 1445118403u, -2937983820u, 184089910u, 346201845u, 2427295202u, -1345448010u, -2884434843u, -3085001879u, 2640105409u, 315310640u, 3530289798u, -3362974764u, 963602652u, 75228477u, 3509381180u, -4012777756u, -2380345941u, -1073137836u, 2083960378u, 1220315185u, 3628720934u, -3508867818u, 67148343u, 3558085158u, 1753943368u, -863309561u, -2844713625u, -441921850u, 854732254u, 816793316u, 2555428747u, -3440623414u, 1707304366u, 3189874375u, 1623229221u, -1220335976u, -806745430u, -3909262947u, 1680369031u, 2926179486u, 3410391660u, -3991630434u, 2876458763u, 1179167079u, 536360759u, -1592117159u, -1514343977u, -1032622306u, 2057494855u, 784938958u, 178402996u, -1152907972u, 2326185495u, 2939973666u, 4181120253u, -552831733u, -664251856u, -1297139539u, 1969357631u, 1474065957u, 3055419017u, -3395829380u, 3316562752u, 2168409017u, 614624786u, -3585854336u, -668291094u, -1162889217u, 3773171307u, 2263271126u, 355089668u, -3195850578u, 3396793277u, 3519870267u, 527857605u, -3972392320u, -2224315010u, -4047225561u, 3271434798u, 3192704713u, 2798505213u, -3932215896u, 3792924012u, 3796843756u, 453872975u, -4050552799u, -1056432676u, -928166947u, 121311642u, 930989547u, 2087070683u, -1288978057u, 1556325239u, 1812435626u, 1682385724u, -1214364933u, -904760776u, -3957045528u, 3949822847u, 2411065880u, 3716420732u, -3424837835u, 3833550693u, 1799375326u, 2012368921u, -2768764136u, -1786111037u, -4055479315u, 3751639533u, 2808224623u, 3492656387u, -1306824780u, 2624000170u, 3134795218u, 1778409297u, -3900821801u, -593336325u, -2772069220u, 2980873673u, 3574497158u, 3994780459u, -4246519854u, 3482758570u, 4228015183u, 33101083u, -1769887734u, -4158035314u, -3690638998u, 1119035482u, 4134969651u, 2483207353u, -3932823321u, 285829887u, 3485140138u, 1304815138u, -995608264u, -3133997465u, -1195477617u, 2147693728u, 3506673112u, 4234467492u, -1183174337u, 1395340482u, 769199343u, 193262308u, -2798920256u, -3827889422u, -3399695609u, 3036045724u, 2999477386u, 3567001759u, -2682864314u, 1414023907u, 3699872975u, 3369870701u, -2662284872u, -2179640019u, -2485080099u, 3234415609u, 3755915606u, 1339453220u, -1567403399u, 2076272391u, 293946298u, 3861962750u, -1291949822u, -2916864995u, -132642326u, 2215117062u, 2205863575u, 2488805750u, -405632860u, 3248129390u, 2952606864u, 896734759u, -2047417173u, -3865951392u, -657296855u, 1328547532u, 3966511825u, 3959682388u, -4171801020u, 2981416957u, 1868896247u, 790081075u, -3143666398u, -2950766549u, -2065854887u, 2737081890u, 995061774u, 1510712611u, -2865954809u, 565044286u, 1565631102u, 1500654931u, -494822108u, -2803515503u, -1058154996u, 3506280187u, 856885925u, 4204610546u, -800905649u, 1130711562u, 558146282u, 2053400666u, -449794061u, -2643520245u, -2101248725u, 3123292429u, 3583524041u, 983372394u, -1587743780u, 672870813u, 444833475u, 100741452u, -366232251u, -1717951248u, -524144122u, 1362432726u, 1304947719u, 674306020u, -405665887u, 4081931036u, 1580408204u, 2343242778u, -3901654006u, -2627173567u, -3015148205u, 814686701u, 1327920712u, 1346494176u, -2468632605u, 2259795544u, 2519278184u, 2129281928u, -2860266380u, -4001619412u, -1154910973u, 2841022216u, 1199925485u, 1372200293u, -2713179055u, 3609776550u, 2896463880u, 1056406892u, -177413841u, -40180172u, -3274788406u, 660921784u, 1686225028u, 4003382965u, -2532691887u, 4256809101u, 1186018983u, 667359096u, -2375266493u, -2760222015u, -745187078u, 312264012u, 396822261u, 2588536966u, -2026998998u, 1766454365u, 3218807676u, 3915487497u, -2630550356u, -4130063378u, -4231937074u, 752212123u, 3085144349u, 3267186363u, -4103872100u, 4193207863u, 1306401710u, 3014853131u, -1067760598u, -2306188342u, -2437881506u, 4258185052u, 2506507580u, 130876929u, -1076894205u, 4106981702u, 2799540844u, 945747327u, -1436722291u, -2499772225u, -2571537041u, 2038830635u, 2066826058u, 2892892912u, -524875858u, 3392572161u, 2869992096u, 1308273341u, -923668994u, -1980407857u, -2275009652u, 240598096u, 2658376530u, 3505603048u, -1022603789u, 582423424u, 846379327u, 4092636095u, -4177298326u, -1004173023u, -2154027018u, 2993634669u, 1098364089u, 3035642175u, -1335688126u, 1376393415u, 1252369770u, 3815033328u, -1999309358u, -1234054757u, -1388595255u, 2859334775u, 366532860u, 3453410395u, -4226967708u, 1321729870u, 2078463405u, 156766592u, -3157683394u, -3549293384u, -3348214547u, 2879648344u, 1144813399u, 2758966254u, -647753581u, 813615926u, 2035441590u, 1961053117u, -600168686u, -2192833387u, -3156481401u, 3627320321u, 383550248u, 81209584u, -2339331745u, 1284116690u, 1980144976u, 2955724163u, -789301728u, -3842040415u, -1115881490u, 965249078u, 4098663322u, 1870257033u, -2923150701u, 4217108433u, 183816559u, 2104089285u, -2640095343u, -3173757052u, -927847464u, 2383114981u, 4287174363u, 1886129652u, -70635161u, 1182924521u, 1121440038u, 4246220730u, -3890583049u, -975913757u, -2436253031u, 1074894869u, 1301280627u, 992471939u, -735658128u, 244441856u, 1541612456u, 3457776165u, -3503534059u, -1931651133u, -349142786u, 3669028584u, 1828812038u, 99128389u, -1364272849u, 1963678455u, 3971963311u, 2316950886u, -1308901796u, -2789591580u, -1460494965u, 2380227479u, 1577190651u, 1755822080u, -2911014607u, 859387544u, 13023113u, 2319243370u, -2522582211u, -2299110490u, -3342378874u, 2589323490u, 1884430765u, 3739058655u, -2419330954u, 355389916u, 273950915u, 3670136553u, -410946824u, -3174041420u, -2609010298u, 3059091350u, 2300275014u, 725729828u, -2548380995u, 1738849964u, 1257081412u, 79430455u, -810321297u, -3246190593u, -1007937684u, 912115394u, 40880059u, 3450073327u, -4289832174u, 2253485111u, 1065639151u, 2953189309u, -124779113u, -654299738u, -115760833u, 1250932069u, 884995826u, 3998908281u, -1382882981u, 1134187162u, 3202324501u, 487502928u, -3032756345u, -4057517628u, -933197381u, 2319223127u, 2044528655u, 2554572663u, -4049450620u, 1620812836u, 2832905391u, 2273005481u, -1913090121u, -1055456023u, -510593296u, 3285343192u, 2912822536u, 1645225063u, -638418430u, 452701300u, 1025483165u, 1639370512u, -167948643u, -2809842730u, -2983135664u, 407521332u, 1543756616u, 3949773145u, -4283462892u, 659962275u, 3878013463u, 1000748756u, -4053212051u, -4099239406u, -3467581965u, 354635541u, 21301844u, 3831212473u, -3189450571u, 2264401966u, 4096484849u, 1736448515u, -3976926096u, -3727194724u, -2243487039u, 585209095u, 3143046007u, 969558123u, -3037113502u, 3594170243u, 2835860223u, 3775493975u, -2787220812u, -2274252217u, -2915380701u, 3077533278u, 1252871826u, 1519790952u, -205297661u, 2950557658u, 3956882191u, 2724439401u, -3694608025u, -124028038u, -216019153u, 1533010676u, 2259986336u, 2014061617u, -2068617849u, 3078123052u, 2692046098u, 1582812948u, -396916232u, -1470894001u, -1694309312u, 300268215u, 1553892743u, 671176040u, -1544988994u, 2793402821u, 4194972569u, 2296476154u, -748354332u, -3491325898u, -4261053291u, 1104998242u, 797816835u, 243564059u, -2197717393u, 299029458u, 1675252188u, 3139770041u, -583018574u, -2532106100u, -2099391658u, 3760526730u, 3422719327u, 3556917689u, -2374009285u, 2130865894u, 3710563151u, 1437538307u, -3938030842u, -2006930694u, -2151243336u, 1939741287u, 1957068175u, 2135147479u, -649553342u, 1713643042u, 4188696599u, 1698739939u, -3549427584u, -1016382174u, -322644378u, 2476164549u, 2037263020u, 88036019u, -2548960923u, 539867919u, 2871157727u, 4031659929u, -754087252u, -972656559u, -4246379429u, 3877308578u, 2059459630u, 3614934323u, -1410565271u, 2102980459u, 215395636u, 1083393481u, -3775523015u, -2062750105u, -2475645882u, 3041186774u, 3534315423u, 758607219u, -1686100614u, 180500983u, 1155581185u, 1476664671u, -2918661695u, -3812731350u, -4003853737u, 4148884881u, 1468469436u, 3278880418u, -1045838071u, 1049161262u, 360450415u, 3158065524u, -814443735u, -3391401707u, -729968410u, 738771593u, 3662738792u, 1672830580u, -4199496163u, 188487238u, 219098233u, 2141731267u, -3890250614u, -2988780375u, -4026279523u, 3489429375u, 2468433807u, 1178270701u, -2685094218u, 2716621497u, 3718335529u, 2273344755u, -701110882u, -1925717409u, -1515176562u, 2325460593u, 3954798930u, 784566105u, -3769422266u, 1641530321u, 2703876862u, 2907480267u, -1828076455u, -1805635221u, -3883381245u, 1476756210u, 2072514392u, 3658557081u, -2003610746u, 2556845550u, 729594004u, 3303898266u, -1968227254u, -423204951u, -231828688u, 4223697811u, 698619045u, 3636824418u, -2738779239u, 2333529003u, 2833158642u, 580285428u, -3038148234u, -1012378004u, -1113647298u, 1424593483u, 4053247723u, 1167152941u, -2677383578u, 3419485379u, 2135673840u, 440478166u, -1682229112u, -3226724137u, -1217439806u, 3828726923u, 3636576271u, 3467643156u, -2005614908u, 2655346461u, 2345488441u, 1027557096u, -3594084220u, -1372306343u, -2342583762u, 4291342905u, 4094931814u, 3254771759u, -821978248u, 2404930117u, 1143937655u, 3156949255u, -3460606610u, -449701786u, -3474906110u, 1932585294u, 2283357584u, 1808481478u, -3522851029u, 3040164731u, 1530172182u, 2950426149u, -1402416557u, -756419859u, -4132576145u, 724994790u, 2852015871u, 2177908339u, -899914731u, 139675671u, 1423281870u, 3198458070u, -807581308u, -2021611521u, -1801452575u, 1425984297u, 2833835949u, 1536827865u, -3902351840u, 164546042u, 1872840974u, 3986194780u, -792156290u, -3378681896u, -941547959u, 3931328334u, 3661060482u, 2386420777u, -3920146272u, 3458621279u, 3348500844u, 2269586542u, -797371473u, -3188953649u, -80514771u, 2913333490u, 1246325623u, 3253846094u, -1723906239u, 1606413555u, 587500718u, 1412413859u, -2310046829u, -2113313263u, -3855635608u, 47271944u, 1112281934u, 3440228404u, -2633519166u, 425094457u, 307659635u, 67338587u, -2412987939u, -2363930989u, -2853008596u, 2844637339u, 922568813u, 130379293u, -2825204405u, 2904442145u, 1176875333u, 1511685505u, -599177514u, -1872681372u, -682394826u, 1888849790u, 3635304282u, 1761257265u, -1571292431u, 355247075u, 1177210823u, 1691529530u, -3629531121u, -3760474006u, -1129340625u, 868116266u, 3908237785u, 1942124366u, -1266630014u, 3214841995u, 334023850u, 1110037019u, -369650727u, -1288666741u, -70535706u, 20230114u, 4284225520u, 727856157u, -293696779u, 1244943770u, 3976592462u, 560421917u, -4171688499u, -2438786950u, -1218144639u, 3809125983u, 1302395746u, 534542359u, -2121993015u, 2899519374u, 3192177626u, 1761707794u, -3101683464u, -1555403906u, -3225675390u, 1875263768u, 4278894569u, 651707603u, -2111591484u, 3802716028u, 2900262228u, 1181469202u, -3254743797u, -1822684466u, -860641829u, 3046128268u, 1284833012u, 1125261608u, -461384524u, 2331344566u, 1274400010u, 990498321u, -3462536298u, -3796842585u, -2346607194u, 279495949u, 3951194590u, 3522664971u, -3169688303u, 726831706u, 1123875117u, 1816166599u, -3759808754u, -2918558151u, -3713203220u, 3369939267u, 466047109u, 384042536u, -587271104u, 2191634696u, 2449929095u, 1157932232u, -2084466674u, -841370485u, -3241372562u, 4277738486u, 2150836793u, 1173569449u, -778768930u, 2594706485u, 3065269405u, 3019263663u, -2660146610u, -2789946230u, -77056913u, 728174395u, 3647185904u, 804562358u, -2697276483u, 881311175u, 1178696435u, 2059173891u, -2308303791u, -221481230u, -50241451u, 3689414100u, 1969074761u, 2732071529u, -1900890356u, 840789500u, 2100609300u, 985565597u, -1220850414u, -2456636259u, -223607678u, 1016310244u, 1937434395u, 85717256u, -275058190u, 3712011133u, 171916016u, 2389569096u, -3679765802u, -3575358777u, -3481108261u, 3178286380u, 2489642395u, 2931039055u, -3086601621u, 3079518902u, 3027718495u, 2506894644u, -2976869602u, -2134336365u, -2420172217u, 918054427u, 661522682u, 1403791357u, -3587174388u, 2623673551u, 1355661457u, 4159477684u, -1109013587u, -3112183488u, -2217849279u, 3500291996u, 2419603731u, 2929886201u, -3854470013u, 1358382103u, 1357666555u, 21053566u, -2716621233u, -3094836862u, -3309729704u, 57086558u, 839187419u, 2757944838u, -3651040558u, 3607536716u, 3691257732u, 2312878285u, -1202511724u, -183479927u, -2509829803u, 109313218u, 478173887u, 2072044014u, -190631406u, 2495604975u, 1010416260u, 3679857586u, -726566957u, -258500881u, -1805873908u, 3081447051u, 2352101327u, 534922207u, -1584552873u, 813470716u, 255914637u, 249169434u, -3193498057u, -1038802706u, -2590158653u, 3147907290u, 663060128u, 1156177857u, -634616100u, 312879189u, 1545020368u, 2054634247u, -3271451914u, -3438291534u, -2181454946u, 3864535432u, 2398586877u, 896491075u, -2810631478u, 2770357487u, 3372930052u, 898070638u, -2051007323u, -392959778u, -36645539u, 3743556044u, 4134529680u, 4124451188u, -566806297u, 2936523982u, 1304761965u, 537399498u, -1940818842u, -40862381u, -36288410u, 3063605629u, 2826611650u, 3961972098u, -1871578006u, 2392095486u, 1136931591u, 513864488u, -173276451u, -3039055682u, -3543322032u, 1943592006u, 657217094u, 1751698246u, -2969618445u, 456616022u, 900309519u, 113892716u, -1126392103u, -1235651045u, -1882073852u, 2136610853u, 2353639710u, 2819956700u, -3980083530u, 828773559u, 224069850u, 902434120u, -2802008036u, -94358995u, -2777723394u, 2812641403u, 2525832595u, 4157388110u, -4235563782u, 937800324u, 141690749u, 568062536u, -550123849u, -1330316521u, -1949488696u, 2296431366u, 1958465262u, 3564751729u, -3748252207u, 120455129u, 1607318832u, 2525729790u, -2640987481u, -2332096657u, -1775969159u, 1555085077u, 2913525137u, 1347085183u, -2376253113u, 3194050574u, 1806090610u, 678641356u, -1499146713u, -383849715u, -3299835823u, 2284860330u, 2614269636u, 3913628844u, -2761334210u, 1959484587u, 529797021u, 239966995u, -3102194829u, -3602307804u, -1122192627u, 3577510006u, 164486066u, 1680137310u, -1473396395u, 1467801424u, 903493660u, 1185943071u, -2798556505u, -2306744492u, -3167201310u, 3577947177u, 3067592134u, 2905506289u, -1210366329u, 204484056u, 2347778932u, 3862374472u, -3277439508u, -4187414621u, -1646699310u, 621385800u, 3934869089u, 3975491588u, -3580085916u, 1925674500u, 2436305348u, 3983301539u, -2739439523u, -3291507446u, -3395637920u, 3753389171u, 2955202032u, 2654255623u, -3771089254u, 2140443405u, 2779834738u, 3261942805u, -3526889244u, -1842009139u, -4048484340u, 2106218403u, 2161244271u, 772152700u, -1158647659u, 3776791619u, 3882186721u, 699525237u, -2954670460u, -1007105869u, -3359152025u, 1146388699u, 1401550303u, 2326582541u, -4181783540u, 1085644043u, 1942143795u, 1038368308u, -1526153809u, -4042547244u, -1891441000u, 2573991874u, 1281441253u, 3635098284u, -1980545715u, 825985487u, 3934748116u, 4228386979u, -1480870944u, -1042194545u, -2397771642u, 2248490001u, 3817869868u, 878654626u, -3785629484u, 1672470870u, 3229367873u, 1894538933u, -1010692731u, -1733824268u, -656620328u, 3048283803u, 3353340056u, 2324965120u, -4192585951u, 2284524675u, 3483884368u, 1510168293u, -1554942691u, -1309709396u, -1241133168u, 3162179280u, 4046378054u, 3171681593u, -1165297136u, 3496703563u, 150437903u, 1948622072u, -1076332463u, -2292479143u, -1464229958u, 3479738093u, 2328067598u, 2334503110u, -833324834u, 3981605747u, 3002629155u, 2854644186u, -2832201336u, -95796957u, -3269249397u, 2358313329u, 3411860910u, 4283292480u, -2802208697u, 1305947955u, 2156803420u, 1991340283u, -189678024u, -447602599u, -1055411517u, 1531748363u, 1555852656u, 412402681u, -3774988152u, 20597551u, 2925024131u, 1423989620u, -3749428061u, -1541439448u, -112270416u, 1936224776u, 132162941u, 3772011507u, -3814102518u, 1908807815u, 444154079u, 823765347u, -3362275567u, -3419047430u, -2108287005u, 2315102125u, 658593738u, 3195094029u, -3721937534u, 3176229204u, 3398835373u, 1271898712u, -1142546577u, -3185986817u, -3562705803u, 2046119567u, 912990621u, 1829977672u, -3459576979u, 1118045834u, 1369529376u, 3320601076u, -3954988953u, -4002467635u, -3359456351u, 1314849568u, 1766750942u, 2998874853u, -1181800239u, 707328036u, 3314954697u, 2066721120u, -598194215u, -1124451278u, -3156679616u, 3742684743u, 2960199690u, 2683497915u, -2566077529u, 937014607u, 102095219u, 4262922475u, -3132264275u, -1262099830u, -862722905u, 2717653494u, 3245583534u, 3427209989u, -3220278124u, 85457091u, 2222333500u, 3513997967u, -3522324951u, -2830855552u, -2215004781u, 3482411840u, 4227160614u, 2030964411u, -1741393851u, 2643723748u, 942813508u, 403442675u, -3112048748u, -530556423u, -3817755244u, 3543286628u, 2247276090u, 1532920842u, -4101962711u, 1446540991u, 3297821473u, 1861255389u, -1984398u, -2366525138u, -377589481u, 3549193828u, 1427765914u, 506831657u, -277278988u, 1447652775u, 3214362239u, 3142198690u, -2843087541u, -468915015u, -807895062u, 2198723907u, 4031145069u, 2417156212u, -4027298697u, 637175947u, 1229254212u, 1773257887u, -1659444818u, -451148891u, -2099741368u, 735351990u, 2534775713u, 3261804619u, -712519954u, 3527962772u, 3758642738u, 4245823575u, -1281314264u, -1167866160u, -1489546151u, 1197354389u, 1043278102u, 2563326586u, -371937794u, 2320164817u, 3189512691u, 573685198u, -4108603513u, -3758899588u, -3507030163u, 2947201212u, 2529492585u, 578234375u, -3362349842u, 3318878925u, 3611203517u, 3059253190u, -4270755916u, -4291274625u, -4237586791u, 4137422245u, 2927218651u, 2444687041u, -797128811u, 2043057612u, 396533859u, 2665256178u, -3346510674u, -1779586176u, -3076562062u, 1882746214u, 921095362u, 2026988397u, -514514911u, 3886379478u, 4218272420u, 1480386793u, -3900160816u, -2292273451u, -1276138356u, 1125461821u, 1912885715u, 3365266013u, -1333211627u, 4085009861u, 1390530102u, 3347984752u, -2721771301u, -1419492325u, -4066766256u, 3250852311u, 820111852u, 1382201318u, -2366036798u, 938032241u, 3100979439u, 487048687u, -2292851045u, -3241399180u, -3912670510u, 2416437067u, 2973194517u, 3507707986u, -1935099406u, 2533441488u, 104616731u, 2892622820u, -3801190339u, -4239188808u, -807238241u, 3300121546u, 2249406147u, 4032114017u, -3713738189u, 3324425575u, 4275607376u, 3663120298u, -4173658372u, -3984289690u, -1827636846u, 3264588778u, 3297165529u, 558623533u, -2728945672u, 1566297318u, 3447249966u, 481719551u, -1596842050u, -1838185946u, -265271620u, 1050246315u, 4046655705u, 1844193138u, -3807563245u, 1075384804u, 1292554949u, 1506525927u, -2921816148u, -2051885269u, -1930534041u, 3872721086u, 1564489377u, 2272482181u, -2849358683u, 589618304u, 2262072443u, 290363051u, -299168363u, -3867603931u, -2868688756u, 2545263115u, 1092098533u, 3885725603u, -2352430409u, 1981595469u, 2047946646u, 1332642839u, -793806516u, -214858837u, -1061484659u, 3192394476u, 1115054785u, 3690637234u