diff --git a/libc/src/__support/CPP/UInt.h b/libc/src/__support/CPP/UInt.h --- a/libc/src/__support/CPP/UInt.h +++ b/libc/src/__support/CPP/UInt.h @@ -37,6 +37,18 @@ val[i] = other.val[i]; } + // Construct a UInt from a C array. + template constexpr UInt(const uint64_t (&nums)[N]) { + size_t min_wordcount = N > WordCount ? N : WordCount; + size_t i = 0; + for (; i < min_wordcount; ++i) + val[i] = nums[i]; + + // If nums doesn't completely fill val, then fill the rest with zeroes. + for (; i < WordCount; ++i) + val[i] = 0; + } + // Initialize the first word to |v| and the rest to 0. constexpr UInt(uint64_t v) { val[0] = v; @@ -65,6 +77,17 @@ return *this; } + template + UInt &operator=(const UInt &other) { + static_assert(SmallerBits < Bits); + size_t i = 0; + for (; i < UInt::WordCount; ++i) + val[i] = other.val[i]; + for (; i < WordCount; ++i) + val[i] = 0; + return *this; + } + // Add x to this number and store the result in this number. // Returns the carry value produced by the addition operation. // To prevent overflow from intermediate results, we use the following @@ -205,6 +228,31 @@ return r1[WordCount]; } + // This multiplication is between two arbitrary length numbers, and as such + // cannot easily evaluate its overflow, so it returns true if it has any + // overflow, and relies on the client to use this information. + constexpr bool mul(const UInt &other) { + UInt result(0); + bool overflow = false; + for (size_t i = 0; i < WordCount; ++i) { + UInt row_result(*this); + overflow = overflow || (row_result.mul(other[i]) > 0); + for (size_t j = WordCount - i; !overflow && j < WordCount; ++j) { + if (row_result[j] > 0) { + overflow = true; + } + } + row_result.shift_left(64 * i); + UInt sum = result + row_result; + if (sum < result) { + overflow = true; + } + result = sum; + } + *this = result; + return overflow; + } + constexpr UInt operator*(const UInt &other) const { UInt result(0); for (size_t i = 0; i < WordCount; ++i) { @@ -216,6 +264,47 @@ return result; } + // div takes another UInt of the same size and divides this by it. The value + // of this will be set to the quotient, and the return value is the remainder. + constexpr UInt div(const UInt &other) { + UInt remainder(0); + if (*this < other) { + remainder = *this; + *this = UInt(0); + return remainder; + } + if (other == UInt(1)) { + return remainder; + } + if (other == UInt(0)) { // TODO: Make this error correctly. + return remainder; + } + + int curBit = 0; + UInt quotient(0); + UInt subtractor = other; + for (; static_cast(curBit) < Bits && subtractor < *this && + subtractor << 1 > subtractor; + ++curBit, subtractor.shift_left(1)) { + ; + } + for (; curBit >= 0 && *this > 0; --curBit, subtractor.shift_right(1)) { + if (*this >= subtractor) { + this->sub(subtractor); + quotient = quotient | (UInt(1) << curBit); + } + } + remainder = *this; + *this = quotient; + return remainder; + } + + constexpr UInt operator/(const UInt &other) const { + UInt result(*this); + result.div(other); + return result; + } + constexpr UInt &operator*=(const UInt &other) { *this = *this * other; return *this; diff --git a/libc/test/src/__support/uint128_test.cpp b/libc/test/src/__support/uint128_test.cpp --- a/libc/test/src/__support/uint128_test.cpp +++ b/libc/test/src/__support/uint128_test.cpp @@ -113,6 +113,42 @@ EXPECT_EQ((val9 * val10), (val10 * val9)); } +TEST(LlvmLibcUInt128ClassTest, DivisionTests) { + LL_UInt128 val1({10, 0}); + LL_UInt128 val2({5, 0}); + LL_UInt128 result1({2, 0}); + EXPECT_EQ((val1 / val2), result1); + EXPECT_EQ((val1 / result1), val2); + + // Check that the division works accross the whole number + LL_UInt128 val3({0xffffffffffffffff, 0xffffffffffffffff}); + LL_UInt128 val4({0xf, 0}); + LL_UInt128 result2({0x1111111111111111, 0x1111111111111111}); + EXPECT_EQ((val3 / val4), result2); + EXPECT_EQ((val3 / result2), val4); + + // Check that division doesn't reorder the bits. + LL_UInt128 val5({0x26ae048cea62c840, 0x02468aceeca86420}); + LL_UInt128 val6({2, 0}); + LL_UInt128 result3({0x1357024675316420, 0x0123456776543210}); + EXPECT_EQ((val5 / val6), result3); + EXPECT_EQ((val5 / result3), val6); + + // Make sure that division handles inexact results correctly. + LL_UInt128 val7({1001, 0}); + LL_UInt128 val8({10, 0}); + LL_UInt128 result4({100, 0}); + EXPECT_EQ((val7 / val8), result4); + EXPECT_EQ((val7 / result4), val8); + + // Make sure that division handles divisors of one correctly. + LL_UInt128 val9({0x1234567812345678, 0x9abcdef09abcdef0}); + LL_UInt128 val10({1, 0}); + LL_UInt128 result5({0x1234567812345678, 0x9abcdef09abcdef0}); + EXPECT_EQ((val9 / val10), result5); + EXPECT_EQ((val9 / result5), val10); +} + TEST(LlvmLibcUInt128ClassTest, ShiftLeftTests) { LL_UInt128 val1(0x0123456789abcdef); LL_UInt128 result1(0x123456789abcdef0);