1// Copyright 2022 Peter Dimov
2// Distributed under the Boost Software License, Version 1.0.
3// https://www.boost.org/LICENSE_1_0.txt
4
5#ifndef BOOST_HASH_DETAIL_HASH_MIX_HPP
6#define BOOST_HASH_DETAIL_HASH_MIX_HPP
7
8#include <boost/cstdint.hpp>
9#include <cstddef>
10#include <climits>
11
12namespace boost
13{
14namespace hash_detail
15{
16
17template<std::size_t Bits> struct hash_mix_impl;
18
19// hash_mix for 64 bit size_t
20//
21// The general "xmxmx" form of state of the art 64 bit mixers originates
22// from Murmur3 by Austin Appleby, which uses the following function as
23// its "final mix":
24//
25// k ^= k >> 33;
26// k *= 0xff51afd7ed558ccd;
27// k ^= k >> 33;
28// k *= 0xc4ceb9fe1a85ec53;
29// k ^= k >> 33;
30//
31// (https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp)
32//
33// It has subsequently been improved multiple times by different authors
34// by changing the constants. The most well known improvement is the
35// so-called "variant 13" function by David Stafford:
36//
37// k ^= k >> 30;
38// k *= 0xbf58476d1ce4e5b9;
39// k ^= k >> 27;
40// k *= 0x94d049bb133111eb;
41// k ^= k >> 31;
42//
43// (https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)
44//
45// This mixing function is used in the splitmix64 RNG:
46// http://xorshift.di.unimi.it/splitmix64.c
47//
48// We use Jon Maiga's implementation from
49// http://jonkagstrom.com/mx3/mx3_rev2.html
50//
51// x ^= x >> 32;
52// x *= 0xe9846af9b1a615d;
53// x ^= x >> 32;
54// x *= 0xe9846af9b1a615d;
55// x ^= x >> 28;
56//
57// An equally good alternative is Pelle Evensen's Moremur:
58//
59// x ^= x >> 27;
60// x *= 0x3C79AC492BA7B653;
61// x ^= x >> 33;
62// x *= 0x1C69B3F74AC4AE35;
63// x ^= x >> 27;
64//
65// (https://mostlymangling.blogspot.com/2019/12/stronger-better-morer-moremur-better.html)
66
67template<> struct hash_mix_impl<64>
68{
69 inline static boost::uint64_t fn( boost::uint64_t x )
70 {
71 boost::uint64_t const m = (boost::uint64_t(0xe9846af) << 32) + 0x9b1a615d;
72
73 x ^= x >> 32;
74 x *= m;
75 x ^= x >> 32;
76 x *= m;
77 x ^= x >> 28;
78
79 return x;
80 }
81};
82
83// hash_mix for 32 bit size_t
84//
85// We use the "best xmxmx" implementation from
86// https://github.com/skeeto/hash-prospector/issues/19
87
88template<> struct hash_mix_impl<32>
89{
90 inline static boost::uint32_t fn( boost::uint32_t x )
91 {
92 boost::uint32_t const m1 = 0x21f0aaad;
93 boost::uint32_t const m2 = 0x735a2d97;
94
95 x ^= x >> 16;
96 x *= m1;
97 x ^= x >> 15;
98 x *= m2;
99 x ^= x >> 15;
100
101 return x;
102 }
103};
104
105inline std::size_t hash_mix( std::size_t v )
106{
107 return hash_mix_impl<sizeof(std::size_t) * CHAR_BIT>::fn( x: v );
108}
109
110} // namespace hash_detail
111} // namespace boost
112
113#endif // #ifndef BOOST_HASH_DETAIL_HASH_MIX_HPP
114