gh-Cyan4973/xxHash

Watch

Fork 0

C++20 compile-time XXH32() calculation #496

New issue

Closed

opened 2021-02-03 05:18:18 -06:00 by t-mat · 3 comments

t-mat commented

2021-02-03 05:18:18 -06:00

(Migrated from github.com)

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.

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()`](https://github.com/ekpyron/xxhashct/blob/master/xxh64.hpp). It's better than my code in many aspects.

👍 6 ❤️ 1 🚀 1

t-mat commented

2021-02-03 05:19:18 -06:00

(Migrated from github.com)

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.

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

## 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++ // 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 ```

👍 3

goodengineer commented

2021-03-10 03:43:55 -06:00

(Migrated from github.com)

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

pls. have tiny typo correction: ↥.

> It also will encourage other developers to implement the algorithm in different form and language. pls. have tiny typo correction: ↥.

No milestone

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

gh-Cyan4973/xxHash#496

No description provided.

Rows
Columns

C++20 compile-time XXH32() calculation #496

What's this?

What's the point of this code?

See also

The code and result

Code

Build