MySQL 8.3.0 Source Code Documentation
ut0math.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 2021, 2023, Oracle and/or its affiliates.
4
5This program is free software; you can redistribute it and/or modify it under
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for more details.
20
21You should have received a copy of the GNU General Public License along with
22this program; if not, write to the Free Software Foundation, Inc.,
2351 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24
25*****************************************************************************/
26
27/** @file include/ut0math.h
28 Math functions.
29
30 ***********************************************************************/
31
32#ifndef ut0math_h
33#define ut0math_h
34
35#include <atomic>
36#include <cstdint>
37#include "ut0class_life_cycle.h"
38#include "ut0dbg.h"
39#include "ut0seq_lock.h"
40
41namespace ut {
42
43/** Calculates the 128bit result of multiplication of the two specified 64bit
44integers. May use CPU native instructions for speed of standard uint64_t
45multiplication.
46@param[in] x First number to multiply.
47@param[in] y Second number to multiply.
48@param[out] hi A reference to 64bit integer that will store higher 64bits of the
49result.
50@return The lower 64bit of the result. */
51[[nodiscard]] static inline uint64_t multiply_uint64(uint64_t x, uint64_t y,
52 uint64_t &hi);
53
54/*Calculates the 64bit result of division of the specified 128bit integer by the
55specified 64bit integer. The result must fit in 64bit or else the behavior is
56undefined. Currently does not use native CPU instructions and can be quite slow.
57@param[in] high High 64bits of the number to divide.
58@param[in] low Low 64bits of the number to divide.
59@param[in] div The number to divide by.
60@return The lower 64bit of the result. */
61[[nodiscard]] static inline uint64_t divide_128(uint64_t high, uint64_t low,
62 uint64_t div);
63class fast_modulo_t;
64
65/** Looks for a prime number slightly greater than the given argument.
66The prime is chosen so that it is not near any power of 2.
67@param[in] n positive number > 100
68@return prime */
70
71namespace detail {
72/** Calculates the 128bit result of multiplication of the two specified 64bit
73integers.
74@param[in] x First number to multiply.
75@param[in] y Second number to multiply.
76@param[out] hi A reference to 64bit integer that will store higher 64bits of the
77result.
78@return The lower 64bit of the result. */
80 uint64_t y,
81 uint64_t &hi) {
82 uint32_t x_hi = static_cast<uint32_t>(x >> 32);
83 uint32_t x_lo = static_cast<uint32_t>(x);
84 uint32_t y_hi = static_cast<uint32_t>(y >> 32);
85 uint32_t y_lo = static_cast<uint32_t>(y);
86
87 uint64_t hi_lo = static_cast<uint64_t>(x_hi) * y_lo;
88
89 uint64_t low = static_cast<uint64_t>(x_lo) * y_lo;
90 /* This will not overflow, as (2^32 -1)^2 = 2^64 - 1 - 2 * 2^32, so there is
91 still a place for two 32bit integers to be added. */
92 uint64_t mid = (low >> 32) + static_cast<uint64_t>(x_lo) * y_hi +
93 static_cast<uint32_t>(hi_lo);
94 hi = (mid >> 32) + static_cast<uint64_t>(x_hi) * y_hi + (hi_lo >> 32);
95 return static_cast<uint32_t>(low) + (mid << 32);
96}
97} // namespace detail
98
99#if defined(_MSC_VER) && defined(_M_X64) && !defined(_M_ARM64EC)
100/* MSVC x86 supports native uint64_t -> uint128_t multiplication */
101#include <intrin.h>
102#pragma intrinsic(_umul128)
103[[nodiscard]] static inline uint64_t multiply_uint64(uint64_t x, uint64_t y,
104 uint64_t &hi) {
105 return _umul128(x, y, &hi);
106}
107#elif defined(__SIZEOF_INT128__)
108/* Compiler supports 128-bit values (GCC/Clang) */
109
110[[nodiscard]] static inline uint64_t multiply_uint64(uint64_t x, uint64_t y,
111 uint64_t &hi) {
112 unsigned __int128 res = (unsigned __int128)x * y;
113 hi = static_cast<uint64_t>(res >> 64);
114 return static_cast<uint64_t>(res);
115}
116#else
117[[nodiscard]] static inline uint64_t multiply_uint64(uint64_t x, uint64_t y,
118 uint64_t &hi) {
119 return detail::multiply_uint64_portable(x, y, hi);
120}
121#endif
122
123[[nodiscard]] static inline uint64_t divide_128(uint64_t high, uint64_t low,
124 uint64_t div) {
125 uint64_t res = 0;
126 for (auto current_bit = 63; current_bit >= 0; current_bit--) {
127 const auto div_hi = current_bit ? (div >> (64 - current_bit)) : 0;
128 const auto div_lo = div << current_bit;
129 if (div_hi < high || (div_hi == high && div_lo <= low)) {
130 high -= div_hi;
131 if (low < div_lo) {
132 high--;
133 }
134 low -= div_lo;
135 res += 1ULL << current_bit;
136 }
137 }
138 return res;
139}
140
141/** Allows to execute x % mod for a specified mod in a fast way, without using a
142slow operation of division. The additional cost is hidden in constructor to
143preprocess the mod constant. */
145 /* Idea behind this implementation is following: (division sign in all
146 equations below is to be treated as mathematical division on reals)
147
148 x % mod = x - floor(x/mod)*mod
149
150 and...
151
152 x / mod = x * 1/mod = (x * (BIG/mod)) /BIG
153
154 and..
155
156 floor(x/mod) = x / mod - epsilon, where 0<=epsilon<1
157
158 Now, lets define:
159
160 M = floor(BIG/mod)
161
162 And take a look at the value of following expression:
163
164 floor( x*M / BIG) * mod =
165
166 floor(x * floor(BIG/mod) / BIG) * mod =
167 floor(x * ((BIG/mod)-epsilon1) / BIG) * mod =
168 ((x*((BIG/mod)-epsilon1)/BIG - epsilon2) * mod
169
170 This sure looks ugly, but it has interesting properties:
171 (1) is divisible by mod, which you can see, because it has a form (...)*
172 mod
173 (2) is smaller or equal to x, which you can see by setting epsilons to 0
174 (3) assuming BIG>x, the expression is strictly larger than x - 2*mod,
175 because it must be larger than the value for epsilons=1, which is:
176 ((x*((BIG/mod)-1))/BIG - 1) * mod =
177 ((x*BIG/mod - x)/BIG -1) * mod =
178 ((x/mod - x/BIG) - 1) * mod =
179 (x - x/BIG*mod - mod)
180 (4) we can compute it without using division at all, if BIG is 1<<k,
181 as it simplifies to
182 (( x * M ) >> k ) * mod
183
184 So, assuming BIG>x, and is a power of two (say BIG=1<<64), we get an
185 expression, which is divisible by mod, and if we subtract it from x, we get
186 something in the range [0...,2mod). What is left is to compare against mod,
187 and subtract it if it is higher.
188 */
189
190 public:
191 fast_modulo_t() = default;
192 explicit fast_modulo_t(uint64_t mod)
193 : m_mod(mod), m_inv(precompute_inv(mod)) {}
194 explicit fast_modulo_t(uint64_t mod, uint64_t inv) : m_mod(mod), m_inv(inv) {}
195
196 /** Computes the value of x % mod. */
197 uint64_t compute(uint64_t x) const {
198 uint64_t hi;
199 (void)multiply_uint64(x, m_inv, hi);
200
201 const uint64_t guess = hi * m_mod;
202 const uint64_t rest = x - guess;
203
204 return rest - (m_mod <= rest) * m_mod;
205 }
206
207 /** Gets the precomputed value of inverse. */
208 uint64_t get_inverse() const { return m_inv; }
209
210 /** Gets the modulo value. */
211 uint64_t get_mod() const { return m_mod; }
212
213 /** Precomputes the inverse needed for fast modulo operations. */
214 static uint64_t precompute_inv(uint64_t mod) {
215 /* pedantic matter: for mod=1 -- you can remove it if you never plan to use
216 it for 1. */
217 if (mod == 1) {
218 /* According to equations we want M to be 1<<64, but this overflows
219 uint64_t, so, let's do the second best thing we can, which is 1<<64-1,
220 this means that our `guess` will be ((x<<64 - x) >> 64)*mod, which for
221 x=0, is 0 (good), and for x>0 is (x-1)*mod = (x-1)*1 = x-1, and then
222 rest=1, which is also good enough (<2*mod). */
223 return ~uint64_t{0};
224 } else {
225 return divide_128(1, 0, mod);
226 }
227 }
228
229 private:
230 uint64_t m_mod{0};
231 uint64_t m_inv{0};
232};
233
234/** A class that allows to atomically set new modulo value for fast modulo
235computations. */
237 public:
238 mt_fast_modulo_t() : m_data{0ULL, 0ULL} {}
239 explicit mt_fast_modulo_t(uint64_t mod)
240 : m_data{mod, fast_modulo_t::precompute_inv(mod)} {}
241 /* This class can be made copyable, but this requires additional constructors.
242 */
243
245 return m_data.read([](const data_t &stored_data) {
248 });
249 }
250
251 void store(uint64_t new_mod) {
252 const fast_modulo_t new_fast_modulo{new_mod};
253 const auto inv = new_fast_modulo.get_inverse();
254 m_data.write([&](data_t &data) {
255 data.m_mod.store(new_mod, std::memory_order_relaxed);
256 data.m_inv.store(inv, std::memory_order_relaxed);
257 });
258 }
259
260 private:
261 struct data_t {
262 std::atomic<uint64_t> m_mod;
263 std::atomic<uint64_t> m_inv;
264 };
265
267};
268
269} // namespace ut
270
271static inline uint64_t operator%(uint64_t x, const ut::fast_modulo_t &fm) {
272 return fm.compute(x);
273}
274
275#endif
A utility class which, if inherited from, prevents the descendant class from being copied,...
Definition: ut0class_life_cycle.h:40
A class that allows to read value of variable of some type T atomically and allows the value to be ch...
Definition: ut0seq_lock.h:48
Allows to execute x % mod for a specified mod in a fast way, without using a slow operation of divisi...
Definition: ut0math.h:144
uint64_t get_inverse() const
Gets the precomputed value of inverse.
Definition: ut0math.h:208
uint64_t m_inv
Definition: ut0math.h:231
uint64_t compute(uint64_t x) const
Computes the value of x % mod.
Definition: ut0math.h:197
fast_modulo_t(uint64_t mod)
Definition: ut0math.h:192
static uint64_t precompute_inv(uint64_t mod)
Precomputes the inverse needed for fast modulo operations.
Definition: ut0math.h:214
uint64_t m_mod
Definition: ut0math.h:230
fast_modulo_t(uint64_t mod, uint64_t inv)
Definition: ut0math.h:194
uint64_t get_mod() const
Gets the modulo value.
Definition: ut0math.h:211
fast_modulo_t()=default
A class that allows to atomically set new modulo value for fast modulo computations.
Definition: ut0math.h:236
mt_fast_modulo_t()
Definition: ut0math.h:238
mt_fast_modulo_t(uint64_t mod)
Definition: ut0math.h:239
Definition: ut0math.h:244
void store(uint64_t new_mod)
Definition: ut0math.h:251
Seq_lock< data_t > m_data
Definition: ut0math.h:266
Definition: ut0tuple.h:56
constexpr uint64_t multiply_uint64_portable(uint64_t x, uint64_t y, uint64_t &hi)
Calculates the 128bit result of multiplication of the two specified 64bit integers.
Definition: ut0math.h:79
This file contains a set of libraries providing overloads for regular dynamic allocation routines whi...
Definition: aligned_alloc.h:47
uint64_t find_prime(uint64_t n)
Looks for a prime number slightly greater than the given argument.
Definition: ut0math.cc:35
static uint64_t multiply_uint64(uint64_t x, uint64_t y, uint64_t &hi)
Calculates the 128bit result of multiplication of the two specified 64bit integers.
Definition: ut0math.h:117
static uint64_t divide_128(uint64_t high, uint64_t low, uint64_t div)
Definition: ut0math.h:123
Definition: ut0math.h:261
std::atomic< uint64_t > m_mod
Definition: ut0math.h:262
std::atomic< uint64_t > m_inv
Definition: ut0math.h:263
Utilities related to class lifecycle.
Debug utilities for Innobase.
static uint64_t operator%(uint64_t x, const ut::fast_modulo_t &fm)
Definition: ut0math.h:271
Implements a sequential lock structure for non-locking atomic read/write operations on a complex stru...
int n
Definition: xcom_base.cc:508