diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt --- a/libc/src/__support/CMakeLists.txt +++ b/libc/src/__support/CMakeLists.txt @@ -60,6 +60,12 @@ 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) diff --git a/libc/src/__support/UInt128.h b/libc/src/__support/UInt128.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/UInt128.h @@ -0,0 +1,193 @@ +//===-- 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 +#include + +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(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(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(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(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(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(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 diff --git a/libc/test/src/__support/CMakeLists.txt b/libc/test/src/__support/CMakeLists.txt --- a/libc/test/src/__support/CMakeLists.txt +++ b/libc/test/src/__support/CMakeLists.txt @@ -40,6 +40,16 @@ 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 diff --git a/libc/test/src/__support/uint128_test.cpp b/libc/test/src/__support/uint128_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/__support/uint128_test.cpp @@ -0,0 +1,184 @@ +//===-- 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); +}