blob: 673f45f2c14dd34b0526354fec54b4ced11cfa39 [file] [log] [blame]
/*
* Copyright (C) 2017 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "util/hash/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_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
#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_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 <libkern/OSByteOrder.h>
#undef bswap_32
#undef bswap_64
#define bswap_32(x) OSSwapInt32(x)
#define bswap_64(x) OSSwapInt64(x)
#elif defined(__sun) || defined(sun)
#include <sys/byteorder.h>
#undef bswap_32
#undef bswap_64
#define bswap_32(x) BSWAP_32(x)
#define bswap_64(x) BSWAP_64(x)
#elif defined(__FreeBSD__)
#include <sys/endian.h>
#undef bswap_32
#undef bswap_64
#define bswap_32(x) bswap32(x)
#define bswap_64(x) bswap64(x)
#elif defined(__OpenBSD__)
#include <sys/types.h>
#undef bswap_32
#undef bswap_64
#define bswap_32(x) swap32(x)
#define bswap_64(x) swap64(x)
#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(x) bswap32(x)
#define bswap_64(x) bswap64(x)
#endif
#else
#undef bswap_32
#undef bswap_64
#include <byteswap.h>
#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__)
#define x86_64 1
#else
#define x86_64 0
#endif
#undef x86
#if defined(__i386__) || defined(__i386) || defined(__X86__)
#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_sse42
#if defined(__SSE4_2__) || defined(FARMHASH_ASSUME_SSE42)
#include <nmmintrin.h>
#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 <wmmintrin.h>
#define can_use_aesni 1
// Now we can use _mm_aesimc_si128 and so on.
#else
#define can_use_aesni 0
#endif
#if can_use_sse42 || can_use_aesni
STATIC_INLINE __m128i Load128(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) 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 <typename T> 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;
}
using namespace std;
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<uint32_t>(a) + (static_cast<uint32_t>(b) << 8);
uint32_t z = len + (static_cast<uint32_t>(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<uint64_t, uint64_t> 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 std::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<uint64_t, uint64_t> 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<uint64_t, uint64_t> v = std::make_pair(0, 0);
pair<uint64_t, uint64_t> w = std::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 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 == nullptr ? 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));
}
STATIC_INLINE __m128i Shuffle2031(__m128i x) {
return _mm_shuffle_epi32(x, (2 << 6) + (0 << 4) + (3 << 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( \
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);
__m128i q;
if (len < 80) {
__m128i a = Load128(s);
__m128i b = Load128(s + 16);
__m128i c = Load128(s + (len - 15) / 2);
__m128i d = Load128(s + len - 32);
__m128i e = Load128(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 = Load128(s); \
__m128i b = Load128(s + 16); \
__m128i c = Load128(s + 32); \
__m128i d = Load128(s + 48); \
__m128i e = Load128(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 = Rot17(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<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 farmhashns {
#if !can_use_sse42 || !can_use_aesni || !x86_64
uint32_t Hash32(const char *s, size_t len) {
FARMHASH_DIE_IF_MISCONFIGURED;
return s == nullptr ? 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 len <= 256 ?
static_cast<uint32_t>(farmhashna::Hash64(s, len)) :
farmhashsu::Hash32(s, len);
}
uint32_t Hash32WithSeed(const char *s, size_t len, uint32_t seed) {
return len <= 256 ?
static_cast<uint32_t>(farmhashna::Hash64WithSeed(s, len, seed)) :
farmhashsu::Hash32WithSeed(s, len, seed);
}
#endif
} // namespace farmhashns
namespace farmhashsa {
#if !can_use_sse42
uint32_t Hash32(const char *s, size_t len) {
FARMHASH_DIE_IF_MISCONFIGURED;
return s == nullptr ? 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 = Load128(s);
__m128i b = Load128(s + 16);
__m128i c = Load128(s + (len - 15) / 2);
__m128i d = Load128(s + len - 32);
__m128i e = Load128(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 = Load128(s); \
__m128i b = Load128(s + 16); \
__m128i c = Load128(s + 32); \
__m128i d = Load128(s + 48); \
__m128i e = Load128(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<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 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<uint32_t>(a) + (static_cast<uint32_t>(b) << 8);
uint32_t z = len + (static_cast<uint32_t>(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<uint64_t, uint64_t> 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 std::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<uint64_t, uint64_t> 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<uint64_t, uint64_t> 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
// 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) {
if (can_use_sse42 & can_use_aesni & x86_64)
return DebugTweak(farmhashns::Hash32(s, len));
return DebugTweak(
(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) {
if (can_use_sse42 & can_use_aesni & x86_64)
return DebugTweak(farmhashns::Hash32WithSeed(s, len, seed));
return DebugTweak(
(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(farmhashna::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);
}
} // namespace NAMESPACE_FOR_HASH_FUNCTIONS
#if FARMHASHSELFTEST
#ifndef FARMHASH_SELF_TEST_GUARD
#define FARMHASH_SELF_TEST_GUARD
#include <cstdio>
#include <iostream>
#include <string.h>
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 6
if (++completed_self_tests == NUM_SELF_TESTS)
std::exit(errors > 0);
return errors;
}
template <typename T> inline bool IsNonZero(T x) {
return x != 0;
}
template <> inline bool IsNonZero<uint128_t>(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<uint32_t>(salt & 0xffffffff);
h = h * c1;
h ^= (h >> 17);
h = h * c1;
h ^= (h >> 17);
h = h * c1;
h ^= (h >> 17);
h += static_cast<uint32_t>(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,