1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
/* Copyright (c) 2021, 2025, Oracle and/or its affiliates.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License, version 2.0,
as published by the Free Software Foundation.
This program is designed to work with certain software (including
but not limited to OpenSSL) that is licensed under separate terms,
as designated in a particular file or component or in included license
documentation. The authors of MySQL hereby grant you an additional
permission to link the program and your derivative works with the
separately licensed software that they have either included with
the program or referenced in the documentation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License, version 2.0, for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
/* See http://code.google.com/p/googletest/wiki/Primer */
#include <gtest/gtest.h>
#include <cstdint>
#include "unittest/gunit/benchmark.h"
#include "storage/innobase/include/ut0rnd.h"
namespace innodb_ut0math_unittest {
/* Correctness test for math functions. */
TEST(ut0math, countr_zero) {
ASSERT_EQ(ut::countr_zero(0), 64);
ASSERT_EQ(ut::countr_zero(~uint64_t{0}), 0);
for (int p = 0; p < 64; ++p) {
ASSERT_EQ(ut::countr_zero(uint64_t{1} << p), p);
ASSERT_EQ(ut::countr_zero(~uint64_t{0} << p), p);
for (int t = 0; t < 100; ++t) {
const auto r = (uint64_t)(rand() | 1) << p;
ASSERT_EQ(ut::countr_zero(r), p);
}
}
}
TEST(ut0math, div_ceil) {
ASSERT_EQ(ut::div_ceil(7, 3), 3);
ASSERT_EQ(ut::div_ceil(7, -3), -2);
ASSERT_EQ(ut::div_ceil(-7, 3), -2);
ASSERT_EQ(ut::div_ceil(-7, -3), 3);
ASSERT_EQ(ut::div_ceil(uint8_t{247}, uint8_t{10}), uint8_t{25});
ASSERT_EQ(ut::div_ceil(uint8_t{255}, uint8_t{1}), uint8_t{255});
ASSERT_EQ(ut::div_ceil(int8_t{-128}, int8_t{1}), int8_t{-128});
}
void test_multiply_uint64(uint64_t x, uint64_t y) {
const auto xy = x * y;
uint64_t hi;
uint64_t lo = ut::detail::multiply_uint64_portable(x, y, hi);
ASSERT_EQ(hi, 0);
ASSERT_EQ(lo, xy);
}
TEST(ut0math, multiply_uint64_portable) {
for (int i = 0; i < 100000; i++) {
const uint64_t x = ut::random_64() >> 2;
if (x < 10) continue;
/* The x*max_y will fit into 64bits. */
const uint64_t max_y = std::numeric_limits<uint64_t>::max() / x;
test_multiply_uint64(x, max_y);
for (int j = 0; j < 10; j++) {
const uint64_t y = (ut::random_64() >> 2) % (max_y + 1);
test_multiply_uint64(x, y);
}
}
}
/* Correctness of the multiply_uint64_portable tested using Chinese Rest
Theorem. */
TEST(ut0math, multiply_uint64_portable_chinese) {
for (int k = 0; k < 100; k++) {
/* Choose a random 32bit prime and calculate 2^64 % P. This value will be
used to calculate value of (128bit integer % P). ut::find_prime finds a
prime bigger than specified argument, so we pass value shifted by more than
32 bits. */
const uint64_t P = ut::find_prime(ut::random_64() >> 34);
ASSERT_LT(P, 1ULL << 32);
const uint64_t two_to_32_mod_P = (1ULL << 32) % P;
const uint64_t two_to_64_mod_P = (two_to_32_mod_P * two_to_32_mod_P) % P;
for (int i = 0; i < 10000; i++) {
const uint64_t x = ut::random_64();
const uint64_t y = ut::random_64();
uint64_t hi;
const uint64_t lo = ut::detail::multiply_uint64_portable(x, y, hi);
/* Does the result agree modulo P? */
const uint64_t expected = ((x % P) * (y % P)) % P;
const uint64_t actual = (hi % P * two_to_64_mod_P % P + lo % P) % P;
ASSERT_EQ(actual, expected);
/* Does the result agree modulo 2^64? */
ASSERT_EQ(lo, static_cast<uint64_t>(x * y));
/* If the above two conditions are met, then it means the result is
correct modulo (P * 2^64). We could add a second random prime Q to mix
to have the multiplication result checked against (P * Q * 2^64), which
would be almost 2^128 bit number, but the 96bits we have now seems enough
having the P is chosen randomly. */
}
}
}
TEST(ut0math, divide_uint128) {
for (int i = 0; i < 1000000; i++) {
const uint64_t x = ut::random_64();
const uint64_t y = ut::random_64();
if (x == 0 || y == 0) continue;
uint64_t high;
uint64_t low = ut::detail::multiply_uint64_portable(x, y, high);
ASSERT_EQ(ut::divide_128(high, low, x), y);
ASSERT_EQ(ut::divide_128(high, low, y), x);
}
}
TEST(ut0math, fast_modulo) {
for (int i = 0; i < 1000000; i++) {
const uint64_t x = ut::random_64();
const uint64_t y = ut::random_64();
if (y == 0) continue;
ut::fast_modulo_t mod{y};
ASSERT_EQ(x % y, x % mod);
}
for (int i = 0; i < 1000000; i++) {
const uint64_t x = ut::random_64();
const uint64_t y = ut::random_64() % 1000 + 1;
ASSERT_EQ(x % y, x % ut::fast_modulo_t{y});
}
}
/* Micro-benchmark raw fast modulo performance. */
static void BM_FAST_MODULO_CALCULATE(const size_t num_iterations) {
uint32_t fold = 0;
ut::fast_modulo_t mod{123 + num_iterations};
for (size_t n = 0; n < num_iterations * 1000; n++) {
fold += n % mod;
}
EXPECT_NE(0U, fold); // To keep the compiler from optimizing it away.
SetBytesProcessed(num_iterations * 1000);
}
BENCHMARK(BM_FAST_MODULO_CALCULATE)
static void BM_MODULO_CALCULATE_CONSTEXPR_MOD(const size_t num_iterations) {
uint32_t fold = 0;
constexpr uint64_t mod{123};
for (size_t n = 0; n < num_iterations * 1000; n++) {
fold += n % mod;
}
EXPECT_NE(0U, fold); // To keep the compiler from optimizing it away.
SetBytesProcessed(num_iterations * 1000);
}
BENCHMARK(BM_MODULO_CALCULATE_CONSTEXPR_MOD)
static void BM_MODULO_CALCULATE_VARIABLE_MOD(const size_t num_iterations) {
uint32_t fold = 0;
const uint64_t mod{123 + num_iterations};
for (size_t n = 0; n < num_iterations * 1000; n++) {
fold += n % mod;
}
EXPECT_NE(0U, fold); // To keep the compiler from optimizing it away.
SetBytesProcessed(num_iterations * 1000);
}
BENCHMARK(BM_MODULO_CALCULATE_VARIABLE_MOD)
} // namespace innodb_ut0math_unittest
|
