1//===-- Unittests for the UInt integer class ------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "src/__support/CPP/optional.h"
10#include "src/__support/big_int.h"
11#include "src/__support/integer_literals.h" // parse_unsigned_bigint
12#include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128
13
14#include "hdr/math_macros.h" // HUGE_VALF, HUGE_VALF
15#include "test/UnitTest/Test.h"
16
17namespace LIBC_NAMESPACE {
18
19enum Value { ZERO, ONE, TWO, MIN, MAX };
20
21template <typename T> auto create(Value value) {
22 switch (value) {
23 case ZERO:
24 return T(0);
25 case ONE:
26 return T(1);
27 case TWO:
28 return T(2);
29 case MIN:
30 return T::min();
31 case MAX:
32 return T::max();
33 }
34}
35
36using Types = testing::TypeList< //
37#ifdef LIBC_TYPES_HAS_INT64
38 BigInt<64, false, uint64_t>, // 64-bits unsigned (1 x uint64_t)
39 BigInt<64, true, uint64_t>, // 64-bits signed (1 x uint64_t)
40#endif
41#ifdef LIBC_TYPES_HAS_INT128
42 BigInt<128, false, __uint128_t>, // 128-bits unsigned (1 x __uint128_t)
43 BigInt<128, true, __uint128_t>, // 128-bits signed (1 x __uint128_t)
44#endif
45 BigInt<16, false, uint16_t>, // 16-bits unsigned (1 x uint16_t)
46 BigInt<16, true, uint16_t>, // 16-bits signed (1 x uint16_t)
47 BigInt<64, false, uint16_t>, // 64-bits unsigned (4 x uint16_t)
48 BigInt<64, true, uint16_t> // 64-bits signed (4 x uint16_t)
49 >;
50
51#define ASSERT_SAME(A, B) ASSERT_TRUE((A) == (B))
52
53TYPED_TEST(LlvmLibcUIntClassTest, Additions, Types) {
54 ASSERT_SAME(create<T>(ZERO) + create<T>(ZERO), create<T>(ZERO));
55 ASSERT_SAME(create<T>(ONE) + create<T>(ZERO), create<T>(ONE));
56 ASSERT_SAME(create<T>(ZERO) + create<T>(ONE), create<T>(ONE));
57 ASSERT_SAME(create<T>(ONE) + create<T>(ONE), create<T>(TWO));
58 // 2's complement addition works for signed and unsigned types.
59 // - unsigned : 0xff + 0x01 = 0x00 (255 + 1 = 0)
60 // - signed : 0xef + 0x01 = 0xf0 (127 + 1 = -128)
61 ASSERT_SAME(create<T>(MAX) + create<T>(ONE), create<T>(MIN));
62}
63
64TYPED_TEST(LlvmLibcUIntClassTest, Subtraction, Types) {
65 ASSERT_SAME(create<T>(ZERO) - create<T>(ZERO), create<T>(ZERO));
66 ASSERT_SAME(create<T>(ONE) - create<T>(ONE), create<T>(ZERO));
67 ASSERT_SAME(create<T>(ONE) - create<T>(ZERO), create<T>(ONE));
68 // 2's complement subtraction works for signed and unsigned types.
69 // - unsigned : 0x00 - 0x01 = 0xff ( 0 - 1 = 255)
70 // - signed : 0xf0 - 0x01 = 0xef (-128 - 1 = 127)
71 ASSERT_SAME(create<T>(MIN) - create<T>(ONE), create<T>(MAX));
72}
73
74TYPED_TEST(LlvmLibcUIntClassTest, Multiplication, Types) {
75 ASSERT_SAME(create<T>(ZERO) * create<T>(ZERO), create<T>(ZERO));
76 ASSERT_SAME(create<T>(ZERO) * create<T>(ONE), create<T>(ZERO));
77 ASSERT_SAME(create<T>(ONE) * create<T>(ZERO), create<T>(ZERO));
78 ASSERT_SAME(create<T>(ONE) * create<T>(ONE), create<T>(ONE));
79 ASSERT_SAME(create<T>(ONE) * create<T>(TWO), create<T>(TWO));
80 ASSERT_SAME(create<T>(TWO) * create<T>(ONE), create<T>(TWO));
81 // - unsigned : 0xff x 0xff = 0x01 (mod 0xff)
82 // - signed : 0xef x 0xef = 0x01 (mod 0xff)
83 ASSERT_SAME(create<T>(MAX) * create<T>(MAX), create<T>(ONE));
84}
85
86template <typename T> void print(const char *msg, T value) {
87 testing::tlog << msg;
88 IntegerToString<T, radix::Hex> buffer(value);
89 testing::tlog << buffer.view() << "\n";
90}
91
92TEST(LlvmLibcUIntClassTest, SignedAddSub) {
93 // Computations performed by https://www.wolframalpha.com/
94 using T = BigInt<128, true, uint32_t>;
95 const T a = parse_bigint<T>(ptr: "1927508279017230597");
96 const T b = parse_bigint<T>(ptr: "278789278723478925");
97 const T s = parse_bigint<T>(ptr: "2206297557740709522");
98 // Addition
99 ASSERT_SAME(a + b, s);
100 ASSERT_SAME(b + a, s); // commutative
101 // Subtraction
102 ASSERT_SAME(a - s, -b);
103 ASSERT_SAME(s - a, b);
104}
105
106TEST(LlvmLibcUIntClassTest, SignedMulDiv) {
107 // Computations performed by https://www.wolframalpha.com/
108 using T = BigInt<128, true, uint16_t>;
109 struct {
110 const char *a;
111 const char *b;
112 const char *mul;
113 } const test_cases[] = {{.a: "-4", .b: "3", .mul: "-12"},
114 {.a: "-3", .b: "-3", .mul: "9"},
115 {.a: "1927508279017230597", .b: "278789278723478925",
116 .mul: "537368642840747885329125014794668225"}};
117 for (auto tc : test_cases) {
118 const T a = parse_bigint<T>(ptr: tc.a);
119 const T b = parse_bigint<T>(ptr: tc.b);
120 const T mul = parse_bigint<T>(ptr: tc.mul);
121 // Multiplication
122 ASSERT_SAME(a * b, mul);
123 ASSERT_SAME(b * a, mul); // commutative
124 ASSERT_SAME(a * -b, -mul); // sign
125 ASSERT_SAME(-a * b, -mul); // sign
126 ASSERT_SAME(-a * -b, mul); // sign
127 // Division
128 ASSERT_SAME(mul / a, b);
129 ASSERT_SAME(mul / b, a);
130 ASSERT_SAME(-mul / a, -b); // sign
131 ASSERT_SAME(mul / -a, -b); // sign
132 ASSERT_SAME(-mul / -a, b); // sign
133 }
134}
135
136TYPED_TEST(LlvmLibcUIntClassTest, Division, Types) {
137 ASSERT_SAME(create<T>(ZERO) / create<T>(ONE), create<T>(ZERO));
138 ASSERT_SAME(create<T>(MAX) / create<T>(ONE), create<T>(MAX));
139 ASSERT_SAME(create<T>(MAX) / create<T>(MAX), create<T>(ONE));
140 ASSERT_SAME(create<T>(ONE) / create<T>(ONE), create<T>(ONE));
141 if constexpr (T::SIGNED) {
142 // Special case found by fuzzing.
143 ASSERT_SAME(create<T>(MIN) / create<T>(MIN), create<T>(ONE));
144 }
145 // - unsigned : 0xff / 0x02 = 0x7f
146 // - signed : 0xef / 0x02 = 0x77
147 ASSERT_SAME(create<T>(MAX) / create<T>(TWO), (create<T>(MAX) >> 1));
148
149 using word_type = typename T::word_type;
150 const T zero_one_repeated = T::all_ones() / T(0xff);
151 const word_type pattern = word_type(~0) / word_type(0xff);
152 for (const word_type part : zero_one_repeated.val) {
153 if constexpr (T::SIGNED == false) {
154 EXPECT_EQ(part, pattern);
155 }
156 }
157}
158
159TYPED_TEST(LlvmLibcUIntClassTest, is_neg, Types) {
160 EXPECT_FALSE(create<T>(ZERO).is_neg());
161 EXPECT_FALSE(create<T>(ONE).is_neg());
162 EXPECT_FALSE(create<T>(TWO).is_neg());
163 EXPECT_EQ(create<T>(MIN).is_neg(), T::SIGNED);
164 EXPECT_FALSE(create<T>(MAX).is_neg());
165}
166
167TYPED_TEST(LlvmLibcUIntClassTest, Masks, Types) {
168 if constexpr (!T::SIGNED) {
169 constexpr size_t BITS = T::BITS;
170 // mask_trailing_ones
171 ASSERT_SAME((mask_trailing_ones<T, 0>()), T::zero());
172 ASSERT_SAME((mask_trailing_ones<T, 1>()), T::one());
173 ASSERT_SAME((mask_trailing_ones<T, BITS - 1>()), T::all_ones() >> 1);
174 ASSERT_SAME((mask_trailing_ones<T, BITS>()), T::all_ones());
175 // mask_leading_ones
176 ASSERT_SAME((mask_leading_ones<T, 0>()), T::zero());
177 ASSERT_SAME((mask_leading_ones<T, 1>()), T::one() << (BITS - 1));
178 ASSERT_SAME((mask_leading_ones<T, BITS - 1>()), T::all_ones() - T::one());
179 ASSERT_SAME((mask_leading_ones<T, BITS>()), T::all_ones());
180 // mask_trailing_zeros
181 ASSERT_SAME((mask_trailing_zeros<T, 0>()), T::all_ones());
182 ASSERT_SAME((mask_trailing_zeros<T, 1>()), T::all_ones() - T::one());
183 ASSERT_SAME((mask_trailing_zeros<T, BITS - 1>()), T::one() << (BITS - 1));
184 ASSERT_SAME((mask_trailing_zeros<T, BITS>()), T::zero());
185 // mask_trailing_zeros
186 ASSERT_SAME((mask_leading_zeros<T, 0>()), T::all_ones());
187 ASSERT_SAME((mask_leading_zeros<T, 1>()), T::all_ones() >> 1);
188 ASSERT_SAME((mask_leading_zeros<T, BITS - 1>()), T::one());
189 ASSERT_SAME((mask_leading_zeros<T, BITS>()), T::zero());
190 }
191}
192
193TYPED_TEST(LlvmLibcUIntClassTest, CountBits, Types) {
194 if constexpr (!T::SIGNED) {
195 for (size_t i = 0; i < T::BITS; ++i) {
196 const auto l_one = T::all_ones() << i; // 0b111...000
197 const auto r_one = T::all_ones() >> i; // 0b000...111
198 const int zeros = i;
199 const int ones = T::BITS - zeros;
200 ASSERT_EQ(cpp::countr_one(r_one), ones);
201 ASSERT_EQ(cpp::countl_one(l_one), ones);
202 ASSERT_EQ(cpp::countr_zero(l_one), zeros);
203 ASSERT_EQ(cpp::countl_zero(r_one), zeros);
204 }
205 }
206}
207
208using LL_UInt64 = UInt<64>;
209// We want to test UInt<128> explicitly. So, for
210// convenience, we use a sugar which does not conflict with the UInt128 type
211// which can resolve to __uint128_t if the platform has it.
212using LL_UInt128 = UInt<128>;
213using LL_UInt192 = UInt<192>;
214using LL_UInt256 = UInt<256>;
215using LL_UInt320 = UInt<320>;
216using LL_UInt512 = UInt<512>;
217using LL_UInt1024 = UInt<1024>;
218
219using LL_Int128 = Int<128>;
220using LL_Int192 = Int<192>;
221
222TEST(LlvmLibcUIntClassTest, BitCastToFromDouble) {
223 static_assert(cpp::is_trivially_copyable<LL_UInt64>::value);
224 static_assert(sizeof(LL_UInt64) == sizeof(double));
225 const double inf = HUGE_VAL;
226 const double max = DBL_MAX;
227 const double array[] = {0.0, 0.1, 1.0, max, inf};
228 for (double value : array) {
229 LL_UInt64 back = cpp::bit_cast<LL_UInt64>(from: value);
230 double forth = cpp::bit_cast<double>(from: back);
231 EXPECT_TRUE(value == forth);
232 }
233}
234
235#ifdef LIBC_TYPES_HAS_INT128
236TEST(LlvmLibcUIntClassTest, BitCastToFromNativeUint128) {
237 static_assert(cpp::is_trivially_copyable<LL_UInt128>::value);
238 static_assert(sizeof(LL_UInt128) == sizeof(__uint128_t));
239 const __uint128_t array[] = {0, 1, ~__uint128_t(0)};
240 for (__uint128_t value : array) {
241 LL_UInt128 back = cpp::bit_cast<LL_UInt128>(from: value);
242 __uint128_t forth = cpp::bit_cast<__uint128_t>(from: back);
243 EXPECT_TRUE(value == forth);
244 }
245}
246#endif // LIBC_TYPES_HAS_INT128
247
248#ifdef LIBC_TYPES_HAS_FLOAT128
249TEST(LlvmLibcUIntClassTest, BitCastToFromNativeFloat128) {
250 static_assert(cpp::is_trivially_copyable<LL_UInt128>::value);
251 static_assert(sizeof(LL_UInt128) == sizeof(float128));
252 const float128 array[] = {0, 0.1, 1};
253 for (float128 value : array) {
254 LL_UInt128 back = cpp::bit_cast<LL_UInt128>(from: value);
255 float128 forth = cpp::bit_cast<float128>(from: back);
256 EXPECT_TRUE(value == forth);
257 }
258}
259#endif // LIBC_TYPES_HAS_FLOAT128
260
261TEST(LlvmLibcUIntClassTest, BasicInit) {
262 LL_UInt128 half_val(12345);
263 LL_UInt128 full_val({12345, 67890});
264 ASSERT_TRUE(half_val != full_val);
265}
266
267TEST(LlvmLibcUIntClassTest, AdditionTests) {
268 LL_UInt128 val1(12345);
269 LL_UInt128 val2(54321);
270 LL_UInt128 result1(66666);
271 EXPECT_EQ(val1 + val2, result1);
272 EXPECT_EQ((val1 + val2), (val2 + val1)); // addition is commutative
273
274 // Test overflow
275 LL_UInt128 val3({0xf000000000000001, 0});
276 LL_UInt128 val4({0x100000000000000f, 0});
277 LL_UInt128 result2({0x10, 0x1});
278 EXPECT_EQ(val3 + val4, result2);
279 EXPECT_EQ(val3 + val4, val4 + val3);
280
281 // Test overflow
282 LL_UInt128 val5({0x0123456789abcdef, 0xfedcba9876543210});
283 LL_UInt128 val6({0x1111222233334444, 0xaaaabbbbccccdddd});
284 LL_UInt128 result3({0x12346789bcdf1233, 0xa987765443210fed});
285 EXPECT_EQ(val5 + val6, result3);
286 EXPECT_EQ(val5 + val6, val6 + val5);
287
288 // Test 192-bit addition
289 LL_UInt192 val7({0x0123456789abcdef, 0xfedcba9876543210, 0xfedcba9889abcdef});
290 LL_UInt192 val8({0x1111222233334444, 0xaaaabbbbccccdddd, 0xeeeeffffeeeeffff});
291 LL_UInt192 result4(
292 {0x12346789bcdf1233, 0xa987765443210fed, 0xedcbba98789acdef});
293 EXPECT_EQ(val7 + val8, result4);
294 EXPECT_EQ(val7 + val8, val8 + val7);
295
296 // Test 256-bit addition
297 LL_UInt256 val9({0x1f1e1d1c1b1a1918, 0xf1f2f3f4f5f6f7f8, 0x0123456789abcdef,
298 0xfedcba9876543210});
299 LL_UInt256 val10({0x1111222233334444, 0xaaaabbbbccccdddd, 0x1111222233334444,
300 0xaaaabbbbccccdddd});
301 LL_UInt256 result5({0x302f3f3e4e4d5d5c, 0x9c9dafb0c2c3d5d5,
302 0x12346789bcdf1234, 0xa987765443210fed});
303 EXPECT_EQ(val9 + val10, result5);
304 EXPECT_EQ(val9 + val10, val10 + val9);
305}
306
307TEST(LlvmLibcUIntClassTest, SubtractionTests) {
308 LL_UInt128 val1(12345);
309 LL_UInt128 val2(54321);
310 LL_UInt128 result1({0xffffffffffff5c08, 0xffffffffffffffff});
311 LL_UInt128 result2(0xa3f8);
312 EXPECT_EQ(val1 - val2, result1);
313 EXPECT_EQ(val1, val2 + result1);
314 EXPECT_EQ(val2 - val1, result2);
315 EXPECT_EQ(val2, val1 + result2);
316
317 LL_UInt128 val3({0xf000000000000001, 0});
318 LL_UInt128 val4({0x100000000000000f, 0});
319 LL_UInt128 result3(0xdffffffffffffff2);
320 LL_UInt128 result4({0x200000000000000e, 0xffffffffffffffff});
321 EXPECT_EQ(val3 - val4, result3);
322 EXPECT_EQ(val3, val4 + result3);
323 EXPECT_EQ(val4 - val3, result4);
324 EXPECT_EQ(val4, val3 + result4);
325
326 LL_UInt128 val5({0x0123456789abcdef, 0xfedcba9876543210});
327 LL_UInt128 val6({0x1111222233334444, 0xaaaabbbbccccdddd});
328 LL_UInt128 result5({0xf0122345567889ab, 0x5431fedca9875432});
329 LL_UInt128 result6({0x0feddcbaa9877655, 0xabce01235678abcd});
330 EXPECT_EQ(val5 - val6, result5);
331 EXPECT_EQ(val5, val6 + result5);
332 EXPECT_EQ(val6 - val5, result6);
333 EXPECT_EQ(val6, val5 + result6);
334}
335
336TEST(LlvmLibcUIntClassTest, MultiplicationTests) {
337 LL_UInt128 val1({5, 0});
338 LL_UInt128 val2({10, 0});
339 LL_UInt128 result1({50, 0});
340 EXPECT_EQ((val1 * val2), result1);
341 EXPECT_EQ((val1 * val2), (val2 * val1)); // multiplication is commutative
342
343 // Check that the multiplication works accross the whole number
344 LL_UInt128 val3({0xf, 0});
345 LL_UInt128 val4({0x1111111111111111, 0x1111111111111111});
346 LL_UInt128 result2({0xffffffffffffffff, 0xffffffffffffffff});
347 EXPECT_EQ((val3 * val4), result2);
348 EXPECT_EQ((val3 * val4), (val4 * val3));
349
350 // Check that multiplication doesn't reorder the bits.
351 LL_UInt128 val5({2, 0});
352 LL_UInt128 val6({0x1357024675316420, 0x0123456776543210});
353 LL_UInt128 result3({0x26ae048cea62c840, 0x02468aceeca86420});
354
355 EXPECT_EQ((val5 * val6), result3);
356 EXPECT_EQ((val5 * val6), (val6 * val5));
357
358 // Make sure that multiplication handles overflow correctly.
359 LL_UInt128 val7(2);
360 LL_UInt128 val8({0x8000800080008000, 0x8000800080008000});
361 LL_UInt128 result4({0x0001000100010000, 0x0001000100010001});
362 EXPECT_EQ((val7 * val8), result4);
363 EXPECT_EQ((val7 * val8), (val8 * val7));
364
365 // val9 is the 128 bit mantissa of 1e60 as a float, val10 is the mantissa for
366 // 1e-60. They almost cancel on the high bits, but the result we're looking
367 // for is just the low bits. The full result would be
368 // 0x7fffffffffffffffffffffffffffffff3a4f32d17f40d08f917cf11d1e039c50
369 LL_UInt128 val9({0x01D762422C946590, 0x9F4F2726179A2245});
370 LL_UInt128 val10({0x3792F412CB06794D, 0xCDB02555653131B6});
371 LL_UInt128 result5({0x917cf11d1e039c50, 0x3a4f32d17f40d08f});
372 EXPECT_EQ((val9 * val10), result5);
373 EXPECT_EQ((val9 * val10), (val10 * val9));
374
375 // Test 192-bit multiplication
376 LL_UInt192 val11(
377 {0xffffffffffffffff, 0x01D762422C946590, 0x9F4F2726179A2245});
378 LL_UInt192 val12(
379 {0xffffffffffffffff, 0x3792F412CB06794D, 0xCDB02555653131B6});
380
381 LL_UInt192 result6(
382 {0x0000000000000001, 0xc695a9ab08652121, 0x5de7faf698d32732});
383 EXPECT_EQ((val11 * val12), result6);
384 EXPECT_EQ((val11 * val12), (val12 * val11));
385
386 LL_UInt256 val13({0xffffffffffffffff, 0x01D762422C946590, 0x9F4F2726179A2245,
387 0xffffffffffffffff});
388 LL_UInt256 val14({0xffffffffffffffff, 0xffffffffffffffff, 0x3792F412CB06794D,
389 0xCDB02555653131B6});
390 LL_UInt256 result7({0x0000000000000001, 0xfe289dbdd36b9a6f,
391 0x291de4c71d5f646c, 0xfd37221cb06d4978});
392 EXPECT_EQ((val13 * val14), result7);
393 EXPECT_EQ((val13 * val14), (val14 * val13));
394}
395
396TEST(LlvmLibcUIntClassTest, DivisionTests) {
397 LL_UInt128 val1({10, 0});
398 LL_UInt128 val2({5, 0});
399 LL_UInt128 result1({2, 0});
400 EXPECT_EQ((val1 / val2), result1);
401 EXPECT_EQ((val1 / result1), val2);
402
403 // Check that the division works accross the whole number
404 LL_UInt128 val3({0xffffffffffffffff, 0xffffffffffffffff});
405 LL_UInt128 val4({0xf, 0});
406 LL_UInt128 result2({0x1111111111111111, 0x1111111111111111});
407 EXPECT_EQ((val3 / val4), result2);
408 EXPECT_EQ((val3 / result2), val4);
409
410 // Check that division doesn't reorder the bits.
411 LL_UInt128 val5({0x26ae048cea62c840, 0x02468aceeca86420});
412 LL_UInt128 val6({2, 0});
413 LL_UInt128 result3({0x1357024675316420, 0x0123456776543210});
414 EXPECT_EQ((val5 / val6), result3);
415 EXPECT_EQ((val5 / result3), val6);
416
417 // Make sure that division handles inexact results correctly.
418 LL_UInt128 val7({1001, 0});
419 LL_UInt128 val8({10, 0});
420 LL_UInt128 result4({100, 0});
421 EXPECT_EQ((val7 / val8), result4);
422 EXPECT_EQ((val7 / result4), val8);
423
424 // Make sure that division handles divisors of one correctly.
425 LL_UInt128 val9({0x1234567812345678, 0x9abcdef09abcdef0});
426 LL_UInt128 val10({1, 0});
427 LL_UInt128 result5({0x1234567812345678, 0x9abcdef09abcdef0});
428 EXPECT_EQ((val9 / val10), result5);
429 EXPECT_EQ((val9 / result5), val10);
430
431 // Make sure that division handles results of slightly more than 1 correctly.
432 LL_UInt128 val11({1050, 0});
433 LL_UInt128 val12({1030, 0});
434 LL_UInt128 result6({1, 0});
435 EXPECT_EQ((val11 / val12), result6);
436
437 // Make sure that division handles dividing by zero correctly.
438 LL_UInt128 val13({1234, 0});
439 LL_UInt128 val14({0, 0});
440 EXPECT_FALSE(val13.div(val14).has_value());
441}
442
443TEST(LlvmLibcUIntClassTest, ModuloTests) {
444 LL_UInt128 val1({10, 0});
445 LL_UInt128 val2({5, 0});
446 LL_UInt128 result1({0, 0});
447 EXPECT_EQ((val1 % val2), result1);
448
449 LL_UInt128 val3({101, 0});
450 LL_UInt128 val4({10, 0});
451 LL_UInt128 result2({1, 0});
452 EXPECT_EQ((val3 % val4), result2);
453
454 LL_UInt128 val5({10000001, 0});
455 LL_UInt128 val6({10, 0});
456 LL_UInt128 result3({1, 0});
457 EXPECT_EQ((val5 % val6), result3);
458
459 LL_UInt128 val7({12345, 10});
460 LL_UInt128 val8({0, 1});
461 LL_UInt128 result4({12345, 0});
462 EXPECT_EQ((val7 % val8), result4);
463
464 LL_UInt128 val9({12345, 10});
465 LL_UInt128 val10({0, 11});
466 LL_UInt128 result5({12345, 10});
467 EXPECT_EQ((val9 % val10), result5);
468
469 LL_UInt128 val11({10, 10});
470 LL_UInt128 val12({10, 10});
471 LL_UInt128 result6({0, 0});
472 EXPECT_EQ((val11 % val12), result6);
473
474 LL_UInt128 val13({12345, 0});
475 LL_UInt128 val14({1, 0});
476 LL_UInt128 result7({0, 0});
477 EXPECT_EQ((val13 % val14), result7);
478
479 LL_UInt128 val15({0xffffffffffffffff, 0xffffffffffffffff});
480 LL_UInt128 val16({0x1111111111111111, 0x111111111111111});
481 LL_UInt128 result8({0xf, 0});
482 EXPECT_EQ((val15 % val16), result8);
483
484 LL_UInt128 val17({5076944270305263619, 54210108624}); // (10 ^ 30) + 3
485 LL_UInt128 val18({10, 0});
486 LL_UInt128 result9({3, 0});
487 EXPECT_EQ((val17 % val18), result9);
488}
489
490TEST(LlvmLibcUIntClassTest, PowerTests) {
491 LL_UInt128 val1({10, 0});
492 val1.pow_n(power: 30);
493 LL_UInt128 result1({5076944270305263616, 54210108624}); // (10 ^ 30)
494 EXPECT_EQ(val1, result1);
495
496 LL_UInt128 val2({1, 0});
497 val2.pow_n(power: 10);
498 LL_UInt128 result2({1, 0});
499 EXPECT_EQ(val2, result2);
500
501 LL_UInt128 val3({0, 0});
502 val3.pow_n(power: 10);
503 LL_UInt128 result3({0, 0});
504 EXPECT_EQ(val3, result3);
505
506 LL_UInt128 val4({10, 0});
507 val4.pow_n(power: 0);
508 LL_UInt128 result4({1, 0});
509 EXPECT_EQ(val4, result4);
510
511 // Test zero to the zero. Currently it returns 1, since that's the easiest
512 // result.
513 LL_UInt128 val5({0, 0});
514 val5.pow_n(power: 0);
515 LL_UInt128 result5({1, 0});
516 EXPECT_EQ(val5, result5);
517
518 // Test a number that overflows. 100 ^ 20 is larger than 2 ^ 128.
519 LL_UInt128 val6({100, 0});
520 val6.pow_n(power: 20);
521 LL_UInt128 result6({0xb9f5610000000000, 0x6329f1c35ca4bfab});
522 EXPECT_EQ(val6, result6);
523
524 // Test that both halves of the number are being used.
525 LL_UInt128 val7({1, 1});
526 val7.pow_n(power: 2);
527 LL_UInt128 result7({1, 2});
528 EXPECT_EQ(val7, result7);
529
530 LL_UInt128 val_pow_two;
531 LL_UInt128 result_pow_two;
532 for (size_t i = 0; i < 128; ++i) {
533 val_pow_two = 2;
534 val_pow_two.pow_n(power: i);
535 result_pow_two = 1;
536 result_pow_two = result_pow_two << i;
537 EXPECT_EQ(val_pow_two, result_pow_two);
538 }
539}
540
541TEST(LlvmLibcUIntClassTest, ShiftLeftTests) {
542 LL_UInt128 val1(0x0123456789abcdef);
543 LL_UInt128 result1(0x123456789abcdef0);
544 EXPECT_EQ((val1 << 4), result1);
545
546 LL_UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0});
547 LL_UInt128 result2({0x02468ace00000000, 0x9abcdef013579bdf});
548 EXPECT_EQ((val2 << 32), result2);
549 LL_UInt128 val22 = val2;
550 val22 <<= 32;
551 EXPECT_EQ(val22, result2);
552
553 LL_UInt128 result3({0, 0x13579bdf02468ace});
554 EXPECT_EQ((val2 << 64), result3);
555
556 LL_UInt128 result4({0, 0x02468ace00000000});
557 EXPECT_EQ((val2 << 96), result4);
558
559 LL_UInt128 result5({0, 0x2468ace000000000});
560 EXPECT_EQ((val2 << 100), result5);
561
562 LL_UInt192 val3({1, 0, 0});
563 LL_UInt192 result7({0, 1, 0});
564 EXPECT_EQ((val3 << 64), result7);
565}
566
567TEST(LlvmLibcUIntClassTest, ShiftRightTests) {
568 LL_UInt128 val1(0x0123456789abcdef);
569 LL_UInt128 result1(0x00123456789abcde);
570 EXPECT_EQ((val1 >> 4), result1);
571
572 LL_UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0});
573 LL_UInt128 result2({0x9abcdef013579bdf, 0x0000000012345678});
574 EXPECT_EQ((val2 >> 32), result2);
575 LL_UInt128 val22 = val2;
576 val22 >>= 32;
577 EXPECT_EQ(val22, result2);
578
579 LL_UInt128 result3({0x123456789abcdef0, 0});
580 EXPECT_EQ((val2 >> 64), result3);
581
582 LL_UInt128 result4({0x0000000012345678, 0});
583 EXPECT_EQ((val2 >> 96), result4);
584
585 LL_UInt128 result5({0x0000000001234567, 0});
586 EXPECT_EQ((val2 >> 100), result5);
587
588 LL_UInt128 v1({0x1111222233334444, 0xaaaabbbbccccdddd});
589 LL_UInt128 r1({0xaaaabbbbccccdddd, 0});
590 EXPECT_EQ((v1 >> 64), r1);
591
592 LL_UInt192 v2({0x1111222233334444, 0x5555666677778888, 0xaaaabbbbccccdddd});
593 LL_UInt192 r2({0x5555666677778888, 0xaaaabbbbccccdddd, 0});
594 LL_UInt192 r3({0xaaaabbbbccccdddd, 0, 0});
595 EXPECT_EQ((v2 >> 64), r2);
596 EXPECT_EQ((v2 >> 128), r3);
597 EXPECT_EQ((r2 >> 64), r3);
598
599 LL_UInt192 val3({0, 0, 1});
600 LL_UInt192 result7({0, 1, 0});
601 EXPECT_EQ((val3 >> 64), result7);
602}
603
604TEST(LlvmLibcUIntClassTest, AndTests) {
605 LL_UInt128 base({0xffff00000000ffff, 0xffffffff00000000});
606 LL_UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff});
607 uint64_t val64 = 0xf0f0f0f00f0f0f0f;
608 int val32 = 0x0f0f0f0f;
609 LL_UInt128 result128({0xf0f0000000000f0f, 0xff00ff0000000000});
610 LL_UInt128 result64(0xf0f0000000000f0f);
611 LL_UInt128 result32(0x00000f0f);
612 EXPECT_EQ((base & val128), result128);
613 EXPECT_EQ((base & val64), result64);
614 EXPECT_EQ((base & val32), result32);
615}
616
617TEST(LlvmLibcUIntClassTest, OrTests) {
618 LL_UInt128 base({0xffff00000000ffff, 0xffffffff00000000});
619 LL_UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff});
620 uint64_t val64 = 0xf0f0f0f00f0f0f0f;
621 int val32 = 0x0f0f0f0f;
622 LL_UInt128 result128({0xfffff0f00f0fffff, 0xffffffff00ff00ff});
623 LL_UInt128 result64({0xfffff0f00f0fffff, 0xffffffff00000000});
624 LL_UInt128 result32({0xffff00000f0fffff, 0xffffffff00000000});
625 EXPECT_EQ((base | val128), result128);
626 EXPECT_EQ((base | val64), result64);
627 EXPECT_EQ((base | val32), result32);
628}
629
630TEST(LlvmLibcUIntClassTest, CompoundAssignments) {
631 LL_UInt128 x({0xffff00000000ffff, 0xffffffff00000000});
632 LL_UInt128 b({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff});
633
634 LL_UInt128 a = x;
635 a |= b;
636 LL_UInt128 or_result({0xfffff0f00f0fffff, 0xffffffff00ff00ff});
637 EXPECT_EQ(a, or_result);
638
639 a = x;
640 a &= b;
641 LL_UInt128 and_result({0xf0f0000000000f0f, 0xff00ff0000000000});
642 EXPECT_EQ(a, and_result);
643
644 a = x;
645 a ^= b;
646 LL_UInt128 xor_result({0x0f0ff0f00f0ff0f0, 0x00ff00ff00ff00ff});
647 EXPECT_EQ(a, xor_result);
648
649 a = LL_UInt128(uint64_t(0x0123456789abcdef));
650 LL_UInt128 shift_left_result(uint64_t(0x123456789abcdef0));
651 a <<= 4;
652 EXPECT_EQ(a, shift_left_result);
653
654 a = LL_UInt128(uint64_t(0x123456789abcdef1));
655 LL_UInt128 shift_right_result(uint64_t(0x0123456789abcdef));
656 a >>= 4;
657 EXPECT_EQ(a, shift_right_result);
658
659 a = LL_UInt128({0xf000000000000001, 0});
660 b = LL_UInt128({0x100000000000000f, 0});
661 LL_UInt128 add_result({0x10, 0x1});
662 a += b;
663 EXPECT_EQ(a, add_result);
664
665 a = LL_UInt128({0xf, 0});
666 b = LL_UInt128({0x1111111111111111, 0x1111111111111111});
667 LL_UInt128 mul_result({0xffffffffffffffff, 0xffffffffffffffff});
668 a *= b;
669 EXPECT_EQ(a, mul_result);
670}
671
672TEST(LlvmLibcUIntClassTest, UnaryPredecrement) {
673 LL_UInt128 a = LL_UInt128({0x1111111111111111, 0x1111111111111111});
674 ++a;
675 EXPECT_EQ(a, LL_UInt128({0x1111111111111112, 0x1111111111111111}));
676
677 a = LL_UInt128({0xffffffffffffffff, 0x0});
678 ++a;
679 EXPECT_EQ(a, LL_UInt128({0x0, 0x1}));
680
681 a = LL_UInt128({0xffffffffffffffff, 0xffffffffffffffff});
682 ++a;
683 EXPECT_EQ(a, LL_UInt128({0x0, 0x0}));
684}
685
686TEST(LlvmLibcUIntClassTest, EqualsTests) {
687 LL_UInt128 a1({0xffffffff00000000, 0xffff00000000ffff});
688 LL_UInt128 a2({0xffffffff00000000, 0xffff00000000ffff});
689 LL_UInt128 b({0xff00ff0000ff00ff, 0xf0f0f0f00f0f0f0f});
690 LL_UInt128 a_reversed({0xffff00000000ffff, 0xffffffff00000000});
691 LL_UInt128 a_upper(0xffff00000000ffff);
692 LL_UInt128 a_lower(0xffffffff00000000);
693 ASSERT_TRUE(a1 == a1);
694 ASSERT_TRUE(a1 == a2);
695 ASSERT_FALSE(a1 == b);
696 ASSERT_FALSE(a1 == a_reversed);
697 ASSERT_FALSE(a1 == a_lower);
698 ASSERT_FALSE(a1 == a_upper);
699 ASSERT_TRUE(a_lower != a_upper);
700}
701
702TEST(LlvmLibcUIntClassTest, ComparisonTests) {
703 LL_UInt128 a({0xffffffff00000000, 0xffff00000000ffff});
704 LL_UInt128 b({0xff00ff0000ff00ff, 0xf0f0f0f00f0f0f0f});
705 EXPECT_GT(a, b);
706 EXPECT_GE(a, b);
707 EXPECT_LT(b, a);
708 EXPECT_LE(b, a);
709
710 LL_UInt128 x(0xffffffff00000000);
711 LL_UInt128 y(0x00000000ffffffff);
712 EXPECT_GT(x, y);
713 EXPECT_GE(x, y);
714 EXPECT_LT(y, x);
715 EXPECT_LE(y, x);
716
717 EXPECT_LE(a, a);
718 EXPECT_GE(a, a);
719}
720
721TEST(LlvmLibcUIntClassTest, FullMulTests) {
722 LL_UInt128 a({0xffffffffffffffffULL, 0xffffffffffffffffULL});
723 LL_UInt128 b({0xfedcba9876543210ULL, 0xfefdfcfbfaf9f8f7ULL});
724 LL_UInt256 r({0x0123456789abcdf0ULL, 0x0102030405060708ULL,
725 0xfedcba987654320fULL, 0xfefdfcfbfaf9f8f7ULL});
726 LL_UInt128 r_hi({0xfedcba987654320eULL, 0xfefdfcfbfaf9f8f7ULL});
727
728 EXPECT_EQ(a.ful_mul(b), r);
729 EXPECT_EQ(a.quick_mul_hi(b), r_hi);
730
731 LL_UInt192 c(
732 {0x7766554433221101ULL, 0xffeeddccbbaa9988ULL, 0x1f2f3f4f5f6f7f8fULL});
733 LL_UInt320 rr({0x8899aabbccddeeffULL, 0x0011223344556677ULL,
734 0x583715f4d3b29171ULL, 0xffeeddccbbaa9988ULL,
735 0x1f2f3f4f5f6f7f8fULL});
736
737 EXPECT_EQ(a.ful_mul(c), rr);
738 EXPECT_EQ(a.ful_mul(c), c.ful_mul(a));
739}
740
741#define TEST_QUICK_MUL_HI(Bits, Error) \
742 do { \
743 LL_UInt##Bits a = ~LL_UInt##Bits(0); \
744 LL_UInt##Bits hi = a.quick_mul_hi(a); \
745 LL_UInt##Bits trunc = static_cast<LL_UInt##Bits>(a.ful_mul(a) >> Bits); \
746 uint64_t overflow = trunc.sub_overflow(hi); \
747 EXPECT_EQ(overflow, uint64_t(0)); \
748 EXPECT_LE(uint64_t(trunc), uint64_t(Error)); \
749 } while (0)
750
751TEST(LlvmLibcUIntClassTest, QuickMulHiTests) {
752 TEST_QUICK_MUL_HI(128, 1);
753 TEST_QUICK_MUL_HI(192, 2);
754 TEST_QUICK_MUL_HI(256, 3);
755 TEST_QUICK_MUL_HI(512, 7);
756}
757
758TEST(LlvmLibcUIntClassTest, ConstexprInitTests) {
759 constexpr LL_UInt128 add = LL_UInt128(1) + LL_UInt128(2);
760 ASSERT_EQ(add, LL_UInt128(3));
761 constexpr LL_UInt128 sub = LL_UInt128(5) - LL_UInt128(4);
762 ASSERT_EQ(sub, LL_UInt128(1));
763}
764
765#define TEST_QUICK_DIV_UINT32_POW2(x, e) \
766 do { \
767 LL_UInt320 y({0x8899aabbccddeeffULL, 0x0011223344556677ULL, \
768 0x583715f4d3b29171ULL, 0xffeeddccbbaa9988ULL, \
769 0x1f2f3f4f5f6f7f8fULL}); \
770 LL_UInt320 d = LL_UInt320(x); \
771 d <<= e; \
772 LL_UInt320 q1 = y / d; \
773 LL_UInt320 r1 = y % d; \
774 LL_UInt320 r2 = *y.div_uint_half_times_pow_2(x, e); \
775 EXPECT_EQ(q1, y); \
776 EXPECT_EQ(r1, r2); \
777 } while (0)
778
779TEST(LlvmLibcUIntClassTest, DivUInt32TimesPow2Tests) {
780 for (size_t i = 0; i < 320; i += 32) {
781 TEST_QUICK_DIV_UINT32_POW2(1, i);
782 TEST_QUICK_DIV_UINT32_POW2(13151719, i);
783 }
784
785 TEST_QUICK_DIV_UINT32_POW2(1, 75);
786 TEST_QUICK_DIV_UINT32_POW2(1, 101);
787
788 TEST_QUICK_DIV_UINT32_POW2(1000000000, 75);
789 TEST_QUICK_DIV_UINT32_POW2(1000000000, 101);
790}
791
792TEST(LlvmLibcUIntClassTest, ComparisonInt128Tests) {
793 LL_Int128 a(123);
794 LL_Int128 b(0);
795 LL_Int128 c(-1);
796
797 ASSERT_TRUE(a == a);
798 ASSERT_TRUE(b == b);
799 ASSERT_TRUE(c == c);
800
801 ASSERT_TRUE(a != b);
802 ASSERT_TRUE(a != c);
803 ASSERT_TRUE(b != a);
804 ASSERT_TRUE(b != c);
805 ASSERT_TRUE(c != a);
806 ASSERT_TRUE(c != b);
807
808 ASSERT_TRUE(a > b);
809 ASSERT_TRUE(a >= b);
810 ASSERT_TRUE(a > c);
811 ASSERT_TRUE(a >= c);
812 ASSERT_TRUE(b > c);
813 ASSERT_TRUE(b >= c);
814
815 ASSERT_TRUE(b < a);
816 ASSERT_TRUE(b <= a);
817 ASSERT_TRUE(c < a);
818 ASSERT_TRUE(c <= a);
819 ASSERT_TRUE(c < b);
820 ASSERT_TRUE(c <= b);
821}
822
823TEST(LlvmLibcUIntClassTest, BasicArithmeticInt128Tests) {
824 LL_Int128 a(123);
825 LL_Int128 b(0);
826 LL_Int128 c(-3);
827
828 ASSERT_EQ(a * a, LL_Int128(123 * 123));
829 ASSERT_EQ(a * c, LL_Int128(-369));
830 ASSERT_EQ(c * a, LL_Int128(-369));
831 ASSERT_EQ(c * c, LL_Int128(9));
832 ASSERT_EQ(a * b, b);
833 ASSERT_EQ(b * a, b);
834 ASSERT_EQ(b * c, b);
835 ASSERT_EQ(c * b, b);
836}
837
838#ifdef LIBC_TYPES_HAS_INT128
839
840TEST(LlvmLibcUIntClassTest, ConstructorFromUInt128Tests) {
841 __uint128_t a = (__uint128_t(123) << 64) + 1;
842 __int128_t b = -static_cast<__int128_t>(a);
843 LL_Int128 c(a);
844 LL_Int128 d(b);
845
846 LL_Int192 e(a);
847 LL_Int192 f(b);
848
849 ASSERT_EQ(static_cast<int>(c), 1);
850 ASSERT_EQ(static_cast<int>(c >> 64), 123);
851 ASSERT_EQ(static_cast<uint64_t>(d), static_cast<uint64_t>(b));
852 ASSERT_EQ(static_cast<uint64_t>(d >> 64), static_cast<uint64_t>(b >> 64));
853 ASSERT_EQ(c + d, LL_Int128(a + b));
854
855 ASSERT_EQ(static_cast<int>(e), 1);
856 ASSERT_EQ(static_cast<int>(e >> 64), 123);
857 ASSERT_EQ(static_cast<uint64_t>(f), static_cast<uint64_t>(b));
858 ASSERT_EQ(static_cast<uint64_t>(f >> 64), static_cast<uint64_t>(b >> 64));
859 ASSERT_EQ(LL_UInt192(e + f), LL_UInt192(a + b));
860}
861
862TEST(LlvmLibcUIntClassTest, WordTypeUInt128Tests) {
863 using LL_UInt256_128 = BigInt<256, false, __uint128_t>;
864 using LL_UInt128_128 = BigInt<128, false, __uint128_t>;
865
866 LL_UInt256_128 a(1);
867
868 ASSERT_EQ(static_cast<int>(a), 1);
869 a = (a << 128) + 2;
870 ASSERT_EQ(static_cast<int>(a), 2);
871 ASSERT_EQ(static_cast<uint64_t>(a), uint64_t(2));
872 a = (a << 32) + 3;
873 ASSERT_EQ(static_cast<int>(a), 3);
874 ASSERT_EQ(static_cast<uint64_t>(a), uint64_t(0x2'0000'0003));
875 ASSERT_EQ(static_cast<int>(a >> 32), 2);
876 ASSERT_EQ(static_cast<int>(a >> (128 + 32)), 1);
877
878 LL_UInt128_128 b(__uint128_t(1) << 127);
879 LL_UInt128_128 c(b);
880 a = b.ful_mul(other: c);
881
882 ASSERT_EQ(static_cast<int>(a >> 254), 1);
883
884 LL_UInt256_128 d = LL_UInt256_128(123) << 4;
885 ASSERT_EQ(static_cast<int>(d), 123 << 4);
886 LL_UInt256_128 e = a / d;
887 LL_UInt256_128 f = a % d;
888 LL_UInt256_128 r = *a.div_uint_half_times_pow_2(x: 123, e: 4);
889 EXPECT_TRUE(e == a);
890 EXPECT_TRUE(f == r);
891}
892
893#endif // LIBC_TYPES_HAS_INT128
894
895TEST(LlvmLibcUIntClassTest, OtherWordTypeTests) {
896 using LL_UInt96 = BigInt<96, false, uint32_t>;
897
898 LL_UInt96 a(1);
899
900 ASSERT_EQ(static_cast<int>(a), 1);
901 a = (a << 32) + 2;
902 ASSERT_EQ(static_cast<int>(a), 2);
903 ASSERT_EQ(static_cast<uint64_t>(a), uint64_t(0x1'0000'0002));
904 a = (a << 32) + 3;
905 ASSERT_EQ(static_cast<int>(a), 3);
906 ASSERT_EQ(static_cast<int>(a >> 32), 2);
907 ASSERT_EQ(static_cast<int>(a >> 64), 1);
908}
909
910} // namespace LIBC_NAMESPACE
911

source code of libc/test/src/__support/big_int_test.cpp