From cf20196055ed5074c448a16144c47b7e8a32c6a8 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Sun, 4 Sep 2011 22:17:38 +0300 Subject: [PATCH] Hash functions --- source/core/hash.cpp | 49 ++++++++++++++++++++++++++++++++++++++++++++ source/core/hash.h | 41 ++++++++++++++++++++++++++++++++++++ 2 files changed, 90 insertions(+) create mode 100644 source/core/hash.cpp create mode 100644 source/core/hash.h diff --git a/source/core/hash.cpp b/source/core/hash.cpp new file mode 100644 index 0000000..26e6059 --- /dev/null +++ b/source/core/hash.cpp @@ -0,0 +1,49 @@ +#include +#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 +*/ + +unsigned 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(data)+i))*prime; + + if(bits<32) + result = (result>>bits ^ result) & ((1<64) + throw invalid_argument("hash64"); + + static const HashValue64 prime = 1099511628211ULL; + static const HashValue64 offset = 14695981039346656037ULL; + + HashValue64 result = offset; + for(unsigned i=0; i(data)+i))*prime; + + if(bits<64) + result = (result>>bits ^ result) & ((1ULL< + +namespace Msp { + +#ifdef WIN32 +typedef __uint64 HashValue64; +#else +typedef unsigned long long HashValue64; +#endif + +/** +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. +*/ +unsigned hash32(const void *, unsigned, unsigned = 32); + +/** +Convenience function to compute a 32-bit hash of a string. +*/ +inline unsigned hash32(const std::string &s, unsigned b = 32) +{ return hash32(s.data(), s.size(), b); } + +/** +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. +*/ +HashValue64 hash64(const void *, unsigned, unsigned = 64); + +/** +Convenience function to compute a 64-bit hash of a string. +*/ +inline HashValue64 hash64(const std::string &s, unsigned b = 64) +{ return hash64(s.data(), s.size(), b); } + +} // namespace Msp + +#endif -- 2.45.2