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 17 namespace LIBC_NAMESPACE { 18 19 enum Value { ZERO, ONE, TWO, MIN, MAX }; 20 21 template <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 36 using 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 53 TYPED_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 64 TYPED_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 74 TYPED_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 86 template <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 92 TEST(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>("1927508279017230597"); 96 const T b = parse_bigint<T>("278789278723478925"); 97 const T s = parse_bigint<T>("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 106 TEST(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[] = {{"-4", "3", "-12"}, 114 {"-3", "-3", "9"}, 115 {"1927508279017230597", "278789278723478925", 116 "537368642840747885329125014794668225"}}; 117 for (auto tc : test_cases) { 118 const T a = parse_bigint<T>(tc.a); 119 const T b = parse_bigint<T>(tc.b); 120 const T mul = parse_bigint<T>(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 136 TYPED_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 159 TYPED_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 167 TYPED_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 193 TYPED_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 208 using 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. 212 using LL_UInt128 = UInt<128>; 213 using LL_UInt192 = UInt<192>; 214 using LL_UInt256 = UInt<256>; 215 using LL_UInt320 = UInt<320>; 216 using LL_UInt512 = UInt<512>; 217 using LL_UInt1024 = UInt<1024>; 218 219 using LL_Int128 = Int<128>; 220 using LL_Int192 = Int<192>; 221 222 TEST(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>(value); 230 double forth = cpp::bit_cast<double>(back); 231 EXPECT_TRUE(value == forth); 232 } 233 } 234 235 #ifdef LIBC_TYPES_HAS_INT128 236 TEST(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>(value); 242 __uint128_t forth = cpp::bit_cast<__uint128_t>(back); 243 EXPECT_TRUE(value == forth); 244 } 245 } 246 #endif // LIBC_TYPES_HAS_INT128 247 248 #ifdef LIBC_TYPES_HAS_FLOAT128 249 TEST(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>(value); 255 float128 forth = cpp::bit_cast<float128>(back); 256 EXPECT_TRUE(value == forth); 257 } 258 } 259 #endif // LIBC_TYPES_HAS_FLOAT128 260 261 TEST(LlvmLibcUIntClassTest, BasicInit) { 262 LL_UInt128 half_val(12345); 263 LL_UInt128 full_val({12345, 67890}); 264 ASSERT_TRUE(half_val != full_val); 265 } 266 267 TEST(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 307 TEST(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 336 TEST(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 396 TEST(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 443 TEST(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 490 TEST(LlvmLibcUIntClassTest, PowerTests) { 491 LL_UInt128 val1({10, 0}); 492 val1.pow_n(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(10); 498 LL_UInt128 result2({1, 0}); 499 EXPECT_EQ(val2, result2); 500 501 LL_UInt128 val3({0, 0}); 502 val3.pow_n(10); 503 LL_UInt128 result3({0, 0}); 504 EXPECT_EQ(val3, result3); 505 506 LL_UInt128 val4({10, 0}); 507 val4.pow_n(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(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(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(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(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 541 TEST(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_UInt128 result6({0, 0}); 563 EXPECT_EQ((val2 << 128), result6); 564 EXPECT_EQ((val2 << 256), result6); 565 566 LL_UInt192 val3({1, 0, 0}); 567 LL_UInt192 result7({0, 1, 0}); 568 EXPECT_EQ((val3 << 64), result7); 569 } 570 571 TEST(LlvmLibcUIntClassTest, ShiftRightTests) { 572 LL_UInt128 val1(0x0123456789abcdef); 573 LL_UInt128 result1(0x00123456789abcde); 574 EXPECT_EQ((val1 >> 4), result1); 575 576 LL_UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0}); 577 LL_UInt128 result2({0x9abcdef013579bdf, 0x0000000012345678}); 578 EXPECT_EQ((val2 >> 32), result2); 579 LL_UInt128 val22 = val2; 580 val22 >>= 32; 581 EXPECT_EQ(val22, result2); 582 583 LL_UInt128 result3({0x123456789abcdef0, 0}); 584 EXPECT_EQ((val2 >> 64), result3); 585 586 LL_UInt128 result4({0x0000000012345678, 0}); 587 EXPECT_EQ((val2 >> 96), result4); 588 589 LL_UInt128 result5({0x0000000001234567, 0}); 590 EXPECT_EQ((val2 >> 100), result5); 591 592 LL_UInt128 result6({0, 0}); 593 EXPECT_EQ((val2 >> 128), result6); 594 EXPECT_EQ((val2 >> 256), result6); 595 596 LL_UInt128 v1({0x1111222233334444, 0xaaaabbbbccccdddd}); 597 LL_UInt128 r1({0xaaaabbbbccccdddd, 0}); 598 EXPECT_EQ((v1 >> 64), r1); 599 600 LL_UInt192 v2({0x1111222233334444, 0x5555666677778888, 0xaaaabbbbccccdddd}); 601 LL_UInt192 r2({0x5555666677778888, 0xaaaabbbbccccdddd, 0}); 602 LL_UInt192 r3({0xaaaabbbbccccdddd, 0, 0}); 603 EXPECT_EQ((v2 >> 64), r2); 604 EXPECT_EQ((v2 >> 128), r3); 605 EXPECT_EQ((r2 >> 64), r3); 606 607 LL_UInt192 val3({0, 0, 1}); 608 LL_UInt192 result7({0, 1, 0}); 609 EXPECT_EQ((val3 >> 64), result7); 610 } 611 612 TEST(LlvmLibcUIntClassTest, AndTests) { 613 LL_UInt128 base({0xffff00000000ffff, 0xffffffff00000000}); 614 LL_UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff}); 615 uint64_t val64 = 0xf0f0f0f00f0f0f0f; 616 int val32 = 0x0f0f0f0f; 617 LL_UInt128 result128({0xf0f0000000000f0f, 0xff00ff0000000000}); 618 LL_UInt128 result64(0xf0f0000000000f0f); 619 LL_UInt128 result32(0x00000f0f); 620 EXPECT_EQ((base & val128), result128); 621 EXPECT_EQ((base & val64), result64); 622 EXPECT_EQ((base & val32), result32); 623 } 624 625 TEST(LlvmLibcUIntClassTest, OrTests) { 626 LL_UInt128 base({0xffff00000000ffff, 0xffffffff00000000}); 627 LL_UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff}); 628 uint64_t val64 = 0xf0f0f0f00f0f0f0f; 629 int val32 = 0x0f0f0f0f; 630 LL_UInt128 result128({0xfffff0f00f0fffff, 0xffffffff00ff00ff}); 631 LL_UInt128 result64({0xfffff0f00f0fffff, 0xffffffff00000000}); 632 LL_UInt128 result32({0xffff00000f0fffff, 0xffffffff00000000}); 633 EXPECT_EQ((base | val128), result128); 634 EXPECT_EQ((base | val64), result64); 635 EXPECT_EQ((base | val32), result32); 636 } 637 638 TEST(LlvmLibcUIntClassTest, CompoundAssignments) { 639 LL_UInt128 x({0xffff00000000ffff, 0xffffffff00000000}); 640 LL_UInt128 b({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff}); 641 642 LL_UInt128 a = x; 643 a |= b; 644 LL_UInt128 or_result({0xfffff0f00f0fffff, 0xffffffff00ff00ff}); 645 EXPECT_EQ(a, or_result); 646 647 a = x; 648 a &= b; 649 LL_UInt128 and_result({0xf0f0000000000f0f, 0xff00ff0000000000}); 650 EXPECT_EQ(a, and_result); 651 652 a = x; 653 a ^= b; 654 LL_UInt128 xor_result({0x0f0ff0f00f0ff0f0, 0x00ff00ff00ff00ff}); 655 EXPECT_EQ(a, xor_result); 656 657 a = LL_UInt128(uint64_t(0x0123456789abcdef)); 658 LL_UInt128 shift_left_result(uint64_t(0x123456789abcdef0)); 659 a <<= 4; 660 EXPECT_EQ(a, shift_left_result); 661 662 a = LL_UInt128(uint64_t(0x123456789abcdef1)); 663 LL_UInt128 shift_right_result(uint64_t(0x0123456789abcdef)); 664 a >>= 4; 665 EXPECT_EQ(a, shift_right_result); 666 667 a = LL_UInt128({0xf000000000000001, 0}); 668 b = LL_UInt128({0x100000000000000f, 0}); 669 LL_UInt128 add_result({0x10, 0x1}); 670 a += b; 671 EXPECT_EQ(a, add_result); 672 673 a = LL_UInt128({0xf, 0}); 674 b = LL_UInt128({0x1111111111111111, 0x1111111111111111}); 675 LL_UInt128 mul_result({0xffffffffffffffff, 0xffffffffffffffff}); 676 a *= b; 677 EXPECT_EQ(a, mul_result); 678 } 679 680 TEST(LlvmLibcUIntClassTest, UnaryPredecrement) { 681 LL_UInt128 a = LL_UInt128({0x1111111111111111, 0x1111111111111111}); 682 ++a; 683 EXPECT_EQ(a, LL_UInt128({0x1111111111111112, 0x1111111111111111})); 684 685 a = LL_UInt128({0xffffffffffffffff, 0x0}); 686 ++a; 687 EXPECT_EQ(a, LL_UInt128({0x0, 0x1})); 688 689 a = LL_UInt128({0xffffffffffffffff, 0xffffffffffffffff}); 690 ++a; 691 EXPECT_EQ(a, LL_UInt128({0x0, 0x0})); 692 } 693 694 TEST(LlvmLibcUIntClassTest, EqualsTests) { 695 LL_UInt128 a1({0xffffffff00000000, 0xffff00000000ffff}); 696 LL_UInt128 a2({0xffffffff00000000, 0xffff00000000ffff}); 697 LL_UInt128 b({0xff00ff0000ff00ff, 0xf0f0f0f00f0f0f0f}); 698 LL_UInt128 a_reversed({0xffff00000000ffff, 0xffffffff00000000}); 699 LL_UInt128 a_upper(0xffff00000000ffff); 700 LL_UInt128 a_lower(0xffffffff00000000); 701 ASSERT_TRUE(a1 == a1); 702 ASSERT_TRUE(a1 == a2); 703 ASSERT_FALSE(a1 == b); 704 ASSERT_FALSE(a1 == a_reversed); 705 ASSERT_FALSE(a1 == a_lower); 706 ASSERT_FALSE(a1 == a_upper); 707 ASSERT_TRUE(a_lower != a_upper); 708 } 709 710 TEST(LlvmLibcUIntClassTest, ComparisonTests) { 711 LL_UInt128 a({0xffffffff00000000, 0xffff00000000ffff}); 712 LL_UInt128 b({0xff00ff0000ff00ff, 0xf0f0f0f00f0f0f0f}); 713 EXPECT_GT(a, b); 714 EXPECT_GE(a, b); 715 EXPECT_LT(b, a); 716 EXPECT_LE(b, a); 717 718 LL_UInt128 x(0xffffffff00000000); 719 LL_UInt128 y(0x00000000ffffffff); 720 EXPECT_GT(x, y); 721 EXPECT_GE(x, y); 722 EXPECT_LT(y, x); 723 EXPECT_LE(y, x); 724 725 EXPECT_LE(a, a); 726 EXPECT_GE(a, a); 727 } 728 729 TEST(LlvmLibcUIntClassTest, FullMulTests) { 730 LL_UInt128 a({0xffffffffffffffffULL, 0xffffffffffffffffULL}); 731 LL_UInt128 b({0xfedcba9876543210ULL, 0xfefdfcfbfaf9f8f7ULL}); 732 LL_UInt256 r({0x0123456789abcdf0ULL, 0x0102030405060708ULL, 733 0xfedcba987654320fULL, 0xfefdfcfbfaf9f8f7ULL}); 734 LL_UInt128 r_hi({0xfedcba987654320eULL, 0xfefdfcfbfaf9f8f7ULL}); 735 736 EXPECT_EQ(a.ful_mul(b), r); 737 EXPECT_EQ(a.quick_mul_hi(b), r_hi); 738 739 LL_UInt192 c( 740 {0x7766554433221101ULL, 0xffeeddccbbaa9988ULL, 0x1f2f3f4f5f6f7f8fULL}); 741 LL_UInt320 rr({0x8899aabbccddeeffULL, 0x0011223344556677ULL, 742 0x583715f4d3b29171ULL, 0xffeeddccbbaa9988ULL, 743 0x1f2f3f4f5f6f7f8fULL}); 744 745 EXPECT_EQ(a.ful_mul(c), rr); 746 EXPECT_EQ(a.ful_mul(c), c.ful_mul(a)); 747 } 748 749 #define TEST_QUICK_MUL_HI(Bits, Error) \ 750 do { \ 751 LL_UInt##Bits a = ~LL_UInt##Bits(0); \ 752 LL_UInt##Bits hi = a.quick_mul_hi(a); \ 753 LL_UInt##Bits trunc = static_cast<LL_UInt##Bits>(a.ful_mul(a) >> Bits); \ 754 uint64_t overflow = trunc.sub_overflow(hi); \ 755 EXPECT_EQ(overflow, uint64_t(0)); \ 756 EXPECT_LE(uint64_t(trunc), uint64_t(Error)); \ 757 } while (0) 758 759 TEST(LlvmLibcUIntClassTest, QuickMulHiTests) { 760 TEST_QUICK_MUL_HI(128, 1); 761 TEST_QUICK_MUL_HI(192, 2); 762 TEST_QUICK_MUL_HI(256, 3); 763 TEST_QUICK_MUL_HI(512, 7); 764 } 765 766 TEST(LlvmLibcUIntClassTest, ConstexprInitTests) { 767 constexpr LL_UInt128 add = LL_UInt128(1) + LL_UInt128(2); 768 ASSERT_EQ(add, LL_UInt128(3)); 769 constexpr LL_UInt128 sub = LL_UInt128(5) - LL_UInt128(4); 770 ASSERT_EQ(sub, LL_UInt128(1)); 771 } 772 773 #define TEST_QUICK_DIV_UINT32_POW2(x, e) \ 774 do { \ 775 LL_UInt320 y({0x8899aabbccddeeffULL, 0x0011223344556677ULL, \ 776 0x583715f4d3b29171ULL, 0xffeeddccbbaa9988ULL, \ 777 0x1f2f3f4f5f6f7f8fULL}); \ 778 LL_UInt320 d = LL_UInt320(x); \ 779 d <<= e; \ 780 LL_UInt320 q1 = y / d; \ 781 LL_UInt320 r1 = y % d; \ 782 LL_UInt320 r2 = *y.div_uint_half_times_pow_2(x, e); \ 783 EXPECT_EQ(q1, y); \ 784 EXPECT_EQ(r1, r2); \ 785 } while (0) 786 787 TEST(LlvmLibcUIntClassTest, DivUInt32TimesPow2Tests) { 788 for (size_t i = 0; i < 320; i += 32) { 789 TEST_QUICK_DIV_UINT32_POW2(1, i); 790 TEST_QUICK_DIV_UINT32_POW2(13151719, i); 791 } 792 793 TEST_QUICK_DIV_UINT32_POW2(1, 75); 794 TEST_QUICK_DIV_UINT32_POW2(1, 101); 795 796 TEST_QUICK_DIV_UINT32_POW2(1000000000, 75); 797 TEST_QUICK_DIV_UINT32_POW2(1000000000, 101); 798 } 799 800 TEST(LlvmLibcUIntClassTest, ComparisonInt128Tests) { 801 LL_Int128 a(123); 802 LL_Int128 b(0); 803 LL_Int128 c(-1); 804 805 ASSERT_TRUE(a == a); 806 ASSERT_TRUE(b == b); 807 ASSERT_TRUE(c == c); 808 809 ASSERT_TRUE(a != b); 810 ASSERT_TRUE(a != c); 811 ASSERT_TRUE(b != a); 812 ASSERT_TRUE(b != c); 813 ASSERT_TRUE(c != a); 814 ASSERT_TRUE(c != b); 815 816 ASSERT_TRUE(a > b); 817 ASSERT_TRUE(a >= b); 818 ASSERT_TRUE(a > c); 819 ASSERT_TRUE(a >= c); 820 ASSERT_TRUE(b > c); 821 ASSERT_TRUE(b >= c); 822 823 ASSERT_TRUE(b < a); 824 ASSERT_TRUE(b <= a); 825 ASSERT_TRUE(c < a); 826 ASSERT_TRUE(c <= a); 827 ASSERT_TRUE(c < b); 828 ASSERT_TRUE(c <= b); 829 } 830 831 TEST(LlvmLibcUIntClassTest, BasicArithmeticInt128Tests) { 832 LL_Int128 a(123); 833 LL_Int128 b(0); 834 LL_Int128 c(-3); 835 836 ASSERT_EQ(a * a, LL_Int128(123 * 123)); 837 ASSERT_EQ(a * c, LL_Int128(-369)); 838 ASSERT_EQ(c * a, LL_Int128(-369)); 839 ASSERT_EQ(c * c, LL_Int128(9)); 840 ASSERT_EQ(a * b, b); 841 ASSERT_EQ(b * a, b); 842 ASSERT_EQ(b * c, b); 843 ASSERT_EQ(c * b, b); 844 } 845 846 #ifdef LIBC_TYPES_HAS_INT128 847 848 TEST(LlvmLibcUIntClassTest, ConstructorFromUInt128Tests) { 849 __uint128_t a = (__uint128_t(123) << 64) + 1; 850 __int128_t b = -static_cast<__int128_t>(a); 851 LL_Int128 c(a); 852 LL_Int128 d(b); 853 854 LL_Int192 e(a); 855 LL_Int192 f(b); 856 857 ASSERT_EQ(static_cast<int>(c), 1); 858 ASSERT_EQ(static_cast<int>(c >> 64), 123); 859 ASSERT_EQ(static_cast<uint64_t>(d), static_cast<uint64_t>(b)); 860 ASSERT_EQ(static_cast<uint64_t>(d >> 64), static_cast<uint64_t>(b >> 64)); 861 ASSERT_EQ(c + d, LL_Int128(a + b)); 862 863 ASSERT_EQ(static_cast<int>(e), 1); 864 ASSERT_EQ(static_cast<int>(e >> 64), 123); 865 ASSERT_EQ(static_cast<uint64_t>(f), static_cast<uint64_t>(b)); 866 ASSERT_EQ(static_cast<uint64_t>(f >> 64), static_cast<uint64_t>(b >> 64)); 867 ASSERT_EQ(LL_UInt192(e + f), LL_UInt192(a + b)); 868 } 869 870 TEST(LlvmLibcUIntClassTest, WordTypeUInt128Tests) { 871 using LL_UInt256_128 = BigInt<256, false, __uint128_t>; 872 using LL_UInt128_128 = BigInt<128, false, __uint128_t>; 873 874 LL_UInt256_128 a(1); 875 876 ASSERT_EQ(static_cast<int>(a), 1); 877 a = (a << 128) + 2; 878 ASSERT_EQ(static_cast<int>(a), 2); 879 ASSERT_EQ(static_cast<uint64_t>(a), uint64_t(2)); 880 a = (a << 32) + 3; 881 ASSERT_EQ(static_cast<int>(a), 3); 882 ASSERT_EQ(static_cast<uint64_t>(a), uint64_t(0x2'0000'0003)); 883 ASSERT_EQ(static_cast<int>(a >> 32), 2); 884 ASSERT_EQ(static_cast<int>(a >> (128 + 32)), 1); 885 886 LL_UInt128_128 b(__uint128_t(1) << 127); 887 LL_UInt128_128 c(b); 888 a = b.ful_mul(c); 889 890 ASSERT_EQ(static_cast<int>(a >> 254), 1); 891 892 LL_UInt256_128 d = LL_UInt256_128(123) << 4; 893 ASSERT_EQ(static_cast<int>(d), 123 << 4); 894 LL_UInt256_128 e = a / d; 895 LL_UInt256_128 f = a % d; 896 LL_UInt256_128 r = *a.div_uint_half_times_pow_2(123, 4); 897 EXPECT_TRUE(e == a); 898 EXPECT_TRUE(f == r); 899 } 900 901 #endif // LIBC_TYPES_HAS_INT128 902 903 TEST(LlvmLibcUIntClassTest, OtherWordTypeTests) { 904 using LL_UInt96 = BigInt<96, false, uint32_t>; 905 906 LL_UInt96 a(1); 907 908 ASSERT_EQ(static_cast<int>(a), 1); 909 a = (a << 32) + 2; 910 ASSERT_EQ(static_cast<int>(a), 2); 911 ASSERT_EQ(static_cast<uint64_t>(a), uint64_t(0x1'0000'0002)); 912 a = (a << 32) + 3; 913 ASSERT_EQ(static_cast<int>(a), 3); 914 ASSERT_EQ(static_cast<int>(a >> 32), 2); 915 ASSERT_EQ(static_cast<int>(a >> 64), 1); 916 } 917 918 } // namespace LIBC_NAMESPACE 919