1// Copyright (C) 2022 Joaquin M Lopez Munoz.
2// Copyright (C) 2022-2023 Christian Mazakas
3//
4// Distributed under the Boost Software License, Version 1.0. (See accompanying
5// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7#ifndef BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP
8#define BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP
9
10#include <boost/unordered/detail/narrow_cast.hpp>
11
12#include <boost/config.hpp>
13#include <boost/cstdint.hpp>
14
15#include <climits>
16#include <cstddef>
17
18#if defined(SIZE_MAX)
19#if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
20#define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
21#endif
22#elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
23#if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
24#define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
25#endif
26#endif
27
28#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) && defined(_MSC_VER)
29#include <intrin.h>
30#endif
31
32namespace boost {
33 namespace unordered {
34 namespace detail {
35 template <class = void> struct prime_fmod_size
36 {
37 constexpr static std::size_t const sizes[] = {13ul, 29ul, 53ul, 97ul,
38 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
39 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul,
40 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul,
41 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul,
42#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
43 4294967291ul
44#else
45 6442450939ull, 12884901893ull, 25769803751ull, 51539607551ull,
46 103079215111ull, 206158430209ull, 412316860441ull, 824633720831ull,
47 1649267441651ull
48#endif
49 };
50
51 constexpr static std::size_t const sizes_len =
52 sizeof(sizes) / sizeof(sizes[0]);
53
54#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
55 constexpr static boost::uint64_t const inv_sizes32[] = {
56 1418980313362273202ull, 636094623231363849ull, 348051774975651918ull,
57 190172619316593316ull, 95578984837873325ull, 47420935922132524ull,
58 23987963684927896ull, 11955116055547344ull, 5991147799191151ull,
59 2998982941588287ull, 1501077717772769ull, 750081082979285ull,
60 375261795343686ull, 187625172388393ull, 93822606204624ull,
61 46909513691883ull, 23456218233098ull, 11728086747027ull,
62 5864041509391ull, 2932024948977ull, 1466014921160ull, 733007198436ull,
63 366503839517ull, 183251896093ull, 91625960335ull, 45812983922ull,
64 22906489714ull, 11453246088ull, 5726623060ull};
65
66 constexpr static std::size_t const inv_sizes32_len =
67 sizeof(inv_sizes32) / sizeof(inv_sizes32[0]);
68#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
69
70 template <std::size_t SizeIndex, std::size_t Size = sizes[SizeIndex]>
71 static std::size_t position(std::size_t hash)
72 {
73 return hash % Size;
74 }
75
76 constexpr static std::size_t (*positions[])(std::size_t) = {
77#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
78 position<0, sizes[0]>,
79 position<1, sizes[1]>,
80 position<2, sizes[2]>,
81 position<3, sizes[3]>,
82 position<4, sizes[4]>,
83 position<5, sizes[5]>,
84 position<6, sizes[6]>,
85 position<7, sizes[7]>,
86 position<8, sizes[8]>,
87 position<9, sizes[9]>,
88 position<10, sizes[10]>,
89 position<11, sizes[11]>,
90 position<12, sizes[12]>,
91 position<13, sizes[13]>,
92 position<14, sizes[14]>,
93 position<15, sizes[15]>,
94 position<16, sizes[16]>,
95 position<17, sizes[17]>,
96 position<18, sizes[18]>,
97 position<19, sizes[19]>,
98 position<20, sizes[20]>,
99 position<21, sizes[21]>,
100 position<22, sizes[22]>,
101 position<23, sizes[23]>,
102 position<24, sizes[24]>,
103 position<25, sizes[25]>,
104 position<26, sizes[26]>,
105 position<27, sizes[27]>,
106 position<28, sizes[28]>,
107 position<29, sizes[29]>,
108#else
109 position<29, sizes[29]>,
110 position<30, sizes[30]>,
111 position<31, sizes[31]>,
112 position<32, sizes[32]>,
113 position<33, sizes[33]>,
114 position<34, sizes[34]>,
115 position<35, sizes[35]>,
116 position<36, sizes[36]>,
117 position<37, sizes[37]>,
118#endif
119 };
120
121 static inline std::size_t size_index(std::size_t n)
122 {
123 std::size_t i = 0;
124 for (; i < (sizes_len - 1); ++i) {
125 if (sizes[i] >= n) {
126 break;
127 }
128 }
129 return i;
130 }
131
132 static inline std::size_t size(std::size_t size_index)
133 {
134 return sizes[size_index];
135 }
136
137#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
138 // We emulate the techniques taken from:
139 // Faster Remainder by Direct Computation: Applications to Compilers and
140 // Software Libraries
141 // https://arxiv.org/abs/1902.01961
142 //
143 // In essence, use fancy math to directly calculate the remainder (aka
144 // modulo) exploiting how compilers transform division
145 //
146
147 static inline boost::uint64_t get_remainder(
148 boost::uint64_t fractional, boost::uint32_t d)
149 {
150#if defined(_MSC_VER)
151 // use MSVC intrinsics when available to avoid promotion to 128 bits
152
153 return __umulh(fractional, d);
154#elif defined(BOOST_HAS_INT128)
155 return static_cast<boost::uint64_t>(
156 ((boost::uint128_type)fractional * d) >> 64);
157#else
158 // portable implementation in the absence of boost::uint128_type on 64
159 // bits, which happens at least in GCC 4.5 and prior
160
161 boost::uint64_t r1 = (fractional & UINT32_MAX) * d;
162 boost::uint64_t r2 = (fractional >> 32) * d;
163 r2 += r1 >> 32;
164 return r2 >> 32;
165#endif /* defined(_MSC_VER) */
166 }
167
168 static inline boost::uint32_t fast_modulo(
169 boost::uint32_t a, boost::uint64_t M, boost::uint32_t d)
170 {
171 boost::uint64_t fractional = M * a;
172 return (boost::uint32_t)(get_remainder(fractional, d));
173 }
174#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
175
176 static inline std::size_t position(
177 std::size_t hash, std::size_t size_index)
178 {
179#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
180 std::size_t sizes_under_32bit = inv_sizes32_len;
181 if (BOOST_LIKELY(size_index < sizes_under_32bit)) {
182 return fast_modulo(a: narrow_cast<boost::uint32_t>(x: hash) +
183 narrow_cast<boost::uint32_t>(x: hash >> 32),
184 M: inv_sizes32[size_index], d: boost::uint32_t(sizes[size_index]));
185 } else {
186 return positions[size_index - sizes_under_32bit](hash);
187 }
188#else
189 return positions[size_index](hash);
190#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
191 }
192 }; // prime_fmod_size
193
194#if defined(BOOST_NO_CXX17_INLINE_VARIABLES)
195 // https://en.cppreference.com/w/cpp/language/static#Constant_static_members
196 // If a const non-inline (since C++17) static data member or a constexpr
197 // static data member (since C++11)(until C++17) is odr-used, a definition
198 // at namespace scope is still required, but it cannot have an
199 // initializer.
200 template <class T> constexpr std::size_t prime_fmod_size<T>::sizes[];
201
202#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
203 template <class T>
204 constexpr boost::uint64_t prime_fmod_size<T>::inv_sizes32[];
205#endif
206
207 template <class T>
208 constexpr std::size_t (*prime_fmod_size<T>::positions[])(std::size_t);
209#endif
210 } // namespace detail
211 } // namespace unordered
212} // namespace boost
213
214#endif // BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP
215

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