Author: Guillaume Chatelet Date: 2024-04-04T11:07:55+02:00 New Revision: c874f0dbfc76f0c5b83e70eb6b8f810fcefb6592
URL: https://github.com/llvm/llvm-project/commit/c874f0dbfc76f0c5b83e70eb6b8f810fcefb6592 DIFF: https://github.com/llvm/llvm-project/commit/c874f0dbfc76f0c5b83e70eb6b8f810fcefb6592.diff LOG: Revert "[libc] Refactor `BigInt` (#86137)" This reverts commit a2306b65d223212dcfafe12c7299262d8d4fdcb4. Added: Modified: libc/fuzzing/CMakeLists.txt libc/src/__support/FPUtil/dyadic_float.h libc/src/__support/UInt.h libc/src/__support/float_to_string.h libc/src/__support/integer_literals.h libc/src/__support/math_extras.h libc/src/__support/number_pair.h libc/test/src/__support/integer_literals_test.cpp libc/test/src/__support/math_extras_test.cpp libc/test/src/__support/uint_test.cpp utils/bazel/llvm-project-overlay/libc/test/src/__support/BUILD.bazel Removed: libc/fuzzing/__support/CMakeLists.txt libc/fuzzing/__support/uint_fuzz.cpp ################################################################################ diff --git a/libc/fuzzing/CMakeLists.txt b/libc/fuzzing/CMakeLists.txt index 816691b4bd4403..82487688af1162 100644 --- a/libc/fuzzing/CMakeLists.txt +++ b/libc/fuzzing/CMakeLists.txt @@ -1,7 +1,6 @@ set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fsanitize=fuzzer") add_custom_target(libc-fuzzer) -add_subdirectory(__support) # TODO(#85680): Re-enable math fuzzing after headers are sorted out # add_subdirectory(math) add_subdirectory(stdlib) diff --git a/libc/fuzzing/__support/CMakeLists.txt b/libc/fuzzing/__support/CMakeLists.txt deleted file mode 100644 index 278e914e3fbe95..00000000000000 --- a/libc/fuzzing/__support/CMakeLists.txt +++ /dev/null @@ -1,7 +0,0 @@ -add_libc_fuzzer( - uint_fuzz - SRCS - uint_fuzz.cpp - DEPENDS - libc.src.__support.uint -) diff --git a/libc/fuzzing/__support/uint_fuzz.cpp b/libc/fuzzing/__support/uint_fuzz.cpp deleted file mode 100644 index f48f00d3b4ba11..00000000000000 --- a/libc/fuzzing/__support/uint_fuzz.cpp +++ /dev/null @@ -1,70 +0,0 @@ -#include "src/__support/CPP/bit.h" -#include "src/__support/UInt.h" -#include "src/string/memory_utils/inline_memcpy.h" - -using namespace LIBC_NAMESPACE; - -// Helper function when using gdb / lldb to set a breakpoint and inspect values. -template <typename T> void debug_and_trap(const char *msg, T a, T b) { - __builtin_trap(); -} - -#define DEBUG_AND_TRAP() - -#define TEST_BINOP(OP) \ - if ((a OP b) != (static_cast<T>(BigInt(a) OP BigInt(b)))) \ - debug_and_trap(#OP, a, b); - -#define TEST_SHIFTOP(OP) \ - if ((a OP b) != (static_cast<T>(BigInt(a) OP b))) \ - debug_and_trap(#OP, a, b); - -#define TEST_FUNCTION(FUN) \ - if (FUN(a) != FUN(BigInt(a))) \ - debug_and_trap(#FUN, a, b); - -// Test that basic arithmetic operations of BigInt behave like their scalar -// counterparts. -template <typename T, typename BigInt> void run_tests(T a, T b) { - TEST_BINOP(+) - TEST_BINOP(-) - TEST_BINOP(*) - if (b != 0) - TEST_BINOP(/) - if (b >= 0 && b < cpp::numeric_limits<T>::digits) { - TEST_SHIFTOP(<<) - TEST_SHIFTOP(>>) - } - if constexpr (!BigInt::SIGNED) { - TEST_FUNCTION(cpp::has_single_bit) - TEST_FUNCTION(cpp::countr_zero) - TEST_FUNCTION(cpp::countl_zero) - TEST_FUNCTION(cpp::countl_one) - TEST_FUNCTION(cpp::countr_one) - } -} - -// Reads a T from libfuzzer data. -template <typename T> T read(const uint8_t *data, size_t &remainder) { - T out = 0; - constexpr size_t T_SIZE = sizeof(T); - const size_t copy_size = remainder < T_SIZE ? remainder : T_SIZE; - inline_memcpy(&out, data, copy_size); - remainder -= copy_size; - return out; -} - -template <typename T, typename BigInt> -void run_tests(const uint8_t *data, size_t size) { - const auto a = read<T>(data, size); - const auto b = read<T>(data, size); - run_tests<T, BigInt>(a, b); -} - -extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { - // unsigned - run_tests<uint64_t, BigInt<64, false, uint16_t>>(data, size); - // signed - run_tests<int64_t, BigInt<64, true, uint16_t>>(data, size); - return 0; -} diff --git a/libc/src/__support/FPUtil/dyadic_float.h b/libc/src/__support/FPUtil/dyadic_float.h index e0c205f52383ba..73fd7381c3c838 100644 --- a/libc/src/__support/FPUtil/dyadic_float.h +++ b/libc/src/__support/FPUtil/dyadic_float.h @@ -58,9 +58,9 @@ template <size_t Bits> struct DyadicFloat { // significant bit. LIBC_INLINE constexpr DyadicFloat &normalize() { if (!mantissa.is_zero()) { - int shift_length = cpp::countl_zero(mantissa); + int shift_length = static_cast<int>(mantissa.clz()); exponent -= shift_length; - mantissa <<= static_cast<size_t>(shift_length); + mantissa.shift_left(static_cast<size_t>(shift_length)); } return *this; } @@ -233,7 +233,7 @@ LIBC_INLINE constexpr DyadicFloat<Bits> quick_add(DyadicFloat<Bits> a, result.sign = a.sign; result.exponent = a.exponent; result.mantissa = a.mantissa; - if (result.mantissa.add_overflow(b.mantissa)) { + if (result.mantissa.add(b.mantissa)) { // Mantissa addition overflow. result.shift_right(1); result.mantissa.val[DyadicFloat<Bits>::MantissaType::WORD_COUNT - 1] |= diff --git a/libc/src/__support/UInt.h b/libc/src/__support/UInt.h index c524de38d98654..282efdba1c5f2b 100644 --- a/libc/src/__support/UInt.h +++ b/libc/src/__support/UInt.h @@ -14,11 +14,10 @@ #include "src/__support/CPP/limits.h" #include "src/__support/CPP/optional.h" #include "src/__support/CPP/type_traits.h" -#include "src/__support/macros/attributes.h" // LIBC_INLINE -#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY -#include "src/__support/macros/properties/compiler.h" // LIBC_COMPILER_IS_CLANG +#include "src/__support/macros/attributes.h" // LIBC_INLINE +#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY #include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128, LIBC_TYPES_HAS_INT64 -#include "src/__support/math_extras.h" // add_with_carry, sub_with_borrow +#include "src/__support/math_extras.h" // SumCarry, DiffBorrow #include "src/__support/number_pair.h" #include <stddef.h> // For size_t @@ -26,321 +25,71 @@ namespace LIBC_NAMESPACE { -namespace multiword { - -// A type trait mapping unsigned integers to their half-width unsigned -// counterparts. +namespace internal { template <typename T> struct half_width; -template <> struct half_width<uint16_t> : cpp::type_identity<uint8_t> {}; -template <> struct half_width<uint32_t> : cpp::type_identity<uint16_t> {}; -#ifdef LIBC_TYPES_HAS_INT64 + template <> struct half_width<uint64_t> : cpp::type_identity<uint32_t> {}; +template <> struct half_width<uint32_t> : cpp::type_identity<uint16_t> {}; +template <> struct half_width<uint16_t> : cpp::type_identity<uint8_t> {}; #ifdef LIBC_TYPES_HAS_INT128 template <> struct half_width<__uint128_t> : cpp::type_identity<uint64_t> {}; #endif // LIBC_TYPES_HAS_INT128 -#endif // LIBC_TYPES_HAS_INT64 -template <typename T> using half_width_t = typename half_width<T>::type; - -// An array of two elements that can be used in multiword operations. -template <typename T> struct DoubleWide final : cpp::array<T, 2> { - using UP = cpp::array<T, 2>; - using UP::UP; - LIBC_INLINE constexpr DoubleWide(T lo, T hi) : UP({lo, hi}) {} -}; - -// Converts an unsigned value into a DoubleWide<half_width_t<T>>. -template <typename T> LIBC_INLINE constexpr auto split(T value) { - static_assert(cpp::is_unsigned_v<T>); - return cpp::bit_cast<DoubleWide<half_width_t<T>>>(value); -} - -// The low part of a DoubleWide value. -template <typename T> LIBC_INLINE constexpr T lo(const DoubleWide<T> &value) { - return value[0]; -} -// The high part of a DoubleWide value. -template <typename T> LIBC_INLINE constexpr T hi(const DoubleWide<T> &value) { - return value[1]; -} -// The low part of an unsigned value. -template <typename T> LIBC_INLINE constexpr half_width_t<T> lo(T value) { - return lo(split(value)); -} -// The high part of an unsigned value. -template <typename T> LIBC_INLINE constexpr half_width_t<T> hi(T value) { - return hi(split(value)); -} - -// Returns 'a' times 'b' in a DoubleWide<word>. Cannot overflow by construction. -template <typename word> -LIBC_INLINE constexpr DoubleWide<word> mul2(word a, word b) { - if constexpr (cpp::is_same_v<word, uint8_t>) { - return split<uint16_t>(uint16_t(a) * uint16_t(b)); - } else if constexpr (cpp::is_same_v<word, uint16_t>) { - return split<uint32_t>(uint32_t(a) * uint32_t(b)); - } -#ifdef LIBC_TYPES_HAS_INT64 - else if constexpr (cpp::is_same_v<word, uint32_t>) { - return split<uint64_t>(uint64_t(a) * uint64_t(b)); - } -#endif -#ifdef LIBC_TYPES_HAS_INT128 - else if constexpr (cpp::is_same_v<word, uint64_t>) { - return split<__uint128_t>(__uint128_t(a) * __uint128_t(b)); - } -#endif - else { - using half_word = half_width_t<word>; - const auto shiftl = [](word value) -> word { - return value << cpp::numeric_limits<half_word>::digits; - }; - const auto shiftr = [](word value) -> word { - return value >> cpp::numeric_limits<half_word>::digits; - }; - // Here we do a one digit multiplication where 'a' and 'b' are of type - // word. We split 'a' and 'b' into half words and perform the classic long - // multiplication with 'a' and 'b' being two-digit numbers. - - // a a_hi a_lo - // x b => x b_hi b_lo - // ---- ----------- - // c result - // We convert 'lo' and 'hi' from 'half_word' to 'word' so multiplication - // doesn't overflow. - const word a_lo = lo(a); - const word b_lo = lo(b); - const word a_hi = hi(a); - const word b_hi = hi(b); - const word step1 = b_lo * a_lo; // no overflow; - const word step2 = b_lo * a_hi; // no overflow; - const word step3 = b_hi * a_lo; // no overflow; - const word step4 = b_hi * a_hi; // no overflow; - word lo_digit = step1; - word hi_digit = step4; - const word no_carry = 0; - word carry; - word _; // unused carry variable. - lo_digit = add_with_carry<word>(lo_digit, shiftl(step2), no_carry, carry); - hi_digit = add_with_carry<word>(hi_digit, shiftr(step2), carry, _); - lo_digit = add_with_carry<word>(lo_digit, shiftl(step3), no_carry, carry); - hi_digit = add_with_carry<word>(hi_digit, shiftr(step3), carry, _); - return DoubleWide<word>(lo_digit, hi_digit); - } -} - -// In-place 'dst op= rhs' with operation with carry propagation. Returns carry. -template <typename Function, typename word, size_t N, size_t M> -LIBC_INLINE constexpr word inplace_binop(Function op_with_carry, - cpp::array<word, N> &dst, - const cpp::array<word, M> &rhs) { - static_assert(N >= M); - word carry_out = 0; - for (size_t i = 0; i < N; ++i) { - const bool has_rhs_value = i < M; - const word rhs_value = has_rhs_value ? rhs[i] : 0; - const word carry_in = carry_out; - dst[i] = op_with_carry(dst[i], rhs_value, carry_in, carry_out); - // stop early when rhs is over and no carry is to be propagated. - if (!has_rhs_value && carry_out == 0) - break; - } - return carry_out; -} -// In-place addition. Returns carry. -template <typename word, size_t N, size_t M> -LIBC_INLINE constexpr word add_with_carry(cpp::array<word, N> &dst, - const cpp::array<word, M> &rhs) { - return inplace_binop(LIBC_NAMESPACE::add_with_carry<word>, dst, rhs); -} +template <typename T> using half_width_t = typename half_width<T>::type; -// In-place subtraction. Returns borrow. -template <typename word, size_t N, size_t M> -LIBC_INLINE constexpr word sub_with_borrow(cpp::array<word, N> &dst, - const cpp::array<word, M> &rhs) { - return inplace_binop(LIBC_NAMESPACE::sub_with_borrow<word>, dst, rhs); -} +template <typename T> constexpr NumberPair<T> full_mul(T a, T b) { + NumberPair<T> pa = split(a); + NumberPair<T> pb = split(b); + NumberPair<T> prod; -// In-place multiply-add. Returns carry. -// i.e., 'dst += b * c' -template <typename word, size_t N> -LIBC_INLINE constexpr word mul_add_with_carry(cpp::array<word, N> &dst, word b, - word c) { - return add_with_carry(dst, mul2(b, c)); -} + prod.lo = pa.lo * pb.lo; // exact + prod.hi = pa.hi * pb.hi; // exact + NumberPair<T> lo_hi = split(pa.lo * pb.hi); // exact + NumberPair<T> hi_lo = split(pa.hi * pb.lo); // exact -// An array of two elements serving as an accumulator during multiword -// computations. -template <typename T> struct Accumulator final : cpp::array<T, 2> { - using UP = cpp::array<T, 2>; - LIBC_INLINE constexpr Accumulator() : UP({0, 0}) {} - LIBC_INLINE constexpr T advance(T carry_in) { - auto result = UP::front(); - UP::front() = UP::back(); - UP::back() = carry_in; - return result; - } - LIBC_INLINE constexpr T sum() const { return UP::front(); } - LIBC_INLINE constexpr T carry() const { return UP::back(); } -}; + constexpr size_t HALF_BIT_WIDTH = sizeof(T) * CHAR_BIT / 2; -// In-place multiplication by a single word. Returns carry. -template <typename word, size_t N> -LIBC_INLINE constexpr word scalar_multiply_with_carry(cpp::array<word, N> &dst, - word x) { - Accumulator<word> acc; - for (auto &val : dst) { - const word carry = mul_add_with_carry(acc, val, x); - val = acc.advance(carry); - } - return acc.carry(); -} + auto r1 = add_with_carry(prod.lo, lo_hi.lo << HALF_BIT_WIDTH, T(0)); + prod.lo = r1.sum; + prod.hi = add_with_carry(prod.hi, lo_hi.hi, r1.carry).sum; -// Multiplication of 'lhs' by 'rhs' into 'dst'. Returns carry. -// This function is safe to use for signed numbers. -// https://stackoverflow.com/a/20793834 -// https://pages.cs.wisc.edu/%7Emarkhill/cs354/Fall2008/beyond354/int.mult.html -template <typename word, size_t O, size_t M, size_t N> -LIBC_INLINE constexpr word multiply_with_carry(cpp::array<word, O> &dst, - const cpp::array<word, M> &lhs, - const cpp::array<word, N> &rhs) { - static_assert(O >= M + N); - Accumulator<word> acc; - for (size_t i = 0; i < O; ++i) { - const size_t lower_idx = i < N ? 0 : i - N + 1; - const size_t upper_idx = i < M ? i : M - 1; - word carry = 0; - for (size_t j = lower_idx; j <= upper_idx; ++j) - carry += mul_add_with_carry(acc, lhs[j], rhs[i - j]); - dst[i] = acc.advance(carry); - } - return acc.carry(); -} + auto r2 = add_with_carry(prod.lo, hi_lo.lo << HALF_BIT_WIDTH, T(0)); + prod.lo = r2.sum; + prod.hi = add_with_carry(prod.hi, hi_lo.hi, r2.carry).sum; -template <typename word, size_t N> -LIBC_INLINE constexpr void quick_mul_hi(cpp::array<word, N> &dst, - const cpp::array<word, N> &lhs, - const cpp::array<word, N> &rhs) { - Accumulator<word> acc; - word carry = 0; - // First round of accumulation for those at N - 1 in the full product. - for (size_t i = 0; i < N; ++i) - carry += mul_add_with_carry(acc, lhs[i], rhs[N - 1 - i]); - for (size_t i = N; i < 2 * N - 1; ++i) { - acc.advance(carry); - carry = 0; - for (size_t j = i - N + 1; j < N; ++j) - carry += mul_add_with_carry(acc, lhs[j], rhs[i - j]); - dst[i - N] = acc.sum(); - } - dst.back() = acc.carry(); + return prod; } -template <typename word, size_t N> -LIBC_INLINE constexpr bool is_negative(cpp::array<word, N> &array) { - using signed_word = cpp::make_signed_t<word>; - return cpp::bit_cast<signed_word>(array.back()) < 0; +template <> +LIBC_INLINE constexpr NumberPair<uint32_t> full_mul<uint32_t>(uint32_t a, + uint32_t b) { + uint64_t prod = uint64_t(a) * uint64_t(b); + NumberPair<uint32_t> result; + result.lo = uint32_t(prod); + result.hi = uint32_t(prod >> 32); + return result; } -// An enum for the shift function below. -enum Direction { LEFT, RIGHT }; - -// A bitwise shift on an array of elements. -// TODO: Make the result UB when 'offset' is greater or equal to the number of -// bits in 'array'. This will allow for better code performance. -template <Direction direction, bool is_signed, typename word, size_t N> -LIBC_INLINE constexpr cpp::array<word, N> shift(cpp::array<word, N> array, - size_t offset) { - static_assert(direction == LEFT || direction == RIGHT); - constexpr size_t WORD_BITS = cpp::numeric_limits<word>::digits; - constexpr size_t TOTAL_BITS = N * WORD_BITS; - if (LIBC_UNLIKELY(offset == 0)) - return array; - if (LIBC_UNLIKELY(offset >= TOTAL_BITS)) - return {}; #ifdef LIBC_TYPES_HAS_INT128 - if constexpr (TOTAL_BITS == 128) { - using type = cpp::conditional_t<is_signed, __int128_t, __uint128_t>; - auto tmp = cpp::bit_cast<type>(array); - if constexpr (direction == LEFT) - tmp <<= offset; - else - tmp >>= offset; - return cpp::bit_cast<cpp::array<word, N>>(tmp); - } -#endif - const bool is_neg = is_signed && is_negative(array); - constexpr auto at = [](size_t index) -> int { - // reverse iteration when direction == LEFT. - if constexpr (direction == LEFT) - return int(N) - int(index) - 1; - return int(index); - }; - const auto safe_get_at = [&](size_t index) -> word { - // return appropriate value when accessing out of bound elements. - const int i = at(index); - if (i < 0) - return 0; - if (i >= int(N)) - return is_neg ? -1 : 0; - return array[i]; - }; - const size_t index_offset = offset / WORD_BITS; - const size_t bit_offset = offset % WORD_BITS; -#ifdef LIBC_COMPILER_IS_CLANG - __builtin_assume(index_offset < N); -#endif - cpp::array<word, N> out = {}; - for (size_t index = 0; index < N; ++index) { - const word part1 = safe_get_at(index + index_offset); - const word part2 = safe_get_at(index + index_offset + 1); - word &dst = out[at(index)]; - if (bit_offset == 0) - dst = part1; // no crosstalk between parts. - else if constexpr (direction == LEFT) - dst = (part1 << bit_offset) | (part2 >> (WORD_BITS - bit_offset)); - else - dst = (part1 >> bit_offset) | (part2 << (WORD_BITS - bit_offset)); - } - return out; +template <> +LIBC_INLINE constexpr NumberPair<uint64_t> full_mul<uint64_t>(uint64_t a, + uint64_t b) { + __uint128_t prod = __uint128_t(a) * __uint128_t(b); + NumberPair<uint64_t> result; + result.lo = uint64_t(prod); + result.hi = uint64_t(prod >> 64); + return result; } +#endif // LIBC_TYPES_HAS_INT128 -#define DECLARE_COUNTBIT(NAME, INDEX_EXPR) \ - template <typename word, size_t N> \ - LIBC_INLINE constexpr int NAME(const cpp::array<word, N> &val) { \ - int bit_count = 0; \ - for (size_t i = 0; i < N; ++i) { \ - const int word_count = cpp::NAME<word>(val[INDEX_EXPR]); \ - bit_count += word_count; \ - if (word_count != cpp::numeric_limits<word>::digits) \ - break; \ - } \ - return bit_count; \ - } - -DECLARE_COUNTBIT(countr_zero, i) // iterating forward -DECLARE_COUNTBIT(countr_one, i) // iterating forward -DECLARE_COUNTBIT(countl_zero, N - i - 1) // iterating backward -DECLARE_COUNTBIT(countl_one, N - i - 1) // iterating backward - -} // namespace multiword +} // namespace internal template <size_t Bits, bool Signed, typename WordType = uint64_t> struct BigInt { -private: static_assert(cpp::is_integral_v<WordType> && cpp::is_unsigned_v<WordType>, "WordType must be unsigned integer."); - struct Division { - BigInt quotient; - BigInt remainder; - }; - -public: using word_type = WordType; - using unsigned_type = BigInt<Bits, false, word_type>; - using signed_type = BigInt<Bits, true, word_type>; - LIBC_INLINE_VAR static constexpr bool SIGNED = Signed; LIBC_INLINE_VAR static constexpr size_t BITS = Bits; LIBC_INLINE_VAR @@ -351,7 +100,10 @@ struct BigInt { LIBC_INLINE_VAR static constexpr size_t WORD_COUNT = Bits / WORD_SIZE; - cpp::array<WordType, WORD_COUNT> val{}; // zero initialized. + using unsigned_type = BigInt<BITS, false, word_type>; + using signed_type = BigInt<BITS, true, word_type>; + + cpp::array<WordType, WORD_COUNT> val{}; LIBC_INLINE constexpr BigInt() = default; @@ -360,67 +112,76 @@ struct BigInt { template <size_t OtherBits, bool OtherSigned> LIBC_INLINE constexpr BigInt( const BigInt<OtherBits, OtherSigned, WordType> &other) { - if (OtherBits >= Bits) { // truncate + if (OtherBits >= Bits) { for (size_t i = 0; i < WORD_COUNT; ++i) val[i] = other[i]; - } else { // zero or sign extend + } else { size_t i = 0; for (; i < OtherBits / WORD_SIZE; ++i) val[i] = other[i]; - extend(i, Signed && other.is_neg()); + WordType sign = 0; + if constexpr (Signed && OtherSigned) { + sign = static_cast<WordType>( + -static_cast<cpp::make_signed_t<WordType>>(other.is_neg())); + } + for (; i < WORD_COUNT; ++i) + val[i] = sign; } } // Construct a BigInt from a C array. - template <size_t N> LIBC_INLINE constexpr BigInt(const WordType (&nums)[N]) { - static_assert(N == WORD_COUNT); - for (size_t i = 0; i < WORD_COUNT; ++i) + template <size_t N, cpp::enable_if_t<N <= WORD_COUNT, int> = 0> + LIBC_INLINE constexpr BigInt(const WordType (&nums)[N]) { + size_t min_wordcount = N < WORD_COUNT ? N : WORD_COUNT; + size_t i = 0; + for (; i < min_wordcount; ++i) val[i] = nums[i]; - } - LIBC_INLINE constexpr explicit BigInt( - const cpp::array<WordType, WORD_COUNT> &words) { - val = words; + // If nums doesn't completely fill val, then fill the rest with zeroes. + for (; i < WORD_COUNT; ++i) + val[i] = 0; } // Initialize the first word to |v| and the rest to 0. template <typename T, typename = cpp::enable_if_t<cpp::is_integral_v<T>>> LIBC_INLINE constexpr BigInt(T v) { - constexpr size_t T_SIZE = sizeof(T) * CHAR_BIT; - const bool is_neg = Signed && (v < 0); - for (size_t i = 0; i < WORD_COUNT; ++i) { - if (v == 0) { - extend(i, is_neg); - return; + val[0] = static_cast<WordType>(v); + + if constexpr (WORD_COUNT == 1) + return; + + if constexpr (Bits < sizeof(T) * CHAR_BIT) { + for (int i = 1; i < WORD_COUNT; ++i) { + v >>= WORD_SIZE; + val[i] = static_cast<WordType>(v); } - val[i] = static_cast<WordType>(v); - if constexpr (T_SIZE > WORD_SIZE) + return; + } + + size_t i = 1; + + if constexpr (WORD_SIZE < sizeof(T) * CHAR_BIT) + for (; i < sizeof(T) * CHAR_BIT / WORD_SIZE; ++i) { v >>= WORD_SIZE; - else - v = 0; + val[i] = static_cast<WordType>(v); + } + + WordType sign = (Signed && (v < 0)) ? ~WordType(0) : WordType(0); + for (; i < WORD_COUNT; ++i) { + val[i] = sign; } } - LIBC_INLINE constexpr BigInt &operator=(const BigInt &other) = default; - // constants - LIBC_INLINE static constexpr BigInt zero() { return BigInt(); } - LIBC_INLINE static constexpr BigInt one() { return BigInt(1); } - LIBC_INLINE static constexpr BigInt all_ones() { return ~zero(); } - LIBC_INLINE static constexpr BigInt min() { - BigInt out; - if constexpr (SIGNED) - out.set_msb(); - return out; - } - LIBC_INLINE static constexpr BigInt max() { - BigInt out = all_ones(); - if constexpr (SIGNED) - out.clear_msb(); - return out; + LIBC_INLINE constexpr explicit BigInt( + const cpp::array<WordType, WORD_COUNT> &words) { + for (size_t i = 0; i < WORD_COUNT; ++i) + val[i] = words[i]; } // TODO: Reuse the Sign type. - LIBC_INLINE constexpr bool is_neg() const { return SIGNED && get_msb(); } + LIBC_INLINE constexpr bool is_neg() const { + return val.back() >> (WORD_SIZE - 1); + } template <typename T> LIBC_INLINE constexpr explicit operator T() const { return to<T>(); @@ -430,100 +191,200 @@ struct BigInt { LIBC_INLINE constexpr cpp::enable_if_t< cpp::is_integral_v<T> && !cpp::is_same_v<T, bool>, T> to() const { - constexpr size_t T_SIZE = sizeof(T) * CHAR_BIT; T lo = static_cast<T>(val[0]); - if constexpr (T_SIZE <= WORD_SIZE) + + constexpr size_t T_BITS = sizeof(T) * CHAR_BIT; + + if constexpr (T_BITS <= WORD_SIZE) return lo; + constexpr size_t MAX_COUNT = - T_SIZE > Bits ? WORD_COUNT : T_SIZE / WORD_SIZE; + T_BITS > Bits ? WORD_COUNT : T_BITS / WORD_SIZE; for (size_t i = 1; i < MAX_COUNT; ++i) lo += static_cast<T>(val[i]) << (WORD_SIZE * i); - if constexpr (Signed && (T_SIZE > Bits)) { + + if constexpr (Signed && (T_BITS > Bits)) { // Extend sign for negative numbers. constexpr T MASK = (~T(0) << Bits); if (is_neg()) lo |= MASK; } + return lo; } LIBC_INLINE constexpr explicit operator bool() const { return !is_zero(); } + LIBC_INLINE constexpr BigInt &operator=(const BigInt &other) = default; + LIBC_INLINE constexpr bool is_zero() const { - for (auto part : val) - if (part != 0) + for (size_t i = 0; i < WORD_COUNT; ++i) { + if (val[i] != 0) return false; + } return true; } - // Add 'rhs' to this number and store the result in this number. + // Add x to this number and store the result in this number. // Returns the carry value produced by the addition operation. - LIBC_INLINE constexpr WordType add_overflow(const BigInt &rhs) { - return multiword::add_with_carry(val, rhs.val); + LIBC_INLINE constexpr WordType add(const BigInt &x) { + SumCarry<WordType> s{0, 0}; + for (size_t i = 0; i < WORD_COUNT; ++i) { + s = add_with_carry(val[i], x.val[i], s.carry); + val[i] = s.sum; + } + return s.carry; } LIBC_INLINE constexpr BigInt operator+(const BigInt &other) const { - BigInt result = *this; - result.add_overflow(other); + BigInt result; + SumCarry<WordType> s{0, 0}; + for (size_t i = 0; i < WORD_COUNT; ++i) { + s = add_with_carry(val[i], other.val[i], s.carry); + result.val[i] = s.sum; + } return result; } // This will only apply when initializing a variable from constant values, so // it will always use the constexpr version of add_with_carry. LIBC_INLINE constexpr BigInt operator+(BigInt &&other) const { - // We use addition commutativity to reuse 'other' and prevent allocation. - other.add_overflow(*this); // Returned carry value is ignored. - return other; + BigInt result; + SumCarry<WordType> s{0, 0}; + for (size_t i = 0; i < WORD_COUNT; ++i) { + s = add_with_carry(val[i], other.val[i], s.carry); + result.val[i] = s.sum; + } + return result; } LIBC_INLINE constexpr BigInt &operator+=(const BigInt &other) { - add_overflow(other); // Returned carry value is ignored. + add(other); // Returned carry value is ignored. return *this; } - // Subtract 'rhs' to this number and store the result in this number. + // Subtract x to this number and store the result in this number. // Returns the carry value produced by the subtraction operation. - LIBC_INLINE constexpr WordType sub_overflow(const BigInt &rhs) { - return multiword::sub_with_borrow(val, rhs.val); + LIBC_INLINE constexpr WordType sub(const BigInt &x) { + DiffBorrow<WordType> d{0, 0}; + for (size_t i = 0; i < WORD_COUNT; ++i) { + d = sub_with_borrow(val[i], x.val[i], d.borrow); + val[i] = d. diff ; + } + return d.borrow; } LIBC_INLINE constexpr BigInt operator-(const BigInt &other) const { - BigInt result = *this; - result.sub_overflow(other); // Returned carry value is ignored. + BigInt result; + DiffBorrow<WordType> d{0, 0}; + for (size_t i = 0; i < WORD_COUNT; ++i) { + d = sub_with_borrow(val[i], other.val[i], d.borrow); + result.val[i] = d. diff ; + } return result; } LIBC_INLINE constexpr BigInt operator-(BigInt &&other) const { - BigInt result = *this; - result.sub_overflow(other); // Returned carry value is ignored. + BigInt result; + DiffBorrow<WordType> d{0, 0}; + for (size_t i = 0; i < WORD_COUNT; ++i) { + d = sub_with_borrow(val[i], other.val[i], d.borrow); + result.val[i] = d. diff ; + } return result; } LIBC_INLINE constexpr BigInt &operator-=(const BigInt &other) { // TODO(lntue): Set overflow flag / errno when carry is true. - sub_overflow(other); // Returned carry value is ignored. + sub(other); return *this; } - // Multiply this number with x and store the result in this number. + // 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. LIBC_INLINE constexpr WordType mul(WordType x) { - return multiword::scalar_multiply_with_carry(val, x); + BigInt<2 * WORD_SIZE, Signed, WordType> partial_sum(0); + for (size_t i = 0; i < WORD_COUNT; ++i) { + NumberPair<WordType> prod = internal::full_mul(val[i], x); + BigInt<2 * WORD_SIZE, Signed, WordType> tmp({prod.lo, prod.hi}); + const WordType carry = partial_sum.add(tmp); + val[i] = partial_sum.val[0]; + partial_sum.val[0] = partial_sum.val[1]; + partial_sum.val[1] = carry; + } + return partial_sum.val[1]; + } + + LIBC_INLINE constexpr BigInt operator*(const BigInt &other) const { + if constexpr (Signed) { + BigInt<Bits, false, WordType> a(*this); + BigInt<Bits, false, WordType> b(other); + const bool a_neg = a.is_neg(); + const bool b_neg = b.is_neg(); + if (a_neg) + a = -a; + if (b_neg) + b = -b; + BigInt<Bits, false, WordType> prod = a * b; + if (a_neg != b_neg) + prod = -prod; + return static_cast<BigInt<Bits, true, WordType>>(prod); + } else { + if constexpr (WORD_COUNT == 1) { + return {val[0] * other.val[0]}; + } else { + BigInt result(0); + BigInt<2 * WORD_SIZE, Signed, WordType> partial_sum(0); + WordType carry = 0; + for (size_t i = 0; i < WORD_COUNT; ++i) { + for (size_t j = 0; j <= i; j++) { + NumberPair<WordType> prod = + internal::full_mul(val[j], other.val[i - j]); + BigInt<2 * WORD_SIZE, Signed, WordType> tmp({prod.lo, prod.hi}); + carry += partial_sum.add(tmp); + } + result.val[i] = partial_sum.val[0]; + partial_sum.val[0] = partial_sum.val[1]; + partial_sum.val[1] = carry; + carry = 0; + } + return result; + } + } } - // Return the full product. + // Return the full product, only unsigned for now. template <size_t OtherBits> - LIBC_INLINE constexpr auto + LIBC_INLINE constexpr BigInt<Bits + OtherBits, Signed, WordType> ful_mul(const BigInt<OtherBits, Signed, WordType> &other) const { - BigInt<Bits + OtherBits, Signed, WordType> result; - multiword::multiply_with_carry(result.val, val, other.val); + BigInt<Bits + OtherBits, Signed, WordType> result(0); + BigInt<2 * WORD_SIZE, Signed, WordType> partial_sum(0); + WordType carry = 0; + constexpr size_t OTHER_WORDCOUNT = + BigInt<OtherBits, Signed, WordType>::WORD_COUNT; + for (size_t i = 0; i <= WORD_COUNT + OTHER_WORDCOUNT - 2; ++i) { + const size_t lower_idx = + i < OTHER_WORDCOUNT ? 0 : i - OTHER_WORDCOUNT + 1; + const size_t upper_idx = i < WORD_COUNT ? i : WORD_COUNT - 1; + for (size_t j = lower_idx; j <= upper_idx; ++j) { + NumberPair<WordType> prod = + internal::full_mul(val[j], other.val[i - j]); + BigInt<2 * WORD_SIZE, Signed, WordType> tmp({prod.lo, prod.hi}); + carry += partial_sum.add(tmp); + } + result.val[i] = partial_sum.val[0]; + partial_sum.val[0] = partial_sum.val[1]; + partial_sum.val[1] = carry; + carry = 0; + } + result.val[WORD_COUNT + OTHER_WORDCOUNT - 1] = partial_sum.val[0]; return result; } - LIBC_INLINE constexpr BigInt operator*(const BigInt &other) const { - // Perform full mul and truncate. - return BigInt(ful_mul(other)); - } - // Fast hi part of the full product. The normal product `operator*` returns // `Bits` least significant bits of the full product, while this function will // approximate `Bits` most significant bits of the full product with errors @@ -546,17 +407,39 @@ struct BigInt { // 256 4 16 10 3 // 512 8 64 36 7 LIBC_INLINE constexpr BigInt quick_mul_hi(const BigInt &other) const { - BigInt result; - multiword::quick_mul_hi(result.val, val, other.val); + BigInt result(0); + BigInt<2 * WORD_SIZE, Signed, WordType> partial_sum(0); + WordType carry = 0; + // First round of accumulation for those at WORD_COUNT - 1 in the full + // product. + for (size_t i = 0; i < WORD_COUNT; ++i) { + NumberPair<WordType> prod = + internal::full_mul(val[i], other.val[WORD_COUNT - 1 - i]); + BigInt<2 * WORD_SIZE, Signed, WordType> tmp({prod.lo, prod.hi}); + carry += partial_sum.add(tmp); + } + for (size_t i = WORD_COUNT; i < 2 * WORD_COUNT - 1; ++i) { + partial_sum.val[0] = partial_sum.val[1]; + partial_sum.val[1] = carry; + carry = 0; + for (size_t j = i - WORD_COUNT + 1; j < WORD_COUNT; ++j) { + NumberPair<WordType> prod = + internal::full_mul(val[j], other.val[i - j]); + BigInt<2 * WORD_SIZE, Signed, WordType> tmp({prod.lo, prod.hi}); + carry += partial_sum.add(tmp); + } + result.val[i - WORD_COUNT] = partial_sum.val[0]; + } + result.val[WORD_COUNT - 1] = partial_sum.val[1]; return result; } - // BigInt(x).pow_n(n) computes x ^ n. - // Note 0 ^ 0 == 1. + // pow takes a power and sets this to its starting value to that power. Zero + // to the zeroth power returns 1. LIBC_INLINE constexpr void pow_n(uint64_t power) { - static_assert(!Signed); - BigInt result = one(); + BigInt result = 1; BigInt cur_power = *this; + while (power > 0) { if ((power % 2) > 0) result *= cur_power; @@ -566,23 +449,38 @@ struct BigInt { *this = result; } - // Performs inplace signed / unsigned division. Returns remainder if not - // dividing by zero. - // For signed numbers it behaves like C++ signed integer division. - // That is by truncating the fractionnal part - // https://stackoverflow.com/a/3602857 - LIBC_INLINE constexpr cpp::optional<BigInt> div(const BigInt ÷r) { - if (LIBC_UNLIKELY(divider.is_zero())) + // TODO: Make division work correctly for signed integers. + + // div takes another BigInt of the same size and divides this by it. The value + // of this will be set to the quotient, and the return value is the remainder. + LIBC_INLINE constexpr cpp::optional<BigInt> div(const BigInt &other) { + BigInt remainder(0); + if (*this < other) { + remainder = *this; + *this = BigInt(0); + return remainder; + } + if (other == 1) { + return remainder; + } + if (other == 0) { return cpp::nullopt; - if (LIBC_UNLIKELY(divider == BigInt::one())) - return BigInt::zero(); - Division result; - if constexpr (SIGNED) - result = divide_signed(*this, divider); - else - result = divide_unsigned(*this, divider); - *this = result.quotient; - return result.remainder; + } + + BigInt quotient(0); + BigInt subtractor = other; + int cur_bit = static_cast<int>(subtractor.clz() - this->clz()); + subtractor.shift_left(cur_bit); + + for (; cur_bit >= 0 && *this > 0; --cur_bit, subtractor.shift_right(1)) { + if (*this >= subtractor) { + this->sub(subtractor); + quotient = quotient | (BigInt(1) << cur_bit); + } + } + remainder = *this; + *this = quotient; + return remainder; } // Efficiently perform BigInt / (x * 2^e), where x is a half-word-size @@ -598,16 +496,19 @@ struct BigInt { // computation of each step is now properly contained within WordType. // And finally we perform some extra alignment steps for the remaining bits. LIBC_INLINE constexpr cpp::optional<BigInt> - div_uint_half_times_pow_2(multiword::half_width_t<WordType> x, size_t e) { - BigInt remainder; - if (x == 0) + div_uint_half_times_pow_2(internal::half_width_t<WordType> x, size_t e) { + BigInt remainder(0); + + if (x == 0) { return cpp::nullopt; + } if (e >= Bits) { remainder = *this; - *this = BigInt<Bits, false, WordType>(); + *this = BigInt<Bits, false, WordType>(0); return remainder; } - BigInt quotient; + + BigInt quotient(0); WordType x_word = static_cast<WordType>(x); constexpr size_t LOG2_WORD_SIZE = cpp::bit_width(WORD_SIZE) - 1; constexpr size_t HALF_WORD_SIZE = WORD_SIZE >> 1; @@ -732,22 +633,189 @@ struct BigInt { return *this; } - LIBC_INLINE constexpr BigInt &operator<<=(size_t s) { - val = multiword::shift<multiword::LEFT, SIGNED>(val, s); - return *this; + // TODO: remove and use cpp::countl_zero below. + [[nodiscard]] LIBC_INLINE constexpr int clz() const { + constexpr int word_digits = cpp::numeric_limits<word_type>::digits; + int leading_zeroes = 0; + for (auto i = val.size(); i > 0;) { + --i; + const int zeroes = cpp::countl_zero(val[i]); + leading_zeroes += zeroes; + if (zeroes != word_digits) + break; + } + return leading_zeroes; + } + + // TODO: remove and use cpp::countr_zero below. + [[nodiscard]] LIBC_INLINE constexpr int ctz() const { + constexpr int word_digits = cpp::numeric_limits<word_type>::digits; + int trailing_zeroes = 0; + for (auto word : val) { + const int zeroes = cpp::countr_zero(word); + trailing_zeroes += zeroes; + if (zeroes != word_digits) + break; + } + return trailing_zeroes; + } + + LIBC_INLINE constexpr void shift_left(size_t s) { + if constexpr (Bits == WORD_SIZE) { + // Use native types if possible. + if (s >= WORD_SIZE) { + val[0] = 0; + return; + } + val[0] <<= s; + return; + } + if constexpr ((Bits == 64) && (WORD_SIZE == 32)) { + // Use builtin 64 bits for 32-bit base type if available; + if (s >= 64) { + val[0] = 0; + val[1] = 0; + return; + } + uint64_t tmp = uint64__t(val[0]) + (uint64_t(val[1]) << 62); + tmp <<= s; + val[0] = uint32_t(tmp); + val[1] = uint32_t(tmp >> 32); + return; + } +#ifdef LIBC_TYPES_HAS_INT128 + if constexpr ((Bits == 128) && (WORD_SIZE == 64)) { + // Use builtin 128 bits if available; + if (s >= 128) { + val[0] = 0; + val[1] = 0; + return; + } + __uint128_t tmp = __uint128_t(val[0]) + (__uint128_t(val[1]) << 64); + tmp <<= s; + val[0] = uint64_t(tmp); + val[1] = uint64_t(tmp >> 64); + return; + } +#endif // LIBC_TYPES_HAS_INT128 + if (LIBC_UNLIKELY(s == 0)) + return; + + const size_t drop = s / WORD_SIZE; // Number of words to drop + const size_t shift = s % WORD_SIZE; // Bits to shift in the remaining words. + size_t i = WORD_COUNT; + + if (drop < WORD_COUNT) { + i = WORD_COUNT - 1; + if (shift > 0) { + for (size_t j = WORD_COUNT - 1 - drop; j > 0; --i, --j) { + val[i] = (val[j] << shift) | (val[j - 1] >> (WORD_SIZE - shift)); + } + val[i] = val[0] << shift; + } else { + for (size_t j = WORD_COUNT - 1 - drop; j > 0; --i, --j) { + val[i] = val[j]; + } + val[i] = val[0]; + } + } + + for (size_t j = 0; j < i; ++j) { + val[j] = 0; + } } LIBC_INLINE constexpr BigInt operator<<(size_t s) const { - return BigInt(multiword::shift<multiword::LEFT, SIGNED>(val, s)); + BigInt result(*this); + result.shift_left(s); + return result; } - LIBC_INLINE constexpr BigInt &operator>>=(size_t s) { - val = multiword::shift<multiword::RIGHT, SIGNED>(val, s); + LIBC_INLINE constexpr BigInt &operator<<=(size_t s) { + shift_left(s); return *this; } + LIBC_INLINE constexpr void shift_right(size_t s) { + if constexpr ((Bits == 64) && (WORD_SIZE == 32)) { + // Use builtin 64 bits if available; + if (s >= 64) { + val[0] = 0; + val[1] = 0; + return; + } + uint64_t tmp = uint64_t(val[0]) + (uint64_t(val[1]) << 32); + if constexpr (Signed) { + tmp = static_cast<uint64_t>(static_cast<int64_t>(tmp) >> s); + } else { + tmp >>= s; + } + val[0] = uint32_t(tmp); + val[1] = uint32_t(tmp >> 32); + return; + } +#ifdef LIBC_TYPES_HAS_INT128 + if constexpr ((Bits == 128) && (WORD_SIZE == 64)) { + // Use builtin 128 bits if available; + if (s >= 128) { + val[0] = 0; + val[1] = 0; + return; + } + __uint128_t tmp = __uint128_t(val[0]) + (__uint128_t(val[1]) << 64); + if constexpr (Signed) { + tmp = static_cast<__uint128_t>(static_cast<__int128_t>(tmp) >> s); + } else { + tmp >>= s; + } + val[0] = uint64_t(tmp); + val[1] = uint64_t(tmp >> 64); + return; + } +#endif // LIBC_TYPES_HAS_INT128 + + if (LIBC_UNLIKELY(s == 0)) + return; + const size_t drop = s / WORD_SIZE; // Number of words to drop + const size_t shift = s % WORD_SIZE; // Bit shift in the remaining words. + + size_t i = 0; + WordType sign = Signed ? is_neg() : 0; + + if (drop < WORD_COUNT) { + if (shift > 0) { + for (size_t j = drop; j < WORD_COUNT - 1; ++i, ++j) { + val[i] = (val[j] >> shift) | (val[j + 1] << (WORD_SIZE - shift)); + } + if constexpr (Signed) { + val[i] = static_cast<WordType>( + static_cast<cpp::make_signed_t<WordType>>(val[WORD_COUNT - 1]) >> + shift); + } else { + val[i] = val[WORD_COUNT - 1] >> shift; + } + ++i; + } else { + for (size_t j = drop; j < WORD_COUNT; ++i, ++j) { + val[i] = val[j]; + } + } + } + + for (; i < WORD_COUNT; ++i) { + val[i] = sign; + } + } + LIBC_INLINE constexpr BigInt operator>>(size_t s) const { - return BigInt(multiword::shift<multiword::RIGHT, SIGNED>(val, s)); + BigInt result(*this); + result.shift_right(s); + return result; + } + + LIBC_INLINE constexpr BigInt &operator>>=(size_t s) { + shift_right(s); + return *this; } #define DEFINE_BINOP(OP) \ @@ -765,9 +833,10 @@ struct BigInt { return lhs; \ } - DEFINE_BINOP(&) // & and &= - DEFINE_BINOP(|) // | and |= - DEFINE_BINOP(^) // ^ and ^= + DEFINE_BINOP(&) + DEFINE_BINOP(|) + DEFINE_BINOP(^) + #undef DEFINE_BINOP LIBC_INLINE constexpr BigInt operator~() const { @@ -778,8 +847,8 @@ struct BigInt { } LIBC_INLINE constexpr BigInt operator-() const { - BigInt result(*this); - result.negate(); + BigInt result = ~(*this); + result.add(BigInt(1)); return result; } @@ -796,6 +865,24 @@ struct BigInt { return !(lhs == rhs); } +private: + LIBC_INLINE friend constexpr int cmp(const BigInt &lhs, const BigInt &rhs) { + const auto compare = [](WordType a, WordType b) { + return a == b ? 0 : a > b ? 1 : -1; + }; + if constexpr (Signed) { + const bool lhs_is_neg = lhs.is_neg(); + const bool rhs_is_neg = rhs.is_neg(); + if (lhs_is_neg != rhs_is_neg) + return rhs_is_neg ? 1 : -1; + } + for (size_t i = WORD_COUNT; i-- > 0;) + if (auto cmp = compare(lhs[i], rhs[i]); cmp != 0) + return cmp; + return 0; + } + +public: LIBC_INLINE friend constexpr bool operator>(const BigInt &lhs, const BigInt &rhs) { return cmp(lhs, rhs) > 0; @@ -814,24 +901,24 @@ struct BigInt { } LIBC_INLINE constexpr BigInt &operator++() { - increment(); + add(BigInt(1)); return *this; } LIBC_INLINE constexpr BigInt operator++(int) { BigInt oldval(*this); - increment(); + add(BigInt(1)); return oldval; } LIBC_INLINE constexpr BigInt &operator--() { - decrement(); + sub(BigInt(1)); return *this; } LIBC_INLINE constexpr BigInt operator--(int) { BigInt oldval(*this); - decrement(); + sub(BigInt(1)); return oldval; } @@ -843,117 +930,9 @@ struct BigInt { // Return the i-th word of the number. LIBC_INLINE constexpr WordType &operator[](size_t i) { return val[i]; } -private: - LIBC_INLINE friend constexpr int cmp(const BigInt &lhs, const BigInt &rhs) { - constexpr auto compare = [](WordType a, WordType b) { - return a == b ? 0 : a > b ? 1 : -1; - }; - if constexpr (Signed) { - const bool lhs_is_neg = lhs.is_neg(); - const bool rhs_is_neg = rhs.is_neg(); - if (lhs_is_neg != rhs_is_neg) - return rhs_is_neg ? 1 : -1; - } - for (size_t i = WORD_COUNT; i-- > 0;) - if (auto cmp = compare(lhs[i], rhs[i]); cmp != 0) - return cmp; - return 0; - } - - LIBC_INLINE constexpr void bitwise_not() { - for (auto &part : val) - part = ~part; - } - - LIBC_INLINE constexpr void negate() { - bitwise_not(); - increment(); - } + LIBC_INLINE WordType *data() { return val; } - LIBC_INLINE constexpr void increment() { - multiword::add_with_carry(val, cpp::array<WordType, 1>{1}); - } - - LIBC_INLINE constexpr void decrement() { - multiword::add_with_carry(val, cpp::array<WordType, 1>{1}); - } - - LIBC_INLINE constexpr void extend(size_t index, bool is_neg) { - const WordType value = is_neg ? cpp::numeric_limits<WordType>::max() - : cpp::numeric_limits<WordType>::min(); - for (size_t i = index; i < WORD_COUNT; ++i) - val[i] = value; - } - - LIBC_INLINE constexpr bool get_msb() const { - return val.back() >> (WORD_SIZE - 1); - } - - LIBC_INLINE constexpr void set_msb() { - val.back() |= mask_leading_ones<WordType, 1>(); - } - - LIBC_INLINE constexpr void clear_msb() { - val.back() &= mask_trailing_ones<WordType, WORD_SIZE - 1>(); - } - - LIBC_INLINE constexpr void set_bit(size_t i) { - const size_t word_index = i / WORD_SIZE; - val[word_index] |= WordType(1) << (i % WORD_SIZE); - } - - LIBC_INLINE constexpr static Division divide_unsigned(const BigInt ÷nd, - const BigInt ÷r) { - BigInt remainder = dividend; - BigInt quotient; - if (remainder >= divider) { - BigInt subtractor = divider; - int cur_bit = multiword::countl_zero(subtractor.val) - - multiword::countl_zero(remainder.val); - subtractor <<= cur_bit; - for (; cur_bit >= 0 && remainder > 0; --cur_bit, subtractor >>= 1) { - if (remainder < subtractor) - continue; - remainder -= subtractor; - quotient.set_bit(cur_bit); - } - } - return Division{quotient, remainder}; - } - - LIBC_INLINE constexpr static Division divide_signed(const BigInt ÷nd, - const BigInt ÷r) { - // Special case because it is not possible to negate the min value of a - // signed integer. - if (dividend == min() && divider == min()) - return Division{one(), zero()}; - // 1. Convert the dividend and divisor to unsigned representation. - unsigned_type udividend(dividend); - unsigned_type udivider(divider); - // 2. Negate the dividend if it's negative, and similarly for the divisor. - const bool dividend_is_neg = dividend.is_neg(); - const bool divider_is_neg = divider.is_neg(); - if (dividend_is_neg) - udividend.negate(); - if (divider_is_neg) - udivider.negate(); - // 3. Use unsigned multiword division algorithm. - const auto unsigned_result = divide_unsigned(udividend, udivider); - // 4. Convert the quotient and remainder to signed representation. - Division result; - result.quotient = signed_type(unsigned_result.quotient); - result.remainder = signed_type(unsigned_result.remainder); - // 5. Negate the quotient if the dividend and divisor had opposite signs. - if (dividend_is_neg != divider_is_neg) - result.quotient.negate(); - // 6. Negate the remainder if the dividend was negative. - if (dividend_is_neg) - result.remainder.negate(); - return result; - } - - friend signed_type; - friend unsigned_type; + LIBC_INLINE const WordType *data() const { return val; } }; namespace internal { @@ -983,8 +962,10 @@ using Int = BigInt<Bits, true, internal::WordTypeSelectorT<Bits>>; // Provides limits of U/Int<128>. template <> class cpp::numeric_limits<UInt<128>> { public: - LIBC_INLINE static constexpr UInt<128> max() { return UInt<128>::max(); } - LIBC_INLINE static constexpr UInt<128> min() { return UInt<128>::min(); } + LIBC_INLINE static constexpr UInt<128> max() { + return UInt<128>({0xffff'ffff'ffff'ffff, 0xffff'ffff'ffff'ffff}); + } + LIBC_INLINE static constexpr UInt<128> min() { return UInt<128>(0); } // Meant to match std::numeric_limits interface. // NOLINTNEXTLINE(readability-identifier-naming) LIBC_INLINE_VAR static constexpr int digits = 128; @@ -992,8 +973,12 @@ template <> class cpp::numeric_limits<UInt<128>> { template <> class cpp::numeric_limits<Int<128>> { public: - LIBC_INLINE static constexpr Int<128> max() { return Int<128>::max(); } - LIBC_INLINE static constexpr Int<128> min() { return Int<128>::min(); } + LIBC_INLINE static constexpr Int<128> max() { + return Int<128>({0xffff'ffff'ffff'ffff, 0x7fff'ffff'ffff'ffff}); + } + LIBC_INLINE static constexpr Int<128> min() { + return Int<128>({0, 0x8000'0000'0000'0000}); + } // Meant to match std::numeric_limits interface. // NOLINTNEXTLINE(readability-identifier-naming) LIBC_INLINE_VAR static constexpr int digits = 128; @@ -1127,28 +1112,30 @@ has_single_bit(T value) { template <typename T> [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> countr_zero(const T &value) { - return multiword::countr_zero(value.val); + return value.ctz(); } // Specialization of cpp::countl_zero ('bit.h') for BigInt. template <typename T> [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> countl_zero(const T &value) { - return multiword::countl_zero(value.val); + return value.clz(); } // Specialization of cpp::countl_one ('bit.h') for BigInt. template <typename T> [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> countl_one(T value) { - return multiword::countl_one(value.val); + // TODO : Implement a faster version not involving operator~. + return cpp::countl_zero<T>(~value); } // Specialization of cpp::countr_one ('bit.h') for BigInt. template <typename T> [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> countr_one(T value) { - return multiword::countr_one(value.val); + // TODO : Implement a faster version not involving operator~. + return cpp::countr_zero<T>(~value); } // Specialization of cpp::bit_width ('bit.h') for BigInt. @@ -1195,59 +1182,65 @@ rotr(T value, int rotate) { template <typename T, size_t count> LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> mask_trailing_ones() { - static_assert(!T::SIGNED && count <= T::BITS); - if (count == T::BITS) - return T::all_ones(); - constexpr size_t QUOTIENT = count / T::WORD_SIZE; - constexpr size_t REMAINDER = count % T::WORD_SIZE; - T out; // zero initialized - for (size_t i = 0; i <= QUOTIENT; ++i) - out[i] = i < QUOTIENT - ? -1 - : mask_trailing_ones<typename T::word_type, REMAINDER>(); + static_assert(!T::SIGNED); + if (count == 0) + return T(); + constexpr unsigned T_BITS = CHAR_BIT * sizeof(T); + static_assert(count <= T_BITS && "Invalid bit index"); + using word_type = typename T::word_type; + T out; + constexpr int CHUNK_INDEX_CONTAINING_BIT = + static_cast<int>(count / T::WORD_SIZE); + int index = 0; + for (auto &word : out.val) { + if (index < CHUNK_INDEX_CONTAINING_BIT) + word = -1; + else if (index > CHUNK_INDEX_CONTAINING_BIT) + word = 0; + else + word = mask_trailing_ones<word_type, count % T::WORD_SIZE>(); + ++index; + } return out; } // Specialization of mask_leading_ones ('math_extras.h') for BigInt. template <typename T, size_t count> LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> mask_leading_ones() { - static_assert(!T::SIGNED && count <= T::BITS); - if (count == T::BITS) - return T::all_ones(); - constexpr size_t QUOTIENT = (T::BITS - count - 1U) / T::WORD_SIZE; - constexpr size_t REMAINDER = count % T::WORD_SIZE; - T out; // zero initialized - for (size_t i = QUOTIENT; i < T::WORD_COUNT; ++i) - out[i] = i > QUOTIENT - ? -1 - : mask_leading_ones<typename T::word_type, REMAINDER>(); + static_assert(!T::SIGNED); + if (count == 0) + return T(); + constexpr unsigned T_BITS = CHAR_BIT * sizeof(T); + static_assert(count <= T_BITS && "Invalid bit index"); + using word_type = typename T::word_type; + T out; + constexpr int CHUNK_INDEX_CONTAINING_BIT = + static_cast<int>((T::BITS - count - 1ULL) / T::WORD_SIZE); + int index = 0; + for (auto &word : out.val) { + if (index < CHUNK_INDEX_CONTAINING_BIT) + word = 0; + else if (index > CHUNK_INDEX_CONTAINING_BIT) + word = -1; + else + word = mask_leading_ones<word_type, count % T::WORD_SIZE>(); + ++index; + } return out; } -// Specialization of mask_trailing_zeros ('math_extras.h') for BigInt. -template <typename T, size_t count> -LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> -mask_trailing_zeros() { - return mask_leading_ones<T, T::BITS - count>(); -} - -// Specialization of mask_leading_zeros ('math_extras.h') for BigInt. -template <typename T, size_t count> -LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> -mask_leading_zeros() { - return mask_trailing_ones<T, T::BITS - count>(); -} - // Specialization of count_zeros ('math_extras.h') for BigInt. template <typename T> -[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> +[[nodiscard]] +LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> count_zeros(T value) { return cpp::popcount(~value); } // Specialization of first_leading_zero ('math_extras.h') for BigInt. template <typename T> -[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> +[[nodiscard]] +LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> first_leading_zero(T value) { return value == cpp::numeric_limits<T>::max() ? 0 : cpp::countl_one(value) + 1; @@ -1255,14 +1248,16 @@ first_leading_zero(T value) { // Specialization of first_leading_one ('math_extras.h') for BigInt. template <typename T> -[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> +[[nodiscard]] +LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> first_leading_one(T value) { return first_leading_zero(~value); } // Specialization of first_trailing_zero ('math_extras.h') for BigInt. template <typename T> -[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> +[[nodiscard]] +LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> first_trailing_zero(T value) { return value == cpp::numeric_limits<T>::max() ? 0 : cpp::countr_zero(~value) + 1; @@ -1270,7 +1265,8 @@ first_trailing_zero(T value) { // Specialization of first_trailing_one ('math_extras.h') for BigInt. template <typename T> -[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> +[[nodiscard]] +LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> first_trailing_one(T value) { return value == cpp::numeric_limits<T>::max() ? 0 : cpp::countr_zero(value) + 1; diff --git a/libc/src/__support/float_to_string.h b/libc/src/__support/float_to_string.h index 4c59cfd99c2e6c..1287c3e9a84fac 100644 --- a/libc/src/__support/float_to_string.h +++ b/libc/src/__support/float_to_string.h @@ -689,7 +689,7 @@ template <> class FloatToString<long double> { wide_int float_as_int = mantissa; - float_as_int <<= exponent; + float_as_int.shift_left(exponent); int_block_index = 0; while (float_as_int > 0) { @@ -708,11 +708,10 @@ template <> class FloatToString<long double> { const int SHIFT_AMOUNT = FLOAT_AS_INT_WIDTH + exponent; static_assert(EXTRA_INT_WIDTH >= sizeof(long double) * 8); - float_as_fixed <<= SHIFT_AMOUNT; + float_as_fixed.shift_left(SHIFT_AMOUNT); // If there are still digits above the decimal point, handle those. - if (cpp::countl_zero(float_as_fixed) < - static_cast<int>(EXTRA_INT_WIDTH)) { + if (float_as_fixed.clz() < static_cast<int>(EXTRA_INT_WIDTH)) { UInt<EXTRA_INT_WIDTH> above_decimal_point = float_as_fixed >> FLOAT_AS_INT_WIDTH; diff --git a/libc/src/__support/integer_literals.h b/libc/src/__support/integer_literals.h index e99799c3512e2f..de1f88fbd3f3f5 100644 --- a/libc/src/__support/integer_literals.h +++ b/libc/src/__support/integer_literals.h @@ -151,15 +151,12 @@ template <size_t N> struct Parser<LIBC_NAMESPACE::UInt<N>> { template <typename T> LIBC_INLINE constexpr T parse_with_prefix(const char *ptr) { using P = Parser<T>; - if (ptr == nullptr) - return T(); - if (ptr[0] == '0') { - if (ptr[1] == 'b') - return P::template parse<2>(ptr + 2); - if (ptr[1] == 'x') - return P::template parse<16>(ptr + 2); - } - return P::template parse<10>(ptr); + if (ptr[0] == '0' && ptr[1] == 'x') + return P::template parse<16>(ptr + 2); + else if (ptr[0] == '0' && ptr[1] == 'b') + return P::template parse<2>(ptr + 2); + else + return P::template parse<10>(ptr); } } // namespace internal @@ -172,16 +169,6 @@ LIBC_INLINE constexpr auto operator""_u256(const char *x) { return internal::parse_with_prefix<UInt<256>>(x); } -template <typename T> LIBC_INLINE constexpr T parse_bigint(const char *ptr) { - if (ptr == nullptr) - return T(); - if (ptr[0] == '-' || ptr[0] == '+') { - auto positive = internal::parse_with_prefix<T>(ptr + 1); - return ptr[0] == '-' ? -positive : positive; - } - return internal::parse_with_prefix<T>(ptr); -} - } // namespace LIBC_NAMESPACE #endif // LLVM_LIBC_SRC___SUPPORT_INTEGER_LITERALS_H diff --git a/libc/src/__support/math_extras.h b/libc/src/__support/math_extras.h index bb6424bfa8e4d4..70a8800b285d02 100644 --- a/libc/src/__support/math_extras.h +++ b/libc/src/__support/math_extras.h @@ -10,9 +10,9 @@ #ifndef LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H #define LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H -#include "src/__support/CPP/bit.h" // countl_one, countr_zero -#include "src/__support/CPP/limits.h" // CHAR_BIT, numeric_limits -#include "src/__support/CPP/type_traits.h" // is_unsigned_v, is_constant_evaluated +#include "src/__support/CPP/bit.h" // countl_one, countr_zero +#include "src/__support/CPP/limits.h" // CHAR_BIT, numeric_limits +#include "src/__support/CPP/type_traits.h" // is_unsigned_v #include "src/__support/macros/attributes.h" // LIBC_INLINE namespace LIBC_NAMESPACE { @@ -32,94 +32,199 @@ mask_trailing_ones() { template <typename T, size_t count> LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> mask_leading_ones() { - return T(~mask_trailing_ones<T, CHAR_BIT * sizeof(T) - count>()); + constexpr T MASK(mask_trailing_ones<T, CHAR_BIT * sizeof(T) - count>()); + return T(~MASK); // bitwise NOT performs integer promotion. } -// Create a bitmask with the count right-most bits set to 0, and all other bits -// set to 1. Only unsigned types are allowed. -template <typename T, size_t count> -LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> -mask_trailing_zeros() { - return mask_leading_ones<T, CHAR_BIT * sizeof(T) - count>(); +// Add with carry +template <typename T> struct SumCarry { + T sum; + T carry; +}; + +// This version is always valid for constexpr. +template <typename T> +LIBC_INLINE constexpr cpp::enable_if_t< + cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, SumCarry<T>> +add_with_carry_const(T a, T b, T carry_in) { + T tmp = a + carry_in; + T sum = b + tmp; + T carry_out = (sum < b) + (tmp < a); + return {sum, carry_out}; } -// Create a bitmask with the count left-most bits set to 0, and all other bits -// set to 1. Only unsigned types are allowed. -template <typename T, size_t count> -LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> -mask_leading_zeros() { - return mask_trailing_ones<T, CHAR_BIT * sizeof(T) - count>(); +template <typename T> +LIBC_INLINE constexpr cpp::enable_if_t< + cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, SumCarry<T>> +add_with_carry(T a, T b, T carry_in) { + return add_with_carry_const<T>(a, b, carry_in); +} + +#if __has_builtin(__builtin_addc) +// https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins + +template <> +LIBC_INLINE constexpr SumCarry<unsigned char> +add_with_carry<unsigned char>(unsigned char a, unsigned char b, + unsigned char carry_in) { + if (__builtin_is_constant_evaluated()) { + return add_with_carry_const<unsigned char>(a, b, carry_in); + } else { + SumCarry<unsigned char> result{0, 0}; + result.sum = __builtin_addcb(a, b, carry_in, &result.carry); + return result; + } +} + +template <> +LIBC_INLINE constexpr SumCarry<unsigned short> +add_with_carry<unsigned short>(unsigned short a, unsigned short b, + unsigned short carry_in) { + if (__builtin_is_constant_evaluated()) { + return add_with_carry_const<unsigned short>(a, b, carry_in); + } else { + SumCarry<unsigned short> result{0, 0}; + result.sum = __builtin_addcs(a, b, carry_in, &result.carry); + return result; + } +} + +template <> +LIBC_INLINE constexpr SumCarry<unsigned int> +add_with_carry<unsigned int>(unsigned int a, unsigned int b, + unsigned int carry_in) { + if (__builtin_is_constant_evaluated()) { + return add_with_carry_const<unsigned int>(a, b, carry_in); + } else { + SumCarry<unsigned int> result{0, 0}; + result.sum = __builtin_addc(a, b, carry_in, &result.carry); + return result; + } +} + +template <> +LIBC_INLINE constexpr SumCarry<unsigned long> +add_with_carry<unsigned long>(unsigned long a, unsigned long b, + unsigned long carry_in) { + if (__builtin_is_constant_evaluated()) { + return add_with_carry_const<unsigned long>(a, b, carry_in); + } else { + SumCarry<unsigned long> result{0, 0}; + result.sum = __builtin_addcl(a, b, carry_in, &result.carry); + return result; + } +} + +template <> +LIBC_INLINE constexpr SumCarry<unsigned long long> +add_with_carry<unsigned long long>(unsigned long long a, unsigned long long b, + unsigned long long carry_in) { + if (__builtin_is_constant_evaluated()) { + return add_with_carry_const<unsigned long long>(a, b, carry_in); + } else { + SumCarry<unsigned long long> result{0, 0}; + result.sum = __builtin_addcll(a, b, carry_in, &result.carry); + return result; + } } -// Returns whether 'a + b' overflows, the result is stored in 'res'. +#endif // __has_builtin(__builtin_addc) + +// Subtract with borrow +template <typename T> struct DiffBorrow { + T diff ; + T borrow; +}; + +// This version is always valid for constexpr. template <typename T> -[[nodiscard]] LIBC_INLINE constexpr bool add_overflow(T a, T b, T &res) { - return __builtin_add_overflow(a, b, &res); +LIBC_INLINE constexpr cpp::enable_if_t< + cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, DiffBorrow<T>> +sub_with_borrow_const(T a, T b, T borrow_in) { + T tmp = a - b; + T diff = tmp - borrow_in; + T borrow_out = ( diff > tmp) + (tmp > a); + return { diff , borrow_out}; } -// Returns whether 'a - b' overflows, the result is stored in 'res'. +// This version is not always valid for constepxr because it's overriden below +// if builtins are available. template <typename T> -[[nodiscard]] LIBC_INLINE constexpr bool sub_overflow(T a, T b, T &res) { - return __builtin_sub_overflow(a, b, &res); +LIBC_INLINE constexpr cpp::enable_if_t< + cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, DiffBorrow<T>> +sub_with_borrow(T a, T b, T borrow_in) { + return sub_with_borrow_const<T>(a, b, borrow_in); } -#define RETURN_IF(TYPE, BUILTIN) \ - if constexpr (cpp::is_same_v<T, TYPE>) \ - return BUILTIN(a, b, carry_in, carry_out); +#if __has_builtin(__builtin_subc) +// https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins -// Returns the result of 'a + b' taking into account 'carry_in'. -// The carry out is stored in 'carry_out' it not 'nullptr', dropped otherwise. -// We keep the pass by pointer interface for consistency with the intrinsic. -template <typename T> -[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> -add_with_carry(T a, T b, T carry_in, T &carry_out) { - if constexpr (!cpp::is_constant_evaluated()) { -#if __has_builtin(__builtin_addcb) - RETURN_IF(unsigned char, __builtin_addcb) -#elif __has_builtin(__builtin_addcs) - RETURN_IF(unsigned short, __builtin_addcs) -#elif __has_builtin(__builtin_addc) - RETURN_IF(unsigned int, __builtin_addc) -#elif __has_builtin(__builtin_addcl) - RETURN_IF(unsigned long, __builtin_addcl) -#elif __has_builtin(__builtin_addcll) - RETURN_IF(unsigned long long, __builtin_addcll) -#endif +template <> +LIBC_INLINE constexpr DiffBorrow<unsigned char> +sub_with_borrow<unsigned char>(unsigned char a, unsigned char b, + unsigned char borrow_in) { + if (__builtin_is_constant_evaluated()) { + return sub_with_borrow_const<unsigned char>(a, b, borrow_in); + } else { + DiffBorrow<unsigned char> result{0, 0}; + result. diff = __builtin_subcb(a, b, borrow_in, &result.borrow); + return result; } - T sum; - T carry1 = add_overflow(a, b, sum); - T carry2 = add_overflow(sum, carry_in, sum); - carry_out = carry1 | carry2; - return sum; } -// Returns the result of 'a - b' taking into account 'carry_in'. -// The carry out is stored in 'carry_out' it not 'nullptr', dropped otherwise. -// We keep the pass by pointer interface for consistency with the intrinsic. -template <typename T> -[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> -sub_with_borrow(T a, T b, T carry_in, T &carry_out) { - if constexpr (!cpp::is_constant_evaluated()) { -#if __has_builtin(__builtin_subcb) - RETURN_IF(unsigned char, __builtin_subcb) -#elif __has_builtin(__builtin_subcs) - RETURN_IF(unsigned short, __builtin_subcs) -#elif __has_builtin(__builtin_subc) - RETURN_IF(unsigned int, __builtin_subc) -#elif __has_builtin(__builtin_subcl) - RETURN_IF(unsigned long, __builtin_subcl) -#elif __has_builtin(__builtin_subcll) - RETURN_IF(unsigned long long, __builtin_subcll) -#endif +template <> +LIBC_INLINE constexpr DiffBorrow<unsigned short> +sub_with_borrow<unsigned short>(unsigned short a, unsigned short b, + unsigned short borrow_in) { + if (__builtin_is_constant_evaluated()) { + return sub_with_borrow_const<unsigned short>(a, b, borrow_in); + } else { + DiffBorrow<unsigned short> result{0, 0}; + result. diff = __builtin_subcs(a, b, borrow_in, &result.borrow); + return result; + } +} + +template <> +LIBC_INLINE constexpr DiffBorrow<unsigned int> +sub_with_borrow<unsigned int>(unsigned int a, unsigned int b, + unsigned int borrow_in) { + if (__builtin_is_constant_evaluated()) { + return sub_with_borrow_const<unsigned int>(a, b, borrow_in); + } else { + DiffBorrow<unsigned int> result{0, 0}; + result. diff = __builtin_subc(a, b, borrow_in, &result.borrow); + return result; + } +} + +template <> +LIBC_INLINE constexpr DiffBorrow<unsigned long> +sub_with_borrow<unsigned long>(unsigned long a, unsigned long b, + unsigned long borrow_in) { + if (__builtin_is_constant_evaluated()) { + return sub_with_borrow_const<unsigned long>(a, b, borrow_in); + } else { + DiffBorrow<unsigned long> result{0, 0}; + result. diff = __builtin_subcl(a, b, borrow_in, &result.borrow); + return result; + } +} + +template <> +LIBC_INLINE constexpr DiffBorrow<unsigned long long> +sub_with_borrow<unsigned long long>(unsigned long long a, unsigned long long b, + unsigned long long borrow_in) { + if (__builtin_is_constant_evaluated()) { + return sub_with_borrow_const<unsigned long long>(a, b, borrow_in); + } else { + DiffBorrow<unsigned long long> result{0, 0}; + result. diff = __builtin_subcll(a, b, borrow_in, &result.borrow); + return result; } - T sub; - T carry1 = sub_overflow(a, b, sub); - T carry2 = sub_overflow(sub, carry_in, sub); - carry_out = carry1 | carry2; - return sub; } -#undef RETURN_IF +#endif // __has_builtin(__builtin_subc) template <typename T> [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int> diff --git a/libc/src/__support/number_pair.h b/libc/src/__support/number_pair.h index 2f713fc03520f9..ee6667b1299fe8 100644 --- a/libc/src/__support/number_pair.h +++ b/libc/src/__support/number_pair.h @@ -20,6 +20,17 @@ template <typename T> struct NumberPair { T hi = T(0); }; +template <typename T> +cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, + NumberPair<T>> constexpr split(T a) { + constexpr size_t HALF_BIT_WIDTH = sizeof(T) * 4; + constexpr T LOWER_HALF_MASK = (T(1) << HALF_BIT_WIDTH) - T(1); + NumberPair<T> result; + result.lo = a & LOWER_HALF_MASK; + result.hi = a >> HALF_BIT_WIDTH; + return result; +} + } // namespace LIBC_NAMESPACE #endif // LLVM_LIBC_SRC___SUPPORT_NUMBER_PAIR_H diff --git a/libc/test/src/__support/integer_literals_test.cpp b/libc/test/src/__support/integer_literals_test.cpp index cbc906aa7c99ad..5298cf30156e20 100644 --- a/libc/test/src/__support/integer_literals_test.cpp +++ b/libc/test/src/__support/integer_literals_test.cpp @@ -133,24 +133,3 @@ TEST(LlvmLibcIntegerLiteralTest, u256) { U256_MAX, 0xFFFFFFFF'FFFFFFFF'FFFFFFFF'FFFFFFFF'FFFFFFFF'FFFFFFFF'FFFFFFFF'FFFFFFFF_u256); } - -TEST(LlvmLibcIntegerLiteralTest, parse_bigint) { - using T = LIBC_NAMESPACE::Int<128>; - struct { - const char *str; - T expected; - } constexpr TEST_CASES[] = { - {"0", 0}, {"-1", -1}, {"+1", 1}, {"-0xFF", -255}, {"-0b11", -3}, - }; - for (auto tc : TEST_CASES) { - T actual = LIBC_NAMESPACE::parse_bigint<T>(tc.str); - EXPECT_EQ(actual, tc.expected); - } -} - -TEST(LlvmLibcIntegerLiteralTest, parse_bigint_invalid) { - using T = LIBC_NAMESPACE::Int<128>; - const T expected; // default construction - EXPECT_EQ(LIBC_NAMESPACE::parse_bigint<T>(nullptr), expected); - EXPECT_EQ(LIBC_NAMESPACE::parse_bigint<T>(""), expected); -} diff --git a/libc/test/src/__support/math_extras_test.cpp b/libc/test/src/__support/math_extras_test.cpp index 401e631ea4bac1..e88b3e1d6b687b 100644 --- a/libc/test/src/__support/math_extras_test.cpp +++ b/libc/test/src/__support/math_extras_test.cpp @@ -101,61 +101,4 @@ TYPED_TEST(LlvmLibcBitTest, CountZeros, UnsignedTypesNoBigInt) { EXPECT_EQ(count_zeros<T>(cpp::numeric_limits<T>::max() >> i), i); } -using UnsignedTypes = testing::TypeList< -#if defined(__SIZEOF_INT128__) - __uint128_t, -#endif - unsigned char, unsigned short, unsigned int, unsigned long, - unsigned long long>; - -TYPED_TEST(LlvmLibcBlockMathExtrasTest, add_overflow, UnsignedTypes) { - constexpr T ZERO = cpp::numeric_limits<T>::min(); - constexpr T ONE(1); - constexpr T MAX = cpp::numeric_limits<T>::max(); - constexpr T BEFORE_MAX = MAX - 1; - - const struct { - T lhs; - T rhs; - T sum; - bool carry; - } TESTS[] = { - {ZERO, ONE, ONE, false}, // 0x00 + 0x01 = 0x01 - {BEFORE_MAX, ONE, MAX, false}, // 0xFE + 0x01 = 0xFF - {MAX, ONE, ZERO, true}, // 0xFF + 0x01 = 0x00 (carry) - {MAX, MAX, BEFORE_MAX, true}, // 0xFF + 0xFF = 0xFE (carry) - }; - for (auto tc : TESTS) { - T sum; - bool carry = add_overflow<T>(tc.lhs, tc.rhs, sum); - EXPECT_EQ(sum, tc.sum); - EXPECT_EQ(carry, tc.carry); - } -} - -TYPED_TEST(LlvmLibcBlockMathExtrasTest, sub_overflow, UnsignedTypes) { - constexpr T ZERO = cpp::numeric_limits<T>::min(); - constexpr T ONE(1); - constexpr T MAX = cpp::numeric_limits<T>::max(); - constexpr T BEFORE_MAX = MAX - 1; - - const struct { - T lhs; - T rhs; - T sub; - bool carry; - } TESTS[] = { - {ONE, ZERO, ONE, false}, // 0x01 - 0x00 = 0x01 - {MAX, MAX, ZERO, false}, // 0xFF - 0xFF = 0x00 - {ZERO, ONE, MAX, true}, // 0x00 - 0x01 = 0xFF (carry) - {BEFORE_MAX, MAX, MAX, true}, // 0xFE - 0xFF = 0xFF (carry) - }; - for (auto tc : TESTS) { - T sub; - bool carry = sub_overflow<T>(tc.lhs, tc.rhs, sub); - EXPECT_EQ(sub, tc.sub); - EXPECT_EQ(carry, tc.carry); - } -} - } // namespace LIBC_NAMESPACE diff --git a/libc/test/src/__support/uint_test.cpp b/libc/test/src/__support/uint_test.cpp index 5696e54c73f363..5764324ca28815 100644 --- a/libc/test/src/__support/uint_test.cpp +++ b/libc/test/src/__support/uint_test.cpp @@ -8,7 +8,6 @@ #include "src/__support/CPP/optional.h" #include "src/__support/UInt.h" -#include "src/__support/integer_literals.h" // parse_unsigned_bigint #include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128 #include "include/llvm-libc-macros/math-macros.h" // HUGE_VALF, HUGE_VALF @@ -16,195 +15,6 @@ namespace LIBC_NAMESPACE { -enum Value { ZERO, ONE, TWO, MIN, MAX }; - -template <typename T> auto create(Value value) { - switch (value) { - case ZERO: - return T(0); - case ONE: - return T(1); - case TWO: - return T(2); - case MIN: - return T::min(); - case MAX: - return T::max(); - } -} - -using Types = testing::TypeList< // -#ifdef LIBC_TYPES_HAS_INT64 - BigInt<64, false, uint64_t>, // 64-bits unsigned (1 x uint64_t) - BigInt<64, true, uint64_t>, // 64-bits signed (1 x uint64_t) -#endif -#ifdef LIBC_TYPES_HAS_INT128 - BigInt<128, false, __uint128_t>, // 128-bits unsigned (1 x __uint128_t) - BigInt<128, true, __uint128_t>, // 128-bits signed (1 x __uint128_t) -#endif - BigInt<16, false, uint16_t>, // 16-bits unsigned (1 x uint16_t) - BigInt<16, true, uint16_t>, // 16-bits signed (1 x uint16_t) - BigInt<64, false, uint16_t>, // 64-bits unsigned (4 x uint16_t) - BigInt<64, true, uint16_t> // 64-bits signed (4 x uint16_t) - >; - -#define ASSERT_SAME(A, B) ASSERT_TRUE((A) == (B)) - -TYPED_TEST(LlvmLibcUIntClassTest, Additions, Types) { - ASSERT_SAME(create<T>(ZERO) + create<T>(ZERO), create<T>(ZERO)); - ASSERT_SAME(create<T>(ONE) + create<T>(ZERO), create<T>(ONE)); - ASSERT_SAME(create<T>(ZERO) + create<T>(ONE), create<T>(ONE)); - ASSERT_SAME(create<T>(ONE) + create<T>(ONE), create<T>(TWO)); - // 2's complement addition works for signed and unsigned types. - // - unsigned : 0xff + 0x01 = 0x00 (255 + 1 = 0) - // - signed : 0xef + 0x01 = 0xf0 (127 + 1 = -128) - ASSERT_SAME(create<T>(MAX) + create<T>(ONE), create<T>(MIN)); -} - -TYPED_TEST(LlvmLibcUIntClassTest, Subtraction, Types) { - ASSERT_SAME(create<T>(ZERO) - create<T>(ZERO), create<T>(ZERO)); - ASSERT_SAME(create<T>(ONE) - create<T>(ONE), create<T>(ZERO)); - ASSERT_SAME(create<T>(ONE) - create<T>(ZERO), create<T>(ONE)); - // 2's complement subtraction works for signed and unsigned types. - // - unsigned : 0x00 - 0x01 = 0xff ( 0 - 1 = 255) - // - signed : 0xf0 - 0x01 = 0xef (-128 - 1 = 127) - ASSERT_SAME(create<T>(MIN) - create<T>(ONE), create<T>(MAX)); -} - -TYPED_TEST(LlvmLibcUIntClassTest, Multiplication, Types) { - ASSERT_SAME(create<T>(ZERO) * create<T>(ZERO), create<T>(ZERO)); - ASSERT_SAME(create<T>(ZERO) * create<T>(ONE), create<T>(ZERO)); - ASSERT_SAME(create<T>(ONE) * create<T>(ZERO), create<T>(ZERO)); - ASSERT_SAME(create<T>(ONE) * create<T>(ONE), create<T>(ONE)); - ASSERT_SAME(create<T>(ONE) * create<T>(TWO), create<T>(TWO)); - ASSERT_SAME(create<T>(TWO) * create<T>(ONE), create<T>(TWO)); - // - unsigned : 0xff x 0xff = 0x01 (mod 0xff) - // - signed : 0xef x 0xef = 0x01 (mod 0xff) - ASSERT_SAME(create<T>(MAX) * create<T>(MAX), create<T>(ONE)); -} - -template <typename T> void print(const char *msg, T value) { - testing::tlog << msg; - IntegerToString<T, radix::Hex> buffer(value); - testing::tlog << buffer.view() << "\n"; -} - -TEST(LlvmLibcUIntClassTest, SignedAddSub) { - // Computations performed by https://www.wolframalpha.com/ - using T = BigInt<128, true, uint32_t>; - const T a = parse_bigint<T>("1927508279017230597"); - const T b = parse_bigint<T>("278789278723478925"); - const T s = parse_bigint<T>("2206297557740709522"); - // Addition - ASSERT_SAME(a + b, s); - ASSERT_SAME(b + a, s); // commutative - // Subtraction - ASSERT_SAME(a - s, -b); - ASSERT_SAME(s - a, b); -} - -TEST(LlvmLibcUIntClassTest, SignedMulDiv) { - // Computations performed by https://www.wolframalpha.com/ - using T = BigInt<128, true, uint16_t>; - struct { - const char *a; - const char *b; - const char *mul; - } const test_cases[] = {{"-4", "3", "-12"}, - {"-3", "-3", "9"}, - {"1927508279017230597", "278789278723478925", - "537368642840747885329125014794668225"}}; - for (auto tc : test_cases) { - const T a = parse_bigint<T>(tc.a); - const T b = parse_bigint<T>(tc.b); - const T mul = parse_bigint<T>(tc.mul); - // Multiplication - ASSERT_SAME(a * b, mul); - ASSERT_SAME(b * a, mul); // commutative - ASSERT_SAME(a * -b, -mul); // sign - ASSERT_SAME(-a * b, -mul); // sign - ASSERT_SAME(-a * -b, mul); // sign - // Division - ASSERT_SAME(mul / a, b); - ASSERT_SAME(mul / b, a); - ASSERT_SAME(-mul / a, -b); // sign - ASSERT_SAME(mul / -a, -b); // sign - ASSERT_SAME(-mul / -a, b); // sign - } -} - -TYPED_TEST(LlvmLibcUIntClassTest, Division, Types) { - ASSERT_SAME(create<T>(ZERO) / create<T>(ONE), create<T>(ZERO)); - ASSERT_SAME(create<T>(MAX) / create<T>(ONE), create<T>(MAX)); - ASSERT_SAME(create<T>(MAX) / create<T>(MAX), create<T>(ONE)); - ASSERT_SAME(create<T>(ONE) / create<T>(ONE), create<T>(ONE)); - if constexpr (T::SIGNED) { - // Special case found by fuzzing. - ASSERT_SAME(create<T>(MIN) / create<T>(MIN), create<T>(ONE)); - } - // - unsigned : 0xff / 0x02 = 0x7f - // - signed : 0xef / 0x02 = 0x77 - ASSERT_SAME(create<T>(MAX) / create<T>(TWO), (create<T>(MAX) >> 1)); - - using word_type = typename T::word_type; - const T zero_one_repeated = T::all_ones() / T(0xff); - const word_type pattern = word_type(~0) / word_type(0xff); - for (const word_type part : zero_one_repeated.val) { - if constexpr (T::SIGNED == false) { - EXPECT_EQ(part, pattern); - } - } -} - -TYPED_TEST(LlvmLibcUIntClassTest, is_neg, Types) { - EXPECT_FALSE(create<T>(ZERO).is_neg()); - EXPECT_FALSE(create<T>(ONE).is_neg()); - EXPECT_FALSE(create<T>(TWO).is_neg()); - EXPECT_EQ(create<T>(MIN).is_neg(), T::SIGNED); - EXPECT_FALSE(create<T>(MAX).is_neg()); -} - -TYPED_TEST(LlvmLibcUIntClassTest, Masks, Types) { - if constexpr (!T::SIGNED) { - constexpr size_t BITS = T::BITS; - // mask_trailing_ones - ASSERT_SAME((mask_trailing_ones<T, 0>()), T::zero()); - ASSERT_SAME((mask_trailing_ones<T, 1>()), T::one()); - ASSERT_SAME((mask_trailing_ones<T, BITS - 1>()), T::all_ones() >> 1); - ASSERT_SAME((mask_trailing_ones<T, BITS>()), T::all_ones()); - // mask_leading_ones - ASSERT_SAME((mask_leading_ones<T, 0>()), T::zero()); - ASSERT_SAME((mask_leading_ones<T, 1>()), T::one() << (BITS - 1)); - ASSERT_SAME((mask_leading_ones<T, BITS - 1>()), T::all_ones() - T::one()); - ASSERT_SAME((mask_leading_ones<T, BITS>()), T::all_ones()); - // mask_trailing_zeros - ASSERT_SAME((mask_trailing_zeros<T, 0>()), T::all_ones()); - ASSERT_SAME((mask_trailing_zeros<T, 1>()), T::all_ones() - T::one()); - ASSERT_SAME((mask_trailing_zeros<T, BITS - 1>()), T::one() << (BITS - 1)); - ASSERT_SAME((mask_trailing_zeros<T, BITS>()), T::zero()); - // mask_trailing_zeros - ASSERT_SAME((mask_leading_zeros<T, 0>()), T::all_ones()); - ASSERT_SAME((mask_leading_zeros<T, 1>()), T::all_ones() >> 1); - ASSERT_SAME((mask_leading_zeros<T, BITS - 1>()), T::one()); - ASSERT_SAME((mask_leading_zeros<T, BITS>()), T::zero()); - } -} - -TYPED_TEST(LlvmLibcUIntClassTest, CountBits, Types) { - if constexpr (!T::SIGNED) { - for (size_t i = 0; i <= T::BITS; ++i) { - const auto l_one = T::all_ones() << i; // 0b111...000 - const auto r_one = T::all_ones() >> i; // 0b000...111 - const int zeros = i; - const int ones = T::BITS - zeros; - ASSERT_EQ(cpp::countr_one(r_one), ones); - ASSERT_EQ(cpp::countl_one(l_one), ones); - ASSERT_EQ(cpp::countr_zero(l_one), zeros); - ASSERT_EQ(cpp::countl_zero(r_one), zeros); - } - } -} - using LL_UInt64 = UInt<64>; // We want to test UInt<128> explicitly. So, for // convenience, we use a sugar which does not conflict with the UInt128 type @@ -751,7 +561,7 @@ TEST(LlvmLibcUIntClassTest, FullMulTests) { LL_UInt##Bits a = ~LL_UInt##Bits(0); \ LL_UInt##Bits hi = a.quick_mul_hi(a); \ LL_UInt##Bits trunc = static_cast<LL_UInt##Bits>(a.ful_mul(a) >> Bits); \ - uint64_t overflow = trunc.sub_overflow(hi); \ + uint64_t overflow = trunc.sub(hi); \ EXPECT_EQ(overflow, uint64_t(0)); \ EXPECT_LE(uint64_t(trunc), uint64_t(Error)); \ } while (0) diff --git a/utils/bazel/llvm-project-overlay/libc/test/src/__support/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/test/src/__support/BUILD.bazel index c0d402a89ea3ce..4f976122967c4d 100644 --- a/utils/bazel/llvm-project-overlay/libc/test/src/__support/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/test/src/__support/BUILD.bazel @@ -87,7 +87,6 @@ libc_test( srcs = ["uint_test.cpp"], deps = [ "//libc:__support_cpp_optional", - "//libc:__support_integer_literals", "//libc:__support_macros_properties_types", "//libc:__support_uint", "//libc:llvm_libc_macros_math_macros", _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
