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;
66 Computes a single round of a hash, adding one byte of data. N must be a native
70 typename HashTraits<N>::ResultType hash_round(typename HashTraits<N>::HashType result, uint8_t byte)
72 constexpr typename HashTraits<N>::HashType prime = HashTraits<N>::prime;
73 return (result^byte)*prime;
77 Updates a previously computed hash by adding bytes to it. N must be a native
81 typename HashTraits<N>::ResultType hash_update(typename HashTraits<N>::HashType result, const void *data, std::size_t size)
83 const uint8_t *ptr = static_cast<const uint8_t *>(data);
84 for(unsigned i=0; i<size; ++i)
85 result = hash_round<N>(result, *ptr++);
90 typename HashTraits<N>::ResultType hash_update(typename HashTraits<N>::HashType result, const std::string &str)
91 { return hash_update<N>(result, str.data(), str.size()); }
93 // For some reason this causes an ambiguity error without the enable_if.
94 template<unsigned N, typename T>
95 typename std::enable_if<!std::is_same<T, std::string>::value, typename HashTraits<N>::ResultType>::type hash_update(typename HashTraits<N>::HashType result, const T &obj)
96 { return hash_update<N>(result, &obj, sizeof(obj)); }
99 Manually folds a hash to a smaller size.
101 template<unsigned N, typename T>
102 typename std::enable_if<N!=std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
103 { return (hash>>N ^ hash) & ((T(1)<<N)-1); }
105 template<unsigned N, typename T>
106 typename std::enable_if<N==std::numeric_limits<T>::digits, typename HashTraits<N>::ResultType>::type hash_fold(T hash)
110 Computes an N-bit Fowler-Noll-Vo (FNV-1a) hash. If N is not a native hash
111 size, the next larger native hash is computed and XOR-folding is applied to
114 http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
115 http://www.isthe.com/chongo/tech/comp/fnv/index.html
118 typename HashTraits<N>::ResultType hash(const void *data, std::size_t size)
120 constexpr unsigned hash_bits = std::numeric_limits<typename HashTraits<N>::HashType>::digits;
121 typename HashTraits<N>::HashType result = hash_update<hash_bits>(HashTraits<hash_bits>::offset, data, size);
122 if(HashTraits<N>::folded)
123 result = hash_fold<N>(result);
128 Convenience function to compute an N-bit hash of a string.
131 typename HashTraits<N>::ResultType hash(const std::string &str)
132 { return hash<N>(str.data(), str.size()); }
135 Convenience function to compute an N-bit hash of any object. The entire object
136 representation is hashed, including any padding bytes.
138 template<unsigned N, typename T>
139 typename HashTraits<N>::ResultType hash(const T &obj)
140 { return hash<N>(&obj, sizeof(obj)); }