Low-level hash algorithm primitives and mixing functions. More...

#include <cstdint>
#include "Concepts.h"
#include "Constants.h"
#include "nfx/detail/hashing/Algorithms.inl"

Include dependency graph for Algorithms.h:

This graph shows which files directly or indirectly include this file:

Functions
template<Hash32or64 HashType = uint32_t>
constexpr HashType	nfx::hashing::larson (HashType hash, uint8_t ch) noexcept
	Larson multiplicative hash function: 37 * hash + ch.
template<Hash32or64 HashType = uint32_t, uint64_t FnvPrime = ( sizeof( HashType ) == 4 ? constants::FNV_PRIME_32 : constants::FNV_PRIME_64 )>
constexpr HashType	nfx::hashing::fnv1a (HashType hash, uint8_t ch) noexcept
	Computes one step of the FNV-1a hash function.
uint32_t	nfx::hashing::crc32c (uint32_t hash, uint8_t ch) noexcept
	Computes one step of the CRC32-C hash function with runtime hardware acceleration.
constexpr uint32_t	nfx::hashing::crc32cSoft (uint32_t hash, uint8_t ch) noexcept
	Software implementation of CRC32-C (Castagnoli) hash function.
template<Hash32or64 HashType = uint32_t, uint64_t MixConstant = constants::SEED_MIX_MULTIPLIER_64>
constexpr HashType	nfx::hashing::seedMix (HashType seed, HashType hash, uint64_t size) noexcept
	Mixes a seed value with a hash using bit-mixing and multiplicative hashing.
template<Hash32or64 HashType = uint32_t>
constexpr HashType	nfx::hashing::combine (HashType existingHash, HashType newHash, HashType prime) noexcept
	Combines two hash values using FNV-1a mixing.
template<Hash32or64 HashType = uint32_t>
constexpr HashType	nfx::hashing::combine (HashType existingHash, HashType newHash) noexcept
	Combines two hash values using Boost hash_combine with MurmurHash3 finalizer.

Detailed Description

Low-level hash algorithm primitives and mixing functions.

Provides core hash building blocks including Larson, FNV-1a, CRC32-C, seed mixing, and hash combination operations for use across hash implementations

Definition in file Algorithms.h.

Function Documentation

◆ combine() [1/2]

template<Hash32or64 HashType = uint32_t>

HashType nfx::hashing::combine	(	HashType	existingHash,
		HashType	newHash )

inlinenodiscardconstexprnoexcept

Combines two hash values using Boost hash_combine with MurmurHash3 finalizer.

Template Parameters

HashType Hash value type - must be uint32_t or uint64_t

Parameters

[in]	existingHash	The current accumulated hash value.
[in]	newHash	The new hash value to combine.

Hybrid algorithm combining Boost's hash_combine formula with MurmurHash3 finalizer.

     **32-bit algorithm:**
     - Uses golden ratio constant (φ = 0x9E3779B9) for uniform distribution
     - Simpler mixing suitable for 32-bit hash values

     **64-bit algorithm:**
     - Phase 1: Boost hash_combine formula with golden ratio constant
     - Phase 2: MurmurHash3 triple avalanche finalization
     - Ensures single-bit changes affect ~50% of output bits

     **Performance:** O(1) with excellent collision resistance and uniform distribution.

Returns: Combined hash value with strong collision resistance and uniform distribution.

See also: https://github.com/aappleby/smhasher/wiki/MurmurHash3; https://www.boost.org/doc/libs/1_89_0/boost/hash2/legacy/murmur3.hpp

Note: This function is marked [[nodiscard]] - the return value should not be ignored

◆ combine() [2/2]

template<Hash32or64 HashType = uint32_t>

HashType nfx::hashing::combine	(	HashType	existingHash,
		HashType	newHash,
		HashType	prime )

inlinenodiscardconstexprnoexcept

Combines two hash values using FNV-1a mixing.

Template Parameters

HashType Hash value type - must be uint32_t or uint64_t

Parameters

[in]	existingHash	The current accumulated hash value.
[in]	newHash	The new hash value to combine.
[in]	prime	The FNV prime constant for mixing.

Uses XOR followed by multiplication for optimal bit mixing.

Returns: Combined hash value with good distribution properties.

Note: This function is marked [[nodiscard]] - the return value should not be ignored

◆ crc32c()

uint32_t nfx::hashing::crc32c	(	uint32_t	hash,
		uint8_t	ch )

inlinenodiscardnoexcept

Computes one step of the CRC32-C hash function with runtime hardware acceleration.

Parameters

[in]	hash	The current hash value.
[in]	ch	The character (byte) to incorporate into the hash.

Returns: The updated hash value.

This function uses SSE4.2 hardware instructions (_mm_crc32_u8) when available. Falls back to crc32cSoft() if CPU doesn't support SSE4.2.

Warning

Compiler flags required for hardware acceleration:

GCC/Clang: -march=native or -msse4.2
MSVC: /arch:AVX or /arch:AVX2 Without these flags, the compiler won't emit SSE4.2 instructions even if the CPU supports them, resulting in software fallback performance.

See also: https://en.wikipedia.org/wiki/Cyclic_redundancy_check; https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm_crc32_u8

Note: This function is marked [[nodiscard]] - the return value should not be ignored

◆ crc32cSoft()

uint32_t nfx::hashing::crc32cSoft	(	uint32_t	hash,
		uint8_t	ch )

inlinenodiscardconstexprnoexcept

Software implementation of CRC32-C (Castagnoli) hash function.

Parameters

[in]	hash	The current hash value.
[in]	ch	The character (byte) to incorporate into the hash.

Returns: The updated hash value.

Pure software implementation using reflected polynomial (0x82F63B78). Produces identical results to SSE4.2 hardware instructions. Useful for testing, benchmarking, or when hardware acceleration is unavailable.

See also: https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Note: This function is marked [[nodiscard]] - the return value should not be ignored

◆ fnv1a()

template<Hash32or64 HashType = uint32_t, uint64_t FnvPrime = ( sizeof( HashType ) == 4 ? constants::FNV_PRIME_32 : constants::FNV_PRIME_64 )>

HashType nfx::hashing::fnv1a	(	HashType	hash,
		uint8_t	ch )

inlinenodiscardconstexprnoexcept

Computes one step of the FNV-1a hash function.

Template Parameters

HashType	Hash value type - must be uint32_t or uint64_t
FnvPrime	The FNV prime constant for mixing (default: FNV_PRIME_32 for 32-bit, FNV_PRIME_64 for 64-bit)

Parameters

[in]	hash	The current hash value.
[in]	ch	The character (byte) to incorporate into the hash.

Returns: The updated hash value.

See also: https://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function

Note: This function is marked [[nodiscard]] - the return value should not be ignored

◆ larson()

template<Hash32or64 HashType = uint32_t>

HashType nfx::hashing::larson	(	HashType	hash,
		uint8_t	ch )

inlinenodiscardconstexprnoexcept

Larson multiplicative hash function: 37 * hash + ch.

Simple hash by Paul Larson, provided for benchmarking.

Template Parameters

HashType Hash value type - must be uint32_t or uint64_t

Parameters

hash	Current hash value to update
ch	Character (byte) to incorporate into the hash

Returns: Updated hash value after incorporating the character

See also: Paul Larson, "The Art of Computer Programming"

Note: This function is marked [[nodiscard]] - the return value should not be ignored

◆ seedMix()

template<Hash32or64 HashType = uint32_t, uint64_t MixConstant = constants::SEED_MIX_MULTIPLIER_64>

HashType nfx::hashing::seedMix	(	HashType	seed,
		HashType	hash,
		uint64_t	size )

inlinenodiscardconstexprnoexcept

Mixes a seed value with a hash using bit-mixing and multiplicative hashing.

Combines a seed and hash value using Thomas Wang's bit-mixing algorithm followed by multiplicative hashing to produce a well-distributed output value within a specified range. The result is deterministic and suitable for hash table probing, double hashing, or any seed-based rehashing scheme.

Template Parameters

HashType	Hash value type - must be uint32_t or uint64_t
MixConstant	Multiplicative hashing constant

Parameters

seed	Additional entropy source to mix with the hash
hash	Primary hash value to be mixed
size	Output range - must be a power of 2

Note: This function is marked [[nodiscard]] - the return value should not be ignored

Returns: Mixed hash value in range [0, size-1]

Functions

Detailed Description

Function Documentation

◆ combine() [1/2]

◆ combine() [2/2]

◆ crc32c()

◆ crc32cSoft()

◆ fnv1a()

◆ larson()

◆ seedMix()