| //===-- 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/types.h" // LIBC_TYPES_HAS_INT128, LIBC_TYPES_HAS_INT64 |
| #include "src/__support/math_extras.h" // SumCarry, DiffBorrow |
| #include "src/__support/number_pair.h" |
| |
| #include <stddef.h> // For size_t |
| #include <stdint.h> |
| |
| namespace LIBC_NAMESPACE { |
| |
| namespace internal { |
| template <typename T> struct half_width; |
| |
| 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 |
| |
| template <typename T> using half_width_t = typename half_width<T>::type; |
| |
| 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; |
| |
| 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 |
| |
| constexpr size_t HALF_BIT_WIDTH = sizeof(T) * CHAR_BIT / 2; |
| |
| 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; |
| |
| 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; |
| |
| return prod; |
| } |
| |
| 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; |
| } |
| |
| #ifdef LIBC_TYPES_HAS_INT128 |
| 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 |
| |
| } // namespace internal |
| |
| template <size_t Bits, bool Signed, typename WordType = uint64_t> |
| struct BigInt { |
| static_assert(cpp::is_integral_v<WordType> && cpp::is_unsigned_v<WordType>, |
| "WordType must be unsigned integer."); |
| |
| using word_type = WordType; |
| 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; |
| |
| 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; |
| |
| 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) { |
| for (size_t i = 0; i < WORD_COUNT; ++i) |
| val[i] = other[i]; |
| } else { |
| size_t i = 0; |
| for (; i < OtherBits / WORD_SIZE; ++i) |
| val[i] = other[i]; |
| 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, 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]; |
| |
| // 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) { |
| 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); |
| } |
| 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; |
| 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 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 val.back() >> (WORD_SIZE - 1); |
| } |
| |
| 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 { |
| T lo = static_cast<T>(val[0]); |
| |
| constexpr size_t T_BITS = sizeof(T) * CHAR_BIT; |
| |
| if constexpr (T_BITS <= WORD_SIZE) |
| return lo; |
| |
| constexpr size_t MAX_COUNT = |
| 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_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 (size_t i = 0; i < WORD_COUNT; ++i) { |
| if (val[i] != 0) |
| return false; |
| } |
| return true; |
| } |
| |
| // 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(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; |
| 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 { |
| 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(other); // Returned carry value is ignored. |
| return *this; |
| } |
| |
| // 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(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; |
| 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; |
| 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(other); |
| return *this; |
| } |
| |
| // 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) { |
| 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, only unsigned for now. |
| template <size_t OtherBits> |
| LIBC_INLINE constexpr BigInt<Bits + OtherBits, Signed, WordType> |
| ful_mul(const BigInt<OtherBits, Signed, WordType> &other) const { |
| 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; |
| } |
| |
| // 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(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; |
| } |
| |
| // 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) { |
| BigInt result = 1; |
| BigInt cur_power = *this; |
| |
| while (power > 0) { |
| if ((power % 2) > 0) |
| result *= cur_power; |
| power >>= 1; |
| cur_power *= cur_power; |
| } |
| *this = result; |
| } |
| |
| // 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; |
| } |
| |
| 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 |
| // 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(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>(0); |
| return remainder; |
| } |
| |
| 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; |
| 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; |
| } |
| |
| // 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 { |
| BigInt result(*this); |
| result.shift_left(s); |
| return result; |
| } |
| |
| 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 { |
| 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) \ |
| 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(&) |
| DEFINE_BINOP(|) |
| DEFINE_BINOP(^) |
| |
| #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.add(BigInt(1)); |
| 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); |
| } |
| |
| 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; |
| } |
| 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++() { |
| add(BigInt(1)); |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator++(int) { |
| BigInt oldval(*this); |
| add(BigInt(1)); |
| return oldval; |
| } |
| |
| LIBC_INLINE constexpr BigInt &operator--() { |
| sub(BigInt(1)); |
| return *this; |
| } |
| |
| LIBC_INLINE constexpr BigInt operator--(int) { |
| BigInt oldval(*this); |
| sub(BigInt(1)); |
| 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]; } |
| |
| LIBC_INLINE WordType *data() { return val; } |
| |
| LIBC_INLINE const WordType *data() const { return val; } |
| }; |
| |
| 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>({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; |
| }; |
| |
| template <> class cpp::numeric_limits<Int<128>> { |
| public: |
| 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; |
| }; |
| |
| // 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 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 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) { |
| // 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) { |
| // TODO : Implement a faster version not involving operator~. |
| return cpp::countr_zero<T>(~value); |
| } |
| |
| // 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); |
| 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); |
| 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 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 |