1#ifndef BOOST_UNORDERED_DETAIL_MULX_HPP
2#define BOOST_UNORDERED_DETAIL_MULX_HPP
3
4// Copyright 2022 Peter Dimov.
5// Copyright 2022 Joaquin M Lopez Munoz.
6// Distributed under the Boost Software License, Version 1.0.
7// https://www.boost.org/LICENSE_1_0.txt)
8
9#include <boost/cstdint.hpp>
10#include <climits>
11#include <cstddef>
12
13#if defined(_MSC_VER) && !defined(__clang__)
14# include <intrin.h>
15#endif
16
17namespace boost {
18namespace unordered {
19namespace detail {
20
21// Bit mixer based on the mulx primitive
22
23#if defined(_MSC_VER) && defined(_M_X64) && !defined(__clang__)
24
25__forceinline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
26{
27 boost::uint64_t r2;
28 boost::uint64_t r = _umul128( x, y, &r2 );
29 return r ^ r2;
30}
31
32#elif defined(_MSC_VER) && defined(_M_ARM64) && !defined(__clang__)
33
34__forceinline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
35{
36 boost::uint64_t r = x * y;
37 boost::uint64_t r2 = __umulh( x, y );
38 return r ^ r2;
39}
40
41#elif defined(__SIZEOF_INT128__)
42
43inline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
44{
45 __uint128_t r = (__uint128_t)x * y;
46 return (boost::uint64_t)r ^ (boost::uint64_t)( r >> 64 );
47}
48
49#else
50
51inline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
52{
53 boost::uint64_t x1 = (boost::uint32_t)x;
54 boost::uint64_t x2 = x >> 32;
55
56 boost::uint64_t y1 = (boost::uint32_t)y;
57 boost::uint64_t y2 = y >> 32;
58
59 boost::uint64_t r3 = x2 * y2;
60
61 boost::uint64_t r2a = x1 * y2;
62
63 r3 += r2a >> 32;
64
65 boost::uint64_t r2b = x2 * y1;
66
67 r3 += r2b >> 32;
68
69 boost::uint64_t r1 = x1 * y1;
70
71 boost::uint64_t r2 = (r1 >> 32) + (boost::uint32_t)r2a + (boost::uint32_t)r2b;
72
73 r1 = (r2 << 32) + (boost::uint32_t)r1;
74 r3 += r2 >> 32;
75
76 return r1 ^ r3;
77}
78
79#endif
80
81inline boost::uint32_t mulx32( boost::uint32_t x, boost::uint32_t y )
82{
83 boost::uint64_t r = (boost::uint64_t)x * y;
84
85#if defined(__MSVC_RUNTIME_CHECKS)
86
87 return (boost::uint32_t)(r & UINT32_MAX) ^ (boost::uint32_t)(r >> 32);
88
89#else
90
91 return (boost::uint32_t)r ^ (boost::uint32_t)(r >> 32);
92
93#endif
94}
95
96#if defined(SIZE_MAX)
97#if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
98#define BOOST_UNORDERED_64B_ARCHITECTURE /* >64 bits assumed as 64 bits */
99#endif
100#elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
101#if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
102#define BOOST_UNORDERED_64B_ARCHITECTURE
103#endif
104#endif
105
106inline std::size_t mulx( std::size_t x ) noexcept
107{
108#if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
109
110 // multiplier is phi
111 return (std::size_t)mulx64( x: (boost::uint64_t)x, y: 0x9E3779B97F4A7C15ull );
112
113#else /* 32 bits assumed */
114
115 // multiplier from https://arxiv.org/abs/2001.05304
116 return mulx32( x, 0xE817FB2Du );
117
118#endif
119}
120
121#ifdef BOOST_UNORDERED_64B_ARCHITECTURE
122#undef BOOST_UNORDERED_64B_ARCHITECTURE
123#endif
124
125} // namespace detail
126} // namespace unordered
127} // namespace boost
128
129#endif // #ifndef BOOST_UNORDERED_DETAIL_MULX_HPP
130

source code of boost/libs/unordered/include/boost/unordered/detail/mulx.hpp