I'm mucking about with hash functions, porting some classics like murmur or fnv families and creating my own, for fun, really. I know js isn't exactly an ideal environment for this but whatever.
The biggest obstacle I run into is the fact that js uses doubles for most arithmetics. Almost every single hash function I've ever seen exploits integer overflow by multiplication. For example, I take the input of 7 and multiply it by some big prime like 0x5bd1e995, this multiplication amplifies the significance of that little input into every single bit of the result which is really neat for hash functions.
Unfortunately this falls totally flat when using doubles to do the math because doubles won't overflow like integers (preserving least significant bits) but instead attempt to preserve the magnitude of the result (preserving most significant bits) and that screws with the design of almost any hash function.
The few ways I've found to deal with this are to
- Modulo the input before multiplying to make sure the result doesn't exceed Number.MAX_SAFE_INTEGER
- Do the multiplication after splitting the input into two 16 bit values and recombine
- Use a variety of magic numbers depending on the input to make sure I stay in doubles range of integers
Problem is though, none of these are fast and cut the performance into shreds. So, question time: Is there a well performing way to emulate integer overflow behavior in js in case of a multiplication that will almost definitely exceed Number.MAX_SAFE_INTEGER?