hash.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_FUNCTIONAL_HASH_HPP__
#define NEFORCE_CORE_FUNCTIONAL_HASH_HPP__

 
#include "NeForce/core/memory/bit.hpp"
#include "NeForce/core/memory/endian.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <typename Key, typename Dummy = void>
struct hash;

template <typename T>
struct hash<T*> {
    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_t operator()(const T* ptr) const noexcept {
        return static_cast<size_t>(reinterpret_cast<uintptr_t>(ptr));
    }
};
 // HashPrimary
 
NEFORCE_BEGIN_CONSTANTS__


NEFORCE_INLINE17 constexpr size_t FNV_OFFSET_BASIS =
#ifdef NEFORCE_ARCH_BITS_64
        14695981039346656037ULL;
#else
        2166136261U;
#endif

NEFORCE_INLINE17 constexpr size_t FNV_PRIME
#ifdef NEFORCE_ARCH_BITS_64
        = 1099511628211ULL;
#else
        = 16777619U;
#endif
 // HashPrimary
 
NEFORCE_END_CONSTANTS__


NEFORCE_CONSTEXPR14 size_t FNV_hash(const byte_t* first, const size_t count) noexcept {
    size_t result = constants::FNV_OFFSET_BASIS;
    for (size_t i = 0; i < count; i++) {
        result ^= static_cast<size_t>(first[i]);
        result *= constants::FNV_PRIME;
    }
    return result;
}

template <typename T>
NEFORCE_CONSTEXPR14 size_t FNV_hash_integer(const T value) noexcept {
    static_assert(is_integral<T>::value, "T must be integral");
 
    size_t result = constants::FNV_OFFSET_BASIS;
    for (size_t i = 0; i < sizeof(T); ++i) {
        const auto byte_val = static_cast<byte_t>((value >> (i * 8)) & 0xFF);
        result ^= static_cast<size_t>(byte_val);
        result *= constants::FNV_PRIME;
    }
    return result;
}

template <typename CharT>
NEFORCE_CONSTEXPR14 size_t FNV_hash_string(const CharT* str, const size_t len) noexcept {
    static_assert(is_character<CharT>::value, "CharT must be character types");
 
    size_t result = constants::FNV_OFFSET_BASIS;
    for (size_t i = 0; i < len; ++i) {
        result ^= static_cast<size_t>(static_cast<byte_t>(str[i]));
        result *= constants::FNV_PRIME;
    }
    return result;
}

NEFORCE_CONSTEXPR14 size_t low_level_hash(size_t x) noexcept {
#ifdef NEFORCE_ARCH_BITS_64
    x += 0x9e3779b97f4a7c15ULL;
    x ^= x >> 33;
    x *= 0xff51afd7ed558ccdULL;
    x ^= x >> 33;
    x *= 0xc4ceb9fe1a85ec53ULL;
    x ^= x >> 33;
    return x;
#else
    x += 0x9e3779b9U;
    x ^= x >> 16;
    x *= 0x85ebca6bU;
    x ^= x >> 13;
    x *= 0xc2b2ae35U;
    x ^= x >> 16;
    return x;
#endif
}
 // HashPrimary

 
template <>
struct hash<bool> {
    NEFORCE_NODISCARD constexpr size_t operator()(const bool x) const noexcept { return x ? 0x9e3779b9 : 0x7f4a7c15; }
};
 
#define __NEFORCE_BUILD_INTEGER_HASH_STRUCT(OPT)                                    \
    template <>                                                                     \
    struct hash<OPT> {                                                              \
        NEFORCE_NODISCARD constexpr size_t operator()(const OPT x) const noexcept { \
            return low_level_hash(static_cast<size_t>(x));                          \
        }                                                                           \
    };
 
NEFORCE_MACRO_RANGE_CHARS(__NEFORCE_BUILD_INTEGER_HASH_STRUCT)
NEFORCE_MACRO_RANGE_INT(__NEFORCE_BUILD_INTEGER_HASH_STRUCT)
#undef __NEFORCE_BUILD_INTEGER_HASH_STRUCT
 
#define __NEFORCE_BUILD_FLOAT_HASH_STRUCT(OPT)                                                \
    template <>                                                                               \
    struct hash<OPT> {                                                                        \
    private:                                                                                  \
        union __float_converter {                                                             \
            OPT f;                                                                            \
            uint64_t i;                                                                       \
        };                                                                                    \
                                                                                              \
    public:                                                                                   \
        NEFORCE_NODISCARD NEFORCE_CONSTEXPR14 size_t operator()(const OPT x) const noexcept { \
            if (x == 0.0f)                                                                    \
                return 0;                                                                     \
            __float_converter converter{};                                                    \
            converter.f = x;                                                                  \
            return low_level_hash(static_cast<size_t>(converter.i));                          \
        }                                                                                     \
    };
 
NEFORCE_MACRO_RANGE_FLOAT(__NEFORCE_BUILD_FLOAT_HASH_STRUCT)
#undef __NEFORCE_BUILD_FLOAT_HASH_STRUCT


template <typename T>
NEFORCE_CONSTEXPR14 void hash_combine(size_t& seed, const T& value) noexcept {
    seed ^= hash<T>()(value) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template <typename... Types>
NEFORCE_CONSTEXPR14 size_t hash_combine_all(const Types&... values) noexcept {
    size_t seed = 0;
    int dummy[] = {(_NEFORCE hash_combine(seed, values), 0)...};
    ignore = dummy;
    return seed;
}


template <typename T>
struct hash<T, enable_if_t<is_enum_v<T>>> {
    NEFORCE_NODISCARD NEFORCE_CONSTEXPR14 size_t operator()(const T e) const {
        using UT = underlying_type_t<T>;
        return hash<UT>()(static_cast<UT>(e));
    }
};

NEFORCE_CONSTEXPR14 size_t DJB2_hash(const char* str, const size_t len) noexcept {
    size_t hash = 5381;
    for (size_t i = 0; i < len; ++i) {
        hash = (hash << 5) + hash + static_cast<byte_t>(str[i]);
    }
    return hash;
}
 
 
#ifdef NEFORCE_ARCH_BITS_64

struct murmur_hash {
    size_t low = 0;  
    size_t high = 0; 
 
    murmur_hash() noexcept = default;
    ~murmur_hash() noexcept = default;

    murmur_hash(const size_t l, const size_t h) noexcept :
    low(l),
    high(h) {}
};

murmur_hash NEFORCE_API murmur_hash64(const void* key, size_t len, uint32_t seed) noexcept;
#endif

uint32_t NEFORCE_API murmur_hash32(const void* key, size_t len, uint32_t seed) noexcept;
 
 
#ifdef NEFORCE_COMPILER_MSVC
// use switch penetrate
#    pragma warning(push)
#    pragma warning(disable : 26819)
#endif
 

NEFORCE_CONSTEXPR14 uint32_t XXH32(const void* input, size_t len, uint32_t seed = 0) noexcept {
    constexpr uint32_t PRIME32_1 = 0x9E3779B1U;
    constexpr uint32_t PRIME32_2 = 0x85EBCA77U;
    constexpr uint32_t PRIME32_3 = 0xC2B2AE3DU;
    constexpr uint32_t PRIME32_4 = 0x27D4EB2FU;
    constexpr uint32_t PRIME32_5 = 0x165667B1U;
 
    const auto* p = static_cast<const byte_t*>(input);
    uint32_t hash = 0;
 
    if (len >= 16) {
        uint32_t acc1 = seed + PRIME32_1 + PRIME32_2;
        uint32_t acc2 = seed + PRIME32_2;
        uint32_t acc3 = seed + 0;
        uint32_t acc4 = seed - PRIME32_1;
 
        const byte_t* limit = p + (len & ~static_cast<size_t>(15));
        for (; p < limit; p += 16) {
            acc1 = rotate_l32(acc1 + endian::read_le32(p + 0) * PRIME32_2, 13) * PRIME32_1;
            acc2 = rotate_l32(acc2 + endian::read_le32(p + 4) * PRIME32_2, 13) * PRIME32_1;
            acc3 = rotate_l32(acc3 + endian::read_le32(p + 8) * PRIME32_2, 13) * PRIME32_1;
            acc4 = rotate_l32(acc4 + endian::read_le32(p + 12) * PRIME32_2, 13) * PRIME32_1;
        }
 
        hash = rotate_l32(acc1, 1) + rotate_l32(acc2, 7) + rotate_l32(acc3, 12) + rotate_l32(acc4, 18);
    } else {
        hash = seed + PRIME32_5;
    }
 
    hash += static_cast<uint32_t>(len);
 
    const byte_t* end = static_cast<const byte_t*>(input) + len;
    for (; p + 4 <= end; p += 4) {
        hash += endian::read_le32(p) * PRIME32_3;
        hash = rotate_l32(hash, 17) * PRIME32_4;
    }
    switch (len & 3) {
        case 3:
            hash += static_cast<uint32_t>(p[2]) * PRIME32_5;
            hash = rotate_l32(hash, 11) * PRIME32_1;
        case 2:
            hash += static_cast<uint32_t>(p[1]) * PRIME32_5;
            hash = rotate_l32(hash, 11) * PRIME32_1;
        case 1:
            hash += static_cast<uint32_t>(p[0]) * PRIME32_5;
            hash = rotate_l32(hash, 11) * PRIME32_1;
        default:
            break;
    }
 
    hash ^= hash >> 15;
    hash *= PRIME32_2;
    hash ^= hash >> 13;
    hash *= PRIME32_3;
    hash ^= hash >> 16;
 
    return hash;
}
 
#ifdef NEFORCE_ARCH_BITS_64

NEFORCE_CONSTEXPR14 uint64_t XXH64(const void* input, size_t len, uint64_t seed = 0) noexcept {
    constexpr uint64_t PRIME64_1 = 0x9E3779B185EBCA87ULL;
    constexpr uint64_t PRIME64_2 = 0xC2B2AE3D27D4EB4FULL;
    constexpr uint64_t PRIME64_3 = 0x165667B19E3779F9ULL;
    constexpr uint64_t PRIME64_4 = 0x85EBCA77C2B2AE63ULL;
    constexpr uint64_t PRIME64_5 = 0x27D4EB2F165667C5ULL;
 
    const auto* p = static_cast<const byte_t*>(input);
    uint64_t hash = 0;
 
    if (len >= 32) {
        uint64_t acc1 = seed + PRIME64_1 + PRIME64_2;
        uint64_t acc2 = seed + PRIME64_2;
        uint64_t acc3 = seed + 0;
        uint64_t acc4 = seed - PRIME64_1;
 
        const byte_t* limit = p + (len & ~static_cast<size_t>(31));
        for (; p < limit; p += 32) {
            acc1 = rotate_l64(acc1 + endian::read_le64(p + 0) * PRIME64_2, 31) * PRIME64_1;
            acc2 = rotate_l64(acc2 + endian::read_le64(p + 8) * PRIME64_2, 31) * PRIME64_1;
            acc3 = rotate_l64(acc3 + endian::read_le64(p + 16) * PRIME64_2, 31) * PRIME64_1;
            acc4 = rotate_l64(acc4 + endian::read_le64(p + 24) * PRIME64_2, 31) * PRIME64_1;
        }
 
        hash = rotate_l64(acc1, 1) + rotate_l64(acc2, 7) + rotate_l64(acc3, 12) + rotate_l64(acc4, 18);
 
        hash ^= rotate_l64(acc1 * PRIME64_2, 31) * PRIME64_1;
        hash = hash * PRIME64_1 + PRIME64_4;
        hash ^= rotate_l64(acc2 * PRIME64_2, 31) * PRIME64_1;
        hash = hash * PRIME64_1 + PRIME64_4;
        hash ^= rotate_l64(acc3 * PRIME64_2, 31) * PRIME64_1;
        hash = hash * PRIME64_1 + PRIME64_4;
        hash ^= rotate_l64(acc4 * PRIME64_2, 31) * PRIME64_1;
        hash = hash * PRIME64_1 + PRIME64_4;
    } else {
        hash = seed + PRIME64_5;
    }
 
    hash += static_cast<uint64_t>(len);
 
    const byte_t* end = static_cast<const byte_t*>(input) + len;
    for (; p + 8 <= end; p += 8) {
        uint64_t k1 = endian::read_le64(p);
        k1 *= PRIME64_2;
        k1 = rotate_l64(k1, 31);
        k1 *= PRIME64_1;
        hash ^= k1;
        hash = rotate_l64(hash, 27) * PRIME64_1 + PRIME64_4;
    }
    for (; p + 4 <= end; p += 4) {
        hash ^= static_cast<uint64_t>(endian::read_le32(p)) * PRIME64_1;
        hash = rotate_l64(hash, 23) * PRIME64_2 + PRIME64_3;
    }
    switch (len & 3) {
        case 3:
            hash ^= static_cast<uint64_t>(p[2]) * PRIME64_5;
            hash = rotate_l64(hash, 11) * PRIME64_1;
        case 2:
            hash ^= static_cast<uint64_t>(p[1]) * PRIME64_5;
            hash = rotate_l64(hash, 11) * PRIME64_1;
        case 1:
            hash ^= static_cast<uint64_t>(p[0]) * PRIME64_5;
            hash = rotate_l64(hash, 11) * PRIME64_1;
        default:
            break;
    }
 
    hash ^= hash >> 33;
    hash *= PRIME64_2;
    hash ^= hash >> 29;
    hash *= PRIME64_3;
    hash ^= hash >> 32;
 
    return hash;
}
 
 
#    ifdef NEFORCE_COMPILER_MSVC
#        pragma warning(pop)
#    endif
 

uint64_t NEFORCE_API wyhash(const void* key, size_t len, uint64_t seed) noexcept;
 
#endif
 

size_t NEFORCE_API city_hash64(const void* key, size_t len) noexcept;
 

uint64_t NEFORCE_API XXH3_64(const void* data, size_t len) noexcept;
 

template <typename Key, typename Dummy = void>
struct is_nothrow_hashable : false_type {};

template <typename Key>
struct is_nothrow_hashable<Key, void_t<decltype(_NEFORCE hash<Key>{}(_NEFORCE declval<const Key&>()))>>
: bool_constant<noexcept(_NEFORCE hash<Key>{}(_NEFORCE declval<const Key&>()))> {};
 
#ifdef NEFORCE_STANDARD_14
template <typename Key>
NEFORCE_INLINE17 constexpr bool is_nothrow_hashable_v = is_nothrow_hashable<Key>::value;
#endif
 

template <typename Func, typename Arg, typename Dummy = void>
struct is_hash : false_type {};

template <typename Func, typename Arg>
struct is_hash<Func, Arg,
               enable_if_t<is_convertible<decltype(_NEFORCE declval<Func>()(_NEFORCE declval<Arg>())), size_t>::value>>
: true_type {};
 
#ifdef NEFORCE_STANDARD_14
template <typename Func, typename Arg>
constexpr bool is_hash_v = is_hash<Func, Arg>::value;
#endif
 // HashPrimary
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_FUNCTIONAL_HASH_HPP__