xxhash

32-bit hash functions

XXH3_accumulate_512 is the tightest loop for long inputs, and it is the most optimized. *

• It is a hardened version of UMAC, based off of FARSH's implementation.

*

• This was chosen because it adapts quite well to 32-bit, 64-bit, and SIMD
• implementations, and it is ridiculously fast.

*

• We harden it by mixing the original input to the accumulators as well as the product.

*

• This means that in the (relatively likely) case of a multiply by zero, the
• original input is preserved.

*

• On 128-bit inputs, we swap 64-bit pairs when we add the input to improve
• cross-pollination, as otherwise the upper and lower halves would be
• essentially independent.

*

• This doesn't matter on 64-bit hashes since they all get merged together in
• the end, so we skip the extra step.

*

• Both XXH3_64bits and XXH3_128bits use this subroutine.

Streaming state.

IMPORTANT: This structure has a strict alignment requirement of 64 bytes!! **
	Default allocators will align it correctly if created via `new`, as will
	placing this struct on the stack, but if using a custom allocator make sure
	that it handles the alignment correctly!

64-bit hash functions

** XXH3 128-bit variant ** Stored in little endian order, although the fields themselves are in native endianness.

This is the optimal update size for incremental hashing.

Do not change this constant.

false - Use this on platforms where unaligned reads are fast

`true`  - Use this on platforms where unaligned reads are slow

0 - Use memcopy, for platforms where unaligned reads are a problem

2 - Direct cast, for platforms where unaligned are allowed (default)

XXH3 New generation hash designed for speed on small keys and vectorization One goal of XXH3 is to make it fast on both 32-bit and 64-bit, while remaining a true 64-bit/128-bit hash function. ========================================== XXH3 default settings ========================================== Custom secrets have a default length of 192, but can be set to a different size.

The minimum secret size is 136 bytes. It must also be a multiple of 64.

======= Long Keys =======

Version definition

A bit slower than XXH3_mix16B, but handles multiply by zero better.

Mix all bits

Canonical representation

The default return values from XXH functions are unsigned 32 and 64 bit integers.

	The canonical representation uses big endian convention,
	the same convention as human-readable numbers (large digits first).

	This way, hash values can be written into a file or buffer, remaining
	comparable across different systems.

	The following functions allow transformation of hash values to and from their
	canonical format.

Hash streaming

====== Canonical representation ======

=== Public XXH128 API ===

=== XXH3 128-bit streaming ===

All the functions are actually the same as for 64-bit streaming variant.
	The only difference is the finalization routine.

=== Public entry point ===

XXH3_accumulate()

• Loops over XXH3_accumulate_512().
• Assumption: nbStripes will not overflow the secret size

scalar variants - universal

generalized SIMD variants

This is a fast avalanche stage, suitable when input bits are already partially mixed

Note: when XXH3_consumeStripes() is invoked, there must be a guarantee that at least

one more byte must be consumed from input so that the function can blindly consume
	all stripes using the "normal" secret segment.

It's important for performance that XXH3_hashLong is not inlined.

It's important for performance that XXH3_hashLong is not inlined.

It's important for performance that XXH3_hashLong is not inlined.

It's important for performance that XXH3_hashLong is not inlined.

Since the function is not inlined, the compiler may not be able to understand that,
	in some scenarios, its `secret` argument is actually a compile time constant.
	This variant enforces that the compiler can detect that,
	and uses this opportunity to streamline the generated code for better performance.

It's important for performance that XXH3_hashLong is not inlined.

XXH3_hashLong_64b_withSeed():

Generate a custom key based on alteration of default XXH3_kSecret with the seed,
	and then use this key for long mode hashing.

	This operation is decently fast but nonetheless costs a little bit of time.
	Try to avoid it whenever possible (typically when seed==0).

	It's important for performance that XXH3_hashLong is not inlined. Not sure
	why (uop cache maybe?), but the difference is large and easily measurable.

=== XXH3 streaming ===

Assumption: secret size is >= XXH3_SECRET_SIZE_MIN

For mid range keys, XXH3 uses a Mum-hash variant.

==========================================

	   XXH3 128 bits (a.k.a XXH128)
	==========================================
	XXH3's 128-bit variant has better mixing and strength than the 64-bit variant,
	even without counting the significantly larger output size.

	For example, extra steps are taken to avoid the seed-dependent collisions
	in 17-240 byte inputs (See XXH3_mix16B and XXH128_mix32B).

	This strength naturally comes at the cost of some speed, especially on short
	lengths. Note that longer hashes are about as fast as the 64-bit version
	due to it using only a slight modification of the 64-bit loop.

	XXH128 is also more oriented towards 64-bit machines. It is still extremely
	fast for a _128-bit_ hash on 32-bit (it usually clears XXH64).

==========================================

Short keys
	==========================================
	One of the shortcomings of XXH32 and XXH64 was that their performance was
	sub-optimal on short lengths. It used an iterative algorithm which strongly
	favored lengths that were a multiple of 4 or 8.

	Instead of iterating over individual inputs, we use a set of single shot
	functions which piece together a range of lengths and operate in constant time.
	Additionally, the number of multiplies has been significantly reduced. This
	reduces latency, especially when emulating 64-bit multiplies on 32-bit.

	Depending on the platform, this may or may not be faster than XXH32, but it
	is almost guaranteed to be faster than XXH64.
At very short lengths, there isn't enough input to fully hide secrets, or use the entire secret.

	There is also only a limited amount of mixing we can do before significantly impacting performance.

	Therefore, we use different sections of the secret and always mix two secret samples with an XOR.
	This should have no effect on performance on the seedless or withSeed variants because everything
	_should_ be constant folded by modern compilers.

	The XOR mixing hides individual parts of the secret and increases entropy.
	This adds an extra layer of strength for custom secrets.

DISCLAIMER: There are known seed-dependent multicollisions here due to

multiplication by zero, affecting hashes of lengths 17 to 240.

	However, they are very unlikely.

	Keep this in mind when using the unseeded XXH3_64bits() variant: As with all
	unseeded non-cryptographic hashes, it does not attempt to defend itself
	against specially crafted inputs, only random inputs.

	Compared to classic UMAC where a 1 in 2^31 chance of 4 consecutive bytes
	cancelling out the secret is taken an arbitrary number of times (addressed
	in XXH3_accumulate_512), this collision is very unlikely with random inputs
	and/or proper seeding:

	This only has a 1 in 2^63 chance of 8 consecutive bytes cancelling out, in a
	function that is only called up to 16 times per hash with up to 240 bytes of
	input.

	This is not too bad for a non-cryptographic hash function, especially with
	only 64 bit outputs.

	The 128-bit variant (which trades some speed for strength) is NOT affected
	by this, although it is always a good idea to use a proper seed if you care
	about strength.

This is a stronger avalanche, inspired by Pelle Evensen's rrmxmx

preferable when input has not been previously mixed

Both XXH3_64bits_update and XXH3_128bits_update use this routine.

Canonical representation

The default return values from XXH functions are unsigned 32 and 64 bit integers.

	The canonical representation uses big endian convention,
	the same convention as human-readable numbers (large digits first).

	This way, hash values can be written into a file or buffer, remaining
	comparable across different systems.

	The following functions allow transformation of hash values to and from their
	canonical format.

Hash Streaming

The reason for the separate function is to prevent passing too many structs

around by value. This will hopefully inline the multiply, but we don't force it.

	@param lhs, rhs The 64-bit integers to multiply
	@return The low 64 bits of the product XOR'd by the high 64 bits.