[libc] add uint128 implementation

[michaelrj]

Summary

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

[michaelrj]

remove some pieces of code left over from initial testing.

[lntue]

libc/src/__support/UInt128.h

42

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

81

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

88

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

libc/test/src/__support/uint128_test.cpp

14

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

[michaelrj]

make every UInt128 function constexpr and const.

libc/src/__support/UInt128.h

88

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

libc/test/src/__support/uint128_test.cpp

14

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

[sivachandra]

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

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

[michaelrj]

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

[sivachandra]

In D124959#3497759, @michaelrj wrote:

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

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

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

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

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

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

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

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

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

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

[michaelrj]

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

[lntue]

libc/src/__support/CMakeLists.txt

63

Is this still needed?

libc/src/__support/FPUtil/UInt.h

20 ↗

(On Diff #428444)

Add suffix -u/-U to the constant.

20 ↗

(On Diff #428444)

can this be all caps MASK32?

40 ↗

(On Diff #428444)

Move this out of the class.

52 ↗

(On Diff #428444)

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

60 ↗

(On Diff #428444)

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

91 ↗

(On Diff #428444)

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

93 ↗

(On Diff #428444)

Remove this if it's not needed.

199 ↗

(On Diff #428444)

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

[sivachandra]

libc/src/__support/FPUtil/UInt.h

20 ↗

(On Diff #428444)

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

40 ↗

(On Diff #428444)

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

libc/test/src/__support/uint128_test.cpp

14

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

[michaelrj]

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

[michaelrj]

libc/src/__support/FPUtil/UInt.h

60 ↗

(On Diff #428444)

No, it throws errors in the tests.

libc/test/src/__support/uint128_test.cpp

14

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

libc/src/__support/CMakeLists.txt

 )
 
 add_header_library(
   arg_list
   HDRS
     arg_list.h
 )
 
+add_header_library(
+  uint128
+  HDRS
+    UInt128.h
+)
+
 # Thread support is used by other support libraries. So, we add the "threads"
 # before other directories.
 add_subdirectory(threads)
 
 add_subdirectory(File)
 add_subdirectory(FPUtil)
 add_subdirectory(OSUtil)

libc/src/__support/UInt128.h

+//===-- 128 bit integer implementation --------------------------*- 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 <inttypes.h>
+#include <stddef.h>
+
+namespace __llvm_libc {
+namespace internal {
+static constexpr inline uint64_t low32(uint64_t num) {
+  return num & 0xffffffff;
+}
+
+static constexpr inline uint64_t high32(uint64_t num) { return num >> 32; }
+
+static constexpr size_t BITS_IN_UINT64 = sizeof(uint64_t) * 8;
+
+// This is an implementation of a 128 bit integer using only 64 bit integers.
+// It's intended to be used when the compiler doesn't support 128 bit integers.
+class UInt128 {
+  uint64_t high = 0;
+  uint64_t low = 0;
+
+public:
+  constexpr UInt128(uint64_t other) : low(other) {}
+  constexpr UInt128(uint64_t new_high, uint64_t new_low)
+      : high(new_high), low(new_low) {}
+  constexpr UInt128() {}
+
+  constexpr uint64_t get_high() const { return high; }
+
+  constexpr uint64_t get_low() const { return low; }
+
+  constexpr operator uint64_t() { return low; }
+  constexpr operator uint32_t() { return low32(low); }
+
+  constexpr UInt128 operator+(const UInt128 &other) const {
+    uint64_t new_low = low + other.get_low();
+    uint64_t new_high =
+        high + other.get_high() + (new_low < low ? 1 : 0); // handle overflow
+    return UInt128(new_high, new_low);
+  }
+
+  constexpr UInt128 operator*(const UInt128 &other) const {
+    // temp low covers bits 0-63, middle covers 32-95, high covers 64-127, and
+    // high overflow covers 96-159.
+    uint64_t temp_low = low32(low) * low32(other.get_low());
+    uint64_t temp_middle_1 = low32(low) * high32(other.get_low());
+    uint64_t temp_middle_2 = high32(low) * low32(other.get_low());
+
+    // temp_middle is split out so that overflows can be handled, but since
+    // but since the result will be truncated to 128 bits any overflow from here
+    // on doesn't matter.
+    uint64_t temp_high = low32(low) * low32(other.get_high()) +
+                         high32(low) * high32(other.get_low()) +
+                         low32(high) * low32(other.get_low());
+
+    uint64_t temp_high_overflow = low32(low) * high32(other.get_high()) +
+                                  high32(low) * low32(other.get_high()) +
+                                  low32(high) * high32(other.get_low()) +
+                                  high32(high) * low32(other.get_low());
+
+    // temp_low_middle has just the high 32 bits of low, as well as any
+    // overflow.
+    uint64_t temp_low_middle =
+        high32(temp_low) + low32(temp_middle_1) + low32(temp_middle_2);
+
+    uint64_t new_low = low32(temp_low) + (low32(temp_low_middle) << 32);
+    uint64_t new_high = high32(temp_low_middle) + high32(temp_middle_1) +
+                        high32(temp_middle_2) + temp_high +
+                        (low32(temp_high_overflow) << 32);
+    return UInt128(new_high, new_low);
+  }
+
+  constexpr UInt128 operator<<(int amount) const {
+    if (amount < 64) {
+      uint64_t new_low = low << amount;
+      uint64_t new_high = (high << amount) | (low >> (BITS_IN_UINT64 - amount));
+      return UInt128(new_high, new_low);
+    } else if (amount < 128) {
+      uint64_t new_high = low << (amount - BITS_IN_UINT64);
+      return UInt128(new_high, 0);
+    } else {
+      return UInt128(0);
+    }
+  }
+
+  constexpr UInt128 operator>>(int amount) const {
+    if (amount < 64) {
+      uint64_t new_low = (low >> amount) | (high << (BITS_IN_UINT64 - amount));
+      uint64_t new_high = (high >> amount);
+      return UInt128(new_high, new_low);
+    } else if (amount < 128) {
+      uint64_t new_low = high >> (amount - BITS_IN_UINT64);
+      return UInt128(0, new_low);
+    } else {
+      return UInt128(0);
+    }
+  }
+
+  constexpr UInt128 operator&(UInt128 other) const {
+    uint64_t new_low = low & other.get_low();
+    uint64_t new_high = high & other.get_high();
+    return UInt128(new_high, new_low);
+  }
+
+  // this feels like it can be done with templates, but when I try it says
+  // "Explicit Specialization is not allowed in the current scope"
+  constexpr UInt128 operator&(unsigned long long other) const {
+    uint64_t new_low = low & other;
+    return UInt128(new_low);
+  }
+
+  constexpr UInt128 operator&(long long other) const {
+    uint64_t new_low = low & static_cast<unsigned long long>(other);
+    return UInt128(new_low);
+  }
+
+  constexpr UInt128 operator&(unsigned long other) const {
+    uint64_t new_low = low & other;
+    return UInt128(new_low);
+  }
+
+  constexpr UInt128 operator&(long other) const {
+    uint64_t new_low = low & static_cast<unsigned long>(other);
+    return UInt128(new_low);
+  }
+
+  constexpr UInt128 operator&(unsigned int other) const {
+    uint64_t new_low = low & other;
+    return UInt128(new_low);
+  }
+
+  constexpr UInt128 operator&(int other) const {
+    uint64_t new_low = low & static_cast<unsigned int>(other);
+    return UInt128(new_low);
+  }
+
+  constexpr UInt128 operator|(UInt128 other) const {
+    uint64_t new_low = low | other.get_low();
+    uint64_t new_high = high | other.get_high();
+    return UInt128(new_high, new_low);
+  }
+
+  constexpr UInt128 operator|(unsigned long long other) const {
+    uint64_t new_low = low | other;
+    return UInt128(high, new_low);
+  }
+
+  constexpr UInt128 operator|(long long other) const {
+    uint64_t new_low = low | static_cast<unsigned long long>(other);
+    return UInt128(high, new_low);
+  }
+
+  constexpr UInt128 operator|(unsigned long other) const {
+    uint64_t new_low = low | other;
+    return UInt128(high, new_low);
+  }
+
+  constexpr UInt128 operator|(long other) const {
+    uint64_t new_low = low | static_cast<unsigned long>(other);
+    return UInt128(high, new_low);
+  }
+
+  constexpr UInt128 operator|(unsigned int other) const {
+    uint64_t new_low = low | other;
+    return UInt128(high, new_low);
+  }
+
+  constexpr UInt128 operator|(int other) const {
+    uint64_t new_low = low | static_cast<unsigned int>(other);
+    return UInt128(high, new_low);
+  }
+
+  bool operator==(UInt128 other) const {
+    return (low == other.get_low()) && (high == other.get_high());
+  }
+};
+} // namespace internal
+} // namespace __llvm_libc
+
+#if !defined(__SIZEOF_INT128__)
+using __uint128_t = __llvm_libc::internal::UInt128;
+#endif // uint128 is not defined, define it with this class.
+
+#endif // LLVM_LIBC_SRC_SUPPORT_UINT128_H

libc/test/src/__support/CMakeLists.txt

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

libc/test/src/__support/uint128_test.cpp

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