Compile time MD5 using constexpr

Today, someone on stackoverflow asked how to perform compile-time hashing in C++. After providing a small, naive, example in my answer, I thought it would actually be interesting to implement some well known hashing algorithm using C++11 features, such as constexpr. So I gave MD5 a try, and after some hours of trying stuff, I was able to create compile-time MD5 hashes.

The MD5 hashing algorithm.

Implementing the algorithm itself was not as hard as I thought it would be. The algorithm is roughly like this:

1. It starts with 4 32-bits integers which contain a predefined value.
2. The algorithm contains 4 "rounds". On each of them, a different function is applied to those integers and the input string.
3. The result of those rounds serves as input to the next ones.
4. Add the 4 resulting 32-bit integers with the original, predefined integer values.
5. Interpret the resulting integers as a chunk of 16 bytes.

That's it. Note that I've somehow stripped down the algorithm to short strings. A real implementation would iterate several times doing the same stuff on the entire buffer. But since nobody is going to hash large strings on compile time, I've simplified the algorithm a little bit.

The implementation

So basically the implementation was not that hard, some template metaprogramming and several constexpr functions. Since there was a pattern on the way the arguments were provided as input to the functions in each round, I used a specialization which avoided lots of repeated code.

The worst part was generating the input for that algorithm. The input is not just the string which is to be hashed. The steps to generate that input is roughly as follows:

1. Create a buffer of 64 bytes, filled with zeros.
2. Copy the input string into the start of the buffer.
3. Add a 0x80 character on buffer[size_of_input_string].
4. On buffer[56], the value sizeof_input_string * 8 must be stored.

That's all. The algorithm will only work with strings of no more than 31 bytes. It could be generalized by modifying the appropriate bytes on buffer[57:60], but that was not my objective.

In order to achieve this buffer initialization, I had to somehow decompose the input string into characters, and then join them and those special bytes, into an array which could be used during compile time. In order to achieve this, I implemented a constexpr_array, which is just a wrapper to a built-in array, but provides a data() constexpr member, something that std::array does not have(I'm not really sure why):

template<typename T, size_t n>
struct constexpr_array {
    const T array[n];
    
    constexpr const T *data() const {
        return array;
    }
};

The decomposition ended up pretty simple, but I had to struggle to figure out how the hell to implement it.

Finally, the interface for the compile time MD5 would be the following:

template<size_t n> constexpr md5_type md5(const char (&data)[n]) 

The typedef for the function's result is the following:

typedef std::array<char, 16> md5_type;

Note that everything in the implementation resides in namespace ConstexprHashes.

As an example, this code generates a hash and prints it:

#include <iostream>
#include "md5.h"

int main() {
    constexpr auto value = ConstexprHashes::md5("constexpr rulz");
   
    std::cout << std::hex;
    for(auto v : value) {
        if(((size_t)v & 0xff) < 0x10)
            std::cout << '0';
        std::cout << ((size_t)v & 0xff);
    }
    std::cout << std::endl;
}

This prints out: "b8b4e2be16d2b11a5902b80f9c0fe6d6", which is the right hash for "constexpr rulz".

Unluckily, the only compiler that is able to compile this is clang 3.1(I haven't tested it on newer versions). GCC doesn't like the code, and believes some constexpr stuff is actually non-constexpr. I'm not 100% sure that clang is the one that's right, but it looks like it is.

You can find the MD5 implementation here. Maybe I'll implement SHA1 soon, whenever I have some time.

Well, this was the first time I used constexpr, it was a nice experience. Implementing this using only TMP would be an extreme pain in the ass.

small integer C++ wrapper

Currently, I'm working on libtins, a library I'm developing with a friend. This library mainly contains classes that abstract PDUs, among other stuff.

Since PDU classes are basically a wrapper over the protocol data units handled by the operating system, getters and setters are provided to enable the user to modify the fields in them. For example, there is a TCP::data_offset method which takes a value of type uint8_t and stores it in the TCP header's data offset field, which is 4 bit wide.

While developing test units for this library, I would use some random number to initialize those fields, and then use the corresponding getter to check that the same number came out of it. A problem that I faced several times is that, there is no way to indicate that, while a setter method takes an uint8_t, the field being set internally is actually 4 bits wide, so any value larger than 15 would overflow, leading to the wrong number being stored. We really want to be able to detect those ugly errors.

One solution would be to, on each setter, check whether the provided value is larger to 2 ** n - 1, where n is the width of the field being set, and raise an exception if this condition is true. This has the drawback that every setter should make the appropriate check, using the appropriate power of 2, and throwing the same exception on each of them. This boilerplate solution already looks nasty.

So I came with a better solution. C++'s implicit conversions can do magic for us. All we need is a class that wraps a value of an arbitrary bit width(up to 64 bits) that performs the corresponding checks while being initialized.

The wrapper class is called small_uint(I thought about providing support for signed integral types, but finally dropped that option. It'd be easy to implement though). The class declaration is this one:

template<size_t n> class small_uint;

The template non-type parameter n indicates the length, in bits, of the field. This class should be optimal, meaning that it should use to smallest integral type that can hold a value of that width.

Internally, a compile time switch is performed to check which is the best underlying type, meaning, the type in which storing the field wastes less space. For example, for 7 bit small_uints, a uint8_t is used, while 11 bit fields will be stored in a member variable of type uint16_t. This underlying type is typedef'ed as the repr_type.

There is a constructor which takes a repr_type and raises an exception if it is larger than the 2 ** n - 1, and a user-defined conversion to repr_type which simply returns the stored value. Since no arithmetic operations are performed with these integers, there are no such operators defined. It don't really know if defining them would make sense. If you wanted to perform such operations, you would just use standard arithmetic types. Only operator== and operator!= have been defined.

I haven't used this class in libtins yet, but setters would probably look like this:

void TCP::data_offset(small_uint<4> value) {
     tcp_header_.data_offset = value;
}

That way, a nice and clean solution can be achieved, avoiding boiler plate code. Note that internally, C++11 features could make a lot of things easier(such as std::numeric_limits<>::max() being constexpr, std::conditional, and constexpr functions), but I wanted to use only C++03 stuff, since the library is intended to work with the latter standard.

The small_uint implementation can be found here.