Debugging MD5    (January 27th, 2026)
=============

I just finished implementing MD5 in Uiua for AoC '15 Day 4.


Implementation gotchas
----------------------
- The left rotation is a true rotation, not just a left shift.
- When you convert the string to ints, you need to make the ints little-endian. In other words, a string C0C1C2C3C4C5C6C7, where each Ci is 8-bit, becomes the two 32-bit ints C3C2C1C0 C7C6C5C4.
- When you append the 64-bit length, you are effectively appending two ints. However, the ints aren't little-endian; but you do append them in the opposite order. So if the length is (big-endian) 0x0000000000000320, you append 0x00000320 0x00000000 to finish the padding. Also, this length represents the number of bits, not the number of bytes.


Uiua notes
----------
Initially, I always reversed ⋯'s result. This is slow, and by removing it and always working with bits reversed, I was able to speed it up by about 33%. Since MD5 uses little-endian everywhere, this change was a major headache because I need to deal with both the algorithm having bytes reversed and Uiua having bits reversed.

Another thing that helped with speed was minimizing uses of ⋯. When I was adding all the intermediate results up, I initially had them in an array and did a fold. The folding operation would ∩°⋯, +, then ⋯. However, you don't need to ⋯ between intermediate results, and removing that helped make it faster.


Algorithm resources
-------------------
- The original MD5 spec
- Wikipedia article on the MD5 algorithm

Resources that help debug
-------------------------
- Rosetta Code MD5/Implementation Debug
- Debugging a MD5 Implementation by Craig Buchanan

~/aoc15ua/md5ua