FNV hashing in Mathematica

May 4, 2012

I recently needed to do Fowler/Noll/Vo hashing in Mathematica. I figured other people might have a need for this hash function as well, so here’s my Mathematica implementation:

(* FNV hash parameters: bit length, FNV prime, FNV offset *)
$FNVData = Append[#, Function[{bi, pr},
Fold[BitXor[Mod[pr #1, 2^bi], #2] &, 0,
ToCharacterCode["chongo /\\../\\"]]] @@ #] & /@ Transpose[{2^Range[5, 10],
2^(8 Quotient[2^Range[5, 10] + 5, 12]) + 2^8 +
Map[FromDigits[#, 16] &,
{"93", "B3", "3B", "63", "57", "8D"}]}];

FNV[dat_String, bi : _Integer : 32, shift : (0 | 1) : 1] := With[{k = IntegerExponent[bi, 2] - 4},
Fold[BitXor[Mod[$FNVData[[k, 2]] #1, 2^bi], #2] &,
shift $FNVData[[k, 3]], ToCharacterCode[dat]]] /;
32 <= bi <= 1024 && BitAnd[bi, bi - 1] == 0

I made sure to provide for both shift-1 and shift-0 versions in the implementation (though as mentioned on the FNV page, FNV-1 is what should be preferred). The FNV page has a few suggestions to extend FNV hashing to bit lengths that are not a power of two, but I did not bother with them. (Maybe somebody else can try!) It should not be too hard to modify the code to do FNV-1a hashing.

questions, questions

August 13, 2010

I really should be getting around to posting something with actual mathematical content in this blog, but for now I’m slowly working through my backlog of my “dumb questions”; and there were quite a lot of them scattered around in my handwritten notes and an assorted bunch of my Mathematica notebook experiments. Thus far, my technique of asking my dumb questions at MathOverflow (and to a lesser extent at “Math Underflow“) seems to be working: if they get downvoted, then they’re definitely dumb.

In at least two separate occasions, some of the answers I got led me to useful new ideas, though not necessarily related to the original question(s) I asked. I guess that’s something. :)

Once I sort myself out, I’ll start posting about my experiments.

Happy trails!