Branch data Line data Source code
1 : : // Copyright 2019-2026 David Robillard <d@drobilla.net>
2 : : // SPDX-License-Identifier: ISC
3 : :
4 : : #include "bigint.h"
5 : : #include "macros.h"
6 : :
7 : : #include "int_math.h"
8 : :
9 : : #include <assert.h>
10 : : #include <stdbool.h>
11 : : #include <stdlib.h>
12 : :
13 : : typedef uint64_t Hugit;
14 : :
15 : : static const uint32_t bigit_mask = ~0U;
16 : : static const uint64_t carry_mask = (uint64_t)~0U << 32U;
17 : :
18 : : typedef struct {
19 : : unsigned bigits;
20 : : unsigned bits;
21 : : } Offset;
22 : :
23 : : static inline Offset
24 : 1411051 : make_offset(const unsigned i)
25 : : {
26 : 1411051 : const unsigned bigits = i / BIGINT_BIGIT_BITS;
27 : 1411051 : const unsigned bits = i % BIGINT_BIGIT_BITS;
28 : :
29 : 1411051 : const Offset offset = {bigits, bits};
30 : 1411051 : return offset;
31 : : }
32 : :
33 : : #ifndef NDEBUG
34 : : static inline bool
35 : 6056574 : exess_bigint_is_clamped(const ExessBigint* num)
36 : : {
37 [ + + + - ]: 6056574 : return num->n_bigits == 0 || num->bigits[num->n_bigits - 1];
38 : : }
39 : : #endif
40 : :
41 : : EXESS_I_NONBLOCKING void
42 : 973270 : exess_bigint_shift_left(ExessBigint* num, const unsigned amount)
43 : : {
44 [ - + ]: 973270 : assert(exess_bigint_is_clamped(num));
45 [ + + - + ]: 973270 : if (amount == 0 || num->n_bigits == 0) {
46 : 428652 : return;
47 : : }
48 : :
49 : 544618 : const Offset offset = make_offset(amount);
50 : :
51 [ - + ]: 544618 : assert(num->n_bigits + offset.bigits < BIGINT_MAX_BIGITS);
52 : 544618 : num->n_bigits += offset.bigits + (bool)offset.bits;
53 : :
54 [ + + ]: 544618 : if (offset.bits == 0) { // Simple bigit-aligned shift
55 [ + + ]: 7799 : for (unsigned i = num->n_bigits - 1; i >= offset.bigits; --i) {
56 : 5966 : num->bigits[i] = num->bigits[i - offset.bigits];
57 : : }
58 : : } else { // Bigit + sub-bigit bit offset shift
59 : 542785 : const unsigned right_shift = BIGINT_BIGIT_BITS - offset.bits;
60 [ + + ]: 4746055 : for (unsigned i = num->n_bigits - offset.bigits - 1; i > 0; --i) {
61 : 4203270 : num->bigits[i + offset.bigits] =
62 : 4203270 : (num->bigits[i] << offset.bits) | (num->bigits[i - 1] >> right_shift);
63 : : }
64 : :
65 : 542785 : num->bigits[offset.bigits] = num->bigits[0] << offset.bits;
66 : : }
67 : :
68 : : // Zero LSBs
69 [ + + ]: 842588 : for (unsigned i = 0; i < offset.bigits; ++i) {
70 : 297970 : num->bigits[i] = 0;
71 : : }
72 : :
73 : 544618 : exess_bigint_clamp(num);
74 [ - + ]: 544618 : assert(exess_bigint_is_clamped(num));
75 : : }
76 : :
77 : : EXESS_I_NONBLOCKING void
78 : 78183 : exess_bigint_zero(ExessBigint* num)
79 : : {
80 : 78183 : EXESS_I_CONSTEXPR ExessBigint zero = {{0}, 0};
81 : :
82 : 78183 : *num = zero;
83 : 78183 : }
84 : :
85 : : EXESS_I_NONBLOCKING void
86 : 13905 : exess_bigint_set(ExessBigint* num, const ExessBigint* value)
87 : : {
88 : 13905 : *num = *value;
89 : 13905 : }
90 : :
91 : : EXESS_I_NONBLOCKING void
92 : 61363 : exess_bigint_set_u32(ExessBigint* num, const uint32_t value)
93 : : {
94 : 61363 : exess_bigint_zero(num);
95 : :
96 : 61363 : num->bigits[0] = value;
97 : 61363 : num->n_bigits = (bool)value;
98 : 61363 : }
99 : :
100 : : EXESS_I_NONBLOCKING void
101 : 1692251 : exess_bigint_clamp(ExessBigint* num)
102 : : {
103 [ + + + + ]: 2242668 : while (num->n_bigits > 0 && num->bigits[num->n_bigits - 1] == 0) {
104 : 550417 : --num->n_bigits;
105 : : }
106 : 1692251 : }
107 : :
108 : : EXESS_I_NONBLOCKING void
109 : 16791 : exess_bigint_set_u64(ExessBigint* num, const uint64_t value)
110 : : {
111 : 16791 : exess_bigint_zero(num);
112 : :
113 : 16791 : num->bigits[0] = (Bigit)(value & bigit_mask);
114 : 16791 : num->bigits[1] = (Bigit)(value >> BIGINT_BIGIT_BITS);
115 [ - + - - ]: 16791 : num->n_bigits = num->bigits[1] ? 2U : num->bigits[0] ? 1U : 0U;
116 : 16791 : }
117 : :
118 : : EXESS_I_NONBLOCKING void
119 : 30667 : exess_bigint_set_pow10(ExessBigint* num, const unsigned exponent)
120 : : {
121 : 30667 : exess_bigint_set_u32(num, 1);
122 : 30667 : exess_bigint_multiply_pow10(num, exponent);
123 : 30667 : }
124 : :
125 : : static EXESS_I_NONBLOCKING uint32_t
126 : 81 : read_u32(const char* const str, uint32_t* result, uint32_t* n_digits)
127 : : {
128 : 81 : EXESS_I_CONSTEXPR size_t uint32_digits10 = 9;
129 : :
130 : 81 : *result = *n_digits = 0;
131 : :
132 : 81 : uint32_t i = 0;
133 [ + + + - : 494 : for (; str[i] >= '0' && str[i] <= '9' && *n_digits < uint32_digits10; ++i) {
+ + ]
134 : 413 : *result = (*result * 10U) + (unsigned)(str[i] - '0');
135 : 413 : *n_digits += 1;
136 : : }
137 : :
138 : 81 : return i;
139 : : }
140 : :
141 : : EXESS_I_NONBLOCKING void
142 : 29 : exess_bigint_set_decimal_string(ExessBigint* num, const char* const str)
143 : : {
144 : 29 : exess_bigint_zero(num);
145 : :
146 : 29 : uint32_t pos = 0;
147 : 29 : uint32_t n_digits = 0;
148 : 29 : uint32_t n_read = 0;
149 : 29 : uint32_t word = 0;
150 [ + + ]: 81 : while ((n_read = read_u32(str + pos, &word, &n_digits))) {
151 : 52 : exess_bigint_multiply_u32(num, (uint32_t)POW10[n_digits]);
152 : 52 : exess_bigint_add_u32(num, word);
153 : 52 : pos += n_read;
154 : : }
155 : :
156 : 29 : exess_bigint_clamp(num);
157 : 29 : }
158 : :
159 : : EXESS_I_NONBLOCKING void
160 : 880834 : exess_bigint_multiply_u32(ExessBigint* num, const uint32_t factor)
161 : : {
162 [ - + + ]: 880834 : switch (factor) {
163 : 0 : case 0:
164 : 0 : exess_bigint_zero(num);
165 : 0 : return;
166 : 2855 : case 1:
167 : 2855 : return;
168 : 877979 : default:
169 : 877979 : break;
170 : : }
171 : :
172 : 877979 : Hugit carry = 0;
173 [ + + ]: 7998254 : for (unsigned i = 0; i < num->n_bigits; ++i) {
174 : 7120275 : const Hugit p = (Hugit)factor * num->bigits[i];
175 : 7120275 : const Hugit hugit = p + (carry & bigit_mask);
176 : :
177 : 7120275 : num->bigits[i] = (Bigit)(hugit & bigit_mask);
178 : :
179 : 7120275 : carry = (hugit >> 32U) + (carry >> 32U);
180 : : }
181 : :
182 [ + + ]: 993981 : for (; carry; carry >>= 32U) {
183 [ - + ]: 116002 : assert(num->n_bigits + 1 <= BIGINT_MAX_BIGITS);
184 : 116002 : num->bigits[num->n_bigits++] = (Bigit)carry;
185 : : }
186 : : }
187 : :
188 : : EXESS_I_NONBLOCKING void
189 : 68054 : exess_bigint_multiply_u64(ExessBigint* num, const uint64_t factor)
190 : : {
191 [ - + + ]: 68054 : switch (factor) {
192 : 0 : case 0:
193 : 0 : exess_bigint_zero(num);
194 : 0 : return;
195 : 2 : case 1:
196 : 2 : return;
197 : 68052 : default:
198 : 68052 : break;
199 : : }
200 : :
201 : 68052 : const Hugit f_lo = factor & bigit_mask;
202 : 68052 : const Hugit f_hi = factor >> 32U;
203 : :
204 : 68052 : Hugit carry = 0;
205 [ + + ]: 354394 : for (unsigned i = 0; i < num->n_bigits; ++i) {
206 : 286342 : const Hugit p_lo = f_lo * num->bigits[i];
207 : 286342 : const Hugit p_hi = f_hi * num->bigits[i];
208 : 286342 : const Hugit hugit = p_lo + (carry & bigit_mask);
209 : :
210 : 286342 : num->bigits[i] = (Bigit)(hugit & bigit_mask);
211 : 286342 : carry = p_hi + (hugit >> 32U) + (carry >> 32U);
212 : : }
213 : :
214 [ + + ]: 180177 : for (; carry; carry >>= 32U) {
215 [ - + ]: 112125 : assert(num->n_bigits + 1 <= BIGINT_MAX_BIGITS);
216 : 112125 : num->bigits[num->n_bigits++] = (Bigit)(carry & bigit_mask);
217 : : }
218 : : }
219 : :
220 : : EXESS_I_NONBLOCKING void
221 : 30696 : exess_bigint_multiply_pow10(ExessBigint* num, const unsigned exponent)
222 : : {
223 : : /* To reduce multiplication, we exploit 10^e = (2*5)^e = 2^e * 5^e to
224 : : factor out an exponentiation by 5 instead of 10. So, we first multiply
225 : : by 5^e (hard), then by 2^e (just a single left shift). */
226 : :
227 : : // 5^27, the largest power of 5 that fits in 64 bits
228 : 30696 : EXESS_I_CONSTEXPR uint64_t pow5_27 = 7450580596923828125ULL;
229 : :
230 : : // Powers of 5 up to 5^13, the largest that fits in 32 bits
231 : 30696 : EXESS_I_CONSTEXPR uint32_t pow5[] = {
232 : : 1,
233 : : 5,
234 : : 5 * 5,
235 : : 5 * 5 * 5,
236 : : 5 * 5 * 5 * 5,
237 : : 5 * 5 * 5 * 5 * 5,
238 : : 5 * 5 * 5 * 5 * 5 * 5,
239 : : 5 * 5 * 5 * 5 * 5 * 5 * 5,
240 : : 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
241 : : 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
242 : : 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
243 : : 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
244 : : 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
245 : : 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
246 : : };
247 : :
248 [ + + - + ]: 30696 : if (exponent == 0 || num->n_bigits == 0) {
249 : 400 : return;
250 : : }
251 : :
252 : : // Multiply by 5^27 until e < 27 so we can switch to 32 bits
253 : 30296 : unsigned e = exponent;
254 [ + + ]: 84445 : while (e >= 27) {
255 : 54149 : exess_bigint_multiply_u64(num, pow5_27);
256 : 54149 : e -= 27;
257 : : }
258 : :
259 : : // Multiply by 5^13 until e < 13 so we have only one multiplication left
260 [ + + ]: 45541 : while (e >= 13) {
261 : 15245 : exess_bigint_multiply_u32(num, pow5[13]);
262 : 15245 : e -= 13;
263 : : }
264 : :
265 : : // Multiply by the final 5^e (which may be zero, making this a noop)
266 : 30296 : exess_bigint_multiply_u32(num, pow5[e]);
267 : :
268 : : // Finally multiply by 2^e
269 : 30296 : exess_bigint_shift_left(num, exponent);
270 : : }
271 : :
272 : : EXESS_I_NONBLOCKING int
273 : 2834692 : exess_bigint_compare(const ExessBigint* lhs, const ExessBigint* rhs)
274 : : {
275 [ + + ]: 2834692 : if (lhs->n_bigits < rhs->n_bigits) {
276 : 3823 : return -1;
277 : : }
278 : :
279 [ + + ]: 2830869 : if (lhs->n_bigits > rhs->n_bigits) {
280 : 331836 : return 1;
281 : : }
282 : :
283 [ + + ]: 2545842 : for (int i = (int)lhs->n_bigits - 1; i >= 0; --i) {
284 : 2542838 : const Bigit bigit_l = lhs->bigits[i];
285 : 2542838 : const Bigit bigit_r = rhs->bigits[i];
286 [ + + ]: 2542838 : if (bigit_l < bigit_r) {
287 : 164708 : return -1;
288 : : }
289 : :
290 [ + + ]: 2378130 : if (bigit_l > bigit_r) {
291 : 2331321 : return 1;
292 : : }
293 : : }
294 : :
295 : 3004 : return 0;
296 : : }
297 : :
298 : : static int
299 : 445884 : exess_bigint_plus_compare_internal(const ExessBigint* const l,
300 : : const ExessBigint* const p,
301 : : const ExessBigint* const c)
302 : : {
303 [ + + ]: 445884 : if (l->n_bigits + 1 < c->n_bigits) {
304 : 44 : return -1;
305 : : }
306 : :
307 [ + + ]: 445840 : if (l->n_bigits > c->n_bigits) {
308 : 974 : return 1;
309 : : }
310 : :
311 [ + + + + ]: 444866 : if (p->n_bigits < l->n_bigits && l->n_bigits < c->n_bigits) {
312 : 11310 : return -1;
313 : : }
314 : :
315 : 433556 : Hugit borrow = 0;
316 [ + + ]: 455079 : for (int i = (int)c->n_bigits - 1; i >= 0; --i) {
317 : 455030 : const Bigit ai = l->bigits[i];
318 : 455030 : const Bigit bi = p->bigits[i];
319 : 455030 : const Bigit ci = c->bigits[i];
320 : 455030 : const Hugit sum = (Hugit)ai + bi;
321 : :
322 [ + + ]: 455030 : if (sum > ci + borrow) {
323 : 33534 : return 1;
324 : : }
325 : :
326 : 421496 : borrow += ci - sum;
327 [ + + ]: 421496 : if (borrow > 1) {
328 : 399973 : return -1;
329 : : }
330 : :
331 : 21523 : borrow <<= 32U;
332 : : }
333 : :
334 [ - + ]: 49 : return borrow ? -1 : 0;
335 : : }
336 : :
337 : : EXESS_I_NONBLOCKING int
338 : 445884 : exess_bigint_plus_compare(const ExessBigint* const l,
339 : : const ExessBigint* const p,
340 : : const ExessBigint* const c)
341 : : {
342 [ - + ]: 445884 : assert(exess_bigint_is_clamped(l));
343 [ - + ]: 445884 : assert(exess_bigint_is_clamped(p));
344 [ - + ]: 445884 : assert(exess_bigint_is_clamped(c));
345 : :
346 : 445884 : return (l->n_bigits < p->n_bigits)
347 : 2329 : ? exess_bigint_plus_compare_internal(p, l, c)
348 [ + + ]: 448213 : : exess_bigint_plus_compare_internal(l, p, c);
349 : : }
350 : :
351 : : static unsigned
352 : 30690 : exess_bigint_add_carry(ExessBigint* lhs, unsigned i, bool carry)
353 : : {
354 [ + + ]: 31151 : for (; carry; ++i) {
355 : 461 : const Hugit sum = (Hugit)carry + lhs->bigits[i];
356 : 461 : lhs->bigits[i] = (Bigit)(sum & bigit_mask);
357 : 461 : carry = (Bigit)((sum & carry_mask) >> 32U);
358 : : }
359 : :
360 : 30690 : return i;
361 : : }
362 : :
363 : : EXESS_I_NONBLOCKING void
364 : 52 : exess_bigint_add_u32(ExessBigint* lhs, const uint32_t rhs)
365 : : {
366 [ + + ]: 52 : if (lhs->n_bigits == 0) {
367 : 29 : exess_bigint_set_u32(lhs, rhs);
368 : 29 : return;
369 : : }
370 : :
371 : 23 : Hugit sum = (Hugit)lhs->bigits[0] + rhs;
372 : 23 : Bigit carry = (Bigit)(sum >> 32U);
373 : :
374 : 23 : lhs->bigits[0] = (Bigit)(sum & bigit_mask);
375 : :
376 : 23 : const unsigned i = exess_bigint_add_carry(lhs, 1U, carry);
377 : 23 : lhs->n_bigits = MAX(i, lhs->n_bigits);
378 [ - + ]: 23 : assert(exess_bigint_is_clamped(lhs));
379 : : }
380 : :
381 : : EXESS_I_NONBLOCKING void
382 : 30667 : exess_bigint_add(ExessBigint* lhs, const ExessBigint* rhs)
383 : : {
384 [ - + ]: 30667 : assert(MAX(lhs->n_bigits, rhs->n_bigits) + 1 <= BIGINT_MAX_BIGITS);
385 : :
386 : 30667 : bool carry = 0;
387 : 30667 : unsigned i = 0;
388 [ + + ]: 216015 : for (; i < rhs->n_bigits; ++i) {
389 : 185348 : const Hugit sum = (Hugit)lhs->bigits[i] + rhs->bigits[i] + carry;
390 : :
391 : 185348 : lhs->bigits[i] = (Bigit)(sum & bigit_mask);
392 : 185348 : carry = (sum & carry_mask) >> 32U;
393 : : }
394 : :
395 : 30667 : i = exess_bigint_add_carry(lhs, i, carry);
396 : 30667 : lhs->n_bigits = MAX(i, lhs->n_bigits);
397 [ - + ]: 30667 : assert(exess_bigint_is_clamped(lhs));
398 : 30667 : }
399 : :
400 : : static unsigned
401 : 1147604 : exess_bigint_subtract_borrow(ExessBigint* lhs, unsigned i, bool borrow)
402 : : {
403 [ + + ]: 1161691 : for (; borrow; ++i) {
404 : 14087 : const Bigit l = lhs->bigits[i];
405 : :
406 : 14087 : lhs->bigits[i] -= borrow;
407 : :
408 : 14087 : borrow = l == 0;
409 : : }
410 : :
411 : 1147604 : return i;
412 : : }
413 : :
414 : : EXESS_I_NONBLOCKING void
415 : 281171 : exess_bigint_subtract(ExessBigint* lhs, const ExessBigint* rhs)
416 : : {
417 [ - + ]: 281171 : assert(exess_bigint_is_clamped(lhs));
418 [ - + ]: 281171 : assert(exess_bigint_is_clamped(rhs));
419 [ - + ]: 281171 : assert(exess_bigint_compare(lhs, rhs) >= 0);
420 : :
421 : 281171 : bool borrow = 0;
422 : 281171 : unsigned i = 0;
423 [ + + ]: 2715189 : for (i = 0; i < rhs->n_bigits; ++i) {
424 : 2434018 : const Bigit l = lhs->bigits[i];
425 : 2434018 : const Bigit r = rhs->bigits[i];
426 : :
427 : 2434018 : lhs->bigits[i] = l - r - borrow;
428 [ + + + + : 2434018 : borrow = l < r || (l == r && borrow);
- + ]
429 : : }
430 : :
431 : 281171 : exess_bigint_subtract_borrow(lhs, i, borrow);
432 : 281171 : exess_bigint_clamp(lhs);
433 : 281171 : }
434 : :
435 : : static unsigned
436 : 1583027 : exess_bigint_leading_zeros(const ExessBigint* num)
437 : : {
438 [ - + ]: 1583027 : assert(num->n_bigits);
439 : 3166054 : return (32 * (BIGINT_MAX_BIGITS - num->n_bigits)) +
440 : 1583027 : exess_clz32(num->bigits[num->n_bigits - 1]);
441 : : }
442 : :
443 : : static Bigit
444 : 7859971 : exess_bigint_left_shifted_bigit_i(const ExessBigint* num,
445 : : const Offset amount,
446 : : const unsigned index)
447 : : {
448 [ + - + + ]: 7859971 : if (amount.bigits == 0 && amount.bits == 0) {
449 : 3684189 : return num->bigits[index];
450 : : }
451 : :
452 [ - + ]: 4175782 : if (index < amount.bigits) {
453 : 0 : return 0;
454 : : }
455 : :
456 [ - + ]: 4175782 : if (amount.bits == 0) { // Simple bigit-aligned shift
457 : 0 : return num->bigits[index - amount.bigits];
458 : : }
459 : :
460 [ + + ]: 4175782 : if (index == amount.bigits) { // Last non-zero bigit
461 : 437847 : return num->bigits[0] << amount.bits;
462 : : }
463 : :
464 : : // Bigit + sub-bigit bit offset shift
465 : 3737935 : const unsigned right_shift = BIGINT_BIGIT_BITS - amount.bits;
466 : 3737935 : return (num->bigits[index - amount.bigits] << amount.bits) |
467 : 3737935 : (num->bigits[index - amount.bigits - 1] >> right_shift);
468 : : }
469 : :
470 : : EXESS_I_NONBLOCKING Bigit
471 : 0 : exess_bigint_left_shifted_bigit(const ExessBigint* num,
472 : : const unsigned amount,
473 : : const unsigned index)
474 : : {
475 : 0 : return exess_bigint_left_shifted_bigit_i(num, make_offset(amount), index);
476 : : }
477 : :
478 : : EXESS_I_NONBLOCKING void
479 : 866433 : exess_bigint_subtract_left_shifted(ExessBigint* lhs,
480 : : const ExessBigint* rhs,
481 : : const unsigned amount)
482 : : {
483 [ - + ]: 866433 : assert(exess_bigint_is_clamped(lhs));
484 [ - + ]: 866433 : assert(exess_bigint_is_clamped(rhs));
485 : : #ifndef NDEBUG
486 : : {
487 : 866433 : ExessBigint check_rhs = *rhs;
488 : 866433 : exess_bigint_shift_left(&check_rhs, amount);
489 [ - + ]: 866433 : assert(exess_bigint_compare(lhs, &check_rhs) >= 0);
490 : : }
491 : : #endif
492 : :
493 : 866433 : const Offset offset = make_offset(amount);
494 : 866433 : const unsigned r_n_bigits = rhs->n_bigits + offset.bigits + (bool)offset.bits;
495 : :
496 : 866433 : bool borrow = 0;
497 : 866433 : unsigned i = 0;
498 [ + + ]: 8726404 : for (i = 0; i < r_n_bigits; ++i) {
499 : 7859971 : const Bigit l = lhs->bigits[i];
500 : 7859971 : const Bigit r = exess_bigint_left_shifted_bigit_i(rhs, offset, i);
501 : :
502 : 7859971 : lhs->bigits[i] = l - r - borrow;
503 [ + + + + : 7859971 : borrow = l < r || ((l == r) && borrow);
+ + ]
504 : : }
505 : :
506 : 866433 : exess_bigint_subtract_borrow(lhs, i, borrow);
507 : 866433 : exess_bigint_clamp(lhs);
508 : 866433 : }
509 : :
510 : : EXESS_I_NONBLOCKING uint32_t
511 : 437568 : exess_bigint_divmod(ExessBigint* lhs, const ExessBigint* rhs)
512 : : {
513 [ - + ]: 437568 : assert(exess_bigint_is_clamped(lhs));
514 [ - + ]: 437568 : assert(exess_bigint_is_clamped(rhs));
515 [ - + ]: 437568 : assert(rhs->n_bigits > 0);
516 [ + + ]: 437568 : if (lhs->n_bigits < rhs->n_bigits) {
517 : 2145 : return 0;
518 : : }
519 : :
520 : 435423 : uint32_t result = 0;
521 : 435423 : const Bigit r0 = rhs->bigits[rhs->n_bigits - 1];
522 : 435423 : const unsigned rlz = exess_bigint_leading_zeros(rhs);
523 : :
524 : : // Shift and subtract until the LHS does not have more bigits
525 [ + + ]: 487788 : while (lhs->n_bigits > rhs->n_bigits) {
526 : 52365 : const unsigned llz = exess_bigint_leading_zeros(lhs);
527 : 52365 : const unsigned shift = rlz - llz - 1;
528 : :
529 : 52365 : result += 1U << shift;
530 : 52365 : exess_bigint_subtract_left_shifted(lhs, rhs, shift);
531 : : }
532 : :
533 : : // Handle simple termination cases
534 : 435423 : int cmp = exess_bigint_compare(lhs, rhs);
535 [ + + ]: 435423 : if (cmp < 0) {
536 : 39460 : return result;
537 : : }
538 : :
539 [ + + - + ]: 395963 : if (cmp > 0 && lhs->n_bigits == 1) {
540 [ # # ]: 0 : assert(rhs->n_bigits == 1);
541 : 0 : const Bigit l0 = lhs->bigits[lhs->n_bigits - 1];
542 : :
543 : 0 : lhs->bigits[lhs->n_bigits - 1] = l0 % r0;
544 : 0 : lhs->n_bigits -= (lhs->bigits[lhs->n_bigits - 1] == 0);
545 : 0 : return result + (l0 / r0);
546 : : }
547 : :
548 : : // Both now have the same number of digits, finish with subtraction
549 [ + + ]: 1210031 : for (; cmp >= 0; cmp = exess_bigint_compare(lhs, rhs)) {
550 : 1095239 : const unsigned llz = exess_bigint_leading_zeros(lhs);
551 [ + + ]: 1095239 : if (rlz == llz) {
552 : : // Both have the same number of leading zeros, just subtract
553 : 281171 : exess_bigint_subtract(lhs, rhs);
554 : 281171 : return result + 1;
555 : : }
556 : :
557 : 814068 : const unsigned shift = rlz - llz - 1;
558 : 814068 : result += 1U << shift;
559 : 814068 : exess_bigint_subtract_left_shifted(lhs, rhs, shift);
560 : : }
561 : :
562 : 114792 : return result;
563 : : }
|
