#pragma once
// 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(_MSC_VER)
# define FARMHASH_NO_BUILTIN_EXPECT
#endif
#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 <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__) || defined(__DragonFly__)
#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_ssse3
#if defined(__SSSE3__) || defined(FARMHASH_ASSUME_SSSE3)
#include <immintrin.h>
#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 <immintrin.h>
#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 <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
#undef can_use_avx
#if defined(__AVX__) || defined(FARMHASH_ASSUME_AVX)
#include <immintrin.h>
#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<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;
}
} // namespace NAMESPACE_FOR_HASH_FUNCTIONS
using namespace std;
using namespace NAMESPACE_FOR_HASH_FUNCTIONS;