xref: /freebsd/contrib/bc/src/num.c (revision 2e3f49888ec8851bafb22011533217487764fdb0)

/*
 * *****************************************************************************
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2018-2023 Gavin D. Howard and contributors.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * * Redistributions of source code must retain the above copyright notice, this
 *   list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * *****************************************************************************
 *
 * Code for the number type.
 *
 */

#include <assert.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>
#include <limits.h>

#include <num.h>
#include <rand.h>
#include <vm.h>
#if BC_ENABLE_LIBRARY
#include <library.h>
#endif // BC_ENABLE_LIBRARY

// Before you try to understand this code, see the development manual
// (manuals/development.md#numbers).

static void
bc_num_m(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale);

/**
 * Multiply two numbers and throw a math error if they overflow.
 * @param a  The first operand.
 * @param b  The second operand.
 * @return   The product of the two operands.
 */
static inline size_t
bc_num_mulOverflow(size_t a, size_t b)
{
	size_t res = a * b;
	if (BC_ERR(BC_VM_MUL_OVERFLOW(a, b, res))) bc_err(BC_ERR_MATH_OVERFLOW);
	return res;
}

/**
 * Conditionally negate @a n based on @a neg. Algorithm taken from
 * https://graphics.stanford.edu/~seander/bithacks.html#ConditionalNegate .
 * @param n    The value to turn into a signed value and negate.
 * @param neg  The condition to negate or not.
 */
static inline ssize_t
bc_num_neg(size_t n, bool neg)
{
	return (((ssize_t) n) ^ -((ssize_t) neg)) + neg;
}

/**
 * Compare a BcNum against zero.
 * @param n  The number to compare.
 * @return   -1 if the number is less than 0, 1 if greater, and 0 if equal.
 */
ssize_t
bc_num_cmpZero(const BcNum* n)
{
	return bc_num_neg((n)->len != 0, BC_NUM_NEG(n));
}

/**
 * Return the number of integer limbs in a BcNum. This is the opposite of rdx.
 * @param n  The number to return the amount of integer limbs for.
 * @return   The amount of integer limbs in @a n.
 */
static inline size_t
bc_num_int(const BcNum* n)
{
	return n->len ? n->len - BC_NUM_RDX_VAL(n) : 0;
}

/**
 * Expand a number's allocation capacity to at least req limbs.
 * @param n    The number to expand.
 * @param req  The number limbs to expand the allocation capacity to.
 */
static void
bc_num_expand(BcNum* restrict n, size_t req)
{
	assert(n != NULL);

	req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;

	if (req > n->cap)
	{
		BC_SIG_LOCK;

		n->num = bc_vm_realloc(n->num, BC_NUM_SIZE(req));
		n->cap = req;

		BC_SIG_UNLOCK;
	}
}

/**
 * Set a number to 0 with the specified scale.
 * @param n      The number to set to zero.
 * @param scale  The scale to set the number to.
 */
static inline void
bc_num_setToZero(BcNum* restrict n, size_t scale)
{
	assert(n != NULL);
	n->scale = scale;
	n->len = n->rdx = 0;
}

void
bc_num_zero(BcNum* restrict n)
{
	bc_num_setToZero(n, 0);
}

void
bc_num_one(BcNum* restrict n)
{
	bc_num_zero(n);
	n->len = 1;
	n->num[0] = 1;
}

/**
 * "Cleans" a number, which means reducing the length if the most significant
 * limbs are zero.
 * @param n  The number to clean.
 */
static void
bc_num_clean(BcNum* restrict n)
{
	// Reduce the length.
	while (BC_NUM_NONZERO(n) && !n->num[n->len - 1])
	{
		n->len -= 1;
	}

	// Special cases.
	if (BC_NUM_ZERO(n)) n->rdx = 0;
	else
	{
		// len must be at least as much as rdx.
		size_t rdx = BC_NUM_RDX_VAL(n);
		if (n->len < rdx) n->len = rdx;
	}
}

/**
 * Returns the log base 10 of @a i. I could have done this with floating-point
 * math, and in fact, I originally did. However, that was the only
 * floating-point code in the entire codebase, and I decided I didn't want any.
 * This is fast enough. Also, it might handle larger numbers better.
 * @param i  The number to return the log base 10 of.
 * @return   The log base 10 of @a i.
 */
static size_t
bc_num_log10(size_t i)
{
	size_t len;

	for (len = 1; i; i /= BC_BASE, ++len)
	{
		continue;
	}

	assert(len - 1 <= BC_BASE_DIGS + 1);

	return len - 1;
}

/**
 * Returns the number of decimal digits in a limb that are zero starting at the
 * most significant digits. This basically returns how much of the limb is used.
 * @param n  The number.
 * @return   The number of decimal digits that are 0 starting at the most
 *           significant digits.
 */
static inline size_t
bc_num_zeroDigits(const BcDig* n)
{
	assert(*n >= 0);
	assert(((size_t) *n) < BC_BASE_POW);
	return BC_BASE_DIGS - bc_num_log10((size_t) *n);
}

/**
 * Return the total number of integer digits in a number. This is the opposite
 * of scale, like bc_num_int() is the opposite of rdx.
 * @param n  The number.
 * @return   The number of integer digits in @a n.
 */
static size_t
bc_num_intDigits(const BcNum* n)
{
	size_t digits = bc_num_int(n) * BC_BASE_DIGS;
	if (digits > 0) digits -= bc_num_zeroDigits(n->num + n->len - 1);
	return digits;
}

/**
 * Returns the number of limbs of a number that are non-zero starting at the
 * most significant limbs. This expects that there are *no* integer limbs in the
 * number because it is specifically to figure out how many zero limbs after the
 * decimal place to ignore. If there are zero limbs after non-zero limbs, they
 * are counted as non-zero limbs.
 * @param n  The number.
 * @return   The number of non-zero limbs after the decimal point.
 */
static size_t
bc_num_nonZeroLen(const BcNum* restrict n)
{
	size_t i, len = n->len;

	assert(len == BC_NUM_RDX_VAL(n));

	for (i = len - 1; i < len && !n->num[i]; --i)
	{
		continue;
	}

	assert(i + 1 > 0);

	return i + 1;
}

/**
 * Performs a one-limb add with a carry.
 * @param a      The first limb.
 * @param b      The second limb.
 * @param carry  An in/out parameter; the carry in from the previous add and the
 *               carry out from this add.
 * @return       The resulting limb sum.
 */
static BcDig
bc_num_addDigits(BcDig a, BcDig b, bool* carry)
{
	assert(((BcBigDig) BC_BASE_POW) * 2 == ((BcDig) BC_BASE_POW) * 2);
	assert(a < BC_BASE_POW && a >= 0);
	assert(b < BC_BASE_POW && b >= 0);

	a += b + *carry;
	*carry = (a >= BC_BASE_POW);
	if (*carry) a -= BC_BASE_POW;

	assert(a >= 0);
	assert(a < BC_BASE_POW);

	return a;
}

/**
 * Performs a one-limb subtract with a carry.
 * @param a      The first limb.
 * @param b      The second limb.
 * @param carry  An in/out parameter; the carry in from the previous subtract
 *               and the carry out from this subtract.
 * @return       The resulting limb difference.
 */
static BcDig
bc_num_subDigits(BcDig a, BcDig b, bool* carry)
{
	assert(a < BC_BASE_POW && a >= 0);
	assert(b < BC_BASE_POW && b >= 0);

	b += *carry;
	*carry = (a < b);
	if (*carry) a += BC_BASE_POW;

	assert(a - b >= 0);
	assert(a - b < BC_BASE_POW);

	return a - b;
}

/**
 * Add two BcDig arrays and store the result in the first array.
 * @param a    The first operand and out array.
 * @param b    The second operand.
 * @param len  The length of @a b.
 */
static void
bc_num_addArrays(BcDig* restrict a, const BcDig* restrict b, size_t len)
{
	size_t i;
	bool carry = false;

	for (i = 0; i < len; ++i)
	{
		a[i] = bc_num_addDigits(a[i], b[i], &carry);
	}

	// Take care of the extra limbs in the bigger array.
	for (; carry; ++i)
	{
		a[i] = bc_num_addDigits(a[i], 0, &carry);
	}
}

/**
 * Subtract two BcDig arrays and store the result in the first array.
 * @param a    The first operand and out array.
 * @param b    The second operand.
 * @param len  The length of @a b.
 */
static void
bc_num_subArrays(BcDig* restrict a, const BcDig* restrict b, size_t len)
{
	size_t i;
	bool carry = false;

	for (i = 0; i < len; ++i)
	{
		a[i] = bc_num_subDigits(a[i], b[i], &carry);
	}

	// Take care of the extra limbs in the bigger array.
	for (; carry; ++i)
	{
		a[i] = bc_num_subDigits(a[i], 0, &carry);
	}
}

/**
 * Multiply a BcNum array by a one-limb number. This is a faster version of
 * multiplication for when we can use it.
 * @param a  The BcNum to multiply by the one-limb number.
 * @param b  The one limb of the one-limb number.
 * @param c  The return parameter.
 */
static void
bc_num_mulArray(const BcNum* restrict a, BcBigDig b, BcNum* restrict c)
{
	size_t i;
	BcBigDig carry = 0;

	assert(b <= BC_BASE_POW);

	// Make sure the return parameter is big enough.
	if (a->len + 1 > c->cap) bc_num_expand(c, a->len + 1);

	// We want the entire return parameter to be zero for cleaning later.
	// NOLINTNEXTLINE
	memset(c->num, 0, BC_NUM_SIZE(c->cap));

	// Actual multiplication loop.
	for (i = 0; i < a->len; ++i)
	{
		BcBigDig in = ((BcBigDig) a->num[i]) * b + carry;
		c->num[i] = in % BC_BASE_POW;
		carry = in / BC_BASE_POW;
	}

	assert(carry < BC_BASE_POW);

	// Finishing touches.
	c->num[i] = (BcDig) carry;
	assert(c->num[i] >= 0 && c->num[i] < BC_BASE_POW);
	c->len = a->len;
	c->len += (carry != 0);

	bc_num_clean(c);

	// Postconditions.
	assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
	assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
	assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);
}

/**
 * Divide a BcNum array by a one-limb number. This is a faster version of divide
 * for when we can use it.
 * @param a    The BcNum to multiply by the one-limb number.
 * @param b    The one limb of the one-limb number.
 * @param c    The return parameter for the quotient.
 * @param rem  The return parameter for the remainder.
 */
static void
bc_num_divArray(const BcNum* restrict a, BcBigDig b, BcNum* restrict c,
                BcBigDig* rem)
{
	size_t i;
	BcBigDig carry = 0;

	assert(c->cap >= a->len);

	// Actual division loop.
	for (i = a->len - 1; i < a->len; --i)
	{
		BcBigDig in = ((BcBigDig) a->num[i]) + carry * BC_BASE_POW;
		assert(in / b < BC_BASE_POW);
		c->num[i] = (BcDig) (in / b);
		assert(c->num[i] >= 0 && c->num[i] < BC_BASE_POW);
		carry = in % b;
	}

	// Finishing touches.
	c->len = a->len;
	bc_num_clean(c);
	*rem = carry;

	// Postconditions.
	assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
	assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
	assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);
}

/**
 * Compare two BcDig arrays and return >0 if @a b is greater, <0 if @a b is
 * less, and 0 if equal. Both @a a and @a b must have the same length.
 * @param a    The first array.
 * @param b    The second array.
 * @param len  The minimum length of the arrays.
 */
static ssize_t
bc_num_compare(const BcDig* restrict a, const BcDig* restrict b, size_t len)
{
	size_t i;
	BcDig c = 0;
	for (i = len - 1; i < len && !(c = a[i] - b[i]); --i)
	{
		continue;
	}
	return bc_num_neg(i + 1, c < 0);
}

ssize_t
bc_num_cmp(const BcNum* a, const BcNum* b)
{
	size_t i, min, a_int, b_int, diff, ardx, brdx;
	BcDig* max_num;
	BcDig* min_num;
	bool a_max, neg = false;
	ssize_t cmp;

	assert(a != NULL && b != NULL);

	// Same num? Equal.
	if (a == b) return 0;

	// Easy cases.
	if (BC_NUM_ZERO(a)) return bc_num_neg(b->len != 0, !BC_NUM_NEG(b));
	if (BC_NUM_ZERO(b)) return bc_num_cmpZero(a);
	if (BC_NUM_NEG(a))
	{
		if (BC_NUM_NEG(b)) neg = true;
		else return -1;
	}
	else if (BC_NUM_NEG(b)) return 1;

	// Get the number of int limbs in each number and get the difference.
	a_int = bc_num_int(a);
	b_int = bc_num_int(b);
	a_int -= b_int;

	// If there's a difference, then just return the comparison.
	if (a_int) return neg ? -((ssize_t) a_int) : (ssize_t) a_int;

	// Get the rdx's and figure out the max.
	ardx = BC_NUM_RDX_VAL(a);
	brdx = BC_NUM_RDX_VAL(b);
	a_max = (ardx > brdx);

	// Set variables based on the above.
	if (a_max)
	{
		min = brdx;
		diff = ardx - brdx;
		max_num = a->num + diff;
		min_num = b->num;
	}
	else
	{
		min = ardx;
		diff = brdx - ardx;
		max_num = b->num + diff;
		min_num = a->num;
	}

	// Do a full limb-by-limb comparison.
	cmp = bc_num_compare(max_num, min_num, b_int + min);

	// If we found a difference, return it based on state.
	if (cmp) return bc_num_neg((size_t) cmp, !a_max == !neg);

	// If there was no difference, then the final step is to check which number
	// has greater or lesser limbs beyond the other's.
	for (max_num -= diff, i = diff - 1; i < diff; --i)
	{
		if (max_num[i]) return bc_num_neg(1, !a_max == !neg);
	}

	return 0;
}

void
bc_num_truncate(BcNum* restrict n, size_t places)
{
	size_t nrdx, places_rdx;

	if (!places) return;

	// Grab these needed values; places_rdx is the rdx equivalent to places like
	// rdx is to scale.
	nrdx = BC_NUM_RDX_VAL(n);
	places_rdx = nrdx ? nrdx - BC_NUM_RDX(n->scale - places) : 0;

	// We cannot truncate more places than we have.
	assert(places <= n->scale && (BC_NUM_ZERO(n) || places_rdx <= n->len));

	n->scale -= places;
	BC_NUM_RDX_SET(n, nrdx - places_rdx);

	// Only when the number is nonzero do we need to do the hard stuff.
	if (BC_NUM_NONZERO(n))
	{
		size_t pow;

		// This calculates how many decimal digits are in the least significant
		// limb.
		pow = n->scale % BC_BASE_DIGS;
		pow = pow ? BC_BASE_DIGS - pow : 0;
		pow = bc_num_pow10[pow];

		n->len -= places_rdx;

		// We have to move limbs to maintain invariants. The limbs must begin at
		// the beginning of the BcNum array.
		// NOLINTNEXTLINE
		memmove(n->num, n->num + places_rdx, BC_NUM_SIZE(n->len));

		// Clear the lower part of the last digit.
		if (BC_NUM_NONZERO(n)) n->num[0] -= n->num[0] % (BcDig) pow;

		bc_num_clean(n);
	}
}

void
bc_num_extend(BcNum* restrict n, size_t places)
{
	size_t nrdx, places_rdx;

	if (!places) return;

	// Easy case with zero; set the scale.
	if (BC_NUM_ZERO(n))
	{
		n->scale += places;
		return;
	}

	// Grab these needed values; places_rdx is the rdx equivalent to places like
	// rdx is to scale.
	nrdx = BC_NUM_RDX_VAL(n);
	places_rdx = BC_NUM_RDX(places + n->scale) - nrdx;

	// This is the hard case. We need to expand the number, move the limbs, and
	// set the limbs that were just cleared.
	if (places_rdx)
	{
		bc_num_expand(n, bc_vm_growSize(n->len, places_rdx));
		// NOLINTNEXTLINE
		memmove(n->num + places_rdx, n->num, BC_NUM_SIZE(n->len));
		// NOLINTNEXTLINE
		memset(n->num, 0, BC_NUM_SIZE(places_rdx));
	}

	// Finally, set scale and rdx.
	BC_NUM_RDX_SET(n, nrdx + places_rdx);
	n->scale += places;
	n->len += places_rdx;

	assert(BC_NUM_RDX_VAL(n) == BC_NUM_RDX(n->scale));
}

/**
 * Retires (finishes) a multiplication or division operation.
 */
static void
bc_num_retireMul(BcNum* restrict n, size_t scale, bool neg1, bool neg2)
{
	// Make sure scale is correct.
	if (n->scale < scale) bc_num_extend(n, scale - n->scale);
	else bc_num_truncate(n, n->scale - scale);

	bc_num_clean(n);

	// We need to ensure rdx is correct.
	if (BC_NUM_NONZERO(n)) n->rdx = BC_NUM_NEG_VAL(n, !neg1 != !neg2);
}

/**
 * Splits a number into two BcNum's. This is used in Karatsuba.
 * @param n    The number to split.
 * @param idx  The index to split at.
 * @param a    An out parameter; the low part of @a n.
 * @param b    An out parameter; the high part of @a n.
 */
static void
bc_num_split(const BcNum* restrict n, size_t idx, BcNum* restrict a,
             BcNum* restrict b)
{
	// We want a and b to be clear.
	assert(BC_NUM_ZERO(a));
	assert(BC_NUM_ZERO(b));

	// The usual case.
	if (idx < n->len)
	{
		// Set the fields first.
		b->len = n->len - idx;
		a->len = idx;
		a->scale = b->scale = 0;
		BC_NUM_RDX_SET(a, 0);
		BC_NUM_RDX_SET(b, 0);

		assert(a->cap >= a->len);
		assert(b->cap >= b->len);

		// Copy the arrays. This is not necessary for safety, but it is faster,
		// for some reason.
		// NOLINTNEXTLINE
		memcpy(b->num, n->num + idx, BC_NUM_SIZE(b->len));
		// NOLINTNEXTLINE
		memcpy(a->num, n->num, BC_NUM_SIZE(idx));

		bc_num_clean(b);
	}
	// If the index is weird, just skip the split.
	else bc_num_copy(a, n);

	bc_num_clean(a);
}

/**
 * Copies a number into another, but shifts the rdx so that the result number
 * only sees the integer part of the source number.
 * @param n  The number to copy.
 * @param r  The result number with a shifted rdx, len, and num.
 */
static void
bc_num_shiftRdx(const BcNum* restrict n, BcNum* restrict r)
{
	size_t rdx = BC_NUM_RDX_VAL(n);

	r->len = n->len - rdx;
	r->cap = n->cap - rdx;
	r->num = n->num + rdx;

	BC_NUM_RDX_SET_NEG(r, 0, BC_NUM_NEG(n));
	r->scale = 0;
}

/**
 * Shifts a number so that all of the least significant limbs of the number are
 * skipped. This must be undone by bc_num_unshiftZero().
 * @param n  The number to shift.
 */
static size_t
bc_num_shiftZero(BcNum* restrict n)
{
	// This is volatile to quiet a GCC warning about longjmp() clobbering.
	volatile size_t i;

	// If we don't have an integer, that is a problem, but it's also a bug
	// because the caller should have set everything up right.
	assert(!BC_NUM_RDX_VAL(n) || BC_NUM_ZERO(n));

	for (i = 0; i < n->len && !n->num[i]; ++i)
	{
		continue;
	}

	n->len -= i;
	n->num += i;

	return i;
}

/**
 * Undo the damage done by bc_num_unshiftZero(). This must be called like all
 * cleanup functions: after a label used by setjmp() and longjmp().
 * @param n           The number to unshift.
 * @param places_rdx  The amount the number was originally shift.
 */
static void
bc_num_unshiftZero(BcNum* restrict n, size_t places_rdx)
{
	n->len += places_rdx;
	n->num -= places_rdx;
}

/**
 * Shifts the digits right within a number by no more than BC_BASE_DIGS - 1.
 * This is the final step on shifting numbers with the shift operators. It
 * depends on the caller to shift the limbs properly because all it does is
 * ensure that the rdx point is realigned to be between limbs.
 * @param n    The number to shift digits in.
 * @param dig  The number of places to shift right.
 */
static void
bc_num_shift(BcNum* restrict n, BcBigDig dig)
{
	size_t i, len = n->len;
	BcBigDig carry = 0, pow;
	BcDig* ptr = n->num;

	assert(dig < BC_BASE_DIGS);

	// Figure out the parameters for division.
	pow = bc_num_pow10[dig];
	dig = bc_num_pow10[BC_BASE_DIGS - dig];

	// Run a series of divisions and mods with carries across the entire number
	// array. This effectively shifts everything over.
	for (i = len - 1; i < len; --i)
	{
		BcBigDig in, temp;
		in = ((BcBigDig) ptr[i]);
		temp = carry * dig;
		carry = in % pow;
		ptr[i] = ((BcDig) (in / pow)) + (BcDig) temp;
		assert(ptr[i] >= 0 && ptr[i] < BC_BASE_POW);
	}

	assert(!carry);
}

/**
 * Shift a number left by a certain number of places. This is the workhorse of
 * the left shift operator.
 * @param n       The number to shift left.
 * @param places  The amount of places to shift @a n left by.
 */
static void
bc_num_shiftLeft(BcNum* restrict n, size_t places)
{
	BcBigDig dig;
	size_t places_rdx;
	bool shift;

	if (!places) return;

	// Make sure to grow the number if necessary.
	if (places > n->scale)
	{
		size_t size = bc_vm_growSize(BC_NUM_RDX(places - n->scale), n->len);
		if (size > SIZE_MAX - 1) bc_err(BC_ERR_MATH_OVERFLOW);
	}

	// If zero, we can just set the scale and bail.
	if (BC_NUM_ZERO(n))
	{
		if (n->scale >= places) n->scale -= places;
		else n->scale = 0;
		return;
	}

	// When I changed bc to have multiple digits per limb, this was the hardest
	// code to change. This and shift right. Make sure you understand this
	// before attempting anything.

	// This is how many limbs we will shift.
	dig = (BcBigDig) (places % BC_BASE_DIGS);
	shift = (dig != 0);

	// Convert places to a rdx value.
	places_rdx = BC_NUM_RDX(places);

	// If the number is not an integer, we need special care. The reason an
	// integer doesn't is because left shift would only extend the integer,
	// whereas a non-integer might have its fractional part eliminated or only
	// partially eliminated.
	if (n->scale)
	{
		size_t nrdx = BC_NUM_RDX_VAL(n);

		// If the number's rdx is bigger, that's the hard case.
		if (nrdx >= places_rdx)
		{
			size_t mod = n->scale % BC_BASE_DIGS, revdig;

			// We want mod to be in the range [1, BC_BASE_DIGS], not
			// [0, BC_BASE_DIGS).
			mod = mod ? mod : BC_BASE_DIGS;

			// We need to reverse dig to get the actual number of digits.
			revdig = dig ? BC_BASE_DIGS - dig : 0;

			// If the two overflow BC_BASE_DIGS, we need to move an extra place.
			if (mod + revdig > BC_BASE_DIGS) places_rdx = 1;
			else places_rdx = 0;
		}
		else places_rdx -= nrdx;
	}

	// If this is non-zero, we need an extra place, so expand, move, and set.
	if (places_rdx)
	{
		bc_num_expand(n, bc_vm_growSize(n->len, places_rdx));
		// NOLINTNEXTLINE
		memmove(n->num + places_rdx, n->num, BC_NUM_SIZE(n->len));
		// NOLINTNEXTLINE
		memset(n->num, 0, BC_NUM_SIZE(places_rdx));
		n->len += places_rdx;
	}

	// Set the scale appropriately.
	if (places > n->scale)
	{
		n->scale = 0;
		BC_NUM_RDX_SET(n, 0);
	}
	else
	{
		n->scale -= places;
		BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale));
	}

	// Finally, shift within limbs.
	if (shift) bc_num_shift(n, BC_BASE_DIGS - dig);

	bc_num_clean(n);
}

void
bc_num_shiftRight(BcNum* restrict n, size_t places)
{
	BcBigDig dig;
	size_t places_rdx, scale, scale_mod, int_len, expand;
	bool shift;

	if (!places) return;

	// If zero, we can just set the scale and bail.
	if (BC_NUM_ZERO(n))
	{
		n->scale += places;
		bc_num_expand(n, BC_NUM_RDX(n->scale));
		return;
	}

	// Amount within a limb we have to shift by.
	dig = (BcBigDig) (places % BC_BASE_DIGS);
	shift = (dig != 0);

	scale = n->scale;

	// Figure out how the scale is affected.
	scale_mod = scale % BC_BASE_DIGS;
	scale_mod = scale_mod ? scale_mod : BC_BASE_DIGS;

	// We need to know the int length and rdx for places.
	int_len = bc_num_int(n);
	places_rdx = BC_NUM_RDX(places);

	// If we are going to shift past a limb boundary or not, set accordingly.
	if (scale_mod + dig > BC_BASE_DIGS)
	{
		expand = places_rdx - 1;
		places_rdx = 1;
	}
	else
	{
		expand = places_rdx;
		places_rdx = 0;
	}

	// Clamp expanding.
	if (expand > int_len) expand -= int_len;
	else expand = 0;

	// Extend, expand, and zero.
	bc_num_extend(n, places_rdx * BC_BASE_DIGS);
	bc_num_expand(n, bc_vm_growSize(expand, n->len));
	// NOLINTNEXTLINE
	memset(n->num + n->len, 0, BC_NUM_SIZE(expand));

	// Set the fields.
	n->len += expand;
	n->scale = 0;
	BC_NUM_RDX_SET(n, 0);

	// Finally, shift within limbs.
	if (shift) bc_num_shift(n, dig);

	n->scale = scale + places;
	BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale));

	bc_num_clean(n);

	assert(BC_NUM_RDX_VAL(n) <= n->len && n->len <= n->cap);
	assert(BC_NUM_RDX_VAL(n) == BC_NUM_RDX(n->scale));
}

/**
 * Tests if a number is a integer with scale or not. Returns true if the number
 * is not an integer. If it is, its integer shifted form is copied into the
 * result parameter for use where only integers are allowed.
 * @param n  The integer to test and shift.
 * @param r  The number to store the shifted result into. This number should
 *           *not* be allocated.
 * @return   True if the number is a non-integer, false otherwise.
 */
static bool
bc_num_nonInt(const BcNum* restrict n, BcNum* restrict r)
{
	bool zero;
	size_t i, rdx = BC_NUM_RDX_VAL(n);

	if (!rdx)
	{
		// NOLINTNEXTLINE
		memcpy(r, n, sizeof(BcNum));
		return false;
	}

	zero = true;

	for (i = 0; zero && i < rdx; ++i)
	{
		zero = (n->num[i] == 0);
	}

	if (BC_ERR(!zero)) return true;

	bc_num_shiftRdx(n, r);

	return false;
}

#if BC_ENABLE_EXTRA_MATH

/**
 * Execute common code for an operater that needs an integer for the second
 * operand and return the integer operand as a BcBigDig.
 * @param a  The first operand.
 * @param b  The second operand.
 * @param c  The result operand.
 * @return   The second operand as a hardware integer.
 */
static BcBigDig
bc_num_intop(const BcNum* a, const BcNum* b, BcNum* restrict c)
{
	BcNum temp;

#if BC_GCC
	temp.len = 0;
	temp.rdx = 0;
	temp.num = NULL;
#endif // BC_GCC

	if (BC_ERR(bc_num_nonInt(b, &temp))) bc_err(BC_ERR_MATH_NON_INTEGER);

	bc_num_copy(c, a);

	return bc_num_bigdig(&temp);
}
#endif // BC_ENABLE_EXTRA_MATH

/**
 * This is the actual implementation of add *and* subtract. Since this function
 * doesn't need to use scale (per the bc spec), I am hijacking it to say whether
 * it's doing an add or a subtract. And then I convert substraction to addition
 * of negative second operand. This is a BcNumBinOp function.
 * @param a    The first operand.
 * @param b    The second operand.
 * @param c    The return parameter.
 * @param sub  Non-zero for a subtract, zero for an add.
 */
static void
bc_num_as(BcNum* a, BcNum* b, BcNum* restrict c, size_t sub)
{
	BcDig* ptr_c;
	BcDig* ptr_l;
	BcDig* ptr_r;
	size_t i, min_rdx, max_rdx, diff, a_int, b_int, min_len, max_len, max_int;
	size_t len_l, len_r, ardx, brdx;
	bool b_neg, do_sub, do_rev_sub, carry, c_neg;

	if (BC_NUM_ZERO(b))
	{
		bc_num_copy(c, a);
		return;
	}

	if (BC_NUM_ZERO(a))
	{
		bc_num_copy(c, b);
		c->rdx = BC_NUM_NEG_VAL(c, BC_NUM_NEG(b) != sub);
		return;
	}

	// Invert sign of b if it is to be subtracted. This operation must
	// precede the tests for any of the operands being zero.
	b_neg = (BC_NUM_NEG(b) != sub);

	// Figure out if we will actually add the numbers if their signs are equal
	// or subtract.
	do_sub = (BC_NUM_NEG(a) != b_neg);

	a_int = bc_num_int(a);
	b_int = bc_num_int(b);
	max_int = BC_MAX(a_int, b_int);

	// Figure out which number will have its last limbs copied (for addition) or
	// subtracted (for subtraction).
	ardx = BC_NUM_RDX_VAL(a);
	brdx = BC_NUM_RDX_VAL(b);
	min_rdx = BC_MIN(ardx, brdx);
	max_rdx = BC_MAX(ardx, brdx);
	diff = max_rdx - min_rdx;

	max_len = max_int + max_rdx;

	if (do_sub)
	{
		// Check whether b has to be subtracted from a or a from b.
		if (a_int != b_int) do_rev_sub = (a_int < b_int);
		else if (ardx > brdx)
		{
			do_rev_sub = (bc_num_compare(a->num + diff, b->num, b->len) < 0);
		}
		else do_rev_sub = (bc_num_compare(a->num, b->num + diff, a->len) <= 0);
	}
	else
	{
		// The result array of the addition might come out one element
		// longer than the bigger of the operand arrays.
		max_len += 1;
		do_rev_sub = (a_int < b_int);
	}

	assert(max_len <= c->cap);

	// Cache values for simple code later.
	if (do_rev_sub)
	{
		ptr_l = b->num;
		ptr_r = a->num;
		len_l = b->len;
		len_r = a->len;
	}
	else
	{
		ptr_l = a->num;
		ptr_r = b->num;
		len_l = a->len;
		len_r = b->len;
	}

	ptr_c = c->num;
	carry = false;

	// This is true if the numbers have a different number of limbs after the
	// decimal point.
	if (diff)
	{
		// If the rdx values of the operands do not match, the result will
		// have low end elements that are the positive or negative trailing
		// elements of the operand with higher rdx value.
		if ((ardx > brdx) != do_rev_sub)
		{
			// !do_rev_sub && ardx > brdx || do_rev_sub && brdx > ardx
			// The left operand has BcDig values that need to be copied,
			// either from a or from b (in case of a reversed subtraction).
			// NOLINTNEXTLINE
			memcpy(ptr_c, ptr_l, BC_NUM_SIZE(diff));
			ptr_l += diff;
			len_l -= diff;
		}
		else
		{
			// The right operand has BcDig values that need to be copied
			// or subtracted from zero (in case of a subtraction).
			if (do_sub)
			{
				// do_sub (do_rev_sub && ardx > brdx ||
				// !do_rev_sub && brdx > ardx)
				for (i = 0; i < diff; i++)
				{
					ptr_c[i] = bc_num_subDigits(0, ptr_r[i], &carry);
				}
			}
			else
			{
				// !do_sub && brdx > ardx
				// NOLINTNEXTLINE
				memcpy(ptr_c, ptr_r, BC_NUM_SIZE(diff));
			}

			// Future code needs to ignore the limbs we just did.
			ptr_r += diff;
			len_r -= diff;
		}

		// The return value pointer needs to ignore what we just did.
		ptr_c += diff;
	}

	// This is the length that can be directly added/subtracted.
	min_len = BC_MIN(len_l, len_r);

	// After dealing with possible low array elements that depend on only one
	// operand above, the actual add or subtract can be performed as if the rdx
	// of both operands was the same.
	//
	// Inlining takes care of eliminating constant zero arguments to
	// addDigit/subDigit (checked in disassembly of resulting bc binary
	// compiled with gcc and clang).
	if (do_sub)
	{
		// Actual subtraction.
		for (i = 0; i < min_len; ++i)
		{
			ptr_c[i] = bc_num_subDigits(ptr_l[i], ptr_r[i], &carry);
		}

		// Finishing the limbs beyond the direct subtraction.
		for (; i < len_l; ++i)
		{
			ptr_c[i] = bc_num_subDigits(ptr_l[i], 0, &carry);
		}
	}
	else
	{
		// Actual addition.
		for (i = 0; i < min_len; ++i)
		{
			ptr_c[i] = bc_num_addDigits(ptr_l[i], ptr_r[i], &carry);
		}

		// Finishing the limbs beyond the direct addition.
		for (; i < len_l; ++i)
		{
			ptr_c[i] = bc_num_addDigits(ptr_l[i], 0, &carry);
		}

		// Addition can create an extra limb. We take care of that here.
		ptr_c[i] = bc_num_addDigits(0, 0, &carry);
	}

	assert(carry == false);

	// The result has the same sign as a, unless the operation was a
	// reverse subtraction (b - a).
	c_neg = BC_NUM_NEG(a) != (do_sub && do_rev_sub);
	BC_NUM_RDX_SET_NEG(c, max_rdx, c_neg);
	c->len = max_len;
	c->scale = BC_MAX(a->scale, b->scale);

	bc_num_clean(c);
}

/**
 * The simple multiplication that karatsuba dishes out to when the length of the
 * numbers gets low enough. This doesn't use scale because it treats the
 * operands as though they are integers.
 * @param a  The first operand.
 * @param b  The second operand.
 * @param c  The return parameter.
 */
static void
bc_num_m_simp(const BcNum* a, const BcNum* b, BcNum* restrict c)
{
	size_t i, alen = a->len, blen = b->len, clen;
	BcDig* ptr_a = a->num;
	BcDig* ptr_b = b->num;
	BcDig* ptr_c;
	BcBigDig sum = 0, carry = 0;

	assert(sizeof(sum) >= sizeof(BcDig) * 2);
	assert(!BC_NUM_RDX_VAL(a) && !BC_NUM_RDX_VAL(b));

	// Make sure c is big enough.
	clen = bc_vm_growSize(alen, blen);
	bc_num_expand(c, bc_vm_growSize(clen, 1));

	// If we don't memset, then we might have uninitialized data use later.
	ptr_c = c->num;
	// NOLINTNEXTLINE
	memset(ptr_c, 0, BC_NUM_SIZE(c->cap));

	// This is the actual multiplication loop. It uses the lattice form of long
	// multiplication (see the explanation on the web page at
	// https://knilt.arcc.albany.edu/What_is_Lattice_Multiplication or the
	// explanation at Wikipedia).
	for (i = 0; i < clen; ++i)
	{
		ssize_t sidx = (ssize_t) (i - blen + 1);
		size_t j, k;

		// These are the start indices.
		j = (size_t) BC_MAX(0, sidx);
		k = BC_MIN(i, blen - 1);

		// On every iteration of this loop, a multiplication happens, then the
		// sum is automatically calculated.
		for (; j < alen && k < blen; ++j, --k)
		{
			sum += ((BcBigDig) ptr_a[j]) * ((BcBigDig) ptr_b[k]);

			if (sum >= ((BcBigDig) BC_BASE_POW) * BC_BASE_POW)
			{
				carry += sum / BC_BASE_POW;
				sum %= BC_BASE_POW;
			}
		}

		// Calculate the carry.
		if (sum >= BC_BASE_POW)
		{
			carry += sum / BC_BASE_POW;
			sum %= BC_BASE_POW;
		}

		// Store and set up for next iteration.
		ptr_c[i] = (BcDig) sum;
		assert(ptr_c[i] < BC_BASE_POW);
		sum = carry;
		carry = 0;
	}

	// This should always be true because there should be no carry on the last
	// digit; multiplication never goes above the sum of both lengths.
	assert(!sum);

	c->len = clen;
}

/**
 * Does a shifted add or subtract for Karatsuba below. This calls either
 * bc_num_addArrays() or bc_num_subArrays().
 * @param n      An in/out parameter; the first operand and return parameter.
 * @param a      The second operand.
 * @param shift  The amount to shift @a n by when adding/subtracting.
 * @param op     The function to call, either bc_num_addArrays() or
 *               bc_num_subArrays().
 */
static void
bc_num_shiftAddSub(BcNum* restrict n, const BcNum* restrict a, size_t shift,
                   BcNumShiftAddOp op)
{
	assert(n->len >= shift + a->len);
	assert(!BC_NUM_RDX_VAL(n) && !BC_NUM_RDX_VAL(a));
	op(n->num + shift, a->num, a->len);
}

/**
 * Implements the Karatsuba algorithm.
 */
static void
bc_num_k(const BcNum* a, const BcNum* b, BcNum* restrict c)
{
	size_t max, max2, total;
	BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp;
	BcDig* digs;
	BcDig* dig_ptr;
	BcNumShiftAddOp op;
	bool aone = BC_NUM_ONE(a);
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	assert(BC_NUM_ZERO(c));

	if (BC_NUM_ZERO(a) || BC_NUM_ZERO(b)) return;

	if (aone || BC_NUM_ONE(b))
	{
		bc_num_copy(c, aone ? b : a);
		if ((aone && BC_NUM_NEG(a)) || BC_NUM_NEG(b)) BC_NUM_NEG_TGL(c);
		return;
	}

	// Shell out to the simple algorithm with certain conditions.
	if (a->len < BC_NUM_KARATSUBA_LEN || b->len < BC_NUM_KARATSUBA_LEN)
	{
		bc_num_m_simp(a, b, c);
		return;
	}

	// We need to calculate the max size of the numbers that can result from the
	// operations.
	max = BC_MAX(a->len, b->len);
	max = BC_MAX(max, BC_NUM_DEF_SIZE);
	max2 = (max + 1) / 2;

	// Calculate the space needed for all of the temporary allocations. We do
	// this to just allocate once.
	total = bc_vm_arraySize(BC_NUM_KARATSUBA_ALLOCS, max);

	BC_SIG_LOCK;

	// Allocate space for all of the temporaries.
	digs = dig_ptr = bc_vm_malloc(BC_NUM_SIZE(total));

	// Set up the temporaries.
	bc_num_setup(&l1, dig_ptr, max);
	dig_ptr += max;
	bc_num_setup(&h1, dig_ptr, max);
	dig_ptr += max;
	bc_num_setup(&l2, dig_ptr, max);
	dig_ptr += max;
	bc_num_setup(&h2, dig_ptr, max);
	dig_ptr += max;
	bc_num_setup(&m1, dig_ptr, max);
	dig_ptr += max;
	bc_num_setup(&m2, dig_ptr, max);

	// Some temporaries need the ability to grow, so we allocate them
	// separately.
	max = bc_vm_growSize(max, 1);
	bc_num_init(&z0, max);
	bc_num_init(&z1, max);
	bc_num_init(&z2, max);
	max = bc_vm_growSize(max, max) + 1;
	bc_num_init(&temp, max);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	// First, set up c.
	bc_num_expand(c, max);
	c->len = max;
	// NOLINTNEXTLINE
	memset(c->num, 0, BC_NUM_SIZE(c->len));

	// Split the parameters.
	bc_num_split(a, max2, &l1, &h1);
	bc_num_split(b, max2, &l2, &h2);

	// Do the subtraction.
	bc_num_sub(&h1, &l1, &m1, 0);
	bc_num_sub(&l2, &h2, &m2, 0);

	// The if statements below are there for efficiency reasons. The best way to
	// understand them is to understand the Karatsuba algorithm because now that
	// the ollocations and splits are done, the algorithm is pretty
	// straightforward.

	if (BC_NUM_NONZERO(&h1) && BC_NUM_NONZERO(&h2))
	{
		assert(BC_NUM_RDX_VALID_NP(h1));
		assert(BC_NUM_RDX_VALID_NP(h2));

		bc_num_m(&h1, &h2, &z2, 0);
		bc_num_clean(&z2);

		bc_num_shiftAddSub(c, &z2, max2 * 2, bc_num_addArrays);
		bc_num_shiftAddSub(c, &z2, max2, bc_num_addArrays);
	}

	if (BC_NUM_NONZERO(&l1) && BC_NUM_NONZERO(&l2))
	{
		assert(BC_NUM_RDX_VALID_NP(l1));
		assert(BC_NUM_RDX_VALID_NP(l2));

		bc_num_m(&l1, &l2, &z0, 0);
		bc_num_clean(&z0);

		bc_num_shiftAddSub(c, &z0, max2, bc_num_addArrays);
		bc_num_shiftAddSub(c, &z0, 0, bc_num_addArrays);
	}

	if (BC_NUM_NONZERO(&m1) && BC_NUM_NONZERO(&m2))
	{
		assert(BC_NUM_RDX_VALID_NP(m1));
		assert(BC_NUM_RDX_VALID_NP(m1));

		bc_num_m(&m1, &m2, &z1, 0);
		bc_num_clean(&z1);

		op = (BC_NUM_NEG_NP(m1) != BC_NUM_NEG_NP(m2)) ?
		         bc_num_subArrays :
		         bc_num_addArrays;
		bc_num_shiftAddSub(c, &z1, max2, op);
	}

err:
	BC_SIG_MAYLOCK;
	free(digs);
	bc_num_free(&temp);
	bc_num_free(&z2);
	bc_num_free(&z1);
	bc_num_free(&z0);
	BC_LONGJMP_CONT(vm);
}

/**
 * Does checks for Karatsuba. It also changes things to ensure that the
 * Karatsuba and simple multiplication can treat the numbers as integers. This
 * is a BcNumBinOp function.
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter.
 * @param scale  The current scale.
 */
static void
bc_num_m(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale)
{
	BcNum cpa, cpb;
	size_t ascale, bscale, ardx, brdx, zero, len, rscale;
	// These are meant to quiet warnings on GCC about longjmp() clobbering.
	// The problem is real here.
	size_t scale1, scale2, realscale;
	// These are meant to quiet the GCC longjmp() clobbering, even though it
	// does not apply here.
	volatile size_t azero;
	volatile size_t bzero;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));

	bc_num_zero(c);

	ascale = a->scale;
	bscale = b->scale;

	// This sets the final scale according to the bc spec.
	scale1 = BC_MAX(scale, ascale);
	scale2 = BC_MAX(scale1, bscale);
	rscale = ascale + bscale;
	realscale = BC_MIN(rscale, scale2);

	// If this condition is true, we can use bc_num_mulArray(), which would be
	// much faster.
	if ((a->len == 1 || b->len == 1) && !a->rdx && !b->rdx)
	{
		BcNum* operand;
		BcBigDig dig;

		// Set the correct operands.
		if (a->len == 1)
		{
			dig = (BcBigDig) a->num[0];
			operand = b;
		}
		else
		{
			dig = (BcBigDig) b->num[0];
			operand = a;
		}

		bc_num_mulArray(operand, dig, c);

		// Need to make sure the sign is correct.
		if (BC_NUM_NONZERO(c))
		{
			c->rdx = BC_NUM_NEG_VAL(c, BC_NUM_NEG(a) != BC_NUM_NEG(b));
		}

		return;
	}

	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));

	BC_SIG_LOCK;

	// We need copies because of all of the mutation needed to make Karatsuba
	// think the numbers are integers.
	bc_num_init(&cpa, a->len + BC_NUM_RDX_VAL(a));
	bc_num_init(&cpb, b->len + BC_NUM_RDX_VAL(b));

	BC_SETJMP_LOCKED(vm, init_err);

	BC_SIG_UNLOCK;

	bc_num_copy(&cpa, a);
	bc_num_copy(&cpb, b);

	assert(BC_NUM_RDX_VALID_NP(cpa));
	assert(BC_NUM_RDX_VALID_NP(cpb));

	BC_NUM_NEG_CLR_NP(cpa);
	BC_NUM_NEG_CLR_NP(cpb);

	assert(BC_NUM_RDX_VALID_NP(cpa));
	assert(BC_NUM_RDX_VALID_NP(cpb));

	// These are what makes them appear like integers.
	ardx = BC_NUM_RDX_VAL_NP(cpa) * BC_BASE_DIGS;
	bc_num_shiftLeft(&cpa, ardx);

	brdx = BC_NUM_RDX_VAL_NP(cpb) * BC_BASE_DIGS;
	bc_num_shiftLeft(&cpb, brdx);

	// We need to reset the jump here because azero and bzero are used in the
	// cleanup, and local variables are not guaranteed to be the same after a
	// jump.
	BC_SIG_LOCK;

	BC_UNSETJMP(vm);

	// We want to ignore zero limbs.
	azero = bc_num_shiftZero(&cpa);
	bzero = bc_num_shiftZero(&cpb);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	bc_num_clean(&cpa);
	bc_num_clean(&cpb);

	bc_num_k(&cpa, &cpb, c);

	// The return parameter needs to have its scale set. This is the start. It
	// also needs to be shifted by the same amount as a and b have limbs after
	// the decimal point.
	zero = bc_vm_growSize(azero, bzero);
	len = bc_vm_growSize(c->len, zero);

	bc_num_expand(c, len);

	// Shift c based on the limbs after the decimal point in a and b.
	bc_num_shiftLeft(c, (len - c->len) * BC_BASE_DIGS);
	bc_num_shiftRight(c, ardx + brdx);

	bc_num_retireMul(c, realscale, BC_NUM_NEG(a), BC_NUM_NEG(b));

err:
	BC_SIG_MAYLOCK;
	bc_num_unshiftZero(&cpb, bzero);
	bc_num_unshiftZero(&cpa, azero);
init_err:
	BC_SIG_MAYLOCK;
	bc_num_free(&cpb);
	bc_num_free(&cpa);
	BC_LONGJMP_CONT(vm);
}

/**
 * Returns true if the BcDig array has non-zero limbs, false otherwise.
 * @param a    The array to test.
 * @param len  The length of the array.
 * @return     True if @a has any non-zero limbs, false otherwise.
 */
static bool
bc_num_nonZeroDig(BcDig* restrict a, size_t len)
{
	size_t i;

	for (i = len - 1; i < len; --i)
	{
		if (a[i] != 0) return true;
	}

	return false;
}

/**
 * Compares a BcDig array against a BcNum. This is especially suited for
 * division. Returns >0 if @a a is greater than @a b, <0 if it is less, and =0
 * if they are equal.
 * @param a    The array.
 * @param b    The number.
 * @param len  The length to assume the arrays are. This is always less than the
 *             actual length because of how this is implemented.
 */
static ssize_t
bc_num_divCmp(const BcDig* a, const BcNum* b, size_t len)
{
	ssize_t cmp;

	if (b->len > len && a[len]) cmp = bc_num_compare(a, b->num, len + 1);
	else if (b->len <= len)
	{
		if (a[len]) cmp = 1;
		else cmp = bc_num_compare(a, b->num, len);
	}
	else cmp = -1;

	return cmp;
}

/**
 * Extends the two operands of a division by BC_BASE_DIGS minus the number of
 * digits in the divisor estimate. In other words, it is shifting the numbers in
 * order to force the divisor estimate to fill the limb.
 * @param a        The first operand.
 * @param b        The second operand.
 * @param divisor  The divisor estimate.
 */
static void
bc_num_divExtend(BcNum* restrict a, BcNum* restrict b, BcBigDig divisor)
{
	size_t pow;

	assert(divisor < BC_BASE_POW);

	pow = BC_BASE_DIGS - bc_num_log10((size_t) divisor);

	bc_num_shiftLeft(a, pow);
	bc_num_shiftLeft(b, pow);
}

/**
 * Actually does division. This is a rewrite of my original code by Stefan Esser
 * from FreeBSD.
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter.
 * @param scale  The current scale.
 */
static void
bc_num_d_long(BcNum* restrict a, BcNum* restrict b, BcNum* restrict c,
              size_t scale)
{
	BcBigDig divisor;
	size_t i, rdx;
	// This is volatile and len 2 and reallen exist to quiet the GCC warning
	// about clobbering on longjmp(). This one is possible, I think.
	volatile size_t len;
	size_t len2, reallen;
	// This is volatile and realend exists to quiet the GCC warning about
	// clobbering on longjmp(). This one is possible, I think.
	volatile size_t end;
	size_t realend;
	BcNum cpb;
	// This is volatile and realnonzero exists to quiet the GCC warning about
	// clobbering on longjmp(). This one is possible, I think.
	volatile bool nonzero;
	bool realnonzero;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	assert(b->len < a->len);

	len = b->len;
	end = a->len - len;

	assert(len >= 1);

	// This is a final time to make sure c is big enough and that its array is
	// properly zeroed.
	bc_num_expand(c, a->len);
	// NOLINTNEXTLINE
	memset(c->num, 0, c->cap * sizeof(BcDig));

	// Setup.
	BC_NUM_RDX_SET(c, BC_NUM_RDX_VAL(a));
	c->scale = a->scale;
	c->len = a->len;

	// This is pulling the most significant limb of b in order to establish a
	// good "estimate" for the actual divisor.
	divisor = (BcBigDig) b->num[len - 1];

	// The entire bit of code in this if statement is to tighten the estimate of
	// the divisor. The condition asks if b has any other non-zero limbs.
	if (len > 1 && bc_num_nonZeroDig(b->num, len - 1))
	{
		// This takes a little bit of understanding. The "10*BC_BASE_DIGS/6+1"
		// results in either 16 for 64-bit 9-digit limbs or 7 for 32-bit 4-digit
		// limbs. Then it shifts a 1 by that many, which in both cases, puts the
		// result above *half* of the max value a limb can store. Basically,
		// this quickly calculates if the divisor is greater than half the max
		// of a limb.
		nonzero = (divisor > 1 << ((10 * BC_BASE_DIGS) / 6 + 1));

		// If the divisor is *not* greater than half the limb...
		if (!nonzero)
		{
			// Extend the parameters by the number of missing digits in the
			// divisor.
			bc_num_divExtend(a, b, divisor);

			// Check bc_num_d(). In there, we grow a again and again. We do it
			// again here; we *always* want to be sure it is big enough.
			len2 = BC_MAX(a->len, b->len);
			bc_num_expand(a, len2 + 1);

			// Make a have a zero most significant limb to match the len.
			if (len2 + 1 > a->len) a->len = len2 + 1;

			// Grab the new divisor estimate, new because the shift has made it
			// different.
			reallen = b->len;
			realend = a->len - reallen;
			divisor = (BcBigDig) b->num[reallen - 1];

			realnonzero = bc_num_nonZeroDig(b->num, reallen - 1);
		}
		else
		{
			realend = end;
			realnonzero = nonzero;
		}
	}
	else
	{
		realend = end;
		realnonzero = false;
	}

	// If b has other nonzero limbs, we want the divisor to be one higher, so
	// that it is an upper bound.
	divisor += realnonzero;

	// Make sure c can fit the new length.
	bc_num_expand(c, a->len);
	// NOLINTNEXTLINE
	memset(c->num, 0, BC_NUM_SIZE(c->cap));

	assert(c->scale >= scale);
	rdx = BC_NUM_RDX_VAL(c) - BC_NUM_RDX(scale);

	BC_SIG_LOCK;

	bc_num_init(&cpb, len + 1);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	// This is the actual division loop.
	for (i = realend - 1; i < realend && i >= rdx && BC_NUM_NONZERO(a); --i)
	{
		ssize_t cmp;
		BcDig* n;
		BcBigDig result;

		n = a->num + i;
		assert(n >= a->num);
		result = 0;

		cmp = bc_num_divCmp(n, b, len);

		// This is true if n is greater than b, which means that division can
		// proceed, so this inner loop is the part that implements one instance
		// of the division.
		while (cmp >= 0)
		{
			BcBigDig n1, dividend, quotient;

			// These should be named obviously enough. Just imagine that it's a
			// division of one limb. Because that's what it is.
			n1 = (BcBigDig) n[len];
			dividend = n1 * BC_BASE_POW + (BcBigDig) n[len - 1];
			quotient = (dividend / divisor);

			// If this is true, then we can just subtract. Remember: setting
			// quotient to 1 is not bad because we already know that n is
			// greater than b.
			if (quotient <= 1)
			{
				quotient = 1;
				bc_num_subArrays(n, b->num, len);
			}
			else
			{
				assert(quotient <= BC_BASE_POW);

				// We need to multiply and subtract for a quotient above 1.
				bc_num_mulArray(b, (BcBigDig) quotient, &cpb);
				bc_num_subArrays(n, cpb.num, cpb.len);
			}

			// The result is the *real* quotient, by the way, but it might take
			// multiple trips around this loop to get it.
			result += quotient;
			assert(result <= BC_BASE_POW);

			// And here's why it might take multiple trips: n might *still* be
			// greater than b. So we have to loop again. That's what this is
			// setting up for: the condition of the while loop.
			if (realnonzero) cmp = bc_num_divCmp(n, b, len);
			else cmp = -1;
		}

		assert(result < BC_BASE_POW);

		// Store the actual limb quotient.
		c->num[i] = (BcDig) result;
	}

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&cpb);
	BC_LONGJMP_CONT(vm);
}

/**
 * Implements division. This is a BcNumBinOp function.
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter.
 * @param scale  The current scale.
 */
static void
bc_num_d(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale)
{
	size_t len, cpardx;
	BcNum cpa, cpb;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	if (BC_NUM_ZERO(b)) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);

	if (BC_NUM_ZERO(a))
	{
		bc_num_setToZero(c, scale);
		return;
	}

	if (BC_NUM_ONE(b))
	{
		bc_num_copy(c, a);
		bc_num_retireMul(c, scale, BC_NUM_NEG(a), BC_NUM_NEG(b));
		return;
	}

	// If this is true, we can use bc_num_divArray(), which would be faster.
	if (!BC_NUM_RDX_VAL(a) && !BC_NUM_RDX_VAL(b) && b->len == 1 && !scale)
	{
		BcBigDig rem;
		bc_num_divArray(a, (BcBigDig) b->num[0], c, &rem);
		bc_num_retireMul(c, scale, BC_NUM_NEG(a), BC_NUM_NEG(b));
		return;
	}

	len = bc_num_divReq(a, b, scale);

	BC_SIG_LOCK;

	// Initialize copies of the parameters. We want the length of the first
	// operand copy to be as big as the result because of the way the division
	// is implemented.
	bc_num_init(&cpa, len);
	bc_num_copy(&cpa, a);
	bc_num_createCopy(&cpb, b);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	len = b->len;

	// Like the above comment, we want the copy of the first parameter to be
	// larger than the second parameter.
	if (len > cpa.len)
	{
		bc_num_expand(&cpa, bc_vm_growSize(len, 2));
		bc_num_extend(&cpa, (len - cpa.len) * BC_BASE_DIGS);
	}

	cpardx = BC_NUM_RDX_VAL_NP(cpa);
	cpa.scale = cpardx * BC_BASE_DIGS;

	// This is just setting up the scale in preparation for the division.
	bc_num_extend(&cpa, b->scale);
	cpardx = BC_NUM_RDX_VAL_NP(cpa) - BC_NUM_RDX(b->scale);
	BC_NUM_RDX_SET_NP(cpa, cpardx);
	cpa.scale = cpardx * BC_BASE_DIGS;

	// Once again, just setting things up, this time to match scale.
	if (scale > cpa.scale)
	{
		bc_num_extend(&cpa, scale);
		cpardx = BC_NUM_RDX_VAL_NP(cpa);
		cpa.scale = cpardx * BC_BASE_DIGS;
	}

	// Grow if necessary.
	if (cpa.cap == cpa.len) bc_num_expand(&cpa, bc_vm_growSize(cpa.len, 1));

	// We want an extra zero in front to make things simpler.
	cpa.num[cpa.len++] = 0;

	// Still setting things up. Why all of these things are needed is not
	// something that can be easily explained, but it has to do with making the
	// actual algorithm easier to understand because it can assume a lot of
	// things. Thus, you should view all of this setup code as establishing
	// assumptions for bc_num_d_long(), where the actual division happens.
	if (cpardx == cpa.len) cpa.len = bc_num_nonZeroLen(&cpa);
	if (BC_NUM_RDX_VAL_NP(cpb) == cpb.len) cpb.len = bc_num_nonZeroLen(&cpb);
	cpb.scale = 0;
	BC_NUM_RDX_SET_NP(cpb, 0);

	bc_num_d_long(&cpa, &cpb, c, scale);

	bc_num_retireMul(c, scale, BC_NUM_NEG(a), BC_NUM_NEG(b));

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&cpb);
	bc_num_free(&cpa);
	BC_LONGJMP_CONT(vm);
}

/**
 * Implements divmod. This is the actual modulus function; since modulus
 * requires a division anyway, this returns the quotient and modulus. Either can
 * be thrown out as desired.
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter for the quotient.
 * @param d      The return parameter for the modulus.
 * @param scale  The current scale.
 * @param ts     The scale that the operation should be done to. Yes, it's not
 *               necessarily the same as scale, per the bc spec.
 */
static void
bc_num_r(BcNum* a, BcNum* b, BcNum* restrict c, BcNum* restrict d, size_t scale,
         size_t ts)
{
	BcNum temp;
	// realscale is meant to quiet a warning on GCC about longjmp() clobbering.
	// This one is real.
	size_t realscale;
	bool neg;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	if (BC_NUM_ZERO(b)) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);

	if (BC_NUM_ZERO(a))
	{
		bc_num_setToZero(c, ts);
		bc_num_setToZero(d, ts);
		return;
	}

	BC_SIG_LOCK;

	bc_num_init(&temp, d->cap);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	// Division.
	bc_num_d(a, b, c, scale);

	// We want an extra digit so we can safely truncate.
	if (scale) realscale = ts + 1;
	else realscale = scale;

	assert(BC_NUM_RDX_VALID(c));
	assert(BC_NUM_RDX_VALID(b));

	// Implement the rest of the (a - (a / b) * b) formula.
	bc_num_m(c, b, &temp, realscale);
	bc_num_sub(a, &temp, d, realscale);

	// Extend if necessary.
	if (ts > d->scale && BC_NUM_NONZERO(d)) bc_num_extend(d, ts - d->scale);

	neg = BC_NUM_NEG(d);
	bc_num_retireMul(d, ts, BC_NUM_NEG(a), BC_NUM_NEG(b));
	d->rdx = BC_NUM_NEG_VAL(d, BC_NUM_NONZERO(d) ? neg : false);

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&temp);
	BC_LONGJMP_CONT(vm);
}

/**
 * Implements modulus/remainder. (Yes, I know they are different, but not in the
 * context of bc.) This is a BcNumBinOp function.
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter.
 * @param scale  The current scale.
 */
static void
bc_num_rem(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale)
{
	BcNum c1;
	size_t ts;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	ts = bc_vm_growSize(scale, b->scale);
	ts = BC_MAX(ts, a->scale);

	BC_SIG_LOCK;

	// Need a temp for the quotient.
	bc_num_init(&c1, bc_num_mulReq(a, b, ts));

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	bc_num_r(a, b, &c1, c, scale, ts);

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&c1);
	BC_LONGJMP_CONT(vm);
}

/**
 * Implements power (exponentiation). This is a BcNumBinOp function.
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter.
 * @param scale  The current scale.
 */
static void
bc_num_p(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale)
{
	BcNum copy, btemp;
	BcBigDig exp;
	// realscale is meant to quiet a warning on GCC about longjmp() clobbering.
	// This one is real.
	size_t powrdx, resrdx, realscale;
	bool neg;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	// This is here to silence a warning from GCC.
#if BC_GCC
	btemp.len = 0;
	btemp.rdx = 0;
	btemp.num = NULL;
#endif // BC_GCC

	if (BC_ERR(bc_num_nonInt(b, &btemp))) bc_err(BC_ERR_MATH_NON_INTEGER);

	assert(btemp.len == 0 || btemp.num != NULL);

	if (BC_NUM_ZERO(&btemp))
	{
		bc_num_one(c);
		return;
	}

	if (BC_NUM_ZERO(a))
	{
		if (BC_NUM_NEG_NP(btemp)) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);
		bc_num_setToZero(c, scale);
		return;
	}

	if (BC_NUM_ONE(&btemp))
	{
		if (!BC_NUM_NEG_NP(btemp)) bc_num_copy(c, a);
		else bc_num_inv(a, c, scale);
		return;
	}

	neg = BC_NUM_NEG_NP(btemp);
	BC_NUM_NEG_CLR_NP(btemp);

	exp = bc_num_bigdig(&btemp);

	BC_SIG_LOCK;

	bc_num_createCopy(&copy, a);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	// If this is true, then we do not have to do a division, and we need to
	// set scale accordingly.
	if (!neg)
	{
		size_t max = BC_MAX(scale, a->scale), scalepow;
		scalepow = bc_num_mulOverflow(a->scale, exp);
		realscale = BC_MIN(scalepow, max);
	}
	else realscale = scale;

	// This is only implementing the first exponentiation by squaring, until it
	// reaches the first time where the square is actually used.
	for (powrdx = a->scale; !(exp & 1); exp >>= 1)
	{
		powrdx <<= 1;
		assert(BC_NUM_RDX_VALID_NP(copy));
		bc_num_mul(&copy, &copy, &copy, powrdx);
	}

	// Make c a copy of copy for the purpose of saving the squares that should
	// be saved.
	bc_num_copy(c, &copy);
	resrdx = powrdx;

	// Now finish the exponentiation by squaring, this time saving the squares
	// as necessary.
	while (exp >>= 1)
	{
		powrdx <<= 1;
		assert(BC_NUM_RDX_VALID_NP(copy));
		bc_num_mul(&copy, &copy, &copy, powrdx);

		// If this is true, we want to save that particular square. This does
		// that by multiplying c with copy.
		if (exp & 1)
		{
			resrdx += powrdx;
			assert(BC_NUM_RDX_VALID(c));
			assert(BC_NUM_RDX_VALID_NP(copy));
			bc_num_mul(c, &copy, c, resrdx);
		}
	}

	// Invert if necessary.
	if (neg) bc_num_inv(c, c, realscale);

	// Truncate if necessary.
	if (c->scale > realscale) bc_num_truncate(c, c->scale - realscale);

	bc_num_clean(c);

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&copy);
	BC_LONGJMP_CONT(vm);
}

#if BC_ENABLE_EXTRA_MATH
/**
 * Implements the places operator. This is a BcNumBinOp function.
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter.
 * @param scale  The current scale.
 */
static void
bc_num_place(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale)
{
	BcBigDig val;

	BC_UNUSED(scale);

	val = bc_num_intop(a, b, c);

	// Just truncate or extend as appropriate.
	if (val < c->scale) bc_num_truncate(c, c->scale - val);
	else if (val > c->scale) bc_num_extend(c, val - c->scale);
}

/**
 * Implements the left shift operator. This is a BcNumBinOp function.
 */
static void
bc_num_left(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale)
{
	BcBigDig val;

	BC_UNUSED(scale);

	val = bc_num_intop(a, b, c);

	bc_num_shiftLeft(c, (size_t) val);
}

/**
 * Implements the right shift operator. This is a BcNumBinOp function.
 */
static void
bc_num_right(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale)
{
	BcBigDig val;

	BC_UNUSED(scale);

	val = bc_num_intop(a, b, c);

	if (BC_NUM_ZERO(c)) return;

	bc_num_shiftRight(c, (size_t) val);
}
#endif // BC_ENABLE_EXTRA_MATH

/**
 * Prepares for, and calls, a binary operator function. This is probably the
 * most important function in the entire file because it establishes assumptions
 * that make the rest of the code so easy. Those assumptions include:
 *
 * - a is not the same pointer as c.
 * - b is not the same pointer as c.
 * - there is enough room in c for the result.
 *
 * Without these, this whole function would basically have to be duplicated for
 * *all* binary operators.
 *
 * @param a      The first operand.
 * @param b      The second operand.
 * @param c      The return parameter.
 * @param scale  The current scale.
 * @param req    The number of limbs needed to fit the result.
 */
static void
bc_num_binary(BcNum* a, BcNum* b, BcNum* c, size_t scale, BcNumBinOp op,
              size_t req)
{
	BcNum* ptr_a;
	BcNum* ptr_b;
	BcNum num2;
#if BC_ENABLE_LIBRARY
	BcVm* vm = NULL;
#endif // BC_ENABLE_LIBRARY

	assert(a != NULL && b != NULL && c != NULL && op != NULL);

	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));

	BC_SIG_LOCK;

	ptr_a = c == a ? &num2 : a;
	ptr_b = c == b ? &num2 : b;

	// Actually reallocate. If we don't reallocate, we want to expand at the
	// very least.
	if (c == a || c == b)
	{
#if BC_ENABLE_LIBRARY
		vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

		// NOLINTNEXTLINE
		memcpy(&num2, c, sizeof(BcNum));

		bc_num_init(c, req);

		// Must prepare for cleanup. We want this here so that locals that got
		// set stay set since a longjmp() is not guaranteed to preserve locals.
		BC_SETJMP_LOCKED(vm, err);
		BC_SIG_UNLOCK;
	}
	else
	{
		BC_SIG_UNLOCK;
		bc_num_expand(c, req);
	}

	// It is okay for a and b to be the same. If a binary operator function does
	// need them to be different, the binary operator function is responsible
	// for that.

	// Call the actual binary operator function.
	op(ptr_a, ptr_b, c, scale);

	assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
	assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
	assert(BC_NUM_RDX_VALID(c));
	assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);

err:
	// Cleanup only needed if we initialized c to a new number.
	if (c == a || c == b)
	{
		BC_SIG_MAYLOCK;
		bc_num_free(&num2);
		BC_LONGJMP_CONT(vm);
	}
}

/**
 * Tests a number string for validity. This function has a history; I originally
 * wrote it because I did not trust my parser. Over time, however, I came to
 * trust it, so I was able to relegate this function to debug builds only, and I
 * used it in assert()'s. But then I created the library, and well, I can't
 * trust users, so I reused this for yelling at users.
 * @param val  The string to check to see if it's a valid number string.
 * @return     True if the string is a valid number string, false otherwise.
 */
bool
bc_num_strValid(const char* restrict val)
{
	bool radix = false;
	size_t i, len = strlen(val);

	// Notice that I don't check if there is a negative sign. That is not part
	// of a valid number, except in the library. The library-specific code takes
	// care of that part.

	// Nothing in the string is okay.
	if (!len) return true;

	// Loop through the characters.
	for (i = 0; i < len; ++i)
	{
		BcDig c = val[i];

		// If we have found a radix point...
		if (c == '.')
		{
			// We don't allow two radices.
			if (radix) return false;

			radix = true;
			continue;
		}

		// We only allow digits and uppercase letters.
		if (!(isdigit(c) || isupper(c))) return false;
	}

	return true;
}

/**
 * Parses one character and returns the digit that corresponds to that
 * character according to the base.
 * @param c     The character to parse.
 * @param base  The base.
 * @return      The character as a digit.
 */
static BcBigDig
bc_num_parseChar(char c, size_t base)
{
	assert(isupper(c) || isdigit(c));

	// If a letter...
	if (isupper(c))
	{
#if BC_ENABLE_LIBRARY
		BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

		// This returns the digit that directly corresponds with the letter.
		c = BC_NUM_NUM_LETTER(c);

		// If the digit is greater than the base, we clamp.
		if (BC_DIGIT_CLAMP)
		{
			c = ((size_t) c) >= base ? (char) base - 1 : c;
		}
	}
	// Straight convert the digit to a number.
	else c -= '0';

	return (BcBigDig) (uchar) c;
}

/**
 * Parses a string as a decimal number. This is separate because it's going to
 * be the most used, and it can be heavily optimized for decimal only.
 * @param n    The number to parse into and return. Must be preallocated.
 * @param val  The string to parse.
 */
static void
bc_num_parseDecimal(BcNum* restrict n, const char* restrict val)
{
	size_t len, i, temp, mod;
	const char* ptr;
	bool zero = true, rdx;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	// Eat leading zeroes.
	for (i = 0; val[i] == '0'; ++i)
	{
		continue;
	}

	val += i;
	assert(!val[0] || isalnum(val[0]) || val[0] == '.');

	// All 0's. We can just return, since this procedure expects a virgin
	// (already 0) BcNum.
	if (!val[0]) return;

	// The length of the string is the length of the number, except it might be
	// one bigger because of a decimal point.
	len = strlen(val);

	// Find the location of the decimal point.
	ptr = strchr(val, '.');
	rdx = (ptr != NULL);

	// We eat leading zeroes again. These leading zeroes are different because
	// they will come after the decimal point if they exist, and since that's
	// the case, they must be preserved.
	for (i = 0; i < len && (zero = (val[i] == '0' || val[i] == '.')); ++i)
	{
		continue;
	}

	// Set the scale of the number based on the location of the decimal point.
	// The casts to uintptr_t is to ensure that bc does not hit undefined
	// behavior when doing math on the values.
	n->scale = (size_t) (rdx *
	                     (((uintptr_t) (val + len)) - (((uintptr_t) ptr) + 1)));

	// Set rdx.
	BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale));

	// Calculate length. First, the length of the integer, then the number of
	// digits in the last limb, then the length.
	i = len - (ptr == val ? 0 : i) - rdx;
	temp = BC_NUM_ROUND_POW(i);
	mod = n->scale % BC_BASE_DIGS;
	i = mod ? BC_BASE_DIGS - mod : 0;
	n->len = ((temp + i) / BC_BASE_DIGS);

	// Expand and zero. The plus extra is in case the lack of clamping causes
	// the number to overflow the original bounds.
	bc_num_expand(n, n->len + !BC_DIGIT_CLAMP);
	// NOLINTNEXTLINE
	memset(n->num, 0, BC_NUM_SIZE(n->len + !BC_DIGIT_CLAMP));

	if (zero)
	{
		// I think I can set rdx directly to zero here because n should be a
		// new number with sign set to false.
		n->len = n->rdx = 0;
	}
	else
	{
		// There is actually stuff to parse if we make it here. Yay...
		BcBigDig exp, pow;

		assert(i <= BC_NUM_BIGDIG_MAX);

		// The exponent and power.
		exp = (BcBigDig) i;
		pow = bc_num_pow10[exp];

		// Parse loop. We parse backwards because numbers are stored little
		// endian.
		for (i = len - 1; i < len; --i, ++exp)
		{
			char c = val[i];

			// Skip the decimal point.
			if (c == '.') exp -= 1;
			else
			{
				// The index of the limb.
				size_t idx = exp / BC_BASE_DIGS;
				BcBigDig dig;

				if (isupper(c))
				{
					// Clamp for the base.
					if (!BC_DIGIT_CLAMP) c = BC_NUM_NUM_LETTER(c);
					else c = 9;
				}
				else c -= '0';

				// Add the digit to the limb. This takes care of overflow from
				// lack of clamping.
				dig = ((BcBigDig) n->num[idx]) + ((BcBigDig) c) * pow;
				if (dig >= BC_BASE_POW)
				{
					// We cannot go over BC_BASE_POW with clamping.
					assert(!BC_DIGIT_CLAMP);

					n->num[idx + 1] = (BcDig) (dig / BC_BASE_POW);
					n->num[idx] = (BcDig) (dig % BC_BASE_POW);
					assert(n->num[idx] >= 0 && n->num[idx] < BC_BASE_POW);
					assert(n->num[idx + 1] >= 0 &&
					       n->num[idx + 1] < BC_BASE_POW);
				}
				else
				{
					n->num[idx] = (BcDig) dig;
					assert(n->num[idx] >= 0 && n->num[idx] < BC_BASE_POW);
				}

				// Adjust the power and exponent.
				if ((exp + 1) % BC_BASE_DIGS == 0) pow = 1;
				else pow *= BC_BASE;
			}
		}
	}

	// Make sure to add one to the length if needed from lack of clamping.
	n->len += (!BC_DIGIT_CLAMP && n->num[n->len] != 0);
}

/**
 * Parse a number in any base (besides decimal).
 * @param n     The number to parse into and return. Must be preallocated.
 * @param val   The string to parse.
 * @param base  The base to parse as.
 */
static void
bc_num_parseBase(BcNum* restrict n, const char* restrict val, BcBigDig base)
{
	BcNum temp, mult1, mult2, result1, result2;
	BcNum* m1;
	BcNum* m2;
	BcNum* ptr;
	char c = 0;
	bool zero = true;
	BcBigDig v;
	size_t digs, len = strlen(val);
	// This is volatile to quiet a warning on GCC about longjmp() clobbering.
	volatile size_t i;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	// If zero, just return because the number should be virgin (already 0).
	for (i = 0; zero && i < len; ++i)
	{
		zero = (val[i] == '.' || val[i] == '0');
	}
	if (zero) return;

	BC_SIG_LOCK;

	bc_num_init(&temp, BC_NUM_BIGDIG_LOG10);
	bc_num_init(&mult1, BC_NUM_BIGDIG_LOG10);

	BC_SETJMP_LOCKED(vm, int_err);

	BC_SIG_UNLOCK;

	// We split parsing into parsing the integer and parsing the fractional
	// part.

	// Parse the integer part. This is the easy part because we just multiply
	// the number by the base, then add the digit.
	for (i = 0; i < len && (c = val[i]) && c != '.'; ++i)
	{
		// Convert the character to a digit.
		v = bc_num_parseChar(c, base);

		// Multiply the number.
		bc_num_mulArray(n, base, &mult1);

		// Convert the digit to a number and add.
		bc_num_bigdig2num(&temp, v);
		bc_num_add(&mult1, &temp, n, 0);
	}

	// If this condition is true, then we are done. We still need to do cleanup
	// though.
	if (i == len && !val[i]) goto int_err;

	// If we get here, we *must* be at the radix point.
	assert(val[i] == '.');

	BC_SIG_LOCK;

	// Unset the jump to reset in for these new initializations.
	BC_UNSETJMP(vm);

	bc_num_init(&mult2, BC_NUM_BIGDIG_LOG10);
	bc_num_init(&result1, BC_NUM_DEF_SIZE);
	bc_num_init(&result2, BC_NUM_DEF_SIZE);
	bc_num_one(&mult1);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	// Pointers for easy switching.
	m1 = &mult1;
	m2 = &mult2;

	// Parse the fractional part. This is the hard part.
	for (i += 1, digs = 0; i < len && (c = val[i]); ++i, ++digs)
	{
		size_t rdx;

		// Convert the character to a digit.
		v = bc_num_parseChar(c, base);

		// We keep growing result2 according to the base because the more digits
		// after the radix, the more significant the digits close to the radix
		// should be.
		bc_num_mulArray(&result1, base, &result2);

		// Convert the digit to a number.
		bc_num_bigdig2num(&temp, v);

		// Add the digit into the fraction part.
		bc_num_add(&result2, &temp, &result1, 0);

		// Keep growing m1 and m2 for use after the loop.
		bc_num_mulArray(m1, base, m2);

		rdx = BC_NUM_RDX_VAL(m2);

		if (m2->len < rdx) m2->len = rdx;

		// Switch.
		ptr = m1;
		m1 = m2;
		m2 = ptr;
	}

	// This one cannot be a divide by 0 because mult starts out at 1, then is
	// multiplied by base, and base cannot be 0, so mult cannot be 0. And this
	// is the reason we keep growing m1 and m2; this division is what converts
	// the parsed fractional part from an integer to a fractional part.
	bc_num_div(&result1, m1, &result2, digs * 2);

	// Pretruncate.
	bc_num_truncate(&result2, digs);

	// The final add of the integer part to the fractional part.
	bc_num_add(n, &result2, n, digs);

	// Basic cleanup.
	if (BC_NUM_NONZERO(n))
	{
		if (n->scale < digs) bc_num_extend(n, digs - n->scale);
	}
	else bc_num_zero(n);

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&result2);
	bc_num_free(&result1);
	bc_num_free(&mult2);
int_err:
	BC_SIG_MAYLOCK;
	bc_num_free(&mult1);
	bc_num_free(&temp);
	BC_LONGJMP_CONT(vm);
}

/**
 * Prints a backslash+newline combo if the number of characters needs it. This
 * is really a convenience function.
 */
static inline void
bc_num_printNewline(void)
{
#if !BC_ENABLE_LIBRARY
	if (vm->nchars >= vm->line_len - 1 && vm->line_len)
	{
		bc_vm_putchar('\\', bc_flush_none);
		bc_vm_putchar('\n', bc_flush_err);
	}
#endif // !BC_ENABLE_LIBRARY
}

/**
 * Prints a character after a backslash+newline, if needed.
 * @param c       The character to print.
 * @param bslash  Whether to print a backslash+newline.
 */
static void
bc_num_putchar(int c, bool bslash)
{
	if (c != '\n' && bslash) bc_num_printNewline();
	bc_vm_putchar(c, bc_flush_save);
}

#if !BC_ENABLE_LIBRARY

/**
 * Prints a character for a number's digit. This is for printing for dc's P
 * command. This function does not need to worry about radix points. This is a
 * BcNumDigitOp.
 * @param n       The "digit" to print.
 * @param len     The "length" of the digit, or number of characters that will
 *                need to be printed for the digit.
 * @param rdx     True if a decimal (radix) point should be printed.
 * @param bslash  True if a backslash+newline should be printed if the character
 *                limit for the line is reached, false otherwise.
 */
static void
bc_num_printChar(size_t n, size_t len, bool rdx, bool bslash)
{
	BC_UNUSED(rdx);
	BC_UNUSED(len);
	BC_UNUSED(bslash);
	assert(len == 1);
	bc_vm_putchar((uchar) n, bc_flush_save);
}

#endif // !BC_ENABLE_LIBRARY

/**
 * Prints a series of characters for large bases. This is for printing in bases
 * above hexadecimal. This is a BcNumDigitOp.
 * @param n       The "digit" to print.
 * @param len     The "length" of the digit, or number of characters that will
 *                need to be printed for the digit.
 * @param rdx     True if a decimal (radix) point should be printed.
 * @param bslash  True if a backslash+newline should be printed if the character
 *                limit for the line is reached, false otherwise.
 */
static void
bc_num_printDigits(size_t n, size_t len, bool rdx, bool bslash)
{
	size_t exp, pow;

	// If needed, print the radix; otherwise, print a space to separate digits.
	bc_num_putchar(rdx ? '.' : ' ', true);

	// Calculate the exponent and power.
	for (exp = 0, pow = 1; exp < len - 1; ++exp, pow *= BC_BASE)
	{
		continue;
	}

	// Print each character individually.
	for (exp = 0; exp < len; pow /= BC_BASE, ++exp)
	{
		// The individual subdigit.
		size_t dig = n / pow;

		// Take the subdigit away.
		n -= dig * pow;

		// Print the subdigit.
		bc_num_putchar(((uchar) dig) + '0', bslash || exp != len - 1);
	}
}

/**
 * Prints a character for a number's digit. This is for printing in bases for
 * hexadecimal and below because they always print only one character at a time.
 * This is a BcNumDigitOp.
 * @param n       The "digit" to print.
 * @param len     The "length" of the digit, or number of characters that will
 *                need to be printed for the digit.
 * @param rdx     True if a decimal (radix) point should be printed.
 * @param bslash  True if a backslash+newline should be printed if the character
 *                limit for the line is reached, false otherwise.
 */
static void
bc_num_printHex(size_t n, size_t len, bool rdx, bool bslash)
{
	BC_UNUSED(len);
	BC_UNUSED(bslash);

	assert(len == 1);

	if (rdx) bc_num_putchar('.', true);

	bc_num_putchar(bc_num_hex_digits[n], bslash);
}

/**
 * Prints a decimal number. This is specially written for optimization since
 * this will be used the most and because bc's numbers are already in decimal.
 * @param n        The number to print.
 * @param newline  Whether to print backslash+newlines on long enough lines.
 */
static void
bc_num_printDecimal(const BcNum* restrict n, bool newline)
{
	size_t i, j, rdx = BC_NUM_RDX_VAL(n);
	bool zero = true;
	size_t buffer[BC_BASE_DIGS];

	// Print loop.
	for (i = n->len - 1; i < n->len; --i)
	{
		BcDig n9 = n->num[i];
		size_t temp;
		bool irdx = (i == rdx - 1);

		// Calculate the number of digits in the limb.
		zero = (zero & !irdx);
		temp = n->scale % BC_BASE_DIGS;
		temp = i || !temp ? 0 : BC_BASE_DIGS - temp;

		// NOLINTNEXTLINE
		memset(buffer, 0, BC_BASE_DIGS * sizeof(size_t));

		// Fill the buffer with individual digits.
		for (j = 0; n9 && j < BC_BASE_DIGS; ++j)
		{
			buffer[j] = ((size_t) n9) % BC_BASE;
			n9 /= BC_BASE;
		}

		// Print the digits in the buffer.
		for (j = BC_BASE_DIGS - 1; j < BC_BASE_DIGS && j >= temp; --j)
		{
			// Figure out whether to print the decimal point.
			bool print_rdx = (irdx & (j == BC_BASE_DIGS - 1));

			// The zero variable helps us skip leading zero digits in the limb.
			zero = (zero && buffer[j] == 0);

			if (!zero)
			{
				// While the first three arguments should be self-explanatory,
				// the last needs explaining. I don't want to print a newline
				// when the last digit to be printed could take the place of the
				// backslash rather than being pushed, as a single character, to
				// the next line. That's what that last argument does for bc.
				bc_num_printHex(buffer[j], 1, print_rdx,
				                !newline || (j > temp || i != 0));
			}
		}
	}
}

#if BC_ENABLE_EXTRA_MATH

/**
 * Prints a number in scientific or engineering format. When doing this, we are
 * always printing in decimal.
 * @param n        The number to print.
 * @param eng      True if we are in engineering mode.
 * @param newline  Whether to print backslash+newlines on long enough lines.
 */
static void
bc_num_printExponent(const BcNum* restrict n, bool eng, bool newline)
{
	size_t places, mod, nrdx = BC_NUM_RDX_VAL(n);
	bool neg = (n->len <= nrdx);
	BcNum temp, exp;
	BcDig digs[BC_NUM_BIGDIG_LOG10];
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	BC_SIG_LOCK;

	bc_num_createCopy(&temp, n);

	BC_SETJMP_LOCKED(vm, exit);

	BC_SIG_UNLOCK;

	// We need to calculate the exponents, and they change based on whether the
	// number is all fractional or not, obviously.
	if (neg)
	{
		// Figure out how many limbs after the decimal point is zero.
		size_t i, idx = bc_num_nonZeroLen(n) - 1;

		places = 1;

		// Figure out how much in the last limb is zero.
		for (i = BC_BASE_DIGS - 1; i < BC_BASE_DIGS; --i)
		{
			if (bc_num_pow10[i] > (BcBigDig) n->num[idx]) places += 1;
			else break;
		}

		// Calculate the combination of zero limbs and zero digits in the last
		// limb.
		places += (nrdx - (idx + 1)) * BC_BASE_DIGS;
		mod = places % 3;

		// Calculate places if we are in engineering mode.
		if (eng && mod != 0) places += 3 - mod;

		// Shift the temp to the right place.
		bc_num_shiftLeft(&temp, places);
	}
	else
	{
		// This is the number of digits that we are supposed to put behind the
		// decimal point.
		places = bc_num_intDigits(n) - 1;

		// Calculate the true number based on whether engineering mode is
		// activated.
		mod = places % 3;
		if (eng && mod != 0) places -= 3 - (3 - mod);

		// Shift the temp to the right place.
		bc_num_shiftRight(&temp, places);
	}

	// Print the shifted number.
	bc_num_printDecimal(&temp, newline);

	// Print the e.
	bc_num_putchar('e', !newline);

	// Need to explicitly print a zero exponent.
	if (!places)
	{
		bc_num_printHex(0, 1, false, !newline);
		goto exit;
	}

	// Need to print sign for the exponent.
	if (neg) bc_num_putchar('-', true);

	// Create a temporary for the exponent...
	bc_num_setup(&exp, digs, BC_NUM_BIGDIG_LOG10);
	bc_num_bigdig2num(&exp, (BcBigDig) places);

	/// ..and print it.
	bc_num_printDecimal(&exp, newline);

exit:
	BC_SIG_MAYLOCK;
	bc_num_free(&temp);
	BC_LONGJMP_CONT(vm);
}
#endif // BC_ENABLE_EXTRA_MATH

/**
 * Takes a number with limbs with base BC_BASE_POW and converts the limb at the
 * given index to base @a pow, where @a pow is obase^N.
 * @param n    The number to convert.
 * @param rem  BC_BASE_POW - @a pow.
 * @param pow  The power of obase we will convert the number to.
 * @param idx  The index of the number to start converting at. Doing the
 *             conversion is O(n^2); we have to sweep through starting at the
 *             least significant limb.
 */
static void
bc_num_printFixup(BcNum* restrict n, BcBigDig rem, BcBigDig pow, size_t idx)
{
	size_t i, len = n->len - idx;
	BcBigDig acc;
	BcDig* a = n->num + idx;

	// Ignore if there's just one limb left. This is the part that requires the
	// extra loop after the one calling this function in bc_num_printPrepare().
	if (len < 2) return;

	// Loop through the remaining limbs and convert. We start at the second limb
	// because we pull the value from the previous one as well.
	for (i = len - 1; i > 0; --i)
	{
		// Get the limb and add it to the previous, along with multiplying by
		// the remainder because that's the proper overflow. "acc" means
		// "accumulator," by the way.
		acc = ((BcBigDig) a[i]) * rem + ((BcBigDig) a[i - 1]);

		// Store a value in base pow in the previous limb.
		a[i - 1] = (BcDig) (acc % pow);

		// Divide by the base and accumulate the remaining value in the limb.
		acc /= pow;
		acc += (BcBigDig) a[i];

		// If the accumulator is greater than the base...
		if (acc >= BC_BASE_POW)
		{
			// Do we need to grow?
			if (i == len - 1)
			{
				// Grow.
				len = bc_vm_growSize(len, 1);
				bc_num_expand(n, bc_vm_growSize(len, idx));

				// Update the pointer because it may have moved.
				a = n->num + idx;

				// Zero out the last limb.
				a[len - 1] = 0;
			}

			// Overflow into the next limb since we are over the base.
			a[i + 1] += acc / BC_BASE_POW;
			acc %= BC_BASE_POW;
		}

		assert(acc < BC_BASE_POW);

		// Set the limb.
		a[i] = (BcDig) acc;
	}

	// We may have grown the number, so adjust the length.
	n->len = len + idx;
}

/**
 * Prepares a number for printing in a base that does not have BC_BASE_POW as a
 * power. This basically converts the number from having limbs of base
 * BC_BASE_POW to limbs of pow, where pow is obase^N.
 * @param n    The number to prepare for printing.
 * @param rem  The remainder of BC_BASE_POW when divided by a power of the base.
 * @param pow  The power of the base.
 */
static void
bc_num_printPrepare(BcNum* restrict n, BcBigDig rem, BcBigDig pow)
{
	size_t i;

	// Loop from the least significant limb to the most significant limb and
	// convert limbs in each pass.
	for (i = 0; i < n->len; ++i)
	{
		bc_num_printFixup(n, rem, pow, i);
	}

	// bc_num_printFixup() does not do everything it is supposed to, so we do
	// the last bit of cleanup here. That cleanup is to ensure that each limb
	// is less than pow and to expand the number to fit new limbs as necessary.
	for (i = 0; i < n->len; ++i)
	{
		assert(pow == ((BcBigDig) ((BcDig) pow)));

		// If the limb needs fixing...
		if (n->num[i] >= (BcDig) pow)
		{
			// Do we need to grow?
			if (i + 1 == n->len)
			{
				// Grow the number.
				n->len = bc_vm_growSize(n->len, 1);
				bc_num_expand(n, n->len);

				// Without this, we might use uninitialized data.
				n->num[i + 1] = 0;
			}

			assert(pow < BC_BASE_POW);

			// Overflow into the next limb.
			n->num[i + 1] += n->num[i] / ((BcDig) pow);
			n->num[i] %= (BcDig) pow;
		}
	}
}

static void
bc_num_printNum(BcNum* restrict n, BcBigDig base, size_t len,
                BcNumDigitOp print, bool newline)
{
	BcVec stack;
	BcNum intp, fracp1, fracp2, digit, flen1, flen2;
	BcNum* n1;
	BcNum* n2;
	BcNum* temp;
	BcBigDig dig = 0, acc, exp;
	BcBigDig* ptr;
	size_t i, j, nrdx, idigits;
	bool radix;
	BcDig digit_digs[BC_NUM_BIGDIG_LOG10 + 1];
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	assert(base > 1);

	// Easy case. Even with scale, we just print this.
	if (BC_NUM_ZERO(n))
	{
		print(0, len, false, !newline);
		return;
	}

	// This function uses an algorithm that Stefan Esser <se@freebsd.org> came
	// up with to print the integer part of a number. What it does is convert
	// intp into a number of the specified base, but it does it directly,
	// instead of just doing a series of divisions and printing the remainders
	// in reverse order.
	//
	// Let me explain in a bit more detail:
	//
	// The algorithm takes the current least significant limb (after intp has
	// been converted to an integer) and the next to least significant limb, and
	// it converts the least significant limb into one of the specified base,
	// putting any overflow into the next to least significant limb. It iterates
	// through the whole number, from least significant to most significant,
	// doing this conversion. At the end of that iteration, the least
	// significant limb is converted, but the others are not, so it iterates
	// again, starting at the next to least significant limb. It keeps doing
	// that conversion, skipping one more limb than the last time, until all
	// limbs have been converted. Then it prints them in reverse order.
	//
	// That is the gist of the algorithm. It leaves out several things, such as
	// the fact that limbs are not always converted into the specified base, but
	// into something close, basically a power of the specified base. In
	// Stefan's words, "You could consider BcDigs to be of base 10^BC_BASE_DIGS
	// in the normal case and obase^N for the largest value of N that satisfies
	// obase^N <= 10^BC_BASE_DIGS. [This means that] the result is not in base
	// "obase", but in base "obase^N", which happens to be printable as a number
	// of base "obase" without consideration for neighbouring BcDigs." This fact
	// is what necessitates the existence of the loop later in this function.
	//
	// The conversion happens in bc_num_printPrepare() where the outer loop
	// happens and bc_num_printFixup() where the inner loop, or actual
	// conversion, happens. In other words, bc_num_printPrepare() is where the
	// loop that starts at the least significant limb and goes to the most
	// significant limb. Then, on every iteration of its loop, it calls
	// bc_num_printFixup(), which has the inner loop of actually converting
	// the limbs it passes into limbs of base obase^N rather than base
	// BC_BASE_POW.

	nrdx = BC_NUM_RDX_VAL(n);

	BC_SIG_LOCK;

	// The stack is what allows us to reverse the digits for printing.
	bc_vec_init(&stack, sizeof(BcBigDig), BC_DTOR_NONE);
	bc_num_init(&fracp1, nrdx);

	// intp will be the "integer part" of the number, so copy it.
	bc_num_createCopy(&intp, n);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	// Make intp an integer.
	bc_num_truncate(&intp, intp.scale);

	// Get the fractional part out.
	bc_num_sub(n, &intp, &fracp1, 0);

	// If the base is not the same as the last base used for printing, we need
	// to update the cached exponent and power. Yes, we cache the values of the
	// exponent and power. That is to prevent us from calculating them every
	// time because printing will probably happen multiple times on the same
	// base.
	if (base != vm->last_base)
	{
		vm->last_pow = 1;
		vm->last_exp = 0;

		// Calculate the exponent and power.
		while (vm->last_pow * base <= BC_BASE_POW)
		{
			vm->last_pow *= base;
			vm->last_exp += 1;
		}

		// Also, the remainder and base itself.
		vm->last_rem = BC_BASE_POW - vm->last_pow;
		vm->last_base = base;
	}

	exp = vm->last_exp;

	// If vm->last_rem is 0, then the base we are printing in is a divisor of
	// BC_BASE_POW, which is the easy case because it means that BC_BASE_POW is
	// a power of obase, and no conversion is needed. If it *is* 0, then we have
	// the hard case, and we have to prepare the number for the base.
	if (vm->last_rem != 0)
	{
		bc_num_printPrepare(&intp, vm->last_rem, vm->last_pow);
	}

	// After the conversion comes the surprisingly easy part. From here on out,
	// this is basically naive code that I wrote, adjusted for the larger bases.

	// Fill the stack of digits for the integer part.
	for (i = 0; i < intp.len; ++i)
	{
		// Get the limb.
		acc = (BcBigDig) intp.num[i];

		// Turn the limb into digits of base obase.
		for (j = 0; j < exp && (i < intp.len - 1 || acc != 0); ++j)
		{
			// This condition is true if we are not at the last digit.
			if (j != exp - 1)
			{
				dig = acc % base;
				acc /= base;
			}
			else
			{
				dig = acc;
				acc = 0;
			}

			assert(dig < base);

			// Push the digit onto the stack.
			bc_vec_push(&stack, &dig);
		}

		assert(acc == 0);
	}

	// Go through the stack backwards and print each digit.
	for (i = 0; i < stack.len; ++i)
	{
		ptr = bc_vec_item_rev(&stack, i);

		assert(ptr != NULL);

		// While the first three arguments should be self-explanatory, the last
		// needs explaining. I don't want to print a backslash+newline when the
		// last digit to be printed could take the place of the backslash rather
		// than being pushed, as a single character, to the next line. That's
		// what that last argument does for bc.
		//
		// First, it needs to check if newlines are completely disabled. If they
		// are not disabled, it needs to check the next part.
		//
		// If the number has a scale, then because we are printing just the
		// integer part, there will be at least two more characters (a radix
		// point plus at least one digit). So if there is a scale, a backslash
		// is necessary.
		//
		// Finally, the last condition checks to see if we are at the end of the
		// stack. If we are *not* (i.e., the index is not one less than the
		// stack length), then a backslash is necessary because there is at
		// least one more character for at least one more digit). Otherwise, if
		// the index is equal to one less than the stack length, we want to
		// disable backslash printing.
		//
		// The function that prints bases 17 and above will take care of not
		// printing a backslash in the right case.
		print(*ptr, len, false,
		      !newline || (n->scale != 0 || i < stack.len - 1));
	}

	// We are done if there is no fractional part.
	if (!n->scale) goto err;

	BC_SIG_LOCK;

	// Reset the jump because some locals are changing.
	BC_UNSETJMP(vm);

	bc_num_init(&fracp2, nrdx);
	bc_num_setup(&digit, digit_digs, sizeof(digit_digs) / sizeof(BcDig));
	bc_num_init(&flen1, BC_NUM_BIGDIG_LOG10);
	bc_num_init(&flen2, BC_NUM_BIGDIG_LOG10);

	BC_SETJMP_LOCKED(vm, frac_err);

	BC_SIG_UNLOCK;

	bc_num_one(&flen1);

	radix = true;

	// Pointers for easy switching.
	n1 = &flen1;
	n2 = &flen2;

	fracp2.scale = n->scale;
	BC_NUM_RDX_SET_NP(fracp2, BC_NUM_RDX(fracp2.scale));

	// As long as we have not reached the scale of the number, keep printing.
	while ((idigits = bc_num_intDigits(n1)) <= n->scale)
	{
		// These numbers will keep growing.
		bc_num_expand(&fracp2, fracp1.len + 1);
		bc_num_mulArray(&fracp1, base, &fracp2);

		nrdx = BC_NUM_RDX_VAL_NP(fracp2);

		// Ensure an invariant.
		if (fracp2.len < nrdx) fracp2.len = nrdx;

		// fracp is guaranteed to be non-negative and small enough.
		dig = bc_num_bigdig2(&fracp2);

		// Convert the digit to a number and subtract it from the number.
		bc_num_bigdig2num(&digit, dig);
		bc_num_sub(&fracp2, &digit, &fracp1, 0);

		// While the first three arguments should be self-explanatory, the last
		// needs explaining. I don't want to print a newline when the last digit
		// to be printed could take the place of the backslash rather than being
		// pushed, as a single character, to the next line. That's what that
		// last argument does for bc.
		print(dig, len, radix, !newline || idigits != n->scale);

		// Update the multipliers.
		bc_num_mulArray(n1, base, n2);

		radix = false;

		// Switch.
		temp = n1;
		n1 = n2;
		n2 = temp;
	}

frac_err:
	BC_SIG_MAYLOCK;
	bc_num_free(&flen2);
	bc_num_free(&flen1);
	bc_num_free(&fracp2);
err:
	BC_SIG_MAYLOCK;
	bc_num_free(&fracp1);
	bc_num_free(&intp);
	bc_vec_free(&stack);
	BC_LONGJMP_CONT(vm);
}

/**
 * Prints a number in the specified base, or rather, figures out which function
 * to call to print the number in the specified base and calls it.
 * @param n        The number to print.
 * @param base     The base to print in.
 * @param newline  Whether to print backslash+newlines on long enough lines.
 */
static void
bc_num_printBase(BcNum* restrict n, BcBigDig base, bool newline)
{
	size_t width;
	BcNumDigitOp print;
	bool neg = BC_NUM_NEG(n);

	// Clear the sign because it makes the actual printing easier when we have
	// to do math.
	BC_NUM_NEG_CLR(n);

	// Bases at hexadecimal and below are printed as one character, larger bases
	// are printed as a series of digits separated by spaces.
	if (base <= BC_NUM_MAX_POSIX_IBASE)
	{
		width = 1;
		print = bc_num_printHex;
	}
	else
	{
		assert(base <= BC_BASE_POW);
		width = bc_num_log10(base - 1);
		print = bc_num_printDigits;
	}

	// Print.
	bc_num_printNum(n, base, width, print, newline);

	// Reset the sign.
	n->rdx = BC_NUM_NEG_VAL(n, neg);
}

#if !BC_ENABLE_LIBRARY

void
bc_num_stream(BcNum* restrict n)
{
	bc_num_printNum(n, BC_NUM_STREAM_BASE, 1, bc_num_printChar, false);
}

#endif // !BC_ENABLE_LIBRARY

void
bc_num_setup(BcNum* restrict n, BcDig* restrict num, size_t cap)
{
	assert(n != NULL);
	n->num = num;
	n->cap = cap;
	bc_num_zero(n);
}

void
bc_num_init(BcNum* restrict n, size_t req)
{
	BcDig* num;

	BC_SIG_ASSERT_LOCKED;

	assert(n != NULL);

	// BC_NUM_DEF_SIZE is set to be about the smallest allocation size that
	// malloc() returns in practice, so just use it.
	req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;

	// If we can't use a temp, allocate.
	if (req != BC_NUM_DEF_SIZE) num = bc_vm_malloc(BC_NUM_SIZE(req));
	else
	{
		num = bc_vm_getTemp() == NULL ? bc_vm_malloc(BC_NUM_SIZE(req)) :
		                                bc_vm_takeTemp();
	}

	bc_num_setup(n, num, req);
}

void
bc_num_clear(BcNum* restrict n)
{
	n->num = NULL;
	n->cap = 0;
}

void
bc_num_free(void* num)
{
	BcNum* n = (BcNum*) num;

	BC_SIG_ASSERT_LOCKED;

	assert(n != NULL);

	if (n->cap == BC_NUM_DEF_SIZE) bc_vm_addTemp(n->num);
	else free(n->num);
}

void
bc_num_copy(BcNum* d, const BcNum* s)
{
	assert(d != NULL && s != NULL);

	if (d == s) return;

	bc_num_expand(d, s->len);
	d->len = s->len;

	// I can just copy directly here because the sign *and* rdx will be
	// properly preserved.
	d->rdx = s->rdx;
	d->scale = s->scale;
	// NOLINTNEXTLINE
	memcpy(d->num, s->num, BC_NUM_SIZE(d->len));
}

void
bc_num_createCopy(BcNum* d, const BcNum* s)
{
	BC_SIG_ASSERT_LOCKED;
	bc_num_init(d, s->len);
	bc_num_copy(d, s);
}

void
bc_num_createFromBigdig(BcNum* restrict n, BcBigDig val)
{
	BC_SIG_ASSERT_LOCKED;
	bc_num_init(n, BC_NUM_BIGDIG_LOG10);
	bc_num_bigdig2num(n, val);
}

size_t
bc_num_scale(const BcNum* restrict n)
{
	return n->scale;
}

size_t
bc_num_len(const BcNum* restrict n)
{
	size_t len = n->len;

	// Always return at least 1.
	if (BC_NUM_ZERO(n)) return n->scale ? n->scale : 1;

	// If this is true, there is no integer portion of the number.
	if (BC_NUM_RDX_VAL(n) == len)
	{
		// We have to take into account the fact that some of the digits right
		// after the decimal could be zero. If that is the case, we need to
		// ignore them until we hit the first non-zero digit.

		size_t zero, scale;

		// The number of limbs with non-zero digits.
		len = bc_num_nonZeroLen(n);

		// Get the number of digits in the last limb.
		scale = n->scale % BC_BASE_DIGS;
		scale = scale ? scale : BC_BASE_DIGS;

		// Get the number of zero digits.
		zero = bc_num_zeroDigits(n->num + len - 1);

		// Calculate the true length.
		len = len * BC_BASE_DIGS - zero - (BC_BASE_DIGS - scale);
	}
	// Otherwise, count the number of int digits and return that plus the scale.
	else len = bc_num_intDigits(n) + n->scale;

	return len;
}

void
bc_num_parse(BcNum* restrict n, const char* restrict val, BcBigDig base)
{
#if BC_DEBUG
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY
#endif // BC_DEBUG

	assert(n != NULL && val != NULL && base);
	assert(base >= BC_NUM_MIN_BASE && base <= vm->maxes[BC_PROG_GLOBALS_IBASE]);
	assert(bc_num_strValid(val));

	// A one character number is *always* parsed as though the base was the
	// maximum allowed ibase, per the bc spec.
	if (!val[1])
	{
		BcBigDig dig = bc_num_parseChar(val[0], BC_NUM_MAX_LBASE);
		bc_num_bigdig2num(n, dig);
	}
	else if (base == BC_BASE) bc_num_parseDecimal(n, val);
	else bc_num_parseBase(n, val, base);

	assert(BC_NUM_RDX_VALID(n));
}

void
bc_num_print(BcNum* restrict n, BcBigDig base, bool newline)
{
	assert(n != NULL);
	assert(BC_ENABLE_EXTRA_MATH || base >= BC_NUM_MIN_BASE);

	// We may need a newline, just to start.
	bc_num_printNewline();

	if (BC_NUM_NONZERO(n))
	{
#if BC_ENABLE_LIBRARY
		BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

		// Print the sign.
		if (BC_NUM_NEG(n)) bc_num_putchar('-', true);

		// Print the leading zero if necessary. We don't print when using
		// scientific or engineering modes.
		if (BC_Z && BC_NUM_RDX_VAL(n) == n->len && base != 0 && base != 1)
		{
			bc_num_printHex(0, 1, false, !newline);
		}
	}

	// Short-circuit 0.
	if (BC_NUM_ZERO(n)) bc_num_printHex(0, 1, false, !newline);
	else if (base == BC_BASE) bc_num_printDecimal(n, newline);
#if BC_ENABLE_EXTRA_MATH
	else if (base == 0 || base == 1)
	{
		bc_num_printExponent(n, base != 0, newline);
	}
#endif // BC_ENABLE_EXTRA_MATH
	else bc_num_printBase(n, base, newline);

	if (newline) bc_num_putchar('\n', false);
}

BcBigDig
bc_num_bigdig2(const BcNum* restrict n)
{
#if BC_DEBUG
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY
#endif // BC_DEBUG

	// This function returns no errors because it's guaranteed to succeed if
	// its preconditions are met. Those preconditions include both n needs to
	// be non-NULL, n being non-negative, and n being less than vm->max. If all
	// of that is true, then we can just convert without worrying about negative
	// errors or overflow.

	BcBigDig r = 0;
	size_t nrdx = BC_NUM_RDX_VAL(n);

	assert(n != NULL);
	assert(!BC_NUM_NEG(n));
	assert(bc_num_cmp(n, &vm->max) < 0);
	assert(n->len - nrdx <= 3);

	// There is a small speed win from unrolling the loop here, and since it
	// only adds 53 bytes, I decided that it was worth it.
	switch (n->len - nrdx)
	{
		case 3:
		{
			r = (BcBigDig) n->num[nrdx + 2];

			// Fallthrough.
			BC_FALLTHROUGH
		}

		case 2:
		{
			r = r * BC_BASE_POW + (BcBigDig) n->num[nrdx + 1];

			// Fallthrough.
			BC_FALLTHROUGH
		}

		case 1:
		{
			r = r * BC_BASE_POW + (BcBigDig) n->num[nrdx];
		}
	}

	return r;
}

BcBigDig
bc_num_bigdig(const BcNum* restrict n)
{
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	assert(n != NULL);

	// This error checking is extremely important, and if you do not have a
	// guarantee that converting a number will always succeed in a particular
	// case, you *must* call this function to get these error checks. This
	// includes all instances of numbers inputted by the user or calculated by
	// the user. Otherwise, you can call the faster bc_num_bigdig2().
	if (BC_ERR(BC_NUM_NEG(n))) bc_err(BC_ERR_MATH_NEGATIVE);
	if (BC_ERR(bc_num_cmp(n, &vm->max) >= 0)) bc_err(BC_ERR_MATH_OVERFLOW);

	return bc_num_bigdig2(n);
}

void
bc_num_bigdig2num(BcNum* restrict n, BcBigDig val)
{
	BcDig* ptr;
	size_t i;

	assert(n != NULL);

	bc_num_zero(n);

	// Already 0.
	if (!val) return;

	// Expand first. This is the only way this function can fail, and it's a
	// fatal error.
	bc_num_expand(n, BC_NUM_BIGDIG_LOG10);

	// The conversion is easy because numbers are laid out in little-endian
	// order.
	for (ptr = n->num, i = 0; val; ++i, val /= BC_BASE_POW)
	{
		ptr[i] = val % BC_BASE_POW;
	}

	n->len = i;
}

#if BC_ENABLE_EXTRA_MATH

void
bc_num_rng(const BcNum* restrict n, BcRNG* rng)
{
	BcNum temp, temp2, intn, frac;
	BcRand state1, state2, inc1, inc2;
	size_t nrdx = BC_NUM_RDX_VAL(n);
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	// This function holds the secret of how I interpret a seed number for the
	// PRNG. Well, it's actually in the development manual
	// (manuals/development.md#pseudo-random-number-generator), so look there
	// before you try to understand this.

	BC_SIG_LOCK;

	bc_num_init(&temp, n->len);
	bc_num_init(&temp2, n->len);
	bc_num_init(&frac, nrdx);
	bc_num_init(&intn, bc_num_int(n));

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	assert(BC_NUM_RDX_VALID_NP(vm->max));

	// NOLINTNEXTLINE
	memcpy(frac.num, n->num, BC_NUM_SIZE(nrdx));
	frac.len = nrdx;
	BC_NUM_RDX_SET_NP(frac, nrdx);
	frac.scale = n->scale;

	assert(BC_NUM_RDX_VALID_NP(frac));
	assert(BC_NUM_RDX_VALID_NP(vm->max2));

	// Multiply the fraction and truncate so that it's an integer. The
	// truncation is what clamps it, by the way.
	bc_num_mul(&frac, &vm->max2, &temp, 0);
	bc_num_truncate(&temp, temp.scale);
	bc_num_copy(&frac, &temp);

	// Get the integer.
	// NOLINTNEXTLINE
	memcpy(intn.num, n->num + nrdx, BC_NUM_SIZE(bc_num_int(n)));
	intn.len = bc_num_int(n);

	// This assert is here because it has to be true. It is also here to justify
	// some optimizations.
	assert(BC_NUM_NONZERO(&vm->max));

	// If there *was* a fractional part...
	if (BC_NUM_NONZERO(&frac))
	{
		// This divmod splits frac into the two state parts.
		bc_num_divmod(&frac, &vm->max, &temp, &temp2, 0);

		// frac is guaranteed to be smaller than vm->max * vm->max (pow).
		// This means that when dividing frac by vm->max, as above, the
		// quotient and remainder are both guaranteed to be less than vm->max,
		// which means we can use bc_num_bigdig2() here and not worry about
		// overflow.
		state1 = (BcRand) bc_num_bigdig2(&temp2);
		state2 = (BcRand) bc_num_bigdig2(&temp);
	}
	else state1 = state2 = 0;

	// If there *was* an integer part...
	if (BC_NUM_NONZERO(&intn))
	{
		// This divmod splits intn into the two inc parts.
		bc_num_divmod(&intn, &vm->max, &temp, &temp2, 0);

		// Because temp2 is the mod of vm->max, from above, it is guaranteed
		// to be small enough to use bc_num_bigdig2().
		inc1 = (BcRand) bc_num_bigdig2(&temp2);

		// Clamp the second inc part.
		if (bc_num_cmp(&temp, &vm->max) >= 0)
		{
			bc_num_copy(&temp2, &temp);
			bc_num_mod(&temp2, &vm->max, &temp, 0);
		}

		// The if statement above ensures that temp is less than vm->max, which
		// means that we can use bc_num_bigdig2() here.
		inc2 = (BcRand) bc_num_bigdig2(&temp);
	}
	else inc1 = inc2 = 0;

	bc_rand_seed(rng, state1, state2, inc1, inc2);

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&intn);
	bc_num_free(&frac);
	bc_num_free(&temp2);
	bc_num_free(&temp);
	BC_LONGJMP_CONT(vm);
}

void
bc_num_createFromRNG(BcNum* restrict n, BcRNG* rng)
{
	BcRand s1, s2, i1, i2;
	BcNum conv, temp1, temp2, temp3;
	BcDig temp1_num[BC_RAND_NUM_SIZE], temp2_num[BC_RAND_NUM_SIZE];
	BcDig conv_num[BC_NUM_BIGDIG_LOG10];
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	BC_SIG_LOCK;

	bc_num_init(&temp3, 2 * BC_RAND_NUM_SIZE);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	bc_num_setup(&temp1, temp1_num, sizeof(temp1_num) / sizeof(BcDig));
	bc_num_setup(&temp2, temp2_num, sizeof(temp2_num) / sizeof(BcDig));
	bc_num_setup(&conv, conv_num, sizeof(conv_num) / sizeof(BcDig));

	// This assert is here because it has to be true. It is also here to justify
	// the assumption that vm->max is not zero.
	assert(BC_NUM_NONZERO(&vm->max));

	// Because this is true, we can just ignore math errors that would happen
	// otherwise.
	assert(BC_NUM_NONZERO(&vm->max2));

	bc_rand_getRands(rng, &s1, &s2, &i1, &i2);

	// Put the second piece of state into a number.
	bc_num_bigdig2num(&conv, (BcBigDig) s2);

	assert(BC_NUM_RDX_VALID_NP(conv));

	// Multiply by max to make room for the first piece of state.
	bc_num_mul(&conv, &vm->max, &temp1, 0);

	// Add in the first piece of state.
	bc_num_bigdig2num(&conv, (BcBigDig) s1);
	bc_num_add(&conv, &temp1, &temp2, 0);

	// Divide to make it an entirely fractional part.
	bc_num_div(&temp2, &vm->max2, &temp3, BC_RAND_STATE_BITS);

	// Now start on the increment parts. It's the same process without the
	// divide, so put the second piece of increment into a number.
	bc_num_bigdig2num(&conv, (BcBigDig) i2);

	assert(BC_NUM_RDX_VALID_NP(conv));

	// Multiply by max to make room for the first piece of increment.
	bc_num_mul(&conv, &vm->max, &temp1, 0);

	// Add in the first piece of increment.
	bc_num_bigdig2num(&conv, (BcBigDig) i1);
	bc_num_add(&conv, &temp1, &temp2, 0);

	// Now add the two together.
	bc_num_add(&temp2, &temp3, n, 0);

	assert(BC_NUM_RDX_VALID(n));

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&temp3);
	BC_LONGJMP_CONT(vm);
}

void
bc_num_irand(BcNum* restrict a, BcNum* restrict b, BcRNG* restrict rng)
{
	BcNum atemp;
	size_t i;

	assert(a != b);

	if (BC_ERR(BC_NUM_NEG(a))) bc_err(BC_ERR_MATH_NEGATIVE);

	// If either of these are true, then the numbers are integers.
	if (BC_NUM_ZERO(a) || BC_NUM_ONE(a)) return;

#if BC_GCC
	// This is here in GCC to quiet the "maybe-uninitialized" warning.
	atemp.num = NULL;
	atemp.len = 0;
#endif // BC_GCC

	if (BC_ERR(bc_num_nonInt(a, &atemp))) bc_err(BC_ERR_MATH_NON_INTEGER);

	assert(atemp.num != NULL);
	assert(atemp.len);

	if (atemp.len > 2)
	{
		size_t len;

		len = atemp.len - 2;

		// Just generate a random number for each limb.
		for (i = 0; i < len; i += 2)
		{
			BcRand dig;

			dig = bc_rand_bounded(rng, BC_BASE_RAND_POW);

			b->num[i] = (BcDig) (dig % BC_BASE_POW);
			b->num[i + 1] = (BcDig) (dig / BC_BASE_POW);
		}
	}
	else
	{
		// We need this set.
		i = 0;
	}

	// This will be true if there's one full limb after the two limb groups.
	if (i == atemp.len - 2)
	{
		// Increment this for easy use.
		i += 1;

		// If the last digit is not one, we need to set a bound for it
		// explicitly. Since there's still an empty limb, we need to fill that.
		if (atemp.num[i] != 1)
		{
			BcRand dig;
			BcRand bound;

			// Set the bound to the bound of the last limb times the amount
			// needed to fill the second-to-last limb as well.
			bound = ((BcRand) atemp.num[i]) * BC_BASE_POW;

			dig = bc_rand_bounded(rng, bound);

			// Fill the last two.
			b->num[i - 1] = (BcDig) (dig % BC_BASE_POW);
			b->num[i] = (BcDig) (dig / BC_BASE_POW);

			// Ensure that the length will be correct. If the last limb is zero,
			// then the length needs to be one less than the bound.
			b->len = atemp.len - (b->num[i] == 0);
		}
		// Here the last limb *is* one, which means the last limb does *not*
		// need to be filled. Also, the length needs to be one less because the
		// last limb is 0.
		else
		{
			b->num[i - 1] = (BcDig) bc_rand_bounded(rng, BC_BASE_POW);
			b->len = atemp.len - 1;
		}
	}
	// Here, there is only one limb to fill.
	else
	{
		// See above for how this works.
		if (atemp.num[i] != 1)
		{
			b->num[i] = (BcDig) bc_rand_bounded(rng, (BcRand) atemp.num[i]);
			b->len = atemp.len - (b->num[i] == 0);
		}
		else b->len = atemp.len - 1;
	}

	bc_num_clean(b);

	assert(BC_NUM_RDX_VALID(b));
}
#endif // BC_ENABLE_EXTRA_MATH

size_t
bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale)
{
	size_t aint, bint, ardx, brdx;

	// Addition and subtraction require the max of the length of the two numbers
	// plus 1.

	BC_UNUSED(scale);

	ardx = BC_NUM_RDX_VAL(a);
	aint = bc_num_int(a);
	assert(aint <= a->len && ardx <= a->len);

	brdx = BC_NUM_RDX_VAL(b);
	bint = bc_num_int(b);
	assert(bint <= b->len && brdx <= b->len);

	ardx = BC_MAX(ardx, brdx);
	aint = BC_MAX(aint, bint);

	return bc_vm_growSize(bc_vm_growSize(ardx, aint), 1);
}

size_t
bc_num_mulReq(const BcNum* a, const BcNum* b, size_t scale)
{
	size_t max, rdx;

	// Multiplication requires the sum of the lengths of the numbers.

	rdx = bc_vm_growSize(BC_NUM_RDX_VAL(a), BC_NUM_RDX_VAL(b));

	max = BC_NUM_RDX(scale);

	max = bc_vm_growSize(BC_MAX(max, rdx), 1);
	rdx = bc_vm_growSize(bc_vm_growSize(bc_num_int(a), bc_num_int(b)), max);

	return rdx;
}

size_t
bc_num_divReq(const BcNum* a, const BcNum* b, size_t scale)
{
	size_t max, rdx;

	// Division requires the length of the dividend plus the scale.

	rdx = bc_vm_growSize(BC_NUM_RDX_VAL(a), BC_NUM_RDX_VAL(b));

	max = BC_NUM_RDX(scale);

	max = bc_vm_growSize(BC_MAX(max, rdx), 1);
	rdx = bc_vm_growSize(bc_num_int(a), max);

	return rdx;
}

size_t
bc_num_powReq(const BcNum* a, const BcNum* b, size_t scale)
{
	BC_UNUSED(scale);
	return bc_vm_growSize(bc_vm_growSize(a->len, b->len), 1);
}

#if BC_ENABLE_EXTRA_MATH
size_t
bc_num_placesReq(const BcNum* a, const BcNum* b, size_t scale)
{
	BC_UNUSED(scale);
	return a->len + b->len - BC_NUM_RDX_VAL(a) - BC_NUM_RDX_VAL(b);
}
#endif // BC_ENABLE_EXTRA_MATH

void
bc_num_add(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, false, bc_num_as, bc_num_addReq(a, b, scale));
}

void
bc_num_sub(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, true, bc_num_as, bc_num_addReq(a, b, scale));
}

void
bc_num_mul(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, scale, bc_num_m, bc_num_mulReq(a, b, scale));
}

void
bc_num_div(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, scale, bc_num_d, bc_num_divReq(a, b, scale));
}

void
bc_num_mod(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, scale, bc_num_rem, bc_num_divReq(a, b, scale));
}

void
bc_num_pow(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, scale, bc_num_p, bc_num_powReq(a, b, scale));
}

#if BC_ENABLE_EXTRA_MATH
void
bc_num_places(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, scale, bc_num_place, bc_num_placesReq(a, b, scale));
}

void
bc_num_lshift(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, scale, bc_num_left, bc_num_placesReq(a, b, scale));
}

void
bc_num_rshift(BcNum* a, BcNum* b, BcNum* c, size_t scale)
{
	assert(BC_NUM_RDX_VALID(a));
	assert(BC_NUM_RDX_VALID(b));
	bc_num_binary(a, b, c, scale, bc_num_right, bc_num_placesReq(a, b, scale));
}
#endif // BC_ENABLE_EXTRA_MATH

void
bc_num_sqrt(BcNum* restrict a, BcNum* restrict b, size_t scale)
{
	BcNum num1, num2, half, f, fprime;
	BcNum* x0;
	BcNum* x1;
	BcNum* temp;
	// realscale is meant to quiet a warning on GCC about longjmp() clobbering.
	// This one is real.
	size_t pow, len, rdx, req, resscale, realscale;
	BcDig half_digs[1];
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	assert(a != NULL && b != NULL && a != b);

	if (BC_ERR(BC_NUM_NEG(a))) bc_err(BC_ERR_MATH_NEGATIVE);

	// We want to calculate to a's scale if it is bigger so that the result will
	// truncate properly.
	if (a->scale > scale) realscale = a->scale;
	else realscale = scale;

	// Set parameters for the result.
	len = bc_vm_growSize(bc_num_intDigits(a), 1);
	rdx = BC_NUM_RDX(realscale);

	// Square root needs half of the length of the parameter.
	req = bc_vm_growSize(BC_MAX(rdx, BC_NUM_RDX_VAL(a)), len >> 1);
	req = bc_vm_growSize(req, 1);

	BC_SIG_LOCK;

	// Unlike the binary operators, this function is the only single parameter
	// function and is expected to initialize the result. This means that it
	// expects that b is *NOT* preallocated. We allocate it here.
	bc_num_init(b, req);

	BC_SIG_UNLOCK;

	assert(a != NULL && b != NULL && a != b);
	assert(a->num != NULL && b->num != NULL);

	// Easy case.
	if (BC_NUM_ZERO(a))
	{
		bc_num_setToZero(b, realscale);
		return;
	}

	// Another easy case.
	if (BC_NUM_ONE(a))
	{
		bc_num_one(b);
		bc_num_extend(b, realscale);
		return;
	}

	// Set the parameters again.
	rdx = BC_NUM_RDX(realscale);
	rdx = BC_MAX(rdx, BC_NUM_RDX_VAL(a));
	len = bc_vm_growSize(a->len, rdx);

	BC_SIG_LOCK;

	bc_num_init(&num1, len);
	bc_num_init(&num2, len);
	bc_num_setup(&half, half_digs, sizeof(half_digs) / sizeof(BcDig));

	// There is a division by two in the formula. We set up a number that's 1/2
	// so that we can use multiplication instead of heavy division.
	bc_num_setToZero(&half, 1);
	half.num[0] = BC_BASE_POW / 2;
	half.len = 1;
	BC_NUM_RDX_SET_NP(half, 1);

	bc_num_init(&f, len);
	bc_num_init(&fprime, len);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	// Pointers for easy switching.
	x0 = &num1;
	x1 = &num2;

	// Start with 1.
	bc_num_one(x0);

	// The power of the operand is needed for the estimate.
	pow = bc_num_intDigits(a);

	// The code in this if statement calculates the initial estimate. First, if
	// a is less than 1, then 0 is a good estimate. Otherwise, we want something
	// in the same ballpark. That ballpark is half of pow because the result
	// will have half the digits.
	if (pow)
	{
		// An odd number is served by starting with 2^((pow-1)/2), and an even
		// number is served by starting with 6^((pow-2)/2). Why? Because math.
		if (pow & 1) x0->num[0] = 2;
		else x0->num[0] = 6;

		pow -= 2 - (pow & 1);
		bc_num_shiftLeft(x0, pow / 2);
	}

	// I can set the rdx here directly because neg should be false.
	x0->scale = x0->rdx = 0;
	resscale = (realscale + BC_BASE_DIGS) + 2;

	// This is the calculation loop. This compare goes to 0 eventually as the
	// difference between the two numbers gets smaller than resscale.
	while (bc_num_cmp(x1, x0))
	{
		assert(BC_NUM_NONZERO(x0));

		// This loop directly corresponds to the iteration in Newton's method.
		// If you know the formula, this loop makes sense. Go study the formula.

		bc_num_div(a, x0, &f, resscale);
		bc_num_add(x0, &f, &fprime, resscale);

		assert(BC_NUM_RDX_VALID_NP(fprime));
		assert(BC_NUM_RDX_VALID_NP(half));

		bc_num_mul(&fprime, &half, x1, resscale);

		// Switch.
		temp = x0;
		x0 = x1;
		x1 = temp;
	}

	// Copy to the result and truncate.
	bc_num_copy(b, x0);
	if (b->scale > realscale) bc_num_truncate(b, b->scale - realscale);

	assert(!BC_NUM_NEG(b) || BC_NUM_NONZERO(b));
	assert(BC_NUM_RDX_VALID(b));
	assert(BC_NUM_RDX_VAL(b) <= b->len || !b->len);
	assert(!b->len || b->num[b->len - 1] || BC_NUM_RDX_VAL(b) == b->len);

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&fprime);
	bc_num_free(&f);
	bc_num_free(&num2);
	bc_num_free(&num1);
	BC_LONGJMP_CONT(vm);
}

void
bc_num_divmod(BcNum* a, BcNum* b, BcNum* c, BcNum* d, size_t scale)
{
	size_t ts, len;
	BcNum *ptr_a, num2;
	// This is volatile to quiet a warning on GCC about clobbering with
	// longjmp().
	volatile bool init = false;
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	// The bulk of this function is just doing what bc_num_binary() does for the
	// binary operators. However, it assumes that only c and a can be equal.

	// Set up the parameters.
	ts = BC_MAX(scale + b->scale, a->scale);
	len = bc_num_mulReq(a, b, ts);

	assert(a != NULL && b != NULL && c != NULL && d != NULL);
	assert(c != d && a != d && b != d && b != c);

	// Initialize or expand as necessary.
	if (c == a)
	{
		// NOLINTNEXTLINE
		memcpy(&num2, c, sizeof(BcNum));
		ptr_a = &num2;

		BC_SIG_LOCK;

		bc_num_init(c, len);

		init = true;

		BC_SETJMP_LOCKED(vm, err);

		BC_SIG_UNLOCK;
	}
	else
	{
		ptr_a = a;
		bc_num_expand(c, len);
	}

	// Do the quick version if possible.
	if (BC_NUM_NONZERO(a) && !BC_NUM_RDX_VAL(a) && !BC_NUM_RDX_VAL(b) &&
	    b->len == 1 && !scale)
	{
		BcBigDig rem;

		bc_num_divArray(ptr_a, (BcBigDig) b->num[0], c, &rem);

		assert(rem < BC_BASE_POW);

		d->num[0] = (BcDig) rem;
		d->len = (rem != 0);
	}
	// Do the slow method.
	else bc_num_r(ptr_a, b, c, d, scale, ts);

	assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
	assert(BC_NUM_RDX_VALID(c));
	assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
	assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);
	assert(!BC_NUM_NEG(d) || BC_NUM_NONZERO(d));
	assert(BC_NUM_RDX_VALID(d));
	assert(BC_NUM_RDX_VAL(d) <= d->len || !d->len);
	assert(!d->len || d->num[d->len - 1] || BC_NUM_RDX_VAL(d) == d->len);

err:
	// Only cleanup if we initialized.
	if (init)
	{
		BC_SIG_MAYLOCK;
		bc_num_free(&num2);
		BC_LONGJMP_CONT(vm);
	}
}

void
bc_num_modexp(BcNum* a, BcNum* b, BcNum* c, BcNum* restrict d)
{
	BcNum base, exp, two, temp, atemp, btemp, ctemp;
	BcDig two_digs[2];
#if BC_ENABLE_LIBRARY
	BcVm* vm = bcl_getspecific();
#endif // BC_ENABLE_LIBRARY

	assert(a != NULL && b != NULL && c != NULL && d != NULL);
	assert(a != d && b != d && c != d);

	if (BC_ERR(BC_NUM_ZERO(c))) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);
	if (BC_ERR(BC_NUM_NEG(b))) bc_err(BC_ERR_MATH_NEGATIVE);

#if BC_DEBUG || BC_GCC
	// This is entirely for quieting a useless scan-build error.
	btemp.len = 0;
	ctemp.len = 0;
#endif // BC_DEBUG || BC_GCC

	// Eliminate fractional parts that are zero or error if they are not zero.
	if (BC_ERR(bc_num_nonInt(a, &atemp) || bc_num_nonInt(b, &btemp) ||
	           bc_num_nonInt(c, &ctemp)))
	{
		bc_err(BC_ERR_MATH_NON_INTEGER);
	}

	bc_num_expand(d, ctemp.len);

	BC_SIG_LOCK;

	bc_num_init(&base, ctemp.len);
	bc_num_setup(&two, two_digs, sizeof(two_digs) / sizeof(BcDig));
	bc_num_init(&temp, btemp.len + 1);
	bc_num_createCopy(&exp, &btemp);

	BC_SETJMP_LOCKED(vm, err);

	BC_SIG_UNLOCK;

	bc_num_one(&two);
	two.num[0] = 2;
	bc_num_one(d);

	// We already checked for 0.
	bc_num_rem(&atemp, &ctemp, &base, 0);

	// If you know the algorithm I used, the memory-efficient method, then this
	// loop should be self-explanatory because it is the calculation loop.
	while (BC_NUM_NONZERO(&exp))
	{
		// Num two cannot be 0, so no errors.
		bc_num_divmod(&exp, &two, &exp, &temp, 0);

		if (BC_NUM_ONE(&temp) && !BC_NUM_NEG_NP(temp))
		{
			assert(BC_NUM_RDX_VALID(d));
			assert(BC_NUM_RDX_VALID_NP(base));

			bc_num_mul(d, &base, &temp, 0);

			// We already checked for 0.
			bc_num_rem(&temp, &ctemp, d, 0);
		}

		assert(BC_NUM_RDX_VALID_NP(base));

		bc_num_mul(&base, &base, &temp, 0);

		// We already checked for 0.
		bc_num_rem(&temp, &ctemp, &base, 0);
	}

err:
	BC_SIG_MAYLOCK;
	bc_num_free(&exp);
	bc_num_free(&temp);
	bc_num_free(&base);
	BC_LONGJMP_CONT(vm);
	assert(!BC_NUM_NEG(d) || d->len);
	assert(BC_NUM_RDX_VALID(d));
	assert(!d->len || d->num[d->len - 1] || BC_NUM_RDX_VAL(d) == d->len);
}

#if BC_DEBUG_CODE
void
bc_num_printDebug(const BcNum* n, const char* name, bool emptyline)
{
	bc_file_puts(&vm->fout, bc_flush_none, name);
	bc_file_puts(&vm->fout, bc_flush_none, ": ");
	bc_num_printDecimal(n, true);
	bc_file_putchar(&vm->fout, bc_flush_err, '\n');
	if (emptyline) bc_file_putchar(&vm->fout, bc_flush_err, '\n');
	vm->nchars = 0;
}

void
bc_num_printDigs(const BcDig* n, size_t len, bool emptyline)
{
	size_t i;

	for (i = len - 1; i < len; --i)
	{
		bc_file_printf(&vm->fout, " %lu", (unsigned long) n[i]);
	}

	bc_file_putchar(&vm->fout, bc_flush_err, '\n');
	if (emptyline) bc_file_putchar(&vm->fout, bc_flush_err, '\n');
	vm->nchars = 0;
}

void
bc_num_printWithDigs(const BcNum* n, const char* name, bool emptyline)
{
	bc_file_puts(&vm->fout, bc_flush_none, name);
	bc_file_printf(&vm->fout, " len: %zu, rdx: %zu, scale: %zu\n", name, n->len,
	               BC_NUM_RDX_VAL(n), n->scale);
	bc_num_printDigs(n->num, n->len, emptyline);
}

void
bc_num_dump(const char* varname, const BcNum* n)
{
	ulong i, scale = n->scale;

	bc_file_printf(&vm->ferr, "\n%s = %s", varname,
	               n->len ? (BC_NUM_NEG(n) ? "-" : "+") : "0 ");

	for (i = n->len - 1; i < n->len; --i)
	{
		if (i + 1 == BC_NUM_RDX_VAL(n))
		{
			bc_file_puts(&vm->ferr, bc_flush_none, ". ");
		}

		if (scale / BC_BASE_DIGS != BC_NUM_RDX_VAL(n) - i - 1)
		{
			bc_file_printf(&vm->ferr, "%lu ", (unsigned long) n->num[i]);
		}
		else
		{
			int mod = scale % BC_BASE_DIGS;
			int d = BC_BASE_DIGS - mod;
			BcDig div;

			if (mod != 0)
			{
				div = n->num[i] / ((BcDig) bc_num_pow10[(ulong) d]);
				bc_file_printf(&vm->ferr, "%lu", (unsigned long) div);
			}

			div = n->num[i] % ((BcDig) bc_num_pow10[(ulong) d]);
			bc_file_printf(&vm->ferr, " ' %lu ", (unsigned long) div);
		}
	}

	bc_file_printf(&vm->ferr, "(%zu | %zu.%zu / %zu) %lu\n", n->scale, n->len,
	               BC_NUM_RDX_VAL(n), n->cap, (unsigned long) (void*) n->num);

	bc_file_flush(&vm->ferr, bc_flush_err);
}
#endif // BC_DEBUG_CODE