Xxhash: C++20 compile-time XXH32() calculation

[t-mat]

This is not an issue. Just for sharing my experiment. The following post demonstrates compile-time XXH32() hash calculation in C++20 and its constexpr.

But if you want to use compile-time xxHash now, please take a look at @ekpyron's excellent C++11 implementation of compile-time XXH64(). It's better than my code in many aspects.

[t-mat]

What's this?

This code demonstrates compile-time XXH32 hash calculation in C++20.

• It calculates hash value of the string "xxHash - Extremely Fast Hash algorithm".
• It also check expected hash value by genuine XXH32() when you define INCLUDE_XXHASH.

What's the point of this code?

When hash value becomes compile-time constant:

• You can use it more freely.
  
  
  
  • For example, using within case label, static_assert() expression, etc.
  
  
  • if constexpr () is also useful.
  
  
• Hash calculation code disappears. See the result at Compiler Explorer.

Since C++17/20 relaxed many restriction of constexpr, this code is a naive version of XXH32().

So my point is, it's always nice to have naive/simple version of the code for clarity and testing.
It also will encourage other developers to implmenent the algorithm in different form and language.

See also

• https://github.com/ekpyron/xxhashct

[t-mat]

The code and result

Code, result and disassembly at Compiler Explorer

• https://godbolt.org/z/bGv7Mh

gist version of the code for convenience

• https://gist.github.com/t-mat/9a7d258324079fd4307b3698b4d109eb

Prerequisites

• C++20 compatible compilers
  
  
  
  • g++ (10.x, aka g++-10)
  
  
  • clang (10.x)
  
  
  • VC++2019 (19.28.x)
  
  

Code

// C++20 Compile-time XXH32()
//
// g++-10 (10.2.0)          g++-10 -std=c++20 -DINCLUDE_XXHASH ./cxx20_ct_xxhash.cpp
// Clang (10.0.0)           clang  -std=c++20 -DINCLUDE_XXHASH ./cxx20_ct_xxhash.cpp
// Visual C++ 2019 (19.28)  cl /std:c++latest /DINCLUDE_XXHASH .\cxx20_ct_xxhash.cpp
//
// Result at Compiler Explorer
// https://godbolt.org/z/bGv7Mh

#include <stdio.h>  // printf()
#include <stdint.h> // uint8_t, uint32_t
#include <bit>      // std::rotl() ( https://en.cppreference.com/w/cpp/numeric/rotl )

// "private" utility functions
namespace compiletime_xxhash::detail {
    constexpr uint32_t rotl(uint32_t v, int x) {
        return std::rotl(v, x);
    }

    constexpr uint8_t read_u8(const char* input, int pos) {
        return static_cast<uint8_t>(input[pos]);
    }

    constexpr uint32_t read_u32le(const char* input, int pos) {
        const uint32_t b0 = read_u8(input, pos + 0);
        const uint32_t b1 = read_u8(input, pos + 1);
        const uint32_t b2 = read_u8(input, pos + 2);
        const uint32_t b3 = read_u8(input, pos + 3);
        return b0 | (b1 << 8) | (b2 << 16) | (b3 << 24);
    }
}

// "private" XXH32 functions
namespace compiletime_xxhash::detail::xxh32 {
    constexpr uint32_t prime32_1 = 0x9E3779B1U;
    constexpr uint32_t prime32_2 = 0x85EBCA77U;
    constexpr uint32_t prime32_3 = 0xC2B2AE3DU;
    constexpr uint32_t prime32_4 = 0x27D4EB2FU;
    constexpr uint32_t prime32_5 = 0x165667B1U;

    constexpr uint32_t xxh32_avalanche(uint32_t h32) {
        h32 ^= h32 >> 15;
        h32 *= prime32_2;
        h32 ^= h32 >> 13;
        h32 *= prime32_3;
        h32 ^= h32 >> 16;
        return h32;
    }

    constexpr uint32_t xxh32_finalize(const char* input, int inputLen, int pos, uint32_t h32) {
        // XXH_PROCESS4
        while((inputLen - pos) >= 4) {
            h32 += read_u32le(input, pos) * prime32_3;
            h32 = rotl(h32, 17) * prime32_4;
            pos += 4;
        }
        // XXH_PROCESS1
        while((inputLen - pos) > 0) {
            h32 += read_u8(input, pos) * prime32_5;
            h32 = rotl(h32, 11) * prime32_1;
            pos += 1;
        }
        return h32;
    }

    constexpr uint32_t xxh32_digest(
        const char* input, int inputLen, int pos,
        uint32_t v1, uint32_t v2, uint32_t v3, uint32_t v4
    ) {
        uint32_t h32 = 0;
        if(inputLen >= 16) {
            h32 = rotl(v1, 1) + rotl(v2, 7) + rotl(v3, 12) + rotl(v4, 18);
        } else {
            h32 = v3 + prime32_5;
        }
        h32 += inputLen;
        h32 = xxh32_finalize(input, inputLen, pos, h32);
        return xxh32_avalanche(h32);
    }

    constexpr uint32_t xxh32_round(uint32_t acc, const char* input, int pos) {
        const uint32_t d = read_u32le(input, pos);
        acc += d * prime32_2;
        acc = rotl(acc, 13) * prime32_1;
        return acc;
    }

    constexpr uint32_t xxh32(const char* input, int inputLen, uint32_t seed) {
        uint32_t v1 = seed + prime32_1 + prime32_2;
        uint32_t v2 = seed + prime32_2;
        uint32_t v3 = seed;
        uint32_t v4 = seed - prime32_1;
        int pos = 0;
        while(pos+16 <= inputLen) {
            v1 = xxh32_round(v1, input, pos + 0*4);
            v2 = xxh32_round(v2, input, pos + 1*4);
            v3 = xxh32_round(v3, input, pos + 2*4);
            v4 = xxh32_round(v4, input, pos + 3*4);
            pos += 16;
        }
        return xxh32_digest(input, inputLen, pos, v1, v2, v3, v4);
    }
}

// "public" function
namespace compiletime_xxhash {
    constexpr uint32_t xxh32(const char* input, int inputLen, uint32_t seed) {
        return detail::xxh32::xxh32(input, inputLen, seed);
    }
}

constexpr int compiletime_strlen(const char* input) {
    int i = 0;
    while(input[i] != 0) { ++i; }
    return i;
}

#if defined(INCLUDE_XXHASH)
#  define XXH_INLINE_ALL
#  include "./xxHash/xxhash.h"  // XXH32()
#endif

int main() {
    constexpr const char* input = "xxHash - Extremely Fast Hash algorithm";
    constexpr const int inputLen = compiletime_strlen(input);
    constexpr uint32_t seed = 0;

    constexpr uint32_t h0 = compiletime_xxhash::xxh32(input, inputLen, seed);

    // Since h0 is compile-time constant value, we can use static_assert().
    static_assert(h0 == 0xd75d048b, "Wrong hash value");

    printf("input     = %s\n"    , input);
    printf("inputLen  = %d\n"    , inputLen);
    printf("constexpr = 0x%08x\n", h0);

#if defined(INCLUDE_XXHASH)
    const uint32_t h1 = XXH32(input, inputLen, seed);
    printf("XXH32()   = 0x%08x\n", h1);
    printf("%s\n"                , (h0 == h1) ? "OK" : "NG");
#endif
}

Build

# Testing C++20 Compile-time XXH32
cd
mkdir my-ct-xxhash-test
cd my-ct-xxhash-test
curl -JOL https://gist.github.com/t-mat/9a7d258324079fd4307b3698b4d109eb/raw/42f5917944fcb29b823416496060a932adb6603f/cxx20_ct_xxhash.cpp
git clone --depth=1 https://github.com/Cyan4973/xxHash

# g++-10
g++-10 -std=c++20 -DINCLUDE_XXHASH ./cxx20_ct_xxhash.cpp
./a.out
rm ./a.out

# clang
clang  -std=c++20 -DINCLUDE_XXHASH ./cxx20_ct_xxhash.cpp
./a.out
rm ./a.out

# output
#
# > input     = xxHash - Extremely Fast Hash algorithm
# > inputLen  = 38
# > constexpr = 0xd75d048b
# > XXH32()   = 0xd75d048b
# > OK

[goodengineer]

It also will encourage other developers to implement the algorithm in different form and language.

pls. have tiny typo correction: ↥.