{"id":1278,"date":"2015-10-14T22:06:47","date_gmt":"2015-10-15T05:06:47","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1278"},"modified":"2015-10-15T08:51:54","modified_gmt":"2015-10-15T15:51:54","slug":"more-string-hashing-with-c11-constexpr","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1278","title":{"rendered":"More string hashing with C++11 constexpr"},"content":{"rendered":"

(Start at the beginning of the series<\/a> – and all the source can be found in my github repo<\/a>)<\/p>\n

So FNV1 was easy, and Murmur3 wasn’t too much harder; for a challenge and to see how far I could go, I decided to try to compute an MD5 string hash using C++11 constexpr<\/code>.<\/p>\n

This was significantly harder. I broke out my copy of Applied Cryptography 2e<\/a>, found a reference implementation of MD5 in C, read through RFC 1321<\/a> and the pseudocode<\/a> on the Wikipedia page.<\/p>\n

Few, few the bird make her nest<\/strong><\/p>\n

I built up MD5 piece by piece, pulling out parts of the reference implementation to check that I’d got each building block right before moving on. The actual round function primitives were the easy part. As usual for a hash function, they are a mixture of bitwise functions, shifts, rotates, adds. These types of things make for trivial constexpr<\/code> functions, for example:<\/p>\n

\r\nconstexpr uint32_t F(uint32_t X, uint32_t Y, uint32_t Z)\r\n{\r\n  return (X & Y) | (~X & Z);\r\n}\r\n\r\nconstexpr uint32_t rotateL(uint32_t x, int n)\r\n{\r\n  return (x << n) | (x >> (32-n));\r\n}\r\n\r\nconstexpr uint32_t FF(uint32_t a, uint32_t b,\r\n                      uint32_t c, uint32_t d,\r\n                      uint32_t x, int s, uint32_t ac)\r\n{\r\n  return rotateL(a + F(b,c,d) + x + ac, s) + b;\r\n}\r\n<\/pre>\n
There are similar functions for the other low-level primitives of the MD5 round functions, conventionally called F, G, H and I.<\/p>\n
Now, MD5 works on buffer chunks of 512 bits, or 16 32-bit words. So assuming we have a string long enough, it’s easy, if a bit long-winded, to convert a block of string into a schedule that MD5 can work on:<\/p>\n
\r\nstruct schedule\r\n{\r\n  uint32_t w[16];\r\n};\r\n\r\nconstexpr schedule init(const char* buf)\r\n{\r\n  return { { word32le(buf), word32le(buf+4), word32le(buf+8), word32le(buf+12),\r\n        word32le(buf+16), word32le(buf+20), word32le(buf+24), word32le(buf+28),\r\n        word32le(buf+32), word32le(buf+36), word32le(buf+40), word32le(buf+44),\r\n        word32le(buf+48), word32le(buf+52), word32le(buf+56), word32le(buf+60) } };\r\n}\r\n<\/pre>\n
Seconds out, round one<\/strong><\/p>\n
It’s not pretty, but such are the constructs that may arise when you only have C++11 constexpr<\/code> to work with. The output of MD5 is going to be 4 32-bit words of hash (denoted A, B, C and D in the literature), and in the main loop, which happens for each 512 bits of the message, there are four rounds, each round having 16 steps. After each step, the 4 words are rotated so that A becomes the new B, B becomes the new C, etc. So a round step is fairly easy – here’s the round 1 step which uses the F primitive:<\/p>\n
\r\nstruct md5sum\r\n{\r\n  uint32_t h[4];\r\n};\r\n\r\nconstexpr md5sum round1step(const md5sum& sum,\r\n                            const uint32_t* block,\r\n                            int step)\r\n{\r\n  return { {\r\n      FF(sum.h[0], sum.h[1], sum.h[2], sum.h[3],\r\n         block[step], r1shift[step&3], r1const[step]),\r\n        sum.h[1], sum.h[2], sum.h[3]\r\n        } };\r\n}\r\n<\/pre>\n
As you can see, there are some constants (r1shift<\/code> and r1const<\/code>) for each stage of round 1. Rotating the words after each round step is also easy:<\/p>\n
\r\nconstexpr md5sum rotateCR(const md5sum& sum)\r\n{\r\n  return { { sum.h[3], sum.h[0], sum.h[1], sum.h[2] } };\r\n}\r\n\r\nconstexpr md5sum rotateCL(const md5sum& sum)\r\n{\r\n  return { { sum.h[1], sum.h[2], sum.h[3], sum.h[0] } };\r\n}\r\n<\/pre>\n
So now we are able to put together a complete round, which recurses, calling the round step function and rotating the output until we’re done after 16 steps.<\/p>\n
\r\nconstexpr md5sum round1(const md5sum& sum,\r\n                        const uint32_t* msg, int n)\r\n{\r\n  return n == 16 ? sum :\r\n    rotateCL(round1(rotateCR(round1step(sum, msg, n)), msg, n+1));\r\n}\r\n<\/pre>\n
Rounds 2 through 4 are very similar, but instead of using the F primitive, they use G, H and I respectively. A complete MD5 transform for one 512-bit block looks like this (with a helper function that sums the MD5 result parts):<\/p>\n
\r\nconstexpr md5sum sumadd(const md5sum& s1, const md5sum& s2)\r\n{\r\n  return { { s1.h[0] + s2.h[0], s1.h[1] + s2.h[1],\r\n        s1.h[2] + s2.h[2], s1.h[3] + s2.h[3] } };\r\n}\r\n\r\nconstexpr md5sum md5transform(const md5sum& sum,\r\n                              const schedule& s)\r\n{\r\n  return sumadd(sum,\r\n                round4(\r\n                    round3(\r\n                        round2(\r\n                            round1(sum, s.w, 0),\r\n                            s.w, 0),\r\n                        s.w, 0),\r\n                    s.w, 0));\r\n}\r\n<\/pre>\n
The ugly business of padding<\/strong><\/p>\n
So far so good. This works, as long as we’re processing the complete 512-bit blocks contained in the message. Now to consider how to finish off. The padding scheme for MD5 is as follows:<\/p>\n