int128_test.cc
Go to the documentation of this file.
1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include "absl/numeric/int128.h"
16 
17 #include <algorithm>
18 #include <limits>
19 #include <random>
20 #include <type_traits>
21 #include <utility>
22 #include <vector>
23 
24 #include "gtest/gtest.h"
26 #include "absl/hash/hash_testing.h"
27 #include "absl/meta/type_traits.h"
28 
29 #if defined(_MSC_VER) && _MSC_VER == 1900
30 // Disable "unary minus operator applied to unsigned type" warnings in Microsoft
31 // Visual C++ 14 (2015).
32 #pragma warning(disable:4146)
33 #endif
34 
35 namespace {
36 
37 template <typename T>
38 class Uint128IntegerTraitsTest : public ::testing::Test {};
39 typedef ::testing::Types<bool, char, signed char, unsigned char, char16_t,
40  char32_t, wchar_t,
41  short, // NOLINT(runtime/int)
42  unsigned short, // NOLINT(runtime/int)
43  int, unsigned int,
44  long, // NOLINT(runtime/int)
45  unsigned long, // NOLINT(runtime/int)
46  long long, // NOLINT(runtime/int)
47  unsigned long long> // NOLINT(runtime/int)
48  IntegerTypes;
49 
50 template <typename T>
51 class Uint128FloatTraitsTest : public ::testing::Test {};
52 typedef ::testing::Types<float, double, long double> FloatingPointTypes;
53 
54 TYPED_TEST_SUITE(Uint128IntegerTraitsTest, IntegerTypes);
55 
56 TYPED_TEST(Uint128IntegerTraitsTest, ConstructAssignTest) {
58  "absl::uint128 must be constructible from TypeParam");
60  "absl::uint128 must be assignable from TypeParam");
62  "TypeParam must not be assignable from absl::uint128");
63 }
64 
65 TYPED_TEST_SUITE(Uint128FloatTraitsTest, FloatingPointTypes);
66 
67 TYPED_TEST(Uint128FloatTraitsTest, ConstructAssignTest) {
69  "absl::uint128 must be constructible from TypeParam");
71  "absl::uint128 must not be assignable from TypeParam");
73  "TypeParam must not be assignable from absl::uint128");
74 }
75 
76 #ifdef ABSL_HAVE_INTRINSIC_INT128
77 // These type traits done separately as TYPED_TEST requires typeinfo, and not
78 // all platforms have this for __int128 even though they define the type.
79 TEST(Uint128, IntrinsicTypeTraitsTest) {
81  "absl::uint128 must be constructible from __int128");
83  "absl::uint128 must be assignable from __int128");
85  "__int128 must not be assignable from absl::uint128");
86 
88  "absl::uint128 must be constructible from unsigned __int128");
90  "absl::uint128 must be assignable from unsigned __int128");
92  "unsigned __int128 must not be assignable from absl::uint128");
93 }
94 #endif // ABSL_HAVE_INTRINSIC_INT128
95 
96 TEST(Uint128, TrivialTraitsTest) {
98  "");
100  "");
103 }
104 
105 TEST(Uint128, AllTests) {
106  absl::uint128 zero = 0;
107  absl::uint128 one = 1;
108  absl::uint128 one_2arg = absl::MakeUint128(0, 1);
109  absl::uint128 two = 2;
110  absl::uint128 three = 3;
111  absl::uint128 big = absl::MakeUint128(2000, 2);
112  absl::uint128 big_minus_one = absl::MakeUint128(2000, 1);
113  absl::uint128 bigger = absl::MakeUint128(2001, 1);
114  absl::uint128 biggest = absl::Uint128Max();
115  absl::uint128 high_low = absl::MakeUint128(1, 0);
116  absl::uint128 low_high =
117  absl::MakeUint128(0, std::numeric_limits<uint64_t>::max());
118  EXPECT_LT(one, two);
119  EXPECT_GT(two, one);
120  EXPECT_LT(one, big);
121  EXPECT_LT(one, big);
122  EXPECT_EQ(one, one_2arg);
123  EXPECT_NE(one, two);
124  EXPECT_GT(big, one);
125  EXPECT_GE(big, two);
126  EXPECT_GE(big, big_minus_one);
127  EXPECT_GT(big, big_minus_one);
128  EXPECT_LT(big_minus_one, big);
129  EXPECT_LE(big_minus_one, big);
130  EXPECT_NE(big_minus_one, big);
131  EXPECT_LT(big, biggest);
132  EXPECT_LE(big, biggest);
133  EXPECT_GT(biggest, big);
134  EXPECT_GE(biggest, big);
135  EXPECT_EQ(big, ~~big);
136  EXPECT_EQ(one, one | one);
137  EXPECT_EQ(big, big | big);
138  EXPECT_EQ(one, one | zero);
139  EXPECT_EQ(one, one & one);
140  EXPECT_EQ(big, big & big);
141  EXPECT_EQ(zero, one & zero);
142  EXPECT_EQ(zero, big & ~big);
143  EXPECT_EQ(zero, one ^ one);
144  EXPECT_EQ(zero, big ^ big);
145  EXPECT_EQ(one, one ^ zero);
146 
147  // Shift operators.
148  EXPECT_EQ(big, big << 0);
149  EXPECT_EQ(big, big >> 0);
150  EXPECT_GT(big << 1, big);
151  EXPECT_LT(big >> 1, big);
152  EXPECT_EQ(big, (big << 10) >> 10);
153  EXPECT_EQ(big, (big >> 1) << 1);
154  EXPECT_EQ(one, (one << 80) >> 80);
155  EXPECT_EQ(zero, (one >> 80) << 80);
156 
157  // Shift assignments.
158  absl::uint128 big_copy = big;
159  EXPECT_EQ(big << 0, big_copy <<= 0);
160  big_copy = big;
161  EXPECT_EQ(big >> 0, big_copy >>= 0);
162  big_copy = big;
163  EXPECT_EQ(big << 1, big_copy <<= 1);
164  big_copy = big;
165  EXPECT_EQ(big >> 1, big_copy >>= 1);
166  big_copy = big;
167  EXPECT_EQ(big << 10, big_copy <<= 10);
168  big_copy = big;
169  EXPECT_EQ(big >> 10, big_copy >>= 10);
170  big_copy = big;
171  EXPECT_EQ(big << 64, big_copy <<= 64);
172  big_copy = big;
173  EXPECT_EQ(big >> 64, big_copy >>= 64);
174  big_copy = big;
175  EXPECT_EQ(big << 73, big_copy <<= 73);
176  big_copy = big;
177  EXPECT_EQ(big >> 73, big_copy >>= 73);
178 
179  EXPECT_EQ(absl::Uint128High64(biggest), std::numeric_limits<uint64_t>::max());
180  EXPECT_EQ(absl::Uint128Low64(biggest), std::numeric_limits<uint64_t>::max());
181  EXPECT_EQ(zero + one, one);
182  EXPECT_EQ(one + one, two);
183  EXPECT_EQ(big_minus_one + one, big);
184  EXPECT_EQ(one - one, zero);
185  EXPECT_EQ(one - zero, one);
186  EXPECT_EQ(zero - one, biggest);
187  EXPECT_EQ(big - big, zero);
188  EXPECT_EQ(big - one, big_minus_one);
189  EXPECT_EQ(big + std::numeric_limits<uint64_t>::max(), bigger);
190  EXPECT_EQ(biggest + 1, zero);
191  EXPECT_EQ(zero - 1, biggest);
192  EXPECT_EQ(high_low - one, low_high);
193  EXPECT_EQ(low_high + one, high_low);
194  EXPECT_EQ(absl::Uint128High64((absl::uint128(1) << 64) - 1), 0);
195  EXPECT_EQ(absl::Uint128Low64((absl::uint128(1) << 64) - 1),
196  std::numeric_limits<uint64_t>::max());
197  EXPECT_TRUE(!!one);
198  EXPECT_TRUE(!!high_low);
199  EXPECT_FALSE(!!zero);
200  EXPECT_FALSE(!one);
201  EXPECT_FALSE(!high_low);
202  EXPECT_TRUE(!zero);
203  EXPECT_TRUE(zero == 0); // NOLINT(readability/check)
204  EXPECT_FALSE(zero != 0); // NOLINT(readability/check)
205  EXPECT_FALSE(one == 0); // NOLINT(readability/check)
206  EXPECT_TRUE(one != 0); // NOLINT(readability/check)
207  EXPECT_FALSE(high_low == 0); // NOLINT(readability/check)
208  EXPECT_TRUE(high_low != 0); // NOLINT(readability/check)
209 
210  absl::uint128 test = zero;
211  EXPECT_EQ(++test, one);
212  EXPECT_EQ(test, one);
213  EXPECT_EQ(test++, one);
214  EXPECT_EQ(test, two);
215  EXPECT_EQ(test -= 2, zero);
216  EXPECT_EQ(test, zero);
217  EXPECT_EQ(test += 2, two);
218  EXPECT_EQ(test, two);
219  EXPECT_EQ(--test, one);
220  EXPECT_EQ(test, one);
221  EXPECT_EQ(test--, one);
222  EXPECT_EQ(test, zero);
223  EXPECT_EQ(test |= three, three);
224  EXPECT_EQ(test &= one, one);
225  EXPECT_EQ(test ^= three, two);
226  EXPECT_EQ(test >>= 1, one);
227  EXPECT_EQ(test <<= 1, two);
228 
229  EXPECT_EQ(big, -(-big));
230  EXPECT_EQ(two, -((-one) - 1));
231  EXPECT_EQ(absl::Uint128Max(), -one);
232  EXPECT_EQ(zero, -zero);
233 
234  EXPECT_EQ(absl::Uint128Max(), absl::kuint128max);
235 }
236 
237 TEST(Uint128, ConversionTests) {
238  EXPECT_TRUE(absl::MakeUint128(1, 0));
239 
240 #ifdef ABSL_HAVE_INTRINSIC_INT128
241  unsigned __int128 intrinsic =
242  (static_cast<unsigned __int128>(0x3a5b76c209de76f6) << 64) +
243  0x1f25e1d63a2b46c5;
244  absl::uint128 custom =
245  absl::MakeUint128(0x3a5b76c209de76f6, 0x1f25e1d63a2b46c5);
246 
247  EXPECT_EQ(custom, absl::uint128(intrinsic));
248  EXPECT_EQ(custom, absl::uint128(static_cast<__int128>(intrinsic)));
249  EXPECT_EQ(intrinsic, static_cast<unsigned __int128>(custom));
250  EXPECT_EQ(intrinsic, static_cast<__int128>(custom));
251 #endif // ABSL_HAVE_INTRINSIC_INT128
252 
253  // verify that an integer greater than 2**64 that can be stored precisely
254  // inside a double is converted to a absl::uint128 without loss of
255  // information.
256  double precise_double = 0x530e * std::pow(2.0, 64.0) + 0xda74000000000000;
257  absl::uint128 from_precise_double(precise_double);
258  absl::uint128 from_precise_ints =
259  absl::MakeUint128(0x530e, 0xda74000000000000);
260  EXPECT_EQ(from_precise_double, from_precise_ints);
261  EXPECT_DOUBLE_EQ(static_cast<double>(from_precise_ints), precise_double);
262 
263  double approx_double = 0xffffeeeeddddcccc * std::pow(2.0, 64.0) +
264  0xbbbbaaaa99998888;
265  absl::uint128 from_approx_double(approx_double);
266  EXPECT_DOUBLE_EQ(static_cast<double>(from_approx_double), approx_double);
267 
268  double round_to_zero = 0.7;
269  double round_to_five = 5.8;
270  double round_to_nine = 9.3;
271  EXPECT_EQ(static_cast<absl::uint128>(round_to_zero), 0);
272  EXPECT_EQ(static_cast<absl::uint128>(round_to_five), 5);
273  EXPECT_EQ(static_cast<absl::uint128>(round_to_nine), 9);
274 
275  absl::uint128 highest_precision_in_long_double =
276  ~absl::uint128{} >> (128 - std::numeric_limits<long double>::digits);
277  EXPECT_EQ(highest_precision_in_long_double,
278  static_cast<absl::uint128>(
279  static_cast<long double>(highest_precision_in_long_double)));
280  // Apply a mask just to make sure all the bits are the right place.
281  const absl::uint128 arbitrary_mask =
282  absl::MakeUint128(0xa29f622677ded751, 0xf8ca66add076f468);
283  EXPECT_EQ(highest_precision_in_long_double & arbitrary_mask,
284  static_cast<absl::uint128>(static_cast<long double>(
285  highest_precision_in_long_double & arbitrary_mask)));
286 
287  EXPECT_EQ(static_cast<absl::uint128>(-0.1L), 0);
288 }
289 
290 TEST(Uint128, OperatorAssignReturnRef) {
291  absl::uint128 v(1);
292  (v += 4) -= 3;
293  EXPECT_EQ(2, v);
294 }
295 
296 TEST(Uint128, Multiply) {
297  absl::uint128 a, b, c;
298 
299  // Zero test.
300  a = 0;
301  b = 0;
302  c = a * b;
303  EXPECT_EQ(0, c);
304 
305  // Max carries.
306  a = absl::uint128(0) - 1;
307  b = absl::uint128(0) - 1;
308  c = a * b;
309  EXPECT_EQ(1, c);
310 
311  // Self-operation with max carries.
312  c = absl::uint128(0) - 1;
313  c *= c;
314  EXPECT_EQ(1, c);
315 
316  // 1-bit x 1-bit.
317  for (int i = 0; i < 64; ++i) {
318  for (int j = 0; j < 64; ++j) {
319  a = absl::uint128(1) << i;
320  b = absl::uint128(1) << j;
321  c = a * b;
322  EXPECT_EQ(absl::uint128(1) << (i + j), c);
323  }
324  }
325 
326  // Verified with dc.
327  a = absl::MakeUint128(0xffffeeeeddddcccc, 0xbbbbaaaa99998888);
328  b = absl::MakeUint128(0x7777666655554444, 0x3333222211110000);
329  c = a * b;
330  EXPECT_EQ(absl::MakeUint128(0x530EDA741C71D4C3, 0xBF25975319080000), c);
331  EXPECT_EQ(0, c - b * a);
332  EXPECT_EQ(a*a - b*b, (a+b) * (a-b));
333 
334  // Verified with dc.
335  a = absl::MakeUint128(0x0123456789abcdef, 0xfedcba9876543210);
336  b = absl::MakeUint128(0x02468ace13579bdf, 0xfdb97531eca86420);
337  c = a * b;
338  EXPECT_EQ(absl::MakeUint128(0x97a87f4f261ba3f2, 0x342d0bbf48948200), c);
339  EXPECT_EQ(0, c - b * a);
340  EXPECT_EQ(a*a - b*b, (a+b) * (a-b));
341 }
342 
343 TEST(Uint128, AliasTests) {
344  absl::uint128 x1 = absl::MakeUint128(1, 2);
345  absl::uint128 x2 = absl::MakeUint128(2, 4);
346  x1 += x1;
347  EXPECT_EQ(x2, x1);
348 
349  absl::uint128 x3 = absl::MakeUint128(1, static_cast<uint64_t>(1) << 63);
350  absl::uint128 x4 = absl::MakeUint128(3, 0);
351  x3 += x3;
352  EXPECT_EQ(x4, x3);
353 }
354 
355 TEST(Uint128, DivideAndMod) {
356  using std::swap;
357 
358  // a := q * b + r
359  absl::uint128 a, b, q, r;
360 
361  // Zero test.
362  a = 0;
363  b = 123;
364  q = a / b;
365  r = a % b;
366  EXPECT_EQ(0, q);
367  EXPECT_EQ(0, r);
368 
369  a = absl::MakeUint128(0x530eda741c71d4c3, 0xbf25975319080000);
370  q = absl::MakeUint128(0x4de2cab081, 0x14c34ab4676e4bab);
371  b = absl::uint128(0x1110001);
372  r = absl::uint128(0x3eb455);
373  ASSERT_EQ(a, q * b + r); // Sanity-check.
374 
375  absl::uint128 result_q, result_r;
376  result_q = a / b;
377  result_r = a % b;
378  EXPECT_EQ(q, result_q);
379  EXPECT_EQ(r, result_r);
380 
381  // Try the other way around.
382  swap(q, b);
383  result_q = a / b;
384  result_r = a % b;
385  EXPECT_EQ(q, result_q);
386  EXPECT_EQ(r, result_r);
387  // Restore.
388  swap(b, q);
389 
390  // Dividend < divisor; result should be q:0 r:<dividend>.
391  swap(a, b);
392  result_q = a / b;
393  result_r = a % b;
394  EXPECT_EQ(0, result_q);
395  EXPECT_EQ(a, result_r);
396  // Try the other way around.
397  swap(a, q);
398  result_q = a / b;
399  result_r = a % b;
400  EXPECT_EQ(0, result_q);
401  EXPECT_EQ(a, result_r);
402  // Restore.
403  swap(q, a);
404  swap(b, a);
405 
406  // Try a large remainder.
407  b = a / 2 + 1;
408  absl::uint128 expected_r =
409  absl::MakeUint128(0x29876d3a0e38ea61, 0xdf92cba98c83ffff);
410  // Sanity checks.
411  ASSERT_EQ(a / 2 - 1, expected_r);
412  ASSERT_EQ(a, b + expected_r);
413  result_q = a / b;
414  result_r = a % b;
415  EXPECT_EQ(1, result_q);
416  EXPECT_EQ(expected_r, result_r);
417 }
418 
419 TEST(Uint128, DivideAndModRandomInputs) {
420  const int kNumIters = 1 << 18;
421  std::minstd_rand random(testing::UnitTest::GetInstance()->random_seed());
422  std::uniform_int_distribution<uint64_t> uniform_uint64;
423  for (int i = 0; i < kNumIters; ++i) {
424  const absl::uint128 a =
425  absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
426  const absl::uint128 b =
427  absl::MakeUint128(uniform_uint64(random), uniform_uint64(random));
428  if (b == 0) {
429  continue; // Avoid a div-by-zero.
430  }
431  const absl::uint128 q = a / b;
432  const absl::uint128 r = a % b;
433  ASSERT_EQ(a, b * q + r);
434  }
435 }
436 
437 TEST(Uint128, ConstexprTest) {
438  constexpr absl::uint128 zero = absl::uint128();
439  constexpr absl::uint128 one = 1;
440  constexpr absl::uint128 minus_two = -2;
441  EXPECT_EQ(zero, absl::uint128(0));
442  EXPECT_EQ(one, absl::uint128(1));
443  EXPECT_EQ(minus_two, absl::MakeUint128(-1, -2));
444 }
445 
446 TEST(Uint128, NumericLimitsTest) {
450  EXPECT_EQ(static_cast<int>(128 * std::log10(2)),
455 }
456 
457 TEST(Uint128, Hash) {
459  // Some simple values
460  absl::uint128{0},
461  absl::uint128{1},
462  ~absl::uint128{},
463  // 64 bit limits
464  absl::uint128{std::numeric_limits<int64_t>::max()},
465  absl::uint128{std::numeric_limits<uint64_t>::max()} + 0,
466  absl::uint128{std::numeric_limits<uint64_t>::max()} + 1,
467  absl::uint128{std::numeric_limits<uint64_t>::max()} + 2,
468  // Keeping high same
469  absl::uint128{1} << 62,
470  absl::uint128{1} << 63,
471  // Keeping low same
472  absl::uint128{1} << 64,
473  absl::uint128{1} << 65,
474  // 128 bit limits
479  }));
480 }
481 
482 } // namespace
int v
Definition: variant_test.cc:81
constexpr uint128 Uint128Max()
Definition: int128.h:242
static constexpr int digits10
Definition: int128.h:268
static constexpr bool is_specialized
Definition: int128.h:254
constexpr uint64_t Uint128High64(uint128 v)
Definition: int128.h:389
static constexpr absl::uint128 lowest()
Definition: int128.h:283
constexpr uint64_t Uint128Low64(uint128 v)
Definition: int128.h:387
std::pair< uint64_t, uint64_t > uint128
Definition: city.h:55
Definition: algorithm.h:29
static constexpr bool is_integer
Definition: int128.h:256
static constexpr absl::uint128() min()
Definition: int128.h:282
static constexpr bool is_signed
Definition: int128.h:255
size_t value
static constexpr absl::uint128() max()
Definition: int128.h:284
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
ABSL_MUST_USE_RESULT testing::AssertionResult VerifyTypeImplementsAbslHashCorrectly(const Container &values)
Definition: hash_testing.h:344
const uint128 kuint128max
Definition: int128.cc:27
constexpr uint128 MakeUint128(uint64_t high, uint64_t low)
Definition: int128.h:301
TEST(Symbolize, Unimplemented)
uint64_t b
Definition: layout_test.cc:50


abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:19