| //===-- A class to manipulate wide integers. --------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_LIBC_SRC___SUPPORT_UINT_H |
| #define LLVM_LIBC_SRC___SUPPORT_UINT_H |
| |
| #include "src/__support/CPP/array.h" |
| #include "src/__support/CPP/bit.h" // countl_zero |
| #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/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/number_pair.h" |
| |
| #include <stddef.h> // For size_t |
| #include <stdint.h> |
| |
| namespace LIBC_NAMESPACE { |
| |
| namespace multiword { |
| |
| // A type trait mapping unsigned integers to their half-width unsigned |
| // counterparts. |
| 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> {}; |
| #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>); |
| using half_type = half_width_t<T>; |
| return DoubleWide<half_type>( |
| half_type(value), |
| half_type(value >> cpp::numeric_limits<half_type>::digits)); |
| } |
| |
| // 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); |
| } |
| |
| // 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); |
| } |
| |
| // 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)); |
| } |
| |
| // 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(); } |
| }; |
| |
| // 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(); |
| } |
| |
| // 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(); |
| } |
| |
| 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(); |
| } |
| |
| 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; |
| } |
| |
| // An enum for the shift function below. |
| enum Direction { LEFT, RIGHT }; |
| |
| // A bitwise shift on an array of elements. |
| // 'offset' must be less than TOTAL_BITS (i.e., sizeof(word) * CHAR_BIT * N) |
| // otherwise the behavior is undefined. |
| 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; |
| #ifdef LIBC_TYPES_HAS_INT128 |
| constexpr size_t TOTAL_BITS = N * WORD_BITS; |
| 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 |
| if (LIBC_UNLIKELY(offset == 0)) |
| return array; |
| 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; |
| } |
| |
| #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 |
| |
| 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 |
| static constexpr size_t WORD_SIZE = sizeof(WordType) * CHAR_BIT; |
| |
| static_assert(Bits > 0 && Bits % WORD_SIZE == 0, |
| "Number of bits in BigInt should be a multiple of WORD_SIZE."); |
| |
| LIBC_INLINE_VAR static constexpr size_t WORD_COUNT = Bits / WORD_SIZE; |
| |
| cpp::array<WordType, WORD_COUNT> val{}; // zero initialized. |
| |
| LIBC_INLINE constexpr BigInt() = default; |
| |
| LIBC_INLINE constexpr BigInt(const BigInt &other) = default; |
| |
| template <size_t OtherBits, bool OtherSigned> |
| LIBC_INLINE constexpr BigInt( |
| const BigInt<OtherBits, OtherSigned, WordType> &other) { |
| if (OtherBits >= Bits) { // truncate |
| for (size_t i = 0; i < WORD_COUNT; ++i) |
| val[i] = other[i]; |
| } else { // zero or sign extend |
| size_t i = 0; |
| for (; i < OtherBits / WORD_SIZE; ++i) |
| val[i] = other[i]; |
| extend(i, Signed && other.is_neg()); |
| } |
| } |
| |
| // 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) |
| val[i] = nums[i]; |
| } |
| |
| LIBC_INLINE constexpr explicit BigInt( |
| const cpp::array<WordType, WORD_COUNT> &words) { |
| val = words; |
| } |
| |
| // 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[i] = static_cast<WordType>(v); |
| if constexpr (T_SIZE > WORD_SIZE) |
| v >>= WORD_SIZE; |
| else |
| v = 0; |
| } |
| } |
| 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; |
| } |
| |
| // TODO: Reuse the Sign type. |
| LIBC_INLINE constexpr bool is_neg() const { return SIGNED && get_msb(); } |
| |
| template <typename T> LIBC_INLINE constexpr explicit operator T() const { |
| return to<T>(); |
| } |
| |
| template <typename T> |
| 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) |
| return lo; |
| constexpr size_t MAX_COUNT = |
| T_SIZE > Bits ? WORD_COUNT : T_SIZE / 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)) { |
| // 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 bool is_zero() const { |
| for (auto part : val) |
| if (part != 0) |
| return false; |
| return true; |
| } |
| |
| // Add 'rhs' 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 BigInt operator+(const BigInt &other) const { |
| BigInt result = *this; |
| result.add_overflow(other); |
| 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; |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator+=(const BigInt &other) { |
| add_overflow(other); // Returned carry value is ignored. |
| return *this; |
| } |
| |
| // Subtract 'rhs' 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 BigInt operator-(const BigInt &other) const { |
| BigInt result = *this; |
| result.sub_overflow(other); // Returned carry value is ignored. |
| return result; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator-(BigInt &&other) const { |
| BigInt result = *this; |
| result.sub_overflow(other); // Returned carry value is ignored. |
| 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. |
| return *this; |
| } |
| |
| // Multiply this number with x and store the result in this number. |
| LIBC_INLINE constexpr WordType mul(WordType x) { |
| return multiword::scalar_multiply_with_carry(val, x); |
| } |
| |
| // Return the full product. |
| template <size_t OtherBits> |
| LIBC_INLINE constexpr auto |
| ful_mul(const BigInt<OtherBits, Signed, WordType> &other) const { |
| BigInt<Bits + OtherBits, Signed, WordType> result; |
| multiword::multiply_with_carry(result.val, val, other.val); |
| 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 |
| // bounded by: |
| // 0 <= (a.full_mul(b) >> Bits) - a.quick_mul_hi(b)) <= WORD_COUNT - 1. |
| // |
| // An example usage of this is to quickly (but less accurately) compute the |
| // product of (normalized) mantissas of floating point numbers: |
| // (mant_1, mant_2) -> quick_mul_hi -> normalize leading bit |
| // is much more efficient than: |
| // (mant_1, mant_2) -> ful_mul -> normalize leading bit |
| // -> convert back to same Bits width by shifting/rounding, |
| // especially for higher precisions. |
| // |
| // Performance summary: |
| // Number of 64-bit x 64-bit -> 128-bit multiplications performed. |
| // Bits WORD_COUNT ful_mul quick_mul_hi Error bound |
| // 128 2 4 3 1 |
| // 196 3 9 6 2 |
| // 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); |
| return result; |
| } |
| |
| // BigInt(x).pow_n(n) computes x ^ n. |
| // Note 0 ^ 0 == 1. |
| LIBC_INLINE constexpr void pow_n(uint64_t power) { |
| static_assert(!Signed); |
| BigInt result = one(); |
| BigInt cur_power = *this; |
| while (power > 0) { |
| if ((power % 2) > 0) |
| result *= cur_power; |
| power >>= 1; |
| cur_power *= cur_power; |
| } |
| *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())) |
| 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; |
| } |
| |
| // Efficiently perform BigInt / (x * 2^e), where x is a half-word-size |
| // unsigned integer, and return the remainder. The main idea is as follow: |
| // Let q = y / (x * 2^e) be the quotient, and |
| // r = y % (x * 2^e) be the remainder. |
| // First, notice that: |
| // r % (2^e) = y % (2^e), |
| // so we just need to focus on all the bits of y that is >= 2^e. |
| // To speed up the shift-and-add steps, we only use x as the divisor, and |
| // performing 32-bit shiftings instead of bit-by-bit shiftings. |
| // Since the remainder of each division step < x < 2^(WORD_SIZE / 2), the |
| // 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) |
| return cpp::nullopt; |
| if (e >= Bits) { |
| remainder = *this; |
| *this = BigInt<Bits, false, WordType>(); |
| return remainder; |
| } |
| BigInt quotient; |
| 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; |
| constexpr WordType HALF_MASK = ((WordType(1) << HALF_WORD_SIZE) - 1); |
| // lower = smallest multiple of WORD_SIZE that is >= e. |
| size_t lower = ((e >> LOG2_WORD_SIZE) + ((e & (WORD_SIZE - 1)) != 0)) |
| << LOG2_WORD_SIZE; |
| // lower_pos is the index of the closest WORD_SIZE-bit chunk >= 2^e. |
| size_t lower_pos = lower / WORD_SIZE; |
| // Keep track of current remainder mod x * 2^(32*i) |
| WordType rem = 0; |
| // pos is the index of the current 64-bit chunk that we are processing. |
| size_t pos = WORD_COUNT; |
| |
| // TODO: look into if constexpr(Bits > 256) skip leading zeroes. |
| |
| for (size_t q_pos = WORD_COUNT - lower_pos; q_pos > 0; --q_pos) { |
| // q_pos is 1 + the index of the current WORD_SIZE-bit chunk of the |
| // quotient being processed. Performing the division / modulus with |
| // divisor: |
| // x * 2^(WORD_SIZE*q_pos - WORD_SIZE/2), |
| // i.e. using the upper (WORD_SIZE/2)-bit of the current WORD_SIZE-bit |
| // chunk. |
| rem <<= HALF_WORD_SIZE; |
| rem += val[--pos] >> HALF_WORD_SIZE; |
| WordType q_tmp = rem / x_word; |
| rem %= x_word; |
| |
| // Performing the division / modulus with divisor: |
| // x * 2^(WORD_SIZE*(q_pos - 1)), |
| // i.e. using the lower (WORD_SIZE/2)-bit of the current WORD_SIZE-bit |
| // chunk. |
| rem <<= HALF_WORD_SIZE; |
| rem += val[pos] & HALF_MASK; |
| quotient.val[q_pos - 1] = (q_tmp << HALF_WORD_SIZE) + rem / x_word; |
| rem %= x_word; |
| } |
| |
| // So far, what we have is: |
| // quotient = y / (x * 2^lower), and |
| // rem = (y % (x * 2^lower)) / 2^lower. |
| // If (lower > e), we will need to perform an extra adjustment of the |
| // quotient and remainder, namely: |
| // y / (x * 2^e) = [ y / (x * 2^lower) ] * 2^(lower - e) + |
| // + (rem * 2^(lower - e)) / x |
| // (y % (x * 2^e)) / 2^e = (rem * 2^(lower - e)) % x |
| size_t last_shift = lower - e; |
| |
| if (last_shift > 0) { |
| // quotient * 2^(lower - e) |
| quotient <<= last_shift; |
| WordType q_tmp = 0; |
| WordType d = val[--pos]; |
| if (last_shift >= HALF_WORD_SIZE) { |
| // The shifting (rem * 2^(lower - e)) might overflow WordTyoe, so we |
| // perform a HALF_WORD_SIZE-bit shift first. |
| rem <<= HALF_WORD_SIZE; |
| rem += d >> HALF_WORD_SIZE; |
| d &= HALF_MASK; |
| q_tmp = rem / x_word; |
| rem %= x_word; |
| last_shift -= HALF_WORD_SIZE; |
| } else { |
| // Only use the upper HALF_WORD_SIZE-bit of the current WORD_SIZE-bit |
| // chunk. |
| d >>= HALF_WORD_SIZE; |
| } |
| |
| if (last_shift > 0) { |
| rem <<= HALF_WORD_SIZE; |
| rem += d; |
| q_tmp <<= last_shift; |
| x_word <<= HALF_WORD_SIZE - last_shift; |
| q_tmp += rem / x_word; |
| rem %= x_word; |
| } |
| |
| quotient.val[0] += q_tmp; |
| |
| if (lower - e <= HALF_WORD_SIZE) { |
| // The remainder rem * 2^(lower - e) might overflow to the higher |
| // WORD_SIZE-bit chunk. |
| if (pos < WORD_COUNT - 1) { |
| remainder[pos + 1] = rem >> HALF_WORD_SIZE; |
| } |
| remainder[pos] = (rem << HALF_WORD_SIZE) + (val[pos] & HALF_MASK); |
| } else { |
| remainder[pos] = rem; |
| } |
| |
| } else { |
| remainder[pos] = rem; |
| } |
| |
| // Set the remaining lower bits of the remainder. |
| for (; pos > 0; --pos) { |
| remainder[pos - 1] = val[pos - 1]; |
| } |
| |
| *this = quotient; |
| return remainder; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator/(const BigInt &other) const { |
| BigInt result(*this); |
| result.div(other); |
| return result; |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator/=(const BigInt &other) { |
| div(other); |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator%(const BigInt &other) const { |
| BigInt result(*this); |
| return *result.div(other); |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator*=(const BigInt &other) { |
| *this = *this * other; |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator<<=(size_t s) { |
| val = multiword::shift<multiword::LEFT, SIGNED>(val, s); |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator<<(size_t s) const { |
| return BigInt(multiword::shift<multiword::LEFT, SIGNED>(val, s)); |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator>>=(size_t s) { |
| val = multiword::shift<multiword::RIGHT, SIGNED>(val, s); |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator>>(size_t s) const { |
| return BigInt(multiword::shift<multiword::RIGHT, SIGNED>(val, s)); |
| } |
| |
| #define DEFINE_BINOP(OP) \ |
| LIBC_INLINE friend constexpr BigInt operator OP(const BigInt &lhs, \ |
| const BigInt &rhs) { \ |
| BigInt result; \ |
| for (size_t i = 0; i < WORD_COUNT; ++i) \ |
| result[i] = lhs[i] OP rhs[i]; \ |
| return result; \ |
| } \ |
| LIBC_INLINE friend constexpr BigInt operator OP##=(BigInt &lhs, \ |
| const BigInt &rhs) { \ |
| for (size_t i = 0; i < WORD_COUNT; ++i) \ |
| lhs[i] OP## = rhs[i]; \ |
| return lhs; \ |
| } |
| |
| DEFINE_BINOP(&) // & and &= |
| DEFINE_BINOP(|) // | and |= |
| DEFINE_BINOP(^) // ^ and ^= |
| #undef DEFINE_BINOP |
| |
| LIBC_INLINE constexpr BigInt operator~() const { |
| BigInt result; |
| for (size_t i = 0; i < WORD_COUNT; ++i) |
| result[i] = ~val[i]; |
| return result; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator-() const { |
| BigInt result(*this); |
| result.negate(); |
| return result; |
| } |
| |
| LIBC_INLINE friend constexpr bool operator==(const BigInt &lhs, |
| const BigInt &rhs) { |
| for (size_t i = 0; i < WORD_COUNT; ++i) |
| if (lhs.val[i] != rhs.val[i]) |
| return false; |
| return true; |
| } |
| |
| LIBC_INLINE friend constexpr bool operator!=(const BigInt &lhs, |
| const BigInt &rhs) { |
| return !(lhs == rhs); |
| } |
| |
| LIBC_INLINE friend constexpr bool operator>(const BigInt &lhs, |
| const BigInt &rhs) { |
| return cmp(lhs, rhs) > 0; |
| } |
| LIBC_INLINE friend constexpr bool operator>=(const BigInt &lhs, |
| const BigInt &rhs) { |
| return cmp(lhs, rhs) >= 0; |
| } |
| LIBC_INLINE friend constexpr bool operator<(const BigInt &lhs, |
| const BigInt &rhs) { |
| return cmp(lhs, rhs) < 0; |
| } |
| LIBC_INLINE friend constexpr bool operator<=(const BigInt &lhs, |
| const BigInt &rhs) { |
| return cmp(lhs, rhs) <= 0; |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator++() { |
| increment(); |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator++(int) { |
| BigInt oldval(*this); |
| increment(); |
| return oldval; |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator--() { |
| decrement(); |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator--(int) { |
| BigInt oldval(*this); |
| decrement(); |
| return oldval; |
| } |
| |
| // Return the i-th word of the number. |
| LIBC_INLINE constexpr const WordType &operator[](size_t i) const { |
| return val[i]; |
| } |
| |
| // 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 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; |
| }; |
| |
| namespace internal { |
| // We default BigInt's WordType to 'uint64_t' or 'uint32_t' depending on type |
| // availability. |
| template <size_t Bits> |
| struct WordTypeSelector : cpp::type_identity< |
| #ifdef LIBC_TYPES_HAS_INT64 |
| uint64_t |
| #else |
| uint32_t |
| #endif // LIBC_TYPES_HAS_INT64 |
| > { |
| }; |
| // Except if we request 32 bits explicitly. |
| template <> struct WordTypeSelector<32> : cpp::type_identity<uint32_t> {}; |
| template <size_t Bits> |
| using WordTypeSelectorT = typename WordTypeSelector<Bits>::type; |
| } // namespace internal |
| |
| template <size_t Bits> |
| using UInt = BigInt<Bits, false, internal::WordTypeSelectorT<Bits>>; |
| |
| template <size_t Bits> |
| 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(); } |
| // Meant to match std::numeric_limits interface. |
| // NOLINTNEXTLINE(readability-identifier-naming) |
| LIBC_INLINE_VAR static constexpr int digits = 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(); } |
| // Meant to match std::numeric_limits interface. |
| // NOLINTNEXTLINE(readability-identifier-naming) |
| LIBC_INLINE_VAR static constexpr int digits = 128; |
| }; |
| |
| // type traits to determine whether a T is a BigInt. |
| template <typename T> struct is_big_int : cpp::false_type {}; |
| |
| template <size_t Bits, bool Signed, typename T> |
| struct is_big_int<BigInt<Bits, Signed, T>> : cpp::true_type {}; |
| |
| template <class T> |
| LIBC_INLINE_VAR constexpr bool is_big_int_v = is_big_int<T>::value; |
| |
| // extensions of type traits to include BigInt |
| |
| // is_integral_or_big_int |
| template <typename T> |
| struct is_integral_or_big_int |
| : cpp::bool_constant<(cpp::is_integral_v<T> || is_big_int_v<T>)> {}; |
| |
| template <typename T> |
| LIBC_INLINE_VAR constexpr bool is_integral_or_big_int_v = |
| is_integral_or_big_int<T>::value; |
| |
| // make_big_int_unsigned |
| template <typename T> struct make_big_int_unsigned; |
| |
| template <size_t Bits, bool Signed, typename T> |
| struct make_big_int_unsigned<BigInt<Bits, Signed, T>> |
| : cpp::type_identity<BigInt<Bits, false, T>> {}; |
| |
| template <typename T> |
| using make_big_int_unsigned_t = typename make_big_int_unsigned<T>::type; |
| |
| // make_big_int_signed |
| template <typename T> struct make_big_int_signed; |
| |
| template <size_t Bits, bool Signed, typename T> |
| struct make_big_int_signed<BigInt<Bits, Signed, T>> |
| : cpp::type_identity<BigInt<Bits, true, T>> {}; |
| |
| template <typename T> |
| using make_big_int_signed_t = typename make_big_int_signed<T>::type; |
| |
| // make_integral_or_big_int_unsigned |
| template <typename T, class = void> struct make_integral_or_big_int_unsigned; |
| |
| template <typename T> |
| struct make_integral_or_big_int_unsigned< |
| T, cpp::enable_if_t<cpp::is_integral_v<T>>> : cpp::make_unsigned<T> {}; |
| |
| template <typename T> |
| struct make_integral_or_big_int_unsigned<T, cpp::enable_if_t<is_big_int_v<T>>> |
| : make_big_int_unsigned<T> {}; |
| |
| template <typename T> |
| using make_integral_or_big_int_unsigned_t = |
| typename make_integral_or_big_int_unsigned<T>::type; |
| |
| // make_integral_or_big_int_signed |
| template <typename T, class = void> struct make_integral_or_big_int_signed; |
| |
| template <typename T> |
| struct make_integral_or_big_int_signed<T, |
| cpp::enable_if_t<cpp::is_integral_v<T>>> |
| : cpp::make_signed<T> {}; |
| |
| template <typename T> |
| struct make_integral_or_big_int_signed<T, cpp::enable_if_t<is_big_int_v<T>>> |
| : make_big_int_signed<T> {}; |
| |
| template <typename T> |
| using make_integral_or_big_int_signed_t = |
| typename make_integral_or_big_int_signed<T>::type; |
| |
| namespace cpp { |
| |
| // Specialization of cpp::bit_cast ('bit.h') from T to BigInt. |
| template <typename To, typename From> |
| LIBC_INLINE constexpr cpp::enable_if_t< |
| (sizeof(To) == sizeof(From)) && cpp::is_trivially_copyable<To>::value && |
| cpp::is_trivially_copyable<From>::value && is_big_int<To>::value, |
| To> |
| bit_cast(const From &from) { |
| To out; |
| using Storage = decltype(out.val); |
| out.val = cpp::bit_cast<Storage>(from); |
| return out; |
| } |
| |
| // Specialization of cpp::bit_cast ('bit.h') from BigInt to T. |
| template <typename To, size_t Bits> |
| LIBC_INLINE constexpr cpp::enable_if_t< |
| sizeof(To) == sizeof(UInt<Bits>) && |
| cpp::is_trivially_constructible<To>::value && |
| cpp::is_trivially_copyable<To>::value && |
| cpp::is_trivially_copyable<UInt<Bits>>::value, |
| To> |
| bit_cast(const UInt<Bits> &from) { |
| return cpp::bit_cast<To>(from.val); |
| } |
| |
| // Specialization of cpp::popcount ('bit.h') for BigInt. |
| template <typename T> |
| [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> |
| popcount(T value) { |
| int bits = 0; |
| for (auto word : value.val) |
| if (word) |
| bits += popcount(word); |
| return bits; |
| } |
| |
| // Specialization of cpp::has_single_bit ('bit.h') for BigInt. |
| template <typename T> |
| [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, bool> |
| has_single_bit(T value) { |
| int bits = 0; |
| for (auto word : value.val) { |
| if (word == 0) |
| continue; |
| bits += popcount(word); |
| if (bits > 1) |
| return false; |
| } |
| return bits == 1; |
| } |
| |
| // Specialization of cpp::countr_zero ('bit.h') for BigInt. |
| 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); |
| } |
| |
| // 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); |
| } |
| |
| // 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); |
| } |
| |
| // 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); |
| } |
| |
| // Specialization of cpp::bit_width ('bit.h') for BigInt. |
| template <typename T> |
| [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int> |
| bit_width(T value) { |
| return cpp::numeric_limits<T>::digits - cpp::countl_zero(value); |
| } |
| |
| // Forward-declare rotr so that rotl can use it. |
| template <typename T> |
| [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> |
| rotr(T value, int rotate); |
| |
| // Specialization of cpp::rotl ('bit.h') for BigInt. |
| template <typename T> |
| [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> |
| rotl(T value, int rotate) { |
| constexpr unsigned N = cpp::numeric_limits<T>::digits; |
| rotate = rotate % N; |
| if (!rotate) |
| return value; |
| if (rotate < 0) |
| return cpp::rotr<T>(value, -rotate); |
| return (value << rotate) | (value >> (N - rotate)); |
| } |
| |
| // Specialization of cpp::rotr ('bit.h') for BigInt. |
| template <typename T> |
| [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> |
| rotr(T value, int rotate) { |
| constexpr unsigned N = cpp::numeric_limits<T>::digits; |
| rotate = rotate % N; |
| if (!rotate) |
| return value; |
| if (rotate < 0) |
| return cpp::rotl<T>(value, -rotate); |
| return (value >> rotate) | (value << (N - rotate)); |
| } |
| |
| } // namespace cpp |
| |
| // Specialization of mask_trailing_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_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>(); |
| 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>(); |
| 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> |
| 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> |
| first_leading_zero(T value) { |
| return value == cpp::numeric_limits<T>::max() ? 0 |
| : cpp::countl_one(value) + 1; |
| } |
| |
| // 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> |
| 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> |
| first_trailing_zero(T value) { |
| return value == cpp::numeric_limits<T>::max() ? 0 |
| : cpp::countr_zero(~value) + 1; |
| } |
| |
| // 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> |
| first_trailing_one(T value) { |
| return value == cpp::numeric_limits<T>::max() ? 0 |
| : cpp::countr_zero(value) + 1; |
| } |
| |
| } // namespace LIBC_NAMESPACE |
| |
| #endif // LLVM_LIBC_SRC___SUPPORT_UINT_H |