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_BIG_INT_H
10#define LLVM_LIBC_SRC___SUPPORT_BIG_INT_H
11
12#include "hdr/stdint_proxy.h"
13#include "src/__support/CPP/array.h"
14#include "src/__support/CPP/bit.h" // countl_zero
15#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_INLINE
19#include "src/__support/macros/config.h"
20#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY
21#include "src/__support/macros/properties/compiler.h" // LIBC_COMPILER_IS_CLANG
22#include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128, LIBC_TYPES_HAS_INT64
23#include "src/__support/math_extras.h" // add_with_carry, sub_with_borrow
24#include "src/__support/number_pair.h"
25
26#include <stddef.h> // For size_t
27
28namespace LIBC_NAMESPACE_DECL {
29
30namespace multiword {
31
32// A type trait mapping unsigned integers to their half-width unsigned
33// 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_INT64
38template <> struct half_width<uint64_t> : cpp::type_identity<uint32_t> {};
39#ifdef LIBC_TYPES_HAS_INT128
40template <> struct half_width<__uint128_t> : cpp::type_identity<uint64_t> {};
41#endif // LIBC_TYPES_HAS_INT128
42#endif // LIBC_TYPES_HAS_INT64
43template <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>(value: uint16_t(a) * uint16_t(b));
83 } else if constexpr (cpp::is_same_v<word, uint16_t>) {
84 return split<uint32_t>(value: uint32_t(a) * uint32_t(b));
85 }
86#ifdef LIBC_TYPES_HAS_INT64
87 else if constexpr (cpp::is_same_v<word, uint32_t>) {
88 return split<uint64_t>(value: uint64_t(a) * uint64_t(b));
89 }
90#endif
91#ifdef LIBC_TYPES_HAS_INT128
92 else if constexpr (cpp::is_same_v<word, uint64_t>) {
93 return split<__uint128_t>(value: __uint128_t(a) * __uint128_t(b));
94 }
95#endif
96 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 type
105 // word. We split 'a' and 'b' into half words and perform the classic long
106 // multiplication with 'a' and 'b' being two-digit numbers.
107
108 // a a_hi a_lo
109 // x b => x b_hi b_lo
110 // ---- -----------
111 // c result
112 // We convert 'lo' and 'hi' from 'half_word' to 'word' so multiplication
113 // 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 multiword
177// 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/20793834
206// https://pages.cs.wisc.edu/%7Emarkhill/cs354/Fall2008/beyond354/int.mult.html
207template <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 constexpr size_t WORD_BITS = cpp::numeric_limits<word>::digits;
246 return (array.back() >> (WORD_BITS - 1)) != 0;
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#if LIBC_HAS_BUILTIN_BIT_CAST
260#ifdef LIBC_TYPES_HAS_INT128
261 constexpr size_t TOTAL_BITS = N * WORD_BITS;
262 if constexpr (TOTAL_BITS == 128 &&
263 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) {
264 using type = cpp::conditional_t<is_signed, __int128_t, __uint128_t>;
265 auto tmp = cpp::bit_cast<type>(array);
266 if constexpr (direction == LEFT)
267 tmp <<= offset;
268 else
269 tmp >>= offset;
270 return cpp::bit_cast<cpp::array<word, N>>(tmp);
271 }
272#endif
273#endif // LIBC_HAS_BUILTIN_BIT_CAST
274
275 if (LIBC_UNLIKELY(offset == 0))
276 return array;
277 const bool is_neg = is_signed && is_negative(array);
278 constexpr auto at = [](size_t index) -> int {
279 // reverse iteration when direction == LEFT.
280 if constexpr (direction == LEFT)
281 return int(N) - int(index) - 1;
282 return int(index);
283 };
284 const auto safe_get_at = [&](size_t index) -> word {
285 // return appropriate value when accessing out of bound elements.
286 const int i = at(index);
287 if (i < 0)
288 return 0;
289 if (i >= int(N))
290 return is_neg ? cpp::numeric_limits<word>::max() : 0;
291 return array[static_cast<unsigned>(i)];
292 };
293 const size_t index_offset = offset / WORD_BITS;
294 const size_t bit_offset = offset % WORD_BITS;
295#ifdef LIBC_COMPILER_IS_CLANG
296 __builtin_assume(index_offset < N);
297#endif
298 cpp::array<word, N> out = {};
299 for (size_t index = 0; index < N; ++index) {
300 const word part1 = safe_get_at(index + index_offset);
301 const word part2 = safe_get_at(index + index_offset + 1);
302 word &dst = out[static_cast<unsigned>(at(index))];
303 if (bit_offset == 0)
304 dst = part1; // no crosstalk between parts.
305 else if constexpr (direction == LEFT)
306 dst = static_cast<word>((part1 << bit_offset) |
307 (part2 >> (WORD_BITS - bit_offset)));
308 else
309 dst = static_cast<word>((part1 >> bit_offset) |
310 (part2 << (WORD_BITS - bit_offset)));
311 }
312 return out;
313}
314
315#define DECLARE_COUNTBIT(NAME, INDEX_EXPR) \
316 template <typename word, size_t N> \
317 LIBC_INLINE constexpr int NAME(const cpp::array<word, N> &val) { \
318 int bit_count = 0; \
319 for (size_t i = 0; i < N; ++i) { \
320 const int word_count = cpp::NAME<word>(val[INDEX_EXPR]); \
321 bit_count += word_count; \
322 if (word_count != cpp::numeric_limits<word>::digits) \
323 break; \
324 } \
325 return bit_count; \
326 }
327
328DECLARE_COUNTBIT(countr_zero, i) // iterating forward
329DECLARE_COUNTBIT(countr_one, i) // iterating forward
330DECLARE_COUNTBIT(countl_zero, N - i - 1) // iterating backward
331DECLARE_COUNTBIT(countl_one, N - i - 1) // iterating backward
332
333} // namespace multiword
334
335template <size_t Bits, bool Signed, typename WordType = uint64_t>
336struct BigInt {
337private:
338 static_assert(cpp::is_integral_v<WordType> && cpp::is_unsigned_v<WordType>,
339 "WordType must be unsigned integer.");
340
341 struct Division {
342 BigInt quotient;
343 BigInt remainder;
344 };
345
346public:
347 using word_type = WordType;
348 using unsigned_type = BigInt<Bits, false, word_type>;
349 using signed_type = BigInt<Bits, true, word_type>;
350
351 LIBC_INLINE_VAR static constexpr bool SIGNED = Signed;
352 LIBC_INLINE_VAR static constexpr size_t BITS = Bits;
353 LIBC_INLINE_VAR
354 static constexpr size_t WORD_SIZE = sizeof(WordType) * CHAR_BIT;
355
356 static_assert(Bits > 0 && Bits % WORD_SIZE == 0,
357 "Number of bits in BigInt should be a multiple of WORD_SIZE.");
358
359 LIBC_INLINE_VAR static constexpr size_t WORD_COUNT = Bits / WORD_SIZE;
360
361 cpp::array<WordType, WORD_COUNT> val{}; // zero initialized.
362
363 LIBC_INLINE constexpr BigInt() = default;
364
365 LIBC_INLINE constexpr BigInt(const BigInt &other) = default;
366
367 template <size_t OtherBits, bool OtherSigned, typename OtherWordType>
368 LIBC_INLINE constexpr BigInt(
369 const BigInt<OtherBits, OtherSigned, OtherWordType> &other) {
370 using BigIntOther = BigInt<OtherBits, OtherSigned, OtherWordType>;
371 [[maybe_unused]] const bool should_sign_extend = Signed && other.is_neg();
372
373 static_assert(!(Bits == OtherBits && WORD_SIZE != BigIntOther::WORD_SIZE) &&
374 "This is currently untested for casting between bigints with "
375 "the same bit width but different word sizes.");
376
377 if constexpr (BigIntOther::WORD_SIZE < WORD_SIZE) {
378 // OtherWordType is smaller
379 constexpr size_t WORD_SIZE_RATIO = WORD_SIZE / BigIntOther::WORD_SIZE;
380 static_assert(
381 (WORD_SIZE % BigIntOther::WORD_SIZE) == 0 &&
382 "Word types must be multiples of each other for correct conversion.");
383 if constexpr (OtherBits >= Bits) { // truncate
384 // for each big word
385 for (size_t i = 0; i < WORD_COUNT; ++i) {
386 WordType cur_word = 0;
387 // combine WORD_SIZE_RATIO small words into a big word
388 for (size_t j = 0; j < WORD_SIZE_RATIO; ++j)
389 cur_word |= static_cast<WordType>(other[(i * WORD_SIZE_RATIO) + j])
390 << (BigIntOther::WORD_SIZE * j);
391
392 val[i] = cur_word;
393 }
394 } else { // zero or sign extend
395 size_t i = 0;
396 WordType cur_word = 0;
397 // for each small word
398 for (; i < BigIntOther::WORD_COUNT; ++i) {
399 // combine WORD_SIZE_RATIO small words into a big word
400 cur_word |= static_cast<WordType>(other[i])
401 << (BigIntOther::WORD_SIZE * (i % WORD_SIZE_RATIO));
402 // if we've completed a big word, copy it into place and reset
403 if ((i % WORD_SIZE_RATIO) == WORD_SIZE_RATIO - 1) {
404 val[i / WORD_SIZE_RATIO] = cur_word;
405 cur_word = 0;
406 }
407 }
408 // Pretend there are extra words of the correct sign extension as needed
409
410 const WordType extension_bits =
411 should_sign_extend ? cpp::numeric_limits<WordType>::max()
412 : cpp::numeric_limits<WordType>::min();
413 if ((i % WORD_SIZE_RATIO) != 0) {
414 cur_word |= static_cast<WordType>(extension_bits)
415 << (BigIntOther::WORD_SIZE * (i % WORD_SIZE_RATIO));
416 }
417 // Copy the last word into place.
418 val[(i / WORD_SIZE_RATIO)] = cur_word;
419 extend(index: (i / WORD_SIZE_RATIO) + 1, is_neg: should_sign_extend);
420 }
421 } else if constexpr (BigIntOther::WORD_SIZE == WORD_SIZE) {
422 if constexpr (OtherBits >= Bits) { // truncate
423 for (size_t i = 0; i < WORD_COUNT; ++i)
424 val[i] = other[i];
425 } else { // zero or sign extend
426 size_t i = 0;
427 for (; i < BigIntOther::WORD_COUNT; ++i)
428 val[i] = other[i];
429 extend(index: i, is_neg: should_sign_extend);
430 }
431 } else {
432 // OtherWordType is bigger.
433 constexpr size_t WORD_SIZE_RATIO = BigIntOther::WORD_SIZE / WORD_SIZE;
434 static_assert(
435 (BigIntOther::WORD_SIZE % WORD_SIZE) == 0 &&
436 "Word types must be multiples of each other for correct conversion.");
437 if constexpr (OtherBits >= Bits) { // truncate
438 // for each small word
439 for (size_t i = 0; i < WORD_COUNT; ++i) {
440 // split each big word into WORD_SIZE_RATIO small words
441 val[i] = static_cast<WordType>(other[i / WORD_SIZE_RATIO] >>
442 ((i % WORD_SIZE_RATIO) * WORD_SIZE));
443 }
444 } else { // zero or sign extend
445 size_t i = 0;
446 // for each big word
447 for (; i < BigIntOther::WORD_COUNT; ++i) {
448 // split each big word into WORD_SIZE_RATIO small words
449 for (size_t j = 0; j < WORD_SIZE_RATIO; ++j)
450 val[(i * WORD_SIZE_RATIO) + j] =
451 static_cast<WordType>(other[i] >> (j * WORD_SIZE));
452 }
453 extend(index: i * WORD_SIZE_RATIO, is_neg: should_sign_extend);
454 }
455 }
456 }
457
458 // Construct a BigInt from a C array.
459 template <size_t N> LIBC_INLINE constexpr BigInt(const WordType (&nums)[N]) {
460 static_assert(N == WORD_COUNT);
461 for (size_t i = 0; i < WORD_COUNT; ++i)
462 val[i] = nums[i];
463 }
464
465 LIBC_INLINE constexpr explicit BigInt(
466 const cpp::array<WordType, WORD_COUNT> &words) {
467 val = words;
468 }
469
470 // Initialize the first word to |v| and the rest to 0.
471 template <typename T, typename = cpp::enable_if_t<cpp::is_integral_v<T>>>
472 LIBC_INLINE constexpr BigInt(T v) {
473 constexpr size_t T_SIZE = sizeof(T) * CHAR_BIT;
474 const bool is_neg = v < 0;
475 for (size_t i = 0; i < WORD_COUNT; ++i) {
476 if (v == 0) {
477 extend(index: i, is_neg);
478 return;
479 }
480 val[i] = static_cast<WordType>(v);
481 if constexpr (T_SIZE > WORD_SIZE)
482 v >>= WORD_SIZE;
483 else
484 v = 0;
485 }
486 }
487 LIBC_INLINE constexpr BigInt &operator=(const BigInt &other) = default;
488
489 // constants
490 LIBC_INLINE static constexpr BigInt zero() { return BigInt(); }
491 LIBC_INLINE static constexpr BigInt one() { return BigInt(1); }
492 LIBC_INLINE static constexpr BigInt all_ones() { return ~zero(); }
493 LIBC_INLINE static constexpr BigInt min() {
494 BigInt out;
495 if constexpr (SIGNED)
496 out.set_msb();
497 return out;
498 }
499 LIBC_INLINE static constexpr BigInt max() {
500 BigInt out = all_ones();
501 if constexpr (SIGNED)
502 out.clear_msb();
503 return out;
504 }
505
506 // TODO: Reuse the Sign type.
507 LIBC_INLINE constexpr bool is_neg() const { return SIGNED && get_msb(); }
508
509 template <size_t OtherBits, bool OtherSigned, typename OtherWordType>
510 LIBC_INLINE constexpr explicit
511 operator BigInt<OtherBits, OtherSigned, OtherWordType>() const {
512 return BigInt<OtherBits, OtherSigned, OtherWordType>(this);
513 }
514
515 template <typename T> LIBC_INLINE constexpr explicit operator T() const {
516 return to<T>();
517 }
518
519 template <typename T>
520 LIBC_INLINE constexpr cpp::enable_if_t<
521 cpp::is_integral_v<T> && !cpp::is_same_v<T, bool>, T>
522 to() const {
523 constexpr size_t T_SIZE = sizeof(T) * CHAR_BIT;
524 T lo = static_cast<T>(val[0]);
525 if constexpr (T_SIZE <= WORD_SIZE)
526 return lo;
527 constexpr size_t MAX_COUNT =
528 T_SIZE > Bits ? WORD_COUNT : T_SIZE / WORD_SIZE;
529 for (size_t i = 1; i < MAX_COUNT; ++i)
530 lo += static_cast<T>(static_cast<T>(val[i]) << (WORD_SIZE * i));
531 if constexpr (Signed && (T_SIZE > Bits)) {
532 // Extend sign for negative numbers.
533 constexpr T MASK = (~T(0) << Bits);
534 if (is_neg())
535 lo |= MASK;
536 }
537 return lo;
538 }
539
540 LIBC_INLINE constexpr explicit operator bool() const { return !is_zero(); }
541
542 LIBC_INLINE constexpr bool is_zero() const {
543 for (auto part : val)
544 if (part != 0)
545 return false;
546 return true;
547 }
548
549 // Add 'rhs' to this number and store the result in this number.
550 // Returns the carry value produced by the addition operation.
551 LIBC_INLINE constexpr WordType add_overflow(const BigInt &rhs) {
552 return multiword::add_with_carry(val, rhs.val);
553 }
554
555 LIBC_INLINE constexpr BigInt operator+(const BigInt &other) const {
556 BigInt result = *this;
557 result.add_overflow(rhs: other);
558 return result;
559 }
560
561 // This will only apply when initializing a variable from constant values, so
562 // it will always use the constexpr version of add_with_carry.
563 LIBC_INLINE constexpr BigInt operator+(BigInt &&other) const {
564 // We use addition commutativity to reuse 'other' and prevent allocation.
565 other.add_overflow(rhs: *this); // Returned carry value is ignored.
566 return other;
567 }
568
569 LIBC_INLINE constexpr BigInt &operator+=(const BigInt &other) {
570 add_overflow(rhs: other); // Returned carry value is ignored.
571 return *this;
572 }
573
574 // Subtract 'rhs' to this number and store the result in this number.
575 // Returns the carry value produced by the subtraction operation.
576 LIBC_INLINE constexpr WordType sub_overflow(const BigInt &rhs) {
577 return multiword::sub_with_borrow(val, rhs.val);
578 }
579
580 LIBC_INLINE constexpr BigInt operator-(const BigInt &other) const {
581 BigInt result = *this;
582 result.sub_overflow(rhs: other); // Returned carry value is ignored.
583 return result;
584 }
585
586 LIBC_INLINE constexpr BigInt operator-(BigInt &&other) const {
587 BigInt result = *this;
588 result.sub_overflow(rhs: other); // Returned carry value is ignored.
589 return result;
590 }
591
592 LIBC_INLINE constexpr BigInt &operator-=(const BigInt &other) {
593 // TODO(lntue): Set overflow flag / errno when carry is true.
594 sub_overflow(rhs: other); // Returned carry value is ignored.
595 return *this;
596 }
597
598 // Multiply this number with x and store the result in this number.
599 LIBC_INLINE constexpr WordType mul(WordType x) {
600 return multiword::scalar_multiply_with_carry(val, x);
601 }
602
603 // Return the full product.
604 template <size_t OtherBits>
605 LIBC_INLINE constexpr auto
606 ful_mul(const BigInt<OtherBits, Signed, WordType> &other) const {
607 BigInt<Bits + OtherBits, Signed, WordType> result;
608 multiword::multiply_with_carry(result.val, val, other.val);
609 return result;
610 }
611
612 LIBC_INLINE constexpr BigInt operator*(const BigInt &other) const {
613 // Perform full mul and truncate.
614 return BigInt(ful_mul(other));
615 }
616
617 // Fast hi part of the full product. The normal product `operator*` returns
618 // `Bits` least significant bits of the full product, while this function will
619 // approximate `Bits` most significant bits of the full product with errors
620 // bounded by:
621 // 0 <= (a.full_mul(b) >> Bits) - a.quick_mul_hi(b)) <= WORD_COUNT - 1.
622 //
623 // An example usage of this is to quickly (but less accurately) compute the
624 // product of (normalized) mantissas of floating point numbers:
625 // (mant_1, mant_2) -> quick_mul_hi -> normalize leading bit
626 // is much more efficient than:
627 // (mant_1, mant_2) -> ful_mul -> normalize leading bit
628 // -> convert back to same Bits width by shifting/rounding,
629 // especially for higher precisions.
630 //
631 // Performance summary:
632 // Number of 64-bit x 64-bit -> 128-bit multiplications performed.
633 // Bits WORD_COUNT ful_mul quick_mul_hi Error bound
634 // 128 2 4 3 1
635 // 196 3 9 6 2
636 // 256 4 16 10 3
637 // 512 8 64 36 7
638 LIBC_INLINE constexpr BigInt quick_mul_hi(const BigInt &other) const {
639 BigInt result;
640 multiword::quick_mul_hi(result.val, val, other.val);
641 return result;
642 }
643
644 // BigInt(x).pow_n(n) computes x ^ n.
645 // Note 0 ^ 0 == 1.
646 LIBC_INLINE constexpr void pow_n(uint64_t power) {
647 static_assert(!Signed);
648 BigInt result = one();
649 BigInt cur_power = *this;
650 while (power > 0) {
651 if ((power % 2) > 0)
652 result *= cur_power;
653 power >>= 1;
654 cur_power *= cur_power;
655 }
656 *this = result;
657 }
658
659 // Performs inplace signed / unsigned division. Returns remainder if not
660 // dividing by zero.
661 // For signed numbers it behaves like C++ signed integer division.
662 // That is by truncating the fractionnal part
663 // https://stackoverflow.com/a/3602857
664 LIBC_INLINE constexpr cpp::optional<BigInt> div(const BigInt &divider) {
665 if (LIBC_UNLIKELY(divider.is_zero()))
666 return cpp::nullopt;
667 if (LIBC_UNLIKELY(divider == BigInt::one()))
668 return BigInt::zero();
669 Division result;
670 if constexpr (SIGNED)
671 result = divide_signed(dividend: *this, divider);
672 else
673 result = divide_unsigned(dividend: *this, divider);
674 *this = result.quotient;
675 return result.remainder;
676 }
677
678 // Efficiently perform BigInt / (x * 2^e), where x is a half-word-size
679 // unsigned integer, and return the remainder. The main idea is as follow:
680 // Let q = y / (x * 2^e) be the quotient, and
681 // r = y % (x * 2^e) be the remainder.
682 // First, notice that:
683 // r % (2^e) = y % (2^e),
684 // so we just need to focus on all the bits of y that is >= 2^e.
685 // To speed up the shift-and-add steps, we only use x as the divisor, and
686 // performing 32-bit shiftings instead of bit-by-bit shiftings.
687 // Since the remainder of each division step < x < 2^(WORD_SIZE / 2), the
688 // computation of each step is now properly contained within WordType.
689 // And finally we perform some extra alignment steps for the remaining bits.
690 LIBC_INLINE constexpr cpp::optional<BigInt>
691 div_uint_half_times_pow_2(multiword::half_width_t<WordType> x, size_t e) {
692 BigInt remainder;
693 if (x == 0)
694 return cpp::nullopt;
695 if (e >= Bits) {
696 remainder = *this;
697 *this = BigInt<Bits, false, WordType>();
698 return remainder;
699 }
700 BigInt quotient;
701 WordType x_word = static_cast<WordType>(x);
702 constexpr size_t LOG2_WORD_SIZE =
703 static_cast<size_t>(cpp::bit_width(value: WORD_SIZE) - 1);
704 constexpr size_t HALF_WORD_SIZE = WORD_SIZE >> 1;
705 constexpr WordType HALF_MASK = ((WordType(1) << HALF_WORD_SIZE) - 1);
706 // lower = smallest multiple of WORD_SIZE that is >= e.
707 size_t lower = ((e >> LOG2_WORD_SIZE) + ((e & (WORD_SIZE - 1)) != 0))
708 << LOG2_WORD_SIZE;
709 // lower_pos is the index of the closest WORD_SIZE-bit chunk >= 2^e.
710 size_t lower_pos = lower / WORD_SIZE;
711 // Keep track of current remainder mod x * 2^(32*i)
712 WordType rem = 0;
713 // pos is the index of the current 64-bit chunk that we are processing.
714 size_t pos = WORD_COUNT;
715
716 // TODO: look into if constexpr(Bits > 256) skip leading zeroes.
717
718 for (size_t q_pos = WORD_COUNT - lower_pos; q_pos > 0; --q_pos) {
719 // q_pos is 1 + the index of the current WORD_SIZE-bit chunk of the
720 // quotient being processed. Performing the division / modulus with
721 // divisor:
722 // x * 2^(WORD_SIZE*q_pos - WORD_SIZE/2),
723 // i.e. using the upper (WORD_SIZE/2)-bit of the current WORD_SIZE-bit
724 // chunk.
725 rem <<= HALF_WORD_SIZE;
726 rem += val[--pos] >> HALF_WORD_SIZE;
727 WordType q_tmp = rem / x_word;
728 rem %= x_word;
729
730 // Performing the division / modulus with divisor:
731 // x * 2^(WORD_SIZE*(q_pos - 1)),
732 // i.e. using the lower (WORD_SIZE/2)-bit of the current WORD_SIZE-bit
733 // chunk.
734 rem <<= HALF_WORD_SIZE;
735 rem += val[pos] & HALF_MASK;
736 quotient.val[q_pos - 1] = (q_tmp << HALF_WORD_SIZE) + rem / x_word;
737 rem %= x_word;
738 }
739
740 // So far, what we have is:
741 // quotient = y / (x * 2^lower), and
742 // rem = (y % (x * 2^lower)) / 2^lower.
743 // If (lower > e), we will need to perform an extra adjustment of the
744 // quotient and remainder, namely:
745 // y / (x * 2^e) = [ y / (x * 2^lower) ] * 2^(lower - e) +
746 // + (rem * 2^(lower - e)) / x
747 // (y % (x * 2^e)) / 2^e = (rem * 2^(lower - e)) % x
748 size_t last_shift = lower - e;
749
750 if (last_shift > 0) {
751 // quotient * 2^(lower - e)
752 quotient <<= last_shift;
753 WordType q_tmp = 0;
754 WordType d = val[--pos];
755 if (last_shift >= HALF_WORD_SIZE) {
756 // The shifting (rem * 2^(lower - e)) might overflow WordTyoe, so we
757 // perform a HALF_WORD_SIZE-bit shift first.
758 rem <<= HALF_WORD_SIZE;
759 rem += d >> HALF_WORD_SIZE;
760 d &= HALF_MASK;
761 q_tmp = rem / x_word;
762 rem %= x_word;
763 last_shift -= HALF_WORD_SIZE;
764 } else {
765 // Only use the upper HALF_WORD_SIZE-bit of the current WORD_SIZE-bit
766 // chunk.
767 d >>= HALF_WORD_SIZE;
768 }
769
770 if (last_shift > 0) {
771 rem <<= HALF_WORD_SIZE;
772 rem += d;
773 q_tmp <<= last_shift;
774 x_word <<= HALF_WORD_SIZE - last_shift;
775 q_tmp += rem / x_word;
776 rem %= x_word;
777 }
778
779 quotient.val[0] += q_tmp;
780
781 if (lower - e <= HALF_WORD_SIZE) {
782 // The remainder rem * 2^(lower - e) might overflow to the higher
783 // WORD_SIZE-bit chunk.
784 if (pos < WORD_COUNT - 1) {
785 remainder[pos + 1] = rem >> HALF_WORD_SIZE;
786 }
787 remainder[pos] = (rem << HALF_WORD_SIZE) + (val[pos] & HALF_MASK);
788 } else {
789 remainder[pos] = rem;
790 }
791
792 } else {
793 remainder[pos] = rem;
794 }
795
796 // Set the remaining lower bits of the remainder.
797 for (; pos > 0; --pos) {
798 remainder[pos - 1] = val[pos - 1];
799 }
800
801 *this = quotient;
802 return remainder;
803 }
804
805 LIBC_INLINE constexpr BigInt operator/(const BigInt &other) const {
806 BigInt result(*this);
807 result.div(divider: other);
808 return result;
809 }
810
811 LIBC_INLINE constexpr BigInt &operator/=(const BigInt &other) {
812 div(divider: other);
813 return *this;
814 }
815
816 LIBC_INLINE constexpr BigInt operator%(const BigInt &other) const {
817 BigInt result(*this);
818 return *result.div(divider: other);
819 }
820
821 LIBC_INLINE constexpr BigInt operator%=(const BigInt &other) {
822 *this = *this % other;
823 return *this;
824 }
825
826 LIBC_INLINE constexpr BigInt &operator*=(const BigInt &other) {
827 *this = *this * other;
828 return *this;
829 }
830
831 LIBC_INLINE constexpr BigInt &operator<<=(size_t s) {
832 val = multiword::shift<multiword::LEFT, SIGNED>(val, s);
833 return *this;
834 }
835
836 LIBC_INLINE constexpr BigInt operator<<(size_t s) const {
837 return BigInt(multiword::shift<multiword::LEFT, SIGNED>(val, s));
838 }
839
840 LIBC_INLINE constexpr BigInt &operator>>=(size_t s) {
841 val = multiword::shift<multiword::RIGHT, SIGNED>(val, s);
842 return *this;
843 }
844
845 LIBC_INLINE constexpr BigInt operator>>(size_t s) const {
846 return BigInt(multiword::shift<multiword::RIGHT, SIGNED>(val, s));
847 }
848
849#define DEFINE_BINOP(OP) \
850 LIBC_INLINE friend constexpr BigInt operator OP(const BigInt &lhs, \
851 const BigInt &rhs) { \
852 BigInt result; \
853 for (size_t i = 0; i < WORD_COUNT; ++i) \
854 result[i] = lhs[i] OP rhs[i]; \
855 return result; \
856 } \
857 LIBC_INLINE friend constexpr BigInt operator OP##=(BigInt &lhs, \
858 const BigInt &rhs) { \
859 for (size_t i = 0; i < WORD_COUNT; ++i) \
860 lhs[i] OP## = rhs[i]; \
861 return lhs; \
862 }
863
864 DEFINE_BINOP(&) // & and &=
865 DEFINE_BINOP(|) // | and |=
866 DEFINE_BINOP(^) // ^ and ^=
867#undef DEFINE_BINOP
868
869 LIBC_INLINE constexpr BigInt operator~() const {
870 BigInt result;
871 for (size_t i = 0; i < WORD_COUNT; ++i)
872 result[i] = static_cast<WordType>(~val[i]);
873 return result;
874 }
875
876 LIBC_INLINE constexpr BigInt operator-() const {
877 BigInt result(*this);
878 result.negate();
879 return result;
880 }
881
882 LIBC_INLINE friend constexpr bool operator==(const BigInt &lhs,
883 const BigInt &rhs) {
884 for (size_t i = 0; i < WORD_COUNT; ++i)
885 if (lhs.val[i] != rhs.val[i])
886 return false;
887 return true;
888 }
889
890 LIBC_INLINE friend constexpr bool operator!=(const BigInt &lhs,
891 const BigInt &rhs) {
892 return !(lhs == rhs);
893 }
894
895 LIBC_INLINE friend constexpr bool operator>(const BigInt &lhs,
896 const BigInt &rhs) {
897 return cmp(lhs, rhs) > 0;
898 }
899 LIBC_INLINE friend constexpr bool operator>=(const BigInt &lhs,
900 const BigInt &rhs) {
901 return cmp(lhs, rhs) >= 0;
902 }
903 LIBC_INLINE friend constexpr bool operator<(const BigInt &lhs,
904 const BigInt &rhs) {
905 return cmp(lhs, rhs) < 0;
906 }
907 LIBC_INLINE friend constexpr bool operator<=(const BigInt &lhs,
908 const BigInt &rhs) {
909 return cmp(lhs, rhs) <= 0;
910 }
911
912 LIBC_INLINE constexpr BigInt &operator++() {
913 increment();
914 return *this;
915 }
916
917 LIBC_INLINE constexpr BigInt operator++(int) {
918 BigInt oldval(*this);
919 increment();
920 return oldval;
921 }
922
923 LIBC_INLINE constexpr BigInt &operator--() {
924 decrement();
925 return *this;
926 }
927
928 LIBC_INLINE constexpr BigInt operator--(int) {
929 BigInt oldval(*this);
930 decrement();
931 return oldval;
932 }
933
934 // Return the i-th word of the number.
935 LIBC_INLINE constexpr const WordType &operator[](size_t i) const {
936 return val[i];
937 }
938
939 // Return the i-th word of the number.
940 LIBC_INLINE constexpr WordType &operator[](size_t i) { return val[i]; }
941
942 // Return the i-th bit of the number.
943 LIBC_INLINE constexpr bool get_bit(size_t i) const {
944 const size_t word_index = i / WORD_SIZE;
945 return 1 & (val[word_index] >> (i % WORD_SIZE));
946 }
947
948 // Set the i-th bit of the number.
949 LIBC_INLINE constexpr void set_bit(size_t i) {
950 const size_t word_index = i / WORD_SIZE;
951 val[word_index] |= WordType(1) << (i % WORD_SIZE);
952 }
953
954private:
955 LIBC_INLINE friend constexpr int cmp(const BigInt &lhs, const BigInt &rhs) {
956 constexpr auto compare = [](WordType a, WordType b) {
957 return a == b ? 0 : a > b ? 1 : -1;
958 };
959 if constexpr (Signed) {
960 const bool lhs_is_neg = lhs.is_neg();
961 const bool rhs_is_neg = rhs.is_neg();
962 if (lhs_is_neg != rhs_is_neg)
963 return rhs_is_neg ? 1 : -1;
964 }
965 for (size_t i = WORD_COUNT; i-- > 0;)
966 if (auto cmp = compare(lhs[i], rhs[i]); cmp != 0)
967 return cmp;
968 return 0;
969 }
970
971 LIBC_INLINE constexpr void bitwise_not() {
972 for (auto &part : val)
973 part = static_cast<WordType>(~part);
974 }
975
976 LIBC_INLINE constexpr void negate() {
977 bitwise_not();
978 increment();
979 }
980
981 LIBC_INLINE constexpr void increment() {
982 multiword::add_with_carry(val, cpp::array<WordType, 1>{1});
983 }
984
985 LIBC_INLINE constexpr void decrement() {
986 multiword::sub_with_borrow(val, cpp::array<WordType, 1>{1});
987 }
988
989 LIBC_INLINE constexpr void extend(size_t index, bool is_neg) {
990 const WordType value = is_neg ? cpp::numeric_limits<WordType>::max()
991 : cpp::numeric_limits<WordType>::min();
992 for (size_t i = index; i < WORD_COUNT; ++i)
993 val[i] = value;
994 }
995
996 LIBC_INLINE constexpr bool get_msb() const {
997 return val.back() >> (WORD_SIZE - 1);
998 }
999
1000 LIBC_INLINE constexpr void set_msb() {
1001 val.back() |= mask_leading_ones<WordType, 1>();
1002 }
1003
1004 LIBC_INLINE constexpr void clear_msb() {
1005 val.back() &= mask_trailing_ones<WordType, WORD_SIZE - 1>();
1006 }
1007 LIBC_INLINE constexpr static Division divide_unsigned(const BigInt &dividend,
1008 const BigInt &divider) {
1009 BigInt remainder = dividend;
1010 BigInt quotient;
1011 if (remainder >= divider) {
1012 BigInt subtractor = divider;
1013 int cur_bit = multiword::countl_zero(subtractor.val) -
1014 multiword::countl_zero(remainder.val);
1015 subtractor <<= static_cast<size_t>(cur_bit);
1016 for (; cur_bit >= 0 && remainder > 0; --cur_bit, subtractor >>= 1) {
1017 if (remainder < subtractor)
1018 continue;
1019 remainder -= subtractor;
1020 quotient.set_bit(static_cast<size_t>(cur_bit));
1021 }
1022 }
1023 return Division{quotient, remainder};
1024 }
1025
1026 LIBC_INLINE constexpr static Division divide_signed(const BigInt &dividend,
1027 const BigInt &divider) {
1028 // Special case because it is not possible to negate the min value of a
1029 // signed integer.
1030 if (dividend == min() && divider == min())
1031 return Division{one(), zero()};
1032 // 1. Convert the dividend and divisor to unsigned representation.
1033 unsigned_type udividend(dividend);
1034 unsigned_type udivider(divider);
1035 // 2. Negate the dividend if it's negative, and similarly for the divisor.
1036 const bool dividend_is_neg = dividend.is_neg();
1037 const bool divider_is_neg = divider.is_neg();
1038 if (dividend_is_neg)
1039 udividend.negate();
1040 if (divider_is_neg)
1041 udivider.negate();
1042 // 3. Use unsigned multiword division algorithm.
1043 const auto unsigned_result = divide_unsigned(dividend: udividend, divider: udivider);
1044 // 4. Convert the quotient and remainder to signed representation.
1045 Division result;
1046 result.quotient = signed_type(unsigned_result.quotient);
1047 result.remainder = signed_type(unsigned_result.remainder);
1048 // 5. Negate the quotient if the dividend and divisor had opposite signs.
1049 if (dividend_is_neg != divider_is_neg)
1050 result.quotient.negate();
1051 // 6. Negate the remainder if the dividend was negative.
1052 if (dividend_is_neg)
1053 result.remainder.negate();
1054 return result;
1055 }
1056
1057 friend signed_type;
1058 friend unsigned_type;
1059};
1060
1061namespace internal {
1062// We default BigInt's WordType to 'uint64_t' or 'uint32_t' depending on type
1063// availability.
1064template <size_t Bits>
1065struct WordTypeSelector : cpp::type_identity<
1066#ifdef LIBC_TYPES_HAS_INT64
1067 uint64_t
1068#else
1069 uint32_t
1070#endif // LIBC_TYPES_HAS_INT64
1071 > {
1072};
1073// Except if we request 16 or 32 bits explicitly.
1074template <> struct WordTypeSelector<16> : cpp::type_identity<uint16_t> {};
1075template <> struct WordTypeSelector<32> : cpp::type_identity<uint32_t> {};
1076template <> struct WordTypeSelector<96> : cpp::type_identity<uint32_t> {};
1077
1078template <size_t Bits>
1079using WordTypeSelectorT = typename WordTypeSelector<Bits>::type;
1080} // namespace internal
1081
1082template <size_t Bits>
1083using UInt = BigInt<Bits, false, internal::WordTypeSelectorT<Bits>>;
1084
1085template <size_t Bits>
1086using Int = BigInt<Bits, true, internal::WordTypeSelectorT<Bits>>;
1087
1088// Provides limits of BigInt.
1089template <size_t Bits, bool Signed, typename T>
1090struct cpp::numeric_limits<BigInt<Bits, Signed, T>> {
1091 LIBC_INLINE static constexpr BigInt<Bits, Signed, T> max() {
1092 return BigInt<Bits, Signed, T>::max();
1093 }
1094 LIBC_INLINE static constexpr BigInt<Bits, Signed, T> min() {
1095 return BigInt<Bits, Signed, T>::min();
1096 }
1097 // Meant to match std::numeric_limits interface.
1098 // NOLINTNEXTLINE(readability-identifier-naming)
1099 LIBC_INLINE_VAR static constexpr int digits = Bits - Signed;
1100};
1101
1102// type traits to determine whether a T is a BigInt.
1103template <typename T> struct is_big_int : cpp::false_type {};
1104
1105template <size_t Bits, bool Signed, typename T>
1106struct is_big_int<BigInt<Bits, Signed, T>> : cpp::true_type {};
1107
1108template <class T>
1109LIBC_INLINE_VAR constexpr bool is_big_int_v = is_big_int<T>::value;
1110
1111// extensions of type traits to include BigInt
1112
1113// is_integral_or_big_int
1114template <typename T>
1115struct is_integral_or_big_int
1116 : cpp::bool_constant<(cpp::is_integral_v<T> || is_big_int_v<T>)> {};
1117
1118template <typename T>
1119LIBC_INLINE_VAR constexpr bool is_integral_or_big_int_v =
1120 is_integral_or_big_int<T>::value;
1121
1122// make_big_int_unsigned
1123template <typename T> struct make_big_int_unsigned;
1124
1125template <size_t Bits, bool Signed, typename T>
1126struct make_big_int_unsigned<BigInt<Bits, Signed, T>>
1127 : cpp::type_identity<BigInt<Bits, false, T>> {};
1128
1129template <typename T>
1130using make_big_int_unsigned_t = typename make_big_int_unsigned<T>::type;
1131
1132// make_big_int_signed
1133template <typename T> struct make_big_int_signed;
1134
1135template <size_t Bits, bool Signed, typename T>
1136struct make_big_int_signed<BigInt<Bits, Signed, T>>
1137 : cpp::type_identity<BigInt<Bits, true, T>> {};
1138
1139template <typename T>
1140using make_big_int_signed_t = typename make_big_int_signed<T>::type;
1141
1142// make_integral_or_big_int_unsigned
1143template <typename T, class = void> struct make_integral_or_big_int_unsigned;
1144
1145template <typename T>
1146struct make_integral_or_big_int_unsigned<
1147 T, cpp::enable_if_t<cpp::is_integral_v<T>>> : cpp::make_unsigned<T> {};
1148
1149template <typename T>
1150struct make_integral_or_big_int_unsigned<T, cpp::enable_if_t<is_big_int_v<T>>>
1151 : make_big_int_unsigned<T> {};
1152
1153template <typename T>
1154using make_integral_or_big_int_unsigned_t =
1155 typename make_integral_or_big_int_unsigned<T>::type;
1156
1157// make_integral_or_big_int_signed
1158template <typename T, class = void> struct make_integral_or_big_int_signed;
1159
1160template <typename T>
1161struct make_integral_or_big_int_signed<T,
1162 cpp::enable_if_t<cpp::is_integral_v<T>>>
1163 : cpp::make_signed<T> {};
1164
1165template <typename T>
1166struct make_integral_or_big_int_signed<T, cpp::enable_if_t<is_big_int_v<T>>>
1167 : make_big_int_signed<T> {};
1168
1169template <typename T>
1170using make_integral_or_big_int_signed_t =
1171 typename make_integral_or_big_int_signed<T>::type;
1172
1173// is_unsigned_integral_or_big_int
1174template <typename T>
1175struct is_unsigned_integral_or_big_int
1176 : cpp::bool_constant<
1177 cpp::is_same_v<T, make_integral_or_big_int_unsigned_t<T>>> {};
1178
1179template <typename T>
1180// Meant to look like <type_traits> helper variable templates.
1181// NOLINTNEXTLINE(readability-identifier-naming)
1182LIBC_INLINE_VAR constexpr bool is_unsigned_integral_or_big_int_v =
1183 is_unsigned_integral_or_big_int<T>::value;
1184
1185namespace cpp {
1186
1187// Specialization of cpp::bit_cast ('bit.h') from T to BigInt.
1188template <typename To, typename From>
1189LIBC_INLINE LIBC_BIT_CAST_CONSTEXPR cpp::enable_if_t<
1190 (sizeof(To) == sizeof(From)) && cpp::is_trivially_copyable<To>::value &&
1191 cpp::is_trivially_copyable<From>::value && is_big_int<To>::value,
1192 To>
1193bit_cast(const From &from) {
1194 To out;
1195 using Storage = decltype(out.val);
1196 out.val = cpp::bit_cast<Storage>(from);
1197 return out;
1198}
1199
1200// Specialization of cpp::bit_cast ('bit.h') from BigInt to T.
1201template <typename To, size_t Bits>
1202LIBC_INLINE LIBC_BIT_CAST_CONSTEXPR
1203 cpp::enable_if_t<sizeof(To) == sizeof(UInt<Bits>) &&
1204 cpp::is_trivially_constructible<To>::value &&
1205 cpp::is_trivially_copyable<To>::value &&
1206 cpp::is_trivially_copyable<UInt<Bits>>::value,
1207 To>
1208 bit_cast(const UInt<Bits> &from) {
1209 return cpp::bit_cast<To>(from.val);
1210}
1211
1212// Specialization of cpp::popcount ('bit.h') for BigInt.
1213template <typename T>
1214[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1215popcount(T value) {
1216 int bits = 0;
1217 for (auto word : value.val)
1218 if (word)
1219 bits += popcount(word);
1220 return bits;
1221}
1222
1223// Specialization of cpp::has_single_bit ('bit.h') for BigInt.
1224template <typename T>
1225[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, bool>
1226has_single_bit(T value) {
1227 int bits = 0;
1228 for (auto word : value.val) {
1229 if (word == 0)
1230 continue;
1231 bits += popcount(word);
1232 if (bits > 1)
1233 return false;
1234 }
1235 return bits == 1;
1236}
1237
1238// Specialization of cpp::countr_zero ('bit.h') for BigInt.
1239template <typename T>
1240[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1241countr_zero(const T &value) {
1242 return multiword::countr_zero(value.val);
1243}
1244
1245// Specialization of cpp::countl_zero ('bit.h') for BigInt.
1246template <typename T>
1247[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1248countl_zero(const T &value) {
1249 return multiword::countl_zero(value.val);
1250}
1251
1252// Specialization of cpp::countl_one ('bit.h') for BigInt.
1253template <typename T>
1254[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1255countl_one(T value) {
1256 return multiword::countl_one(value.val);
1257}
1258
1259// Specialization of cpp::countr_one ('bit.h') for BigInt.
1260template <typename T>
1261[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1262countr_one(T value) {
1263 return multiword::countr_one(value.val);
1264}
1265
1266// Specialization of cpp::bit_width ('bit.h') for BigInt.
1267template <typename T>
1268[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1269bit_width(T value) {
1270 return cpp::numeric_limits<T>::digits - cpp::countl_zero(value);
1271}
1272
1273// Forward-declare rotr so that rotl can use it.
1274template <typename T>
1275[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
1276rotr(T value, int rotate);
1277
1278// Specialization of cpp::rotl ('bit.h') for BigInt.
1279template <typename T>
1280[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
1281rotl(T value, int rotate) {
1282 constexpr int N = cpp::numeric_limits<T>::digits;
1283 rotate = rotate % N;
1284 if (!rotate)
1285 return value;
1286 if (rotate < 0)
1287 return cpp::rotr<T>(value, -rotate);
1288 return (value << static_cast<size_t>(rotate)) |
1289 (value >> (N - static_cast<size_t>(rotate)));
1290}
1291
1292// Specialization of cpp::rotr ('bit.h') for BigInt.
1293template <typename T>
1294[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
1295rotr(T value, int rotate) {
1296 constexpr int N = cpp::numeric_limits<T>::digits;
1297 rotate = rotate % N;
1298 if (!rotate)
1299 return value;
1300 if (rotate < 0)
1301 return cpp::rotl<T>(value, -rotate);
1302 return (value >> static_cast<size_t>(rotate)) |
1303 (value << (N - static_cast<size_t>(rotate)));
1304}
1305
1306} // namespace cpp
1307
1308// Specialization of mask_trailing_ones ('math_extras.h') for BigInt.
1309template <typename T, size_t count>
1310LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
1311mask_trailing_ones() {
1312 static_assert(!T::SIGNED && count <= T::BITS);
1313 if (count == T::BITS)
1314 return T::all_ones();
1315 constexpr size_t QUOTIENT = count / T::WORD_SIZE;
1316 constexpr size_t REMAINDER = count % T::WORD_SIZE;
1317 T out; // zero initialized
1318 for (size_t i = 0; i <= QUOTIENT; ++i)
1319 out[i] = i < QUOTIENT
1320 ? cpp::numeric_limits<typename T::word_type>::max()
1321 : mask_trailing_ones<typename T::word_type, REMAINDER>();
1322 return out;
1323}
1324
1325// Specialization of mask_leading_ones ('math_extras.h') for BigInt.
1326template <typename T, size_t count>
1327LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> mask_leading_ones() {
1328 static_assert(!T::SIGNED && count <= T::BITS);
1329 if (count == T::BITS)
1330 return T::all_ones();
1331 constexpr size_t QUOTIENT = (T::BITS - count - 1U) / T::WORD_SIZE;
1332 constexpr size_t REMAINDER = count % T::WORD_SIZE;
1333 T out; // zero initialized
1334 for (size_t i = QUOTIENT; i < T::WORD_COUNT; ++i)
1335 out[i] = i > QUOTIENT
1336 ? cpp::numeric_limits<typename T::word_type>::max()
1337 : mask_leading_ones<typename T::word_type, REMAINDER>();
1338 return out;
1339}
1340
1341// Specialization of mask_trailing_zeros ('math_extras.h') for BigInt.
1342template <typename T, size_t count>
1343LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
1344mask_trailing_zeros() {
1345 return mask_leading_ones<T, T::BITS - count>();
1346}
1347
1348// Specialization of mask_leading_zeros ('math_extras.h') for BigInt.
1349template <typename T, size_t count>
1350LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
1351mask_leading_zeros() {
1352 return mask_trailing_ones<T, T::BITS - count>();
1353}
1354
1355// Specialization of count_zeros ('math_extras.h') for BigInt.
1356template <typename T>
1357[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1358count_zeros(T value) {
1359 return cpp::popcount(~value);
1360}
1361
1362// Specialization of first_leading_zero ('math_extras.h') for BigInt.
1363template <typename T>
1364[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1365first_leading_zero(T value) {
1366 return value == cpp::numeric_limits<T>::max() ? 0
1367 : cpp::countl_one(value) + 1;
1368}
1369
1370// Specialization of first_leading_one ('math_extras.h') for BigInt.
1371template <typename T>
1372[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1373first_leading_one(T value) {
1374 return first_leading_zero(~value);
1375}
1376
1377// Specialization of first_trailing_zero ('math_extras.h') for BigInt.
1378template <typename T>
1379[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1380first_trailing_zero(T value) {
1381 return value == cpp::numeric_limits<T>::max() ? 0
1382 : cpp::countr_zero(~value) + 1;
1383}
1384
1385// Specialization of first_trailing_one ('math_extras.h') for BigInt.
1386template <typename T>
1387[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
1388first_trailing_one(T value) {
1389 return value == 0 ? 0 : cpp::countr_zero(value) + 1;
1390}
1391
1392} // namespace LIBC_NAMESPACE_DECL
1393
1394#endif // LLVM_LIBC_SRC___SUPPORT_BIG_INT_H
1395