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