Writing FNV-1a by Hand

Spent an evening writing FNV-1a by hand, which is about fifteen lines and took a great deal longer than fifteen lines ought to. The job is turning a whole world into one 64 bit number, so I can tell whether two runs of the simulation came out identical.

I started out assuming a hash was the values added up. Add them and a level of 3 with 5 players comes out the same as 4 and 4, and the same as 2 and 6. You fix that by multiplying after each value goes in, because the multiply lands on everything accumulated so far, so the first value has been through it once for every value that followed. Position sets the weight, and 3 then 5 stops looking like 4 then 4.

Then xor, which I had filed away as a sort of addition and which is not. Addition carries into the next column, xor does not, every bit resolves on its own. So the multiply does all the spreading and the xor only injects the new value, two jobs, two operations, neither getting in the other’s way.

Then masking, which is a stencil. You AND the value against a pattern and only the bits you left as 1 come through. I spent a good while convinced that a mask of eight ones would let everything past, which it would, if the value were a byte. It is 64 bits. Eight ones keeps eight of them and throws away fifty six.