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

source code of libc/src/__support/big_int.h