[libc] Add subtraction for UInt<N> class.

[lntue]

Summary

Add subtraction operators (-, -=) for UInt<N> class.

[michaelrj]

LGTM

libc/src/__support/CPP/UInt.h

public:
   }
 
   constexpr UInt<Bits> operator+=(const UInt<Bits> &other) {
     // TODO(lntue): Set overflow flag / errno when carry is true.
     add(other);
     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<Bits> &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<Bits> operator-(const UInt<Bits> &other) const {
+    UInt<Bits> result(*this);
+    result.sub(other);
+    // TODO(lntue): Set overflow flag / errno when carry is true.
+    return result;
+  }
+
+  constexpr UInt<Bits> operator-=(const UInt<Bits> &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
   // the operations using 64-bit numbers. This ensures that we don't lose the
   // carry bits.
   // Returns the carry value produced by the multiplication operation.
   constexpr uint64_t mul(uint64_t x) {
     uint64_t x_lo = low(x);

libc/test/src/__support/uint128_test.cpp

TEST(LlvmLibcUInt128ClassTest, AdditionTests) {
   // Test overflow
   LL_UInt128 val5({0x0123456789abcdef, 0xfedcba9876543210});
   LL_UInt128 val6({0x1111222233334444, 0xaaaabbbbccccdddd});
   LL_UInt128 result3({0x12346789bcdf1233, 0xa987765443210fed});
   EXPECT_EQ(val5 + val6, result3);
   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});
   LL_UInt128 result1({50, 0});
   EXPECT_EQ((val1 * val2), result1);
   EXPECT_EQ((val1 * val2), (val2 * val1)); // multiplication is commutative
 
   // Check that the multiplication works accross the whole number