unordered/detail/xmx.hpp

0001 /* 32b/64b xmx mix function.
0002  *
0003  * Copyright 2022 Peter Dimov.
0004  * Copyright 2022 Joaquin M Lopez Munoz.
0005  * Distributed under the Boost Software License, Version 1.0.
0006  * (See accompanying file LICENSE_1_0.txt or copy at
0007  * http://www.boost.org/LICENSE_1_0.txt)
0008  *
0009  * See https://www.boost.org/libs/unordered for library home page.
0010  */
0011
0012 #ifndef BOOST_UNORDERED_DETAIL_XMX_HPP
0013 #define BOOST_UNORDERED_DETAIL_XMX_HPP
0014
0015 #include <boost/cstdint.hpp>
0016 #include <climits>
0017 #include <cstddef>
0018
0019 namespace boost{
0020 namespace unordered{
0021 namespace detail{
0022
0023 /* Bit mixer for improvement of statistical properties of hash functions.
0024  * The implementation is different on 64bit and 32bit architectures:
0025  *
0026  *   - 64bit: same as xmx function in
0027  *     http://jonkagstrom.com/bit-mixer-construction/index.html
0028  *   - 32bit: generated by Hash Function Prospector
0029  *     (https://github.com/skeeto/hash-prospector) and selected as the
0030  *     best overall performer in benchmarks of Boost.Unordered flat containers.
0031  *     Score assigned by Hash Prospector: 333.7934929677524
0032  */
0033
0034 #if defined(SIZE_MAX)
0035 #if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
0036 #define BOOST_UNORDERED_64B_ARCHITECTURE /* >64 bits assumed as 64 bits */
0037 #endif
0038 #elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
0039 #if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
0040 #define BOOST_UNORDERED_64B_ARCHITECTURE
0041 #endif
0042 #endif
0043
0044 static inline std::size_t xmx(std::size_t x)noexcept
0045 {
0046 #if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
0047
0048   boost::uint64_t z=(boost::uint64_t)x;
0049
0050   z^=z>>23;
0051   z*=0xff51afd7ed558ccdull;
0052   z^=z>>23;
0053
0054   return (std::size_t)z;
0055
0056 #else /* 32 bits assumed */
0057
0058   x^=x>>18;
0059   x*=0x56b5aaadu;
0060   x^=x>>16;
0061
0062   return x;
0063
0064 #endif
0065 }
0066
0067 #ifdef BOOST_UNORDERED_64B_ARCHITECTURE
0068 #undef BOOST_UNORDERED_64B_ARCHITECTURE
0069 #endif
0070
0071 } /* namespace detail */
0072 } /* namespace unordered */
0073 } /* namespace boost */
0074
0075 #endif