qhash.cpp

Go to the documentation of this file.

// Copyright (C) 2020 The Qt Company Ltd.
// Copyright (C) 2021 Intel Corporation.
// Copyright (C) 2012 Giuseppe D'Angelo <dangelog@gmail.com>.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
// for rand_s, _CRT_RAND_S must be #defined before #including stdlib.h.
// put it at the beginning so some indirect inclusion doesn't break it
#ifndef _CRT_RAND_S
#define _CRT_RAND_S
#endif
#include <stdlib.h>
#include <stdint.h>
 
#include "qhash.h"
 
#ifdef truncate
#undef truncate
#endif
 
#include <qbitarray.h>
#include <qstring.h>
#include <qglobal.h>
#include <qbytearray.h>
#include <qdatetime.h>
#include <qbasicatomic.h>
#include <qendian.h>
#include <private/qrandom_p.h>
#include <private/qsimd_p.h>
 
#ifndef QT_BOOTSTRAPPED
#include <qcoreapplication.h>
#include <qrandom.h>
#include <private/qlocale_tools_p.h>
#endif // QT_BOOTSTRAPPED
 
#include <array>
#include <limits.h>
 
#if defined(QT_NO_DEBUG) && !defined(NDEBUG)
#  define NDEBUG
#endif
#include <assert.h>
 
#ifdef Q_CC_GNU
#  define Q_DECL_HOT_FUNCTION       __attribute__((hot))
#else
#  define Q_DECL_HOT_FUNCTION
#endif
 
QT_BEGIN_NAMESPACE
 
// We assume that pointers and size_t have the same size. If that assumption should fail
// on a platform the code selecting the different methods below needs to be fixed.
static_assert(sizeof(size_t) == QT_POINTER_SIZE, "size_t and pointers have different size.");
 
namespace {
struct HashSeedStorage
{
    static constexpr int SeedCount = 2;
    QBasicAtomicInteger<quintptr> seeds[SeedCount] = { Q_BASIC_ATOMIC_INITIALIZER(0), Q_BASIC_ATOMIC_INITIALIZER(0) };
 
#if !QT_SUPPORTS_INIT_PRIORITY || defined(QT_BOOTSTRAPPED)
    constexpr HashSeedStorage() = default;
#else
    HashSeedStorage() { initialize(0); }
#endif
 
    enum State {
        OverriddenByEnvironment = -1,
        JustInitialized,
        AlreadyInitialized
    };
    struct StateResult {
        quintptr requestedSeed;
        State state;
    };
 
    StateResult state(int which = -1);
    Q_DECL_HOT_FUNCTION QHashSeed currentSeed(int which)
    {
        return { state(which).requestedSeed };
    }
 
    void resetSeed()
    {
        if (state().state < AlreadyInitialized)
            return;
 
        // update the public seed
        QRandomGenerator *generator = QRandomGenerator::system();
        seeds[0].storeRelaxed(sizeof(size_t) > sizeof(quint32)
                              ? generator->generate64() : generator->generate());
    }
 
    void clearSeed()
    {
        state();
        seeds[0].storeRelaxed(0);   // always write (smaller code)
    }
 
private:
    Q_DECL_COLD_FUNCTION Q_NEVER_INLINE StateResult initialize(int which) noexcept;
};
 
[[maybe_unused]] HashSeedStorage::StateResult HashSeedStorage::initialize(int which) noexcept
{
    StateResult result = { 0, OverriddenByEnvironment };
#ifdef QT_BOOTSTRAPPED
    Q_UNUSED(which);
    Q_UNREACHABLE_RETURN(result);
#else
    // can't use qEnvironmentVariableIntValue (reentrancy)
    const char *seedstr = getenv("QT_HASH_SEED");
    if (seedstr) {
        auto r = qstrntoll(seedstr, strlen(seedstr), 10);
        if (r.used > 0 && size_t(r.used) == strlen(seedstr)) {
            if (r.result) {
                // can't use qWarning here (reentrancy)
                fprintf(stderr, "QT_HASH_SEED: forced seed value is not 0; ignored.\n");
            }
 
            // we don't have to store to the seed, since it's pre-initialized by
            // the compiler to zero
            return result;
        }
    }
 
    // update the full seed
    auto x = qt_initial_random_value();
    for (int i = 0; i < SeedCount; ++i) {
        seeds[i].storeRelaxed(x.data[i]);
        if (which == i)
            result.requestedSeed = x.data[i];
    }
    result.state = JustInitialized;
    return result;
#endif
}
 
inline HashSeedStorage::StateResult HashSeedStorage::state(int which)
{
    constexpr quintptr BadSeed = quintptr(Q_UINT64_C(0x5555'5555'5555'5555));
    StateResult result = { BadSeed, AlreadyInitialized };
 
#if defined(QT_BOOTSTRAPPED)
    result = { 0, OverriddenByEnvironment };
#elif !QT_SUPPORTS_INIT_PRIORITY
    // dynamic initialization
    static auto once = [&]() {
        result = initialize(which);
        return true;
    }();
    Q_UNUSED(once);
#endif
 
    if (result.state == AlreadyInitialized && which >= 0)
        return { seeds[which].loadRelaxed(), AlreadyInitialized };
    return result;
}
} // unnamed namespace
 
/*
    The QHash seed itself.
*/
#ifdef Q_DECL_INIT_PRIORITY
Q_DECL_INIT_PRIORITY(05)
#else
Q_CONSTINIT
#endif
static HashSeedStorage qt_qhash_seed;
 
/*
 * Hashing for memory segments is based on the public domain MurmurHash2 by
 * Austin Appleby. See http://murmurhash.googlepages.com/
 */
#if QT_POINTER_SIZE == 4
Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
static inline uint murmurhash(const void *key, uint len, uint seed) noexcept
{
    // 'm' and 'r' are mixing constants generated offline.
    // They're not really 'magic', they just happen to work well.
 
    const unsigned int m = 0x5bd1e995;
    const int r = 24;
 
    // Initialize the hash to a 'random' value
 
    unsigned int h = seed ^ len;
 
    // Mix 4 bytes at a time into the hash
 
    const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
    const unsigned char *end = data + (len & ~3);
 
    while (data != end) {
        size_t k;
        memcpy(&k, data, sizeof(uint));
 
        k *= m;
        k ^= k >> r;
        k *= m;
 
        h *= m;
        h ^= k;
 
        data += 4;
    }
 
    // Handle the last few bytes of the input array
    len &= 3;
    if (len) {
        unsigned int k = 0;
        end += len;
 
        while (data != end) {
            k <<= 8;
            k |= *data;
            ++data;
        }
        h ^= k;
        h *= m;
    }
 
    // Do a few final mixes of the hash to ensure the last few
    // bytes are well-incorporated.
 
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;
 
    return h;
}
 
#else
Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
static inline uint64_t murmurhash(const void *key, uint64_t len, uint64_t seed) noexcept
{
    const uint64_t m = 0xc6a4a7935bd1e995ULL;
    const int r = 47;
 
    uint64_t h = seed ^ (len * m);
 
    const unsigned char *data = reinterpret_cast<const unsigned char *>(key);
    const unsigned char *end = data + (len & ~7ul);
 
    while (data != end) {
        uint64_t k;
        memcpy(&k, data, sizeof(uint64_t));
 
        k *= m;
        k ^= k >> r;
        k *= m;
 
        h ^= k;
        h *= m;
 
        data += 8;
    }
 
    len &= 7;
    if (len) {
        // handle the last few bytes of input
        size_t k = 0;
        end += len;
 
        while (data != end) {
            k <<= 8;
            k |= *data;
            ++data;
        }
        h ^= k;
        h *= m;
    }
 
    h ^= h >> r;
    h *= m;
    h ^= h >> r;
 
    return h;
}
 
#endif
 
#if QT_POINTER_SIZE == 8
// This is an inlined version of the SipHash implementation that is
// trying to avoid some memcpy's from uint64 to uint8[] and back.
//
 
// Use SipHash-1-2, which has similar performance characteristics as
// stablehash() above, instead of the SipHash-2-4 default
#define cROUNDS 1
#define dROUNDS 2
 
#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
 
#define SIPROUND                                                               \
  do {                                                                         \
    v0 += v1;                                                                  \
    v1 = ROTL(v1, 13);                                                         \
    v1 ^= v0;                                                                  \
    v0 = ROTL(v0, 32);                                                         \
    v2 += v3;                                                                  \
    v3 = ROTL(v3, 16);                                                         \
    v3 ^= v2;                                                                  \
    v0 += v3;                                                                  \
    v3 = ROTL(v3, 21);                                                         \
    v3 ^= v0;                                                                  \
    v2 += v1;                                                                  \
    v1 = ROTL(v1, 17);                                                         \
    v1 ^= v2;                                                                  \
    v2 = ROTL(v2, 32);                                                         \
  } while (0)
 
Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
static uint64_t siphash(const uint8_t *in, uint64_t inlen, uint64_t seed, uint64_t seed2)
{
    /* "somepseudorandomlygeneratedbytes" */
    uint64_t v0 = 0x736f6d6570736575ULL;
    uint64_t v1 = 0x646f72616e646f6dULL;
    uint64_t v2 = 0x6c7967656e657261ULL;
    uint64_t v3 = 0x7465646279746573ULL;
    uint64_t b;
    uint64_t k0 = seed;
    uint64_t k1 = seed2;
    int i;
    const uint8_t *end = in + (inlen & ~7ULL);
    const int left = inlen & 7;
    b = inlen << 56;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;
 
    for (; in != end; in += 8) {
        uint64_t m = qFromUnaligned<uint64_t>(in);
        v3 ^= m;
 
        for (i = 0; i < cROUNDS; ++i)
            SIPROUND;
 
        v0 ^= m;
    }
 
 
#if defined(Q_CC_GNU_ONLY) && Q_CC_GNU >= 700
    QT_WARNING_DISABLE_GCC("-Wimplicit-fallthrough")
#endif
    switch (left) {
    case 7:
        b |= ((uint64_t)in[6]) << 48;
    case 6:
        b |= ((uint64_t)in[5]) << 40;
    case 5:
        b |= ((uint64_t)in[4]) << 32;
    case 4:
        b |= ((uint64_t)in[3]) << 24;
    case 3:
        b |= ((uint64_t)in[2]) << 16;
    case 2:
        b |= ((uint64_t)in[1]) << 8;
    case 1:
        b |= ((uint64_t)in[0]);
        break;
    case 0:
        break;
    }
 
    v3 ^= b;
 
    for (i = 0; i < cROUNDS; ++i)
        SIPROUND;
 
    v0 ^= b;
 
    v2 ^= 0xff;
 
    for (i = 0; i < dROUNDS; ++i)
        SIPROUND;
 
    b = v0 ^ v1 ^ v2 ^ v3;
    return b;
}
#else
// This is a "SipHash" implementation adopted for 32bit platforms. It performs
// basically the same operations as the 64bit version using 4 byte at a time
// instead of 8.
//
// To make this work, we also need to change the constants for the mixing
// rotations in ROTL. We're simply using half of the 64bit constants, rounded up
// for odd numbers.
//
// For the v0-v4 constants, simply use the first four bytes of the 64 bit versions.
//
// Use SipHash-1-2, which has similar performance characteristics as
// stablehash() above, instead of the SipHash-2-4 default
#define cROUNDS 1
#define dROUNDS 2
 
#define ROTL(x, b) (uint32_t)(((x) << (b)) | ((x) >> (32 - (b))))
 
#define SIPROUND                                                               \
  do {                                                                         \
    v0 += v1;                                                                  \
    v1 = ROTL(v1, 7);                                                          \
    v1 ^= v0;                                                                  \
    v0 = ROTL(v0, 16);                                                         \
    v2 += v3;                                                                  \
    v3 = ROTL(v3, 8);                                                          \
    v3 ^= v2;                                                                  \
    v0 += v3;                                                                  \
    v3 = ROTL(v3, 11);                                                         \
    v3 ^= v0;                                                                  \
    v2 += v1;                                                                  \
    v1 = ROTL(v1, 9);                                                          \
    v1 ^= v2;                                                                  \
    v2 = ROTL(v2, 16);                                                         \
  } while (0)
 
Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
static uint siphash(const uint8_t *in, uint inlen, uint seed, uint seed2)
{
    /* "somepseudorandomlygeneratedbytes" */
    uint v0 = 0x736f6d65U;
    uint v1 = 0x646f7261U;
    uint v2 = 0x6c796765U;
    uint v3 = 0x74656462U;
    uint b;
    uint k0 = seed;
    uint k1 = seed2;
    int i;
    const uint8_t *end = in + (inlen & ~3ULL);
    const int left = inlen & 3;
    b = inlen << 24;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;
 
    for (; in != end; in += 4) {
        uint m = qFromUnaligned<uint>(in);
        v3 ^= m;
 
        for (i = 0; i < cROUNDS; ++i)
            SIPROUND;
 
        v0 ^= m;
    }
 
#if defined(Q_CC_GNU_ONLY) && Q_CC_GNU >= 700
    QT_WARNING_DISABLE_GCC("-Wimplicit-fallthrough")
#endif
    switch (left) {
    case 3:
        b |= ((uint)in[2]) << 16;
    case 2:
        b |= ((uint)in[1]) << 8;
    case 1:
        b |= ((uint)in[0]);
        break;
    case 0:
        break;
    }
 
    v3 ^= b;
 
    for (i = 0; i < cROUNDS; ++i)
        SIPROUND;
 
    v0 ^= b;
 
    v2 ^= 0xff;
 
    for (i = 0; i < dROUNDS; ++i)
        SIPROUND;
 
    b = v0 ^ v1 ^ v2 ^ v3;
    return b;
}
#endif
 
#if defined(__SANITIZE_ADDRESS__) || defined(__SANITIZE_THREAD__)  // GCC
#  define QHASH_AES_SANITIZER_BUILD
#elif __has_feature(address_sanitizer) || __has_feature(thread_sanitizer)  // Clang
#  define QHASH_AES_SANITIZER_BUILD
#endif
 
// When built with a sanitizer, aeshash() is rightfully reported to have a
// heap-buffer-overflow issue. However, we consider it to be safe in this
// specific case and overcome the problem by correctly discarding the
// out-of-range bits. To allow building the code with sanitizer,
// QHASH_AES_SANITIZER_BUILD is used to disable aeshash() usage.
#if QT_COMPILER_SUPPORTS_HERE(AES) && QT_COMPILER_SUPPORTS_HERE(SSE4_2) && \
    !defined(QHASH_AES_SANITIZER_BUILD)
#  define AESHASH
#  define QT_FUNCTION_TARGET_STRING_AES_AVX2    "avx2,aes"
#  define QT_FUNCTION_TARGET_STRING_AES_AVX512          \
    QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 ","   \
    QT_FUNCTION_TARGET_STRING_AES
#  define QT_FUNCTION_TARGET_STRING_VAES_AVX512         \
    QT_FUNCTION_TARGET_STRING_ARCH_SKYLAKE_AVX512 ","   \
    QT_FUNCTION_TARGET_STRING_VAES
#  undef QHASH_AES_SANITIZER_BUILD
#  if QT_POINTER_SIZE == 8
#    define mm_set1_epz     _mm_set1_epi64x
#    define mm_cvtsz_si128  _mm_cvtsi64_si128
#    define mm_cvtsi128_sz  _mm_cvtsi128_si64
#    define mm256_set1_epz  _mm256_set1_epi64x
#  else
#    define mm_set1_epz     _mm_set1_epi32
#    define mm_cvtsz_si128  _mm_cvtsi32_si128
#    define mm_cvtsi128_sz  _mm_cvtsi128_si32
#    define mm256_set1_epz  _mm256_set1_epi32
#  endif
 
namespace {
    // This is inspired by the algorithm in the Go language. See:
    // https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_amd64.s#L1105
    // https://github.com/golang/go/blob/01b6cf09fc9f272d9db3d30b4c93982f4911d120/src/runtime/asm_386.s#L908
    //
    // Even though we're using the AESENC instruction from the CPU, this code
    // is not encryption and this routine makes no claim to be
    // cryptographically secure. We're simply using the instruction that performs
    // the scrambling round (step 3 in [1]) because it's just very good at
    // spreading the bits around.
    //
    // [1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm
 
    // hash 16 bytes, running 3 scramble rounds of AES on itself (like label "final1")
    static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL
    hash16bytes(__m128i &state0, __m128i data)
    {
        state0 = _mm_xor_si128(state0, data);
        state0 = _mm_aesenc_si128(state0, state0);
        state0 = _mm_aesenc_si128(state0, state0);
        state0 = _mm_aesenc_si128(state0, state0);
    }
 
    // hash twice 16 bytes, running 2 scramble rounds of AES on itself
    static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL
    hash2x16bytes(__m128i &state0, __m128i &state1, const __m128i *src0, const __m128i *src1)
    {
        __m128i data0 = _mm_loadu_si128(src0);
        __m128i data1 = _mm_loadu_si128(src1);
        state0 = _mm_xor_si128(data0, state0);
        state1 = _mm_xor_si128(data1, state1);
        state0 = _mm_aesenc_si128(state0, state0);
        state1 = _mm_aesenc_si128(state1, state1);
        state0 = _mm_aesenc_si128(state0, state0);
        state1 = _mm_aesenc_si128(state1, state1);
    }
 
    struct AESHashSeed
    {
        __m128i state0;
        __m128i mseed2;
        AESHashSeed(size_t seed, size_t seed2) QT_FUNCTION_TARGET(AES);
        __m128i state1() const QT_FUNCTION_TARGET(AES);
        __m256i state0_256() const QT_FUNCTION_TARGET(AES_AVX2)
        { return _mm256_set_m128i(state1(), state0); }
    };
} // unnamed namespace
 
Q_ALWAYS_INLINE AESHashSeed::AESHashSeed(size_t seed, size_t seed2)
{
    __m128i mseed = mm_cvtsz_si128(seed);
    mseed2 = mm_set1_epz(seed2);
 
    // mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, 0, 0, 0 ]
    mseed = _mm_insert_epi16(mseed, short(seed), 4);
    // mseed (epi16) = [ seed, seed >> 16, seed >> 32, seed >> 48, len, len, len, len ]
    mseed = _mm_shufflehi_epi16(mseed, 0);
 
    // merge with the process-global seed
    __m128i key = _mm_xor_si128(mseed, mseed2);
 
    // scramble the key
    __m128i state0 = _mm_aesenc_si128(key, key);
    this->state0 = state0;
}
 
Q_ALWAYS_INLINE __m128i AESHashSeed::state1() const
{
    {
        // unlike the Go code, we don't have more per-process seed
        __m128i state1 = _mm_aesenc_si128(state0, mseed2);
        return state1;
    }
}
 
static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
aeshash128_16to32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend)
{
    {
        if (src + 1 < srcend) {
            // epilogue: between 16 and 31 bytes
            hash2x16bytes(state0, state1, src, srcend - 1);
        } else if (src != srcend) {
            // epilogue: between 1 and 16 bytes, overlap with the end
            __m128i data = _mm_loadu_si128(srcend - 1);
            hash16bytes(state0, data);
        }
 
        // combine results:
        state0 = _mm_xor_si128(state0, state1);
    }
 
    return mm_cvtsi128_sz(state0);
}
 
static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
aeshash128_lt16(__m128i state0, const uchar *p, size_t len)
{
    if (len) {
        // We're going to load 16 bytes and mask zero the part we don't care
        // (the hash of a short string is different from the hash of a longer
        // including NULLs at the end because the length is in the key)
        // WARNING: this may produce valgrind warnings, but it's safe
 
        constexpr quintptr PageSize = 4096;
        __m128i data;
 
        if ((quintptr(p) & (PageSize / 2)) == 0) {
            // lower half of the page:
            // load all 16 bytes and mask off the bytes past the end of the source
            static const qint8 maskarray[] = {
                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
                0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
            };
            __m128i mask = _mm_loadu_si128(reinterpret_cast<const __m128i *>(maskarray + 15 - len));
            data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(p));
            data = _mm_and_si128(data, mask);
        } else {
            // upper half of the page:
            // load 16 bytes ending at the data end, then shuffle them to the beginning
            static const qint8 shufflecontrol[] = {
                1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
            };
            __m128i control = _mm_loadu_si128(reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len));
            data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(p + len) - 1);
            data = _mm_shuffle_epi8(data, control);
        }
 
        hash16bytes(state0, data);
    }
    return mm_cvtsi128_sz(state0);
}
 
static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
aeshash128_ge32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend)
{
    // main loop: scramble two 16-byte blocks
    for ( ; src + 2 < srcend; src += 2)
        hash2x16bytes(state0, state1, src, src + 1);
 
    return aeshash128_16to32(state0, state1, src, srcend);
}
 
#  if QT_COMPILER_SUPPORTS_HERE(VAES)
static size_t QT_FUNCTION_TARGET(ARCH_ICL) QT_VECTORCALL
aeshash256_lt32_avx256(__m256i state0, const uchar *p, size_t len)
{
    __m128i state0_128 = _mm256_castsi256_si128(state0);
    if (len) {
        __mmask32 mask = _bzhi_u32(-1, unsigned(len));
        __m256i data = _mm256_maskz_loadu_epi8(mask, p);
        __m128i data0 = _mm256_castsi256_si128(data);
        if (len >= sizeof(__m128i)) {
            state0 = _mm256_xor_si256(state0, data);
            state0 = _mm256_aesenc_epi128(state0, state0);
            state0 = _mm256_aesenc_epi128(state0, state0);
            // we're XOR'ing the two halves so we skip the third AESENC
            // state0 = _mm256_aesenc_epi128(state0, state0);
 
            // XOR the two halves and extract
            __m128i low = _mm256_extracti128_si256(state0, 0);
            __m128i high = _mm256_extracti128_si256(state0, 1);
            state0_128 = _mm_xor_si128(low, high);
        } else {
            hash16bytes(state0_128, data0);
        }
    }
    return mm_cvtsi128_sz(state0_128);
}
 
static size_t QT_FUNCTION_TARGET(VAES) QT_VECTORCALL
aeshash256_ge32(__m256i state0, const uchar *p, size_t len)
{
    static const auto hash32bytes = [](__m256i &state0, __m256i data) QT_FUNCTION_TARGET(VAES) {
        state0 = _mm256_xor_si256(state0, data);
        state0 = _mm256_aesenc_epi128(state0, state0);
        state0 = _mm256_aesenc_epi128(state0, state0);
        state0 = _mm256_aesenc_epi128(state0, state0);
    };
 
    // hash twice 32 bytes, running 2 scramble rounds of AES on itself
    const auto hash2x32bytes = [](__m256i &state0, __m256i &state1, const __m256i *src0,
            const __m256i *src1) QT_FUNCTION_TARGET(VAES) {
        __m256i data0 = _mm256_loadu_si256(src0);
        __m256i data1 = _mm256_loadu_si256(src1);
        state0 = _mm256_xor_si256(data0, state0);
        state1 = _mm256_xor_si256(data1, state1);
        state0 = _mm256_aesenc_epi128(state0, state0);
        state1 = _mm256_aesenc_epi128(state1, state1);
        state0 = _mm256_aesenc_epi128(state0, state0);
        state1 = _mm256_aesenc_epi128(state1, state1);
    };
 
    const __m256i *src = reinterpret_cast<const __m256i *>(p);
    const __m256i *srcend = reinterpret_cast<const __m256i *>(p + len);
 
    __m256i state1 = _mm256_aesenc_epi128(state0, mm256_set1_epz(len));
 
    // main loop: scramble two 32-byte blocks
    for ( ; src + 2 < srcend; src += 2)
        hash2x32bytes(state0, state1, src, src + 1);
 
    if (src + 1 < srcend) {
        // epilogue: between 32 and 31 bytes
        hash2x32bytes(state0, state1, src, srcend - 1);
    } else if (src != srcend) {
        // epilogue: between 1 and 32 bytes, overlap with the end
        __m256i data = _mm256_loadu_si256(srcend - 1);
        hash32bytes(state0, data);
    }
 
    // combine results:
    state0 = _mm256_xor_si256(state0, state1);
 
    // XOR the two halves and extract
    __m128i low = _mm256_extracti128_si256(state0, 0);
    __m128i high = _mm256_extracti128_si256(state0, 1);
    return mm_cvtsi128_sz(_mm_xor_si128(low, high));
}
 
static size_t QT_FUNCTION_TARGET(VAES)
aeshash256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
{
    AESHashSeed state(seed, seed2);
    auto src = reinterpret_cast<const __m128i *>(p);
    const auto srcend = reinterpret_cast<const __m128i *>(p + len);
 
    if (len < sizeof(__m128i))
        return aeshash128_lt16(state.state0, p, len);
 
    if (len <= sizeof(__m256i))
        return aeshash128_16to32(state.state0, state.state1(), src, srcend);
 
    return aeshash256_ge32(state.state0_256(), p, len);
}
 
static size_t QT_FUNCTION_TARGET(VAES_AVX512)
aeshash256_avx256(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
{
    AESHashSeed state(seed, seed2);
    if (len <= sizeof(__m256i))
        return aeshash256_lt32_avx256(state.state0_256(), p, len);
 
    return aeshash256_ge32(state.state0_256(), p, len);
}
#  endif // VAES
 
static size_t QT_FUNCTION_TARGET(AES)
aeshash128(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
{
    AESHashSeed state(seed, seed2);
    auto src = reinterpret_cast<const __m128i *>(p);
    const auto srcend = reinterpret_cast<const __m128i *>(p + len);
 
    if (len < sizeof(__m128i))
        return aeshash128_lt16(state.state0, p, len);
 
    if (len <= sizeof(__m256i))
        return aeshash128_16to32(state.state0, state.state1(), src, srcend);
 
    return aeshash128_ge32(state.state0, state.state1(), src, srcend);
}
 
static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
{
#  if QT_COMPILER_SUPPORTS_HERE(VAES)
    if (qCpuHasFeature(VAES)) {
        if (qCpuHasFeature(AVX512VL))
            return aeshash256_avx256(p, len, seed, seed2);
        return aeshash256(p, len, seed, seed2);
    }
#  endif
    return aeshash128(p, len, seed, seed2);
}
#endif // x86 AESNI
 
#if defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(AES) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED)
QT_FUNCTION_TARGET(AES)
static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
{
    uint8x16_t key;
#  if QT_POINTER_SIZE == 8
    uint64x2_t vseed = vcombine_u64(vcreate_u64(seed), vcreate_u64(seed2));
    key = vreinterpretq_u8_u64(vseed);
#  else
 
    uint32x2_t vseed = vmov_n_u32(seed);
    vseed = vset_lane_u32(seed2, vseed, 1);
    key = vreinterpretq_u8_u32(vcombine_u32(vseed, vseed));
#  endif
 
    // Compared to x86 AES, ARM splits each round into two instructions
    // and includes the pre-xor instead of the post-xor.
    const auto hash16bytes = [](uint8x16_t &state0, uint8x16_t data) {
        auto state1 = state0;
        state0 = vaeseq_u8(state0, data);
        state0 = vaesmcq_u8(state0);
        auto state2 = state0;
        state0 = vaeseq_u8(state0, state1);
        state0 = vaesmcq_u8(state0);
        auto state3 = state0;
        state0 = vaeseq_u8(state0, state2);
        state0 = vaesmcq_u8(state0);
        state0 = veorq_u8(state0, state3);
    };
 
    uint8x16_t state0 = key;
 
    if (len < 8)
        goto lt8;
    if (len < 16)
        goto lt16;
    if (len < 32)
        goto lt32;
 
    // rounds of 32 bytes
    {
        // Make state1 = ~state0:
        uint8x16_t state1 = veorq_u8(state0, vdupq_n_u8(255));
 
        // do simplified rounds of 32 bytes: unlike the Go code, we only
        // scramble twice and we keep 256 bits of state
        const auto *e = p + len - 31;
        while (p < e) {
            uint8x16_t data0 = vld1q_u8(p);
            uint8x16_t data1 = vld1q_u8(p + 16);
            auto oldstate0 = state0;
            auto oldstate1 = state1;
            state0 = vaeseq_u8(state0, data0);
            state1 = vaeseq_u8(state1, data1);
            state0 = vaesmcq_u8(state0);
            state1 = vaesmcq_u8(state1);
            auto laststate0 = state0;
            auto laststate1 = state1;
            state0 = vaeseq_u8(state0, oldstate0);
            state1 = vaeseq_u8(state1, oldstate1);
            state0 = vaesmcq_u8(state0);
            state1 = vaesmcq_u8(state1);
            state0 = veorq_u8(state0, laststate0);
            state1 = veorq_u8(state1, laststate1);
            p += 32;
        }
        state0 = veorq_u8(state0, state1);
    }
    len &= 0x1f;
 
    // do we still have 16 or more bytes?
    if (len & 0x10) {
lt32:
        uint8x16_t data = vld1q_u8(p);
        hash16bytes(state0, data);
        p += 16;
    }
    len &= 0xf;
 
    if (len & 0x08) {
lt16:
        uint8x8_t data8 = vld1_u8(p);
        uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0));
        hash16bytes(state0, data);
        p += 8;
    }
    len &= 0x7;
 
lt8:
    if (len) {
        // load the last chunk of data
        // We're going to load 8 bytes and mask zero the part we don't care
        // (the hash of a short string is different from the hash of a longer
        // including NULLs at the end because the length is in the key)
        // WARNING: this may produce valgrind warnings, but it's safe
 
        uint8x8_t data8;
 
        if (Q_LIKELY(quintptr(p + 8) & 0xff8)) {
            // same page, we definitely can't fault:
            // load all 8 bytes and mask off the bytes past the end of the source
            static const qint8 maskarray[] = {
                -1, -1, -1, -1, -1, -1, -1,
                 0,  0,  0,  0,  0,  0,  0,
            };
            uint8x8_t mask = vld1_u8(reinterpret_cast<const quint8 *>(maskarray) + 7 - len);
            data8 = vld1_u8(p);
            data8 = vand_u8(data8, mask);
        } else {
            // too close to the end of the page, it could fault:
            // load 8 bytes ending at the data end, then shuffle them to the beginning
            static const qint8 shufflecontrol[] = {
                 1,  2,  3,  4,  5,  6,  7,
                -1, -1, -1, -1, -1, -1, -1,
            };
            uint8x8_t control = vld1_u8(reinterpret_cast<const quint8 *>(shufflecontrol) + 7 - len);
            data8 = vld1_u8(p - 8 + len);
            data8 = vtbl1_u8(data8, control);
        }
        uint8x16_t data = vcombine_u8(data8, vdup_n_u8(0));
        hash16bytes(state0, data);
    }
 
    // extract state0
#  if QT_POINTER_SIZE == 8
    return vgetq_lane_u64(vreinterpretq_u64_u8(state0), 0);
#  else
    return vgetq_lane_u32(vreinterpretq_u32_u8(state0), 0);
#  endif
}
#endif
 
size_t qHashBits(const void *p, size_t size, size_t seed) noexcept
{
#ifdef QT_BOOTSTRAPPED
    // the seed is always 0 in bootstrapped mode (no seed generation code),
    // so help the compiler do dead code elimination
    seed = 0;
#endif
    // mix in the length as a secondary seed. For seed == 0, seed2 must be
    // size, to match what we used to do prior to Qt 6.2.
    size_t seed2 = size;
    if (seed)
        seed2 = qt_qhash_seed.currentSeed(1);
#ifdef AESHASH
    if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
        return aeshash(reinterpret_cast<const uchar *>(p), size, seed, seed2);
#elif defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(AES) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED)
# if defined(Q_OS_LINUX)
    // Do specific runtime-only check as Yocto hard enables Crypto extension for
    // all armv8 configs
    if (seed && (qCpuFeatures() & CpuFeatureAES))
# else
    if (seed && qCpuHasFeature(AES))
# endif
        return aeshash(reinterpret_cast<const uchar *>(p), size, seed, seed2);
#endif
 
    if (size <= QT_POINTER_SIZE)
        return murmurhash(p, size, seed);
 
    return siphash(reinterpret_cast<const uchar *>(p), size, seed, seed2);
}
 
size_t qHash(QByteArrayView key, size_t seed) noexcept
{
    return qHashBits(key.constData(), size_t(key.size()), seed);
}
 
size_t qHash(QStringView key, size_t seed) noexcept
{
    return qHashBits(key.data(), key.size()*sizeof(QChar), seed);
}
 
size_t qHash(const QBitArray &bitArray, size_t seed) noexcept
{
    qsizetype m = bitArray.d.size() - 1;
    size_t result = qHashBits(reinterpret_cast<const uchar *>(bitArray.d.constData()), size_t(qMax(0, m)), seed);
 
    // deal with the last 0 to 7 bits manually, because we can't trust that
    // the padding is initialized to 0 in bitArray.d
    qsizetype n = bitArray.size();
    if (n & 0x7)
        result = ((result << 4) + bitArray.d.at(m)) & ((1 << n) - 1);
    return result;
}
 
size_t qHash(QLatin1StringView key, size_t seed) noexcept
{
    return qHashBits(reinterpret_cast<const uchar *>(key.data()), size_t(key.size()), seed);
}
 
QHashSeed QHashSeed::globalSeed() noexcept
{
    return qt_qhash_seed.currentSeed(0);
}
 
void QHashSeed::setDeterministicGlobalSeed()
{
    qt_qhash_seed.clearSeed();
}
 
void QHashSeed::resetRandomGlobalSeed()
{
    qt_qhash_seed.resetSeed();
}
 
#if QT_DEPRECATED_SINCE(6,6)
int qGlobalQHashSeed()
{
    return int(QHashSeed::globalSeed() & INT_MAX);
}
 
void qSetGlobalQHashSeed(int newSeed)
{
    if (Q_LIKELY(newSeed == 0 || newSeed == -1)) {
        if (newSeed == 0)
            QHashSeed::setDeterministicGlobalSeed();
        else
            QHashSeed::resetRandomGlobalSeed();
    } else {
        // can't use qWarning here (reentrancy)
        fprintf(stderr, "qSetGlobalQHashSeed: forced seed value is not 0; ignoring call\n");
    }
}
#endif  // QT_DEPRECATED_SINCE(6,6)
 
uint qt_hash(QStringView key, uint chained) noexcept
{
    auto n = key.size();
    auto p = key.utf16();
 
    uint h = chained;
 
    while (n--) {
        h = (h << 4) + *p++;
        h ^= (h & 0xf0000000) >> 23;
        h &= 0x0fffffff;
    }
    return h;
}
 
size_t qHash(double key, size_t seed) noexcept
{
    // ensure -0 gets mapped to 0
    key += 0.0;
    if constexpr (sizeof(double) == sizeof(size_t)) {
        size_t k;
        memcpy(&k, &key, sizeof(double));
        return QHashPrivate::hash(k, seed);
    } else {
        return murmurhash(&key, sizeof(key), seed);
    }
}
 
#if !defined(Q_OS_DARWIN) || defined(Q_QDOC)
size_t qHash(long double key, size_t seed) noexcept
{
    // ensure -0 gets mapped to 0
    key += static_cast<long double>(0.0);
    if constexpr (sizeof(long double) == sizeof(size_t)) {
        size_t k;
        memcpy(&k, &key, sizeof(long double));
        return QHashPrivate::hash(k, seed);
    } else {
        return murmurhash(&key, sizeof(key), seed);
    }
}
#endif
 
#ifdef QT_HAS_CONSTEXPR_BITOPS
namespace QHashPrivate {
static_assert(qPopulationCount(SpanConstants::NEntries) == 1,
        "NEntries must be a power of 2 for bucketForHash() to work.");
 
// ensure the size of a Span does not depend on the template parameters
using Node1 = Node<int, int>;
static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<char, void *>>));
static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<qsizetype, QHashDummyValue>>));
static_assert(sizeof(Span<Node1>) == sizeof(Span<Node<QString, QVariant>>));
static_assert(sizeof(Span<Node1>) > SpanConstants::NEntries);
static_assert(qNextPowerOfTwo(sizeof(Span<Node1>)) == SpanConstants::NEntries * 2);
 
// ensure allocations are always a power of two, at a minimum NEntries,
// obeying the fomula
//   qNextPowerOfTwo(2 * N);
// without overflowing
static constexpr size_t NEntries = SpanConstants::NEntries;
static_assert(GrowthPolicy::bucketsForCapacity(1) == NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(NEntries / 2 + 0) == NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(NEntries / 2 + 1) == 2 * NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 1 - 1) == 2 * NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 1 + 0) == 4 * NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 1 + 1) == 4 * NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 2 - 1) == 4 * NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(NEntries * 2 + 0) == 8 * NEntries);
static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 4) == SIZE_MAX / 2 + 1);
static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX / 2) == SIZE_MAX);
static_assert(GrowthPolicy::bucketsForCapacity(SIZE_MAX) == SIZE_MAX);
}
#endif
 
QT_END_NAMESPACE