From: Mikko Rasa <tdb@tdb.fi>
Date: Wed, 17 Nov 2021 12:13:06 +0000 (+0200)
Subject: Rewrite the hash functions to be more generic
X-Git-Url: http://git.tdb.fi/?p=libs%2Fcore.git;a=commitdiff_plain;h=4ad05c650c55e3edccea887d15b26f41cdf60fb6

Rewrite the hash functions to be more generic

The number of bits is now taken as a template parameter and the hash
size is determined automatically.
---

diff --git a/source/core/hash.cpp b/source/core/hash.cpp
deleted file mode 100644
index aed9ed1..0000000
--- a/source/core/hash.cpp
+++ /dev/null
@@ -1,49 +0,0 @@
-#include <stdexcept>
-#include "hash.h"
-
-using namespace std;
-
-namespace Msp {
-
-/*
-http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
-http://www.isthe.com/chongo/tech/comp/fnv/index.html
-*/
-
-uint32_t hash32(const void *data, unsigned size, unsigned bits)
-{
-	if(bits==0 || bits>32)
-		throw invalid_argument("hash32");
-
-	static const unsigned prime = 16777619;
-	static const unsigned offset = 2166136261U;
-
-	unsigned result = offset;
-	for(unsigned i=0; i<size; ++i)
-		result = (result^*(reinterpret_cast<const unsigned char *>(data)+i))*prime;
-
-	if(bits<32)
-		result = (result>>bits ^ result) & ((1<<bits)-1);
-
-	return result;
-}
-
-uint64_t hash64(const void *data, unsigned size, unsigned bits)
-{
-	if(bits==0 || bits>64)
-		throw invalid_argument("hash64");
-
-	static const uint64_t prime = 1099511628211ULL;
-	static const uint64_t offset = 14695981039346656037ULL;
-
-	uint64_t result = offset;
-	for(unsigned i=0; i<size; ++i)
-		result = (result^*(reinterpret_cast<const unsigned char *>(data)+i))*prime;
-
-	if(bits<64)
-		result = (result>>bits ^ result) & ((1ULL<<bits)-1);
-
-	return result;
-}
-
-} // namespace Msp
diff --git a/source/core/hash.h b/source/core/hash.h
index 85ee5dd..a7e8cb1 100644
--- a/source/core/hash.h
+++ b/source/core/hash.h
@@ -2,40 +2,105 @@
 #define MSP_CORE_HASH_H_
 
 #include <cstdint>
+#include <limits>
 #include <string>
 
 namespace Msp {
 
-/**
-Computes a 32-bit Fowler-Noll-Vo (FNV-1a) hash.  The number of bits can be
-limited to less than 32, in which case XOR-folding is used to reduce the hash
-size.
-*/
-std::uint32_t hash32(const void *, unsigned, unsigned = 32);
+template<unsigned N, unsigned L = 3+(N>8)+(N>16)+(N>32)+(N>64)>
+struct HashTraits;
+
+template<>
+struct HashTraits<64, 6>
+{
+	using HashType = uint64_t;
+	using ResultType = uint64_t;
+	static constexpr HashType prime = 1099511628211ULL;
+	static constexpr HashType offset = 14695981039346656037ULL;
+	static constexpr bool folded = false;
+};
+
+template<>
+struct HashTraits<32, 5>
+{
+	using HashType = uint32_t;
+	using ResultType = uint32_t;
+	static constexpr HashType prime = 16777619;
+	static constexpr HashType offset = 2166136261U;
+	static constexpr bool folded = false;
+};
+
+template<unsigned N>
+struct HashTraits<N, 6>
+{
+	using HashType = uint64_t;
+	using ResultType = uint64_t;
+	static constexpr bool folded = true;
+};
+
+template<unsigned N>
+struct HashTraits<N, 5>
+{
+	using HashType = uint32_t;
+	using ResultType = uint32_t;
+	static constexpr bool folded = true;
+};
+
+template<unsigned N>
+struct HashTraits<N, 4>
+{
+	using HashType = uint32_t;
+	using ResultType = uint16_t;
+	static constexpr bool folded = true;
+};
+
+template<unsigned N>
+struct HashTraits<N, 3>
+{
+	using HashType = uint32_t;
+	using ResultType = uint8_t;
+	static constexpr bool folded = true;
+};
+
 
 /**
-Convenience function to compute a 32-bit hash of a string.
+Manually folds a hash to a smaller size.
 */
-inline unsigned hash32(const std::string &s, unsigned b = 32)
-{ return hash32(s.data(), s.size(), b); }
+template<unsigned N, typename T>
+typename std::enable_if<N!=std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
+{ return (hash>>N ^ hash) & ((T(1)<<N)-1); }
+
+template<unsigned N, typename T>
+typename std::enable_if<N==std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
+{ return hash; }
 
 /**
-Computes a 64-bit Fowler-Noll-Vo (FNV-1a) hash.  Note that even if bits is
-limited to 32 or less, this does not produce the same result as hash32.
+Computes an N-bit Fowler-Noll-Vo (FNV-1a) hash.  If N is not a native hash
+size, the next larger native hash is computed and XOR-folding is applied to
+the result.
+
+http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
+http://www.isthe.com/chongo/tech/comp/fnv/index.html
 */
-std::uint64_t hash64(const void *, unsigned, unsigned = 64);
+template<unsigned N>
+typename HashTraits<N>::ResultType hash(const void *data, std::size_t size)
+{
+	constexpr unsigned hash_bits = std::numeric_limits<typename HashTraits<N>::HashType>::digits;
+	constexpr typename HashTraits<N>::HashType prime = HashTraits<hash_bits>::prime;
+	typename HashTraits<N>::HashType result = HashTraits<hash_bits>::offset;
+	for(unsigned i=0; i<size; ++i)
+		result = (result^*(reinterpret_cast<const unsigned char *>(data)+i))*prime;
+	if(HashTraits<N>::folded)
+		result = hash_fold<N>(result);
+	return result;
+}
 
 /**
-Convenience function to compute a 64-bit hash of a string.
+Convenience function to compute an N-bit hash of a string.
 */
-inline std::uint64_t hash64(const std::string &s, unsigned b = 64)
-{ return hash64(s.data(), s.size(), b); }
-
-inline std::uint32_t fold32(std::uint64_t hash)
-{ return hash^(hash>>32); }
-
-inline std::uint16_t fold16(std::uint64_t hash)
-{ return hash^(hash>>16)^(hash>>32)^(hash>>48); }
+template<unsigned N>
+typename HashTraits<N>::ResultType hash(const std::string &str)
+{ return hash<N>(str.data(), str.size()); }
 
 } // namespace Msp