[libc][math] Improve the performance and error printing of UInt.

[lntue]

Summary

Use add_with_carry builtin to improve the performance of
addition and multiplication of UInt class. For 128-bit, it is as
fast as using __uint128_t.

Microbenchmark for addition:
https://quick-bench.com/q/-5a6xM4T8rIXBhqMTtLE-DD2h8w

Microbenchmark for multiplication:
https://quick-bench.com/q/P2muLAzJ_W-VqWCuxEJ0CU0bLDg

Microbenchmark for shift right:
https://quick-bench.com/q/N-jkKXaVsGQ4AAv3k8VpsVkua5Y

Microbenchmark for shift left:
https://quick-bench.com/q/5-RzwF8UdslC-zuhNajXtXdzLRM

[lntue]

Imnprove shift left and shift right performance.

[lntue]

Use __uint128_t builtin for shift left if available.

[michaelrj]

libc/src/__support/UInt.h

25

is there a reason this is changed?

314

for clarity could this be j > 0?

[lntue]

libc/src/__support/UInt.h

25

I put everything in this class as public for 3 reasons:

• To access to WordCount without recomputing it
• To make this class behave as a value class, I'm going to remove the operator[], and simply use .val[i] directly if we want to access to its ith uint64_t block.
• Utility functions low and high (and MASK32 constant) will be removed and switched completely to use split(uint64_t) instead. That would separate what we want to do with the class vs what we want to do with uint64_t.

[lntue]

Address comment.

[sivachandra]

libc/src/__support/UInt.h

25

I put everything in this class as public for 3 reasons:

• To access to WordCount without recomputing it

You can make that public alone?

• To make this class behave as a value class, I'm going to remove the operator[], and simply use .val[i] directly if we want to access to its ith uint64_t block.

Whats wrong with operator[] for such word access?

• Utility functions low and high (and MASK32 constant) will be removed and switched completely to use split(uint64_t) instead. That would separate what we want to do with the class vs what we want to do with uint64_t.

I did not get how this is related to class vs struct.

libc/src/__support/number_pair.h

38

The full_mul functions should not belong here or name this file something else. May be integer_utils.h.

libc/utils/UnitTest/LibcTest.cpp

281

Ideally, these specializations should be in a different file, say integer_test_utils.cpp, right next to where UInt is defined. May be it leads to a CMake cyclic directory problem?

[lntue]

libc/src/__support/UInt.h

25

It's just that accessing a specific uint64_t block is clearer with .val[i] vs [i], especially when we have an array of UInt. And with low and high functions being factored out to number_pair.h, there is no need for private members, and we can simply keep everything public.

libc/utils/UnitTest/LibcTest.cpp

281

Since we UInt<128> is required here as replacement for __uint128_t if not available, instantiate other UInt here is the most suitable, without complicating the dependency, I think.

[lntue]

Move full_mul to integer_utils.h and update bazel layout.

[lntue]

Fix bazel build.

[sivachandra]

libc/src/__support/UInt.h

25

I don't find the reasoning compelling enough to not hide the implementation detail. But, there is not a lot of implementation detail so I am on the fence.

296

What is a ?

540

I think we can make this a template like this:

template <size_t S>
struct is_integral<UInt<S>> : public cpp::true_type { static_assert(valid S); };

544

We can use a template instead of a specialization here also.

libc/src/__support/number_pair.h

24

Few questions:

1. Is this the only reason why the rest of the content from this file is not in integer_utils.h?
2. Is lo, hi split for a DoubleDouble the correct nomenclature?

I am still not convinced of the different styles used here. For example, why is number_pair not NumberPair or DoubleDouble not double_double? We should follow a uniform style. The exceptions are only applicable for the cpp directory. So, I suggest this:

1. Add a simple cpp::pair<T1, T2> class.
2. Instead of number_pair, define IntegerSplit:

template <typename T>
class IntegerSplit : protected cpp::pair<T, T> {
public:
  IntegerSplit() = default;
  IntegerSplit(T l, T h) : first(l), second(h) {}
  T &lo() { return cpp::pair<T, T>::first; }
  T &hi() { return cpp::pair<T, T>::second; }
  const T &lo() const { return cpp::pair<T, T>::first; }
  const T &hi() const { return cpp::pair<T, T>::second; }
};

3. Not in this patch, but when required:

class DoubleDouble : protected cpp::pair<double, double> {
public:
  DoubleDouble() = default;
  Double(double m, double d) : cpp::pair<T, T>(m, d) {}
  double &main() { return cpp::pair<T, T>::first; }
  double &delta() { return cpp::pair<T, T>::second; }
  const double &main() const { return cpp::pair<T, T>::first; }
  const double &delta() const { return cpp::pair<T, T>::second; }
};

libc/utils/UnitTest/LibcTest.cpp

281

We can keep specializations of only standard types here. Everything else, including those for __uint128_t, should go to another file.

[lntue]

libc/src/__support/UInt.h

296

Thanks for finding the bug! It turns out that I missed extra __ at the end of the macro in #ifdef, hence dead-code here.

libc/src/__support/number_pair.h

24

Yes, I think the normal splitting in the literature with double-double data type will call high/low parts, with abbreviations hi/lo. I do update the style name to NumberPair, but IntegerSplit does not seem fit, since it could be more generic and applied to double to get DoubleDouble type.

On the other hand, I don't see any benefit of a more complicated class structure over a simple POD struct for this yet. If there is a need for them, I'd be happy to update its definition.

libc/utils/UnitTest/LibcTest.cpp

281

Does it also mean that by default we will need to link to the other file, in addition to LibcTest ?

[lntue]

Fix SIZEOF_INT128 macro detection and fix naming style.

[sivachandra]

libc/src/__support/number_pair.h

24

Ah! If the normal convention is to use hi and lo for the main and delta components of a double-double, then having a single definition is OK.

libc/utils/UnitTest/LibcTest.cpp

281

Yes, like other custom matchers we have.

[lntue]

libc/utils/UnitTest/LibcTest.cpp

281

The template test that is instantiated here is actually only defined internally inside LibcTest.cpp. Untangle and refactoring it out to a common header so that we can have a separate instantiation target for UInt<192> and UInt<256> feel like out-of-scope for this patch. It should be a separate task / patch to refactor this file instead.

[sivachandra]

libc/utils/UnitTest/LibcTest.cpp

281

Yes - what I am describing is the end situation. You don't have to do it in this patch. The main point is that we can't keep adding specializations here. I agree it will take much more surgery than just moving it out. It is probably also exposing a deficiency in the current design.

libc/src/__support/CMakeLists.txt

add_header_library(
   fixedvector
   HDRS
     fixedvector.h
   DEPENDS
     libc.src.__support.CPP.array
 )
 
 add_header_library(
+  number_pair
+  HDRS
+    number_pair.h
+  DEPENDS
+    libc.src.__support.CPP.type_traits
+)
+
+add_header_library(
+  integer_utils
+  HDRS
+    integer_utils.h
+  DEPENDS
+    .builtin_wrappers
+    .number_pair
+    libc.src.__support.CPP.type_traits
+)
+
+add_header_library(
   uint
   HDRS
     UInt.h
   DEPENDS
+    .builtin_wrappers
+    .number_pair
+    .integer_utils
     libc.src.__support.CPP.array
+    libc.src.__support.CPP.type_traits
 )
 
 add_header_library(
   uint128
   HDRS
     UInt128.h
   DEPENDS
     .uint

libc/src/__support/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_UINT_H
-#define LLVM_LIBC_UTILS_UINT_H
+#ifndef LLVM_LIBC_SRC_SUPPORT_UINT_H
+#define LLVM_LIBC_SRC_SUPPORT_UINT_H
 
 #include "src/__support/CPP/array.h"
 #include "src/__support/CPP/limits.h"
 #include "src/__support/CPP/optional.h"
 #include "src/__support/CPP/type_traits.h"
 #include "src/__support/builtin_wrappers.h"
+#include "src/__support/integer_utils.h"
+#include "src/__support/number_pair.h"
 
 #include <stddef.h> // For size_t
 #include <stdint.h>
 
 namespace __llvm_libc::cpp {
 
-template <size_t Bits> class UInt {
+template <size_t Bits> struct 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];
   }
 
   template <size_t OtherBits> constexpr UInt(const UInt<OtherBits> &other) {
template <size_t Bits> struct UInt {
   }
 
   // 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
   // property of unsigned integers:
   //   x + (~x) = 2^(sizeof(x)) - 1.
   constexpr uint64_t add(const UInt<Bits> &x) {
-    bool carry = false;
+    uint64_t carry_in = 0;
+    uint64_t carry_out = 0;
     for (size_t i = 0; i < WordCount; ++i) {
-      uint64_t complement = ~x.val[i];
-      if (!carry) {
-        if (val[i] <= complement)
-          val[i] += x.val[i];
-        else {
-          val[i] -= complement + 1;
-          carry = true;
-        }
-      } else {
-        if (val[i] < complement) {
-          val[i] += x.val[i] + 1;
-          carry = false;
-        } else
-          val[i] -= complement;
-      }
-    }
-    return carry ? 1 : 0;
+      val[i] = add_with_carry(val[i], x.val[i], carry_in, carry_out);
+      carry_in = carry_out;
+    return carry_out;
   }
 
   constexpr UInt<Bits> operator+(const UInt<Bits> &other) const {
-    UInt<Bits> result(*this);
-    result.add(other);
-    // TODO(lntue): Set overflow flag / errno when carry is true.
+    UInt<Bits> result;
+    uint64_t carry_in = 0;
+    uint64_t carry_out = 0;
+    for (size_t i = 0; i < WordCount; ++i) {
+      result.val[i] = add_with_carry(val[i], other.val[i], carry_in, carry_out);
+      carry_in = carry_out;
+    }
     return result;
   }
 
   constexpr UInt<Bits> operator+=(const UInt<Bits> &other) {
-    // TODO(lntue): Set overflow flag / errno when carry is true.
-    add(other);
+    add(other); // Returned carry value is ignored.
     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,
template <size_t Bits> struct UInt {
 
   // 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;
+    UInt<128> partial_sum(0);
     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;
+      NumberPair<uint64_t> prod = full_mul(val[i], x);
+      UInt<128> tmp({prod.lo, prod.hi});
+      carry += partial_sum.add(tmp);
+      val[i] = partial_sum.val[0];
+      partial_sum.val[0] = partial_sum.val[1];
+      partial_sum.val[1] = carry;
       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];
+    return partial_sum.val[1];
   }
 
   constexpr UInt<Bits> operator*(const UInt<Bits> &other) const {
+    if constexpr (WordCount == 1) {
+      return {val[0] * other.val[0]};
+    } else {
       UInt<Bits> result(0);
+      UInt<128> partial_sum(0);
+      uint64_t carry = 0;
       for (size_t i = 0; i < WordCount; ++i) {
-      if (other[i] == 0)
-        continue;
-      UInt<Bits> row_result(*this);
-      row_result.mul(other[i]);
-      row_result.shift_left(64 * i);
-      result = result + row_result;
+        for (size_t j = 0; j <= i; j++) {
+          NumberPair<uint64_t> prod = full_mul(val[j], other.val[i - j]);
+          UInt<128> tmp({prod.lo, prod.hi});
+          carry += partial_sum.add(tmp);
+        }
+        result.val[i] = partial_sum.val[0];
+        partial_sum.val[0] = partial_sum.val[1];
+        partial_sum.val[1] = carry;
+        carry = 0;
       }
       return result;
     }
+  }
 
   // pow takes a power and sets this to its starting value to that power. Zero
   // to the zeroth power returns 1.
   constexpr void pow_n(uint64_t power) {
     UInt<Bits> result = 1;
     UInt<Bits> cur_power = *this;
 
     while (power > 0) {
for (size_t i = WordCount; i > 0; --i) {
         leading_zeroes += unsafe_clz(val[i - 1]);
         break;
       }
     }
     return leading_zeroes;
   }
 
   constexpr void shift_left(size_t s) {
+#ifdef __SIZEOF_INT128__
+    if constexpr (Bits == 128) {
+      // Use builtin 128 bits if available;
+      if (s >= 128) {
+        val[0] = 0;
+        val[1] = 0;
+        return;
+      }
+      __uint128_t tmp = __uint128_t(val[0]) + (__uint128_t(val[1]) << 64);
+      tmp <<= s;
+      val[0] = uint64_t(tmp);
+      val[1] = uint64_t(tmp >> 64);
+      return;
+    }
+#endif                           // __SIZEOF_INT128__
     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);
+    size_t i = WordCount;
 
-    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;
+    if (drop < WordCount) {
+      i = WordCount - 1;
+      size_t j = WordCount - 1 - drop;
+      for (; j > 0; --i, --j) {
+        val[i] = (val[j] << shift) | (val[j - 1] >> (64 - shift));
       }
-    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;
+      val[i] = val[0] << shift;
+    }
+
+    for (size_t j = 0; j < i; ++j) {
+      val[j] = 0;
     }
   }
 
   constexpr UInt<Bits> operator<<(size_t s) const {
     UInt<Bits> result(*this);
     result.shift_left(s);
     return result;
   }
 
   constexpr UInt<Bits> &operator<<=(size_t s) {
     shift_left(s);
     return *this;
   }
 
   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;
+    size_t i = 0;
+
+    if (drop < WordCount) {
+      size_t j = drop;
+      for (; j < WordCount - 1; ++i, ++j) {
+        val[i] = (val[j] >> shift) | (val[j + 1] << (64 - shift));
       }
-    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;
+      val[i] = val[j] >> shift;
+      ++i;
+    }
+
+    for (; i < WordCount; ++i) {
+      val[i] = 0;
     }
   }
 
   constexpr UInt<Bits> operator>>(size_t s) const {
     UInt<Bits> result(*this);
     result.shift_right(s);
     return result;
   }

 
 // Provides limits of UInt<128>.
 template <> class numeric_limits<UInt<128>> {
 public:
   static constexpr UInt<128> max() { return ~UInt<128>(0); }
   static constexpr UInt<128> min() { return 0; }
 };
 
-// Provides is_integral of UInt<128>.
-template <> struct is_integral<UInt<128>> : public cpp::true_type {};
+// Provides is_integral of UInt<128>, UInt<192>, UInt<256>.
+template <size_t Bits> struct is_integral<UInt<Bits>> : public cpp::true_type {
+  static_assert(Bits > 0 && Bits % 64 == 0,
+                "Number of bits in UInt should be a multiple of 64.");
+};
+
+// Provides is_unsigned of UInt<128>, UInt<192>, UInt<256>.
+template <size_t Bits> struct is_unsigned<UInt<Bits>> : public cpp::true_type {
+  static_assert(Bits > 0 && Bits % 64 == 0,
+                "Number of bits in UInt should be a multiple of 64.");
+};
 
 } // namespace __llvm_libc::cpp
 
-#endif // LLVM_LIBC_UTILS_UINT_H
+#endif // LLVM_LIBC_SRC_SUPPORT_UINT_H

libc/src/__support/integer_utils.h

+//===-- Utilities for 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_SRC_SUPPORT_INTEGER_UTILS_H
+#define LLVM_LIBC_SRC_SUPPORT_INTEGER_UTILS_H
+
+#include "CPP/type_traits.h"
+#include "builtin_wrappers.h"
+#include "number_pair.h"
+
+#include <stdint.h>
+
+namespace __llvm_libc {
+
+template <typename T> NumberPair<T> full_mul(T a, T b);
+
+template <>
+inline NumberPair<uint32_t> full_mul<uint32_t>(uint32_t a, uint32_t b) {
+  uint64_t prod = uint64_t(a) * uint64_t(b);
+  NumberPair<uint32_t> result;
+  result.lo = uint32_t(prod);
+  result.hi = uint32_t(prod >> 32);
+  return result;
+}
+
+template <>
+inline NumberPair<uint64_t> full_mul<uint64_t>(uint64_t a, uint64_t b) {
+#ifdef __SIZEOF_INT128__
+  __uint128_t prod = __uint128_t(a) * __uint128_t(b);
+  NumberPair<uint64_t> result;
+  result.lo = uint64_t(prod);
+  result.hi = uint64_t(prod >> 64);
+  return result;
+#else
+  NumberPair<uint64_t> pa = split(a);
+  NumberPair<uint64_t> pb = split(b);
+  NumberPair<uint64_t> prod;
+
+  prod.lo = pa.lo * pb.lo;                           // exact
+  prod.hi = pa.hi * pb.hi;                           // exact
+  NumberPair<uint64_t> lo_hi = split(pa.lo * pb.hi); // exact
+  NumberPair<uint64_t> hi_lo = split(pa.hi * pb.lo); // exact
+
+  uint64_t carry_in = 0;
+  uint64_t carry_out = 0;
+  uint64_t carry_unused = 0;
+  prod.lo = add_with_carry(prod.lo, lo_hi.lo << 32, carry_in, carry_out);
+  prod.hi = add_with_carry(prod.hi, lo_hi.hi, carry_out, carry_unused);
+  prod.lo = add_with_carry(prod.lo, hi_lo.lo << 32, carry_in, carry_out);
+  prod.hi = add_with_carry(prod.hi, hi_lo.hi, carry_out, carry_unused);
+
+  return prod;
+#endif // __SIZEOF_INT128__
+}
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SUPPORT_INTEGER_UTILS_H

libc/src/__support/number_pair.h

+//===-- Utilities for pairs of numbers. -------------------------*- 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_NUMBER_PAIR_H
+#define LLVM_LIBC_SRC_SUPPORT_NUMBER_PAIR_H
+
+#include "CPP/type_traits.h"
+
+#include <stdint.h>
+
+namespace __llvm_libc {
+
+template <typename T> struct NumberPair {
+  T lo;
+  T hi;
+};
+
+using DoubleDouble = NumberPair<double>;
+
+template <typename T>
+cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, NumberPair<T>>
+split(T a) {
+  constexpr size_t HALF_BIT_WIDTH = sizeof(T) * 4;
+  constexpr T LOWER_HALF_MASK = (T(1) << HALF_BIT_WIDTH) - T(1);
+  NumberPair<T> result;
+  result.lo = a & LOWER_HALF_MASK;
+  result.hi = a >> HALF_BIT_WIDTH;
+  return result;
+}
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_SUPPORT_NUMBER_PAIR_H

libc/test/src/__support/uint128_test.cpp

 #include "src/__support/UInt.h"
 
 #include "utils/UnitTest/Test.h"
 
 // We want to test __llvm_libc::cpp::UInt<128> explicitly. So, for convenience,
 // we use a sugar which does not conflict with the UInt128 type which can
 // resolve to __uint128_t if the platform has it.
 using LL_UInt128 = __llvm_libc::cpp::UInt<128>;
+using LL_UInt192 = __llvm_libc::cpp::UInt<192>;
+using LL_UInt256 = __llvm_libc::cpp::UInt<256>;
 
 TEST(LlvmLibcUInt128ClassTest, BasicInit) {
   LL_UInt128 empty;
   LL_UInt128 half_val(12345);
   LL_UInt128 full_val({12345, 67890});
   ASSERT_TRUE(half_val != full_val);
 }
 
TEST(LlvmLibcUInt128ClassTest, AdditionTests) {
   EXPECT_EQ(val3 + val4, val4 + val3);
 
   // 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 192-bit addition
+  LL_UInt192 val7({0x0123456789abcdef, 0xfedcba9876543210, 0xfedcba9889abcdef});
+  LL_UInt192 val8({0x1111222233334444, 0xaaaabbbbccccdddd, 0xeeeeffffeeeeffff});
+  LL_UInt192 result4(
+      {0x12346789bcdf1233, 0xa987765443210fed, 0xedcbba98789acdef});
+  EXPECT_EQ(val7 + val8, result4);
+  EXPECT_EQ(val7 + val8, val8 + val7);
+
+  // Test 256-bit addition
+  LL_UInt256 val9({0x1f1e1d1c1b1a1918, 0xf1f2f3f4f5f6f7f8, 0x0123456789abcdef,
+                   0xfedcba9876543210});
+  LL_UInt256 val10({0x1111222233334444, 0xaaaabbbbccccdddd, 0x1111222233334444,
+                    0xaaaabbbbccccdddd});
+  LL_UInt256 result5({0x302f3f3e4e4d5d5c, 0x9c9dafb0c2c3d5d5,
+                      0x12346789bcdf1234, 0xa987765443210fed});
+  EXPECT_EQ(val9 + val10, result5);
+  EXPECT_EQ(val9 + val10, val10 + val9);
 }
 
 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);
TEST(LlvmLibcUInt128ClassTest, MultiplicationTests) {
   // 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
   LL_UInt128 val9({0x01D762422C946590, 0x9F4F2726179A2245});
   LL_UInt128 val10({0x3792F412CB06794D, 0xCDB02555653131B6});
   LL_UInt128 result5({0x917cf11d1e039c50, 0x3a4f32d17f40d08f});
   EXPECT_EQ((val9 * val10), result5);
   EXPECT_EQ((val9 * val10), (val10 * val9));
+
+  // Test 192-bit multiplication
+  LL_UInt192 val11(
+      {0xffffffffffffffff, 0x01D762422C946590, 0x9F4F2726179A2245});
+  LL_UInt192 val12(
+      {0xffffffffffffffff, 0x3792F412CB06794D, 0xCDB02555653131B6});
+
+  LL_UInt192 result6(
+      {0x0000000000000001, 0xc695a9ab08652121, 0x5de7faf698d32732});
+  EXPECT_EQ((val11 * val12), result6);
+  EXPECT_EQ((val11 * val12), (val12 * val11));
+
+  LL_UInt256 val13({0xffffffffffffffff, 0x01D762422C946590, 0x9F4F2726179A2245,
+                    0xffffffffffffffff});
+  LL_UInt256 val14({0xffffffffffffffff, 0xffffffffffffffff, 0x3792F412CB06794D,
+                    0xCDB02555653131B6});
+  LL_UInt256 result7({0x0000000000000001, 0xfe289dbdd36b9a6f,
+                      0x291de4c71d5f646c, 0xfd37221cb06d4978});
+  EXPECT_EQ((val13 * val14), result7);
+  EXPECT_EQ((val13 * val14), (val14 * val13));
 }
 
 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);

libc/utils/UnitTest/LibcTest.cpp

public:
   void markFail() { Status = Result_Fail; }
 
 private:
   RunResult Status = Result_Pass;
 };
 
 namespace internal {
 
-// When the value is of integral type, just display it as normal.
-template <typename ValType>
-cpp::enable_if_t<cpp::is_integral_v<ValType>, std::string>
-describeValue(ValType Value) {
-  return std::to_string(Value);
-}
-
-std::string describeValue(std::string Value) { return std::string(Value); }
-std::string describeValue(cpp::string_view Value) {
-  return std::string(Value.data(), Value.size());
-}
-
 // When the value is UInt128 or __uint128_t, show its hexadecimal digits.
 // We cannot just use a UInt128 specialization as that resolves to only
 // one type, UInt<128> or __uint128_t. We want both overloads as we want to
 // be able to unittest UInt<128> on platforms where UInt128 resolves to
 // UInt128.
-// TODO(lntue): Investigate why UInt<128> was printed backward, with the lower
-// 64-bits first.
-template <typename UInt128Type>
-std::string describeValue128(UInt128Type Value) {
-  std::string S(sizeof(UInt128) * 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;
+template <typename T>
+cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, std::string>
+describeValueUInt(T Value) {
+  static_assert(sizeof(T) % 8 == 0, "Unsupported size of UInt");
+  std::string S(sizeof(T) * 2, '0');
+
+  constexpr char HEXADECIMALS[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
+                                     '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
+
+  for (auto I = S.rbegin(), End = S.rend(); I != End; ++I, Value >>= 8) {
+    unsigned char Mod = static_cast<unsigned char>(Value) & 0xFF;
+    *(I++) = HEXADECIMALS[Mod & 0x0F];
+    *I = HEXADECIMALS[Mod >> 4];
   }
 
   return "0x" + S;
 }
 
-#ifdef __SIZEOF_INT128__
-template <> std::string describeValue<__uint128_t>(__uint128_t Value) {
-  return describeValue128(Value);
+// When the value is of integral type, just display it as normal.
+template <typename ValType>
+cpp::enable_if_t<cpp::is_integral_v<ValType>, std::string>
+describeValue(ValType Value) {
+  if constexpr (sizeof(ValType) <= sizeof(uint64_t)) {
+    return std::to_string(Value);
+  } else {
+    return describeValueUInt(Value);
+  }
 }
-#endif
 
-template <>
-std::string
-describeValue<__llvm_libc::cpp::UInt<128>>(__llvm_libc::cpp::UInt<128> Value) {
-  return describeValue128(Value);
+std::string describeValue(std::string Value) { return std::string(Value); }
+std::string describeValue(cpp::string_view Value) {
+  return std::string(Value.data(), Value.size());
 }
 
 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, ' ');
template bool test<__uint128_t>(RunContext *Ctx, TestCondition Cond,
                                 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<__llvm_libc::cpp::UInt<192>>(
+    RunContext *Ctx, TestCondition Cond, __llvm_libc::cpp::UInt<192> LHS,
+    __llvm_libc::cpp::UInt<192> RHS, const char *LHSStr, const char *RHSStr,
+    const char *File, unsigned long Line);
+
+template bool test<__llvm_libc::cpp::UInt<256>>(
+    RunContext *Ctx, TestCondition Cond, __llvm_libc::cpp::UInt<256> LHS,
+    __llvm_libc::cpp::UInt<256> RHS, const char *LHSStr, const char *RHSStr,
+    const char *File, unsigned long Line);
+
 template bool test<__llvm_libc::cpp::string_view>(
     RunContext *Ctx, TestCondition Cond, __llvm_libc::cpp::string_view LHS,
     __llvm_libc::cpp::string_view RHS, const char *LHSStr, const char *RHSStr,
     const char *File, unsigned long Line);
 
 } // namespace internal
 
 bool Test::testStrEq(const char *LHS, const char *RHS, const char *LHSStr,

utils/bazel/llvm-project-overlay/libc/BUILD.bazel

cc_library(
     hdrs = ["src/__support/CPP/atomic.h"],
     deps = [
         ":__support_cpp_type_traits",
         ":libc_root",
     ],
 )
 
 cc_library(
+    name = "__support_number_pair",
+    hdrs = ["src/__support/number_pair.h"],
+    deps = [
+        "__support_cpp_type_traits",
+        ":libc_root",
+    ],
+)
+
+cc_library(
+    name = "__support_integer_utils",
+    hdrs = ["src/__support/integer_utils.h"],
+    deps = [
+        "__support_builtin_wrappers",
+        "__support_cpp_type_traits",
+        "__support_number_pair",
+        ":libc_root",
+    ],
+)
+
+cc_library(
     name = "__support_uint",
     hdrs = ["src/__support/UInt.h"],
     deps = [
         "__support_cpp_array",
         "__support_cpp_limits",
         "__support_cpp_type_traits",
         "__support_cpp_optional",
         "__support_builtin_wrappers",
+        "__support_number_pair",
+        "__support_integer_utils",
         ":libc_root",
     ],
 )
 
 cc_library(
     name = "__support_uint128",
     hdrs = ["src/__support/UInt128.h"],
     deps = [