128-bit and 256-bit variants of "ASM hashes"

[DonaldTsang]

64 bits of hash is too small for large amounts of data, due to hash collisions being more common. It would be great if there are longer options.

[lmcilroy]

6 out of the 10 algorithms produce 128-bit hashes. The ones that don't would be significantly slower if they needed to produce larger hash values. The AVX variants could naturally support 256 bit hashes with a little bit of work.

[DonaldTsang]

For reference this is why I suggested the idea Cyan4973/xxHash#257
Also which 6 of the 10? And out of the 6, which can be modified to support 256-bit variants?

[lmcilroy]

SSEHash, SSEHash2, CLMHash, AVXHash, AVXHash2 and AESHash all produce 128-bit hashes.

I've just added MLXHash2 and AVXHash3 which both produce 256-bit hashes. Despite producing a larger hash AVXHash3 is also the fastest algorithm in the suite.

It would be trivial to provide variants of the other algorithms so they also produce 256-bit hashes but they wouldn't be as fast. I'm sure 512-bit or even 1024-bit would be possible too.

[DonaldTsang]

Thanks for the help, also there are some questions I would like to raise:

1. Are SSE and AVX "bigger integer" Instruction sets?
2. What about MLX, CLM and others, are those for "smaller integers" that are greater than 64-bits?
3. Is it possible to user AES-NI to construct a hash longer than 256-bit similar to the schemes of Groestl (structurally similar) or ECHO/SHAVite3 (which uses AES-NI sub-components)

[lmcilroy]

SSE and AVX are vectorised instructions. You can do the same operations as with general purpose registers but instead do multiple operations in parallel. For example a 128-bit SSE register allows 8 parallel 16-bit operations or 4 parallel 32-bit operations or 2 parallel 64-bit operations. AVX allows double that. The algorithms here make use of 16-bit and 32-bit multiplication so could be considered smaller integer operations.

The MLX and CLM algorithms both utilise the multiplication of two 64-bit numbers into a 128-bit result so they could be considered bigger integer operations.

You could use AES-NI as the mixing function for a hash algorithm that produces hashes of any size. It's just a matter of mixing between the AES-NI registers. Grostl is based on the same primitives as AES but uses wider arrays than is supported by the AES-NI instructions. SHAvite-3 (as far as I can tell) uses standard AES rounds on concurrent streams and then mixes across them in a particular order. ECHO is like AES squared where it uses an AES like array structure but each element in the array is an AES structure itself.