Compile-Time Hash Using constexpr

In this blog entry I present a fairly simple implementation of the djb2 hash function using constexpr which enables the hash to be computed at compile-time.

Until C++11 it has not been possible to provide an easy-to-use compile-time hash function. Template meta-programming does not come to the rescue as it toys with template expansion, which means varying template arguments as various templates expand with different specializations and constraints. TMP suited to type manipulation and to a limited degree doing some work with integer values (as they can be used for template arguments).

Additionally an index into an array was not a compile-time operation. So both the mechanism for doing compile time calculations (TMP) and the actual accessing of the elements to be hashed (indexing into an array) could not be done nicely at compile time.

I say ‘nicely’ because if one were to separate the elements, it is possible to implement a hash using a macro with a usecase looking similar to this:

enum {
  JPEG_HASH = HASH('J','P','E','G')
}

Now in C++11 the specification adds a new kind of keyword called constexpr. I won’t describe it in detail because you’re either aware of its meaning or able to look up a much nicer description of its meaning than I could write.

However it is worth noting that this, combined with other constraints around what operations can be done at compile-time being more relaxed, allows us to actually implement a compile-time hash function with ease. I think the code is simple enough to really speak for itself.

Here is the djb2 hash with xor implemented using constexpr:

constexpr unsigned long djb2_hash_impl( const char* text, unsigned long prev_hash )
{
    return text[0] == '\0' ? prev_hash : djb2_hash_impl( &text[1], prev_hash * 33 ^ static_cast<unsigned long>(text[0]) );
}

constexpr unsigned long djb2_hash( const char* text )
{
    return djb2_hash_impl( text, 5381 );
}

To see this in action click here.

Note that at this time constexpr is not available in VS2013. You will need one of the latest CTP releases of the compiler to test it. It is supported by GCC currently.

This doesn’t seem like much of a blog entry – certainly if you search you’ll find other hash functions being implemented similarly. However this is likely to be step 1 in a more ambitious experiment. If it pans out, I’ll have a few more blog entries which use this specifically.

Advertisements
Compile-Time Hash Using constexpr

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s