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