1// Copyright 2022 Christian Mazakas.
2// Distributed under the Boost Software License, Version 1.0. (See accompanying
3// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
4
5#include <boost/unordered/detail/prime_fmod.hpp>
6
7#include <boost/core/detail/splitmix64.hpp>
8#include <boost/core/lightweight_test.hpp>
9
10#include <limits>
11
12#if defined(BOOST_MSVC)
13// conditional expression is constant
14#pragma warning(disable : 4127)
15#endif
16
17void macros_test()
18{
19 if (std::numeric_limits<std::size_t>::digits >= 64) {
20#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
21 BOOST_ERROR("std::numeric_limits<size_t>::digits >= 64, but "
22 "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is not defined");
23#endif
24 } else {
25#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
26 BOOST_ERROR("std::numeric_limits<size_t>::digits < 64, but "
27 "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is defined");
28#endif
29 }
30}
31
32// Pretty inefficient, but the test is fast enough.
33// Might be too slow if we had larger primes?
34bool is_prime(std::size_t x)
35{
36 if (x == 2) {
37 return true;
38 }
39
40 if (x == 1 || x % 2 == 0) {
41 return false;
42 }
43
44 // y*y <= x is susceptible to overflow, so instead make sure to use y <= (x/y)
45 for (std::size_t y = 3; y <= (x / y); y += 2) {
46 if (x % y == 0) {
47 return false;
48 }
49 }
50
51 return true;
52}
53
54void prime_sizes_test()
55{
56 // just some basic sanity checks
57 //
58 BOOST_TEST(!is_prime(0));
59 BOOST_TEST(!is_prime(1));
60 BOOST_TEST(is_prime(2));
61 BOOST_TEST(is_prime(3));
62 BOOST_TEST(is_prime(13));
63 BOOST_TEST(!is_prime(4));
64 BOOST_TEST(!is_prime(100));
65 BOOST_TEST(!is_prime(49));
66
67 std::size_t const* sizes = boost::unordered::detail::prime_fmod_size<>::sizes;
68 std::size_t sizes_len =
69 boost::unordered::detail::prime_fmod_size<>::sizes_len;
70
71 // prove every number in our sizes array is prime
72 //
73 BOOST_TEST_GT(sizes_len, 0u);
74
75 for (std::size_t i = 0; i < sizes_len; ++i) {
76 BOOST_TEST(is_prime(sizes[i]));
77 }
78
79 // prove that every subsequent number in the sequence is larger than the
80 // previous
81 //
82 for (std::size_t i = 1; i < sizes_len; ++i) {
83 BOOST_TEST_GT(sizes[i], sizes[i - 1]);
84 }
85
86#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
87 // now we wish to prove that if we do have the reciprocals stored, we have the
88 // correct amount of them, i.e. one for every entry in sizes[] that fits in 32
89 // bits
90 //
91 boost::uint64_t const* inv_sizes32 =
92 boost::unordered::detail::prime_fmod_size<>::inv_sizes32;
93
94 std::size_t inv_sizes32_len =
95 boost::unordered::detail::prime_fmod_size<>::inv_sizes32_len;
96
97 std::size_t count = 0;
98 for (std::size_t i = 0; i < sizes_len; ++i) {
99 if (sizes[i] <= UINT32_MAX) {
100 ++count;
101 }
102 }
103
104 BOOST_TEST_GT(inv_sizes32_len, 0u);
105 BOOST_TEST_EQ(inv_sizes32_len, count);
106
107 // these values should also be monotonically decreasing
108 //
109 for (std::size_t i = 1; i < inv_sizes32_len; ++i) {
110 BOOST_TEST_LT(inv_sizes32[i], inv_sizes32[i - 1]);
111 }
112
113 // now make sure the values in inv_sizes32 are what they should be as derived
114 // from the paper
115 //
116 for (std::size_t i = 0; i < inv_sizes32_len; ++i) {
117 std::size_t const size = sizes[i];
118 BOOST_TEST_LE(size, UINT_MAX);
119
120 boost::uint32_t d = static_cast<boost::uint32_t>(sizes[i]);
121 boost::uint64_t M = ((boost::ulong_long_type(0xffffffff) << 32) +
122 boost::ulong_long_type(0xffffffff)) /
123 d +
124 1;
125
126 BOOST_TEST_EQ(inv_sizes32[i], M);
127 }
128#endif
129}
130
131void get_remainder_test()
132{
133#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
134 struct
135 {
136 // boost::unordered::detail::prime_fmod_size<>::get_remainder
137 // uses several internal implementations depending on the availability of
138 // certain intrinsics or 128 bit integer support, defaulting to a slow,
139 // portable routine. The following is a transcription of the portable
140 // routine used here for verification purposes.
141 //
142 boost::uint64_t operator()(boost::uint64_t f, boost::uint32_t d)
143 {
144 boost::uint64_t r1 = (f & UINT32_MAX) * d;
145 boost::uint64_t r2 = (f >> 32) * d;
146
147 r2 += r1 >> 32;
148
149 return r2 >> 32;
150 }
151 } get_remainder;
152
153 boost::detail::splitmix64 rng;
154
155 for (std::size_t i = 0; i < 1000000u; ++i) {
156 boost::uint64_t f = rng();
157 boost::uint32_t d = rng() & 0xffffffffu;
158
159 boost::uint64_t r1 =
160 boost::unordered::detail::prime_fmod_size<>::get_remainder(fractional: f, d);
161
162 boost::uint64_t r2 = get_remainder(f, d);
163
164 if (!BOOST_TEST_EQ(r1, r2)) {
165 std::cerr << "f: " << f << ", d: " << d << std::endl;
166 return;
167 }
168 }
169#endif
170}
171
172void modulo_test()
173{
174 std::size_t const* sizes = boost::unordered::detail::prime_fmod_size<>::sizes;
175
176 std::size_t const sizes_len =
177 boost::unordered::detail::prime_fmod_size<>::sizes_len;
178
179 boost::detail::splitmix64 rng;
180
181 for (std::size_t i = 0; i < 1000000u; ++i) {
182 std::size_t hash = static_cast<std::size_t>(-1) & rng();
183
184 for (std::size_t j = 0; j < sizes_len; ++j) {
185 std::size_t h = hash;
186
187#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
188 if (sizes[j] <= UINT_MAX) {
189 h = boost::uint32_t(h & 0xffffffffu) + boost::uint32_t(h >> 32);
190 }
191#endif
192 std::size_t p1 =
193 boost::unordered::detail::prime_fmod_size<>::position(hash, size_index: j);
194
195 std::size_t p2 = h % sizes[j];
196
197 if (!BOOST_TEST_EQ(p1, p2)) {
198 std::cerr << "hash: " << hash << ", j: " << j << ", h: " << h
199 << ", sizes[" << j << "]: " << sizes[j] << std::endl;
200 return;
201 }
202 }
203 }
204}
205
206int main()
207{
208 macros_test();
209 prime_sizes_test();
210 get_remainder_test();
211 modulo_test();
212
213 return boost::report_errors();
214}
215

source code of boost/libs/unordered/test/unordered/prime_fmod_tests.cpp