From 1170951c737773e22b686cac195e0d13b2441374 Mon Sep 17 00:00:00 2001 From: Michael Jones Date: Tue, 3 May 2022 09:55:00 -0700 Subject: [PATCH] [libc] add uint128 implementation 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. Reviewed By: sivachandra, lntue Differential Revision: https://reviews.llvm.org/D124959 --- libc/src/__support/CPP/CMakeLists.txt | 10 +- libc/src/__support/CPP/TypeTraits.h | 5 +- libc/src/__support/CPP/UInt.h | 334 +++++++++++++++++++++++++++++++ libc/src/__support/FPUtil/CMakeLists.txt | 10 +- libc/src/__support/FPUtil/UInt.h | 236 ---------------------- libc/src/__support/FPUtil/XFloat.h | 2 +- libc/src/math/generic/CMakeLists.txt | 4 +- libc/test/src/__support/CMakeLists.txt | 10 + libc/test/src/__support/uint128_test.cpp | 163 +++++++++++++++ libc/utils/UnitTest/LibcTest.cpp | 20 +- 10 files changed, 551 insertions(+), 243 deletions(-) create mode 100644 libc/src/__support/CPP/UInt.h delete mode 100644 libc/src/__support/FPUtil/UInt.h create mode 100644 libc/test/src/__support/uint128_test.cpp diff --git a/libc/src/__support/CPP/CMakeLists.txt b/libc/src/__support/CPP/CMakeLists.txt index 75b7740..294a46b 100644 --- a/libc/src/__support/CPP/CMakeLists.txt +++ b/libc/src/__support/CPP/CMakeLists.txt @@ -10,14 +10,12 @@ add_header_library( ArrayRef.h ) - add_header_library( bit HDRS Bit.h ) - add_header_library( bitset HDRS @@ -79,3 +77,11 @@ add_header_library( HDRS error.h ) + +add_header_library( + uint + HDRS + UInt.h + DEPENDS + libc.src.__support.CPP.array +) diff --git a/libc/src/__support/CPP/TypeTraits.h b/libc/src/__support/CPP/TypeTraits.h index b07e25f..f37447f 100644 --- a/libc/src/__support/CPP/TypeTraits.h +++ b/libc/src/__support/CPP/TypeTraits.h @@ -9,6 +9,8 @@ #ifndef LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H #define LLVM_LIBC_SRC_SUPPORT_CPP_TYPETRAITS_H +#include "UInt.h" + namespace __llvm_libc { namespace cpp { @@ -49,7 +51,8 @@ template struct IsIntegral { IsSameV || IsSameV || IsSameV || IsSameV || IsSameV || IsSameV || - IsSameV || IsSameV + IsSameV || IsSameV || + IsSameV, TypeNoCV> #ifdef __SIZEOF_INT128__ || IsSameV<__uint128_t, TypeNoCV> || IsSameV<__int128_t, TypeNoCV> #endif diff --git a/libc/src/__support/CPP/UInt.h b/libc/src/__support/CPP/UInt.h new file mode 100644 index 0000000..e61392a --- /dev/null +++ b/libc/src/__support/CPP/UInt.h @@ -0,0 +1,334 @@ +//===-- A class to manipulate wide integers. --------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIBC_UTILS_CPP_UINT_H +#define LLVM_LIBC_UTILS_CPP_UINT_H + +#include "src/__support/CPP/Array.h" + +#include // For size_t +#include + +namespace __llvm_libc { +namespace cpp { + +template class UInt { + + static_assert(Bits > 0 && Bits % 64 == 0, + "Number of bits in UInt should be a multiple of 64."); + static constexpr size_t WordCount = Bits / 64; + uint64_t val[WordCount]; + + static constexpr uint64_t MASK32 = 0xFFFFFFFFu; + + static constexpr uint64_t low(uint64_t v) { return v & MASK32; } + static constexpr uint64_t high(uint64_t v) { return (v >> 32) & MASK32; } + +public: + constexpr UInt() {} + + constexpr UInt(const UInt &other) { + for (size_t i = 0; i < WordCount; ++i) + val[i] = other.val[i]; + } + + // Initialize the first word to |v| and the rest to 0. + constexpr UInt(uint64_t v) { + val[0] = v; + for (size_t i = 1; i < WordCount; ++i) { + val[i] = 0; + } + } + constexpr explicit UInt(const cpp::Array &words) { + for (size_t i = 0; i < WordCount; ++i) + val[i] = words[i]; + } + + constexpr explicit operator uint64_t() const { return val[0]; } + + constexpr explicit operator uint32_t() const { + return uint32_t(uint64_t(*this)); + } + + constexpr explicit operator uint8_t() const { + return uint8_t(uint64_t(*this)); + } + + UInt &operator=(const UInt &other) { + for (size_t i = 0; i < WordCount; ++i) + val[i] = other.val[i]; + return *this; + } + + // Add x to this number and store the result in this number. + // Returns the carry value produced by the addition operation. + constexpr uint64_t add(const UInt &x) { + uint64_t carry = 0; + for (size_t i = 0; i < WordCount; ++i) { + uint64_t res_lo = low(val[i]) + low(x.val[i]) + carry; + carry = high(res_lo); + res_lo = low(res_lo); + + uint64_t res_hi = high(val[i]) + high(x.val[i]) + carry; + carry = high(res_hi); + res_hi = low(res_hi); + + val[i] = res_lo + (res_hi << 32); + } + return carry; + } + + constexpr UInt operator+(const UInt &other) const { + UInt result(*this); + result.add(other); + return result; + } + + // Multiply this number with x and store the result in this number. It is + // implemented using the long multiplication algorithm by splitting the + // 64-bit words of this number and |x| in to 32-bit halves but peforming + // the operations using 64-bit numbers. This ensures that we don't lose the + // carry bits. + // Returns the carry value produced by the multiplication operation. + constexpr uint64_t mul(uint64_t x) { + uint64_t x_lo = low(x); + uint64_t x_hi = high(x); + + cpp::Array row1; + uint64_t carry = 0; + for (size_t i = 0; i < WordCount; ++i) { + uint64_t l = low(val[i]); + uint64_t h = high(val[i]); + uint64_t p1 = x_lo * l; + uint64_t p2 = x_lo * h; + + uint64_t res_lo = low(p1) + carry; + carry = high(res_lo); + uint64_t res_hi = high(p1) + low(p2) + carry; + carry = high(res_hi) + high(p2); + + res_lo = low(res_lo); + res_hi = low(res_hi); + row1[i] = res_lo + (res_hi << 32); + } + row1[WordCount] = carry; + + cpp::Array row2; + row2[0] = 0; + carry = 0; + for (size_t i = 0; i < WordCount; ++i) { + uint64_t l = low(val[i]); + uint64_t h = high(val[i]); + uint64_t p1 = x_hi * l; + uint64_t p2 = x_hi * h; + + uint64_t res_lo = low(p1) + carry; + carry = high(res_lo); + uint64_t res_hi = high(p1) + low(p2) + carry; + carry = high(res_hi) + high(p2); + + res_lo = low(res_lo); + res_hi = low(res_hi); + row2[i] = res_lo + (res_hi << 32); + } + row2[WordCount] = carry; + + UInt<(WordCount + 1) * 64> r1(row1), r2(row2); + r2.shift_left(32); + r1.add(r2); + for (size_t i = 0; i < WordCount; ++i) { + val[i] = r1[i]; + } + return r1[WordCount]; + } + + constexpr UInt operator*(const UInt &other) const { + UInt result(0); + for (size_t i = 0; i < WordCount; ++i) { + UInt row_result(*this); + row_result.mul(other[i]); + row_result.shift_left(64 * i); + result = result + row_result; + } + return result; + } + + constexpr void shift_left(size_t s) { + const size_t drop = s / 64; // Number of words to drop + const size_t shift = s % 64; // Bits to shift in the remaining words. + const uint64_t mask = ((uint64_t(1) << shift) - 1) << (64 - shift); + + for (size_t i = WordCount; drop > 0 && i > 0; --i) { + if (i > drop) + val[i - 1] = val[i - drop - 1]; + else + val[i - 1] = 0; + } + for (size_t i = WordCount; shift > 0 && i > drop; --i) { + uint64_t drop_val = (val[i - 1] & mask) >> (64 - shift); + val[i - 1] <<= shift; + if (i < WordCount) + val[i] |= drop_val; + } + } + + constexpr UInt operator<<(size_t s) const { + UInt result(*this); + result.shift_left(s); + return result; + } + + constexpr void shift_right(size_t s) { + const size_t drop = s / 64; // Number of words to drop + const size_t shift = s % 64; // Bit shift in the remaining words. + const uint64_t mask = (uint64_t(1) << shift) - 1; + + for (size_t i = 0; drop > 0 && i < WordCount; ++i) { + if (i + drop < WordCount) + val[i] = val[i + drop]; + else + val[i] = 0; + } + for (size_t i = 0; shift > 0 && i < WordCount; ++i) { + uint64_t drop_val = ((val[i] & mask) << (64 - shift)); + val[i] >>= shift; + if (i > 0) + val[i - 1] |= drop_val; + } + } + + constexpr UInt operator>>(size_t s) const { + UInt result(*this); + result.shift_right(s); + return result; + } + + constexpr UInt operator&(const UInt &other) const { + UInt result; + for (size_t i = 0; i < WordCount; ++i) + result.val[i] = val[i] & other.val[i]; + return result; + } + + constexpr UInt operator|(const UInt &other) const { + UInt result; + for (size_t i = 0; i < WordCount; ++i) + result.val[i] = val[i] | other.val[i]; + return result; + } + + constexpr UInt operator^(const UInt &other) const { + UInt result; + for (size_t i = 0; i < WordCount; ++i) + result.val[i] = val[i] ^ other.val[i]; + return result; + } + + constexpr bool operator==(const UInt &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 &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 &other) const { + for (size_t i = WordCount; i > 0; --i) { + if (val[i - 1] <= other.val[i - 1]) + return false; + } + return true; + } + + constexpr bool operator>=(const UInt &other) const { + for (size_t i = WordCount; i > 0; --i) { + if (val[i - 1] < other.val[i - 1]) + return false; + } + return true; + } + + constexpr bool operator<(const UInt &other) const { + for (size_t i = WordCount; i > 0; --i) { + if (val[i - 1] >= other.val[i - 1]) + return false; + } + return true; + } + + constexpr bool operator<=(const UInt &other) const { + for (size_t i = WordCount; i > 0; --i) { + if (val[i - 1] > other.val[i - 1]) + return false; + } + return true; + } + + // Return the i-th 64-bit word of the number. + const uint64_t &operator[](size_t i) const { return val[i]; } + + // Return the i-th 64-bit word of the number. + uint64_t &operator[](size_t i) { return val[i]; } + + uint64_t *data() { return val; } + + const uint64_t *data() const { return val; } +}; + +template <> +constexpr UInt<128> UInt<128>::operator*(const UInt<128> &other) const { + // temp low covers bits 0-63, middle covers 32-95, high covers 64-127, and + // high overflow covers 96-159. + uint64_t temp_low = low(val[0]) * low(other[0]); + uint64_t temp_middle_1 = low(val[0]) * high(other[0]); + uint64_t temp_middle_2 = high(val[0]) * low(other[0]); + + // temp_middle is split out so that overflows can be handled, but since + // but since the result will be truncated to 128 bits any overflow from here + // on doesn't matter. + uint64_t temp_high = low(val[0]) * low(other[1]) + + high(val[0]) * high(other[0]) + + low(val[1]) * low(other[0]); + + uint64_t temp_high_overflow = + low(val[0]) * high(other[1]) + high(val[0]) * low(other[1]) + + low(val[1]) * high(other[0]) + high(val[1]) * low(other[0]); + + // temp_low_middle has just the high 32 bits of low, as well as any + // overflow. + uint64_t temp_low_middle = + high(temp_low) + low(temp_middle_1) + low(temp_middle_2); + + uint64_t new_low = low(temp_low) + (low(temp_low_middle) << 32); + uint64_t new_high = high(temp_low_middle) + high(temp_middle_1) + + high(temp_middle_2) + temp_high + + (low(temp_high_overflow) << 32); + UInt<128> result(0); + result[0] = new_low; + result[1] = new_high; + return result; +} + +} // namespace cpp +} // namespace __llvm_libc + +/* TODO: determine the best way to support uint128 using this class. +#if !defined(__SIZEOF_INT128__) +using __uint128_t = __llvm_libc::internal::UInt<128>; +#endif // uint128 is not defined, define it with this class. +*/ + +#endif // LLVM_LIBC_UTILS_CPP_UINT_H diff --git a/libc/src/__support/FPUtil/CMakeLists.txt b/libc/src/__support/FPUtil/CMakeLists.txt index 7f1cecc..0bb3daa 100644 --- a/libc/src/__support/FPUtil/CMakeLists.txt +++ b/libc/src/__support/FPUtil/CMakeLists.txt @@ -13,7 +13,6 @@ add_header_library( NormalFloat.h PlatformDefs.h UInt.h - XFloat.h DEPENDS libc.include.math libc.include.errno @@ -25,6 +24,15 @@ add_header_library( ) add_header_library( + xfloat + HDRS + XFloat.h + DEPENDS + .fputil #FPBits and NormalFloat + libc.src.__support.CPP.uint +) + +add_header_library( sqrt HDRS sqrt.h diff --git a/libc/src/__support/FPUtil/UInt.h b/libc/src/__support/FPUtil/UInt.h deleted file mode 100644 index 9e3f029..0000000 --- a/libc/src/__support/FPUtil/UInt.h +++ /dev/null @@ -1,236 +0,0 @@ -//===-- A class to manipulate wide integers. --------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_LIBC_UTILS_FPUTIL_UINT_H -#define LLVM_LIBC_UTILS_FPUTIL_UINT_H - -#include // For size_t -#include - -namespace __llvm_libc { -namespace fputil { - -template class UInt { - - // This is mainly used for debugging. - enum Kind { - NotANumber, - Valid, - }; - - static_assert(Bits > 0 && Bits % 64 == 0, - "Number of bits in UInt should be a multiple of 64."); - static constexpr uint64_t Mask32 = 0xFFFFFFFF; - static constexpr size_t WordCount = Bits / 64; - static constexpr uint64_t InvalidHexDigit = 20; - uint64_t val[WordCount]; - Kind kind; - - uint64_t low(uint64_t v) { return v & Mask32; } - - uint64_t high(uint64_t v) { return (v >> 32) & Mask32; } - - uint64_t hexval(char c) { - uint64_t diff; - if ((diff = uint64_t(c) - 'A') < 6) - return diff + 10; - else if ((diff = uint64_t(c) - 'a') < 6) - return diff + 10; - else if ((diff = uint64_t(c) - '0') < 10) - return diff; - else - return InvalidHexDigit; - } - - size_t strlen(const char *s) { - size_t len; - for (len = 0; *s != '\0'; ++s, ++len) - ; - return len; - } - -public: - UInt() { kind = Valid; } - - UInt(const UInt &other) : kind(other.kind) { - if (kind == Valid) { - for (size_t i = 0; i < WordCount; ++i) - val[i] = other.val[i]; - } - } - - // This constructor is used for debugging. - explicit UInt(const char *s) { - size_t len = strlen(s); - if (len > Bits / 4 + 2 || len < 3) { - kind = NotANumber; - return; - } - - if (!(s[0] == '0' && s[1] == 'x')) { - kind = NotANumber; - return; - } - - for (size_t i = 0; i < WordCount; ++i) - val[i] = 0; - - for (size_t i = len - 1, w = 0; i >= 2; --i, w += 4) { - uint64_t hex = hexval(s[i]); - if (hex == InvalidHexDigit) { - kind = NotANumber; - return; - } - val[w / 64] |= (hex << (w % 64)); - } - - kind = Valid; - } - - explicit UInt(uint64_t v) { - val[0] = v; - for (size_t i = 1; i < WordCount; ++i) - val[i] = 0; - kind = Valid; - } - - explicit UInt(uint64_t data[WordCount]) { - for (size_t i = 0; i < WordCount; ++i) - val[i] = data[i]; - kind = Valid; - } - - bool is_valid() const { return kind == Valid; } - - // Add x to this number and store the result in this number. - // Returns the carry value produced by the addition operation. - uint64_t add(const UInt &x) { - uint64_t carry = 0; - for (size_t i = 0; i < WordCount; ++i) { - uint64_t res_lo = low(val[i]) + low(x.val[i]) + carry; - carry = high(res_lo); - res_lo = low(res_lo); - - uint64_t res_hi = high(val[i]) + high(x.val[i]) + carry; - carry = high(res_hi); - res_hi = low(res_hi); - - val[i] = res_lo + (res_hi << 32); - } - return carry; - } - - // Multiply this number with x and store the result in this number. It is - // implemented using the long multiplication algorithm by splitting the - // 64-bit words of this number and |x| in to 32-bit halves but peforming - // the operations using 64-bit numbers. This ensures that we don't lose the - // carry bits. - // Returns the carry value produced by the multiplication operation. - uint64_t mul(uint64_t x) { - uint64_t x_lo = low(x); - uint64_t x_hi = high(x); - - uint64_t row1[WordCount + 1]; - uint64_t carry = 0; - for (size_t i = 0; i < WordCount; ++i) { - uint64_t l = low(val[i]); - uint64_t h = high(val[i]); - uint64_t p1 = x_lo * l; - uint64_t p2 = x_lo * h; - - uint64_t res_lo = low(p1) + carry; - carry = high(res_lo); - uint64_t res_hi = high(p1) + low(p2) + carry; - carry = high(res_hi) + high(p2); - - res_lo = low(res_lo); - res_hi = low(res_hi); - row1[i] = res_lo + (res_hi << 32); - } - row1[WordCount] = carry; - - uint64_t row2[WordCount + 1]; - row2[0] = 0; - carry = 0; - for (size_t i = 0; i < WordCount; ++i) { - uint64_t l = low(val[i]); - uint64_t h = high(val[i]); - uint64_t p1 = x_hi * l; - uint64_t p2 = x_hi * h; - - uint64_t res_lo = low(p1) + carry; - carry = high(res_lo); - uint64_t res_hi = high(p1) + low(p2) + carry; - carry = high(res_hi) + high(p2); - - res_lo = low(res_lo); - res_hi = low(res_hi); - row2[i] = res_lo + (res_hi << 32); - } - row2[WordCount] = carry; - - UInt<(WordCount + 1) * 64> r1(row1), r2(row2); - r2.shift_left(32); - r1.add(r2); - for (size_t i = 0; i < WordCount; ++i) { - val[i] = r1[i]; - } - return r1[WordCount]; - } - - void shift_left(size_t s) { - const size_t drop = s / 64; // Number of words to drop - const size_t shift = s % 64; // Bits to shift in the remaining words. - const uint64_t mask = ((uint64_t(1) << shift) - 1) << (64 - shift); - - for (size_t i = WordCount; drop > 0 && i > 0; --i) { - if (i - drop > 0) - val[i - 1] = val[i - drop - 1]; - else - val[i - 1] = 0; - } - for (size_t i = WordCount; shift > 0 && i > drop; --i) { - uint64_t drop_val = (val[i - 1] & mask) >> (64 - shift); - val[i - 1] <<= shift; - if (i < WordCount) - val[i] |= drop_val; - } - } - - void shift_right(size_t s) { - const size_t drop = s / 64; // Number of words to drop - const size_t shift = s % 64; // Bit shift in the remaining words. - const uint64_t mask = (uint64_t(1) << shift) - 1; - - for (size_t i = 0; drop > 0 && i < WordCount; ++i) { - if (i + drop < WordCount) - val[i] = val[i + drop]; - else - val[i] = 0; - } - for (size_t i = 0; shift > 0 && i < WordCount; ++i) { - uint64_t drop_val = ((val[i] & mask) << (64 - shift)); - val[i] >>= shift; - if (i > 0) - val[i - 1] |= drop_val; - } - } - - const uint64_t &operator[](size_t i) const { return val[i]; } - - uint64_t &operator[](size_t i) { return val[i]; } - - uint64_t *data() { return val; } - - const uint64_t *data() const { return val; } -}; - -} // namespace fputil -} // namespace __llvm_libc - -#endif // LLVM_LIBC_UTILS_FPUTIL_UINT_H diff --git a/libc/src/__support/FPUtil/XFloat.h b/libc/src/__support/FPUtil/XFloat.h index 11dbf7d..b3d3e23 100644 --- a/libc/src/__support/FPUtil/XFloat.h +++ b/libc/src/__support/FPUtil/XFloat.h @@ -8,7 +8,7 @@ #include "FPBits.h" #include "NormalFloat.h" -#include "UInt.h" +#include "src/__support/CPP/UInt.h" #include diff --git a/libc/src/math/generic/CMakeLists.txt b/libc/src/math/generic/CMakeLists.txt index 6a96b55..2b65d0a 100644 --- a/libc/src/math/generic/CMakeLists.txt +++ b/libc/src/math/generic/CMakeLists.txt @@ -1091,7 +1091,9 @@ add_object_library( HDRS dp_trig.h DEPENDS - libc.src.__support.FPUtil.fputil + libc.src.__support.FPUtil.fputil #FPBits and ManipulationFunction + libc.src.__support.FPUtil.xfloat + libc.src.__support.CPP.uint COMPILE_OPTIONS -O3 ) diff --git a/libc/test/src/__support/CMakeLists.txt b/libc/test/src/__support/CMakeLists.txt index 2fa7325..64c014c 100644 --- a/libc/test/src/__support/CMakeLists.txt +++ b/libc/test/src/__support/CMakeLists.txt @@ -40,6 +40,16 @@ add_libc_unittest( libc.src.__support.arg_list ) +add_libc_unittest( + uint128_test + SUITE + libc_support_unittests + SRCS + uint128_test.cpp + DEPENDS + libc.src.__support.CPP.uint +) + add_executable( libc_str_to_float_comparison_test str_to_float_comparison_test.cpp diff --git a/libc/test/src/__support/uint128_test.cpp b/libc/test/src/__support/uint128_test.cpp new file mode 100644 index 0000000..4ef104c --- /dev/null +++ b/libc/test/src/__support/uint128_test.cpp @@ -0,0 +1,163 @@ +//===-- Unittests for the 128 bit integer class ---------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "src/__support/CPP/UInt.h" + +#include "utils/UnitTest/Test.h" + +using UInt128 = __llvm_libc::cpp::UInt<128>; + +TEST(LlvmLibcUInt128ClassTest, BasicInit) { + UInt128 empty; + UInt128 half_val(12345); + UInt128 full_val({12345, 67890}); + ASSERT_TRUE(half_val != full_val); +} + +TEST(LlvmLibcUInt128ClassTest, AdditionTests) { + UInt128 val1(12345); + UInt128 val2(54321); + UInt128 result1(66666); + EXPECT_EQ(val1 + val2, result1); + EXPECT_EQ((val1 + val2), (val2 + val1)); // addition is reciprocal + + // Test overflow + UInt128 val3({0xf000000000000001, 0}); + UInt128 val4({0x100000000000000f, 0}); + UInt128 result2({0x10, 0x1}); + EXPECT_EQ(val3 + val4, result2); + EXPECT_EQ(val3 + val4, val4 + val3); +} + +TEST(LlvmLibcUInt128ClassTest, MultiplicationTests) { + UInt128 val1({5, 0}); + UInt128 val2({10, 0}); + UInt128 result1({50, 0}); + EXPECT_EQ((val1 * val2), result1); + EXPECT_EQ((val1 * val2), (val2 * val1)); // multiplication is reciprocal + + // Check that the multiplication works accross the whole number + UInt128 val3({0xf, 0}); + UInt128 val4({0x1111111111111111, 0x1111111111111111}); + UInt128 result2({0xffffffffffffffff, 0xffffffffffffffff}); + EXPECT_EQ((val3 * val4), result2); + EXPECT_EQ((val3 * val4), (val4 * val3)); + + // Check that multiplication doesn't reorder the bits. + UInt128 val5({2, 0}); + UInt128 val6({0x1357024675316420, 0x0123456776543210}); + UInt128 result3({0x26ae048cea62c840, 0x02468aceeca86420}); + + EXPECT_EQ((val5 * val6), result3); + EXPECT_EQ((val5 * val6), (val6 * val5)); + + // Make sure that multiplication handles overflow correctly. + UInt128 val7(2); + UInt128 val8({0x8000800080008000, 0x8000800080008000}); + UInt128 result4({0x0001000100010000, 0x0001000100010001}); + EXPECT_EQ((val7 * val8), result4); + EXPECT_EQ((val7 * val8), (val8 * val7)); + + // val9 is the 128 bit mantissa of 1e60 as a float, val10 is the mantissa for + // 1e-60. They almost cancel on the high bits, but the result we're looking + // for is just the low bits. The full result would be + // 0x7fffffffffffffffffffffffffffffff3a4f32d17f40d08f917cf11d1e039c50 + UInt128 val9({0x01D762422C946590, 0x9F4F2726179A2245}); + UInt128 val10({0x3792F412CB06794D, 0xCDB02555653131B6}); + UInt128 result5({0x917cf11d1e039c50, 0x3a4f32d17f40d08f}); + EXPECT_EQ((val9 * val10), result5); + EXPECT_EQ((val9 * val10), (val10 * val9)); +} + +TEST(LlvmLibcUInt128ClassTest, ShiftLeftTests) { + UInt128 val1(0x0123456789abcdef); + UInt128 result1(0x123456789abcdef0); + EXPECT_EQ((val1 << 4), result1); + + UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0}); + UInt128 result2({0x02468ace00000000, 0x9abcdef013579bdf}); + EXPECT_EQ((val2 << 32), result2); + + UInt128 result3({0, 0x13579bdf02468ace}); + EXPECT_EQ((val2 << 64), result3); + + UInt128 result4({0, 0x02468ace00000000}); + EXPECT_EQ((val2 << 96), result4); + + UInt128 result5({0, 0x2468ace000000000}); + EXPECT_EQ((val2 << 100), result5); + + UInt128 result6({0, 0}); + EXPECT_EQ((val2 << 128), result6); + EXPECT_EQ((val2 << 256), result6); +} + +TEST(LlvmLibcUInt128ClassTest, ShiftRightTests) { + UInt128 val1(0x0123456789abcdef); + UInt128 result1(0x00123456789abcde); + EXPECT_EQ((val1 >> 4), result1); + + UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0}); + UInt128 result2({0x9abcdef013579bdf, 0x0000000012345678}); + EXPECT_EQ((val2 >> 32), result2); + + UInt128 result3({0x123456789abcdef0, 0}); + EXPECT_EQ((val2 >> 64), result3); + + UInt128 result4({0x0000000012345678, 0}); + EXPECT_EQ((val2 >> 96), result4); + + UInt128 result5({0x0000000001234567, 0}); + EXPECT_EQ((val2 >> 100), result5); + + UInt128 result6({0, 0}); + EXPECT_EQ((val2 >> 128), result6); + EXPECT_EQ((val2 >> 256), result6); +} + +TEST(LlvmLibcUInt128ClassTest, AndTests) { + UInt128 base({0xffff00000000ffff, 0xffffffff00000000}); + UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff}); + uint64_t val64 = 0xf0f0f0f00f0f0f0f; + int val32 = 0x0f0f0f0f; + UInt128 result128({0xf0f0000000000f0f, 0xff00ff0000000000}); + UInt128 result64(0xf0f0000000000f0f); + UInt128 result32(0x00000f0f); + EXPECT_EQ((base & val128), result128); + EXPECT_EQ((base & val64), result64); + EXPECT_EQ((base & val32), result32); +} + +TEST(LlvmLibcUInt128ClassTest, OrTests) { + UInt128 base({0xffff00000000ffff, 0xffffffff00000000}); + UInt128 val128({0xf0f0f0f00f0f0f0f, 0xff00ff0000ff00ff}); + uint64_t val64 = 0xf0f0f0f00f0f0f0f; + int val32 = 0x0f0f0f0f; + UInt128 result128({0xfffff0f00f0fffff, 0xffffffff00ff00ff}); + UInt128 result64({0xfffff0f00f0fffff, 0xffffffff00000000}); + UInt128 result32({0xffff00000f0fffff, 0xffffffff00000000}); + EXPECT_EQ((base | val128), result128); + EXPECT_EQ((base | val64), result64); + EXPECT_EQ((base | val32), result32); +} + +TEST(LlvmLibcUInt128ClassTest, EqualsTests) { + UInt128 a1({0xffffffff00000000, 0xffff00000000ffff}); + UInt128 a2({0xffffffff00000000, 0xffff00000000ffff}); + UInt128 b({0xff00ff0000ff00ff, 0xf0f0f0f00f0f0f0f}); + UInt128 a_reversed({0xffff00000000ffff, 0xffffffff00000000}); + UInt128 a_upper(0xffff00000000ffff); + UInt128 a_lower(0xffffffff00000000); + ASSERT_TRUE(a1 == a1); + ASSERT_TRUE(a1 == a2); + ASSERT_FALSE(a1 == b); + ASSERT_FALSE(a1 == a_reversed); + ASSERT_FALSE(a1 == a_lower); + ASSERT_FALSE(a1 == a_upper); + ASSERT_TRUE(a_lower != a_upper); +} diff --git a/libc/utils/UnitTest/LibcTest.cpp b/libc/utils/UnitTest/LibcTest.cpp index 21b54a1..f37440d 100644 --- a/libc/utils/UnitTest/LibcTest.cpp +++ b/libc/utils/UnitTest/LibcTest.cpp @@ -8,6 +8,7 @@ #include "LibcTest.h" +#include "src/__support/CPP/UInt.h" #include "utils/testutils/ExecuteFunction.h" #include #include @@ -41,7 +42,6 @@ describeValue(ValType Value) { } std::string describeValue(std::string Value) { return std::string(Value); } - #ifdef __SIZEOF_INT128__ // When the value is __uint128_t, also show its hexadecimal digits. // Using template to force exact match, prevent ambiguous promotion. @@ -64,6 +64,20 @@ template <> std::string describeValue<__uint128_t>(__uint128_t Value) { } #endif +// When the value is UInt<128>, also show its hexadecimal digits. +template <> +std::string +describeValue<__llvm_libc::cpp::UInt<128>>(__llvm_libc::cpp::UInt<128> Value) { + std::string S(sizeof(__llvm_libc::cpp::UInt<128>) * 2, '0'); + + for (auto I = S.rbegin(), End = S.rend(); I != End; ++I, Value = Value >> 4) { + unsigned char Mod = static_cast(Value) & 15; + *I = Mod < 10 ? '0' + Mod : 'a' + Mod - 10; + } + + return "0x" + S; +} + template void explainDifference(ValType LHS, ValType RHS, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line, @@ -226,6 +240,10 @@ template bool test<__int128_t>(RunContext *Ctx, TestCondition Cond, const char *LHSStr, const char *RHSStr, const char *File, unsigned long Line); #endif +template bool test<__llvm_libc::cpp::UInt<128>>( + RunContext *Ctx, TestCondition Cond, __llvm_libc::cpp::UInt<128> LHS, + __llvm_libc::cpp::UInt<128> RHS, const char *LHSStr, const char *RHSStr, + const char *File, unsigned long Line); template bool test(RunContext *Ctx, TestCondition Cond, unsigned char LHS, unsigned char RHS, -- 2.7.4