45 #ifndef WPIUTIL_WPI_HASHING_H
46 #define WPIUTIL_WPI_HASHING_H
48 #include "wpi/Endian.h"
49 #include "wpi/SwapByteOrder.h"
50 #include "wpi/type_traits.h"
60 #pragma warning(disable : 26495)
89 operator size_t()
const {
return value; }
92 return lhs.value == rhs.value;
95 return lhs.value != rhs.value;
109 template <
typename T>
110 typename std::enable_if<is_integral_or_enum<T>::value, hash_code>::type
116 template <
typename T> hash_code hash_value(
const T *ptr);
119 template <
typename T,
typename U>
120 hash_code hash_value(
const std::pair<T, U> &arg);
123 template <
typename T>
124 hash_code hash_value(
const std::basic_string<T> &arg);
150 inline uint64_t fetch64(
const char *p) {
152 memcpy(&result, p,
sizeof(result));
153 if (support::endian::system_endianness() == support::big)
154 sys::swapByteOrder(result);
158 inline uint32_t fetch32(
const char *p) {
160 memcpy(&result, p,
sizeof(result));
161 if (support::endian::system_endianness() == support::big)
162 sys::swapByteOrder(result);
167 static const uint64_t k0 = 0xc3a5c85c97cb3127ULL;
168 static const uint64_t k1 = 0xb492b66fbe98f273ULL;
169 static const uint64_t k2 = 0x9ae16a3b2f90404fULL;
170 static const uint64_t k3 = 0xc949d7c7509e6557ULL;
175 inline uint64_t rotate(uint64_t val,
size_t shift) {
177 return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
180 inline uint64_t shift_mix(uint64_t val) {
181 return val ^ (val >> 47);
184 inline uint64_t hash_16_bytes(uint64_t low, uint64_t high) {
186 const uint64_t kMul = 0x9ddfea08eb382d69ULL;
187 uint64_t a = (low ^ high) * kMul;
189 uint64_t b = (high ^ a) * kMul;
195 inline uint64_t hash_1to3_bytes(
const char *s,
size_t len, uint64_t seed) {
197 uint8_t b = s[len >> 1];
198 uint8_t c = s[len - 1];
199 uint32_t y = static_cast<uint32_t>(a) + (static_cast<uint32_t>(b) << 8);
200 uint32_t z = static_cast<uint32_t>(len + (static_cast<uint64_t>(c) << 2));
201 return shift_mix(y * k2 ^ z * k3 ^ seed) * k2;
204 inline uint64_t hash_4to8_bytes(
const char *s,
size_t len, uint64_t seed) {
205 uint64_t a = fetch32(s);
206 return hash_16_bytes(len + (a << 3), seed ^ fetch32(s + len - 4));
209 inline uint64_t hash_9to16_bytes(
const char *s,
size_t len, uint64_t seed) {
210 uint64_t a = fetch64(s);
211 uint64_t b = fetch64(s + len - 8);
212 return hash_16_bytes(seed ^ a, rotate(b + len, len)) ^ b;
215 inline uint64_t hash_17to32_bytes(
const char *s,
size_t len, uint64_t seed) {
216 uint64_t a = fetch64(s) * k1;
217 uint64_t b = fetch64(s + 8);
218 uint64_t c = fetch64(s + len - 8) * k2;
219 uint64_t d = fetch64(s + len - 16) * k0;
220 return hash_16_bytes(rotate(a - b, 43) + rotate(c ^ seed, 30) + d,
221 a + rotate(b ^ k3, 20) - c + len + seed);
224 inline uint64_t hash_33to64_bytes(
const char *s,
size_t len, uint64_t seed) {
225 uint64_t z = fetch64(s + 24);
226 uint64_t a = fetch64(s) + (len + fetch64(s + len - 16)) * k0;
227 uint64_t b = rotate(a + z, 52);
228 uint64_t c = rotate(a, 37);
231 a += fetch64(s + 16);
233 uint64_t vs = b + rotate(a, 31) + c;
234 a = fetch64(s + 16) + fetch64(s + len - 32);
235 z = fetch64(s + len - 8);
236 b = rotate(a + z, 52);
238 a += fetch64(s + len - 24);
240 a += fetch64(s + len - 16);
242 uint64_t ws = b + rotate(a, 31) + c;
243 uint64_t r = shift_mix((vf + ws) * k2 + (wf + vs) * k0);
244 return shift_mix((seed ^ (r * k0)) + vs) * k2;
247 inline uint64_t hash_short(
const char *s,
size_t length, uint64_t seed) {
248 if (length >= 4 && length <= 8)
249 return hash_4to8_bytes(s, length, seed);
250 if (length > 8 && length <= 16)
251 return hash_9to16_bytes(s, length, seed);
252 if (length > 16 && length <= 32)
253 return hash_17to32_bytes(s, length, seed);
255 return hash_33to64_bytes(s, length, seed);
257 return hash_1to3_bytes(s, length, seed);
266 uint64_t h0, h1, h2, h3, h4, h5, h6;
273 0, seed, hash_16_bytes(seed, k1), rotate(seed ^ k1, 49),
274 seed * k1, shift_mix(seed), 0 };
275 state.h6 = hash_16_bytes(state.h4, state.h5);
284 uint64_t c = fetch64(s + 24);
285 b = rotate(b + a + c, 21);
287 a += fetch64(s + 8) + fetch64(s + 16);
288 b += rotate(a, 44) + d;
296 h0 = rotate(h0 + h1 + h3 + fetch64(s + 8), 37) * k1;
297 h1 = rotate(h1 + h4 + fetch64(s + 48), 42) * k1;
299 h1 += h3 + fetch64(s + 40);
300 h2 = rotate(h2 + h5, 33) * k1;
305 h6 = h1 + fetch64(s + 16);
313 return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2,
314 hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0);
324 extern uint64_t fixed_seed_override;
326 inline uint64_t get_execution_seed() {
333 const uint64_t seed_prime = 0xff51afd7ed558ccdULL;
334 static uint64_t seed = fixed_seed_override ? fixed_seed_override : seed_prime;
352 : std::integral_constant<bool, ((is_integral_or_enum<T>::value ||
353 std::is_pointer<T>::value) &&
354 64 % sizeof(T) == 0)> {};
361 : std::integral_constant<bool, (is_hashable_data<T>::value &&
362 is_hashable_data<U>::value &&
363 (sizeof(T) + sizeof(U)) ==
364 sizeof(std::pair<T, U>))> {};
368 template <
typename T>
369 typename std::enable_if<is_hashable_data<T>::value, T>::type
370 get_hashable_data(
const T &value) {
376 template <
typename T>
377 typename std::enable_if<!is_hashable_data<T>::value,
size_t>::type
378 get_hashable_data(
const T &value) {
379 using ::wpi::hash_value;
380 return hash_value(value);
390 template <
typename T>
391 bool store_and_advance(
char *&buffer_ptr,
char *buffer_end,
const T& value,
393 size_t store_size =
sizeof(value) - offset;
394 if (buffer_ptr + store_size > buffer_end)
396 const char *value_data = reinterpret_cast<const char *>(&value);
397 memcpy(buffer_ptr, value_data + offset, store_size);
398 buffer_ptr += store_size;
407 template <
typename InputIteratorT>
408 hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) {
409 const uint64_t seed = get_execution_seed();
410 char buffer[64], *buffer_ptr = buffer;
411 char *
const buffer_end = std::end(buffer);
412 while (first != last && store_and_advance(buffer_ptr, buffer_end,
413 get_hashable_data(*first)))
416 return hash_short(buffer, buffer_ptr - buffer, seed);
417 assert(buffer_ptr == buffer_end);
419 hash_state state = state.create(buffer, seed);
421 while (first != last) {
425 while (first != last && store_and_advance(buffer_ptr, buffer_end,
426 get_hashable_data(*first)))
432 std::rotate(buffer, buffer_ptr, buffer_end);
436 length += buffer_ptr - buffer;
439 return state.finalize(length);
450 template <
typename ValueT>
451 typename std::enable_if<is_hashable_data<ValueT>::value, hash_code>::type
452 hash_combine_range_impl(ValueT *first, ValueT *last) {
453 const uint64_t seed = get_execution_seed();
454 const char *s_begin = reinterpret_cast<const char *>(first);
455 const char *s_end = reinterpret_cast<const char *>(last);
456 const size_t length = std::distance(s_begin, s_end);
458 return hash_short(s_begin, length, seed);
460 const char *s_aligned_end = s_begin + (length & ~63);
461 hash_state state = state.create(s_begin, seed);
463 while (s_begin != s_aligned_end) {
468 state.mix(s_end - 64);
470 return state.finalize(length);
483 template <
typename InputIteratorT>
485 return ::wpi::hashing::detail::hash_combine_range_impl(first, last);
511 : seed(get_execution_seed()) {}
519 template <
typename T>
520 char *
combine_data(
size_t &length,
char *buffer_ptr,
char *buffer_end, T data) {
521 if (!store_and_advance(buffer_ptr, buffer_end, data)) {
526 size_t partial_store_size = buffer_end - buffer_ptr;
527 memcpy(buffer_ptr, &data, partial_store_size);
534 state = state.
create(buffer, seed);
547 if (!store_and_advance(buffer_ptr, buffer_end, data,
558 template <
typename T,
typename ...Ts>
560 const T &arg,
const Ts &...args) {
561 buffer_ptr =
combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg));
564 return combine(length, buffer_ptr, buffer_end, args...);
576 return static_cast<size_t>(hash_short(buffer, buffer_ptr - buffer, seed));
582 std::rotate(buffer, buffer_ptr, buffer_end);
586 length += buffer_ptr - buffer;
588 return static_cast<size_t>(state.
finalize(length));
609 return helper.
combine(0, helper.buffer, helper.buffer + 64, args...);
622 inline hash_code hash_integer_value(uint64_t value) {
624 const uint64_t seed = get_execution_seed();
625 const char *s = reinterpret_cast<const char *>(&value);
626 const uint64_t a = fetch32(s);
627 return static_cast<size_t>(hash_16_bytes(seed + (a << 3), fetch32(s + 4)));
635 template <
typename T>
636 typename std::enable_if<is_integral_or_enum<T>::value, hash_code>::type
637 hash_value(T value) {
638 return ::wpi::hashing::detail::hash_integer_value(
639 static_cast<uint64_t>(value));
644 template <
typename T>
hash_code hash_value(
const T *ptr) {
645 return ::wpi::hashing::detail::hash_integer_value(
646 reinterpret_cast<uintptr_t>(ptr));
651 template <
typename T,
typename U>
658 template <
typename T>