[libc] Prevent overflow from intermediate results when adding UInt<N> values.
Prevent overflow from intermediate results when adding UInt<N> values.
Reviewed By: orex
Differential Revision: https://reviews.llvm.org/D131095
GitOrigin-RevId: d1a9ba7b67038a8d2560fa4b5abac59ddda28f11
diff --git a/src/__support/CPP/UInt.h b/src/__support/CPP/UInt.h
index dd15635..ebdcb07 100644
--- a/src/__support/CPP/UInt.h
+++ b/src/__support/CPP/UInt.h
@@ -67,30 +67,41 @@
// Add x to this number and store the result in this number.
// Returns the carry value produced by the addition operation.
+ // To prevent overflow from intermediate results, we use the following
+ // property of unsigned integers:
+ // x + (~x) = 2^(sizeof(x)) - 1.
constexpr uint64_t add(const UInt<Bits> &x) {
- uint64_t carry = 0;
+ bool carry = false;
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);
+ uint64_t complement = ~x.val[i];
+ if (!carry) {
+ if (val[i] <= complement)
+ val[i] += x.val[i];
+ else {
+ val[i] -= complement + 1;
+ carry = true;
+ }
+ } else {
+ if (val[i] < complement) {
+ val[i] += x.val[i] + 1;
+ carry = false;
+ } else
+ val[i] -= complement;
+ }
}
- return carry;
+ return carry ? 1 : 0;
}
constexpr UInt<Bits> operator+(const UInt<Bits> &other) const {
UInt<Bits> result(*this);
result.add(other);
+ // TODO(lntue): Set overflow flag / errno when carry is true.
return result;
}
constexpr UInt<Bits> operator+=(const UInt<Bits> &other) {
- *this = *this + other;
+ // TODO(lntue): Set overflow flag / errno when carry is true.
+ add(other);
return *this;
}
diff --git a/test/src/__support/uint128_test.cpp b/test/src/__support/uint128_test.cpp
index 7cb405c..a5205b9 100644
--- a/test/src/__support/uint128_test.cpp
+++ b/test/src/__support/uint128_test.cpp
@@ -27,7 +27,7 @@
LL_UInt128 val2(54321);
LL_UInt128 result1(66666);
EXPECT_EQ(val1 + val2, result1);
- EXPECT_EQ((val1 + val2), (val2 + val1)); // addition is reciprocal
+ EXPECT_EQ((val1 + val2), (val2 + val1)); // addition is commutative
// Test overflow
LL_UInt128 val3({0xf000000000000001, 0});
@@ -35,6 +35,13 @@
LL_UInt128 result2({0x10, 0x1});
EXPECT_EQ(val3 + val4, result2);
EXPECT_EQ(val3 + val4, val4 + val3);
+
+ // Test overflow
+ LL_UInt128 val5({0x0123456789abcdef, 0xfedcba9876543210});
+ LL_UInt128 val6({0x1111222233334444, 0xaaaabbbbccccdddd});
+ LL_UInt128 result3({0x12346789bcdf1233, 0xa987765443210fed});
+ EXPECT_EQ(val5 + val6, result3);
+ EXPECT_EQ(val5 + val6, val6 + val5);
}
TEST(LlvmLibcUInt128ClassTest, MultiplicationTests) {
@@ -42,7 +49,7 @@
LL_UInt128 val2({10, 0});
LL_UInt128 result1({50, 0});
EXPECT_EQ((val1 * val2), result1);
- EXPECT_EQ((val1 * val2), (val2 * val1)); // multiplication is reciprocal
+ EXPECT_EQ((val1 * val2), (val2 * val1)); // multiplication is commutative
// Check that the multiplication works accross the whole number
LL_UInt128 val3({0xf, 0});
diff --git a/utils/UnitTest/LibcTest.cpp b/utils/UnitTest/LibcTest.cpp
index 1153084..2785994 100644
--- a/utils/UnitTest/LibcTest.cpp
+++ b/utils/UnitTest/LibcTest.cpp
@@ -48,6 +48,8 @@
// one type, UInt<128> or __uint128_t. We want both overloads as we want to
// be able to unittest UInt<128> on platforms where UInt128 resolves to
// UInt128.
+// TODO(lntue): Investigate why UInt<128> was printed backward, with the lower
+// 64-bits first.
template <typename UInt128Type>
std::string describeValue128(UInt128Type Value) {
std::string S(sizeof(UInt128) * 2, '0');
