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
 
void qt_from_latin1(char16_t *dst, const char *str, size_t size) noexcept;  // qstring.cpp
 
// 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()
    {
#ifndef QT_BOOTSTRAPPED
        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());
#endif
    }
 
    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
 
namespace {
// This is an inlined version of the SipHash implementation that is
// trying to avoid some memcpy's from uint64 to uint8[] and back.
 
#define ROTL(x, b) (((x) << (b)) | ((x) >> (sizeof(x) * 8 - (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)
 
template <int cROUNDS = 2, int dROUNDS = 4> struct SipHash64
{
    /* "somepseudorandomlygeneratedbytes" */
    uint64_t v0 = 0x736f6d6570736575ULL;
    uint64_t v1 = 0x646f72616e646f6dULL;
    uint64_t v2 = 0x6c7967656e657261ULL;
    uint64_t v3 = 0x7465646279746573ULL;
    uint64_t b;
    uint64_t k0;
    uint64_t k1;
 
    inline SipHash64(uint64_t fulllen, uint64_t seed, uint64_t seed2);
    inline void addBlock(const uint8_t *in, size_t inlen);
    inline uint64_t finalize(const uint8_t *in, size_t left);
};
 
template <int cROUNDS, int dROUNDS>
SipHash64<cROUNDS, dROUNDS>::SipHash64(uint64_t inlen, uint64_t seed, uint64_t seed2)
{
    b = inlen << 56;
    k0 = seed;
    k1 = seed2;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;
}
 
template <int cROUNDS, int dROUNDS> Q_DECL_HOT_FUNCTION void
SipHash64<cROUNDS, dROUNDS>::addBlock(const uint8_t *in, size_t inlen)
{
    Q_ASSERT((inlen & 7ULL) == 0);
    int i;
    const uint8_t *end = in + inlen;
    for (; in != end; in += 8) {
        uint64_t m = qFromUnaligned<uint64_t>(in);
        v3 ^= m;
 
        for (i = 0; i < cROUNDS; ++i)
            SIPROUND;
 
        v0 ^= m;
    }
}
 
template <int cROUNDS, int dROUNDS> Q_DECL_HOT_FUNCTION uint64_t
SipHash64<cROUNDS, dROUNDS>::finalize(const uint8_t *in, size_t left)
{
    int i;
    switch (left) {
    case 7:
        b |= ((uint64_t)in[6]) << 48;
        Q_FALLTHROUGH();
    case 6:
        b |= ((uint64_t)in[5]) << 40;
        Q_FALLTHROUGH();
    case 5:
        b |= ((uint64_t)in[4]) << 32;
        Q_FALLTHROUGH();
    case 4:
        b |= ((uint64_t)in[3]) << 24;
        Q_FALLTHROUGH();
    case 3:
        b |= ((uint64_t)in[2]) << 16;
        Q_FALLTHROUGH();
    case 2:
        b |= ((uint64_t)in[1]) << 8;
        Q_FALLTHROUGH();
    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;
}
#undef SIPROUND
 
// 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.
//
 
#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)
 
template <int cROUNDS = 2, int dROUNDS = 4> struct SipHash32
{
    /* "somepseudorandomlygeneratedbytes" */
    uint v0 = 0x736f6d65U;
    uint v1 = 0x646f7261U;
    uint v2 = 0x6c796765U;
    uint v3 = 0x74656462U;
    uint b;
    uint k0;
    uint k1;
 
    inline SipHash32(size_t fulllen, uint seed, uint seed2);
    inline void addBlock(const uint8_t *in, size_t inlen);
    inline uint finalize(const uint8_t *in, size_t left);
};
 
template <int cROUNDS, int dROUNDS> inline
SipHash32<cROUNDS, dROUNDS>::SipHash32(size_t inlen, uint seed, uint seed2)
{
    uint k0 = seed;
    uint k1 = seed2;
    b = inlen << 24;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;
}
 
template <int cROUNDS, int dROUNDS> inline Q_DECL_HOT_FUNCTION void
SipHash32<cROUNDS, dROUNDS>::addBlock(const uint8_t *in, size_t inlen)
{
    Q_ASSERT((inlen & 3ULL) == 0);
    int i;
    const uint8_t *end = in + inlen;
    for (; in != end; in += 4) {
        uint m = qFromUnaligned<uint>(in);
        v3 ^= m;
 
        for (i = 0; i < cROUNDS; ++i)
            SIPROUND;
 
        v0 ^= m;
    }
}
 
template <int cROUNDS, int dROUNDS> inline Q_DECL_HOT_FUNCTION uint
SipHash32<cROUNDS, dROUNDS>::finalize(const uint8_t *in, size_t left)
{
    int i;
    switch (left) {
    case 3:
        b |= ((uint)in[2]) << 16;
        Q_FALLTHROUGH();
    case 2:
        b |= ((uint)in[1]) << 8;
        Q_FALLTHROUGH();
    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;
}
#undef SIPROUND
#undef ROTL
 
// Use SipHash-1-2, which has similar performance characteristics as
// stablehash() above, instead of the SipHash-2-4 default
template <int cROUNDS = 1, int dROUNDS = 2>
using SipHash = std::conditional_t<sizeof(void *) == 8,
        SipHash64<cROUNDS, dROUNDS>, SipHash32<cROUNDS, dROUNDS>>;
} // unnamed namespace
 
Q_NEVER_INLINE Q_DECL_HOT_FUNCTION
static size_t siphash(const uint8_t *in, size_t inlen, size_t seed, size_t seed2)
{
    constexpr size_t TailSizeMask = sizeof(void *) - 1;
    SipHash<> hasher(inlen, seed, seed2);
    hasher.addBlock(in, inlen & ~TailSizeMask);
    return hasher.finalize(in + (inlen & ~TailSizeMask), inlen & TailSizeMask);
}
 
enum ZeroExtension {
    None = 0,
    ByteToWord = 1,
};
 
template <ZeroExtension = None> static size_t
qHashBits_fallback(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept;
template <> size_t qHashBits_fallback<None>(const uchar *p, size_t size, size_t seed, size_t seed2) noexcept
{
    if (size <= QT_POINTER_SIZE)
        return murmurhash(p, size, seed);
 
    return siphash(reinterpret_cast<const uchar *>(p), size, seed, seed2);
}
 
template <> size_t qHashBits_fallback<ByteToWord>(const uchar *data, size_t size, size_t seed, size_t seed2) noexcept
{
    auto quick_from_latin1 = [](char16_t *dest, const uchar *data, size_t size) {
        // Quick, "inlined" version for very short blocks
        std::copy_n(data, size, dest);
    };
    if (size <= QT_POINTER_SIZE / 2) {
        std::array<char16_t, QT_POINTER_SIZE / 2> buf;
        quick_from_latin1(buf.data(), data, size);
        return murmurhash(buf.data(), size * 2, seed);
    }
 
    constexpr size_t TailSizeMask = sizeof(void *) / 2 - 1;
    std::array<char16_t, 256> buf;
    SipHash<> siphash(size * 2, seed, seed2);
    ptrdiff_t offset = 0;
    for ( ; offset + buf.size() < size; offset += buf.size()) {
        qt_from_latin1(buf.data(), reinterpret_cast<const char *>(data) + offset, buf.size());
        siphash.addBlock(reinterpret_cast<uint8_t *>(buf.data()), sizeof(buf));
    }
    if (size_t n = size - offset; n > TailSizeMask) {
        n &= ~TailSizeMask;
        qt_from_latin1(buf.data(), reinterpret_cast<const char *>(data) + offset, n);
        siphash.addBlock(reinterpret_cast<uint8_t *>(buf.data()), n * 2);
        offset += n;
    }
 
    quick_from_latin1(buf.data(), data + offset, size - offset);
    return siphash.finalize(reinterpret_cast<uint8_t *>(buf.data()), (size - offset) * 2);
}
 
#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.
    //
    // Note on Latin-1 hashing (ZX == ByteToWord): for simplicity of the
    // algorithm, we pass sizes equivalent to the UTF-16 content (ZX == None).
    // That means we must multiply by 2 on entry, divide by 2 on pointer
    // advancing, and load half as much data from memory (though we produce
    // exactly as much data in registers). The compilers appear to optimize
    // this out.
    //
    // [1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#High-level_description_of_the_algorithm
 
    template <ZeroExtension ZX, typename T> static const T *advance(const T *ptr, ptrdiff_t n)
    {
        if constexpr (ZX == None)
            return ptr + n;
 
        // see note above on ZX == ByteToWord hashing
        auto p = reinterpret_cast<const uchar *>(ptr);
        n *= sizeof(T);
        return reinterpret_cast<const T *>(p + n/2);
    }
 
    template <ZeroExtension> static __m128i loadu128(const void *ptr);
    template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<None>(const void *ptr)
    {
        return _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr));
    }
    template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(AES) __m128i loadu128<ByteToWord>(const void *ptr)
    {
        // use a MOVQ followed by PMOVZXBW
        // the compiler usually combines them as a single, loading PMOVZXBW
        __m128i data = _mm_loadl_epi64(static_cast<const __m128i *>(ptr));
        return _mm_cvtepu8_epi16(data);
    }
 
    // hash 16 bytes, running 3 scramble rounds of AES on itself (like label "final1")
    static void Q_ALWAYS_INLINE 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
    template <ZeroExtension ZX>
    static void QT_FUNCTION_TARGET(AES) QT_VECTORCALL
    hash2x16bytes(__m128i &state0, __m128i &state1, const __m128i *src0, const __m128i *src1)
    {
        __m128i data0 = loadu128<ZX>(src0);
        __m128i data1 = loadu128<ZX>(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;
    }
}
 
template <ZeroExtension ZX>
static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
aeshash128_16to32(__m128i state0, __m128i state1, const __m128i *src, const __m128i *srcend)
{
    {
        const __m128i *src2 = advance<ZX>(srcend, -1);
        if (advance<ZX>(src, 1) < srcend) {
            // epilogue: between 16 and 31 bytes
            hash2x16bytes<ZX>(state0, state1, src, src2);
        } else if (src != srcend) {
            // epilogue: between 1 and 16 bytes, overlap with the end
            __m128i data = loadu128<ZX>(src2);
            hash16bytes(state0, data);
        }
 
        // combine results:
        state0 = _mm_xor_si128(state0, state1);
    }
 
    return mm_cvtsi128_sz(state0);
}
 
// 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,
};
 
// 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
};
 
template <ZeroExtension ZX>
static size_t QT_FUNCTION_TARGET(AES) QT_VECTORCALL
aeshash128_lt16(__m128i state0, const __m128i *src, const __m128i *srcend, 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 CachelineSize = 64;
        __m128i data;
 
        if ((quintptr(src) & (CachelineSize / 2)) == 0) {
            // lower half of the cacheline:
            __m128i mask = _mm_loadu_si128(reinterpret_cast<const __m128i *>(maskarray + 15 - len));
            data = loadu128<ZX>(src);
            data = _mm_and_si128(data, mask);
        } else {
            // upper half of the cacheline:
            __m128i control = _mm_loadu_si128(reinterpret_cast<const __m128i *>(shufflecontrol + 15 - len));
            data = loadu128<ZX>(advance<ZX>(srcend, -1));
            data = _mm_shuffle_epi8(data, control);
        }
 
        hash16bytes(state0, data);
    }
    return mm_cvtsi128_sz(state0);
}
 
template <ZeroExtension ZX>
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 ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2))
        hash2x16bytes<ZX>(state0, state1, src, advance<ZX>(src, 1));
 
    return aeshash128_16to32<ZX>(state0, state1, src, srcend);
}
 
#  if QT_COMPILER_SUPPORTS_HERE(VAES)
template <ZeroExtension> static __m256i loadu256(const void *ptr);
template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<None>(const void *ptr)
{
    return _mm256_loadu_si256(reinterpret_cast<const __m256i *>(ptr));
}
template <> Q_ALWAYS_INLINE QT_FUNCTION_TARGET(VAES) __m256i loadu256<ByteToWord>(const void *ptr)
{
    // VPMOVZXBW xmm, ymm
    __m128i data = _mm_loadu_si128(reinterpret_cast<const __m128i *>(ptr));
    return _mm256_cvtepu8_epi16(data);
}
 
template <ZeroExtension ZX>
static size_t QT_FUNCTION_TARGET(VAES_AVX512) QT_VECTORCALL
aeshash256_lt32_avx256(__m256i state0, const uchar *p, size_t len)
{
    __m128i state0_128 = _mm256_castsi256_si128(state0);
    if (len) {
        __m256i data;
        if constexpr (ZX == None) {
            __mmask32 mask = _bzhi_u32(-1, unsigned(len));
            data = _mm256_maskz_loadu_epi8(mask, p);
        } else {
            __mmask16 mask = _bzhi_u32(-1, unsigned(len) / 2);
            __m128i data0 = _mm_maskz_loadu_epi8(mask, p);
            data = _mm256_cvtepu8_epi16(data0);
        }
        __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);
}
 
template <ZeroExtension ZX>
static size_t QT_FUNCTION_TARGET(VAES) QT_VECTORCALL
aeshash256_ge32(__m256i state0, const __m128i *s, const __m128i *end, 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 void *src0,
            const void *src1) QT_FUNCTION_TARGET(VAES) {
        __m256i data0 = loadu256<ZX>(src0);
        __m256i data1 = loadu256<ZX>(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 *>(s);
    const __m256i *srcend = reinterpret_cast<const __m256i *>(end);
 
    __m256i state1 = _mm256_aesenc_epi128(state0, mm256_set1_epz(len));
 
    // main loop: scramble two 32-byte blocks
    for ( ; advance<ZX>(src, 2) < srcend; src = advance<ZX>(src, 2))
        hash2x32bytes(state0, state1, src, advance<ZX>(src, 1));
 
    const __m256i *src2 = advance<ZX>(srcend, -1);
    if (advance<ZX>(src, 1) < srcend) {
        // epilogue: between 32 and 31 bytes
        hash2x32bytes(state0, state1, src, src2);
    } else if (src != srcend) {
        // epilogue: between 1 and 32 bytes, overlap with the end
        __m256i data = loadu256<ZX>(src2);
        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));
}
 
template <ZeroExtension ZX>
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 *>(advance<ZX>(p, len));
 
    if (len < sizeof(__m128i))
        return aeshash128_lt16<ZX>(state.state0, src, srcend, len);
 
    if (len <= sizeof(__m256i))
        return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend);
 
    return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len);
}
 
template <ZeroExtension ZX>
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);
    auto src = reinterpret_cast<const __m128i *>(p);
    const auto srcend = reinterpret_cast<const __m128i *>(advance<ZX>(p, len));
 
    if (len <= sizeof(__m256i))
        return aeshash256_lt32_avx256<ZX>(state.state0_256(), p, len);
 
    return aeshash256_ge32<ZX>(state.state0_256(), src, srcend, len);
}
#  endif // VAES
 
template <ZeroExtension ZX>
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 *>(advance<ZX>(p, len));
 
    if (len < sizeof(__m128i))
        return aeshash128_lt16<ZX>(state.state0, src, srcend, len);
 
    if (len <= sizeof(__m256i))
        return aeshash128_16to32<ZX>(state.state0, state.state1(), src, srcend);
 
    return aeshash128_ge32<ZX>(state.state0, state.state1(), src, srcend);
}
 
template <ZeroExtension ZX = None>
static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
{
    if constexpr (ZX == ByteToWord)
        len *= 2;           // see note above on ZX == ByteToWord hashing
 
#  if QT_COMPILER_SUPPORTS_HERE(VAES)
    if (qCpuHasFeature(VAES)) {
        if (qCpuHasFeature(AVX512VL))
            return aeshash256_avx256<ZX>(p, len, seed, seed2);
        return aeshash256<ZX>(p, len, seed, seed2);
    }
#  endif
    return aeshash128<ZX>(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);
 
    auto data = reinterpret_cast<const uchar *>(p);
#ifdef AESHASH
    if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
        return aeshash(data, size, seed, seed2);
#elif defined(Q_PROCESSOR_ARM) && QT_COMPILER_SUPPORTS_HERE(AES) && !defined(QHASH_AES_SANITIZER_BUILD) && !defined(QT_BOOTSTRAPPED)
    if (seed && qCpuHasFeature(AES))
        return aeshash(data, size, seed, seed2);
#endif
 
    return qHashBits_fallback<>(data, 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);
}
 
#ifndef QT_BOOTSTRAPPED
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;
}
#endif
 
size_t qHash(QLatin1StringView key, 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
 
    auto data = reinterpret_cast<const uchar *>(key.data());
    size_t size = key.size();
 
    // Mix in the length as a secondary seed.
    // Multiplied by 2 to match the byte size of the equiavlent UTF-16 string.
    size_t seed2 = size * 2;
    if (seed)
        seed2 = qt_qhash_seed.currentSeed(1);
 
#if defined(AESHASH)
    if (seed && qCpuHasFeature(AES) && qCpuHasFeature(SSE4_2))
        return aeshash<ByteToWord>(data, size, seed, seed2);
#endif
    return qHashBits_fallback<ByteToWord>(data, size, seed, seed2);
}
 
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);
    }
}
 
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);
    }
}
 
 
 
#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