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 : 1414992 : make_offset(const unsigned i)
25 : : {
26 : 1414992 : const unsigned bigits = i / BIGINT_BIGIT_BITS;
27 : 1414992 : const unsigned bits = i % BIGINT_BIGIT_BITS;
28 : :
29 : 1414992 : const Offset offset = {bigits, bits};
30 : 1414992 : return offset;
31 : : }
32 : :
33 : : #ifndef NDEBUG
34 : : static inline bool
35 : 6065009 : exess_bigint_is_clamped(const ExessBigint* num)
36 : : {
37 [ + + + - ]: 6065009 : return num->n_bigits == 0 || num->bigits[num->n_bigits - 1];
38 : : }
39 : : #endif
40 : :
41 : : EXESS_I_NONBLOCKING void
42 : 975372 : exess_bigint_shift_left(ExessBigint* num, const unsigned amount)
43 : : {
44 [ - + ]: 975372 : assert(exess_bigint_is_clamped(num));
45 [ + + - + ]: 975372 : if (amount == 0 || num->n_bigits == 0) {
46 : 428872 : return;
47 : : }
48 : :
49 : 546500 : const Offset offset = make_offset(amount);
50 : :
51 [ - + ]: 546500 : assert(num->n_bigits + offset.bigits < BIGINT_MAX_BIGITS);
52 : 546500 : num->n_bigits += offset.bigits + (bool)offset.bits;
53 : :
54 [ + + ]: 546500 : if (offset.bits == 0) { // Simple bigit-aligned shift
55 [ + + ]: 8086 : for (unsigned i = num->n_bigits - 1; i >= offset.bigits; --i) {
56 : 6131 : num->bigits[i] = num->bigits[i - offset.bigits];
57 : : }
58 : : } else { // Bigit + sub-bigit bit offset shift
59 : 544545 : const unsigned right_shift = BIGINT_BIGIT_BITS - offset.bits;
60 [ + + ]: 4767316 : for (unsigned i = num->n_bigits - offset.bigits - 1; i > 0; --i) {
61 : 4222771 : num->bigits[i + offset.bigits] =
62 : 4222771 : (num->bigits[i] << offset.bits) | (num->bigits[i - 1] >> right_shift);
63 : : }
64 : :
65 : 544545 : num->bigits[offset.bigits] = num->bigits[0] << offset.bits;
66 : : }
67 : :
68 : : // Zero LSBs
69 [ + + ]: 844628 : for (unsigned i = 0; i < offset.bigits; ++i) {
70 : 298128 : num->bigits[i] = 0;
71 : : }
72 : :
73 : 546500 : exess_bigint_clamp(num);
74 [ - + ]: 546500 : assert(exess_bigint_is_clamped(num));
75 : : }
76 : :
77 : : EXESS_I_NONBLOCKING void
78 : 78158 : exess_bigint_zero(ExessBigint* num)
79 : : {
80 : 78158 : EXESS_I_CONSTEXPR ExessBigint zero = {{0}, 0};
81 : :
82 : 78158 : *num = zero;
83 : 78158 : }
84 : :
85 : : EXESS_I_NONBLOCKING void
86 : 13939 : exess_bigint_set(ExessBigint* num, const ExessBigint* value)
87 : : {
88 : 13939 : *num = *value;
89 : 13939 : }
90 : :
91 : : EXESS_I_NONBLOCKING void
92 : 61368 : exess_bigint_set_u32(ExessBigint* num, const uint32_t value)
93 : : {
94 : 61368 : exess_bigint_zero(num);
95 : :
96 : 61368 : num->bigits[0] = value;
97 : 61368 : num->n_bigits = (bool)value;
98 : 61368 : }
99 : :
100 : : EXESS_I_NONBLOCKING void
101 : 1695799 : exess_bigint_clamp(ExessBigint* num)
102 : : {
103 [ + + + + ]: 2247961 : while (num->n_bigits > 0 && num->bigits[num->n_bigits - 1] == 0) {
104 : 552162 : --num->n_bigits;
105 : : }
106 : 1695799 : }
107 : :
108 : : EXESS_I_NONBLOCKING void
109 : 16760 : exess_bigint_set_u64(ExessBigint* num, const uint64_t value)
110 : : {
111 : 16760 : exess_bigint_zero(num);
112 : :
113 : 16760 : num->bigits[0] = (Bigit)(value & bigit_mask);
114 : 16760 : num->bigits[1] = (Bigit)(value >> BIGINT_BIGIT_BITS);
115 [ - + - - ]: 16760 : num->n_bigits = num->bigits[1] ? 2U : num->bigits[0] ? 1U : 0U;
116 : 16760 : }
117 : :
118 : : EXESS_I_NONBLOCKING void
119 : 30669 : exess_bigint_set_pow10(ExessBigint* num, const unsigned exponent)
120 : : {
121 : 30669 : exess_bigint_set_u32(num, 1);
122 : 30669 : exess_bigint_multiply_pow10(num, exponent);
123 : 30669 : }
124 : :
125 : : static EXESS_I_NONBLOCKING uint32_t
126 : 83 : read_u32(const char* const str, uint32_t* result, uint32_t* n_digits)
127 : : {
128 : 83 : EXESS_I_CONSTEXPR size_t uint32_digits10 = 9;
129 : :
130 : 83 : *result = *n_digits = 0;
131 : :
132 : 83 : uint32_t i = 0;
133 [ + + + - : 504 : for (; str[i] >= '0' && str[i] <= '9' && *n_digits < uint32_digits10; ++i) {
+ + ]
134 : 421 : *result = (*result * 10U) + (unsigned)(str[i] - '0');
135 : 421 : *n_digits += 1;
136 : : }
137 : :
138 : 83 : return i;
139 : : }
140 : :
141 : : EXESS_I_NONBLOCKING void
142 : 30 : exess_bigint_set_decimal_string(ExessBigint* num, const char* const str)
143 : : {
144 : 30 : exess_bigint_zero(num);
145 : :
146 : 30 : uint32_t pos = 0;
147 : 30 : uint32_t n_digits = 0;
148 : 30 : uint32_t n_read = 0;
149 : 30 : uint32_t word = 0;
150 [ + + ]: 83 : while ((n_read = read_u32(str + pos, &word, &n_digits))) {
151 : 53 : exess_bigint_multiply_u32(num, (uint32_t)POW10[n_digits]);
152 : 53 : exess_bigint_add_u32(num, word);
153 : 53 : pos += n_read;
154 : : }
155 : :
156 : 30 : exess_bigint_clamp(num);
157 : 30 : }
158 : :
159 : : EXESS_I_NONBLOCKING void
160 : 880920 : exess_bigint_multiply_u32(ExessBigint* num, const uint32_t factor)
161 : : {
162 [ - + + ]: 880920 : switch (factor) {
163 : 0 : case 0:
164 : 0 : exess_bigint_zero(num);
165 : 0 : return;
166 : 2847 : case 1:
167 : 2847 : return;
168 : 878073 : default:
169 : 878073 : break;
170 : : }
171 : :
172 : 878073 : Hugit carry = 0;
173 [ + + ]: 7998926 : for (unsigned i = 0; i < num->n_bigits; ++i) {
174 : 7120853 : const Hugit p = (Hugit)factor * num->bigits[i];
175 : 7120853 : const Hugit hugit = p + (carry & bigit_mask);
176 : :
177 : 7120853 : num->bigits[i] = (Bigit)(hugit & bigit_mask);
178 : :
179 : 7120853 : carry = (hugit >> 32U) + (carry >> 32U);
180 : : }
181 : :
182 [ + + ]: 993233 : for (; carry; carry >>= 32U) {
183 [ - + ]: 115160 : assert(num->n_bigits + 1 <= BIGINT_MAX_BIGITS);
184 : 115160 : num->bigits[num->n_bigits++] = (Bigit)carry;
185 : : }
186 : : }
187 : :
188 : : EXESS_I_NONBLOCKING void
189 : 68077 : exess_bigint_multiply_u64(ExessBigint* num, const uint64_t factor)
190 : : {
191 [ - + + ]: 68077 : switch (factor) {
192 : 0 : case 0:
193 : 0 : exess_bigint_zero(num);
194 : 0 : return;
195 : 2 : case 1:
196 : 2 : return;
197 : 68075 : default:
198 : 68075 : break;
199 : : }
200 : :
201 : 68075 : const Hugit f_lo = factor & bigit_mask;
202 : 68075 : const Hugit f_hi = factor >> 32U;
203 : :
204 : 68075 : Hugit carry = 0;
205 [ + + ]: 354396 : for (unsigned i = 0; i < num->n_bigits; ++i) {
206 : 286321 : const Hugit p_lo = f_lo * num->bigits[i];
207 : 286321 : const Hugit p_hi = f_hi * num->bigits[i];
208 : 286321 : const Hugit hugit = p_lo + (carry & bigit_mask);
209 : :
210 : 286321 : num->bigits[i] = (Bigit)(hugit & bigit_mask);
211 : 286321 : carry = p_hi + (hugit >> 32U) + (carry >> 32U);
212 : : }
213 : :
214 [ + + ]: 180308 : for (; carry; carry >>= 32U) {
215 [ - + ]: 112233 : assert(num->n_bigits + 1 <= BIGINT_MAX_BIGITS);
216 : 112233 : num->bigits[num->n_bigits++] = (Bigit)(carry & bigit_mask);
217 : : }
218 : : }
219 : :
220 : : EXESS_I_NONBLOCKING void
221 : 30699 : 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 : 30699 : 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 : 30699 : 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 [ + + - + ]: 30699 : if (exponent == 0 || num->n_bigits == 0) {
249 : 373 : return;
250 : : }
251 : :
252 : : // Multiply by 5^27 until e < 27 so we can switch to 32 bits
253 : 30326 : unsigned e = exponent;
254 [ + + ]: 84464 : while (e >= 27) {
255 : 54138 : exess_bigint_multiply_u64(num, pow5_27);
256 : 54138 : e -= 27;
257 : : }
258 : :
259 : : // Multiply by 5^13 until e < 13 so we have only one multiplication left
260 [ + + ]: 45534 : while (e >= 13) {
261 : 15208 : exess_bigint_multiply_u32(num, pow5[13]);
262 : 15208 : e -= 13;
263 : : }
264 : :
265 : : // Multiply by the final 5^e (which may be zero, making this a noop)
266 : 30326 : exess_bigint_multiply_u32(num, pow5[e]);
267 : :
268 : : // Finally multiply by 2^e
269 : 30326 : exess_bigint_shift_left(num, exponent);
270 : : }
271 : :
272 : : EXESS_I_NONBLOCKING int
273 : 2840482 : exess_bigint_compare(const ExessBigint* lhs, const ExessBigint* rhs)
274 : : {
275 [ + + ]: 2840482 : if (lhs->n_bigits < rhs->n_bigits) {
276 : 3536 : return -1;
277 : : }
278 : :
279 [ + + ]: 2836946 : if (lhs->n_bigits > rhs->n_bigits) {
280 : 331345 : return 1;
281 : : }
282 : :
283 [ + + ]: 2552363 : for (int i = (int)lhs->n_bigits - 1; i >= 0; --i) {
284 : 2549332 : const Bigit bigit_l = lhs->bigits[i];
285 : 2549332 : const Bigit bigit_r = rhs->bigits[i];
286 [ + + ]: 2549332 : if (bigit_l < bigit_r) {
287 : 165804 : return -1;
288 : : }
289 : :
290 [ + + ]: 2383528 : if (bigit_l > bigit_r) {
291 : 2336766 : return 1;
292 : : }
293 : : }
294 : :
295 : 3031 : return 0;
296 : : }
297 : :
298 : : static int
299 : 446155 : exess_bigint_plus_compare_internal(const ExessBigint* const l,
300 : : const ExessBigint* const p,
301 : : const ExessBigint* const c)
302 : : {
303 [ + + ]: 446155 : if (l->n_bigits + 1 < c->n_bigits) {
304 : 36 : return -1;
305 : : }
306 : :
307 [ + + ]: 446119 : if (l->n_bigits > c->n_bigits) {
308 : 924 : return 1;
309 : : }
310 : :
311 [ + + + + ]: 445195 : if (p->n_bigits < l->n_bigits && l->n_bigits < c->n_bigits) {
312 : 11170 : return -1;
313 : : }
314 : :
315 : 434025 : Hugit borrow = 0;
316 [ + + ]: 454829 : for (int i = (int)c->n_bigits - 1; i >= 0; --i) {
317 : 454786 : const Bigit ai = l->bigits[i];
318 : 454786 : const Bigit bi = p->bigits[i];
319 : 454786 : const Bigit ci = c->bigits[i];
320 : 454786 : const Hugit sum = (Hugit)ai + bi;
321 : :
322 [ + + ]: 454786 : if (sum > ci + borrow) {
323 : 33757 : return 1;
324 : : }
325 : :
326 : 421029 : borrow += ci - sum;
327 [ + + ]: 421029 : if (borrow > 1) {
328 : 400225 : return -1;
329 : : }
330 : :
331 : 20804 : borrow <<= 32U;
332 : : }
333 : :
334 [ - + ]: 43 : return borrow ? -1 : 0;
335 : : }
336 : :
337 : : EXESS_I_NONBLOCKING int
338 : 446155 : exess_bigint_plus_compare(const ExessBigint* const l,
339 : : const ExessBigint* const p,
340 : : const ExessBigint* const c)
341 : : {
342 [ - + ]: 446155 : assert(exess_bigint_is_clamped(l));
343 [ - + ]: 446155 : assert(exess_bigint_is_clamped(p));
344 [ - + ]: 446155 : assert(exess_bigint_is_clamped(c));
345 : :
346 : 446155 : return (l->n_bigits < p->n_bigits)
347 : 2323 : ? exess_bigint_plus_compare_internal(p, l, c)
348 [ + + ]: 448478 : : exess_bigint_plus_compare_internal(l, p, c);
349 : : }
350 : :
351 : : static unsigned
352 : 30692 : exess_bigint_add_carry(ExessBigint* lhs, unsigned i, bool carry)
353 : : {
354 [ + + ]: 31148 : for (; carry; ++i) {
355 : 456 : const Hugit sum = (Hugit)carry + lhs->bigits[i];
356 : 456 : lhs->bigits[i] = (Bigit)(sum & bigit_mask);
357 : 456 : carry = (Bigit)((sum & carry_mask) >> 32U);
358 : : }
359 : :
360 : 30692 : return i;
361 : : }
362 : :
363 : : EXESS_I_NONBLOCKING void
364 : 53 : exess_bigint_add_u32(ExessBigint* lhs, const uint32_t rhs)
365 : : {
366 [ + + ]: 53 : if (lhs->n_bigits == 0) {
367 : 30 : exess_bigint_set_u32(lhs, rhs);
368 : 30 : 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 : 30669 : exess_bigint_add(ExessBigint* lhs, const ExessBigint* rhs)
383 : : {
384 [ - + ]: 30669 : assert(MAX(lhs->n_bigits, rhs->n_bigits) + 1 <= BIGINT_MAX_BIGITS);
385 : :
386 : 30669 : bool carry = 0;
387 : 30669 : unsigned i = 0;
388 [ + + ]: 215981 : for (; i < rhs->n_bigits; ++i) {
389 : 185312 : const Hugit sum = (Hugit)lhs->bigits[i] + rhs->bigits[i] + carry;
390 : :
391 : 185312 : lhs->bigits[i] = (Bigit)(sum & bigit_mask);
392 : 185312 : carry = (sum & carry_mask) >> 32U;
393 : : }
394 : :
395 : 30669 : i = exess_bigint_add_carry(lhs, i, carry);
396 : 30669 : lhs->n_bigits = MAX(i, lhs->n_bigits);
397 [ - + ]: 30669 : assert(exess_bigint_is_clamped(lhs));
398 : 30669 : }
399 : :
400 : : static unsigned
401 : 1149269 : exess_bigint_subtract_borrow(ExessBigint* lhs, unsigned i, bool borrow)
402 : : {
403 [ + + ]: 1162342 : for (; borrow; ++i) {
404 : 13073 : const Bigit l = lhs->bigits[i];
405 : :
406 : 13073 : lhs->bigits[i] -= borrow;
407 : :
408 : 13073 : borrow = l == 0;
409 : : }
410 : :
411 : 1149269 : return i;
412 : : }
413 : :
414 : : EXESS_I_NONBLOCKING void
415 : 280777 : exess_bigint_subtract(ExessBigint* lhs, const ExessBigint* rhs)
416 : : {
417 [ - + ]: 280777 : assert(exess_bigint_is_clamped(lhs));
418 [ - + ]: 280777 : assert(exess_bigint_is_clamped(rhs));
419 [ - + ]: 280777 : assert(exess_bigint_compare(lhs, rhs) >= 0);
420 : :
421 : 280777 : bool borrow = 0;
422 : 280777 : unsigned i = 0;
423 [ + + ]: 2713879 : for (i = 0; i < rhs->n_bigits; ++i) {
424 : 2433102 : const Bigit l = lhs->bigits[i];
425 : 2433102 : const Bigit r = rhs->bigits[i];
426 : :
427 : 2433102 : lhs->bigits[i] = l - r - borrow;
428 [ + + + + : 2433102 : borrow = l < r || (l == r && borrow);
- + ]
429 : : }
430 : :
431 : 280777 : exess_bigint_subtract_borrow(lhs, i, borrow);
432 : 280777 : exess_bigint_clamp(lhs);
433 : 280777 : }
434 : :
435 : : static unsigned
436 : 1584953 : exess_bigint_leading_zeros(const ExessBigint* num)
437 : : {
438 [ - + ]: 1584953 : assert(num->n_bigits);
439 : 3169906 : return (32 * (BIGINT_MAX_BIGITS - num->n_bigits)) +
440 : 1584953 : exess_clz32(num->bigits[num->n_bigits - 1]);
441 : : }
442 : :
443 : : static Bigit
444 : 7883094 : exess_bigint_left_shifted_bigit_i(const ExessBigint* num,
445 : : const Offset amount,
446 : : const unsigned index)
447 : : {
448 [ + - + + ]: 7883094 : if (amount.bigits == 0 && amount.bits == 0) {
449 : 3685902 : return num->bigits[index];
450 : : }
451 : :
452 [ - + ]: 4197192 : if (index < amount.bigits) {
453 : 0 : return 0;
454 : : }
455 : :
456 [ - + ]: 4197192 : if (amount.bits == 0) { // Simple bigit-aligned shift
457 : 0 : return num->bigits[index - amount.bigits];
458 : : }
459 : :
460 [ + + ]: 4197192 : if (index == amount.bigits) { // Last non-zero bigit
461 : 439697 : return num->bigits[0] << amount.bits;
462 : : }
463 : :
464 : : // Bigit + sub-bigit bit offset shift
465 : 3757495 : const unsigned right_shift = BIGINT_BIGIT_BITS - amount.bits;
466 : 3757495 : return (num->bigits[index - amount.bigits] << amount.bits) |
467 : 3757495 : (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 : 868492 : exess_bigint_subtract_left_shifted(ExessBigint* lhs,
480 : : const ExessBigint* rhs,
481 : : const unsigned amount)
482 : : {
483 [ - + ]: 868492 : assert(exess_bigint_is_clamped(lhs));
484 [ - + ]: 868492 : assert(exess_bigint_is_clamped(rhs));
485 : : #ifndef NDEBUG
486 : : {
487 : 868492 : ExessBigint check_rhs = *rhs;
488 : 868492 : exess_bigint_shift_left(&check_rhs, amount);
489 [ - + ]: 868492 : assert(exess_bigint_compare(lhs, &check_rhs) >= 0);
490 : : }
491 : : #endif
492 : :
493 : 868492 : const Offset offset = make_offset(amount);
494 : 868492 : const unsigned r_n_bigits = rhs->n_bigits + offset.bigits + (bool)offset.bits;
495 : :
496 : 868492 : bool borrow = 0;
497 : 868492 : unsigned i = 0;
498 [ + + ]: 8751586 : for (i = 0; i < r_n_bigits; ++i) {
499 : 7883094 : const Bigit l = lhs->bigits[i];
500 : 7883094 : const Bigit r = exess_bigint_left_shifted_bigit_i(rhs, offset, i);
501 : :
502 : 7883094 : lhs->bigits[i] = l - r - borrow;
503 [ + + + + : 7883094 : borrow = l < r || ((l == r) && borrow);
+ + ]
504 : : }
505 : :
506 : 868492 : exess_bigint_subtract_borrow(lhs, i, borrow);
507 : 868492 : exess_bigint_clamp(lhs);
508 : 868492 : }
509 : :
510 : : EXESS_I_NONBLOCKING uint32_t
511 : 437721 : exess_bigint_divmod(ExessBigint* lhs, const ExessBigint* rhs)
512 : : {
513 [ - + ]: 437721 : assert(exess_bigint_is_clamped(lhs));
514 [ - + ]: 437721 : assert(exess_bigint_is_clamped(rhs));
515 [ - + ]: 437721 : assert(rhs->n_bigits > 0);
516 [ + + ]: 437721 : if (lhs->n_bigits < rhs->n_bigits) {
517 : 2037 : return 0;
518 : : }
519 : :
520 : 435684 : uint32_t result = 0;
521 : 435684 : const Bigit r0 = rhs->bigits[rhs->n_bigits - 1];
522 : 435684 : const unsigned rlz = exess_bigint_leading_zeros(rhs);
523 : :
524 : : // Shift and subtract until the LHS does not have more bigits
525 [ + + ]: 486398 : while (lhs->n_bigits > rhs->n_bigits) {
526 : 50714 : const unsigned llz = exess_bigint_leading_zeros(lhs);
527 : 50714 : const unsigned shift = rlz - llz - 1;
528 : :
529 : 50714 : result += 1U << shift;
530 : 50714 : exess_bigint_subtract_left_shifted(lhs, rhs, shift);
531 : : }
532 : :
533 : : // Handle simple termination cases
534 : 435684 : int cmp = exess_bigint_compare(lhs, rhs);
535 [ + + ]: 435684 : if (cmp < 0) {
536 : 39321 : return result;
537 : : }
538 : :
539 [ + + - + ]: 396363 : 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 [ + + ]: 1214141 : for (; cmp >= 0; cmp = exess_bigint_compare(lhs, rhs)) {
550 : 1098555 : const unsigned llz = exess_bigint_leading_zeros(lhs);
551 [ + + ]: 1098555 : if (rlz == llz) {
552 : : // Both have the same number of leading zeros, just subtract
553 : 280777 : exess_bigint_subtract(lhs, rhs);
554 : 280777 : return result + 1;
555 : : }
556 : :
557 : 817778 : const unsigned shift = rlz - llz - 1;
558 : 817778 : result += 1U << shift;
559 : 817778 : exess_bigint_subtract_left_shifted(lhs, rhs, shift);
560 : : }
561 : :
562 : 115586 : return result;
563 : : }
|
