Add new XMSX Hash - Githubissues

rurban / smhasher

Hash function quality and speed tests

https://rurban.github.io/smhasher/

Other

1.86k stars 179 forks source link

Add new XMSX Hash #280

Closed dlebed closed 1 year ago

dlebed commented 1 year ago

XMSX (XOR - Multiply - Shift - XOR) Hash Inspired by MUM and Murmur hashes

Design inputs:

be faster than SW CRC32 on modern 32-bit CPUs (and microcontrollers) (supporting HW 32bx32b->64b multiplication)
be as simple as possible (small code size)
try to reuse the same core round function (xor-mul-shift-xor)
provide reasonable hashing quality (pass SMHasher tests)

XMSX32 passes all SMHasher tests (2 bad seeds) XMSX64 currently fails one MomentChi2 test (might be fixed later)

rurban commented 1 year ago

It's extremely small, not particularly fast, but without the original MUM problems. The 64bit variant uses a very bad high word mixing.

dlebed commented 1 year ago

Thanks @rurban. Initially my goal was to get a small good enough hash for 32-bit platforms to use instead of byte-wise CRC32. On platforms like MCUs and other 32-bit CPUs it is quite fast, but yes, it was not designed to be vectorized or take advantage of 64-bit CPUs. Other "fast" hashes that could vectorized and runs faster on x64 or top ARM cores in reality are quite slower that this simple hash on mid- and low-end 32-bit CPUs. 64-bit version is just a free "add-on", maybe I even should remove it or improve mixing there later, we'l see.

rurban commented 1 year ago

I would just remove it, or use a better mixer for the higher word.

dlebed commented 1 year ago

Makes sense. Let me remove 64-bit version for now. If I'll have time to improve 64-bit version it anyway will be a different hash and could be added later.

Removing xmsx64 for now https://github.com/rurban/smhasher/pull/281