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