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!

At least by my reading of §7.1.5/3 and §5.19, the following might be legitimate:

unsigned constexpr const_hash(char const *input) {
    return *input ?
        static_cast<unsigned int>(*input) + 33 * const_hash(input + 1) :
        5381;
}

This does seem to follow the basic rules in §7.1.5/3:

1. The form is: "return expression;"
2. Its only parameter is a pointer, which is a scalar type, and therefore a literal type.
3. Its return is unsigned int, which is also scalar (and therefore literal).
4. There is no implicit conversion to the return type.

There is some question whether the *inputs involve an illegal lvalue to rvalue conversion, and I'm not sure I understand the rules in §5.19/2/6/2¹ and §4.1 well enough to be sure about that.

From a practical viewpoint, this code is accepted by (for one example) g++, at least as far back as g++ 4.7.1.

Usage would be something like:

switch(std::hash(value)) {
    case const_hash("one"): one(); break;
    case const_hash("two"): two(); break;
    // ...
    default: other(); break;
}

To comply with the requirements of §5.19/2/6/2 you might have to do something like this though:

// one of the `constexpr`s is probably redundant, but I haven't figure out which.
char constexpr * constexpr v_one = "one"; 

// ....

case const_hash(v_one): one(); break;

1. I'm using the extra 'slash' numbers to refer to unnumbered bullet points, so this is the second bullet point inside if the sixth bullet point under §5.19/2. I think I might have to talk to Pete Becker about whether it's possible to add some sort of numbers/letters/roman numerals down the hierarchy to identify pieces like this...

If you have a c++17 compiler and string_view, this becomes trivial, just write the normal version:

constexpr uint32_t crc32(std::string_view str)
{
    uint32_t crc = 0xffffffff;
    for (auto c : str)
        crc = (crc >> 8) ^ crc_table[(crc ^ c) & 0xff];
    return crc ^ 0xffffffff;
}

Note that the form shown here wasn't accepted into the standard, as noted below.

Compile time string processing is guessed to become possible through user-defined literals proposed in N2765.
As i already mentioned, i don't know of any compiler that currently implements it and without compiler support there can be only guess work.

In §2.13.7.3 and 4 of the draft we have the following:

Otherwise (S contains a literal operator template), L is treated as a call of the form
operator "" X<'c1', 'c2', ... , 'ck'>() where n is the source character sequence c1c2...ck. [Note: The sequence c1c2...ck can only contain characters from the basic source character set. —end note]

Combine that with constexpr and we should have compile time string processing.

update: i overlooked that i was reading the wrong paragraph, this form is allowed for user-defined-integer-literals and -floating-literals, but apparently not for -string-literals (§2.13.7.5).
This part of the proposal seems to have not been accepted.

That being said, with my limited glimpse at C++0x, it might look something like this (i most likely got something wrong):

template<char c, char... str>
struct hash {
    static const unsigned result = c + hash<str...>::result;
};

template<char c>
struct hash {
    static const unsigned result = c;
};

template<char... str> 
constexpr unsigned
operator "" _hash() {
    return hash<str>::result;
}

// update: probably wrong, because the above 
// form is not allowed for string-literals:    
const unsigned h = "abcd"_hash;

If Jerrys approach works, then the following should work however:

constexpr unsigned operator "" _hash(const char* s, size_t) {
    return const_hash(s);
}

I was still missing a crc32-literal variant (which is not possible with templates), so here is my suggestion based on CygnusX1. Did some testing, feel free to give feedback.

Testet on MSVC.

PS: I hate searching for additional stuff somewhere else, so i copied the CRC table on the bottom of my answer.

#include <inttypes.h>

namespace detail
{
    // CRC32 Table (zlib polynomial)
    static constexpr uint32_t crc_table[256] =
    {
        0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
        ...
    };

    constexpr uint32_t combine_crc32( const char c, uint32_t part )
    {
        return (part >> 8) ^ crc_table[(part ^ c) & 0x000000FF];
    }

    constexpr uint32_t crc32( const char * str, size_t idx )
    {
        return combine_crc32( str[idx], idx ? crc32( str, idx - 1 ) : 0xFFFFFFFF );
    }
} //namespace detail

constexpr uint32_t ctcrc32( const char* str, size_t len )
{
    return detail::crc32( str, len ) ^ 0xFFFFFFFF;
}

size_t constexpr operator "" _hash( const char* str, size_t len )
{
    return ctcrc32( str, len );
}

Alternative with algorithmn from Dan Bernstein (djb2) (combined answers from Jerry Coffin + Georg Fritzsche)

unsigned constexpr const_hash( char const *input )
{
    return *input ?
        static_cast<unsigned int>(*input) + 33 * const_hash( input + 1 ) :
        5381;
}
size_t constexpr operator "" _hash( const char* str, size_t len )
{
    return const_hash( str );
}

Crc32 table:

static constexpr uint32_t crc_table[256] =
    {
        0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
        0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
        0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
        0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
        0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
        0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
        0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
        0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
        0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
        0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
        0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
        0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
        0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
        0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
        0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
        0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
        0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
        0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
        0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
        0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
        0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
        0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
        0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
        0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
        0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
        0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
        0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
        0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
        0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
        0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
        0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
        0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
        0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
        0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
        0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
        0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
        0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
        0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
        0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
        0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
        0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
        0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
        0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
        0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
        0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
        0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
        0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
        0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
        0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
        0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
        0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
        0x2d02ef8dL
    };

Based on Jerry Coffin's approach and Georg Fritzsche's approach

I used the following code without constexpr auto const_tmp = NGX_EM_HASH("authorization");:

template <size_t N> constexpr size_t string_literal_length(const char(&str)[N]) { return N - 1; }

// https://stackoverflow.com/questions/2111667/compile-time-string-hashing/66690839#66690839
// "cookie"_hash = ngx_hash(ngx_hash(ngx_hash(ngx_hash(ngx_hash('c', 'o'), 'o'), 'k'), 'i'), 'e');
// See also `ngx_uint_t ngx_hash_key(u_char *data, size_t len)` in nginx\src\core\ngx_hash.c
#if 0
template<ngx_uint_t sum, char ch, char... str> struct ngx_em_hasher {
    static const ngx_uint_t result = ngx_em_hasher<ngx_hash(sum, u_char(ch)), str...>::result;
};
template<ngx_uint_t sum, char ch> struct ngx_em_hasher {
    static const ngx_uint_t result = ngx_hash(sum, u_char(ch));
};
template<char... str> constexpr
ngx_uint_t operator "" _hash() { return ngx_em_hasher<0, str>::result; }

// update: probably wrong, because the above form is not allowed for string-literals:    
// const unsigned h = "abcd"_hash;
#elif defined(_MSC_VER2)
// reducer function: the previous calculation result must be passed to the next iteration
static constexpr ngx_uint_t ngx_em_hash(const char* const psz, ngx_uint_t sum = 0) {
    return *psz ? ngx_em_hash(psz + 1, ngx_hash(sum, u_char(*psz))) : sum;
}
constexpr ngx_uint_t operator "" _hash(const char* s, size_t) { return ngx_em_hash(s); }
// #define NGX_EM_HASH(str) ngx_em_hash(str)

#define NGX_EM_X(x) x
// constexpr auto const_hash = NGX_EM_HASH("authorization");
// hdr->hash = const_hash;
#define NGX_EM_HASH(string_literals) ngx_em_const<NGX_EM_X(string_literals)_hash>::value

#else
template<size_t idx> constexpr ngx_uint_t ngx_em_hash(const char* const psz, ngx_uint_t sum = 0) {
    return ngx_em_hash<idx - 1>(psz + 1, ngx_hash(sum, u_char(*psz)));
}
// This is the stop-recursion function
template<> constexpr ngx_uint_t ngx_em_hash<0>(const char* const psz, ngx_uint_t sum) {
    return sum;
}
// This doesn't take into account the nul char.
#define COMPILE_TIME_NGX_HASH(x) ngx_em_hash<sizeof(x) - 1>(x)
// Regardless of what Optimize Options of the compiler?
// https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
// https://docs.microsoft.com/en-us/cpp/build/reference/o-options-optimize-code?view=msvc-160
#define NGX_EM_HASH(x) ngx_em_const<ngx_em_hash<sizeof(x) - 1>(x)>::value
#endif

void snippet(ngx_table_elt_t *hdr) {
    ngx_str_set(&hdr->key, "Authorization");
    hdr->lowcase_key = (u_char *) "authorization";
    //constexpr auto const_tmp = NGX_EM_HASH("authorization");
    //hdr->hash = const_tmp;
    hdr->hash = NGX_EM_HASH("authorization");
    sr->headers_in.authorization = hdr;
}

And then its disassembly result looked like this (using VS2017 v15.9.27):

                ;hdr->hash = NGX_EM_HASH("authorization");
00007FFD36B8B7DE  mov         rax,qword ptr [rbp+4D8h]  
00007FFD36B8B7E5  mov         rcx,4EEC63AFAD69E079h     ; Decimal=5687030035641917561 __int64
00007FFD36B8B7EF  mov         qword ptr [rax],rcx 

But, if using #define NGX_EM_HASH(string_literals) NGX_EM_X(string_literals)_hash, its disassembly result looked like this:

                ;hdr->hash = NGX_EM_HASH("authorization");
00007FFD337FFE93  lea         rcx,[string "authorization" (07FFD33885ED0h)]  
00007FFD337FFE9A  call        operator "" _hash (07FFD336B78ECh)  
00007FFD337FFE9F  mov         rcx,qword ptr [rbp+4D8h]  
00007FFD337FFEA6  mov         qword ptr [rcx],rax  

Online

• Compiler Explorer with disassembly outputs of VC++ and GCC (Run compilers interactively from your web browser and interact with the assembly)
• ngx_hash@OnlineGDB beta (online compiler and debugger for c/c++)