MD5 implementation in C++11

Question

I'm writing a C++ implementation of the MD5 hashing algorithm based on the pseudocode of this wikipedia article.

#include <array>
#include <iterator>
#include <cstdint>

class md5 {
    private:
        std::uint32_t a0_;
        std::uint32_t b0_;
        std::uint32_t c0_;
        std::uint32_t d0_;

        std::array<std::uint32_t, 16> m_array_;
        std::array<std::uint32_t, 16>::iterator m_array_first_;

        static const std::array<std::uint32_t, 64> k_array_;
        static const std::array<std::uint32_t, 64> s_array_;

    private:
        static std::uint32_t left_rotate(std::uint32_t x, std::uint32_t c) {
            return (x << c) | (x >> (32 - c));
        }

        template <class OutputIterator>
        static void uint32_to_byte(std::uint32_t n, OutputIterator & first) {

            *first++ = n & 0xff;
            *first++ = (n >> 8) & 0xff;
            *first++ = (n >> 16) & 0xff;
            *first++ = (n >> 24) & 0xff;
        }

        template <class OutputIterator>
        static void uint32_to_hex(std::uint32_t n, OutputIterator & first) {
            const char * hex_chars = "0123456789abcdef";            

            std::uint32_t b;

            b = n & 0xff;
            *first++ = hex_chars[b >> 4];
            *first++ = hex_chars[b & 0xf];

            b = (n >> 8) & 0xff;
            *first++ = hex_chars[b >> 4];
            *first++ = hex_chars[b & 0xf];

            b = (n >> 16) & 0xff;
            *first++ = hex_chars[b >> 4];
            *first++ = hex_chars[b & 0xf];

            b = (n >> 24) & 0xff;
            *first++ = hex_chars[b >> 4];
            *first++ = hex_chars[b & 0xf];
        }

    private:
        void reset_m_array() {
            m_array_first_ = m_array_.begin();
        }

        template <class InputIterator>
        void bytes_to_m_array(InputIterator & first, std::array<std::uint32_t, 16>::iterator m_array_last) {
            for (; m_array_first_ != m_array_last; ++m_array_first_) {
                *m_array_first_ = *first++;
                *m_array_first_ |= *first++ << 8;
                *m_array_first_ |= *first++ << 16; 
                *m_array_first_ |= *first++ << 24;
            }
        }

        template <class InputIterator>
        void true_bit_to_m_array(InputIterator & first, std::ptrdiff_t chunk_length) {
            switch (chunk_length % 4) {
                case 0:
                    *m_array_first_++ = 0x00000080;
                    break;
                case 1:
                    *m_array_first_++ = *first++;
                    *m_array_first_ |= 0x00008000;
                    break;
                case 2:
                    *m_array_first_++ = *first++; 
                    *m_array_first_ |= *first++ << 8;
                    *m_array_first_ |= 0x00800000;
                    break;
                case 3:
                    *m_array_first_++ = *first++;
                    *m_array_first_ |= *first++ << 8;
                    *m_array_first_ |= *first++ << 16;
                    *m_array_first_ |= 0x80000000;
                    break;
            }
        }

        void zeros_to_m_array(std::array<std::uint32_t, 16>::iterator m_array_last) {
            for (; m_array_first_ != m_array_last; ++m_array_first_) {
                *m_array_first_ = 0;
            }
        }

        void original_length_bits_to_m_array(std::uint64_t original_length_bits) {
            original_length_bits &= 0xffffffffffffffff;
            *m_array_first_++ = (original_length_bits) & 0x00000000ffffffff;
            *m_array_first_++ = (original_length_bits & 0xffffffff00000000) >> 32;
        }

        void hash_chunk() {
            std::uint32_t A = a0_;
            std::uint32_t B = b0_;
            std::uint32_t C = c0_;
            std::uint32_t D = d0_;

            std::uint32_t F;
            unsigned int g;

            for (unsigned int i = 0; i < 64; ++i) {
                if (i < 16) {
                    F = (B & C) | ((~B) & D);
                    g = i;
                }
                else if (i < 32) {
                    F = (D & B) | ((~D) & C);
                    g = (5 * i + 1) & 0xf; 
                }
                else if (i < 48) {
                    F = B ^ C ^ D;
                    g = (3 * i + 5) & 0xf;
                }
                else {
                    F = C ^ (B | (~D));
                    g = (7 * i) & 0xf;
                }

                std::uint32_t D_temp = D;
                D = C;
                C = B;
                B += left_rotate(A + F + k_array_[i] + m_array_[g], s_array_[i]);
                A = D_temp;
            }

            a0_ += A;
            b0_ += B;
            c0_ += C;
            d0_ += D;
        }

    public:
        template <class InputIterator>
        void update(InputIterator first, InputIterator last) {

            std::uint64_t original_length_bits = std::distance(first, last) * 8;

            std::ptrdiff_t chunk_length;
            while ((chunk_length = std::distance(first, last)) >= 64) {
                reset_m_array();
                bytes_to_m_array(first, m_array_.end());
                hash_chunk();
            }

            reset_m_array();
            bytes_to_m_array(first, m_array_.begin() + chunk_length / 4);
            true_bit_to_m_array(first, chunk_length);

            if (chunk_length >= 56) {
                zeros_to_m_array(m_array_.end());
                hash_chunk();

                reset_m_array();
                zeros_to_m_array(m_array_.end() - 2);
                original_length_bits_to_m_array(original_length_bits);
                hash_chunk();
            }
            else {
                zeros_to_m_array(m_array_.end() - 2);
                original_length_bits_to_m_array(original_length_bits);
                hash_chunk();
            }
        }   

    public:
        md5()
          : a0_(0x67452301),
            b0_(0xefcdab89),
            c0_(0x98badcfe),
            d0_(0x10325476)
        {}

        template <class Container> 
        void digest(Container & container) {
            container.resize(16);
            auto it = container.begin();

            uint32_to_byte(a0_, it);
            uint32_to_byte(b0_, it);
            uint32_to_byte(c0_, it);
            uint32_to_byte(d0_, it);
        }

        template <class Container>
        void hex_digest(Container & container) {
            container.resize(32);
            auto it = container.begin();

            uint32_to_hex(a0_, it);
            uint32_to_hex(b0_, it);
            uint32_to_hex(c0_, it);
            uint32_to_hex(d0_, it);
        }
};

const std::array<std::uint32_t, 64> md5::k_array_ = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
    0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
    0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
    0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
    0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
    0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
    0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
    0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
    0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
    0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
    0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
    0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
    0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
    0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
};

const std::array<std::uint32_t, 64> md5::s_array_ = {
    7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,
    5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,
    4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,
    6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21
};

Here is some example usage

#include <iostream>

int main() {
    std::string data = "Hello World";
    std::string data_hex_digest;

    md5 hash;
    hash.update(data.begin(), data.end());
    hash.hex_digest(data_hex_digest);

    std::cout << data_hex_digest << std::endl;
}

Output: b10a8db164e0754105b7a99be72e3fe5

Answer 1

First impressions

The code seems very clean and tidy. As far as I can tell, you're including exactly the required headers - no more, and no less. There's generally good use of const and static, but left_rotate() could benefit from constexpr, and digest() and hex_digest should both be const.

Separability

Consider moving the member function definitions out from within the class. This will make it easier to see what's in the class in a single screenful, and will help you extract a reusable header file from the implementation.

Initial values

We don't need this constructor:

    md5()
      : a0_(0x67452301),
        b0_(0xefcdab89),
        c0_(0x98badcfe),
        d0_(0x10325476)
    {}

We can instead give the members their initial values inline:

    std::uint32_t a0_ = 0x67452301;
    std::uint32_t b0_ = 0xefcdab89;
    std::uint32_t c0_ = 0x98badcfe;
    std::uint32_t d0_ = 0x10325476;

Perhaps roll up a loop of repeated instructions

I'm not sure whether it works out cleaner that what you have, but an alternative implementation of uint32_to_hex() puts the eight writes into a loop:

template<class OutputIterator>
static void uint32_to_hex(const std::uint32_t n, OutputIterator& out)
{
    static auto const hex_chars = "0123456789abcdef";

    // print nibbles, low byte first (but high nibble before low nibble)
    // so shift is 4, 0, 12, 8, 20, 16, ...
    for (auto i = 0u;  i < 32;  i += 4) {
        *out++ = hex_chars[(n >> (i ^ 4)) & 0xf];
    }
}

It's likely that the two produce similar code when subject to a good optimizer.

Remove unnecessary bit-masking

This function has useless & operations:

void original_length_bits_to_m_array(std::uint64_t original_length_bits)
{
    original_length_bits &= 0xffffffffffffffff;
    *m_array_first_++ = (original_length_bits) & 0x00000000ffffffff;
    *m_array_first_++ = (original_length_bits & 0xffffffff00000000) >> 32;
}

The first is meaningless because 0xffffffffffffffff is the same as ~0 in 64 bits, so makes no change. The other two are redundant because assigning an unsigned 64-bit value to a 32-bit variable simply discards the upper bits. So it's exactly equivalent to:

void original_length_bits_to_m_array(std::uint64_t original_length_bits)
{
    *m_array_first_++ = original_length_bits;
    *m_array_first_++ = original_length_bits >> 32;
}

Simplify the interface

We should be able to initialize a md5 object and feed it its first (perhaps only) data. And it would be nice if we didn't have to create an output collection and pass it to be written to. That's easily achieved by adding a constructor and overloads of digest() and hex_digest():

md5()
{}

template<class InputIterator>
md5(InputIterator first, InputIterator last)
{
    update(first, last);
}

template<class Container>
Container digest() const
{
    Container c;
    digest(c);
    return c;
}

template<class Container>
Container hex_digest() const
{
    Container c;
    hex_digest(c);
    return c;
}

Then our main() becomes shorter, simpler and more robust:

int main()
{
    std::string data = "Hello World";

    const md5 hash(data.begin(), data.end());
    const auto data_hex_digest = hash.hex_digest<std::string>();

    std::cout << data_hex_digest << std::endl;
}

Constrain the input type

At present, update will accept a pair of iterators if they dereference to integer types. However, the algorithm assumes that they will be no wider than 8 bits, so I could pass it a std::wstring and be surprised by the result. It's better to prevent such code from compiling:

#include <limits>
#include <type_traits>

template<class InputIterator>
typename std::enable_if<
    std::numeric_limits<typename InputIterator::value_type>::digits <= 8
>::type
update(InputIterator first, InputIterator last)

We also need to ensure that bytes_to_m_array() doesn't sign-extend the values it reads:

template<class InputIterator>
void bytes_to_m_array(InputIterator& first,
                      std::array<std::uint32_t, 16>::iterator m_array_last)
{
    for (; m_array_first_ != m_array_last; ++m_array_first_) {
        *m_array_first_ = std::uint8_t(*first++);
        *m_array_first_ |= std::uint8_t(*first++) << 8;
        *m_array_first_ |= std::uint8_t(*first++) << 16;
        *m_array_first_ |= std::uint8_t(*first++) << 24;
    }
}

There's a similar change needed in true_bit_to_m_array() - it's probably worth writing a small helper function:

template<class InputIterator>
static std::uint8_t input_u8(const InputIterator& it)
{
    return *it;
}

template<class InputIterator>
void bytes_to_m_array(InputIterator& first,
                      std::array<std::uint32_t, 16>::iterator m_array_last)
{
    for (; m_array_first_ != m_array_last; ++m_array_first_) {
        *m_array_first_ = input_u8(first++);
        *m_array_first_ |= input_u8(first++) << 8;
        *m_array_first_ |= input_u8(first++) << 16;
        *m_array_first_ |= input_u8(first++) << 24;
    }
}

template<class InputIterator>
void true_bit_to_m_array(InputIterator& first, std::ptrdiff_t chunk_length)
{
    switch (chunk_length % 4) {
    case 0:
        *m_array_first_++ = 0x00000080;
        break;
    case 1:
        *m_array_first_++ = input_u8(first++);
        *m_array_first_ |= 0x00008000;
        break;
    case 2:
        *m_array_first_++ = input_u8(first++);
        *m_array_first_ |= input_u8(first++) << 8;
        *m_array_first_ |= 0x00800000;
        break;
    case 3:
        *m_array_first_++ = input_u8(first++);
        *m_array_first_ |= input_u8(first++) << 8;
        *m_array_first_ |= input_u8(first++) << 16;
        *m_array_first_ |= 0x80000000;
        break;
    }
}

BUG: increment last

Whilst editing that last function, I spotted a bug:

        *m_array_first_++ = input_u8(first++);
        *m_array_first_ |= input_u8(first++) << 8;
        *m_array_first_ |= input_u8(first++) << 16;
        *m_array_first_ |= 0x80000000;

I think that _array_first_ is meant to be incremented in the last of those statements, rather than the first:

        *m_array_first_ = input_u8(first++);
        *m_array_first_ |= input_u8(first++) << 8;
        *m_array_first_ |= input_u8(first++) << 16;
        *m_array_first_++ |= 0x80000000;

I suspect that this was caused by a last-minute change that wasn't detected by your test suite. That's a sign that your tests are missing some vital cases, but as they are not included in the review, I'm not able to make any recommendations beyond very general advice to add tests for the bugs you find before you fix them (writing the test and showing it to fail is the easiest way to demonstrate that it's a useful and effective test).

It may be clearer and safer to write a separate increment statement outside the switch:

template<class InputIterator>
void true_bit_to_m_array(InputIterator& first, std::ptrdiff_t chunk_length)
{
    switch (chunk_length % 4) {
    case 0:
        *m_array_first_  = 0x00000080;
        break;
    case 1:
        *m_array_first_  = input_u8(first++);
        *m_array_first_ |= 0x00008000;
        break;
    case 2:
        *m_array_first_  = input_u8(first++);
        *m_array_first_ |= input_u8(first++) << 8;
        *m_array_first_ |= 0x00800000;
        break;
    case 3:
        *m_array_first_  = input_u8(first++);
        *m_array_first_ |= input_u8(first++) << 8;
        *m_array_first_ |= input_u8(first++) << 16;
        *m_array_first_ |= 0x80000000;
        break;
    }
    ++m_array_first_;
}