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>.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/
 
// 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>
#endif // QT_BOOTSTRAPPED
 
#include <array>
#include <limits.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) };
 
    constexpr HashSeedStorage() = default;
 
    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]] static void ensureConstexprConstructibility()
    {
        static_assert(std::is_trivially_destructible_v<HashSeedStorage>);
        static constexpr HashSeedStorage dummy {};
        Q_UNUSED(dummy);
    }
};
 
[[maybe_unused]] HashSeedStorage::StateResult HashSeedStorage::initialize(int which) noexcept
{
    StateResult result = { 0, OverriddenByEnvironment };
    bool ok;
    int seed = qEnvironmentVariableIntValue("QT_HASH_SEED", &ok);
    if (ok) {
        if (seed) {
            // 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;
}
 
inline HashSeedStorage::StateResult HashSeedStorage::state(int which)
{
    constexpr quintptr BadSeed = quintptr(Q_UINT64_C(0x5555'5555'5555'5555));
    StateResult result = { BadSeed, AlreadyInitialized };
 
#ifndef QT_BOOTSTRAPPED
    static auto once = [&]() {
        result = initialize(which);
        return true;
    }();
    Q_UNUSED(once);
#else
    result = { 0, OverriddenByEnvironment };
#endif
 
    if (result.state == AlreadyInitialized && which >= 0)
        return { seeds[which].loadRelaxed(), AlreadyInitialized };
    return result;
}
} // unnamed namespace
 
/*
    The QHash seed itself.
*/
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
 
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
 
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)
 
 
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)
 
 
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
 
#undef QHASH_AES_SANITIZER_BUILD
 
QT_FUNCTION_TARGET(AES)
static size_t aeshash(const uchar *p, size_t len, size_t seed, size_t seed2) noexcept
{
    // 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")
    const auto hash16bytes = [](__m128i &state0, __m128i data) QT_FUNCTION_TARGET(AES) {
        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
    const auto hash2x16bytes = [](__m128i &state0, __m128i &state1, const __m128i *src0,
            const __m128i *src1) QT_FUNCTION_TARGET(AES) {
        __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);
    };
 
    __m128i mseed, mseed2;
    if (sizeof(size_t) == 8) {
#ifdef Q_PROCESSOR_X86_64
        mseed = _mm_cvtsi64_si128(seed);
        mseed2 = _mm_set1_epi64x(seed2);
#endif
    } else {
        mseed = _mm_cvtsi32_si128(int(seed));
        mseed2 = _mm_set1_epi32(int(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);
 
    auto src = reinterpret_cast<const __m128i *>(p);
    if (len >= sizeof(__m128i)) {
        // unlike the Go code, we don't have more per-process seed
        __m128i state1 = _mm_aesenc_si128(state0, mseed2);
 
        const auto srcend = reinterpret_cast<const __m128i *>(p + len);
 
        // main loop: scramble two 16-byte blocks
        for ( ; src + 2 < srcend; src += 2)
            hash2x16bytes(state0, state1, src, src + 1);
 
        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);
    } else 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(src) & (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(src);
            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);
    }
 
    // extract state0
#  if QT_POINTER_SIZE == 8
    return _mm_cvtsi128_si64(state0);
#  else
    return _mm_cvtsi128_si32(state0);
#  endif
}
#endif
 
#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(const QByteArray &key, size_t seed) noexcept
{
    return qHashBits(key.constData(), size_t(key.size()), seed);
}
 
size_t qHash(const 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(QLatin1String 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_CLANG_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
 
QT_END_NAMESPACE