Monday, November 29, 2010

C++: How to calculate string hash at compile-time

#define HASH_BASE 2166136261
#define HASH_MULT 16777619
#define HASH_ROUND(prev_hash, next_char) \
    unsigned((prev_hash ^ next_char) * (next_char ? HASH_MULT : 1))
#define HASH_IMPL(f, s) f(f(f(f( f(f(f(f( HASH_BASE \
    , s[0]), s[1]), s[2]), s[3]), s[4]), s[5]), s[6]), s[7])

#define HASH(str) HASH_IMPL(HASH_ROUND, (str "\0\0\0\0" "\0\0\0\0"))

// FNV-1a hash
unsigned hash(const char* s)
{
    unsigned value = HASH_BASE;
    for(; *s; ++s)
       value = (value ^ *s) * HASH_MULT;
    return value;
}
The idea was borrowed from this SO answer.

At least MSVC 2010 compiler calculates such hashes in compile-time.
Unfortunately they aren't compile-time constants, because by standard "s"[0] yields const l-value reference. So, we should wait C++0x constexpr keyword implementation.

No comments:

Post a Comment