[libc] Add Int<> type and fix (U)Int<128> compatibility issues.

[lntue]

Summary

Add Int<> and Int128 types to replace the usage of int128_t in math
functions. Clean up to make sure that (U)Int128 and (u)int128_t are
interchangeable in the code base.

[sivachandra]

libc/test/src/math/TruncTest.h

68 ↗

(On Diff #529669)

I did not do a detailed review but why were these constexpr decls converted to const decls?

[lntue]

libc/test/src/math/TruncTest.h

68 ↗

(On Diff #529669)

Because these use the division operator, which using clz() internally, which in turn calls __builtin_clz* that are not constexpr.

[lntue]

Add missing dependencies.

[sivachandra]

libc/test/src/math/TruncTest.h

68 ↗

(On Diff #529669)

We should be able to implement cpp::is_constant_evaluated using __builtin_is_constant_evaluated and use it to retain the constexpr nature where relevant. We should ideally do that first before adding BigInt.

[lntue]

Make clz functions constexpr.

[lntue]

Revert LDExpTest changes and sync to HEAD.

[lntue]

libc/test/src/math/TruncTest.h

68 ↗

(On Diff #529669)

Turns out that __builtin_clz* are already constexpr, so marking all our clz functions constexpr is enough.

[lntue]

Fix LibcTest merging issue.

[michaelrj]

overall LGTM

libc/src/__support/UInt.h

76

would it be possible to add a template version of this initializer for the primitive uint128?

[lntue]

Add conversion to and from __(u)int128_t.

libc/src/__support/UInt.h

76

I added conversion to and from __(u)int128_t.

[lntue]

Fix a unit test and sync to HEAD.

[mikhail.ramalho]

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

135

In https://reviews.llvm.org/D149594, I had to set the explicit bit when the value is not zero because some tests start to fail due to:

diff --git a/libc/src/__support/str_to_float.h b/libc/src/__support/str_to_float.h
index b36c73fbe8ef..79a1c8fe6f0b 100644
--- a/libc/src/__support/str_to_float.h
+++ b/libc/src/__support/str_to_float.h
@@ -13,6 +13,7 @@
 #include "src/__support/CPP/optional.h"
 #include "src/__support/FPUtil/FEnvImpl.h"
 #include "src/__support/FPUtil/FPBits.h"
+#include "src/__support/FPUtil/dyadic_float.h"
 #include "src/__support/UInt128.h"
 #include "src/__support/builtin_wrappers.h"
 #include "src/__support/common.h"
@@ -570,7 +572,9 @@ clinger_fast_path(ExpandedFloat<T> init_num,
   }
 
   fputil::FPBits<T> result;
-  T float_mantissa = static_cast<T>(mantissa);
+  T float_mantissa =
+      static_cast<T>(fputil::DyadicFloat<128>(/*sign*/ false, /*exponent*/ 0,
+                                              /*mantissa*/ mantissa));
 
   if (exp10 == 0) {
     result = fputil::FPBits<T>(float_mantissa);
-- 
2.39.2

We need this change to support platforms with no native 128-bit integers.

May I ask if you can double-check that?

[mikhail.ramalho]

The tests are all passing in rv32 once we apply D148797, D150211, D150223 and the following change:

diff --git a/libc/src/__support/FPUtil/generic/sqrt.h b/libc/src/__support/FPUtil/generic/sqrt.h
index 9e9896ed185f..7c4e4a485320 100644
--- a/libc/src/__support/FPUtil/generic/sqrt.h
+++ b/libc/src/__support/FPUtil/generic/sqrt.h
@@ -137,7 +137,7 @@ LIBC_INLINE cpp::enable_if_t<cpp::is_floating_point_v<T>, T> sqrt(T x) {
       }
 
       // We compute one more iteration in order to round correctly.
-      bool lsb = y & 1; // Least significant bit
+      bool lsb = bool(y & 1); // Least significant bit
       bool rb = false;  // Round bit
       r <<= 2;
       UIntType tmp = (y << 2) + 1;

Feel free to add it to this patch, otherwise, I can add it to D150223 once I rebase it.

[lntue]

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

135

This code path should not be in ARM32 or RISCV-32 platforms? I thought that for those platform, long double is either double or quad precision (Float128), right?

[sivachandra]

libc/src/__support/UInt.h

102

Should there be an additional condition sizeof(T) <= 16?

[mikhail.ramalho]

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

135

It's not used in rv32, but because of the change to the clinger_fast_path function, this gets called in other platforms

[lntue]

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

135

Do you mind creating a github issue for me or @michaelrj to investigate the problem? It's possible that we might need to clean up some comparison / testing codes for x86 long double instead.

libc/src/__support/CMakeLists.txt

DEPENDS
     .str_to_integer
     .str_to_num_result
     .uint128
     libc.src.__support.CPP.optional
     libc.src.__support.CPP.limits
     libc.src.__support.FPUtil.fenv_impl
     libc.src.__support.FPUtil.fp_bits
     libc.src.__support.FPUtil.rounding_mode
+    libc.src.__support.FPUtil.dyadic_float
     libc.src.__support.builtin_wrappers
     libc.src.__support.common
     libc.src.errno.errno
 )
 
 
 add_header_library(
   integer_operations

libc/src/__support/FPUtil/generic/sqrt.h

if (bits.is_inf_or_nan()) {
         UIntType tmp = (y << 1) + current_bit; // 2*y(n - 1) + 2^(-n-1)
         if (r >= tmp) {
           r -= tmp;
           y += current_bit;
         }
       }
 
       // We compute one more iteration in order to round correctly.
-      bool lsb = y & 1; // Least significant bit
+      bool lsb = static_cast<bool>(y & 1); // Least significant bit
       bool rb = false;  // Round bit
       r <<= 2;
       UIntType tmp = (y << 2) + 1;
       if (r >= tmp) {
         r -= tmp;
         rb = true;
       }
 

libc/src/__support/FPUtil/generic/sqrt_80_bit_long_double.h

for (UIntType current_bit = ONE >> 1; current_bit; current_bit >>= 1) {
       UIntType tmp = (y << 1) + current_bit; // 2*y(n - 1) + 2^(-n-1)
       if (r >= tmp) {
         r -= tmp;
         y += current_bit;
       }
     }
 
     // We compute one more iteration in order to round correctly.
-    bool lsb = y & 1; // Least significant bit
+    bool lsb = static_cast<bool>(y & 1); // Least significant bit
     bool rb = false;  // Round bit
     r <<= 2;
     UIntType tmp = (y << 2) + 1;
     if (r >= tmp) {
       r -= tmp;
       rb = true;
     }
 

libc/src/__support/FPUtil/x86_64/LongDoubleBits.h

LIBC_INLINE UIntType uintval() {
     // We zero the padding bits as they can contain garbage.
     static constexpr UIntType MASK =
         (UIntType(1) << (sizeof(long double) * 8 -
                          Padding<sizeof(uintptr_t)>::VALUE)) -
         1;
     return bits & MASK;
   }
 
+  LIBC_INLINE long double get_val() const {
+    return cpp::bit_cast<long double>(bits);
+  }
+
   LIBC_INLINE int get_exponent() const {
     if (get_unbiased_exponent() == 0)
       return int(1) - EXPONENT_BIAS;
     return int(get_unbiased_exponent()) - EXPONENT_BIAS;
   }
 
   LIBC_INLINE bool is_zero() const {
     return get_unbiased_exponent() == 0 && get_mantissa() == 0 &&

libc/src/__support/UInt.h

 #include "src/__support/macros/optimization.h" // LIBC_UNLIKELY
 #include "src/__support/number_pair.h"
 
 #include <stddef.h> // For size_t
 #include <stdint.h>
 
 namespace __llvm_libc::cpp {
 
-template <size_t Bits> struct UInt {
+template <size_t Bits, bool Signed> struct BigInt {
 
   static_assert(Bits > 0 && Bits % 64 == 0,
-                "Number of bits in UInt should be a multiple of 64.");
+                "Number of bits in BigInt 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; }
 
-  constexpr UInt() = default;
+  constexpr BigInt() = default;
 
-  constexpr UInt(const UInt<Bits> &other) = default;
+  constexpr BigInt(const BigInt<Bits, Signed> &other) = default;
 
-  template <size_t OtherBits> constexpr UInt(const UInt<OtherBits> &other) {
+  template <size_t OtherBits, bool OtherSigned>
+  constexpr BigInt(const BigInt<OtherBits, OtherSigned> &other) {
     if (OtherBits >= Bits) {
       for (size_t i = 0; i < WORDCOUNT; ++i)
         val[i] = other[i];
     } else {
       size_t i = 0;
       for (; i < OtherBits / 64; ++i)
         val[i] = other[i];
+      uint64_t sign = 0;
+      if constexpr (Signed && OtherSigned) {
+        sign = static_cast<uint64_t>(
+            -static_cast<int64_t>(other[OtherBits / 64 - 1] >> 63));
+      }
       for (; i < WORDCOUNT; ++i)
-        val[i] = 0;
+        val[i] = sign;
     }
   }
 
-  // Construct a UInt from a C array.
+  // Construct a BigInt from a C array.
   template <size_t N, enable_if_t<N <= WORDCOUNT, int> = 0>
-  constexpr UInt(const uint64_t (&nums)[N]) {
+  constexpr BigInt(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;
-    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];
-  }
+  template <typename T,
+            typename = cpp::enable_if_t<is_integral_v<T> && sizeof(T) <= 16>>
+  constexpr BigInt(T v) {
+    val[0] = static_cast<uint64_t>(v);
 
-  constexpr explicit operator unsigned long long() const {
-    return static_cast<unsigned long long>(val[0]);
-  }
+    if constexpr (Bits == 64)
+      return;
 
-  constexpr explicit operator unsigned long() const {
-    return static_cast<unsigned long>(val[0]);
+    // Bits is at least 128.
+    size_t i = 1;
+    if constexpr (sizeof(T) == 16) {
+      val[1] = static_cast<uint64_t>(v >> 64);
+      i = 2;
     }
 
-  constexpr explicit operator unsigned int() const {
-    return static_cast<unsigned int>(val[0]);
+    uint64_t sign = (Signed && (v < 0)) ? 0xffff'ffff'ffff'ffff : 0;
+    for (; i < WORDCOUNT; ++i) {
+      val[i] = sign;
+    }
   }
 
-  constexpr explicit operator unsigned short() const {
-    return static_cast<unsigned short>(val[0]);
+  constexpr explicit BigInt(const cpp::array<uint64_t, WORDCOUNT> &words) {
+    for (size_t i = 0; i < WORDCOUNT; ++i)
+      val[i] = words[i];
   }
 
-  constexpr explicit operator unsigned char() const {
-    return static_cast<unsigned char>(val[0]);
+  template <typename T, typename = cpp::enable_if_t<cpp::is_integral_v<T> &&
+                                                    sizeof(T) <= 16 &&
+                                                    !cpp::is_same_v<T, bool>>>
+  constexpr explicit operator T() const {
+    if constexpr (sizeof(T) <= 8)
+      return static_cast<T>(val[0]);
+
+    // T is 128-bit.
+    T lo = static_cast<T>(val[0]);
+
+    if constexpr (Bits == 64) {
+      if constexpr (Signed) {
+        // Extend sign for negative numbers.
+        return (val[0] >> 63) ? ((T(-1) << 64) + lo) : lo;
+      } else {
+        return lo;
+      }
+    } else {
+      return (static_cast<T>(val[1]) << 64) + lo;
+    }
   }
 
   constexpr explicit operator bool() const { return !is_zero(); }
 
-  UInt<Bits> &operator=(const UInt<Bits> &other) = default;
+  BigInt<Bits, Signed> &operator=(const BigInt<Bits, Signed> &other) = default;
 
   constexpr bool is_zero() const {
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       if (val[i] != 0)
         return false;
     }
     return true;
   }
 
   // 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) {
+  constexpr uint64_t add(const BigInt<Bits, Signed> &x) {
     SumCarry<uint64_t> s{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       s = add_with_carry(val[i], x.val[i], s.carry);
       val[i] = s.sum;
     }
     return s.carry;
   }
 
-  UInt<Bits> operator+(const UInt<Bits> &other) const {
-    UInt<Bits> result;
+  BigInt<Bits, Signed> operator+(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> result;
     SumCarry<uint64_t> s{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       s = add_with_carry(val[i], other.val[i], s.carry);
       result.val[i] = s.sum;
     }
     return result;
   }
 
   // This will only apply when initializing a variable from constant values, so
   // it will always use the constexpr version of add_with_carry.
-  constexpr UInt<Bits> operator+(UInt<Bits> &&other) const {
-    UInt<Bits> result;
+  constexpr BigInt<Bits, Signed> operator+(BigInt<Bits, Signed> &&other) const {
+    BigInt<Bits, Signed> result;
     SumCarry<uint64_t> s{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       s = add_with_carry_const(val[i], other.val[i], s.carry);
       result.val[i] = s.sum;
     }
     return result;
   }
 
-  constexpr UInt<Bits> &operator+=(const UInt<Bits> &other) {
+  constexpr BigInt<Bits, Signed> &
+  operator+=(const BigInt<Bits, Signed> &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.
-  constexpr uint64_t sub(const UInt<Bits> &x) {
+  constexpr uint64_t sub(const BigInt<Bits, Signed> &x) {
     DiffBorrow<uint64_t> d{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       d = sub_with_borrow(val[i], x.val[i], d.borrow);
       val[i] = d.diff;
     }
     return d.borrow;
   }
 
-  UInt<Bits> operator-(const UInt<Bits> &other) const {
-    UInt<Bits> result;
+  BigInt<Bits, Signed> operator-(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> result;
     DiffBorrow<uint64_t> d{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       d = sub_with_borrow(val[i], other.val[i], d.borrow);
       result.val[i] = d.diff;
     }
     return result;
   }
 
-  constexpr UInt<Bits> operator-(UInt<Bits> &&other) const {
-    UInt<Bits> result;
+  constexpr BigInt<Bits, Signed> operator-(BigInt<Bits, Signed> &&other) const {
+    BigInt<Bits, Signed> result;
     DiffBorrow<uint64_t> d{0, 0};
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       d = sub_with_borrow_const(val[i], other.val[i], d.borrow);
       result.val[i] = d.diff;
     }
     return result;
   }
 
-  constexpr UInt<Bits> &operator-=(const UInt<Bits> &other) {
+  constexpr BigInt<Bits, Signed> &
+  operator-=(const BigInt<Bits, Signed> &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) {
-    UInt<128> partial_sum(0);
+    BigInt<128, Signed> partial_sum(0);
     uint64_t carry = 0;
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       NumberPair<uint64_t> prod = full_mul(val[i], x);
-      UInt<128> tmp({prod.lo, prod.hi});
+      BigInt<128, Signed> 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;
     }
     return partial_sum.val[1];
   }
 
-  constexpr UInt<Bits> operator*(const UInt<Bits> &other) const {
+  constexpr BigInt<Bits, Signed>
+  operator*(const BigInt<Bits, Signed> &other) const {
+    if constexpr (Signed) {
+      BigInt<Bits, false> a(*this);
+      BigInt<Bits, false> b(other);
+      bool a_neg = (a.val[WORDCOUNT - 1] >> 63);
+      bool b_neg = (b.val[WORDCOUNT - 1] >> 63);
+      if (a_neg)
+        a = -a;
+      if (b_neg)
+        b = -b;
+      BigInt<Bits, false> prod = a * b;
+      if (a_neg != b_neg)
+        prod = -prod;
+      return static_cast<BigInt<Bits, true>>(prod);
+    } else {
+
       if constexpr (WORDCOUNT == 1) {
         return {val[0] * other.val[0]};
       } else {
-      UInt<Bits> result(0);
-      UInt<128> partial_sum(0);
+        BigInt<Bits, Signed> result(0);
+        BigInt<128, Signed> partial_sum(0);
         uint64_t carry = 0;
         for (size_t i = 0; i < WORDCOUNT; ++i) {
           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});
+            BigInt<128, Signed> 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;
       }
     }
+  }
 
-  // Return the full product.
+  // Return the full product, only unsigned for now.
   template <size_t OtherBits>
-  constexpr UInt<Bits + OtherBits> ful_mul(const UInt<OtherBits> &other) const {
-    UInt<Bits + OtherBits> result(0);
-    UInt<128> partial_sum(0);
+  constexpr BigInt<Bits + OtherBits, Signed>
+  ful_mul(const BigInt<OtherBits, Signed> &other) const {
+    BigInt<Bits + OtherBits, Signed> result(0);
+    BigInt<128, Signed> partial_sum(0);
     uint64_t carry = 0;
-    constexpr size_t OTHER_WORDCOUNT = UInt<OtherBits>::WORDCOUNT;
+    constexpr size_t OTHER_WORDCOUNT = BigInt<OtherBits, Signed>::WORDCOUNT;
     for (size_t i = 0; i <= WORDCOUNT + OTHER_WORDCOUNT - 2; ++i) {
       const size_t lower_idx =
           i < OTHER_WORDCOUNT ? 0 : i - OTHER_WORDCOUNT + 1;
       const size_t upper_idx = i < WORDCOUNT ? i : WORDCOUNT - 1;
       for (size_t j = lower_idx; j <= upper_idx; ++j) {
         NumberPair<uint64_t> prod = full_mul(val[j], other.val[i - j]);
-        UInt<128> tmp({prod.lo, prod.hi});
+        BigInt<128, Signed> 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;
     }
     result.val[WORDCOUNT + OTHER_WORDCOUNT - 1] = partial_sum.val[0];
template <size_t Bits, bool Signed> struct BigInt {
   //
   // Performance summary:
   //   Number of 64-bit x 64-bit -> 128-bit multiplications performed.
   //   Bits  WORDCOUNT  ful_mul  quick_mul_hi  Error bound
   //    128      2         4           3            1
   //    196      3         9           6            2
   //    256      4        16          10            3
   //    512      8        64          36            7
-  constexpr UInt<Bits> quick_mul_hi(const UInt<Bits> &other) const {
-    UInt<Bits> result(0);
-    UInt<128> partial_sum(0);
+  constexpr BigInt<Bits, Signed>
+  quick_mul_hi(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> result(0);
+    BigInt<128, Signed> partial_sum(0);
     uint64_t carry = 0;
     // First round of accumulation for those at WORDCOUNT - 1 in the full
     // product.
     for (size_t i = 0; i < WORDCOUNT; ++i) {
       NumberPair<uint64_t> prod =
           full_mul(val[i], other.val[WORDCOUNT - 1 - i]);
-      UInt<128> tmp({prod.lo, prod.hi});
+      BigInt<128, Signed> tmp({prod.lo, prod.hi});
       carry += partial_sum.add(tmp);
     }
     for (size_t i = WORDCOUNT; i < 2 * WORDCOUNT - 1; ++i) {
       partial_sum.val[0] = partial_sum.val[1];
       partial_sum.val[1] = carry;
       carry = 0;
       for (size_t j = i - WORDCOUNT + 1; j < WORDCOUNT; ++j) {
         NumberPair<uint64_t> prod = full_mul(val[j], other.val[i - j]);
-        UInt<128> tmp({prod.lo, prod.hi});
+        BigInt<128, Signed> tmp({prod.lo, prod.hi});
         carry += partial_sum.add(tmp);
       }
       result.val[i - WORDCOUNT] = partial_sum.val[0];
     }
     result.val[WORDCOUNT - 1] = partial_sum.val[1];
     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;
+    BigInt<Bits, Signed> result = 1;
+    BigInt<Bits, Signed> cur_power = *this;
 
     while (power > 0) {
       if ((power % 2) > 0) {
         result = result * cur_power;
       }
       power = power >> 1;
       cur_power *= cur_power;
     }
     *this = result;
   }
 
-  // div takes another UInt of the same size and divides this by it. The value
+  // TODO: Make division work correctly for signed integers.
+
+  // div takes another BigInt 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 optional<UInt<Bits>> div(const UInt<Bits> &other) {
-    UInt<Bits> remainder(0);
+  constexpr optional<BigInt<Bits, Signed>>
+  div(const BigInt<Bits, Signed> &other) {
+    BigInt<Bits, Signed> remainder(0);
     if (*this < other) {
       remainder = *this;
-      *this = UInt<Bits>(0);
+      *this = BigInt<Bits, Signed>(0);
       return remainder;
     }
     if (other == 1) {
       return remainder;
     }
     if (other == 0) {
       return nullopt;
     }
 
-    UInt<Bits> quotient(0);
-    UInt<Bits> subtractor = other;
+    BigInt<Bits, Signed> quotient(0);
+    BigInt<Bits, Signed> subtractor = other;
     int cur_bit = subtractor.clz() - this->clz();
     subtractor.shift_left(cur_bit);
 
     for (; cur_bit >= 0 && *this > 0; --cur_bit, subtractor.shift_right(1)) {
       if (*this >= subtractor) {
         this->sub(subtractor);
-        quotient = quotient | (UInt<Bits>(1) << cur_bit);
+        quotient = quotient | (BigInt<Bits, Signed>(1) << cur_bit);
       }
     }
     remainder = *this;
     *this = quotient;
     return remainder;
   }
 
-  // Efficiently perform UInt / (x * 2^e), where x is a 32-bit unsigned integer,
-  // and return the remainder.
-  // The main idea is as follow:
+  // Efficiently perform BigInt / (x * 2^e), where x is a 32-bit unsigned
+  // integer, and return the remainder. The main idea is as follow:
   //   Let q = y / (x * 2^e) be the quotient, and
   //       r = y % (x * 2^e) be the remainder.
   //   First, notice that:
   //     r % (2^e) = y % (2^e),
   // so we just need to focus on all the bits of y that is >= 2^e.
   //   To speed up the shift-and-add steps, we only use x as the divisor, and
   // performing 32-bit shiftings instead of bit-by-bit shiftings.
   //   Since the remainder of each division step < x < 2^32, the computation of
   // each step is now properly contained within uint64_t.
   //   And finally we perform some extra alignment steps for the remaining bits.
-  constexpr optional<UInt<Bits>> div_uint32_times_pow_2(uint32_t x, size_t e) {
-    UInt<Bits> remainder(0);
+  constexpr optional<BigInt<Bits, Signed>> div_uint32_times_pow_2(uint32_t x,
+                                                                  size_t e) {
+    BigInt<Bits, Signed> remainder(0);
 
     if (x == 0) {
       return nullopt;
     }
     if (e >= Bits) {
       remainder = *this;
-      *this = UInt<Bits>(0);
+      *this = BigInt<Bits, false>(0);
       return remainder;
     }
 
-    UInt<Bits> quotient(0);
+    BigInt<Bits, Signed> quotient(0);
     uint64_t x64 = static_cast<uint64_t>(x);
     // lower64 = smallest multiple of 64 that is >= e.
     size_t lower64 = ((e >> 6) + ((e & 63) != 0)) << 6;
     // lower_pos is the index of the closest 64-bit chunk >= 2^e.
     size_t lower_pos = lower64 / 64;
     // Keep track of current remainder mod x * 2^(32*i)
     uint64_t rem = 0;
     // pos is the index of the current 64-bit chunk that we are processing.
constexpr optional<BigInt<Bits, Signed>> div_uint32_times_pow_2(uint32_t x,
     for (; pos > 0; --pos) {
       remainder[pos - 1] = val[pos - 1];
     }
 
     *this = quotient;
     return remainder;
   }
 
-  constexpr UInt<Bits> operator/(const UInt<Bits> &other) const {
-    UInt<Bits> result(*this);
+  constexpr BigInt<Bits, Signed>
+  operator/(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> result(*this);
     result.div(other);
     return result;
   }
 
-  constexpr UInt<Bits> operator%(const UInt<Bits> &other) const {
-    UInt<Bits> result(*this);
+  constexpr BigInt<Bits, Signed> &
+  operator/=(const BigInt<Bits, Signed> &other) {
+    div(other);
+    return *this;
+  }
+
+  constexpr BigInt<Bits, Signed>
+  operator%(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> result(*this);
     return *result.div(other);
   }
 
-  constexpr UInt<Bits> &operator*=(const UInt<Bits> &other) {
+  constexpr BigInt<Bits, Signed> &
+  operator*=(const BigInt<Bits, Signed> &other) {
     *this = *this * other;
     return *this;
   }
 
   constexpr uint64_t clz() {
     uint64_t leading_zeroes = 0;
     for (size_t i = WORDCOUNT; i > 0; --i) {
       if (val[i - 1] == 0) {
if (drop < WORDCOUNT) {
       }
     }
 
     for (size_t j = 0; j < i; ++j) {
       val[j] = 0;
     }
   }
 
-  constexpr UInt<Bits> operator<<(size_t s) const {
-    UInt<Bits> result(*this);
+  constexpr BigInt<Bits, Signed> operator<<(size_t s) const {
+    BigInt<Bits, Signed> result(*this);
     result.shift_left(s);
     return result;
   }
 
-  constexpr UInt<Bits> &operator<<=(size_t s) {
+  constexpr BigInt<Bits, Signed> &operator<<=(size_t s) {
     shift_left(s);
     return *this;
   }
 
   constexpr void shift_right(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);
+      if constexpr (Signed) {
+        tmp = static_cast<__uint128_t>(static_cast<__int128_t>(tmp) >> s);
+      } else {
         tmp >>= s;
+      }
       val[0] = uint64_t(tmp);
       val[1] = uint64_t(tmp >> 64);
       return;
     }
 #endif // __SIZEOF_INT128__
 
     if (LIBC_UNLIKELY(s == 0))
       return;
     const size_t drop = s / 64;  // Number of words to drop
     const size_t shift = s % 64; // Bit shift in the remaining words.
 
     size_t i = 0;
+    uint64_t sign = Signed ? (val[WORDCOUNT - 1] >> 63) : 0;
 
     if (drop < WORDCOUNT) {
       if (shift > 0) {
         for (size_t j = drop; j < WORDCOUNT - 1; ++i, ++j) {
           val[i] = (val[j] >> shift) | (val[j + 1] << (64 - shift));
         }
+        if constexpr (Signed) {
+          val[i] = static_cast<uint64_t>(
+              static_cast<int64_t>(val[WORDCOUNT - 1]) >> shift);
+        } else {
           val[i] = val[WORDCOUNT - 1] >> shift;
+        }
         ++i;
       } else {
         for (size_t j = drop; j < WORDCOUNT; ++i, ++j) {
           val[i] = val[j];
         }
       }
     }
 
     for (; i < WORDCOUNT; ++i) {
-      val[i] = 0;
+      val[i] = sign;
     }
   }
 
-  constexpr UInt<Bits> operator>>(size_t s) const {
-    UInt<Bits> result(*this);
+  constexpr BigInt<Bits, Signed> operator>>(size_t s) const {
+    BigInt<Bits, Signed> result(*this);
     result.shift_right(s);
     return result;
   }
 
-  constexpr UInt<Bits> &operator>>=(size_t s) {
+  constexpr BigInt<Bits, Signed> &operator>>=(size_t s) {
     shift_right(s);
     return *this;
   }
 
-  constexpr UInt<Bits> operator&(const UInt<Bits> &other) const {
-    UInt<Bits> result;
+  constexpr BigInt<Bits, Signed>
+  operator&(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> 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) {
+  constexpr BigInt<Bits, Signed> &
+  operator&=(const BigInt<Bits, Signed> &other) {
     for (size_t i = 0; i < WORDCOUNT; ++i)
       val[i] &= other.val[i];
     return *this;
   }
 
-  constexpr UInt<Bits> operator|(const UInt<Bits> &other) const {
-    UInt<Bits> result;
+  constexpr BigInt<Bits, Signed>
+  operator|(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> 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) {
+  constexpr BigInt<Bits, Signed> &
+  operator|=(const BigInt<Bits, Signed> &other) {
     for (size_t i = 0; i < WORDCOUNT; ++i)
       val[i] |= other.val[i];
     return *this;
   }
 
-  constexpr UInt<Bits> operator^(const UInt<Bits> &other) const {
-    UInt<Bits> result;
+  constexpr BigInt<Bits, Signed>
+  operator^(const BigInt<Bits, Signed> &other) const {
+    BigInt<Bits, Signed> 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) {
+  constexpr BigInt<Bits, Signed> &
+  operator^=(const BigInt<Bits, Signed> &other) {
     for (size_t i = 0; i < WORDCOUNT; ++i)
       val[i] ^= other.val[i];
     return *this;
   }
 
-  constexpr UInt<Bits> operator~() const {
-    UInt<Bits> result;
+  constexpr BigInt<Bits, Signed> operator~() const {
+    BigInt<Bits, Signed> result;
     for (size_t i = 0; i < WORDCOUNT; ++i)
       result.val[i] = ~val[i];
     return result;
   }
 
-  constexpr bool operator==(const UInt<Bits> &other) const {
+  constexpr BigInt<Bits, Signed> operator-() const {
+    BigInt<Bits, Signed> result = ~(*this);
+    result.add(BigInt<Bits, Signed>(1));
+    return result;
+  }
+
+  constexpr bool operator==(const BigInt<Bits, Signed> &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 {
+  constexpr bool operator!=(const BigInt<Bits, Signed> &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 {
+  constexpr bool operator>(const BigInt<Bits, Signed> &other) const {
+    if constexpr (Signed) {
+      // Check for different signs;
+      bool a_sign = val[WORDCOUNT - 1] >> 63;
+      bool b_sign = other.val[WORDCOUNT - 1] >> 63;
+      if (a_sign != b_sign) {
+        return b_sign;
+      }
+    }
     for (size_t i = WORDCOUNT; i > 0; --i) {
       uint64_t word = val[i - 1];
       uint64_t other_word = other.val[i - 1];
       if (word > other_word)
         return true;
       else if (word < other_word)
         return false;
     }
     // Equal
     return false;
   }
 
-  constexpr bool operator>=(const UInt<Bits> &other) const {
+  constexpr bool operator>=(const BigInt<Bits, Signed> &other) const {
+    if constexpr (Signed) {
+      // Check for different signs;
+      bool a_sign = val[WORDCOUNT - 1] >> 63;
+      bool b_sign = other.val[WORDCOUNT - 1] >> 63;
+      if (a_sign != b_sign) {
+        return b_sign;
+      }
+    }
     for (size_t i = WORDCOUNT; i > 0; --i) {
       uint64_t word = val[i - 1];
       uint64_t other_word = other.val[i - 1];
       if (word > other_word)
         return true;
       else if (word < other_word)
         return false;
     }
     // Equal
     return true;
   }
 
-  constexpr bool operator<(const UInt<Bits> &other) const {
+  constexpr bool operator<(const BigInt<Bits, Signed> &other) const {
+    if constexpr (Signed) {
+      // Check for different signs;
+      bool a_sign = val[WORDCOUNT - 1] >> 63;
+      bool b_sign = other.val[WORDCOUNT - 1] >> 63;
+      if (a_sign != b_sign) {
+        return a_sign;
+      }
+    }
+
     for (size_t i = WORDCOUNT; i > 0; --i) {
       uint64_t word = val[i - 1];
       uint64_t other_word = other.val[i - 1];
       if (word > other_word)
         return false;
       else if (word < other_word)
         return true;
     }
     // Equal
     return false;
   }
 
-  constexpr bool operator<=(const UInt<Bits> &other) const {
+  constexpr bool operator<=(const BigInt<Bits, Signed> &other) const {
+    if constexpr (Signed) {
+      // Check for different signs;
+      bool a_sign = val[WORDCOUNT - 1] >> 63;
+      bool b_sign = other.val[WORDCOUNT - 1] >> 63;
+      if (a_sign != b_sign) {
+        return a_sign;
+      }
+    }
     for (size_t i = WORDCOUNT; i > 0; --i) {
       uint64_t word = val[i - 1];
       uint64_t other_word = other.val[i - 1];
       if (word > other_word)
         return false;
       else if (word < other_word)
         return true;
     }
     // Equal
     return true;
   }
 
-  constexpr UInt<Bits> &operator++() {
-    UInt<Bits> one(1);
+  constexpr BigInt<Bits, Signed> &operator++() {
+    BigInt<Bits, Signed> one(1);
     add(one);
     return *this;
   }
 
+  constexpr BigInt<Bits, Signed> operator++(int) {
+    BigInt<Bits, Signed> oldval(*this);
+    BigInt<Bits, Signed> one(1);
+    add(one);
+    return oldval;
+  }
+
+  constexpr BigInt<Bits, Signed> &operator--() {
+    BigInt<Bits, Signed> one(1);
+    sub(one);
+    return *this;
+  }
+
+  constexpr BigInt<Bits, Signed> operator--(int) {
+    BigInt<Bits, Signed> oldval(*this);
+    BigInt<Bits, Signed> one(1);
+    sub(one);
+    return oldval;
+  }
+
   // Return the i-th 64-bit word of the number.
   constexpr const uint64_t &operator[](size_t i) const { return val[i]; }
 
   // Return the i-th 64-bit word of the number.
   constexpr uint64_t &operator[](size_t i) { return val[i]; }
 
   uint64_t *data() { return val; }
 
   const uint64_t *data() const { return val; }
 };
 
-// Provides limits of UInt<128>.
+template <size_t Bits> using UInt = BigInt<Bits, false>;
+
+template <size_t Bits> using Int = BigInt<Bits, true>;
+
+// Provides limits of U/Int<128>.
 template <> class numeric_limits<UInt<128>> {
 public:
-  static constexpr UInt<128> max() { return ~UInt<128>(0); }
-  static constexpr UInt<128> min() { return 0; }
+  static constexpr UInt<128> max() {
+    return UInt<128>({0xffff'ffff'ffff'ffff, 0xffff'ffff'ffff'ffff});
+  }
+  static constexpr UInt<128> min() { return UInt<128>(0); }
 };
 
-// Provides is_integral of UInt<128>, UInt<192>, UInt<256>.
-template <size_t Bits> struct is_integral<UInt<Bits>> : public cpp::true_type {
+template <> class numeric_limits<Int<128>> {
+public:
+  static constexpr Int<128> max() {
+    return Int<128>({0xffff'ffff'ffff'ffff, 0x7fff'ffff'ffff'ffff});
+  }
+  static constexpr Int<128> min() {
+    return Int<128>({0, 0x8000'0000'0000'0000});
+  }
+};
+
+// Provides is_integral of U/Int<128>, U/Int<192>, U/Int<256>.
+template <size_t Bits, bool Signed>
+struct is_integral<BigInt<Bits, Signed>> : cpp::true_type {
   static_assert(Bits > 0 && Bits % 64 == 0,
-                "Number of bits in UInt should be a multiple of 64.");
+                "Number of bits in BigInt 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.");
 };
 
+template <size_t Bits>
+struct make_unsigned<Int<Bits>> : type_identity<UInt<Bits>> {
+  static_assert(Bits > 0 && Bits % 64 == 0,
+                "Number of bits in Int should be a multiple of 64.");
+};
+
 } // namespace __llvm_libc::cpp
 
 #endif // LLVM_LIBC_SRC_SUPPORT_UINT_H

libc/src/__support/UInt128.h

-//===-- A 128 bit unsigned int type -----------------------------*- C++ -*-===//
+//===-- 128-bit signed and unsigned int types -------------------*- 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_UINT128_H
 #define LLVM_LIBC_SRC_SUPPORT_UINT128_H
 
 #include "UInt.h"
 
 #if !defined(__SIZEOF_INT128__)
 using UInt128 = __llvm_libc::cpp::UInt<128>;
+using Int128 = __llvm_libc::cpp::Int<128>;
 #else
 using UInt128 = __uint128_t;
+using Int128 = __int128_t;
 #endif
 
 #endif // LLVM_LIBC_SRC_SUPPORT_UINT128_H

libc/src/__support/builtin_wrappers.h

 namespace __llvm_libc {
 
 // The following overloads are matched based on what is accepted by
 // __builtin_clz/ctz* rather than using the exactly-sized aliases from stdint.h.
 // This way, we can avoid making any assumptions about integer sizes and let the
 // compiler match for us.
 namespace __internal {
 
-template <typename T> LIBC_INLINE int correct_zero(T val, int bits) {
+template <typename T> LIBC_INLINE int constexpr correct_zero(T val, int bits) {
   if (val == T(0))
     return sizeof(T(0)) * 8;
   else
     return bits;
 }
 
-template <typename T> LIBC_INLINE int clz(T val);
+template <typename T> LIBC_INLINE constexpr int clz(T val);
 template <> LIBC_INLINE int clz<unsigned int>(unsigned int val) {
   return __builtin_clz(val);
 }
-template <> LIBC_INLINE int clz<unsigned long int>(unsigned long int val) {
+template <>
+LIBC_INLINE constexpr int clz<unsigned long int>(unsigned long int val) {
   return __builtin_clzl(val);
 }
 template <>
-LIBC_INLINE int clz<unsigned long long int>(unsigned long long int val) {
+LIBC_INLINE constexpr int
+clz<unsigned long long int>(unsigned long long int val) {
   return __builtin_clzll(val);
 }
 
-template <typename T> LIBC_INLINE int ctz(T val);
+template <typename T> LIBC_INLINE constexpr int ctz(T val);
 template <> LIBC_INLINE int ctz<unsigned int>(unsigned int val) {
   return __builtin_ctz(val);
 }
-template <> LIBC_INLINE int ctz<unsigned long int>(unsigned long int val) {
+template <>
+LIBC_INLINE constexpr int ctz<unsigned long int>(unsigned long int val) {
   return __builtin_ctzl(val);
 }
 template <>
-LIBC_INLINE int ctz<unsigned long long int>(unsigned long long int val) {
+LIBC_INLINE constexpr int
+ctz<unsigned long long int>(unsigned long long int val) {
   return __builtin_ctzll(val);
 }
 } // namespace __internal
 
-template <typename T> LIBC_INLINE int safe_ctz(T val) {
+template <typename T> LIBC_INLINE constexpr int safe_ctz(T val) {
   return __internal::correct_zero(val, __internal::ctz(val));
 }
 
-template <typename T> LIBC_INLINE int unsafe_ctz(T val) {
+template <typename T> LIBC_INLINE constexpr int unsafe_ctz(T val) {
   return __internal::ctz(val);
 }
 
-template <typename T> LIBC_INLINE int safe_clz(T val) {
+template <typename T> LIBC_INLINE constexpr int safe_clz(T val) {
   return __internal::correct_zero(val, __internal::clz(val));
 }
 
-template <typename T> LIBC_INLINE int unsafe_clz(T val) {
+template <typename T> LIBC_INLINE constexpr int unsafe_clz(T val) {
   return __internal::clz(val);
 }
 
 // Add with carry
 DEFINE_NAMED_PAIR_TEMPLATE(SumCarry, sum, carry);
 
 // This version is always valid for constexpr.
 template <typename T>

libc/src/__support/float_to_string.h

 
 LIBC_INLINE uint32_t mul_shift_mod_1e9(const MantissaInt mantissa,
                                        const cpp::UInt<MID_INT_SIZE> &large,
                                        const int32_t shift_amount) {
   constexpr size_t MANT_INT_SIZE = sizeof(MantissaInt) * 8;
   cpp::UInt<MID_INT_SIZE + MANT_INT_SIZE> val(large);
   // TODO: Find a better way to force __uint128_t to be UInt<128>
   cpp::UInt<MANT_INT_SIZE> wide_mant(0);
-  wide_mant[0] = mantissa & (uint64_t(-1));
-  wide_mant[1] = mantissa >> 64;
+  wide_mant[0] = static_cast<size_t>(mantissa & (uint64_t(-1)));
+  wide_mant[1] = static_cast<size_t>(mantissa >> 64);
   val = (val * wide_mant) >> shift_amount;
 
   return val.div_uint32_times_pow_2(1000000000, 0).value()[0];
   // return fast_uint_mod_1e9(val);
 }
 
 } // namespace internal
 

libc/src/__support/integer_to_string.h

public:
   template <typename T, cpp::enable_if_t<cpp::is_integral_v<T> &&
                                              (sizeof(T) <= sizeof(uintmax_t)),
                                          int> = 0>
   LIBC_INLINE static cpp::optional<cpp::string_view>
   hex(T val, cpp::span<char> buffer, bool lowercase = true) {
     return convert<16>(val, buffer, lowercase);
   }
 
-  template <typename T,
-            cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T> &&
+  template <typename T, cpp::enable_if_t<cpp::is_integral_v<T> &&
                                              (sizeof(T) > sizeof(uintmax_t)) &&
                                              sizeof(T) % sizeof(uintmax_t) == 0,
                                          int> = 0>
   LIBC_INLINE static cpp::optional<cpp::string_view>
   hex(T val, cpp::span<char> buffer, bool lowercase = true) {
     // We will assume the buffer is exactly sized, which will be the case if
     // it was sized using the bufsize method.
     constexpr size_t BLOCKS = sizeof(T) / sizeof(uintmax_t);
     constexpr size_t UINTMAX_BUFSIZE = bufsize<16, uintmax_t>();
     // We will zero out the buffer. This specialization is not used to
     // implement a public function so zeroing out byte-by-byte does not

libc/src/__support/str_to_float.h

 //===-- String to float conversion utils ------------------------*- 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 LIBC_SRC_SUPPORT_STR_TO_FLOAT_H
 #define LIBC_SRC_SUPPORT_STR_TO_FLOAT_H
 
 #include "src/__support/CPP/limits.h"
 #include "src/__support/CPP/optional.h"
 #include "src/__support/FPUtil/FEnvImpl.h"
 #include "src/__support/FPUtil/FPBits.h"
+#include "src/__support/FPUtil/dyadic_float.h"
 #include "src/__support/FPUtil/rounding_mode.h"
 #include "src/__support/UInt128.h"
 #include "src/__support/builtin_wrappers.h"
 #include "src/__support/common.h"
 #include "src/__support/ctype_utils.h"
 #include "src/__support/detailed_powers_of_ten.h"
 #include "src/__support/high_precision_decimal.h"
 #include "src/__support/str_to_integer.h"
constexpr UInt128 HALFWAY_CONSTANT =
       1;
 
   if ((final_approx_upper & HALFWAY_CONSTANT) == HALFWAY_CONSTANT &&
       final_approx_lower + mantissa < mantissa) {
     return cpp::nullopt;
   }
 
   // Shifting to 65 bits for 80 bit floats and 113 bits for 128 bit floats
-  BitsType msb = final_approx_upper >> (BITS_IN_MANTISSA - 1);
+  uint32_t msb =
+      static_cast<uint32_t>(final_approx_upper >> (BITS_IN_MANTISSA - 1));
   BitsType final_mantissa =
       final_approx_upper >>
       (msb + BITS_IN_MANTISSA -
        (fputil::FloatProperties<long double>::MANTISSA_WIDTH + 3));
   exp2 -= static_cast<uint32_t>(1 ^ msb); // same as !msb
 
   if (round == RoundDirection::Nearest) {
     // Half-way ambiguity
clinger_fast_path(ExpandedFloat<T> init_num,
   typename fputil::FPBits<T>::UIntType mantissa = init_num.mantissa;
   int32_t exp10 = init_num.exponent;
 
   if (mantissa >> fputil::FloatProperties<T>::MANTISSA_WIDTH > 0) {
     return cpp::nullopt;
   }
 
   fputil::FPBits<T> result;
-  T float_mantissa = static_cast<T>(mantissa);
+  T float_mantissa;
+  if constexpr (cpp::is_same_v<typename fputil::FPBits<T>::UIntType,
+                               cpp::UInt<128>>) {
+    float_mantissa = static_cast<T>(fputil::DyadicFloat<128>(
+        false, 0,
+        fputil::DyadicFloat<128>::MantissaType(
+            {uint64_t(mantissa), uint64_t(mantissa >> 64)})));
+  } else {
+    float_mantissa = static_cast<T>(mantissa);
+  }
 
   if (exp10 == 0) {
     result = fputil::FPBits<T>(float_mantissa);
   }
   if (exp10 > 0) {
     if (exp10 > ClingerConsts<T>::EXACT_POWERS_OF_TEN +
                     ClingerConsts<T>::DIGITS_IN_MANTISSA) {
       return cpp::nullopt;
if (amount_to_shift_right > NUMBITS) {
       output.num = {0, 0};
       output.error = ERANGE;
       return output;
     }
   }
 
   BitsType round_bit_mask = BitsType(1) << (amount_to_shift_right - 1);
   BitsType sticky_mask = round_bit_mask - 1;
-  bool round_bit = mantissa & round_bit_mask;
+  bool round_bit = static_cast<bool>(mantissa & round_bit_mask);
   bool sticky_bit = static_cast<bool>(mantissa & sticky_mask) || truncated;
 
   if (amount_to_shift_right < NUMBITS) {
     // Shift the mantissa and clear the implicit bit.
     mantissa >>= amount_to_shift_right;
     mantissa &= fputil::FloatProperties<T>::MANTISSA_MASK;
   } else {
     mantissa = 0;
   }
-  bool least_significant_bit = mantissa & BitsType(1);
+  bool least_significant_bit = static_cast<bool>(mantissa & BitsType(1));
 
   // TODO: check that this rounding behavior is correct.
 
   if (round == RoundDirection::Nearest) {
     // Perform rounding-to-nearest, tie-to-even.
     if (round_bit && (least_significant_bit || sticky_bit)) {
       ++mantissa;
     }

libc/src/math/generic/CMakeLists.txt

 )
 
 add_header_library(
   log_range_reduction
   HDRS
     log_range_reduction.h
   DEPENDS
     .common_constants
+    libc.src.__support.uint128
     libc.src.__support.FPUtil.dyadic_float
 )
 
 add_entrypoint_object(
   log10
   SRCS
     log10.cpp
   HDRS

libc/src/math/generic/log_range_reduction.h

 //===-- Extra range reduction steps for accurate pass of logarithms -------===//
 //
 // 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_MATH_GENERIC_LOG_RANGE_REDUCTION_H
 #define LLVM_LIBC_SRC_MATH_GENERIC_LOG_RANGE_REDUCTION_H
 
 #include "common_constants.h"
 #include "src/__support/FPUtil/dyadic_float.h"
+#include "src/__support/UInt128.h"
 
 namespace __llvm_libc {
 
 // Struct to store -log*(r) for 4 range reduction steps.
 struct LogRR {
   fputil::DyadicFloat<128> step_1[128];
   fputil::DyadicFloat<128> step_2[193];
   fputil::DyadicFloat<128> step_3[161];
log_range_reduction(double m_x, const LogRR &log_table,
   // Output range: vv3 in [-0x1.01928p-22 , 0x1p-22]
   // idx3 = trunc(2^21 * (v + 80*2^-21 + 2^-22))
   size_t idx3 = static_cast<size_t>((vv2 + 0x2840'0000'0000'0000) >> 55);
   sum = fputil::quick_add(sum, log_table.step_3[idx3]);
 
   int64_t s3 = static_cast<int64_t>(S3[idx3]); // |s| < 2^-13, ulp = 2^-21
   int64_t spv3 = (s3 << 55) + vv2;             // |s + v| < 2^-21, ulp = 2^-76
   // |s*v| < 2^-27, ulp = 2^(-76-21) = 2^-97
-  __int128_t sv3 = static_cast<__int128_t>(s3) * static_cast<__int128_t>(vv2);
+  Int128 sv3 = static_cast<Int128>(s3) * static_cast<Int128>(vv2);
   // |vv3| < 2^-21, ulp = 2^-97
-  __int128_t vv3 = (static_cast<__int128_t>(spv3) << 21) + sv3;
+  Int128 vv3 = (static_cast<Int128>(spv3) << 21) + sv3;
 
   // Range reduction - Step 4
   // Output range: vv4 in [-0x1.0002143p-29 , 0x1p-29]
   // idx4 = trunc(2^21 * (v + 65*2^-28 + 2^-29))
   size_t idx4 = static_cast<size_t>((static_cast<int>(vv3 >> 68) + 131) >> 1);
 
   sum = fputil::quick_add(sum, log_table.step_4[idx4]);
 
-  __int128_t s4 = static_cast<__int128_t>(S4[idx4]); // |s| < 2^-21, ulp = 2^-28
+  Int128 s4 = static_cast<Int128>(S4[idx4]); // |s| < 2^-21, ulp = 2^-28
   // |s + v| < 2^-28, ulp = 2^-97
-  __int128_t spv4 = (s4 << 69) + vv3;
+  Int128 spv4 = (s4 << 69) + vv3;
   // |s*v| < 2^-42, ulp = 2^(-97-28) = 2^-125
-  __int128_t sv4 = s4 * vv3;
+  Int128 sv4 = s4 * vv3;
   // |vv4| < 2^-28, ulp = 2^-125
-  __int128_t vv4 = (spv4 << 28) + sv4;
+  Int128 vv4 = (spv4 << 28) + sv4;
 
   return (vv4 < 0) ? Float128(true, -125,
                               MType({static_cast<uint64_t>(-vv4),
                                      static_cast<uint64_t>((-vv4) >> 64)}))
                    : Float128(false, -125,
                               MType({static_cast<uint64_t>(vv4),
                                      static_cast<uint64_t>(vv4 >> 64)}));
 }
 
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_MATH_GENERIC_LOG_RANGE_REDUCTION_H

libc/src/stdio/printf_core/char_converter.h

 #include "src/stdio/printf_core/converter_utils.h"
 #include "src/stdio/printf_core/core_structs.h"
 #include "src/stdio/printf_core/writer.h"
 
 namespace __llvm_libc {
 namespace printf_core {
 
 LIBC_INLINE int convert_char(Writer *writer, const FormatSection &to_conv) {
-  char c = to_conv.conv_val_raw;
+  char c = static_cast<char>(to_conv.conv_val_raw);
 
   constexpr int string_len = 1;
 
   size_t padding_spaces =
       to_conv.min_width > string_len ? to_conv.min_width - string_len : 0;
 
   // If the padding is on the left side, write the spaces first.
   if (padding_spaces > 0 &&

libc/src/stdio/printf_core/float_dec_converter.h

 #include <stddef.h>
 
 namespace __llvm_libc {
 namespace printf_core {
 
 using MantissaInt = fputil::FPBits<long double>::UIntType;
 
 // Returns true if value is divisible by 2^p.
-LIBC_INLINE constexpr bool multiple_of_power_of_2(const uint64_t value,
-                                                  const uint32_t p) {
-  return (value & ((uint64_t(1) << p) - 1)) == 0;
+template <typename T>
+LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_integral_v<T>, bool>
+multiple_of_power_of_2(T value, uint32_t p) {
+  return (value & ((T(1) << p) - 1)) == 0;
 }
 
 constexpr size_t BLOCK_SIZE = 9;
 constexpr uint32_t MAX_BLOCK = 999999999;
 
 // constexpr size_t BLOCK_SIZE = 18;
 // constexpr uint32_t MAX_BLOCK = 999999999999999999;
 constexpr char DECIMAL_POINT = '.';
LIBC_INLINE int convert_float_decimal(Writer *writer,
   if (to_conv.length_modifier == LengthModifier::L) {
     fputil::FPBits<long double>::UIntType float_raw = to_conv.conv_val_raw;
     fputil::FPBits<long double> float_bits(float_raw);
     if (!float_bits.is_inf_or_nan()) {
       return convert_float_decimal_typed<long double>(writer, to_conv,
                                                       float_bits);
     }
   } else {
-    fputil::FPBits<double>::UIntType float_raw = to_conv.conv_val_raw;
+    fputil::FPBits<double>::UIntType float_raw =
+        static_cast<fputil::FPBits<double>::UIntType>(to_conv.conv_val_raw);
     fputil::FPBits<double> float_bits(float_raw);
     if (!float_bits.is_inf_or_nan()) {
       return convert_float_decimal_typed<double>(writer, to_conv, float_bits);
     }
   }
 
   return convert_inf_nan(writer, to_conv);
 }
 
 LIBC_INLINE int convert_float_dec_exp(Writer *writer,
                                       const FormatSection &to_conv) {
   if (to_conv.length_modifier == LengthModifier::L) {
     fputil::FPBits<long double>::UIntType float_raw = to_conv.conv_val_raw;
     fputil::FPBits<long double> float_bits(float_raw);
     if (!float_bits.is_inf_or_nan()) {
       return convert_float_dec_exp_typed<long double>(writer, to_conv,
                                                       float_bits);
     }
   } else {
-    fputil::FPBits<double>::UIntType float_raw = to_conv.conv_val_raw;
+    fputil::FPBits<double>::UIntType float_raw =
+        static_cast<fputil::FPBits<double>::UIntType>(to_conv.conv_val_raw);
     fputil::FPBits<double> float_bits(float_raw);
     if (!float_bits.is_inf_or_nan()) {
       return convert_float_dec_exp_typed<double>(writer, to_conv, float_bits);
     }
   }
 
   return convert_inf_nan(writer, to_conv);
 }
 
 LIBC_INLINE int convert_float_dec_auto(Writer *writer,
                                        const FormatSection &to_conv) {
   if (to_conv.length_modifier == LengthModifier::L) {
     fputil::FPBits<long double>::UIntType float_raw = to_conv.conv_val_raw;
     fputil::FPBits<long double> float_bits(float_raw);
     if (!float_bits.is_inf_or_nan()) {
       return convert_float_dec_auto_typed<long double>(writer, to_conv,
                                                        float_bits);
     }
   } else {
-    fputil::FPBits<double>::UIntType float_raw = to_conv.conv_val_raw;
+    fputil::FPBits<double>::UIntType float_raw =
+        static_cast<fputil::FPBits<double>::UIntType>(to_conv.conv_val_raw);
     fputil::FPBits<double> float_bits(float_raw);
     if (!float_bits.is_inf_or_nan()) {
       return convert_float_dec_auto_typed<double>(writer, to_conv, float_bits);
     }
   }
 
   return convert_inf_nan(writer, to_conv);
 }
 
 } // namespace printf_core
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FLOAT_DEC_CONVERTER_H

libc/src/stdio/printf_core/float_hex_converter.h

if (to_conv.length_modifier == LengthModifier::L) {
     fputil::FPBits<long double> float_bits(float_raw);
     is_negative = float_bits.get_sign();
     exponent = float_bits.get_exponent();
     mantissa = float_bits.get_explicit_mantissa();
     is_inf_or_nan = float_bits.is_inf_or_nan();
   } else {
     mantissa_width = fputil::MantissaWidth<double>::VALUE;
     exponent_bias = fputil::FPBits<double>::EXPONENT_BIAS;
-    fputil::FPBits<double>::UIntType float_raw = to_conv.conv_val_raw;
+    fputil::FPBits<double>::UIntType float_raw =
+        static_cast<fputil::FPBits<double>::UIntType>(to_conv.conv_val_raw);
     fputil::FPBits<double> float_bits(float_raw);
     is_negative = float_bits.get_sign();
     exponent = float_bits.get_exponent();
     mantissa = float_bits.get_explicit_mantissa();
     is_inf_or_nan = float_bits.is_inf_or_nan();
   }
 
   if (is_inf_or_nan)
if (mantissa >= (MantissaInt(1) << (intended_digits * BITS_IN_HEX_DIGIT))) {
       exponent += BITS_IN_HEX_DIGIT;
     }
 
     mant_len = intended_digits;
   }
 
   size_t mant_cur = mant_len;
   size_t first_non_zero = 1;
-  for (; mant_cur > 0; --mant_cur, mantissa /= 16) {
-    char new_digit = ((mantissa % 16) > 9) ? ((mantissa % 16) - 10 + a)
-                                           : ((mantissa % 16) + '0');
+  for (; mant_cur > 0; --mant_cur, mantissa >>= 4) {
+    char mant_mod_16 = static_cast<char>(mantissa) & 15;
+    char new_digit =
+        (mant_mod_16 > 9) ? (mant_mod_16 - 10 + a) : (mant_mod_16 + '0');
     mant_buffer[mant_cur - 1] = new_digit;
     if (new_digit != '0' && first_non_zero < mant_cur)
       first_non_zero = mant_cur;
   }
 
   size_t mant_digits = first_non_zero;
   if (to_conv.precision >= 0)
     mant_digits = mant_len;

libc/src/stdio/printf_core/float_inf_nan_converter.h

LIBC_INLINE int convert_inf_nan(Writer *writer, const FormatSection &to_conv) {
   bool is_negative;
   MantissaInt mantissa;
   if (to_conv.length_modifier == LengthModifier::L) {
     fputil::FPBits<long double>::UIntType float_raw = to_conv.conv_val_raw;
     fputil::FPBits<long double> float_bits(float_raw);
     is_negative = float_bits.get_sign();
     mantissa = float_bits.get_explicit_mantissa();
   } else {
-    fputil::FPBits<double>::UIntType float_raw = to_conv.conv_val_raw;
+    fputil::FPBits<double>::UIntType float_raw =
+        static_cast<fputil::FPBits<double>::UIntType>(to_conv.conv_val_raw);
     fputil::FPBits<double> float_bits(float_raw);
     is_negative = float_bits.get_sign();
     mantissa = float_bits.get_explicit_mantissa();
   }
 
   char sign_char = 0;
 
   if (is_negative)

libc/src/stdio/printf_core/int_converter.h

if (to_lower(conv_name) == 'x') {
     return IntegerToString::dec(num, bufref);
   }
 }
 
 LIBC_INLINE int convert_int(Writer *writer, const FormatSection &to_conv) {
   static constexpr size_t BITS_IN_BYTE = 8;
   static constexpr size_t BITS_IN_NUM = sizeof(uintmax_t) * BITS_IN_BYTE;
 
-  uintmax_t num = to_conv.conv_val_raw;
+  uintmax_t num = static_cast<uintmax_t>(to_conv.conv_val_raw);
   bool is_negative = false;
   FormatFlags flags = to_conv.flags;
 
   const char a = is_lower(to_conv.conv_name) ? 'a' : 'A';
 
   // If the conversion is signed, then handle negative values.
   if (to_conv.conv_name == 'd' || to_conv.conv_name == 'i') {
     // Check if the number is negative by checking the high bit. This works even

libc/test/UnitTest/LibcTest.cpp

 namespace internal {
 
 TestLogger &operator<<(TestLogger &logger, Location Loc) {
   return logger << Loc.file << ":" << Loc.line << ": FAILURE\n";
 }
 
 // When the value is UInt128, __uint128_t or wider, show its hexadecimal digits.
 template <typename T>
-cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T> &&
-                     (sizeof(T) > sizeof(uint64_t)),
+cpp::enable_if_t<cpp::is_integral_v<T> && (sizeof(T) > sizeof(uint64_t)),
                  cpp::string>
 describeValue(T Value) {
   static_assert(sizeof(T) % 8 == 0, "Unsupported size of UInt");
   char buf[IntegerToString::hex_bufsize<T>()];
   IntegerToString::hex(Value, buf, false);
   return "0x" + cpp::string(buf, sizeof(buf));
 }
 

 #ifdef __SIZEOF_INT128__
 // When builtin __uint128_t type is available, include its specialization
 // also.
 template bool test<__uint128_t>(RunContext *Ctx, TestCond Cond, __uint128_t LHS,
                                 __uint128_t RHS, const char *LHSStr,
                                 const char *RHSStr, Location Loc);
 #endif
 
+template bool test<__llvm_libc::cpp::Int<128>>(RunContext *Ctx, TestCond Cond,
+                                               __llvm_libc::cpp::Int<128> LHS,
+                                               __llvm_libc::cpp::Int<128> RHS,
+                                               const char *LHSStr,
+                                               const char *RHSStr,
+                                               Location Loc);
+
 template bool test<__llvm_libc::cpp::UInt<128>>(RunContext *Ctx, TestCond Cond,
                                                 __llvm_libc::cpp::UInt<128> LHS,
                                                 __llvm_libc::cpp::UInt<128> RHS,
                                                 const char *LHSStr,
                                                 const char *RHSStr,
                                                 Location Loc);
 
 template bool test<__llvm_libc::cpp::UInt<192>>(RunContext *Ctx, TestCond Cond,

libc/test/src/__support/uint_test.cpp

 // 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>;
 using LL_UInt320 = __llvm_libc::cpp::UInt<320>;
 using LL_UInt512 = __llvm_libc::cpp::UInt<512>;
 using LL_UInt1024 = __llvm_libc::cpp::UInt<1024>;
 
+using LL_Int128 = __llvm_libc::cpp::Int<128>;
+using LL_Int192 = __llvm_libc::cpp::Int<192>;
+
 TEST(LlvmLibcUIntClassTest, BasicInit) {
   LL_UInt128 empty;
   LL_UInt128 half_val(12345);
   LL_UInt128 full_val({12345, 67890});
   ASSERT_TRUE(half_val != full_val);
 }
 
 TEST(LlvmLibcUIntClassTest, AdditionTests) {
TEST(LlvmLibcUIntClassTest, DivUInt32TimesPow2Tests) {
   }
 
   TEST_QUICK_DIV_UINT32_POW2(1, 75);
   TEST_QUICK_DIV_UINT32_POW2(1, 101);
 
   TEST_QUICK_DIV_UINT32_POW2(1000000000, 75);
   TEST_QUICK_DIV_UINT32_POW2(1000000000, 101);
 }
+
+TEST(LlvmLibcUIntClassTest, ComparisonInt128Tests) {
+  LL_Int128 a(123);
+  LL_Int128 b(0);
+  LL_Int128 c(-1);
+
+  ASSERT_TRUE(a == a);
+  ASSERT_TRUE(b == b);
+  ASSERT_TRUE(c == c);
+
+  ASSERT_TRUE(a != b);
+  ASSERT_TRUE(a != c);
+  ASSERT_TRUE(b != a);
+  ASSERT_TRUE(b != c);
+  ASSERT_TRUE(c != a);
+  ASSERT_TRUE(c != b);
+
+  ASSERT_TRUE(a > b);
+  ASSERT_TRUE(a >= b);
+  ASSERT_TRUE(a > c);
+  ASSERT_TRUE(a >= c);
+  ASSERT_TRUE(b > c);
+  ASSERT_TRUE(b >= c);
+
+  ASSERT_TRUE(b < a);
+  ASSERT_TRUE(b <= a);
+  ASSERT_TRUE(c < a);
+  ASSERT_TRUE(c <= a);
+  ASSERT_TRUE(c < b);
+  ASSERT_TRUE(c <= b);
+}
+
+TEST(LlvmLibcUIntClassTest, BasicArithmeticInt128Tests) {
+  LL_Int128 a(123);
+  LL_Int128 b(0);
+  LL_Int128 c(-3);
+
+  ASSERT_EQ(a * a, LL_Int128(123 * 123));
+  ASSERT_EQ(a * c, LL_Int128(-369));
+  ASSERT_EQ(c * a, LL_Int128(-369));
+  ASSERT_EQ(c * c, LL_Int128(9));
+  ASSERT_EQ(a * b, b);
+  ASSERT_EQ(b * a, b);
+  ASSERT_EQ(b * c, b);
+  ASSERT_EQ(c * b, b);
+}
+
+#ifdef __SIZEOF_INT128__
+
+TEST(LlvmLibcUIntClassTest, ConstructorFromUInt128Tests) {
+  __uint128_t a = (__uint128_t(123) << 64) + 1;
+  __int128_t b = -static_cast<__int128_t>(a);
+  LL_Int128 c(a);
+  LL_Int128 d(b);
+
+  LL_Int192 e(a);
+  LL_Int192 f(b);
+
+  ASSERT_EQ(static_cast<int>(c), 1);
+  ASSERT_EQ(static_cast<int>(c >> 64), 123);
+  ASSERT_EQ(static_cast<uint64_t>(d), static_cast<uint64_t>(b));
+  ASSERT_EQ(static_cast<uint64_t>(d >> 64), static_cast<uint64_t>(b >> 64));
+  ASSERT_EQ(c + d, LL_Int128(a + b));
+
+  ASSERT_EQ(static_cast<int>(e), 1);
+  ASSERT_EQ(static_cast<int>(e >> 64), 123);
+  ASSERT_EQ(static_cast<uint64_t>(f), static_cast<uint64_t>(b));
+  ASSERT_EQ(static_cast<uint64_t>(f >> 64), static_cast<uint64_t>(b >> 64));
+  ASSERT_EQ(LL_UInt192(e + f), LL_UInt192(a + b));
+}
+
+#endif // __SIZEOF_INT128__

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

deps = [
         ":__support_builtin_wrappers",
         ":__support_common",
         ":__support_cpp_limits",
         ":__support_cpp_optional",
         ":__support_ctype_utils",
         ":__support_fputil_fenv_impl",
         ":__support_fputil_fp_bits",
         ":__support_fputil_rounding_mode",
+        ":__support_fputil_dyadic_float",
         ":__support_str_to_integer",
         ":__support_str_to_num_result",
         ":__support_uint128",
         ":errno",
     ],
 )
 
 libc_support_library(
libc_support_library(
     ],
 )
 
 libc_support_library(
     name = "log_range_reduction",
     hdrs = ["src/math/generic/log_range_reduction.h"],
     deps = [
         ":__support_common",
+        ":__support_uint128",
         ":__support_fputil_dyadic_float",
         ":common_constants",
     ],
 )
 
 libc_math_function(
     name = "expm1f",
     additional_deps = [