1392 lines · c
1//===-- A class to manipulate wide integers. --------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_BIG_INT_H10#define LLVM_LIBC_SRC___SUPPORT_BIG_INT_H11 12#include "hdr/stdint_proxy.h"13#include "src/__support/CPP/array.h"14#include "src/__support/CPP/bit.h" // countl_zero15#include "src/__support/CPP/limits.h"16#include "src/__support/CPP/optional.h"17#include "src/__support/CPP/type_traits.h"18#include "src/__support/macros/attributes.h" // LIBC_INLINE19#include "src/__support/macros/config.h"20#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY21#include "src/__support/macros/properties/compiler.h" // LIBC_COMPILER_IS_CLANG22#include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128, LIBC_TYPES_HAS_INT6423#include "src/__support/math_extras.h" // add_with_carry, sub_with_borrow24#include "src/__support/number_pair.h"25 26#include <stddef.h> // For size_t27 28namespace LIBC_NAMESPACE_DECL {29 30namespace multiword {31 32// A type trait mapping unsigned integers to their half-width unsigned33// counterparts.34template <typename T> struct half_width;35template <> struct half_width<uint16_t> : cpp::type_identity<uint8_t> {};36template <> struct half_width<uint32_t> : cpp::type_identity<uint16_t> {};37#ifdef LIBC_TYPES_HAS_INT6438template <> struct half_width<uint64_t> : cpp::type_identity<uint32_t> {};39#ifdef LIBC_TYPES_HAS_INT12840template <> struct half_width<__uint128_t> : cpp::type_identity<uint64_t> {};41#endif // LIBC_TYPES_HAS_INT12842#endif // LIBC_TYPES_HAS_INT6443template <typename T> using half_width_t = typename half_width<T>::type;44 45// An array of two elements that can be used in multiword operations.46template <typename T> struct DoubleWide final : cpp::array<T, 2> {47 using UP = cpp::array<T, 2>;48 using UP::UP;49 LIBC_INLINE constexpr DoubleWide(T lo, T hi) : UP({lo, hi}) {}50};51 52// Converts an unsigned value into a DoubleWide<half_width_t<T>>.53template <typename T> LIBC_INLINE constexpr auto split(T value) {54 static_assert(cpp::is_unsigned_v<T>);55 using half_type = half_width_t<T>;56 return DoubleWide<half_type>(57 half_type(value),58 half_type(value >> cpp::numeric_limits<half_type>::digits));59}60 61// The low part of a DoubleWide value.62template <typename T> LIBC_INLINE constexpr T lo(const DoubleWide<T> &value) {63 return value[0];64}65// The high part of a DoubleWide value.66template <typename T> LIBC_INLINE constexpr T hi(const DoubleWide<T> &value) {67 return value[1];68}69// The low part of an unsigned value.70template <typename T> LIBC_INLINE constexpr half_width_t<T> lo(T value) {71 return lo(split(value));72}73// The high part of an unsigned value.74template <typename T> LIBC_INLINE constexpr half_width_t<T> hi(T value) {75 return hi(split(value));76}77 78// Returns 'a' times 'b' in a DoubleWide<word>. Cannot overflow by construction.79template <typename word>80LIBC_INLINE constexpr DoubleWide<word> mul2(word a, word b) {81 if constexpr (cpp::is_same_v<word, uint8_t>) {82 return split<uint16_t>(uint16_t(a) * uint16_t(b));83 } else if constexpr (cpp::is_same_v<word, uint16_t>) {84 return split<uint32_t>(uint32_t(a) * uint32_t(b));85 }86#ifdef LIBC_TYPES_HAS_INT6487 else if constexpr (cpp::is_same_v<word, uint32_t>) {88 return split<uint64_t>(uint64_t(a) * uint64_t(b));89 }90#endif91#ifdef LIBC_TYPES_HAS_INT12892 else if constexpr (cpp::is_same_v<word, uint64_t>) {93 return split<__uint128_t>(__uint128_t(a) * __uint128_t(b));94 }95#endif96 else {97 using half_word = half_width_t<word>;98 constexpr auto shiftl = [](word value) -> word {99 return value << cpp::numeric_limits<half_word>::digits;100 };101 constexpr auto shiftr = [](word value) -> word {102 return value >> cpp::numeric_limits<half_word>::digits;103 };104 // Here we do a one digit multiplication where 'a' and 'b' are of type105 // word. We split 'a' and 'b' into half words and perform the classic long106 // multiplication with 'a' and 'b' being two-digit numbers.107 108 // a a_hi a_lo109 // x b => x b_hi b_lo110 // ---- -----------111 // c result112 // We convert 'lo' and 'hi' from 'half_word' to 'word' so multiplication113 // doesn't overflow.114 word a_lo = lo(a);115 word b_lo = lo(b);116 word a_hi = hi(a);117 word b_hi = hi(b);118 word step1 = b_lo * a_lo; // no overflow;119 word step2 = b_lo * a_hi; // no overflow;120 word step3 = b_hi * a_lo; // no overflow;121 word step4 = b_hi * a_hi; // no overflow;122 word lo_digit = step1;123 word hi_digit = step4;124 word no_carry = 0;125 word carry = 0;126 [[maybe_unused]] word _ = 0; // unused carry variable.127 lo_digit = add_with_carry<word>(lo_digit, shiftl(step2), no_carry, carry);128 hi_digit = add_with_carry<word>(hi_digit, shiftr(step2), carry, _);129 lo_digit = add_with_carry<word>(lo_digit, shiftl(step3), no_carry, carry);130 hi_digit = add_with_carry<word>(hi_digit, shiftr(step3), carry, _);131 return DoubleWide<word>(lo_digit, hi_digit);132 }133}134 135// In-place 'dst op= rhs' with operation with carry propagation. Returns carry.136template <typename Function, typename word, size_t N, size_t M>137LIBC_INLINE constexpr word inplace_binop(Function op_with_carry,138 cpp::array<word, N> &dst,139 const cpp::array<word, M> &rhs) {140 static_assert(N >= M);141 word carry_out = 0;142 for (size_t i = 0; i < N; ++i) {143 const bool has_rhs_value = i < M;144 const word rhs_value = has_rhs_value ? rhs[i] : 0;145 const word carry_in = carry_out;146 dst[i] = op_with_carry(dst[i], rhs_value, carry_in, carry_out);147 // stop early when rhs is over and no carry is to be propagated.148 if (!has_rhs_value && carry_out == 0)149 break;150 }151 return carry_out;152}153 154// In-place addition. Returns carry.155template <typename word, size_t N, size_t M>156LIBC_INLINE constexpr word add_with_carry(cpp::array<word, N> &dst,157 const cpp::array<word, M> &rhs) {158 return inplace_binop(LIBC_NAMESPACE::add_with_carry<word>, dst, rhs);159}160 161// In-place subtraction. Returns borrow.162template <typename word, size_t N, size_t M>163LIBC_INLINE constexpr word sub_with_borrow(cpp::array<word, N> &dst,164 const cpp::array<word, M> &rhs) {165 return inplace_binop(LIBC_NAMESPACE::sub_with_borrow<word>, dst, rhs);166}167 168// In-place multiply-add. Returns carry.169// i.e., 'dst += b * c'170template <typename word, size_t N>171LIBC_INLINE constexpr word mul_add_with_carry(cpp::array<word, N> &dst, word b,172 word c) {173 return add_with_carry(dst, mul2(b, c));174}175 176// An array of two elements serving as an accumulator during multiword177// computations.178template <typename T> struct Accumulator final : cpp::array<T, 2> {179 using UP = cpp::array<T, 2>;180 LIBC_INLINE constexpr Accumulator() : UP({0, 0}) {}181 LIBC_INLINE constexpr T advance(T carry_in) {182 auto result = UP::front();183 UP::front() = UP::back();184 UP::back() = carry_in;185 return result;186 }187 LIBC_INLINE constexpr T sum() const { return UP::front(); }188 LIBC_INLINE constexpr T carry() const { return UP::back(); }189};190 191// In-place multiplication by a single word. Returns carry.192template <typename word, size_t N>193LIBC_INLINE constexpr word scalar_multiply_with_carry(cpp::array<word, N> &dst,194 word x) {195 Accumulator<word> acc;196 for (auto &val : dst) {197 const word carry = mul_add_with_carry(acc, val, x);198 val = acc.advance(carry);199 }200 return acc.carry();201}202 203// Multiplication of 'lhs' by 'rhs' into 'dst'. Returns carry.204// This function is safe to use for signed numbers.205// https://stackoverflow.com/a/20793834206// https://pages.cs.wisc.edu/%7Emarkhill/cs354/Fall2008/beyond354/int.mult.html207template <typename word, size_t O, size_t M, size_t N>208LIBC_INLINE constexpr word multiply_with_carry(cpp::array<word, O> &dst,209 const cpp::array<word, M> &lhs,210 const cpp::array<word, N> &rhs) {211 static_assert(O >= M + N);212 Accumulator<word> acc;213 for (size_t i = 0; i < O; ++i) {214 const size_t lower_idx = i < N ? 0 : i - N + 1;215 const size_t upper_idx = i < M ? i : M - 1;216 word carry = 0;217 for (size_t j = lower_idx; j <= upper_idx; ++j)218 carry += mul_add_with_carry(acc, lhs[j], rhs[i - j]);219 dst[i] = acc.advance(carry);220 }221 return acc.carry();222}223 224template <typename word, size_t N>225LIBC_INLINE constexpr void quick_mul_hi(cpp::array<word, N> &dst,226 const cpp::array<word, N> &lhs,227 const cpp::array<word, N> &rhs) {228 Accumulator<word> acc;229 word carry = 0;230 // First round of accumulation for those at N - 1 in the full product.231 for (size_t i = 0; i < N; ++i)232 carry += mul_add_with_carry(acc, lhs[i], rhs[N - 1 - i]);233 for (size_t i = N; i < 2 * N - 1; ++i) {234 acc.advance(carry);235 carry = 0;236 for (size_t j = i - N + 1; j < N; ++j)237 carry += mul_add_with_carry(acc, lhs[j], rhs[i - j]);238 dst[i - N] = acc.sum();239 }240 dst.back() = acc.carry();241}242 243template <typename word, size_t N>244LIBC_INLINE constexpr bool is_negative(const cpp::array<word, N> &array) {245 using signed_word = cpp::make_signed_t<word>;246 return cpp::bit_cast<signed_word>(array.back()) < 0;247}248 249// An enum for the shift function below.250enum Direction { LEFT, RIGHT };251 252// A bitwise shift on an array of elements.253// 'offset' must be less than TOTAL_BITS (i.e., sizeof(word) * CHAR_BIT * N)254// otherwise the behavior is undefined.255template <Direction direction, bool is_signed, typename word, size_t N>256LIBC_INLINE constexpr cpp::array<word, N> shift(cpp::array<word, N> array,257 size_t offset) {258 static_assert(direction == LEFT || direction == RIGHT);259 constexpr size_t WORD_BITS = cpp::numeric_limits<word>::digits;260#ifdef LIBC_TYPES_HAS_INT128261 constexpr size_t TOTAL_BITS = N * WORD_BITS;262 if constexpr (TOTAL_BITS == 128) {263 using type = cpp::conditional_t<is_signed, __int128_t, __uint128_t>;264 auto tmp = cpp::bit_cast<type>(array);265 if constexpr (direction == LEFT)266 tmp <<= offset;267 else268 tmp >>= offset;269 return cpp::bit_cast<cpp::array<word, N>>(tmp);270 }271#endif272 if (LIBC_UNLIKELY(offset == 0))273 return array;274 const bool is_neg = is_signed && is_negative(array);275 constexpr auto at = [](size_t index) -> int {276 // reverse iteration when direction == LEFT.277 if constexpr (direction == LEFT)278 return int(N) - int(index) - 1;279 return int(index);280 };281 const auto safe_get_at = [&](size_t index) -> word {282 // return appropriate value when accessing out of bound elements.283 const int i = at(index);284 if (i < 0)285 return 0;286 if (i >= int(N))287 return is_neg ? cpp::numeric_limits<word>::max() : 0;288 return array[static_cast<unsigned>(i)];289 };290 const size_t index_offset = offset / WORD_BITS;291 const size_t bit_offset = offset % WORD_BITS;292#ifdef LIBC_COMPILER_IS_CLANG293 __builtin_assume(index_offset < N);294#endif295 cpp::array<word, N> out = {};296 for (size_t index = 0; index < N; ++index) {297 const word part1 = safe_get_at(index + index_offset);298 const word part2 = safe_get_at(index + index_offset + 1);299 word &dst = out[static_cast<unsigned>(at(index))];300 if (bit_offset == 0)301 dst = part1; // no crosstalk between parts.302 else if constexpr (direction == LEFT)303 dst = static_cast<word>((part1 << bit_offset) |304 (part2 >> (WORD_BITS - bit_offset)));305 else306 dst = static_cast<word>((part1 >> bit_offset) |307 (part2 << (WORD_BITS - bit_offset)));308 }309 return out;310}311 312#define DECLARE_COUNTBIT(NAME, INDEX_EXPR) \313 template <typename word, size_t N> \314 LIBC_INLINE constexpr int NAME(const cpp::array<word, N> &val) { \315 int bit_count = 0; \316 for (size_t i = 0; i < N; ++i) { \317 const int word_count = cpp::NAME<word>(val[INDEX_EXPR]); \318 bit_count += word_count; \319 if (word_count != cpp::numeric_limits<word>::digits) \320 break; \321 } \322 return bit_count; \323 }324 325DECLARE_COUNTBIT(countr_zero, i) // iterating forward326DECLARE_COUNTBIT(countr_one, i) // iterating forward327DECLARE_COUNTBIT(countl_zero, N - i - 1) // iterating backward328DECLARE_COUNTBIT(countl_one, N - i - 1) // iterating backward329 330} // namespace multiword331 332template <size_t Bits, bool Signed, typename WordType = uint64_t>333struct BigInt {334private:335 static_assert(cpp::is_integral_v<WordType> && cpp::is_unsigned_v<WordType>,336 "WordType must be unsigned integer.");337 338 struct Division {339 BigInt quotient;340 BigInt remainder;341 };342 343public:344 using word_type = WordType;345 using unsigned_type = BigInt<Bits, false, word_type>;346 using signed_type = BigInt<Bits, true, word_type>;347 348 LIBC_INLINE_VAR static constexpr bool SIGNED = Signed;349 LIBC_INLINE_VAR static constexpr size_t BITS = Bits;350 LIBC_INLINE_VAR351 static constexpr size_t WORD_SIZE = sizeof(WordType) * CHAR_BIT;352 353 static_assert(Bits > 0 && Bits % WORD_SIZE == 0,354 "Number of bits in BigInt should be a multiple of WORD_SIZE.");355 356 LIBC_INLINE_VAR static constexpr size_t WORD_COUNT = Bits / WORD_SIZE;357 358 cpp::array<WordType, WORD_COUNT> val{}; // zero initialized.359 360 LIBC_INLINE constexpr BigInt() = default;361 362 LIBC_INLINE constexpr BigInt(const BigInt &other) = default;363 364 template <size_t OtherBits, bool OtherSigned, typename OtherWordType>365 LIBC_INLINE constexpr BigInt(366 const BigInt<OtherBits, OtherSigned, OtherWordType> &other) {367 using BigIntOther = BigInt<OtherBits, OtherSigned, OtherWordType>;368 const bool should_sign_extend = Signed && other.is_neg();369 370 static_assert(!(Bits == OtherBits && WORD_SIZE != BigIntOther::WORD_SIZE) &&371 "This is currently untested for casting between bigints with "372 "the same bit width but different word sizes.");373 374 if constexpr (BigIntOther::WORD_SIZE < WORD_SIZE) {375 // OtherWordType is smaller376 constexpr size_t WORD_SIZE_RATIO = WORD_SIZE / BigIntOther::WORD_SIZE;377 static_assert(378 (WORD_SIZE % BigIntOther::WORD_SIZE) == 0 &&379 "Word types must be multiples of each other for correct conversion.");380 if constexpr (OtherBits >= Bits) { // truncate381 // for each big word382 for (size_t i = 0; i < WORD_COUNT; ++i) {383 WordType cur_word = 0;384 // combine WORD_SIZE_RATIO small words into a big word385 for (size_t j = 0; j < WORD_SIZE_RATIO; ++j)386 cur_word |= static_cast<WordType>(other[(i * WORD_SIZE_RATIO) + j])387 << (BigIntOther::WORD_SIZE * j);388 389 val[i] = cur_word;390 }391 } else { // zero or sign extend392 size_t i = 0;393 WordType cur_word = 0;394 // for each small word395 for (; i < BigIntOther::WORD_COUNT; ++i) {396 // combine WORD_SIZE_RATIO small words into a big word397 cur_word |= static_cast<WordType>(other[i])398 << (BigIntOther::WORD_SIZE * (i % WORD_SIZE_RATIO));399 // if we've completed a big word, copy it into place and reset400 if ((i % WORD_SIZE_RATIO) == WORD_SIZE_RATIO - 1) {401 val[i / WORD_SIZE_RATIO] = cur_word;402 cur_word = 0;403 }404 }405 // Pretend there are extra words of the correct sign extension as needed406 407 const WordType extension_bits =408 should_sign_extend ? cpp::numeric_limits<WordType>::max()409 : cpp::numeric_limits<WordType>::min();410 if ((i % WORD_SIZE_RATIO) != 0) {411 cur_word |= static_cast<WordType>(extension_bits)412 << (BigIntOther::WORD_SIZE * (i % WORD_SIZE_RATIO));413 }414 // Copy the last word into place.415 val[(i / WORD_SIZE_RATIO)] = cur_word;416 extend((i / WORD_SIZE_RATIO) + 1, should_sign_extend);417 }418 } else if constexpr (BigIntOther::WORD_SIZE == WORD_SIZE) {419 if constexpr (OtherBits >= Bits) { // truncate420 for (size_t i = 0; i < WORD_COUNT; ++i)421 val[i] = other[i];422 } else { // zero or sign extend423 size_t i = 0;424 for (; i < BigIntOther::WORD_COUNT; ++i)425 val[i] = other[i];426 extend(i, should_sign_extend);427 }428 } else {429 // OtherWordType is bigger.430 constexpr size_t WORD_SIZE_RATIO = BigIntOther::WORD_SIZE / WORD_SIZE;431 static_assert(432 (BigIntOther::WORD_SIZE % WORD_SIZE) == 0 &&433 "Word types must be multiples of each other for correct conversion.");434 if constexpr (OtherBits >= Bits) { // truncate435 // for each small word436 for (size_t i = 0; i < WORD_COUNT; ++i) {437 // split each big word into WORD_SIZE_RATIO small words438 val[i] = static_cast<WordType>(other[i / WORD_SIZE_RATIO] >>439 ((i % WORD_SIZE_RATIO) * WORD_SIZE));440 }441 } else { // zero or sign extend442 size_t i = 0;443 // for each big word444 for (; i < BigIntOther::WORD_COUNT; ++i) {445 // split each big word into WORD_SIZE_RATIO small words446 for (size_t j = 0; j < WORD_SIZE_RATIO; ++j)447 val[(i * WORD_SIZE_RATIO) + j] =448 static_cast<WordType>(other[i] >> (j * WORD_SIZE));449 }450 extend(i * WORD_SIZE_RATIO, should_sign_extend);451 }452 }453 }454 455 // Construct a BigInt from a C array.456 template <size_t N> LIBC_INLINE constexpr BigInt(const WordType (&nums)[N]) {457 static_assert(N == WORD_COUNT);458 for (size_t i = 0; i < WORD_COUNT; ++i)459 val[i] = nums[i];460 }461 462 LIBC_INLINE constexpr explicit BigInt(463 const cpp::array<WordType, WORD_COUNT> &words) {464 val = words;465 }466 467 // Initialize the first word to |v| and the rest to 0.468 template <typename T, typename = cpp::enable_if_t<cpp::is_integral_v<T>>>469 LIBC_INLINE constexpr BigInt(T v) {470 constexpr size_t T_SIZE = sizeof(T) * CHAR_BIT;471 const bool is_neg = v < 0;472 for (size_t i = 0; i < WORD_COUNT; ++i) {473 if (v == 0) {474 extend(i, is_neg);475 return;476 }477 val[i] = static_cast<WordType>(v);478 if constexpr (T_SIZE > WORD_SIZE)479 v >>= WORD_SIZE;480 else481 v = 0;482 }483 }484 LIBC_INLINE constexpr BigInt &operator=(const BigInt &other) = default;485 486 // constants487 LIBC_INLINE static constexpr BigInt zero() { return BigInt(); }488 LIBC_INLINE static constexpr BigInt one() { return BigInt(1); }489 LIBC_INLINE static constexpr BigInt all_ones() { return ~zero(); }490 LIBC_INLINE static constexpr BigInt min() {491 BigInt out;492 if constexpr (SIGNED)493 out.set_msb();494 return out;495 }496 LIBC_INLINE static constexpr BigInt max() {497 BigInt out = all_ones();498 if constexpr (SIGNED)499 out.clear_msb();500 return out;501 }502 503 // TODO: Reuse the Sign type.504 LIBC_INLINE constexpr bool is_neg() const { return SIGNED && get_msb(); }505 506 template <size_t OtherBits, bool OtherSigned, typename OtherWordType>507 LIBC_INLINE constexpr explicit508 operator BigInt<OtherBits, OtherSigned, OtherWordType>() const {509 return BigInt<OtherBits, OtherSigned, OtherWordType>(this);510 }511 512 template <typename T> LIBC_INLINE constexpr explicit operator T() const {513 return to<T>();514 }515 516 template <typename T>517 LIBC_INLINE constexpr cpp::enable_if_t<518 cpp::is_integral_v<T> && !cpp::is_same_v<T, bool>, T>519 to() const {520 constexpr size_t T_SIZE = sizeof(T) * CHAR_BIT;521 T lo = static_cast<T>(val[0]);522 if constexpr (T_SIZE <= WORD_SIZE)523 return lo;524 constexpr size_t MAX_COUNT =525 T_SIZE > Bits ? WORD_COUNT : T_SIZE / WORD_SIZE;526 for (size_t i = 1; i < MAX_COUNT; ++i)527 lo += static_cast<T>(static_cast<T>(val[i]) << (WORD_SIZE * i));528 if constexpr (Signed && (T_SIZE > Bits)) {529 // Extend sign for negative numbers.530 constexpr T MASK = (~T(0) << Bits);531 if (is_neg())532 lo |= MASK;533 }534 return lo;535 }536 537 LIBC_INLINE constexpr explicit operator bool() const { return !is_zero(); }538 539 LIBC_INLINE constexpr bool is_zero() const {540 for (auto part : val)541 if (part != 0)542 return false;543 return true;544 }545 546 // Add 'rhs' to this number and store the result in this number.547 // Returns the carry value produced by the addition operation.548 LIBC_INLINE constexpr WordType add_overflow(const BigInt &rhs) {549 return multiword::add_with_carry(val, rhs.val);550 }551 552 LIBC_INLINE constexpr BigInt operator+(const BigInt &other) const {553 BigInt result = *this;554 result.add_overflow(other);555 return result;556 }557 558 // This will only apply when initializing a variable from constant values, so559 // it will always use the constexpr version of add_with_carry.560 LIBC_INLINE constexpr BigInt operator+(BigInt &&other) const {561 // We use addition commutativity to reuse 'other' and prevent allocation.562 other.add_overflow(*this); // Returned carry value is ignored.563 return other;564 }565 566 LIBC_INLINE constexpr BigInt &operator+=(const BigInt &other) {567 add_overflow(other); // Returned carry value is ignored.568 return *this;569 }570 571 // Subtract 'rhs' to this number and store the result in this number.572 // Returns the carry value produced by the subtraction operation.573 LIBC_INLINE constexpr WordType sub_overflow(const BigInt &rhs) {574 return multiword::sub_with_borrow(val, rhs.val);575 }576 577 LIBC_INLINE constexpr BigInt operator-(const BigInt &other) const {578 BigInt result = *this;579 result.sub_overflow(other); // Returned carry value is ignored.580 return result;581 }582 583 LIBC_INLINE constexpr BigInt operator-(BigInt &&other) const {584 BigInt result = *this;585 result.sub_overflow(other); // Returned carry value is ignored.586 return result;587 }588 589 LIBC_INLINE constexpr BigInt &operator-=(const BigInt &other) {590 // TODO(lntue): Set overflow flag / errno when carry is true.591 sub_overflow(other); // Returned carry value is ignored.592 return *this;593 }594 595 // Multiply this number with x and store the result in this number.596 LIBC_INLINE constexpr WordType mul(WordType x) {597 return multiword::scalar_multiply_with_carry(val, x);598 }599 600 // Return the full product.601 template <size_t OtherBits>602 LIBC_INLINE constexpr auto603 ful_mul(const BigInt<OtherBits, Signed, WordType> &other) const {604 BigInt<Bits + OtherBits, Signed, WordType> result;605 multiword::multiply_with_carry(result.val, val, other.val);606 return result;607 }608 609 LIBC_INLINE constexpr BigInt operator*(const BigInt &other) const {610 // Perform full mul and truncate.611 return BigInt(ful_mul(other));612 }613 614 // Fast hi part of the full product. The normal product `operator*` returns615 // `Bits` least significant bits of the full product, while this function will616 // approximate `Bits` most significant bits of the full product with errors617 // bounded by:618 // 0 <= (a.full_mul(b) >> Bits) - a.quick_mul_hi(b)) <= WORD_COUNT - 1.619 //620 // An example usage of this is to quickly (but less accurately) compute the621 // product of (normalized) mantissas of floating point numbers:622 // (mant_1, mant_2) -> quick_mul_hi -> normalize leading bit623 // is much more efficient than:624 // (mant_1, mant_2) -> ful_mul -> normalize leading bit625 // -> convert back to same Bits width by shifting/rounding,626 // especially for higher precisions.627 //628 // Performance summary:629 // Number of 64-bit x 64-bit -> 128-bit multiplications performed.630 // Bits WORD_COUNT ful_mul quick_mul_hi Error bound631 // 128 2 4 3 1632 // 196 3 9 6 2633 // 256 4 16 10 3634 // 512 8 64 36 7635 LIBC_INLINE constexpr BigInt quick_mul_hi(const BigInt &other) const {636 BigInt result;637 multiword::quick_mul_hi(result.val, val, other.val);638 return result;639 }640 641 // BigInt(x).pow_n(n) computes x ^ n.642 // Note 0 ^ 0 == 1.643 LIBC_INLINE constexpr void pow_n(uint64_t power) {644 static_assert(!Signed);645 BigInt result = one();646 BigInt cur_power = *this;647 while (power > 0) {648 if ((power % 2) > 0)649 result *= cur_power;650 power >>= 1;651 cur_power *= cur_power;652 }653 *this = result;654 }655 656 // Performs inplace signed / unsigned division. Returns remainder if not657 // dividing by zero.658 // For signed numbers it behaves like C++ signed integer division.659 // That is by truncating the fractionnal part660 // https://stackoverflow.com/a/3602857661 LIBC_INLINE constexpr cpp::optional<BigInt> div(const BigInt ÷r) {662 if (LIBC_UNLIKELY(divider.is_zero()))663 return cpp::nullopt;664 if (LIBC_UNLIKELY(divider == BigInt::one()))665 return BigInt::zero();666 Division result;667 if constexpr (SIGNED)668 result = divide_signed(*this, divider);669 else670 result = divide_unsigned(*this, divider);671 *this = result.quotient;672 return result.remainder;673 }674 675 // Efficiently perform BigInt / (x * 2^e), where x is a half-word-size676 // unsigned integer, and return the remainder. The main idea is as follow:677 // Let q = y / (x * 2^e) be the quotient, and678 // r = y % (x * 2^e) be the remainder.679 // First, notice that:680 // r % (2^e) = y % (2^e),681 // so we just need to focus on all the bits of y that is >= 2^e.682 // To speed up the shift-and-add steps, we only use x as the divisor, and683 // performing 32-bit shiftings instead of bit-by-bit shiftings.684 // Since the remainder of each division step < x < 2^(WORD_SIZE / 2), the685 // computation of each step is now properly contained within WordType.686 // And finally we perform some extra alignment steps for the remaining bits.687 LIBC_INLINE constexpr cpp::optional<BigInt>688 div_uint_half_times_pow_2(multiword::half_width_t<WordType> x, size_t e) {689 BigInt remainder;690 if (x == 0)691 return cpp::nullopt;692 if (e >= Bits) {693 remainder = *this;694 *this = BigInt<Bits, false, WordType>();695 return remainder;696 }697 BigInt quotient;698 WordType x_word = static_cast<WordType>(x);699 constexpr size_t LOG2_WORD_SIZE =700 static_cast<size_t>(cpp::bit_width(WORD_SIZE) - 1);701 constexpr size_t HALF_WORD_SIZE = WORD_SIZE >> 1;702 constexpr WordType HALF_MASK = ((WordType(1) << HALF_WORD_SIZE) - 1);703 // lower = smallest multiple of WORD_SIZE that is >= e.704 size_t lower = ((e >> LOG2_WORD_SIZE) + ((e & (WORD_SIZE - 1)) != 0))705 << LOG2_WORD_SIZE;706 // lower_pos is the index of the closest WORD_SIZE-bit chunk >= 2^e.707 size_t lower_pos = lower / WORD_SIZE;708 // Keep track of current remainder mod x * 2^(32*i)709 WordType rem = 0;710 // pos is the index of the current 64-bit chunk that we are processing.711 size_t pos = WORD_COUNT;712 713 // TODO: look into if constexpr(Bits > 256) skip leading zeroes.714 715 for (size_t q_pos = WORD_COUNT - lower_pos; q_pos > 0; --q_pos) {716 // q_pos is 1 + the index of the current WORD_SIZE-bit chunk of the717 // quotient being processed. Performing the division / modulus with718 // divisor:719 // x * 2^(WORD_SIZE*q_pos - WORD_SIZE/2),720 // i.e. using the upper (WORD_SIZE/2)-bit of the current WORD_SIZE-bit721 // chunk.722 rem <<= HALF_WORD_SIZE;723 rem += val[--pos] >> HALF_WORD_SIZE;724 WordType q_tmp = rem / x_word;725 rem %= x_word;726 727 // Performing the division / modulus with divisor:728 // x * 2^(WORD_SIZE*(q_pos - 1)),729 // i.e. using the lower (WORD_SIZE/2)-bit of the current WORD_SIZE-bit730 // chunk.731 rem <<= HALF_WORD_SIZE;732 rem += val[pos] & HALF_MASK;733 quotient.val[q_pos - 1] = (q_tmp << HALF_WORD_SIZE) + rem / x_word;734 rem %= x_word;735 }736 737 // So far, what we have is:738 // quotient = y / (x * 2^lower), and739 // rem = (y % (x * 2^lower)) / 2^lower.740 // If (lower > e), we will need to perform an extra adjustment of the741 // quotient and remainder, namely:742 // y / (x * 2^e) = [ y / (x * 2^lower) ] * 2^(lower - e) +743 // + (rem * 2^(lower - e)) / x744 // (y % (x * 2^e)) / 2^e = (rem * 2^(lower - e)) % x745 size_t last_shift = lower - e;746 747 if (last_shift > 0) {748 // quotient * 2^(lower - e)749 quotient <<= last_shift;750 WordType q_tmp = 0;751 WordType d = val[--pos];752 if (last_shift >= HALF_WORD_SIZE) {753 // The shifting (rem * 2^(lower - e)) might overflow WordTyoe, so we754 // perform a HALF_WORD_SIZE-bit shift first.755 rem <<= HALF_WORD_SIZE;756 rem += d >> HALF_WORD_SIZE;757 d &= HALF_MASK;758 q_tmp = rem / x_word;759 rem %= x_word;760 last_shift -= HALF_WORD_SIZE;761 } else {762 // Only use the upper HALF_WORD_SIZE-bit of the current WORD_SIZE-bit763 // chunk.764 d >>= HALF_WORD_SIZE;765 }766 767 if (last_shift > 0) {768 rem <<= HALF_WORD_SIZE;769 rem += d;770 q_tmp <<= last_shift;771 x_word <<= HALF_WORD_SIZE - last_shift;772 q_tmp += rem / x_word;773 rem %= x_word;774 }775 776 quotient.val[0] += q_tmp;777 778 if (lower - e <= HALF_WORD_SIZE) {779 // The remainder rem * 2^(lower - e) might overflow to the higher780 // WORD_SIZE-bit chunk.781 if (pos < WORD_COUNT - 1) {782 remainder[pos + 1] = rem >> HALF_WORD_SIZE;783 }784 remainder[pos] = (rem << HALF_WORD_SIZE) + (val[pos] & HALF_MASK);785 } else {786 remainder[pos] = rem;787 }788 789 } else {790 remainder[pos] = rem;791 }792 793 // Set the remaining lower bits of the remainder.794 for (; pos > 0; --pos) {795 remainder[pos - 1] = val[pos - 1];796 }797 798 *this = quotient;799 return remainder;800 }801 802 LIBC_INLINE constexpr BigInt operator/(const BigInt &other) const {803 BigInt result(*this);804 result.div(other);805 return result;806 }807 808 LIBC_INLINE constexpr BigInt &operator/=(const BigInt &other) {809 div(other);810 return *this;811 }812 813 LIBC_INLINE constexpr BigInt operator%(const BigInt &other) const {814 BigInt result(*this);815 return *result.div(other);816 }817 818 LIBC_INLINE constexpr BigInt operator%=(const BigInt &other) {819 *this = *this % other;820 return *this;821 }822 823 LIBC_INLINE constexpr BigInt &operator*=(const BigInt &other) {824 *this = *this * other;825 return *this;826 }827 828 LIBC_INLINE constexpr BigInt &operator<<=(size_t s) {829 val = multiword::shift<multiword::LEFT, SIGNED>(val, s);830 return *this;831 }832 833 LIBC_INLINE constexpr BigInt operator<<(size_t s) const {834 return BigInt(multiword::shift<multiword::LEFT, SIGNED>(val, s));835 }836 837 LIBC_INLINE constexpr BigInt &operator>>=(size_t s) {838 val = multiword::shift<multiword::RIGHT, SIGNED>(val, s);839 return *this;840 }841 842 LIBC_INLINE constexpr BigInt operator>>(size_t s) const {843 return BigInt(multiword::shift<multiword::RIGHT, SIGNED>(val, s));844 }845 846#define DEFINE_BINOP(OP) \847 LIBC_INLINE friend constexpr BigInt operator OP(const BigInt &lhs, \848 const BigInt &rhs) { \849 BigInt result; \850 for (size_t i = 0; i < WORD_COUNT; ++i) \851 result[i] = lhs[i] OP rhs[i]; \852 return result; \853 } \854 LIBC_INLINE friend constexpr BigInt operator OP##=(BigInt &lhs, \855 const BigInt &rhs) { \856 for (size_t i = 0; i < WORD_COUNT; ++i) \857 lhs[i] OP## = rhs[i]; \858 return lhs; \859 }860 861 DEFINE_BINOP(&) // & and &=862 DEFINE_BINOP(|) // | and |=863 DEFINE_BINOP(^) // ^ and ^=864#undef DEFINE_BINOP865 866 LIBC_INLINE constexpr BigInt operator~() const {867 BigInt result;868 for (size_t i = 0; i < WORD_COUNT; ++i)869 result[i] = static_cast<WordType>(~val[i]);870 return result;871 }872 873 LIBC_INLINE constexpr BigInt operator-() const {874 BigInt result(*this);875 result.negate();876 return result;877 }878 879 LIBC_INLINE friend constexpr bool operator==(const BigInt &lhs,880 const BigInt &rhs) {881 for (size_t i = 0; i < WORD_COUNT; ++i)882 if (lhs.val[i] != rhs.val[i])883 return false;884 return true;885 }886 887 LIBC_INLINE friend constexpr bool operator!=(const BigInt &lhs,888 const BigInt &rhs) {889 return !(lhs == rhs);890 }891 892 LIBC_INLINE friend constexpr bool operator>(const BigInt &lhs,893 const BigInt &rhs) {894 return cmp(lhs, rhs) > 0;895 }896 LIBC_INLINE friend constexpr bool operator>=(const BigInt &lhs,897 const BigInt &rhs) {898 return cmp(lhs, rhs) >= 0;899 }900 LIBC_INLINE friend constexpr bool operator<(const BigInt &lhs,901 const BigInt &rhs) {902 return cmp(lhs, rhs) < 0;903 }904 LIBC_INLINE friend constexpr bool operator<=(const BigInt &lhs,905 const BigInt &rhs) {906 return cmp(lhs, rhs) <= 0;907 }908 909 LIBC_INLINE constexpr BigInt &operator++() {910 increment();911 return *this;912 }913 914 LIBC_INLINE constexpr BigInt operator++(int) {915 BigInt oldval(*this);916 increment();917 return oldval;918 }919 920 LIBC_INLINE constexpr BigInt &operator--() {921 decrement();922 return *this;923 }924 925 LIBC_INLINE constexpr BigInt operator--(int) {926 BigInt oldval(*this);927 decrement();928 return oldval;929 }930 931 // Return the i-th word of the number.932 LIBC_INLINE constexpr const WordType &operator[](size_t i) const {933 return val[i];934 }935 936 // Return the i-th word of the number.937 LIBC_INLINE constexpr WordType &operator[](size_t i) { return val[i]; }938 939 // Return the i-th bit of the number.940 LIBC_INLINE constexpr bool get_bit(size_t i) const {941 const size_t word_index = i / WORD_SIZE;942 return 1 & (val[word_index] >> (i % WORD_SIZE));943 }944 945 // Set the i-th bit of the number.946 LIBC_INLINE constexpr void set_bit(size_t i) {947 const size_t word_index = i / WORD_SIZE;948 val[word_index] |= WordType(1) << (i % WORD_SIZE);949 }950 951private:952 LIBC_INLINE friend constexpr int cmp(const BigInt &lhs, const BigInt &rhs) {953 constexpr auto compare = [](WordType a, WordType b) {954 return a == b ? 0 : a > b ? 1 : -1;955 };956 if constexpr (Signed) {957 const bool lhs_is_neg = lhs.is_neg();958 const bool rhs_is_neg = rhs.is_neg();959 if (lhs_is_neg != rhs_is_neg)960 return rhs_is_neg ? 1 : -1;961 }962 for (size_t i = WORD_COUNT; i-- > 0;)963 if (auto cmp = compare(lhs[i], rhs[i]); cmp != 0)964 return cmp;965 return 0;966 }967 968 LIBC_INLINE constexpr void bitwise_not() {969 for (auto &part : val)970 part = static_cast<WordType>(~part);971 }972 973 LIBC_INLINE constexpr void negate() {974 bitwise_not();975 increment();976 }977 978 LIBC_INLINE constexpr void increment() {979 multiword::add_with_carry(val, cpp::array<WordType, 1>{1});980 }981 982 LIBC_INLINE constexpr void decrement() {983 multiword::sub_with_borrow(val, cpp::array<WordType, 1>{1});984 }985 986 LIBC_INLINE constexpr void extend(size_t index, bool is_neg) {987 const WordType value = is_neg ? cpp::numeric_limits<WordType>::max()988 : cpp::numeric_limits<WordType>::min();989 for (size_t i = index; i < WORD_COUNT; ++i)990 val[i] = value;991 }992 993 LIBC_INLINE constexpr bool get_msb() const {994 return val.back() >> (WORD_SIZE - 1);995 }996 997 LIBC_INLINE constexpr void set_msb() {998 val.back() |= mask_leading_ones<WordType, 1>();999 }1000 1001 LIBC_INLINE constexpr void clear_msb() {1002 val.back() &= mask_trailing_ones<WordType, WORD_SIZE - 1>();1003 }1004 LIBC_INLINE constexpr static Division divide_unsigned(const BigInt ÷nd,1005 const BigInt ÷r) {1006 BigInt remainder = dividend;1007 BigInt quotient;1008 if (remainder >= divider) {1009 BigInt subtractor = divider;1010 int cur_bit = multiword::countl_zero(subtractor.val) -1011 multiword::countl_zero(remainder.val);1012 subtractor <<= static_cast<size_t>(cur_bit);1013 for (; cur_bit >= 0 && remainder > 0; --cur_bit, subtractor >>= 1) {1014 if (remainder < subtractor)1015 continue;1016 remainder -= subtractor;1017 quotient.set_bit(static_cast<size_t>(cur_bit));1018 }1019 }1020 return Division{quotient, remainder};1021 }1022 1023 LIBC_INLINE constexpr static Division divide_signed(const BigInt ÷nd,1024 const BigInt ÷r) {1025 // Special case because it is not possible to negate the min value of a1026 // signed integer.1027 if (dividend == min() && divider == min())1028 return Division{one(), zero()};1029 // 1. Convert the dividend and divisor to unsigned representation.1030 unsigned_type udividend(dividend);1031 unsigned_type udivider(divider);1032 // 2. Negate the dividend if it's negative, and similarly for the divisor.1033 const bool dividend_is_neg = dividend.is_neg();1034 const bool divider_is_neg = divider.is_neg();1035 if (dividend_is_neg)1036 udividend.negate();1037 if (divider_is_neg)1038 udivider.negate();1039 // 3. Use unsigned multiword division algorithm.1040 const auto unsigned_result = divide_unsigned(udividend, udivider);1041 // 4. Convert the quotient and remainder to signed representation.1042 Division result;1043 result.quotient = signed_type(unsigned_result.quotient);1044 result.remainder = signed_type(unsigned_result.remainder);1045 // 5. Negate the quotient if the dividend and divisor had opposite signs.1046 if (dividend_is_neg != divider_is_neg)1047 result.quotient.negate();1048 // 6. Negate the remainder if the dividend was negative.1049 if (dividend_is_neg)1050 result.remainder.negate();1051 return result;1052 }1053 1054 friend signed_type;1055 friend unsigned_type;1056};1057 1058namespace internal {1059// We default BigInt's WordType to 'uint64_t' or 'uint32_t' depending on type1060// availability.1061template <size_t Bits>1062struct WordTypeSelector : cpp::type_identity<1063#ifdef LIBC_TYPES_HAS_INT641064 uint64_t1065#else1066 uint32_t1067#endif // LIBC_TYPES_HAS_INT641068 > {1069};1070// Except if we request 16 or 32 bits explicitly.1071template <> struct WordTypeSelector<16> : cpp::type_identity<uint16_t> {};1072template <> struct WordTypeSelector<32> : cpp::type_identity<uint32_t> {};1073template <> struct WordTypeSelector<96> : cpp::type_identity<uint32_t> {};1074 1075template <size_t Bits>1076using WordTypeSelectorT = typename WordTypeSelector<Bits>::type;1077} // namespace internal1078 1079template <size_t Bits>1080using UInt = BigInt<Bits, false, internal::WordTypeSelectorT<Bits>>;1081 1082template <size_t Bits>1083using Int = BigInt<Bits, true, internal::WordTypeSelectorT<Bits>>;1084 1085// Provides limits of BigInt.1086template <size_t Bits, bool Signed, typename T>1087struct cpp::numeric_limits<BigInt<Bits, Signed, T>> {1088 LIBC_INLINE static constexpr BigInt<Bits, Signed, T> max() {1089 return BigInt<Bits, Signed, T>::max();1090 }1091 LIBC_INLINE static constexpr BigInt<Bits, Signed, T> min() {1092 return BigInt<Bits, Signed, T>::min();1093 }1094 // Meant to match std::numeric_limits interface.1095 // NOLINTNEXTLINE(readability-identifier-naming)1096 LIBC_INLINE_VAR static constexpr int digits = Bits - Signed;1097};1098 1099// type traits to determine whether a T is a BigInt.1100template <typename T> struct is_big_int : cpp::false_type {};1101 1102template <size_t Bits, bool Signed, typename T>1103struct is_big_int<BigInt<Bits, Signed, T>> : cpp::true_type {};1104 1105template <class T>1106LIBC_INLINE_VAR constexpr bool is_big_int_v = is_big_int<T>::value;1107 1108// extensions of type traits to include BigInt1109 1110// is_integral_or_big_int1111template <typename T>1112struct is_integral_or_big_int1113 : cpp::bool_constant<(cpp::is_integral_v<T> || is_big_int_v<T>)> {};1114 1115template <typename T>1116LIBC_INLINE_VAR constexpr bool is_integral_or_big_int_v =1117 is_integral_or_big_int<T>::value;1118 1119// make_big_int_unsigned1120template <typename T> struct make_big_int_unsigned;1121 1122template <size_t Bits, bool Signed, typename T>1123struct make_big_int_unsigned<BigInt<Bits, Signed, T>>1124 : cpp::type_identity<BigInt<Bits, false, T>> {};1125 1126template <typename T>1127using make_big_int_unsigned_t = typename make_big_int_unsigned<T>::type;1128 1129// make_big_int_signed1130template <typename T> struct make_big_int_signed;1131 1132template <size_t Bits, bool Signed, typename T>1133struct make_big_int_signed<BigInt<Bits, Signed, T>>1134 : cpp::type_identity<BigInt<Bits, true, T>> {};1135 1136template <typename T>1137using make_big_int_signed_t = typename make_big_int_signed<T>::type;1138 1139// make_integral_or_big_int_unsigned1140template <typename T, class = void> struct make_integral_or_big_int_unsigned;1141 1142template <typename T>1143struct make_integral_or_big_int_unsigned<1144 T, cpp::enable_if_t<cpp::is_integral_v<T>>> : cpp::make_unsigned<T> {};1145 1146template <typename T>1147struct make_integral_or_big_int_unsigned<T, cpp::enable_if_t<is_big_int_v<T>>>1148 : make_big_int_unsigned<T> {};1149 1150template <typename T>1151using make_integral_or_big_int_unsigned_t =1152 typename make_integral_or_big_int_unsigned<T>::type;1153 1154// make_integral_or_big_int_signed1155template <typename T, class = void> struct make_integral_or_big_int_signed;1156 1157template <typename T>1158struct make_integral_or_big_int_signed<T,1159 cpp::enable_if_t<cpp::is_integral_v<T>>>1160 : cpp::make_signed<T> {};1161 1162template <typename T>1163struct make_integral_or_big_int_signed<T, cpp::enable_if_t<is_big_int_v<T>>>1164 : make_big_int_signed<T> {};1165 1166template <typename T>1167using make_integral_or_big_int_signed_t =1168 typename make_integral_or_big_int_signed<T>::type;1169 1170// is_unsigned_integral_or_big_int1171template <typename T>1172struct is_unsigned_integral_or_big_int1173 : cpp::bool_constant<1174 cpp::is_same_v<T, make_integral_or_big_int_unsigned_t<T>>> {};1175 1176template <typename T>1177// Meant to look like <type_traits> helper variable templates.1178// NOLINTNEXTLINE(readability-identifier-naming)1179LIBC_INLINE_VAR constexpr bool is_unsigned_integral_or_big_int_v =1180 is_unsigned_integral_or_big_int<T>::value;1181 1182namespace cpp {1183 1184// Specialization of cpp::bit_cast ('bit.h') from T to BigInt.1185template <typename To, typename From>1186LIBC_INLINE constexpr cpp::enable_if_t<1187 (sizeof(To) == sizeof(From)) && cpp::is_trivially_copyable<To>::value &&1188 cpp::is_trivially_copyable<From>::value && is_big_int<To>::value,1189 To>1190bit_cast(const From &from) {1191 To out;1192 using Storage = decltype(out.val);1193 out.val = cpp::bit_cast<Storage>(from);1194 return out;1195}1196 1197// Specialization of cpp::bit_cast ('bit.h') from BigInt to T.1198template <typename To, size_t Bits>1199LIBC_INLINE constexpr cpp::enable_if_t<1200 sizeof(To) == sizeof(UInt<Bits>) &&1201 cpp::is_trivially_constructible<To>::value &&1202 cpp::is_trivially_copyable<To>::value &&1203 cpp::is_trivially_copyable<UInt<Bits>>::value,1204 To>1205bit_cast(const UInt<Bits> &from) {1206 return cpp::bit_cast<To>(from.val);1207}1208 1209// Specialization of cpp::popcount ('bit.h') for BigInt.1210template <typename T>1211[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1212popcount(T value) {1213 int bits = 0;1214 for (auto word : value.val)1215 if (word)1216 bits += popcount(word);1217 return bits;1218}1219 1220// Specialization of cpp::has_single_bit ('bit.h') for BigInt.1221template <typename T>1222[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, bool>1223has_single_bit(T value) {1224 int bits = 0;1225 for (auto word : value.val) {1226 if (word == 0)1227 continue;1228 bits += popcount(word);1229 if (bits > 1)1230 return false;1231 }1232 return bits == 1;1233}1234 1235// Specialization of cpp::countr_zero ('bit.h') for BigInt.1236template <typename T>1237[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1238countr_zero(const T &value) {1239 return multiword::countr_zero(value.val);1240}1241 1242// Specialization of cpp::countl_zero ('bit.h') for BigInt.1243template <typename T>1244[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1245countl_zero(const T &value) {1246 return multiword::countl_zero(value.val);1247}1248 1249// Specialization of cpp::countl_one ('bit.h') for BigInt.1250template <typename T>1251[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1252countl_one(T value) {1253 return multiword::countl_one(value.val);1254}1255 1256// Specialization of cpp::countr_one ('bit.h') for BigInt.1257template <typename T>1258[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1259countr_one(T value) {1260 return multiword::countr_one(value.val);1261}1262 1263// Specialization of cpp::bit_width ('bit.h') for BigInt.1264template <typename T>1265[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1266bit_width(T value) {1267 return cpp::numeric_limits<T>::digits - cpp::countl_zero(value);1268}1269 1270// Forward-declare rotr so that rotl can use it.1271template <typename T>1272[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>1273rotr(T value, int rotate);1274 1275// Specialization of cpp::rotl ('bit.h') for BigInt.1276template <typename T>1277[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>1278rotl(T value, int rotate) {1279 constexpr int N = cpp::numeric_limits<T>::digits;1280 rotate = rotate % N;1281 if (!rotate)1282 return value;1283 if (rotate < 0)1284 return cpp::rotr<T>(value, -rotate);1285 return (value << static_cast<size_t>(rotate)) |1286 (value >> (N - static_cast<size_t>(rotate)));1287}1288 1289// Specialization of cpp::rotr ('bit.h') for BigInt.1290template <typename T>1291[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>1292rotr(T value, int rotate) {1293 constexpr int N = cpp::numeric_limits<T>::digits;1294 rotate = rotate % N;1295 if (!rotate)1296 return value;1297 if (rotate < 0)1298 return cpp::rotl<T>(value, -rotate);1299 return (value >> static_cast<size_t>(rotate)) |1300 (value << (N - static_cast<size_t>(rotate)));1301}1302 1303} // namespace cpp1304 1305// Specialization of mask_trailing_ones ('math_extras.h') for BigInt.1306template <typename T, size_t count>1307LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>1308mask_trailing_ones() {1309 static_assert(!T::SIGNED && count <= T::BITS);1310 if (count == T::BITS)1311 return T::all_ones();1312 constexpr size_t QUOTIENT = count / T::WORD_SIZE;1313 constexpr size_t REMAINDER = count % T::WORD_SIZE;1314 T out; // zero initialized1315 for (size_t i = 0; i <= QUOTIENT; ++i)1316 out[i] = i < QUOTIENT1317 ? cpp::numeric_limits<typename T::word_type>::max()1318 : mask_trailing_ones<typename T::word_type, REMAINDER>();1319 return out;1320}1321 1322// Specialization of mask_leading_ones ('math_extras.h') for BigInt.1323template <typename T, size_t count>1324LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> mask_leading_ones() {1325 static_assert(!T::SIGNED && count <= T::BITS);1326 if (count == T::BITS)1327 return T::all_ones();1328 constexpr size_t QUOTIENT = (T::BITS - count - 1U) / T::WORD_SIZE;1329 constexpr size_t REMAINDER = count % T::WORD_SIZE;1330 T out; // zero initialized1331 for (size_t i = QUOTIENT; i < T::WORD_COUNT; ++i)1332 out[i] = i > QUOTIENT1333 ? cpp::numeric_limits<typename T::word_type>::max()1334 : mask_leading_ones<typename T::word_type, REMAINDER>();1335 return out;1336}1337 1338// Specialization of mask_trailing_zeros ('math_extras.h') for BigInt.1339template <typename T, size_t count>1340LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>1341mask_trailing_zeros() {1342 return mask_leading_ones<T, T::BITS - count>();1343}1344 1345// Specialization of mask_leading_zeros ('math_extras.h') for BigInt.1346template <typename T, size_t count>1347LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>1348mask_leading_zeros() {1349 return mask_trailing_ones<T, T::BITS - count>();1350}1351 1352// Specialization of count_zeros ('math_extras.h') for BigInt.1353template <typename T>1354[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1355count_zeros(T value) {1356 return cpp::popcount(~value);1357}1358 1359// Specialization of first_leading_zero ('math_extras.h') for BigInt.1360template <typename T>1361[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1362first_leading_zero(T value) {1363 return value == cpp::numeric_limits<T>::max() ? 01364 : cpp::countl_one(value) + 1;1365}1366 1367// Specialization of first_leading_one ('math_extras.h') for BigInt.1368template <typename T>1369[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1370first_leading_one(T value) {1371 return first_leading_zero(~value);1372}1373 1374// Specialization of first_trailing_zero ('math_extras.h') for BigInt.1375template <typename T>1376[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1377first_trailing_zero(T value) {1378 return value == cpp::numeric_limits<T>::max() ? 01379 : cpp::countr_zero(~value) + 1;1380}1381 1382// Specialization of first_trailing_one ('math_extras.h') for BigInt.1383template <typename T>1384[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>1385first_trailing_one(T value) {1386 return value == 0 ? 0 : cpp::countr_zero(value) + 1;1387}1388 1389} // namespace LIBC_NAMESPACE_DECL1390 1391#endif // LLVM_LIBC_SRC___SUPPORT_BIG_INT_H1392