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

source code of boost/libs/intrusive/include/boost/intrusive/detail/hash_mix.hpp