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/FPUtil/CMakeLists.txt b/libc/src/__support/FPUtil/CMakeLists.txt
--- a/libc/src/__support/FPUtil/CMakeLists.txt
+++ b/libc/src/__support/FPUtil/CMakeLists.txt
@@ -13,7 +13,6 @@
NormalFloat.h
PlatformDefs.h
UInt.h
- XFloat.h
DEPENDS
libc.include.math
libc.include.errno
@@ -24,6 +23,23 @@
libc.src.errno.errno
)
+add_header_library(
+ uint
+ HDRS
+ UInt.h
+ DEPENDS
+ libc.src.__support.CPP.array
+)
+
+add_header_library(
+ xfloat
+ HDRS
+ XFloat.h
+ DEPENDS
+ .fputil #FPBits and NormalFloat
+ .uint
+)
+
add_header_library(
sqrt
HDRS
diff --git a/libc/src/__support/FPUtil/UInt.h b/libc/src/__support/FPUtil/UInt.h
--- a/libc/src/__support/FPUtil/UInt.h
+++ b/libc/src/__support/FPUtil/UInt.h
@@ -9,31 +9,33 @@
#ifndef LLVM_LIBC_UTILS_FPUTIL_UINT_H
#define LLVM_LIBC_UTILS_FPUTIL_UINT_H
+#include "src/__support/CPP/Array.h"
+
#include <stddef.h> // For size_t
#include <stdint.h>
namespace __llvm_libc {
namespace fputil {
-template <size_t Bits> class UInt {
+static constexpr uint64_t Mask32 = 0xFFFFFFFF;
- // This is mainly used for debugging.
- enum Kind {
- NotANumber,
- Valid,
- };
+constexpr uint64_t low(uint64_t v) { return v & Mask32; }
+constexpr uint64_t high(uint64_t v) { return (v >> 32) & Mask32; }
+
+template <size_t Bits> class UInt {
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; }
+ constexpr void init(uint64_t x) {
+ val[0] = x;
+ for (size_t i = 1; i < WordCount; ++i) {
+ val[i] = 0;
+ }
+ }
uint64_t hexval(char c) {
uint64_t diff;
@@ -55,61 +57,64 @@
}
public:
- UInt() { kind = Valid; }
+ constexpr UInt() {}
- UInt(const UInt<Bits> &other) : kind(other.kind) {
- if (kind == Valid) {
- for (size_t i = 0; i < WordCount; ++i)
- val[i] = other.val[i];
- }
+ constexpr UInt(const UInt<Bits> &other) {
+ 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) {
+ return;
+ }
- // 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;
- }
+ if (!(s[0] == '0' && s[1] == 'x')) {
+ return;
+ }
- for (size_t i = 0; i < WordCount; ++i)
- val[i] = 0;
+ 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;
+ for (size_t i = len - 1, w = 0; i >= 2; --i, w += 4) {
+ uint64_t hex = hexval(s[i]);
+ if (hex == InvalidHexDigit) {
+ return;
+ }
+ val[w / 64] |= (hex << (w % 64));
}
- val[w / 64] |= (hex << (w % 64));
}
-
- kind = Valid;
+ */
+ // Initialize the first word to |v| and the rest to 0.
+ constexpr UInt(uint64_t v) { init(v); }
+ /*
+ constexpr explicit UInt(const uint64_t data[WordCount]) {
+ for (size_t i = 0; i < WordCount; ++i)
+ val[i] = data[i];
+ }
+ */
+ constexpr explicit UInt(const cpp::Array<uint64_t, WordCount> &words) {
+ for (size_t i = 0; i < WordCount; ++i)
+ val[i] = words[i];
}
- explicit UInt(uint64_t v) {
- val[0] = v;
- for (size_t i = 1; i < WordCount; ++i)
- val[i] = 0;
- kind = Valid;
+ constexpr explicit operator uint64_t() const { return val[0]; }
+
+ constexpr explicit operator uint32_t() const {
+ return uint32_t(uint64_t(*this));
}
- explicit UInt(uint64_t data[WordCount]) {
+ UInt<Bits> &operator=(const UInt<Bits> &other) {
for (size_t i = 0; i < WordCount; ++i)
- val[i] = data[i];
- kind = Valid;
+ val[i] = other.val[i];
+ return *this;
}
- 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<Bits> &x) {
+ constexpr uint64_t add(const UInt<Bits> &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;
@@ -125,17 +130,23 @@
return carry;
}
+ constexpr UInt<Bits> operator+(const UInt<Bits> &other) const {
+ UInt<Bits> 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.
- uint64_t mul(uint64_t x) {
+ constexpr uint64_t mul(uint64_t x) {
uint64_t x_lo = low(x);
uint64_t x_hi = high(x);
- uint64_t row1[WordCount + 1];
+ cpp::Array<uint64_t, WordCount + 1> row1;
uint64_t carry = 0;
for (size_t i = 0; i < WordCount; ++i) {
uint64_t l = low(val[i]);
@@ -154,7 +165,7 @@
}
row1[WordCount] = carry;
- uint64_t row2[WordCount + 1];
+ cpp::Array<uint64_t, WordCount + 1> row2;
row2[0] = 0;
carry = 0;
for (size_t i = 0; i < WordCount; ++i) {
@@ -183,13 +194,25 @@
return r1[WordCount];
}
- void shift_left(size_t s) {
+ constexpr UInt<Bits> operator*(const UInt<Bits> &other) const {
+ UInt<Bits> result(0);
+ result.mul(other[0]);
+ for (size_t i = 0; i < WordCount; ++i) {
+ UInt<Bits> 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 > 0)
+ if (i > drop)
val[i - 1] = val[i - drop - 1];
else
val[i - 1] = 0;
@@ -202,7 +225,13 @@
}
}
- void shift_right(size_t s) {
+ constexpr UInt<Bits> operator<<(size_t s) const {
+ UInt<Bits> 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;
@@ -221,8 +250,53 @@
}
}
+ constexpr UInt<Bits> operator>>(size_t s) const {
+ UInt<Bits> result(*this);
+ result.shift_right(s);
+ return result;
+ }
+
+ constexpr UInt<Bits> operator&(const UInt<Bits> &other) const {
+ UInt<Bits> 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) const {
+ UInt<Bits> 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) const {
+ UInt<Bits> result;
+ for (size_t i = 0; i < WordCount; ++i)
+ result.val[i] = val[i] ^ other.val[i];
+ return result;
+ }
+
+ constexpr bool operator==(const UInt<Bits> &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 {
+ for (size_t i = 0; i < WordCount; ++i) {
+ if (val[i] != other.val[i])
+ return true;
+ }
+ return false;
+ }
+
+ // 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; }
@@ -230,7 +304,47 @@
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 fputil
} // 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_FPUTIL_UINT_H
diff --git a/libc/src/math/generic/CMakeLists.txt b/libc/src/math/generic/CMakeLists.txt
--- a/libc/src/math/generic/CMakeLists.txt
+++ b/libc/src/math/generic/CMakeLists.txt
@@ -1091,7 +1091,9 @@
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.FPUtil.uint
COMPILE_OPTIONS
-O3
)
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.FPUtil.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
--- /dev/null
+++ b/libc/test/src/__support/uint128_test.cpp
@@ -0,0 +1,176 @@
+//===-- 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/FPUtil/UInt.h"
+
+#include "utils/UnitTest/Test.h"
+
+// while I could use "ASSERT_TRUE(a == b)", this will tell me what the values
+// actually are.
+#define EXPECT_128_EQ(LHS, RHS) \
+ { \
+ EXPECT_EQ((LHS)[0], (RHS)[0]); \
+ EXPECT_EQ((LHS)[1], (RHS)[1]); \
+ }
+#define ASSERT_128_EQ(LHS, RHS) \
+ { \
+ ASSERT_EQ((LHS)[0], (RHS)[0]); \
+ ASSERT_EQ((LHS)[1], (RHS)[1]); \
+ }
+
+using UInt128 = __llvm_libc::fputil::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_128_EQ(val1 + val2, result1);
+ EXPECT_128_EQ((val1 + val2), (val2 + val1)); // addition is reciprocal
+
+ // Test overflow
+ UInt128 val3({0xf000000000000001, 0});
+ UInt128 val4({0x100000000000000f, 0});
+ UInt128 result2({0x10, 0x1});
+ EXPECT_128_EQ(val3 + val4, result2);
+ EXPECT_128_EQ(val3 + val4, val4 + val3);
+}
+
+TEST(LlvmLibcUInt128ClassTest, MultiplicationTests) {
+ UInt128 val1({5, 0});
+ UInt128 val2({10, 0});
+ UInt128 result1({50, 0});
+ 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
+ UInt128 val3({0xf, 0});
+ UInt128 val4({0x1111111111111111, 0x1111111111111111});
+ 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.
+ UInt128 val5({2, 0});
+ UInt128 val6({0x1357024675316420, 0x0123456776543210});
+ UInt128 result3({0x26ae048cea62c840, 0x02468aceeca86420});
+
+ EXPECT_128_EQ((val5 * val6), result3);
+ EXPECT_128_EQ((val5 * val6), (val6 * val5));
+
+ // Make sure that multiplication handles overflow correctly.
+ UInt128 val7(2);
+ UInt128 val8({0x8000800080008000, 0x8000800080008000});
+ UInt128 result4({0x0001000100010000, 0x0001000100010001});
+ 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
+ UInt128 val9({0x01D762422C946590, 0x9F4F2726179A2245});
+ UInt128 val10({0x3792F412CB06794D, 0xCDB02555653131B6});
+ UInt128 result5({0x917cf11d1e039c50, 0x3a4f32d17f40d08f});
+ EXPECT_128_EQ((val9 * val10), result5);
+ EXPECT_128_EQ((val9 * val10), (val10 * val9));
+}
+
+TEST(LlvmLibcUInt128ClassTest, ShiftLeftTests) {
+ UInt128 val1(0x0123456789abcdef);
+ UInt128 result1(0x123456789abcdef0);
+ EXPECT_128_EQ((val1 << 4), result1);
+
+ UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0});
+ UInt128 result2({0x02468ace00000000, 0x9abcdef013579bdf});
+ EXPECT_128_EQ((val2 << 32), result2);
+
+ UInt128 result3({0, 0x13579bdf02468ace});
+ EXPECT_128_EQ((val2 << 64), result3);
+
+ UInt128 result4({0, 0x02468ace00000000});
+ EXPECT_128_EQ((val2 << 96), result4);
+
+ UInt128 result5({0, 0x2468ace000000000});
+ EXPECT_128_EQ((val2 << 100), result5);
+
+ UInt128 result6({0, 0});
+ EXPECT_128_EQ((val2 << 128), result6);
+ EXPECT_128_EQ((val2 << 256), result6);
+}
+
+TEST(LlvmLibcUInt128ClassTest, ShiftRightTests) {
+ UInt128 val1(0x0123456789abcdef);
+ UInt128 result1(0x00123456789abcde);
+ EXPECT_128_EQ((val1 >> 4), result1);
+
+ UInt128 val2({0x13579bdf02468ace, 0x123456789abcdef0});
+ UInt128 result2({0x9abcdef013579bdf, 0x0000000012345678});
+ EXPECT_128_EQ((val2 >> 32), result2);
+
+ UInt128 result3({0x123456789abcdef0, 0});
+ EXPECT_128_EQ((val2 >> 64), result3);
+
+ UInt128 result4({0x0000000012345678, 0});
+ EXPECT_128_EQ((val2 >> 96), result4);
+
+ UInt128 result5({0x0000000001234567, 0});
+ EXPECT_128_EQ((val2 >> 100), result5);
+
+ UInt128 result6({0, 0});
+ EXPECT_128_EQ((val2 >> 128), result6);
+ EXPECT_128_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_128_EQ((base & val128), result128);
+ EXPECT_128_EQ((base & val64), result64);
+ EXPECT_128_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_128_EQ((base | val128), result128);
+ EXPECT_128_EQ((base | val64), result64);
+ EXPECT_128_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);
+}