Compile Time String Hashing

Compile time string hashing

This is a little bit late, but I succeeded in implementing a compile-time CRC32 function with the use of constexpr. The problem with it is that at the time of writing, it only works with GCC and not MSVC nor Intel compiler.

Here is the code snippet:

// CRC32 Table (zlib polynomial)
static constexpr uint32_t crc_table[256] = {
    0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
    0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
    0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
...
};
template<size_t idx>
constexpr uint32_t crc32(const char * str)
{
    return (crc32<idx-1>(str) >> 8) ^ crc_table[(crc32<idx-1>(str) ^ str[idx]) & 0x000000FF];
}

// This is the stop-recursion function
template<>
constexpr uint32_t crc32<size_t(-1)>(const char * str)
{
    return 0xFFFFFFFF;
}

// This doesn't take into account the nul char
#define COMPILE_TIME_CRC32_STR(x) (crc32<sizeof(x) - 2>(x) ^ 0xFFFFFFFF)

enum TestEnum
{
    CrcVal01 = COMPILE_TIME_CRC32_STR("stack-overflow"),
};

CrcVal01 is equal to 0x335CC04A

Hope this will help you!

Hashing types at compile-time in C++17/C++2a

I don't know a way to obtain a std::size_t for the hash.

But if you accept a pointer to something, maybe you can take the address of a static member in a template class.

I mean... something as follows

#include <iostream>
#include <type_traits>

template <typename>
struct type_hash
 {
   static constexpr int          i     { };
   static constexpr int const *  value { &i };
 };

template <typename T>
static constexpr auto type_hash_v = type_hash<T>::value;


int main ()
 {
   auto x = []{};
   auto y = []{};
   auto z = x;
   std::cout << std::is_same_v<decltype(x), decltype(y)> << std::endl; // 0
   std::cout << std::is_same_v<decltype(x), decltype(z)> << std::endl; // 1
   constexpr auto xhash = type_hash_v<decltype(x)>;
   constexpr auto yhash = type_hash_v<decltype(y)>;
   constexpr auto zhash = type_hash_v<decltype(z)>;
   std::cout << (xhash == yhash) << std::endl; // should be 0
   std::cout << (xhash == zhash) << std::endl; // should be 1
 } // ...........^^^^^  xhash, not yhash

If you really want type_hash as a function, I suppose you could simply create a function that return the type_hash_v<T> of the type received.

compile-time string hashing

Solution with gcc-4.6:

#include <iostream>
template<size_t N, size_t I=0>
struct hash_calc {
    static constexpr size_t apply (const char (&s)[N]) {
       return  (hash_calc<N, I+1>::apply(s) ^ s[I]) * 16777619u;
    };
};

template<size_t N>
struct hash_calc<N,N> {
    static constexpr size_t apply (const char (&s)[N]) {
       return  2166136261u;
    };
};

template<size_t N>
constexpr size_t hash ( const char (&s)[N] ) {
    return hash_calc<N>::apply(s);
}

int main() {
   char a[] = "12345678";
   std::cout << std::hex << hash(a) << std::endl;
   std::cout << std::hex << hash("12345678") << std::endl;
}

http://liveworkspace.org/code/DPObf

I`m happy!

Truly compile-time string hashing in C++

The trouble is that in C++03 the result of subscripting a string literal (i.e. access a single character) is not a compile-time constant suitable for use as a template parameter.

It is therefore not possible to do this. I would recommend you to write a script to compute the hashes and insert them directly into the source code, i.e.

printf("%d", SOMEHASH("string"));

gets converted to

printf("%d", 257359823 /*SOMEHASH("string")*/ ));

Compile-time (preprocessor) hashing of string

With C++0x, this is possible as covered by answers in #1 and #2.

In C++03 there was no compile time string processing. With the preprocessor you can't seperate the string into tokens, with templates you can't access single characters. There was however a discussion on the speculated approach using C++0x.

What you could do for C++03 is to pass the string character-wise (possible using multi-character literals):

foo = hash<3DES, str<'a','b','c'> >::result;
// or:
foo = hash<3DES, str<'abc','def'> >::result;

... or simply do it as a pre-build step.

Strange assembly output when optimizing string hashing

sizeof is wrong here. It returns the size of the char pointer not the length of the string.

In your case it is an UB and the compiler cannot optimize it out as you read outside string literal bounds. it is a clang bug not the feature.

if you do it properly gcc will optimize it as well

int main(void)
{
    char const string[] = "hello";
    int hash = 0;
    for (unsigned char i=0; i < sizeof(string); ++i)
    {
        hash += string[i]; //reeaally simple hash :)
    }

    printf("%i", hash);
    return 0;
}

https://godbolt.org/z/YCCNCt

Compile time hash with constexpr

Read the error message: you are calling a non-constexpr function when evaluating a constexpr value. Have you tried fixing that?

When you make all relevant functions as constexpr you will get a few additional errors needing your attention. Some remarks:

Make sure you compile with -std=c++14. C++11 is not good enough for this.
remove all operations on std::cout from within SDBMCalculator functions - those are not permitted at compile-time
change int into unsigned int in all relevant computations. When left shift overflows on int type you get an undefined behavior. Left shift on unsigned type is computed modulo its maximum value+1 instead.
```
error: shift expression ‘(4723229 << 16)’ overflows
constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello")
```

With all the above fixes your code will work. I get the result:

2873473298