xxhash.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: AGPL-3.0-or-later
// Copyright 2026 Johnson Ogundeji
#pragma once
 
 
#include <cstdint>
#include <cstring>
#include <string>
#include <type_traits>
 
namespace signet::forge {
 
namespace xxhash {
 
namespace detail {
 
static constexpr uint64_t PRIME1 = 0x9E3779B185EBCA87ULL; 
static constexpr uint64_t PRIME2 = 0xC2B2AE3D27D4EB4FULL; 
static constexpr uint64_t PRIME3 = 0x165667B19E3779F9ULL; 
static constexpr uint64_t PRIME4 = 0x85EBCA77C2B2AE63ULL; 
static constexpr uint64_t PRIME5 = 0x27D4EB2F165667C5ULL; 
 
// ---------------------------------------------------------------------------
// Helpers
// ---------------------------------------------------------------------------
 
inline constexpr uint64_t rotl64(uint64_t v, int r) {
    r &= 63; // guard against UB when r==0 or r>=64
    return (v << r) | (v >> ((64 - r) & 63));
}
 
inline uint64_t read_u64_le(const uint8_t* p) {
    uint64_t v;
    std::memcpy(&v, p, 8);
    // On big-endian platforms this would need a byte swap.
    // x86, x86_64, and ARM (little-endian mode) are fine.
#if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
    v = __builtin_bswap64(v);
#elif defined(_MSC_VER)
    // Portability: MSVC targets are always little-endian (x86/x64/ARM-LE),
    // so no byte-swap is needed. If MSVC ever targets a big-endian arch,
    // this branch must be revisited.
#elif !defined(__BYTE_ORDER__)
#  error "Cannot determine endianness — define __BYTE_ORDER__"
#endif
    return v;
}
 
inline uint32_t read_u32_le(const uint8_t* p) {
    uint32_t v;
    std::memcpy(&v, p, 4);
#if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
    v = __builtin_bswap32(v);
#elif defined(_MSC_VER)
    // Portability: MSVC targets are always little-endian (x86/x64/ARM-LE),
    // so no byte-swap is needed.
#elif !defined(__BYTE_ORDER__)
#  error "Cannot determine endianness — define __BYTE_ORDER__"
#endif
    return v;
}
 
// ---------------------------------------------------------------------------
// Core primitives
// ---------------------------------------------------------------------------
 
inline constexpr uint64_t round(uint64_t acc, uint64_t lane) {
    acc += lane * PRIME2;
    acc  = rotl64(acc, 31);
    acc *= PRIME1;
    return acc;
}
 
inline constexpr uint64_t merge_accumulator(uint64_t acc, uint64_t v) {
    acc ^= round(0, v);
    acc  = acc * PRIME1 + PRIME4;
    return acc;
}
 
inline constexpr uint64_t avalanche(uint64_t h) {
    h ^= h >> 33;
    h *= PRIME2;
    h ^= h >> 29;
    h *= PRIME3;
    h ^= h >> 32;
    return h;
}
 
} // namespace detail
 
// ---------------------------------------------------------------------------
// Public API
// ---------------------------------------------------------------------------
 
inline uint64_t hash64(const void* data, size_t length, uint64_t seed = 0) {
    using namespace detail;
 
    const auto* p   = static_cast<const uint8_t*>(data);
    const auto* end = p + length;
 
    uint64_t h;
 
    if (length >= 32) {
        // -----------------------------------------------------------------
        // Step 1: Initialize four accumulators
        // -----------------------------------------------------------------
        uint64_t v1 = seed + PRIME1 + PRIME2;
        uint64_t v2 = seed + PRIME2;
        uint64_t v3 = seed;
        uint64_t v4 = seed - PRIME1;
 
        // -----------------------------------------------------------------
        // Step 2: Process 32-byte stripes
        // -----------------------------------------------------------------
        const auto* stripe_end = end - 31;  // ensure at least 32 bytes remain
        do {
            v1 = round(v1, read_u64_le(p));      p += 8;
            v2 = round(v2, read_u64_le(p));      p += 8;
            v3 = round(v3, read_u64_le(p));      p += 8;
            v4 = round(v4, read_u64_le(p));      p += 8;
        } while (p < stripe_end);
 
        // -----------------------------------------------------------------
        // Step 3: Converge four accumulators into one
        // -----------------------------------------------------------------
        h = rotl64(v1,  1) +
            rotl64(v2,  7) +
            rotl64(v3, 12) +
            rotl64(v4, 18);
 
        h = merge_accumulator(h, v1);
        h = merge_accumulator(h, v2);
        h = merge_accumulator(h, v3);
        h = merge_accumulator(h, v4);
    } else {
        // -----------------------------------------------------------------
        // Small input (< 32 bytes): single accumulator
        // -----------------------------------------------------------------
        h = seed + PRIME5;
    }
 
    // -----------------------------------------------------------------
    // Step 4: Add total input length
    // -----------------------------------------------------------------
    h += static_cast<uint64_t>(length);
 
    // -----------------------------------------------------------------
    // Step 5: Consume remaining bytes
    // -----------------------------------------------------------------
 
    // Process remaining 8-byte chunks
    while (p + 8 <= end) {
        uint64_t lane = read_u64_le(p);
        h ^= round(0, lane);
        h  = rotl64(h, 27) * PRIME1 + PRIME4;
        p += 8;
    }
 
    // Process a remaining 4-byte chunk
    if (p + 4 <= end) {
        uint64_t lane = static_cast<uint64_t>(read_u32_le(p));
        h ^= lane * PRIME1;
        h  = rotl64(h, 23) * PRIME2 + PRIME3;
        p += 4;
    }
 
    // Process remaining 1-byte chunks
    while (p < end) {
        uint64_t lane = static_cast<uint64_t>(*p);
        h ^= lane * PRIME5;
        h  = rotl64(h, 11) * PRIME1;
        p += 1;
    }
 
    // -----------------------------------------------------------------
    // Step 6: Avalanche / finalization
    // -----------------------------------------------------------------
    return avalanche(h);
}
 
inline uint64_t hash64(const std::string& s, uint64_t seed = 0) {
    return hash64(s.data(), s.size(), seed);
}
 
template <typename T>
inline uint64_t hash64_value(const T& val, uint64_t seed = 0) {
    static_assert(std::is_trivially_copyable_v<T>,
                  "hash64_value requires a trivially-copyable type");
    return hash64(&val, sizeof(T), seed);
}
 
} // namespace xxhash
} // namespace signet::forge