Non-power-of-two PEAC is almost an entirely different thing. Different behaviour, different applications...
It is a bit slower because the carry wraparound can't be performed with basic masks & shifts. However they can use a prime number, which is known to increase mixing. This is a welcome feature for the cases where you want to calculate a hashed key from a short string (such as a filename, a variable name or a URL/URI).
http://www.burtleburtle.net/bob/hash/doobs.html is an essential, required reading!
PEAC16x2 is not appropriate in this case because the avalanche is too weak. However npo2 PEAC promises to increase this property, by choosing an appropriate modulo. A prime factor is well known "mixer" (?) but I'd have to run heavy tests to prove that this is still the case in this new algorithm. At this moment I'm "harvesting" as many interesting values as I can in order to select good candidates.
For now, I'm going for an algo that processes up to 256 bytes in 2×16-bit chunks. The values should fit in 32-bit registers. In fact the range of values should be the closest possible to a power of two, to reduce the bias that occurs when truncating the MSB. From the Adler32 debacle, we know the modulus must be slightly higher than 65536. But other values are interesting, I'm looking at those around 2^16.5=92681 because the state space reaches 8Gi states and is not too large, and might still provide better mixing than a prime too close to 2^16. Yes, multiplying the Po2 modulus by √2 gives an irrational number, which would be more likely to be binary dense.
Interesting prime candidates: 91159, 91229, 91691, 91771, 91823, 92003, 92219, 92369 (0x168D1), 92761 (0x16A59) 92779 (0x16A6B)....
The closest max orbit to 92681 is 92688 (not a prime) with an orbit length of 4295579015, 24 × 3 × 1931 so there are 4 LSB cleared: 0x16A10 is not very dense... But since the wrap-around adds 1, that's not too bad in the end. (the choice should take into account the average mixing, which depends on the bit density of the number)
Unfortunately, it is not possible to apply the same optimisation as Adler & Fletcher because the accumulators loop back into each other: the "correction" (increment) can't be accumulated separately to be applied at the end. The separate accumulator would have to undergo its own PEAC cycles in parallel... So it's not the very fastest algo but it's simple and grounded in some sort of theoretical framework, unlike many hash algos that try as many permutations of operations and values, hoping to find "a sweet spot" that passes tests.
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.