[libc] add uint128 implementation

[michaelrj]

Summary

Some platforms don't support proper 128 bit integers, but some
algorithms use them, such as any that use long doubles. This patch
modifies the existing UInt class to support the necessary operators.
This does not put this new class into use, that will be in followup
patches.

[michaelrj]

remove some pieces of code left over from initial testing.

[lntue]

libc/src/__support/UInt128.h

41 ↗

(On Diff #427122)

other should either be UInt128 or const UInt128&. You can also add const after the declaration:
UInt128 operator+(UInt128 other) const {. Same for operator*.

80 ↗

(On Diff #427122)

Drop the const for amount and add const at the end:
UInt128 operator<<(int amount) const {. Same for other operators.

87 ↗

(On Diff #427122)

BITS_IN_UINT64 is unsigned, mixing with signed amount might trigger UB / warnings.

libc/test/src/__support/uint128_test.cpp

14

You should be able to add specialization for UInt128 in LibcTest.cpp and use ASSERT_EQ, EXPECT_EQ as usual. Also disable the __uint128_t variant over there when it's not defined.

[michaelrj]

make every UInt128 function constexpr and const.

libc/src/__support/UInt128.h

87 ↗

(On Diff #427122)

it theoretically could, although the bigger problem was the algorithm being wrong for numbers above 64. I've fixed both shifts.

libc/test/src/__support/uint128_test.cpp

14

I could make ASSERT_EQ support my custom UInt128, but that would add a dependency for effectively no gain, since UInt128 shouldn't be called by name in any other test file. Also, the __uint128_t code is already disabled for LibcTest.cpp

[sivachandra]

We already have a more generic UInt class here: https://github.com/llvm/llvm-project/blob/main/libc/src/__support/FPUtil/UInt.h

It does not have all the operations exactly as you want, but I could add straightforward extensions and the tests you have in this patch all pass. I strongly suggest adding such extensions to the existing class instead of re-implementing a new class.

[michaelrj]

I'm not sure that extending UInt.h is a good idea, since it adds a lot of complexity for not a lot of benefit. If we had actual uses for integers larger than 128 bits, then I would agree, but right now the UInt class is not used in any entrypoint. There is a use of 192 bit integers in src/__support/FPUtil/XFloat.h which is included in src/math/generic/dp_trig.cpp, but that's never actually used. To move these functions to UInt would involve rewriting all of these functions to support arbitrary sized integers when in reality there's only one size used. This would be easy for most things, but would be very difficult for multiplying two 128 bit integers. Finally, The designs of these classes are different, my UInt128 class is intended to be an immutable number, acting similar to a primitive. The UInt class acts more like a proper class, its functions take an argument and modify the object instead of creating a new object to be returned. These are both valid designs, but mine is closer to what's expected when using __uint128_t, which is I think what's most important.

[sivachandra]

In D124959#3497759, @michaelrj wrote:

I'm not sure that extending UInt.h is a good idea, since it adds a lot of complexity for not a lot of benefit.

If you are starting out, and need only 128 bit integers, I agree with this. The point I am making is, a much general class is already present.

If we had actual uses for integers larger than 128 bits, then I would agree, but right now the UInt class is not used in any entrypoint.

I agree its not used in an entrypoint. But, that doesn't mean its incorrect or totally unused. It is actually tested in one range reduction function.

To move these functions to UInt would involve rewriting all of these functions to support arbitrary sized integers when in reality there's only one size used.

My point is to not move any of the complex pieces. Those complex parts are already implemented in very a general fashion.

Finally, The designs of these classes are different, my UInt128 class is intended to be an immutable number, acting similar to a primitive.

That is why I said that all you need is to add a few straightforward methods. Before I actually made the comment, I tried it out to actually convince myself that I was talking sense. With just a few additional but straightforward methods, all your tests work as is. For example, for addition, all I had to add was this:

UInt<Bits> operator+(const UInt<Bits> &other) const {
  UInt<Bits> result(*this);
  result.add(other);
  return result;
}

Similarly, I added straightforward methods for multiplication, shift and bitwise operators also.

[michaelrj]

changed to use the existing uint class, much of this change was contributed by sivachandra

[lntue]

libc/src/__support/CMakeLists.txt

63 ↗

(On Diff #428444)

Is this still needed?

libc/src/__support/FPUtil/UInt.h

0

Add suffix -u/-U to the constant.

0

can this be all caps MASK32?

0

Move this out of the class.

0

Move this out of the class. You can keep them in a separate namespace of use different function name so that it won't clash with the usual strlen.

0

If you remove trivial implementations of the default and copy constructors, does it still work correctly?

2

init method is only used here, why don't we just leave its implementation here and remove the private init method?

2

This line is not needed. result was 0-initialized, and multiply by other[0] would should still be 0.

4

Remove this if it's not needed.

[sivachandra]

libc/src/__support/FPUtil/UInt.h

0

The hexval and strlen methods should be removed along with the commented out constructor. Even the InvalidHexDigit member.

0

Why have these been moved out of the class? They are supposed to be internal conveniences and should not be made available from a "public" namespace. If you moved them out for use in the operator* specialization, then if you make them them static, they can still live as private members.

libc/test/src/__support/uint128_test.cpp

14

By "disabled" do you mean the conditional on __SIZEOF_INT128__? If yes, you should add the else branches for it with this specialization. To keep everything more logically organized, you should probably move the UInt.h header file to src/__support/CPP.

[michaelrj]

move UInt to CPP
add UInt comparison to LibcTest
Move tests to use default comparison

[michaelrj]

libc/src/__support/FPUtil/UInt.h

0

No, it throws errors in the tests.

libc/test/src/__support/uint128_test.cpp

14

I've moved UInt.h into CPP, and I've added specializations to LibcTest, but they're not conditional since this class is always available.

libc/src/__support/CPP/CMakeLists.txt

 add_header_library(
   array
   HDRS
     Array.h
 )
 
 add_header_library(
   array_ref
   HDRS
     ArrayRef.h
 )
 
-
 add_header_library(
   bit
   HDRS
     Bit.h
 )
 
-
 add_header_library(
   bitset
   HDRS
     Bitset.h
 )
 
 add_header_library(
   functional
HDRS
     blockstore.h
 )
 
 add_header_library(
   error
   HDRS
     error.h
 )
+
+add_header_library(
+  uint
+  HDRS
+    UInt.h
+  DEPENDS
+    libc.src.__support.CPP.array
+)

libc/src/__support/CPP/TypeTraits.h

 //===-- Self contained C++ type traits --------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H
 #define LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H
 
+#include "UInt.h"
+
 namespace __llvm_libc {
 namespace cpp {
 
 template <bool B, typename T> struct EnableIf;
 template <typename T> struct EnableIf<true, T> { typedef T Type; };
 
 template <bool B, typename T>
 using EnableIfType = typename EnableIf<B, T>::Type;

 template <typename Type> struct IsIntegral {
   using TypeNoCV = RemoveCVType<Type>;
   static constexpr bool Value =
       IsSameV<char, TypeNoCV> || IsSameV<signed char, TypeNoCV> ||
       IsSameV<unsigned char, TypeNoCV> || IsSameV<short, TypeNoCV> ||
       IsSameV<unsigned short, TypeNoCV> || IsSameV<int, TypeNoCV> ||
       IsSameV<unsigned int, TypeNoCV> || IsSameV<long, TypeNoCV> ||
       IsSameV<unsigned long, TypeNoCV> || IsSameV<long long, TypeNoCV> ||
-      IsSameV<unsigned long long, TypeNoCV> || IsSameV<bool, TypeNoCV>
+      IsSameV<unsigned long long, TypeNoCV> || IsSameV<bool, TypeNoCV> ||
+      IsSameV<UInt<128>, TypeNoCV>
 #ifdef __SIZEOF_INT128__
       || IsSameV<__uint128_t, TypeNoCV> || IsSameV<__int128_t, TypeNoCV>
 #endif
       ;
 };
 
 template <typename T> struct IsPointerTypeNoCV : public FalseValue {};
 template <typename T> struct IsPointerTypeNoCV<T *> : public TrueValue {};

libc/src/__support/CPP/UInt.h

+//===-- A class to manipulate wide integers. --------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_UTILS_CPP_UINT_H
+#define LLVM_LIBC_UTILS_CPP_UINT_H
+
+#include "src/__support/CPP/Array.h"
+
+#include <stddef.h> // For size_t
+#include <stdint.h>
+
+namespace __llvm_libc {
+namespace cpp {
+
+template <size_t Bits> class UInt {
+
+  static_assert(Bits > 0 && Bits % 64 == 0,
+                "Number of bits in UInt should be a multiple of 64.");
+  static constexpr size_t WordCount = Bits / 64;
+  uint64_t val[WordCount];
+
+  static constexpr uint64_t MASK32 = 0xFFFFFFFFu;
+
+  static constexpr uint64_t low(uint64_t v) { return v & MASK32; }
+  static constexpr uint64_t high(uint64_t v) { return (v >> 32) & MASK32; }
+
+public:
+  constexpr UInt() {}
+
+  constexpr UInt(const UInt<Bits> &other) {
+    for (size_t i = 0; i < WordCount; ++i)
+      val[i] = other.val[i];
+  }
+
+  // Initialize the first word to |v| and the rest to 0.
+  constexpr UInt(uint64_t v) {
+    val[0] = v;
+    for (size_t i = 1; i < WordCount; ++i) {
+      val[i] = 0;
+    }
+  }
+  constexpr explicit UInt(const cpp::Array<uint64_t, WordCount> &words) {
+    for (size_t i = 0; i < WordCount; ++i)
+      val[i] = words[i];
+  }
+
+  constexpr explicit operator uint64_t() const { return val[0]; }
+
+  constexpr explicit operator uint32_t() const {
+    return uint32_t(uint64_t(*this));
+  }
+
+  constexpr explicit operator uint8_t() const {
+    return uint8_t(uint64_t(*this));
+  }
+
+  UInt<Bits> &operator=(const UInt<Bits> &other) {
+    for (size_t i = 0; i < WordCount; ++i)
+      val[i] = other.val[i];
+    return *this;
+  }
+
+  // Add x to this number and store the result in this number.
+  // Returns the carry value produced by the addition operation.
+  constexpr uint64_t add(const UInt<Bits> &x) {
+    uint64_t carry = 0;
+    for (size_t i = 0; i < WordCount; ++i) {
+      uint64_t res_lo = low(val[i]) + low(x.val[i]) + carry;
+      carry = high(res_lo);
+      res_lo = low(res_lo);
+
+      uint64_t res_hi = high(val[i]) + high(x.val[i]) + carry;
+      carry = high(res_hi);
+      res_hi = low(res_hi);
+
+      val[i] = res_lo + (res_hi << 32);
+    }
+    return carry;
+  }
+
+  constexpr UInt<Bits> operator+(const UInt<Bits> &other) const {
+    UInt<Bits> result(*this);
+    result.add(other);
+    return result;
+  }
+
+  // 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);
+    uint64_t x_hi = high(x);
+
+    cpp::Array<uint64_t, WordCount + 1> row1;
+    uint64_t carry = 0;
+    for (size_t i = 0; i < WordCount; ++i) {
+      uint64_t l = low(val[i]);
+      uint64_t h = high(val[i]);
+      uint64_t p1 = x_lo * l;
+      uint64_t p2 = x_lo * h;
+
+      uint64_t res_lo = low(p1) + carry;
+      carry = high(res_lo);
+      uint64_t res_hi = high(p1) + low(p2) + carry;
+      carry = high(res_hi) + high(p2);
+
+      res_lo = low(res_lo);
+      res_hi = low(res_hi);
+      row1[i] = res_lo + (res_hi << 32);
+    }
+    row1[WordCount] = carry;
+
+    cpp::Array<uint64_t, WordCount + 1> row2;
+    row2[0] = 0;
+    carry = 0;
+    for (size_t i = 0; i < WordCount; ++i) {
+      uint64_t l = low(val[i]);
+      uint64_t h = high(val[i]);
+      uint64_t p1 = x_hi * l;
+      uint64_t p2 = x_hi * h;
+
+      uint64_t res_lo = low(p1) + carry;
+      carry = high(res_lo);
+      uint64_t res_hi = high(p1) + low(p2) + carry;
+      carry = high(res_hi) + high(p2);
+
+      res_lo = low(res_lo);
+      res_hi = low(res_hi);
+      row2[i] = res_lo + (res_hi << 32);
+    }
+    row2[WordCount] = carry;
+
+    UInt<(WordCount + 1) * 64> r1(row1), r2(row2);
+    r2.shift_left(32);
+    r1.add(r2);
+    for (size_t i = 0; i < WordCount; ++i) {
+      val[i] = r1[i];
+    }
+    return r1[WordCount];
+  }
+
+  constexpr UInt<Bits> operator*(const UInt<Bits> &other) const {
+    UInt<Bits> result(0);
+    for (size_t i = 0; i < WordCount; ++i) {
+      UInt<Bits> row_result(*this);
+      row_result.mul(other[i]);
+      row_result.shift_left(64 * i);
+      result = result + row_result;
+    }
+    return result;
+  }
+
+  constexpr void shift_left(size_t s) {
+    const size_t drop = s / 64;  // Number of words to drop
+    const size_t shift = s % 64; // Bits to shift in the remaining words.
+    const uint64_t mask = ((uint64_t(1) << shift) - 1) << (64 - shift);
+
+    for (size_t i = WordCount; drop > 0 && i > 0; --i) {
+      if (i > drop)
+        val[i - 1] = val[i - drop - 1];
+      else
+        val[i - 1] = 0;
+    }
+    for (size_t i = WordCount; shift > 0 && i > drop; --i) {
+      uint64_t drop_val = (val[i - 1] & mask) >> (64 - shift);
+      val[i - 1] <<= shift;
+      if (i < WordCount)
+        val[i] |= drop_val;
+    }
+  }
+
+  constexpr UInt<Bits> operator<<(size_t s) const {
+    UInt<Bits> result(*this);
+    result.shift_left(s);
+    return result;
+  }
+
+  constexpr void shift_right(size_t s) {
+    const size_t drop = s / 64;  // Number of words to drop
+    const size_t shift = s % 64; // Bit shift in the remaining words.
+    const uint64_t mask = (uint64_t(1) << shift) - 1;
+
+    for (size_t i = 0; drop > 0 && i < WordCount; ++i) {
+      if (i + drop < WordCount)
+        val[i] = val[i + drop];
+      else
+        val[i] = 0;
+    }
+    for (size_t i = 0; shift > 0 && i < WordCount; ++i) {
+      uint64_t drop_val = ((val[i] & mask) << (64 - shift));
+      val[i] >>= shift;
+      if (i > 0)
+        val[i - 1] |= drop_val;
+    }
+  }
+
+  constexpr UInt<Bits> operator>>(size_t s) const {
+    UInt<Bits> result(*this);
+    result.shift_right(s);
+    return result;
+  }
+
+  constexpr UInt<Bits> operator&(const UInt<Bits> &other) const {
+    UInt<Bits> result;
+    for (size_t i = 0; i < WordCount; ++i)
+      result.val[i] = val[i] & other.val[i];
+    return result;
+  }
+
+  constexpr UInt<Bits> operator|(const UInt<Bits> &other) const {
+    UInt<Bits> result;
+    for (size_t i = 0; i < WordCount; ++i)
+      result.val[i] = val[i] | other.val[i];
+    return result;
+  }
+
+  constexpr UInt<Bits> operator^(const UInt<Bits> &other) const {
+    UInt<Bits> result;
+    for (size_t i = 0; i < WordCount; ++i)
+      result.val[i] = val[i] ^ other.val[i];
+    return result;
+  }
+
+  constexpr bool operator==(const UInt<Bits> &other) const {
+    for (size_t i = 0; i < WordCount; ++i) {
+      if (val[i] != other.val[i])
+        return false;
+    }
+    return true;
+  }
+
+  constexpr bool operator!=(const UInt<Bits> &other) const {
+    for (size_t i = 0; i < WordCount; ++i) {
+      if (val[i] != other.val[i])
+        return true;
+    }
+    return false;
+  }
+
+  constexpr bool operator>(const UInt<Bits> &other) const {
+    for (size_t i = WordCount; i > 0; --i) {
+      if (val[i - 1] <= other.val[i - 1])
+        return false;
+    }
+    return true;
+  }
+
+  constexpr bool operator>=(const UInt<Bits> &other) const {
+    for (size_t i = WordCount; i > 0; --i) {
+      if (val[i - 1] < other.val[i - 1])
+        return false;
+    }
+    return true;
+  }
+
+  constexpr bool operator<(const UInt<Bits> &other) const {
+    for (size_t i = WordCount; i > 0; --i) {
+      if (val[i - 1] >= other.val[i - 1])
+        return false;
+    }
+    return true;
+  }
+
+  constexpr bool operator<=(const UInt<Bits> &other) const {
+    for (size_t i = WordCount; i > 0; --i) {
+      if (val[i - 1] > other.val[i - 1])
+        return false;
+    }
+    return true;
+  }
+
+  // Return the i-th 64-bit word of the number.
+  const uint64_t &operator[](size_t i) const { return val[i]; }
+
+  // Return the i-th 64-bit word of the number.
+  uint64_t &operator[](size_t i) { return val[i]; }
+
+  uint64_t *data() { return val; }
+
+  const uint64_t *data() const { return val; }
+};
+
+template <>
+constexpr UInt<128> UInt<128>::operator*(const UInt<128> &other) const {
+  // temp low covers bits 0-63, middle covers 32-95, high covers 64-127, and
+  // high overflow covers 96-159.
+  uint64_t temp_low = low(val[0]) * low(other[0]);
+  uint64_t temp_middle_1 = low(val[0]) * high(other[0]);
+  uint64_t temp_middle_2 = high(val[0]) * low(other[0]);
+
+  // temp_middle is split out so that overflows can be handled, but since
+  // but since the result will be truncated to 128 bits any overflow from here
+  // on doesn't matter.
+  uint64_t temp_high = low(val[0]) * low(other[1]) +
+                       high(val[0]) * high(other[0]) +
+                       low(val[1]) * low(other[0]);
+
+  uint64_t temp_high_overflow =
+      low(val[0]) * high(other[1]) + high(val[0]) * low(other[1]) +
+      low(val[1]) * high(other[0]) + high(val[1]) * low(other[0]);
+
+  // temp_low_middle has just the high 32 bits of low, as well as any
+  // overflow.
+  uint64_t temp_low_middle =
+      high(temp_low) + low(temp_middle_1) + low(temp_middle_2);
+
+  uint64_t new_low = low(temp_low) + (low(temp_low_middle) << 32);
+  uint64_t new_high = high(temp_low_middle) + high(temp_middle_1) +
+                      high(temp_middle_2) + temp_high +
+                      (low(temp_high_overflow) << 32);
+  UInt<128> result(0);
+  result[0] = new_low;
+  result[1] = new_high;
+  return result;
+}
+
+} // namespace cpp
+} // namespace __llvm_libc
+
+/* TODO: determine the best way to support uint128 using this class.
+#if !defined(__SIZEOF_INT128__)
+using __uint128_t = __llvm_libc::internal::UInt<128>;
+#endif // uint128 is not defined, define it with this class.
+*/
+
+#endif // LLVM_LIBC_UTILS_CPP_UINT_H

libc/src/__support/FPUtil/CMakeLists.txt

 #TODO(michaelrj): separate the fputil library into individual targets.
 add_header_library(
   fputil
   HDRS
     FEnvImpl.h
     BasicOperations.h
     DivisionAndRemainderOperations.h
     FloatProperties.h
     FPBits.h
     BasicOperations.h
     ManipulationFunctions.h
     NearestIntegerOperations.h
     NormalFloat.h
     PlatformDefs.h
     UInt.h
-    XFloat.h
   DEPENDS
     libc.include.math
     libc.include.errno
     libc.include.fenv
     libc.src.__support.common
     libc.src.__support.CPP.type_traits
     libc.src.__support.CPP.bit
     libc.src.errno.errno
 )
 
 add_header_library(
+  xfloat
+  HDRS
+    XFloat.h
+  DEPENDS
+    .fputil #FPBits and NormalFloat
+    libc.src.__support.CPP.uint
+)
+
+add_header_library(
   sqrt
   HDRS
     sqrt.h
   DEPENDS
     .fputil
     libc.src.__support.FPUtil.generic.sqrt
 )
 

libc/src/__support/FPUtil/UInt.h

-//===-- A class to manipulate wide integers. --------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_LIBC_UTILS_FPUTIL_UINT_H
-#define LLVM_LIBC_UTILS_FPUTIL_UINT_H
-
-#include <stddef.h> // For size_t
-#include <stdint.h>
-
-namespace __llvm_libc {
-namespace fputil {
-
-template <size_t Bits> class UInt {
-
-  // This is mainly used for debugging.
-  enum Kind {
-    NotANumber,
-    Valid,
-  };
-
-  static_assert(Bits > 0 && Bits % 64 == 0,
-                "Number of bits in UInt should be a multiple of 64.");
-  static constexpr uint64_t Mask32 = 0xFFFFFFFF;
-  static constexpr size_t WordCount = Bits / 64;
-  static constexpr uint64_t InvalidHexDigit = 20;
-  uint64_t val[WordCount];
-  Kind kind;
-
-  uint64_t low(uint64_t v) { return v & Mask32; }
-
-  uint64_t high(uint64_t v) { return (v >> 32) & Mask32; }
-
-  uint64_t hexval(char c) {
-    uint64_t diff;
-    if ((diff = uint64_t(c) - 'A') < 6)
-      return diff + 10;
-    else if ((diff = uint64_t(c) - 'a') < 6)
-      return diff + 10;
-    else if ((diff = uint64_t(c) - '0') < 10)
-      return diff;
-    else
-      return InvalidHexDigit;
-  }
-
-  size_t strlen(const char *s) {
-    size_t len;
-    for (len = 0; *s != '\0'; ++s, ++len)
-      ;
-    return len;
-  }
-
-public:
-  UInt() { kind = Valid; }
-
-  UInt(const UInt<Bits> &other) : kind(other.kind) {
-    if (kind == Valid) {
-      for (size_t i = 0; i < WordCount; ++i)
-        val[i] = other.val[i];
-    }
-  }
-
-  // This constructor is used for debugging.
-  explicit UInt(const char *s) {
-    size_t len = strlen(s);
-    if (len > Bits / 4 + 2 || len < 3) {
-      kind = NotANumber;
-      return;
-    }
-
-    if (!(s[0] == '0' && s[1] == 'x')) {
-      kind = NotANumber;
-      return;
-    }
-
-    for (size_t i = 0; i < WordCount; ++i)
-      val[i] = 0;
-
-    for (size_t i = len - 1, w = 0; i >= 2; --i, w += 4) {
-      uint64_t hex = hexval(s[i]);
-      if (hex == InvalidHexDigit) {
-        kind = NotANumber;
-        return;
-      }
-      val[w / 64] |= (hex << (w % 64));
-    }
-
-    kind = Valid;
-  }
-
-  explicit UInt(uint64_t v) {
-    val[0] = v;
-    for (size_t i = 1; i < WordCount; ++i)
-      val[i] = 0;
-    kind = Valid;
-  }
-
-  explicit UInt(uint64_t data[WordCount]) {
-    for (size_t i = 0; i < WordCount; ++i)
-      val[i] = data[i];
-    kind = Valid;
-  }
-
-  bool is_valid() const { return kind == Valid; }
-
-  // Add x to this number and store the result in this number.
-  // Returns the carry value produced by the addition operation.
-  uint64_t add(const UInt<Bits> &x) {
-    uint64_t carry = 0;
-    for (size_t i = 0; i < WordCount; ++i) {
-      uint64_t res_lo = low(val[i]) + low(x.val[i]) + carry;
-      carry = high(res_lo);
-      res_lo = low(res_lo);
-
-      uint64_t res_hi = high(val[i]) + high(x.val[i]) + carry;
-      carry = high(res_hi);
-      res_hi = low(res_hi);
-
-      val[i] = res_lo + (res_hi << 32);
-    }
-    return carry;
-  }
-
-  // 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.
-  uint64_t mul(uint64_t x) {
-    uint64_t x_lo = low(x);
-    uint64_t x_hi = high(x);
-
-    uint64_t row1[WordCount + 1];
-    uint64_t carry = 0;
-    for (size_t i = 0; i < WordCount; ++i) {
-      uint64_t l = low(val[i]);
-      uint64_t h = high(val[i]);
-      uint64_t p1 = x_lo * l;
-      uint64_t p2 = x_lo * h;
-
-      uint64_t res_lo = low(p1) + carry;
-      carry = high(res_lo);
-      uint64_t res_hi = high(p1) + low(p2) + carry;
-      carry = high(res_hi) + high(p2);
-
-      res_lo = low(res_lo);
-      res_hi = low(res_hi);
-      row1[i] = res_lo + (res_hi << 32);
-    }
-    row1[WordCount] = carry;
-
-    uint64_t row2[WordCount + 1];
-    row2[0] = 0;
-    carry = 0;
-    for (size_t i = 0; i < WordCount; ++i) {
-      uint64_t l = low(val[i]);
-      uint64_t h = high(val[i]);
-      uint64_t p1 = x_hi * l;
-      uint64_t p2 = x_hi * h;
-
-      uint64_t res_lo = low(p1) + carry;
-      carry = high(res_lo);
-      uint64_t res_hi = high(p1) + low(p2) + carry;
-      carry = high(res_hi) + high(p2);
-
-      res_lo = low(res_lo);
-      res_hi = low(res_hi);
-      row2[i] = res_lo + (res_hi << 32);
-    }
-    row2[WordCount] = carry;
-
-    UInt<(WordCount + 1) * 64> r1(row1), r2(row2);
-    r2.shift_left(32);
-    r1.add(r2);
-    for (size_t i = 0; i < WordCount; ++i) {
-      val[i] = r1[i];
-    }
-    return r1[WordCount];
-  }
-
-  void shift_left(size_t s) {
-    const size_t drop = s / 64;  // Number of words to drop
-    const size_t shift = s % 64; // Bits to shift in the remaining words.
-    const uint64_t mask = ((uint64_t(1) << shift) - 1) << (64 - shift);
-
-    for (size_t i = WordCount; drop > 0 && i > 0; --i) {
-      if (i - drop > 0)
-        val[i - 1] = val[i - drop - 1];
-      else
-        val[i - 1] = 0;
-    }
-    for (size_t i = WordCount; shift > 0 && i > drop; --i) {
-      uint64_t drop_val = (val[i - 1] & mask) >> (64 - shift);
-      val[i - 1] <<= shift;
-      if (i < WordCount)
-        val[i] |= drop_val;
-    }
-  }
-
-  void shift_right(size_t s) {
-    const size_t drop = s / 64;  // Number of words to drop
-    const size_t shift = s % 64; // Bit shift in the remaining words.
-    const uint64_t mask = (uint64_t(1) << shift) - 1;
-
-    for (size_t i = 0; drop > 0 && i < WordCount; ++i) {
-      if (i + drop < WordCount)
-        val[i] = val[i + drop];
-      else
-        val[i] = 0;
-    }
-    for (size_t i = 0; shift > 0 && i < WordCount; ++i) {
-      uint64_t drop_val = ((val[i] & mask) << (64 - shift));
-      val[i] >>= shift;
-      if (i > 0)
-        val[i - 1] |= drop_val;
-    }
-  }
-
-  const uint64_t &operator[](size_t i) const { return val[i]; }
-
-  uint64_t &operator[](size_t i) { return val[i]; }
-
-  uint64_t *data() { return val; }
-
-  const uint64_t *data() const { return val; }
-};
-
-} // namespace fputil
-} // namespace __llvm_libc
-
-#endif // LLVM_LIBC_UTILS_FPUTIL_UINT_H

libc/src/__support/FPUtil/XFloat.h

 //===-- Utility class to manipulate wide floats. ----------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "FPBits.h"
 #include "NormalFloat.h"
-#include "UInt.h"
+#include "src/__support/CPP/UInt.h"
 
 #include <stdint.h>
 
 namespace __llvm_libc {
 namespace fputil {
 
 // Store and manipulate positive double precision numbers at |Precision| bits.
 template <size_t Precision> class XFloat {

libc/src/math/generic/CMakeLists.txt

 
 add_object_library(
   dp_trig
   SRCS
     dp_trig.cpp
   HDRS
     dp_trig.h
   DEPENDS
-    libc.src.__support.FPUtil.fputil
+    libc.src.__support.FPUtil.fputil #FPBits and ManipulationFunction
+    libc.src.__support.FPUtil.xfloat
+    libc.src.__support.CPP.uint
   COMPILE_OPTIONS
    -O3
 )

libc/test/src/__support/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_support_unittests
   SRCS
     arg_list_test.cpp
   DEPENDS
     libc.src.__support.arg_list
 )
 
+add_libc_unittest(
+  uint128_test
+  SUITE
+    libc_support_unittests
+  SRCS
+    uint128_test.cpp
+  DEPENDS
+    libc.src.__support.CPP.uint
+)
+
 add_executable(
   libc_str_to_float_comparison_test
   str_to_float_comparison_test.cpp
 )
 
 target_link_libraries(libc_str_to_float_comparison_test
   PRIVATE
     llvmlibc

libc/test/src/__support/uint128_test.cpp

+//===-- Unittests for the 128 bit integer class ---------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/CPP/UInt.h"
+
+#include "utils/UnitTest/Test.h"
+
+using UInt128 = __llvm_libc::cpp::UInt<128>;
+
+TEST(LlvmLibcUInt128ClassTest, BasicInit) {
+  UInt128 empty;
+  UInt128 half_val(12345);
+  UInt128 full_val({12345, 67890});
+  ASSERT_TRUE(half_val != full_val);
+}
+
+TEST(LlvmLibcUInt128ClassTest, AdditionTests) {
+  UInt128 val1(12345);
+  UInt128 val2(54321);
+  UInt128 result1(66666);
+  EXPECT_EQ(val1 + val2, result1);
+  EXPECT_EQ((val1 + val2), (val2 + val1)); // addition is reciprocal
+
+  // Test overflow
+  UInt128 val3({0xf000000000000001, 0});
+  UInt128 val4({0x100000000000000f, 0});
+  UInt128 result2({0x10, 0x1});
+  EXPECT_EQ(val3 + val4, result2);
+  EXPECT_EQ(val3 + val4, val4 + val3);
+}
+
+TEST(LlvmLibcUInt128ClassTest, MultiplicationTests) {
+  UInt128 val1({5, 0});
+  UInt128 val2({10, 0});
+  UInt128 result1({50, 0});
+  EXPECT_EQ((val1 * val2), result1);
+  EXPECT_EQ((val1 * val2), (val2 * val1)); // multiplication is reciprocal
+
+  // Check that the multiplication works accross the whole number
+  UInt128 val3({0xf, 0});
+  UInt128 val4({0x1111111111111111, 0x1111111111111111});
+  UInt128 result2({0xffffffffffffffff, 0xffffffffffffffff});
+  EXPECT_EQ((val3 * val4), result2);
+  EXPECT_EQ((val3 * val4), (val4 * val3));
+
+  // Check that multiplication doesn't reorder the bits.
+  UInt128 val5({2, 0});
+  UInt128 val6({0x1357024675316420, 0x0123456776543210});
+  UInt128 result3({0x26ae048cea62c840, 0x02468aceeca86420});
+
+  EXPECT_EQ((val5 * val6), result3);
+  EXPECT_EQ((val5 * val6), (val6 * val5));
+
+  // Make sure that multiplication handles overflow correctly.
+  UInt128 val7(2);
+  UInt128 val8({0x8000800080008000, 0x8000800080008000});
+  UInt128 result4({0x0001000100010000, 0x0001000100010001});
+  EXPECT_EQ((val7 * val8), result4);
+  EXPECT_EQ((val7 * val8), (val8 * val7));
+
+  // val9 is the 128 bit mantissa of 1e60 as a float, val10 is the mantissa for
+  // 1e-60. They almost cancel on the high bits, but the result we're looking
+  // for is just the low bits. The full result would be
+  // 0x7fffffffffffffffffffffffffffffff3a4f32d17f40d08f917cf11d1e039c50
+  UInt128 val9({0x01D762422C946590, 0x9F4F2726179A2245});
+  UInt128 val10({0x3792F412CB06794D, 0xCDB02555653131B6});
+  UInt128 result5({0x917cf11d1e039c50, 0x3a4f32d17f40d08f});
+  EXPECT_EQ((val9 * val10), result5);
+  EXPECT_EQ((val9 * val10), (val10 * val9));
+}
+
+TEST(LlvmLibcUInt128ClassTest, ShiftLeftTests) {
+  UInt128 val1(0x0123456789abcdef);
+  UInt128 result1(0x123456789abcdef0);
+  EXPECT_EQ((val1 << 4), result1);
+
+  UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0});
+  UInt128 result2({0x02468ace00000000, 0x9abcdef013579bdf});
+  EXPECT_EQ((val2 << 32), result2);
+
+  UInt128 result3({0, 0x13579bdf02468ace});
+  EXPECT_EQ((val2 << 64), result3);
+
+  UInt128 result4({0, 0x02468ace00000000});
+  EXPECT_EQ((val2 << 96), result4);
+
+  UInt128 result5({0, 0x2468ace000000000});
+  EXPECT_EQ((val2 << 100), result5);
+
+  UInt128 result6({0, 0});
+  EXPECT_EQ((val2 << 128), result6);
+  EXPECT_EQ((val2 << 256), result6);
+}
+
+TEST(LlvmLibcUInt128ClassTest, ShiftRightTests) {
+  UInt128 val1(0x0123456789abcdef);
+  UInt128 result1(0x00123456789abcde);
+  EXPECT_EQ((val1 >> 4), result1);
+
+  UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0});
+  UInt128 result2({0x9abcdef013579bdf, 0x0000000012345678});
+  EXPECT_EQ((val2 >> 32), result2);
+
+  UInt128 result3({0x123456789abcdef0, 0});
+  EXPECT_EQ((val2 >> 64), result3);
+
+  UInt128 result4({0x0000000012345678, 0});
+  EXPECT_EQ((val2 >> 96), result4);
+
+  UInt128 result5({0x0000000001234567, 0});
+  EXPECT_EQ((val2 >> 100), result5);
+
+  UInt128 result6({0, 0});
+  EXPECT_EQ((val2 >> 128), result6);
+  EXPECT_EQ((val2 >> 256), result6);
+}
+
+TEST(LlvmLibcUInt128ClassTest, AndTests) {
+  UInt128 base({0xffff00000000ffff, 0xffffffff00000000});
+  UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff});
+  uint64_t val64 = 0xf0f0f0f00f0f0f0f;
+  int val32 = 0x0f0f0f0f;
+  UInt128 result128({0xf0f0000000000f0f, 0xff00ff0000000000});
+  UInt128 result64(0xf0f0000000000f0f);
+  UInt128 result32(0x00000f0f);
+  EXPECT_EQ((base & val128), result128);
+  EXPECT_EQ((base & val64), result64);
+  EXPECT_EQ((base & val32), result32);
+}
+
+TEST(LlvmLibcUInt128ClassTest, OrTests) {
+  UInt128 base({0xffff00000000ffff, 0xffffffff00000000});
+  UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff});
+  uint64_t val64 = 0xf0f0f0f00f0f0f0f;
+  int val32 = 0x0f0f0f0f;
+  UInt128 result128({0xfffff0f00f0fffff, 0xffffffff00ff00ff});
+  UInt128 result64({0xfffff0f00f0fffff, 0xffffffff00000000});
+  UInt128 result32({0xffff00000f0fffff, 0xffffffff00000000});
+  EXPECT_EQ((base | val128), result128);
+  EXPECT_EQ((base | val64), result64);
+  EXPECT_EQ((base | val32), result32);
+}
+
+TEST(LlvmLibcUInt128ClassTest, EqualsTests) {
+  UInt128 a1({0xffffffff00000000, 0xffff00000000ffff});
+  UInt128 a2({0xffffffff00000000, 0xffff00000000ffff});
+  UInt128 b({0xff00ff0000ff00ff, 0xf0f0f0f00f0f0f0f});
+  UInt128 a_reversed({0xffff00000000ffff, 0xffffffff00000000});
+  UInt128 a_upper(0xffff00000000ffff);
+  UInt128 a_lower(0xffffffff00000000);
+  ASSERT_TRUE(a1 == a1);
+  ASSERT_TRUE(a1 == a2);
+  ASSERT_FALSE(a1 == b);
+  ASSERT_FALSE(a1 == a_reversed);
+  ASSERT_FALSE(a1 == a_lower);
+  ASSERT_FALSE(a1 == a_upper);
+  ASSERT_TRUE(a_lower != a_upper);
+}

libc/utils/UnitTest/LibcTest.cpp

 //===-- Implementation of the base class for libc unittests----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "LibcTest.h"
 
+#include "src/__support/CPP/UInt.h"
 #include "utils/testutils/ExecuteFunction.h"
 #include <cassert>
 #include <iostream>
 #include <string>
 
 namespace __llvm_libc {
 namespace testing {
 

 // When the value is of integral type, just display it as normal.
 template <typename ValType>
 cpp::EnableIfType<cpp::IsIntegral<ValType>::Value, std::string>
 describeValue(ValType Value) {
   return std::to_string(Value);
 }
 
 std::string describeValue(std::string Value) { return std::string(Value); }
-
 #ifdef __SIZEOF_INT128__
 // When the value is __uint128_t, also show its hexadecimal digits.
 // Using template to force exact match, prevent ambiguous promotion.
 std::string describeValue128(__uint128_t Value) {
   std::string S(sizeof(__uint128_t) * 2, '0');
 
   for (auto I = S.rbegin(), End = S.rend(); I != End; ++I, Value >>= 4) {
     unsigned char Mod = static_cast<unsigned char>(Value) & 15;
     *I = Mod < 10 ? '0' + Mod : 'a' + Mod - 10;
   }
 
   return "0x" + S;
 }
 
 template <> std::string describeValue<__int128_t>(__int128_t Value) {
   return describeValue128(Value);
 }
 template <> std::string describeValue<__uint128_t>(__uint128_t Value) {
   return describeValue128(Value);
 }
 #endif
 
+// When the value is UInt<128>, also show its hexadecimal digits.
+template <>
+std::string
+describeValue<__llvm_libc::cpp::UInt<128>>(__llvm_libc::cpp::UInt<128> Value) {
+  std::string S(sizeof(__llvm_libc::cpp::UInt<128>) * 2, '0');
+
+  for (auto I = S.rbegin(), End = S.rend(); I != End; ++I, Value = Value >> 4) {
+    unsigned char Mod = static_cast<unsigned char>(Value) & 15;
+    *I = Mod < 10 ? '0' + Mod : 'a' + Mod - 10;
+  }
+
+  return "0x" + S;
+}
+
 template <typename ValType>
 void explainDifference(ValType LHS, ValType RHS, const char *LHSStr,
                        const char *RHSStr, const char *File, unsigned long Line,
                        std::string OpString) {
   size_t OffsetLength = OpString.size() > 2 ? OpString.size() - 2 : 0;
   std::string Offset(OffsetLength, ' ');
 
   std::cout << File << ":" << Line << ": FAILURE\n"
template bool test<long long>(RunContext *Ctx, TestCondition Cond,
                               unsigned long Line);
 
 #ifdef __SIZEOF_INT128__
 template bool test<__int128_t>(RunContext *Ctx, TestCondition Cond,
                                __int128_t LHS, __int128_t RHS,
                                const char *LHSStr, const char *RHSStr,
                                const char *File, unsigned long Line);
 #endif
+template bool test<__llvm_libc::cpp::UInt<128>>(
+    RunContext *Ctx, TestCondition Cond, __llvm_libc::cpp::UInt<128> LHS,
+    __llvm_libc::cpp::UInt<128> RHS, const char *LHSStr, const char *RHSStr,
+    const char *File, unsigned long Line);
 
 template bool test<unsigned char>(RunContext *Ctx, TestCondition Cond,
                                   unsigned char LHS, unsigned char RHS,
                                   const char *LHSStr, const char *RHSStr,
                                   const char *File, unsigned long Line);
 
 template bool test<unsigned short>(RunContext *Ctx, TestCondition Cond,
                                    unsigned short LHS, unsigned short RHS,