unordered/detail/mulx.hpp

0001 #ifndef BOOST_UNORDERED_DETAIL_MULX_HPP
0002 #define BOOST_UNORDERED_DETAIL_MULX_HPP
0003
0004 // Copyright 2022 Peter Dimov.
0005 // Copyright 2022 Joaquin M Lopez Munoz.
0006 // Distributed under the Boost Software License, Version 1.0.
0007 // https://www.boost.org/LICENSE_1_0.txt)
0008
0009 #include <boost/cstdint.hpp>
0010 #include <climits>
0011 #include <cstddef>
0012
0013 #if defined(_MSC_VER) && !defined(__clang__)
0014 # include <intrin.h>
0015 #endif
0016
0017 namespace boost {
0018 namespace unordered {
0019 namespace detail {
0020
0021 // Bit mixer based on the mulx primitive
0022
0023 #if defined(_MSC_VER) && defined(_M_X64) && !defined(__clang__)
0024
0025 __forceinline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
0026 {
0027     boost::uint64_t r2;
0028     boost::uint64_t r = _umul128( x, y, &r2 );
0029     return r ^ r2;
0030 }
0031
0032 #elif defined(_MSC_VER) && defined(_M_ARM64) && !defined(__clang__)
0033
0034 __forceinline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
0035 {
0036     boost::uint64_t r = x * y;
0037     boost::uint64_t r2 = __umulh( x, y );
0038     return r ^ r2;
0039 }
0040
0041 #elif defined(__SIZEOF_INT128__)
0042
0043 inline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
0044 {
0045     __uint128_t r = (__uint128_t)x * y;
0046     return (boost::uint64_t)r ^ (boost::uint64_t)( r >> 64 );
0047 }
0048
0049 #else
0050
0051 inline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
0052 {
0053     boost::uint64_t x1 = (boost::uint32_t)x;
0054     boost::uint64_t x2 = x >> 32;
0055
0056     boost::uint64_t y1 = (boost::uint32_t)y;
0057     boost::uint64_t y2 = y >> 32;
0058
0059     boost::uint64_t r3 = x2 * y2;
0060
0061     boost::uint64_t r2a = x1 * y2;
0062
0063     r3 += r2a >> 32;
0064
0065     boost::uint64_t r2b = x2 * y1;
0066
0067     r3 += r2b >> 32;
0068
0069     boost::uint64_t r1 = x1 * y1;
0070
0071     boost::uint64_t r2 = (r1 >> 32) + (boost::uint32_t)r2a + (boost::uint32_t)r2b;
0072
0073     r1 = (r2 << 32) + (boost::uint32_t)r1;
0074     r3 += r2 >> 32;
0075
0076     return r1 ^ r3;
0077 }
0078
0079 #endif
0080
0081 inline boost::uint32_t mulx32( boost::uint32_t x, boost::uint32_t y )
0082 {
0083     boost::uint64_t r = (boost::uint64_t)x * y;
0084
0085 #if defined(__MSVC_RUNTIME_CHECKS)
0086
0087     return (boost::uint32_t)(r & UINT32_MAX) ^ (boost::uint32_t)(r >> 32);
0088
0089 #else
0090
0091     return (boost::uint32_t)r ^ (boost::uint32_t)(r >> 32);
0092
0093 #endif
0094 }
0095
0096 #if defined(SIZE_MAX)
0097 #if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
0098 #define BOOST_UNORDERED_64B_ARCHITECTURE /* >64 bits assumed as 64 bits */
0099 #endif
0100 #elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
0101 #if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
0102 #define BOOST_UNORDERED_64B_ARCHITECTURE
0103 #endif
0104 #endif
0105
0106 inline std::size_t mulx( std::size_t x ) noexcept
0107 {
0108 #if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
0109
0110     // multiplier is phi
0111     return (std::size_t)mulx64( (boost::uint64_t)x, 0x9E3779B97F4A7C15ull );
0112
0113 #else /* 32 bits assumed */
0114
0115     // multiplier from https://arxiv.org/abs/2001.05304
0116     return mulx32( x, 0xE817FB2Du );
0117
0118 #endif
0119 }
0120
0121 #ifdef BOOST_UNORDERED_64B_ARCHITECTURE
0122 #undef BOOST_UNORDERED_64B_ARCHITECTURE
0123 #endif
0124
0125 } // namespace detail
0126 } // namespace unordered
0127 } // namespace boost
0128
0129 #endif // #ifndef BOOST_UNORDERED_DETAIL_MULX_HPP