1 #ifndef MSP_CORE_HASH_H_
2 #define MSP_CORE_HASH_H_
10 template<unsigned N, unsigned L = 3+(N>8)+(N>16)+(N>32)+(N>64)>
14 struct HashTraits<64, 6>
16 using HashType = uint64_t;
17 using ResultType = uint64_t;
18 static constexpr HashType prime = 1099511628211ULL;
19 static constexpr HashType offset = 14695981039346656037ULL;
20 static constexpr bool folded = false;
24 struct HashTraits<32, 5>
26 using HashType = uint32_t;
27 using ResultType = uint32_t;
28 static constexpr HashType prime = 16777619;
29 static constexpr HashType offset = 2166136261U;
30 static constexpr bool folded = false;
34 struct HashTraits<N, 6>
36 using HashType = uint64_t;
37 using ResultType = uint64_t;
38 static constexpr bool folded = true;
42 struct HashTraits<N, 5>
44 using HashType = uint32_t;
45 using ResultType = uint32_t;
46 static constexpr bool folded = true;
50 struct HashTraits<N, 4>
52 using HashType = uint32_t;
53 using ResultType = uint16_t;
54 static constexpr bool folded = true;
58 struct HashTraits<N, 3>
60 using HashType = uint32_t;
61 using ResultType = uint8_t;
62 static constexpr bool folded = true;
67 Manually folds a hash to a smaller size.
69 template<unsigned N, typename T>
70 typename std::enable_if<N!=std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
71 { return (hash>>N ^ hash) & ((T(1)<<N)-1); }
73 template<unsigned N, typename T>
74 typename std::enable_if<N==std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
78 Computes an N-bit Fowler-Noll-Vo (FNV-1a) hash. If N is not a native hash
79 size, the next larger native hash is computed and XOR-folding is applied to
82 http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
83 http://www.isthe.com/chongo/tech/comp/fnv/index.html
86 typename HashTraits<N>::ResultType hash(const void *data, std::size_t size)
88 constexpr unsigned hash_bits = std::numeric_limits<typename HashTraits<N>::HashType>::digits;
89 constexpr typename HashTraits<N>::HashType prime = HashTraits<hash_bits>::prime;
90 typename HashTraits<N>::HashType result = HashTraits<hash_bits>::offset;
91 for(unsigned i=0; i<size; ++i)
92 result = (result^*(reinterpret_cast<const unsigned char *>(data)+i))*prime;
93 if(HashTraits<N>::folded)
94 result = hash_fold<N>(result);
99 Convenience function to compute an N-bit hash of a string.
102 typename HashTraits<N>::ResultType hash(const std::string &str)
103 { return hash<N>(str.data(), str.size()); }