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 @@ -105,6 +105,48 @@ return *this; } + // Subtract x to this number and store the result in this number. + // Returns the carry value produced by the subtraction operation. + // To prevent overflow from intermediate results, we use the following + // property of unsigned integers: + // x + (~x) = 2^(sizeof(x)) - 1, + // So: + // -x = ((~x) + 1) + (-2^(sizeof(x))), + // where 2^(sizeof(x)) is represented by the carry bit. + constexpr uint64_t sub(const UInt &x) { + bool carry = false; + for (size_t i = 0; i < WordCount; ++i) { + if (!carry) { + if (val[i] >= x.val[i]) + val[i] -= x.val[i]; + else { + val[i] += (~x.val[i]) + 1; + carry = true; + } + } else { + if (val[i] > x.val[i]) { + val[i] -= x.val[i] + 1; + carry = false; + } else + val[i] += ~x.val[i]; + } + } + return carry ? 1 : 0; + } + + constexpr UInt operator-(const UInt &other) const { + UInt result(*this); + result.sub(other); + // TODO(lntue): Set overflow flag / errno when carry is true. + return result; + } + + constexpr UInt operator-=(const UInt &other) { + // TODO(lntue): Set overflow flag / errno when carry is true. + sub(other); + return *this; + } + // Multiply this number with x and store the result in this number. It is // implemented using the long multiplication algorithm by splitting the // 64-bit words of this number and |x| in to 32-bit halves but peforming 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 @@ -44,6 +44,35 @@ EXPECT_EQ(val5 + val6, val6 + val5); } +TEST(LlvmLibcUInt128ClassTest, SubtractionTests) { + LL_UInt128 val1(12345); + LL_UInt128 val2(54321); + LL_UInt128 result1({0xffffffffffff5c08, 0xffffffffffffffff}); + LL_UInt128 result2(0xa3f8); + EXPECT_EQ(val1 - val2, result1); + EXPECT_EQ(val1, val2 + result1); + EXPECT_EQ(val2 - val1, result2); + EXPECT_EQ(val2, val1 + result2); + + LL_UInt128 val3({0xf000000000000001, 0}); + LL_UInt128 val4({0x100000000000000f, 0}); + LL_UInt128 result3(0xdffffffffffffff2); + LL_UInt128 result4({0x200000000000000e, 0xffffffffffffffff}); + EXPECT_EQ(val3 - val4, result3); + EXPECT_EQ(val3, val4 + result3); + EXPECT_EQ(val4 - val3, result4); + EXPECT_EQ(val4, val3 + result4); + + LL_UInt128 val5({0x0123456789abcdef, 0xfedcba9876543210}); + LL_UInt128 val6({0x1111222233334444, 0xaaaabbbbccccdddd}); + LL_UInt128 result5({0xf0122345567889ab, 0x5431fedca9875432}); + LL_UInt128 result6({0x0feddcbaa9877655, 0xabce01235678abcd}); + EXPECT_EQ(val5 - val6, result5); + EXPECT_EQ(val5, val6 + result5); + EXPECT_EQ(val6 - val5, result6); + EXPECT_EQ(val6, val5 + result6); +} + TEST(LlvmLibcUInt128ClassTest, MultiplicationTests) { LL_UInt128 val1({5, 0}); LL_UInt128 val2({10, 0});