Lines Matching +full:se +full:- +full:neg
4 * SPDX-License-Identifier: BSD-2-Clause
6 * Copyright (c) 2018-2024 Gavin D. Howard and contributors.
72 * Conditionally negate @a n based on @a neg. Algorithm taken from
75 * @param neg The condition to negate or not.
78 bc_num_neg(size_t n, bool neg) in bc_num_neg() argument
80 return (((ssize_t) n) ^ -((ssize_t) neg)) + neg; in bc_num_neg()
86 * @return -1 if the number is less than 0, 1 if greater, and 0 if equal.
91 return bc_num_neg((n)->len != 0, BC_NUM_NEG(n)); in bc_num_cmpZero()
102 return n->len ? n->len - BC_NUM_RDX_VAL(n) : 0; in bc_num_int()
117 if (req > n->cap) in bc_num_expand()
121 n->num = bc_vm_realloc(n->num, BC_NUM_SIZE(req)); in bc_num_expand()
122 n->cap = req; in bc_num_expand()
137 n->scale = scale; in bc_num_setToZero()
138 n->len = n->rdx = 0; in bc_num_setToZero()
151 n->len = 1; in bc_num_one()
152 n->num[0] = 1; in bc_num_one()
164 while (BC_NUM_NONZERO(n) && !n->num[n->len - 1]) in bc_num_clean()
166 n->len -= 1; in bc_num_clean()
170 if (BC_NUM_ZERO(n)) n->rdx = 0; in bc_num_clean()
175 if (n->len < rdx) n->len = rdx; in bc_num_clean()
180 * Returns the log base 10 of @a i. I could have done this with floating-point
182 * floating-point code in the entire codebase, and I decided I didn't want any.
197 assert(len - 1 <= BC_BASE_DIGS + 1); in bc_num_log10()
199 return len - 1; in bc_num_log10()
214 return BC_BASE_DIGS - bc_num_log10((size_t) *n); in bc_num_zeroDigits()
232 digs = digs != 0 ? BC_BASE_DIGS - digs : 0; in bc_num_leastSigPow()
247 if (digits > 0) digits -= bc_num_zeroDigits(n->num + n->len - 1); in bc_num_intDigits()
252 * Returns the number of limbs of a number that are non-zero starting at the
255 * decimal place to ignore. If there are zero limbs after non-zero limbs, they
256 * are counted as non-zero limbs.
258 * @return The number of non-zero limbs after the decimal point.
263 size_t i, len = n->len; in bc_num_nonZeroLen()
267 for (i = len - 1; i < len && !n->num[i]; --i) in bc_num_nonZeroLen()
281 * needs to be multiplied by in order to be greater than 1 or less than -1.
283 * @return The power of 10 that a number greater than 1 and less than -1 must
284 * be multiplied by to be greater than 1 or less than -1.
290 size_t i, places, idx = bc_num_nonZeroLen(n) - 1; in bc_num_negPow10()
295 for (i = BC_BASE_DIGS - 1; i < BC_BASE_DIGS; --i) in bc_num_negPow10()
297 if (bc_num_pow10[i] > (BcBigDig) n->num[idx]) places += 1; in bc_num_negPow10()
303 return places + (BC_NUM_RDX_VAL(n) - (idx + 1)) * BC_BASE_DIGS; in bc_num_negPow10()
309 * Performs a one-limb add with a carry.
325 if (*carry) a -= BC_BASE_POW; in bc_num_addDigits()
334 * Performs a one-limb subtract with a carry.
351 assert(a - b >= 0); in bc_num_subDigits()
352 assert(a - b < BC_BASE_POW); in bc_num_subDigits()
354 return a - b; in bc_num_subDigits()
406 * Multiply a BcNum array by a one-limb number. This is a faster version of
408 * @param a The BcNum to multiply by the one-limb number.
409 * @param b The one limb of the one-limb number.
421 if (a->len + 1 > c->cap) bc_num_expand(c, a->len + 1); in bc_num_mulArray()
425 memset(c->num, 0, BC_NUM_SIZE(c->cap)); in bc_num_mulArray()
428 for (i = 0; i < a->len; ++i) in bc_num_mulArray()
430 BcBigDig in = ((BcBigDig) a->num[i]) * b + carry; in bc_num_mulArray()
431 c->num[i] = in % BC_BASE_POW; in bc_num_mulArray()
438 c->num[i] = (BcDig) carry; in bc_num_mulArray()
439 assert(c->num[i] >= 0 && c->num[i] < BC_BASE_POW); in bc_num_mulArray()
440 c->len = a->len; in bc_num_mulArray()
441 c->len += (carry != 0); in bc_num_mulArray()
447 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len); in bc_num_mulArray()
448 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len); in bc_num_mulArray()
452 * Divide a BcNum array by a one-limb number. This is a faster version of divide
454 * @param a The BcNum to multiply by the one-limb number.
455 * @param b The one limb of the one-limb number.
466 assert(c->cap >= a->len); in bc_num_divArray()
469 for (i = a->len - 1; i < a->len; --i) in bc_num_divArray()
471 BcBigDig in = ((BcBigDig) a->num[i]) + carry * BC_BASE_POW; in bc_num_divArray()
473 c->num[i] = (BcDig) (in / b); in bc_num_divArray()
474 assert(c->num[i] >= 0 && c->num[i] < BC_BASE_POW); in bc_num_divArray()
479 c->len = a->len; in bc_num_divArray()
485 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len); in bc_num_divArray()
486 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len); in bc_num_divArray()
501 for (i = len - 1; i < len && !(c = a[i] - b[i]); --i) in bc_num_compare()
514 bool a_max, neg = false; in bc_num_cmp() local
523 if (BC_NUM_ZERO(a)) return bc_num_neg(b->len != 0, !BC_NUM_NEG(b)); in bc_num_cmp()
527 if (BC_NUM_NEG(b)) neg = true; in bc_num_cmp()
528 else return -1; in bc_num_cmp()
535 a_int -= b_int; in bc_num_cmp()
538 if (a_int) return neg ? -((ssize_t) a_int) : (ssize_t) a_int; in bc_num_cmp()
549 diff = ardx - brdx; in bc_num_cmp()
550 max_num = a->num + diff; in bc_num_cmp()
551 min_num = b->num; in bc_num_cmp()
556 diff = brdx - ardx; in bc_num_cmp()
557 max_num = b->num + diff; in bc_num_cmp()
558 min_num = a->num; in bc_num_cmp()
561 // Do a full limb-by-limb comparison. in bc_num_cmp()
565 if (cmp) return bc_num_neg((size_t) cmp, !a_max == !neg); in bc_num_cmp()
569 for (max_num -= diff, i = diff - 1; i < diff; --i) in bc_num_cmp()
571 if (max_num[i]) return bc_num_neg(1, !a_max == !neg); in bc_num_cmp()
587 places_rdx = nrdx ? nrdx - BC_NUM_RDX(n->scale - places) : 0; in bc_num_truncate()
590 assert(places <= n->scale && (BC_NUM_ZERO(n) || places_rdx <= n->len)); in bc_num_truncate()
592 n->scale -= places; in bc_num_truncate()
593 BC_NUM_RDX_SET(n, nrdx - places_rdx); in bc_num_truncate()
602 pow = bc_num_leastSigPow(n->scale); in bc_num_truncate()
604 n->len -= places_rdx; in bc_num_truncate()
609 memmove(n->num, n->num + places_rdx, BC_NUM_SIZE(n->len)); in bc_num_truncate()
612 if (BC_NUM_NONZERO(n)) n->num[0] -= n->num[0] % (BcDig) pow; in bc_num_truncate()
628 n->scale += places; in bc_num_extend()
635 places_rdx = BC_NUM_RDX(places + n->scale) - nrdx; in bc_num_extend()
641 bc_num_expand(n, bc_vm_growSize(n->len, places_rdx)); in bc_num_extend()
643 memmove(n->num + places_rdx, n->num, BC_NUM_SIZE(n->len)); in bc_num_extend()
645 memset(n->num, 0, BC_NUM_SIZE(places_rdx)); in bc_num_extend()
650 n->scale += places; in bc_num_extend()
651 n->len += places_rdx; in bc_num_extend()
653 assert(BC_NUM_RDX_VAL(n) == BC_NUM_RDX(n->scale)); in bc_num_extend()
663 if (n->scale < scale) bc_num_extend(n, scale - n->scale); in bc_num_retireMul()
664 else bc_num_truncate(n, n->scale - scale); in bc_num_retireMul()
669 if (BC_NUM_NONZERO(n)) n->rdx = BC_NUM_NEG_VAL(n, !neg1 != !neg2); in bc_num_retireMul()
688 if (idx < n->len) in bc_num_split()
691 b->len = n->len - idx; in bc_num_split()
692 a->len = idx; in bc_num_split()
693 a->scale = b->scale = 0; in bc_num_split()
697 assert(a->cap >= a->len); in bc_num_split()
698 assert(b->cap >= b->len); in bc_num_split()
703 memcpy(b->num, n->num + idx, BC_NUM_SIZE(b->len)); in bc_num_split()
705 memcpy(a->num, n->num, BC_NUM_SIZE(idx)); in bc_num_split()
726 r->len = n->len - rdx; in bc_num_shiftRdx()
727 r->cap = n->cap - rdx; in bc_num_shiftRdx()
728 r->num = n->num + rdx; in bc_num_shiftRdx()
731 r->scale = 0; in bc_num_shiftRdx()
749 for (i = 0; i < n->len && !n->num[i]; ++i) in bc_num_shiftZero()
754 n->len -= i; in bc_num_shiftZero()
755 n->num += i; in bc_num_shiftZero()
769 n->len += places_rdx; in bc_num_unshiftZero()
770 n->num -= places_rdx; in bc_num_unshiftZero()
774 * Shifts the digits right within a number by no more than BC_BASE_DIGS - 1.
784 size_t i, len = n->len; in bc_num_shift()
786 BcDig* ptr = n->num; in bc_num_shift()
792 dig = bc_num_pow10[BC_BASE_DIGS - dig]; in bc_num_shift()
796 for (i = len - 1; i < len; --i) in bc_num_shift()
825 if (places > n->scale) in bc_num_shiftLeft()
827 size_t size = bc_vm_growSize(BC_NUM_RDX(places - n->scale), n->len); in bc_num_shiftLeft()
828 if (size > SIZE_MAX - 1) bc_err(BC_ERR_MATH_OVERFLOW); in bc_num_shiftLeft()
834 if (n->scale >= places) n->scale -= places; in bc_num_shiftLeft()
835 else n->scale = 0; in bc_num_shiftLeft()
852 // whereas a non-integer might have its fractional part eliminated or only in bc_num_shiftLeft()
854 if (n->scale) in bc_num_shiftLeft()
861 size_t mod = n->scale % BC_BASE_DIGS, revdig; in bc_num_shiftLeft()
868 revdig = dig ? BC_BASE_DIGS - dig : 0; in bc_num_shiftLeft()
874 else places_rdx -= nrdx; in bc_num_shiftLeft()
877 // If this is non-zero, we need an extra place, so expand, move, and set. in bc_num_shiftLeft()
880 bc_num_expand(n, bc_vm_growSize(n->len, places_rdx)); in bc_num_shiftLeft()
882 memmove(n->num + places_rdx, n->num, BC_NUM_SIZE(n->len)); in bc_num_shiftLeft()
884 memset(n->num, 0, BC_NUM_SIZE(places_rdx)); in bc_num_shiftLeft()
885 n->len += places_rdx; in bc_num_shiftLeft()
889 if (places > n->scale) in bc_num_shiftLeft()
891 n->scale = 0; in bc_num_shiftLeft()
896 n->scale -= places; in bc_num_shiftLeft()
897 BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale)); in bc_num_shiftLeft()
901 if (shift) bc_num_shift(n, BC_BASE_DIGS - dig); in bc_num_shiftLeft()
918 n->scale += places; in bc_num_shiftRight()
919 bc_num_expand(n, BC_NUM_RDX(n->scale)); in bc_num_shiftRight()
927 scale = n->scale; in bc_num_shiftRight()
940 expand = places_rdx - 1; in bc_num_shiftRight()
950 if (expand > int_len) expand -= int_len; in bc_num_shiftRight()
955 bc_num_expand(n, bc_vm_growSize(expand, n->len)); in bc_num_shiftRight()
957 memset(n->num + n->len, 0, BC_NUM_SIZE(expand)); in bc_num_shiftRight()
960 n->len += expand; in bc_num_shiftRight()
961 n->scale = 0; in bc_num_shiftRight()
967 n->scale = scale + places; in bc_num_shiftRight()
968 BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale)); in bc_num_shiftRight()
972 assert(BC_NUM_RDX_VAL(n) <= n->len && n->len <= n->cap); in bc_num_shiftRight()
973 assert(BC_NUM_RDX_VAL(n) == BC_NUM_RDX(n->scale)); in bc_num_shiftRight()
983 * @return True if the number is a non-integer, false otherwise.
1002 zero = (n->num[i] == 0); in bc_num_nonInt()
1049 * @param sub Non-zero for a subtract, zero for an add.
1070 c->rdx = BC_NUM_NEG_VAL(c, BC_NUM_NEG(b) != sub); in bc_num_as()
1092 diff = max_rdx - min_rdx; in bc_num_as()
1102 do_rev_sub = (bc_num_compare(a->num + diff, b->num, b->len) < 0); in bc_num_as()
1104 else do_rev_sub = (bc_num_compare(a->num, b->num + diff, a->len) <= 0); in bc_num_as()
1114 assert(max_len <= c->cap); in bc_num_as()
1119 ptr_l = b->num; in bc_num_as()
1120 ptr_r = a->num; in bc_num_as()
1121 len_l = b->len; in bc_num_as()
1122 len_r = a->len; in bc_num_as()
1126 ptr_l = a->num; in bc_num_as()
1127 ptr_r = b->num; in bc_num_as()
1128 len_l = a->len; in bc_num_as()
1129 len_r = b->len; in bc_num_as()
1132 ptr_c = c->num; in bc_num_as()
1150 len_l -= diff; in bc_num_as()
1174 len_r -= diff; in bc_num_as()
1226 // reverse subtraction (b - a). in bc_num_as()
1229 c->len = max_len; in bc_num_as()
1230 c->scale = BC_MAX(a->scale, b->scale); in bc_num_as()
1246 size_t i, alen = a->len, blen = b->len, clen; in bc_num_m_simp()
1247 BcDig* ptr_a = a->num; in bc_num_m_simp()
1248 BcDig* ptr_b = b->num; in bc_num_m_simp()
1260 ptr_c = c->num; in bc_num_m_simp()
1262 memset(ptr_c, 0, BC_NUM_SIZE(c->cap)); in bc_num_m_simp()
1270 ssize_t sidx = (ssize_t) (i - blen + 1); in bc_num_m_simp()
1275 k = BC_MIN(i, blen - 1); in bc_num_m_simp()
1279 for (; j < alen && k < blen; ++j, --k) in bc_num_m_simp()
1308 c->len = clen; in bc_num_m_simp()
1324 assert(n->len >= shift + a->len); in bc_num_shiftAddSub()
1326 op(n->num + shift, a->num, a->len); in bc_num_shiftAddSub()
1357 if (a->len < BC_NUM_KARATSUBA_LEN || b->len < BC_NUM_KARATSUBA_LEN) in bc_num_k()
1365 max = BC_MAX(a->len, b->len); in bc_num_k()
1406 c->len = max; in bc_num_k()
1408 memset(c->num, 0, BC_NUM_SIZE(c->len)); in bc_num_k()
1501 ascale = a->scale; in bc_num_m()
1502 bscale = b->scale; in bc_num_m()
1512 if ((a->len == 1 || b->len == 1) && !a->rdx && !b->rdx) in bc_num_m()
1518 if (a->len == 1) in bc_num_m()
1520 dig = (BcBigDig) a->num[0]; in bc_num_m()
1525 dig = (BcBigDig) b->num[0]; in bc_num_m()
1534 c->rdx = BC_NUM_NEG_VAL(c, BC_NUM_NEG(a) != BC_NUM_NEG(b)); in bc_num_m()
1547 bc_num_init(&cpa, a->len + BC_NUM_RDX_VAL(a)); in bc_num_m()
1548 bc_num_init(&cpb, b->len + BC_NUM_RDX_VAL(b)); in bc_num_m()
1597 len = bc_vm_growSize(c->len, zero); in bc_num_m()
1602 bc_num_shiftLeft(c, (len - c->len) * BC_BASE_DIGS); in bc_num_m()
1619 * Returns true if the BcDig array has non-zero limbs, false otherwise.
1622 * @return True if @a has any non-zero limbs, false otherwise.
1629 for (i = len - 1; i < len; --i) in bc_num_nonZeroDig()
1651 if (b->len > len && a[len]) cmp = bc_num_compare(a, b->num, len + 1); in bc_num_divCmp()
1652 else if (b->len <= len) in bc_num_divCmp()
1655 else cmp = bc_num_compare(a, b->num, len); in bc_num_divCmp()
1657 else cmp = -1; in bc_num_divCmp()
1677 pow = BC_BASE_DIGS - bc_num_log10((size_t) divisor); in bc_num_divExtend()
1714 assert(b->len < a->len); in bc_num_d_long()
1716 len = b->len; in bc_num_d_long()
1717 end = a->len - len; in bc_num_d_long()
1723 bc_num_expand(c, a->len); in bc_num_d_long()
1725 memset(c->num, 0, c->cap * sizeof(BcDig)); in bc_num_d_long()
1729 c->scale = a->scale; in bc_num_d_long()
1730 c->len = a->len; in bc_num_d_long()
1734 divisor = (BcBigDig) b->num[len - 1]; in bc_num_d_long()
1737 // the divisor. The condition asks if b has any other non-zero limbs. in bc_num_d_long()
1738 if (len > 1 && bc_num_nonZeroDig(b->num, len - 1)) in bc_num_d_long()
1741 // results in either 16 for 64-bit 9-digit limbs or 7 for 32-bit 4-digit in bc_num_d_long()
1757 len2 = BC_MAX(a->len, b->len); in bc_num_d_long()
1761 if (len2 + 1 > a->len) a->len = len2 + 1; in bc_num_d_long()
1765 reallen = b->len; in bc_num_d_long()
1766 realend = a->len - reallen; in bc_num_d_long()
1767 divisor = (BcBigDig) b->num[reallen - 1]; in bc_num_d_long()
1769 realnonzero = bc_num_nonZeroDig(b->num, reallen - 1); in bc_num_d_long()
1788 bc_num_expand(c, a->len); in bc_num_d_long()
1790 memset(c->num, 0, BC_NUM_SIZE(c->cap)); in bc_num_d_long()
1792 assert(c->scale >= scale); in bc_num_d_long()
1793 rdx = BC_NUM_RDX_VAL(c) - BC_NUM_RDX(scale); in bc_num_d_long()
1804 for (i = realend - 1; i < realend && i >= rdx && BC_NUM_NONZERO(a); --i) in bc_num_d_long()
1810 n = a->num + i; in bc_num_d_long()
1811 assert(n >= a->num); in bc_num_d_long()
1826 dividend = n1 * BC_BASE_POW + (BcBigDig) n[len - 1]; in bc_num_d_long()
1835 bc_num_subArrays(n, b->num, len); in bc_num_d_long()
1855 else cmp = -1; in bc_num_d_long()
1861 c->num[i] = (BcDig) result; in bc_num_d_long()
1902 if (!BC_NUM_RDX_VAL(a) && !BC_NUM_RDX_VAL(b) && b->len == 1 && !scale) in bc_num_d()
1905 bc_num_divArray(a, (BcBigDig) b->num[0], c, &rem); in bc_num_d()
1925 len = b->len; in bc_num_d()
1932 bc_num_extend(&cpa, (len - cpa.len) * BC_BASE_DIGS); in bc_num_d()
1939 bc_num_extend(&cpa, b->scale); in bc_num_d()
1940 cpardx = BC_NUM_RDX_VAL_NP(cpa) - BC_NUM_RDX(b->scale); in bc_num_d()
2002 bool neg; in bc_num_r() local
2018 bc_num_init(&temp, d->cap); in bc_num_r()
2034 // Implement the rest of the (a - (a / b) * b) formula. in bc_num_r()
2039 if (ts > d->scale && BC_NUM_NONZERO(d)) bc_num_extend(d, ts - d->scale); in bc_num_r()
2041 neg = BC_NUM_NEG(d); in bc_num_r()
2043 d->rdx = BC_NUM_NEG_VAL(d, BC_NUM_NONZERO(d) ? neg : false); in bc_num_r()
2068 ts = bc_vm_growSize(scale, b->scale); in bc_num_rem()
2069 ts = BC_MAX(ts, a->scale); in bc_num_rem()
2103 bool neg; in bc_num_p() local
2139 neg = BC_NUM_NEG_NP(btemp); in bc_num_p()
2154 if (!neg) in bc_num_p()
2156 size_t max = BC_MAX(scale, a->scale), scalepow; in bc_num_p()
2157 scalepow = bc_num_mulOverflow(a->scale, exp); in bc_num_p()
2164 for (powrdx = a->scale; !(exp & 1); exp >>= 1) in bc_num_p()
2196 if (neg) bc_num_inv(c, c, realscale); in bc_num_p()
2199 if (c->scale > realscale) bc_num_truncate(c, c->scale - realscale); in bc_num_p()
2227 if (val < c->scale) bc_num_truncate(c, c->scale - val); in bc_num_place()
2228 else if (val > c->scale) bc_num_extend(c, val - c->scale); in bc_num_place()
2269 * - a is not the same pointer as c.
2270 * - b is not the same pointer as c.
2271 * - there is enough room in c for the result.
2335 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len); in bc_num_binary()
2337 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len); in bc_num_binary()
2365 // of a valid number, except in the library. The library-specific code takes in bc_num_strValid()
2418 c = ((size_t) c) >= base ? (char) base - 1 : c; in bc_num_parseChar()
2422 else c -= '0'; in bc_num_parseChar()
2475 n->scale = (size_t) (rdx * in bc_num_parseDecimal()
2476 (((uintptr_t) (val + len)) - (((uintptr_t) ptr) + 1))); in bc_num_parseDecimal()
2479 BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale)); in bc_num_parseDecimal()
2483 i = len - (ptr == val ? 0 : i) - rdx; in bc_num_parseDecimal()
2485 mod = n->scale % BC_BASE_DIGS; in bc_num_parseDecimal()
2486 i = mod ? BC_BASE_DIGS - mod : 0; in bc_num_parseDecimal()
2487 n->len = ((temp + i) / BC_BASE_DIGS); in bc_num_parseDecimal()
2491 bc_num_expand(n, n->len + !BC_DIGIT_CLAMP); in bc_num_parseDecimal()
2493 memset(n->num, 0, BC_NUM_SIZE(n->len + !BC_DIGIT_CLAMP)); in bc_num_parseDecimal()
2499 n->len = n->rdx = 0; in bc_num_parseDecimal()
2514 for (i = len - 1; i < len; --i, ++exp) in bc_num_parseDecimal()
2519 if (c == '.') exp -= 1; in bc_num_parseDecimal()
2532 else c -= '0'; in bc_num_parseDecimal()
2536 dig = ((BcBigDig) n->num[idx]) + ((BcBigDig) c) * pow; in bc_num_parseDecimal()
2542 n->num[idx + 1] = (BcDig) (dig / BC_BASE_POW); in bc_num_parseDecimal()
2543 n->num[idx] = (BcDig) (dig % BC_BASE_POW); in bc_num_parseDecimal()
2544 assert(n->num[idx] >= 0 && n->num[idx] < BC_BASE_POW); in bc_num_parseDecimal()
2545 assert(n->num[idx + 1] >= 0 && in bc_num_parseDecimal()
2546 n->num[idx + 1] < BC_BASE_POW); in bc_num_parseDecimal()
2550 n->num[idx] = (BcDig) dig; in bc_num_parseDecimal()
2551 assert(n->num[idx] >= 0 && n->num[idx] < BC_BASE_POW); in bc_num_parseDecimal()
2562 n->len += (!BC_DIGIT_CLAMP && n->num[n->len] != 0); in bc_num_parseDecimal()
2671 if (m2->len < rdx) m2->len = rdx; in bc_num_parseBase()
2694 if (n->scale < digs) bc_num_extend(n, digs - n->scale); in bc_num_parseBase()
2718 if (vm->nchars >= vm->line_len - 1 && vm->line_len) in bc_num_printNewline()
2782 for (exp = 0, pow = 1; exp < len - 1; ++exp, pow *= BC_BASE) in bc_num_printDigits()
2794 n -= dig * pow; in bc_num_printDigits()
2797 bc_num_putchar(((uchar) dig) + '0', bslash || exp != len - 1); in bc_num_printDigits()
2839 for (i = n->len - 1; i < n->len; --i) in bc_num_printDecimal()
2841 BcDig n9 = n->num[i]; in bc_num_printDecimal()
2843 bool irdx = (i == rdx - 1); in bc_num_printDecimal()
2847 temp = n->scale % BC_BASE_DIGS; in bc_num_printDecimal()
2848 temp = i || !temp ? 0 : BC_BASE_DIGS - temp; in bc_num_printDecimal()
2861 for (j = BC_BASE_DIGS - 1; j < BC_BASE_DIGS && j >= temp; --j) in bc_num_printDecimal()
2864 bool print_rdx = (irdx & (j == BC_BASE_DIGS - 1)); in bc_num_printDecimal()
2871 // While the first three arguments should be self-explanatory, in bc_num_printDecimal()
2896 bool neg = (n->len <= nrdx); in bc_num_printExponent() local
2913 if (neg) in bc_num_printExponent()
2923 if (eng && mod != 0) places += 3 - mod; in bc_num_printExponent()
2932 places = bc_num_intDigits(n) - 1; in bc_num_printExponent()
2937 if (eng && mod != 0) places -= 3 - (3 - mod); in bc_num_printExponent()
2957 if (neg) bc_num_putchar('-', true); in bc_num_printExponent()
2977 * @param rem BC_BASE_POW - @a pow.
2986 size_t i, len = n->len - idx; in bc_num_printFixup()
2988 BcDig* a = n->num + idx; in bc_num_printFixup()
2996 for (i = len - 1; i > 0; --i) in bc_num_printFixup()
3001 acc = ((BcBigDig) a[i]) * rem + ((BcBigDig) a[i - 1]); in bc_num_printFixup()
3004 a[i - 1] = (BcDig) (acc % pow); in bc_num_printFixup()
3014 if (i == len - 1) in bc_num_printFixup()
3021 a = n->num + idx; in bc_num_printFixup()
3024 a[len - 1] = 0; in bc_num_printFixup()
3039 n->len = len + idx; in bc_num_printFixup()
3057 for (i = 0; i < n->len; ++i) in bc_num_printPrepare()
3065 for (i = 0; i < n->len; ++i) in bc_num_printPrepare()
3070 if (n->num[i] >= (BcDig) pow) in bc_num_printPrepare()
3073 if (i + 1 == n->len) in bc_num_printPrepare()
3076 n->len = bc_vm_growSize(n->len, 1); in bc_num_printPrepare()
3077 bc_num_expand(n, n->len); in bc_num_printPrepare()
3080 n->num[i + 1] = 0; in bc_num_printPrepare()
3086 n->num[i + 1] += n->num[i] / ((BcDig) pow); in bc_num_printPrepare()
3087 n->num[i] %= (BcDig) pow; in bc_num_printPrepare()
3119 // This function uses an algorithm that Stefan Esser <se@freebsd.org> came in bc_num_printNum()
3183 if (base != vm->last_base) in bc_num_printNum()
3185 vm->last_pow = 1; in bc_num_printNum()
3186 vm->last_exp = 0; in bc_num_printNum()
3189 while (vm->last_pow * base <= BC_BASE_POW) in bc_num_printNum()
3191 vm->last_pow *= base; in bc_num_printNum()
3192 vm->last_exp += 1; in bc_num_printNum()
3196 vm->last_rem = BC_BASE_POW - vm->last_pow; in bc_num_printNum()
3197 vm->last_base = base; in bc_num_printNum()
3200 exp = vm->last_exp; in bc_num_printNum()
3202 // If vm->last_rem is 0, then the base we are printing in is a divisor of in bc_num_printNum()
3206 if (vm->last_rem != 0) in bc_num_printNum()
3208 bc_num_printPrepare(&intp, vm->last_rem, vm->last_pow); in bc_num_printNum()
3221 for (j = 0; j < exp && (i < intp.len - 1 || acc != 0); ++j) in bc_num_printNum()
3224 if (j != exp - 1) in bc_num_printNum()
3251 // While the first three arguments should be self-explanatory, the last in bc_num_printNum()
3275 !newline || (n->scale != 0 || i < stack.len - 1)); in bc_num_printNum()
3279 if (!n->scale) goto err; in bc_num_printNum()
3303 fracp2.scale = n->scale; in bc_num_printNum()
3307 while ((idigits = bc_num_intDigits(n1)) <= n->scale) in bc_num_printNum()
3318 // fracp is guaranteed to be non-negative and small enough. in bc_num_printNum()
3325 // While the first three arguments should be self-explanatory, the last in bc_num_printNum()
3330 print(dig, len, radix, !newline || idigits != n->scale); in bc_num_printNum()
3368 bool neg = BC_NUM_NEG(n); in bc_num_printBase() local
3384 width = bc_num_log10(base - 1); in bc_num_printBase()
3392 n->rdx = BC_NUM_NEG_VAL(n, neg); in bc_num_printBase()
3409 n->num = num; in bc_num_setup()
3410 n->cap = cap; in bc_num_setup()
3441 n->num = NULL; in bc_num_clear()
3442 n->cap = 0; in bc_num_clear()
3454 if (n->cap == BC_NUM_DEF_SIZE) bc_vm_addTemp(n->num); in bc_num_free()
3455 else free(n->num); in bc_num_free()
3465 bc_num_expand(d, s->len); in bc_num_copy()
3466 d->len = s->len; in bc_num_copy()
3470 d->rdx = s->rdx; in bc_num_copy()
3471 d->scale = s->scale; in bc_num_copy()
3473 memcpy(d->num, s->num, BC_NUM_SIZE(d->len)); in bc_num_copy()
3480 bc_num_init(d, s->len); in bc_num_createCopy()
3495 return n->scale; in bc_num_scale()
3501 size_t len = n->len; in bc_num_len()
3504 if (BC_NUM_ZERO(n)) return n->scale ? n->scale : 1; in bc_num_len()
3511 // ignore them until we hit the first non-zero digit. in bc_num_len()
3515 // The number of limbs with non-zero digits. in bc_num_len()
3519 scale = n->scale % BC_BASE_DIGS; in bc_num_len()
3523 zero = bc_num_zeroDigits(n->num + len - 1); in bc_num_len()
3526 len = len * BC_BASE_DIGS - zero - (BC_BASE_DIGS - scale); in bc_num_len()
3529 else len = bc_num_intDigits(n) + n->scale; in bc_num_len()
3544 assert(base >= BC_NUM_MIN_BASE && base <= vm->maxes[BC_PROG_GLOBALS_IBASE]); in bc_num_parse()
3576 if (BC_NUM_NEG(n)) bc_num_putchar('-', true); in bc_num_print()
3580 if (BC_Z && BC_NUM_RDX_VAL(n) == n->len && base != 0 && base != 1) in bc_num_print()
3586 // Short-circuit 0. in bc_num_print()
3611 // be non-NULL, n being non-negative, and n being less than vm->max. If all in bc_num_bigdig2()
3620 assert(bc_num_cmp(n, &vm->max) < 0); in bc_num_bigdig2()
3621 assert(n->len - nrdx <= 3); in bc_num_bigdig2()
3625 switch (n->len - nrdx) in bc_num_bigdig2()
3629 r = (BcBigDig) n->num[nrdx + 2]; in bc_num_bigdig2()
3637 r = r * BC_BASE_POW + (BcBigDig) n->num[nrdx + 1]; in bc_num_bigdig2()
3645 r = r * BC_BASE_POW + (BcBigDig) n->num[nrdx]; in bc_num_bigdig2()
3667 if (BC_ERR(bc_num_cmp(n, &vm->max) >= 0)) bc_err(BC_ERR_MATH_OVERFLOW); in bc_num_bigdig()
3689 // The conversion is easy because numbers are laid out in little-endian in bc_num_bigdig2num()
3691 for (ptr = n->num, i = 0; val; ++i, val /= BC_BASE_POW) in bc_num_bigdig2num()
3696 n->len = i; in bc_num_bigdig2num()
3713 // (manuals/development.md#pseudo-random-number-generator), so look there in bc_num_rng()
3718 bc_num_init(&temp, n->len); in bc_num_rng()
3719 bc_num_init(&temp2, n->len); in bc_num_rng()
3727 assert(BC_NUM_RDX_VALID_NP(vm->max)); in bc_num_rng()
3730 memcpy(frac.num, n->num, BC_NUM_SIZE(nrdx)); in bc_num_rng()
3733 frac.scale = n->scale; in bc_num_rng()
3736 assert(BC_NUM_RDX_VALID_NP(vm->max2)); in bc_num_rng()
3740 bc_num_mul(&frac, &vm->max2, &temp, 0); in bc_num_rng()
3746 memcpy(intn.num, n->num + nrdx, BC_NUM_SIZE(bc_num_int(n))); in bc_num_rng()
3751 assert(BC_NUM_NONZERO(&vm->max)); in bc_num_rng()
3757 bc_num_divmod(&frac, &vm->max, &temp, &temp2, 0); in bc_num_rng()
3759 // frac is guaranteed to be smaller than vm->max * vm->max (pow). in bc_num_rng()
3760 // This means that when dividing frac by vm->max, as above, the in bc_num_rng()
3761 // quotient and remainder are both guaranteed to be less than vm->max, in bc_num_rng()
3773 bc_num_divmod(&intn, &vm->max, &temp, &temp2, 0); in bc_num_rng()
3775 // Because temp2 is the mod of vm->max, from above, it is guaranteed in bc_num_rng()
3780 if (bc_num_cmp(&temp, &vm->max) >= 0) in bc_num_rng()
3783 bc_num_mod(&temp2, &vm->max, &temp, 0); in bc_num_rng()
3786 // The if statement above ensures that temp is less than vm->max, which in bc_num_rng()
3827 // the assumption that vm->max is not zero. in bc_num_createFromRNG()
3828 assert(BC_NUM_NONZERO(&vm->max)); in bc_num_createFromRNG()
3832 assert(BC_NUM_NONZERO(&vm->max2)); in bc_num_createFromRNG()
3842 bc_num_mul(&conv, &vm->max, &temp1, 0); in bc_num_createFromRNG()
3849 bc_num_div(&temp2, &vm->max2, &temp3, BC_RAND_STATE_BITS); in bc_num_createFromRNG()
3858 bc_num_mul(&conv, &vm->max, &temp1, 0); in bc_num_createFromRNG()
3889 // This is here in GCC to quiet the "maybe-uninitialized" warning. in bc_num_irand()
3903 len = atemp.len - 2; in bc_num_irand()
3912 b->num[i] = (BcDig) (dig % BC_BASE_POW); in bc_num_irand()
3913 b->num[i + 1] = (BcDig) (dig / BC_BASE_POW); in bc_num_irand()
3923 if (i == atemp.len - 2) in bc_num_irand()
3936 // needed to fill the second-to-last limb as well. in bc_num_irand()
3942 b->num[i - 1] = (BcDig) (dig % BC_BASE_POW); in bc_num_irand()
3943 b->num[i] = (BcDig) (dig / BC_BASE_POW); in bc_num_irand()
3947 b->len = atemp.len - (b->num[i] == 0); in bc_num_irand()
3954 b->num[i - 1] = (BcDig) bc_rand_bounded(rng, BC_BASE_POW); in bc_num_irand()
3955 b->len = atemp.len - 1; in bc_num_irand()
3964 b->num[i] = (BcDig) bc_rand_bounded(rng, (BcRand) atemp.num[i]); in bc_num_irand()
3965 b->len = atemp.len - (b->num[i] == 0); in bc_num_irand()
3967 else b->len = atemp.len - 1; in bc_num_irand()
3988 assert(aint <= a->len && ardx <= a->len); in bc_num_addReq()
3992 assert(bint <= b->len && brdx <= b->len); in bc_num_addReq()
4038 return bc_vm_growSize(bc_vm_growSize(a->len, b->len), 1); in bc_num_powReq()
4046 return a->len + b->len - BC_NUM_RDX_VAL(a) - BC_NUM_RDX_VAL(b); in bc_num_placesReq()
4145 if (a->scale > scale) realscale = a->scale; in bc_num_sqrt()
4166 assert(a->num != NULL && b->num != NULL); in bc_num_sqrt()
4186 len = bc_vm_growSize(a->len, rdx); in bc_num_sqrt()
4224 // An odd number is served by starting with 2^((pow-1)/2), and an even in bc_num_sqrt()
4225 // number is served by starting with 6^((pow-2)/2). Why? Because math. in bc_num_sqrt()
4226 if (pow & 1) x0->num[0] = 2; in bc_num_sqrt()
4227 else x0->num[0] = 6; in bc_num_sqrt()
4229 pow -= 2 - (pow & 1); in bc_num_sqrt()
4233 // I can set the rdx here directly because neg should be false. in bc_num_sqrt()
4234 x0->scale = x0->rdx = 0; in bc_num_sqrt()
4262 if (b->scale > realscale) bc_num_truncate(b, b->scale - realscale); in bc_num_sqrt()
4266 assert(BC_NUM_RDX_VAL(b) <= b->len || !b->len); in bc_num_sqrt()
4267 assert(!b->len || b->num[b->len - 1] || BC_NUM_RDX_VAL(b) == b->len); in bc_num_sqrt()
4294 ts = BC_MAX(scale + b->scale, a->scale); in bc_num_divmod()
4325 b->len == 1 && !scale) in bc_num_divmod()
4329 bc_num_divArray(ptr_a, (BcBigDig) b->num[0], c, &rem); in bc_num_divmod()
4333 d->num[0] = (BcDig) rem; in bc_num_divmod()
4334 d->len = (rem != 0); in bc_num_divmod()
4341 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len); in bc_num_divmod()
4342 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len); in bc_num_divmod()
4345 assert(BC_NUM_RDX_VAL(d) <= d->len || !d->len); in bc_num_divmod()
4346 assert(!d->len || d->num[d->len - 1] || BC_NUM_RDX_VAL(d) == d->len); in bc_num_divmod()
4374 // This is entirely for quieting a useless scan-build error. in bc_num_modexp()
4406 // If you know the algorithm I used, the memory-efficient method, then this in bc_num_modexp()
4407 // loop should be self-explanatory because it is the calculation loop. in bc_num_modexp()
4438 assert(!BC_NUM_NEG(d) || d->len); in bc_num_modexp()
4440 assert(!d->len || d->num[d->len - 1] || BC_NUM_RDX_VAL(d) == d->len); in bc_num_modexp()
4447 bc_file_puts(&vm->fout, bc_flush_none, name); in bc_num_printDebug()
4448 bc_file_puts(&vm->fout, bc_flush_none, ": "); in bc_num_printDebug()
4450 bc_file_putchar(&vm->fout, bc_flush_err, '\n'); in bc_num_printDebug()
4451 if (emptyline) bc_file_putchar(&vm->fout, bc_flush_err, '\n'); in bc_num_printDebug()
4452 vm->nchars = 0; in bc_num_printDebug()
4460 for (i = len - 1; i < len; --i) in bc_num_printDigs()
4462 bc_file_printf(&vm->fout, " %lu", (unsigned long) n[i]); in bc_num_printDigs()
4465 bc_file_putchar(&vm->fout, bc_flush_err, '\n'); in bc_num_printDigs()
4466 if (emptyline) bc_file_putchar(&vm->fout, bc_flush_err, '\n'); in bc_num_printDigs()
4467 vm->nchars = 0; in bc_num_printDigs()
4473 bc_file_puts(&vm->fout, bc_flush_none, name); in bc_num_printWithDigs()
4474 bc_file_printf(&vm->fout, " len: %zu, rdx: %zu, scale: %zu\n", name, n->len, in bc_num_printWithDigs()
4475 BC_NUM_RDX_VAL(n), n->scale); in bc_num_printWithDigs()
4476 bc_num_printDigs(n->num, n->len, emptyline); in bc_num_printWithDigs()
4482 ulong i, scale = n->scale; in bc_num_dump()
4484 bc_file_printf(&vm->ferr, "\n%s = %s", varname, in bc_num_dump()
4485 n->len ? (BC_NUM_NEG(n) ? "-" : "+") : "0 "); in bc_num_dump()
4487 for (i = n->len - 1; i < n->len; --i) in bc_num_dump()
4491 bc_file_puts(&vm->ferr, bc_flush_none, ". "); in bc_num_dump()
4494 if (scale / BC_BASE_DIGS != BC_NUM_RDX_VAL(n) - i - 1) in bc_num_dump()
4496 bc_file_printf(&vm->ferr, "%lu ", (unsigned long) n->num[i]); in bc_num_dump()
4501 int d = BC_BASE_DIGS - mod; in bc_num_dump()
4506 div = n->num[i] / ((BcDig) bc_num_pow10[(ulong) d]); in bc_num_dump()
4507 bc_file_printf(&vm->ferr, "%lu", (unsigned long) div); in bc_num_dump()
4510 div = n->num[i] % ((BcDig) bc_num_pow10[(ulong) d]); in bc_num_dump()
4511 bc_file_printf(&vm->ferr, " ' %lu ", (unsigned long) div); in bc_num_dump()
4515 bc_file_printf(&vm->ferr, "(%zu | %zu.%zu / %zu) %lu\n", n->scale, n->len, in bc_num_dump()
4516 BC_NUM_RDX_VAL(n), n->cap, (unsigned long) (void*) n->num); in bc_num_dump()
4518 bc_file_flush(&vm->ferr, bc_flush_err); in bc_num_dump()