unordered/detail/prime_fmod.hpp

0001 // Copyright (C) 2022 Joaquin M Lopez Munoz.
0002 // Copyright (C) 2022-2023 Christian Mazakas
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0005 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP
0008 #define BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP
0009
0010 #include <boost/unordered/detail/narrow_cast.hpp>
0011
0012 #include <boost/config.hpp>
0013 #include <boost/cstdint.hpp>
0014
0015 #include <climits>
0016 #include <cstddef>
0017
0018 #if defined(SIZE_MAX)
0019 #if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
0020 #define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
0021 #endif
0022 #elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
0023 #if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
0024 #define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
0025 #endif
0026 #endif
0027
0028 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) && defined(_MSC_VER)
0029 #include <intrin.h>
0030 #endif
0031
0032 namespace boost {
0033   namespace unordered {
0034     namespace detail {
0035       template <class = void> struct prime_fmod_size
0036       {
0037         constexpr static std::size_t const sizes[] = {13ul, 29ul, 53ul, 97ul,
0038           193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
0039           49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul,
0040           6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul,
0041           201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul,
0042 #if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
0043           4294967291ul
0044 #else
0045           6442450939ull, 12884901893ull, 25769803751ull, 51539607551ull,
0046           103079215111ull, 206158430209ull, 412316860441ull, 824633720831ull,
0047           1649267441651ull
0048 #endif
0049         };
0050
0051         constexpr static std::size_t const sizes_len =
0052           sizeof(sizes) / sizeof(sizes[0]);
0053
0054 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
0055         constexpr static boost::uint64_t const inv_sizes32[] = {
0056           1418980313362273202ull, 636094623231363849ull, 348051774975651918ull,
0057           190172619316593316ull, 95578984837873325ull, 47420935922132524ull,
0058           23987963684927896ull, 11955116055547344ull, 5991147799191151ull,
0059           2998982941588287ull, 1501077717772769ull, 750081082979285ull,
0060           375261795343686ull, 187625172388393ull, 93822606204624ull,
0061           46909513691883ull, 23456218233098ull, 11728086747027ull,
0062           5864041509391ull, 2932024948977ull, 1466014921160ull, 733007198436ull,
0063           366503839517ull, 183251896093ull, 91625960335ull, 45812983922ull,
0064           22906489714ull, 11453246088ull, 5726623060ull};
0065
0066         constexpr static std::size_t const inv_sizes32_len =
0067           sizeof(inv_sizes32) / sizeof(inv_sizes32[0]);
0068 #endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
0069
0070         template <std::size_t SizeIndex, std::size_t Size = sizes[SizeIndex]>
0071         static std::size_t position(std::size_t hash)
0072         {
0073           return hash % Size;
0074         }
0075
0076         constexpr static std::size_t (*positions[])(std::size_t) = {
0077 #if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
0078           position<0, sizes[0]>,
0079           position<1, sizes[1]>,
0080           position<2, sizes[2]>,
0081           position<3, sizes[3]>,
0082           position<4, sizes[4]>,
0083           position<5, sizes[5]>,
0084           position<6, sizes[6]>,
0085           position<7, sizes[7]>,
0086           position<8, sizes[8]>,
0087           position<9, sizes[9]>,
0088           position<10, sizes[10]>,
0089           position<11, sizes[11]>,
0090           position<12, sizes[12]>,
0091           position<13, sizes[13]>,
0092           position<14, sizes[14]>,
0093           position<15, sizes[15]>,
0094           position<16, sizes[16]>,
0095           position<17, sizes[17]>,
0096           position<18, sizes[18]>,
0097           position<19, sizes[19]>,
0098           position<20, sizes[20]>,
0099           position<21, sizes[21]>,
0100           position<22, sizes[22]>,
0101           position<23, sizes[23]>,
0102           position<24, sizes[24]>,
0103           position<25, sizes[25]>,
0104           position<26, sizes[26]>,
0105           position<27, sizes[27]>,
0106           position<28, sizes[28]>,
0107           position<29, sizes[29]>,
0108 #else
0109           position<29, sizes[29]>,
0110           position<30, sizes[30]>,
0111           position<31, sizes[31]>,
0112           position<32, sizes[32]>,
0113           position<33, sizes[33]>,
0114           position<34, sizes[34]>,
0115           position<35, sizes[35]>,
0116           position<36, sizes[36]>,
0117           position<37, sizes[37]>,
0118 #endif
0119         };
0120
0121         static inline std::size_t size_index(std::size_t n)
0122         {
0123           std::size_t i = 0;
0124           for (; i < (sizes_len - 1); ++i) {
0125             if (sizes[i] >= n) {
0126               break;
0127             }
0128           }
0129           return i;
0130         }
0131
0132         static inline std::size_t size(std::size_t size_index)
0133         {
0134           return sizes[size_index];
0135         }
0136
0137 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
0138         // We emulate the techniques taken from:
0139         // Faster Remainder by Direct Computation: Applications to Compilers and
0140         // Software Libraries
0141         // https://arxiv.org/abs/1902.01961
0142         //
0143         // In essence, use fancy math to directly calculate the remainder (aka
0144         // modulo) exploiting how compilers transform division
0145         //
0146
0147         static inline boost::uint64_t get_remainder(
0148           boost::uint64_t fractional, boost::uint32_t d)
0149         {
0150 #if defined(_MSC_VER)
0151           // use MSVC intrinsics when available to avoid promotion to 128 bits
0152
0153           return __umulh(fractional, d);
0154 #elif defined(BOOST_HAS_INT128)
0155           return static_cast<boost::uint64_t>(
0156             ((boost::uint128_type)fractional * d) >> 64);
0157 #else
0158           // portable implementation in the absence of boost::uint128_type on 64
0159           // bits, which happens at least in GCC 4.5 and prior
0160
0161           boost::uint64_t r1 = (fractional & UINT32_MAX) * d;
0162           boost::uint64_t r2 = (fractional >> 32) * d;
0163           r2 += r1 >> 32;
0164           return r2 >> 32;
0165 #endif /* defined(_MSC_VER) */
0166         }
0167
0168         static inline boost::uint32_t fast_modulo(
0169           boost::uint32_t a, boost::uint64_t M, boost::uint32_t d)
0170         {
0171           boost::uint64_t fractional = M * a;
0172           return (boost::uint32_t)(get_remainder(fractional, d));
0173         }
0174 #endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
0175
0176         static inline std::size_t position(
0177           std::size_t hash, std::size_t size_index)
0178         {
0179 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
0180           std::size_t sizes_under_32bit = inv_sizes32_len;
0181           if (BOOST_LIKELY(size_index < sizes_under_32bit)) {
0182             return fast_modulo(narrow_cast<boost::uint32_t>(hash) +
0183                                  narrow_cast<boost::uint32_t>(hash >> 32),
0184               inv_sizes32[size_index], boost::uint32_t(sizes[size_index]));
0185           } else {
0186             return positions[size_index - sizes_under_32bit](hash);
0187           }
0188 #else
0189           return positions[size_index](hash);
0190 #endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
0191         }
0192       }; // prime_fmod_size
0193
0194 #if defined(BOOST_NO_CXX17_INLINE_VARIABLES)
0195       // https://en.cppreference.com/w/cpp/language/static#Constant_static_members
0196       // If a const non-inline (since C++17) static data member or a constexpr
0197       // static data member (since C++11)(until C++17) is odr-used, a definition
0198       // at namespace scope is still required, but it cannot have an
0199       // initializer.
0200       template <class T> constexpr std::size_t prime_fmod_size<T>::sizes[];
0201
0202 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
0203       template <class T>
0204       constexpr boost::uint64_t prime_fmod_size<T>::inv_sizes32[];
0205 #endif
0206
0207       template <class T>
0208       constexpr std::size_t (*prime_fmod_size<T>::positions[])(std::size_t);
0209 #endif
0210     } // namespace detail
0211   } // namespace unordered
0212 } // namespace boost
0213
0214 #endif // BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP