//	Zinc Application Framework - Z_BNUM.CPP
//	COPYRIGHT (C) 1990-1999.  All Rights Reserved.
//	Zinc Software Incorporated.  Pleasant Grove, Utah  USA

#include <z_bnum.hpp>
#include <z_ctype.hpp>
#include <z_lang.hpp>
#include <z_real.hpp>
#include <z_stdlib.hpp>
#include <z_stdarg.hpp>
#include <z_string.hpp>
#define ZAF_BIGNUM_DATA_INFO
#include "gbl_def.cpp"

// WARNING: This must change if ZAF_DIGITS changes
// WHOLE_WORD is 10^ZAF_DIGITS, MOD_WORD is sqrt(WHOLE_WORD)
#if (ZAF_DIGITS == 8)
	const ZafNumber WHOLE_WORD = 100000000U;
	const ZafNumber MOD_WORD = 10000U;
#elif (ZAF_DIGITS == 4)
	const ZafNumber WHOLE_WORD = 10000U;
	const ZafNumber MOD_WORD = 100U;
#endif

const ZafNumber MAXSTORED = (ZafNumber)(WHOLE_WORD - 1);

#define LENGTHOF(x)	((int)(sizeof(x)/sizeof((x)[0])))

// TO DO
// sqrt

// DONE
// add		*
// sub		*
// neg		-
// abs		-
// zero		-
// ceil		-
// floor	-
// truncate	-
// round	-
// >		*
// >=		*
// <		*
// <=		*
// ==		*
// !=		*
// mul		*
// div		*
// rem		*
// ascii to ui_num
// ui_num to ascii
// underflow/overflow exceptions

static ZafNumber poten[ZAF_DIGITS+1] = {
	1,		// 0
#if (ZAF_DIGITS > 0)
	10,		// 1
#endif
#if (ZAF_DIGITS > 1)
	100,		// 2
#endif
#if (ZAF_DIGITS > 2)
	1000,		// 3
#endif
#if (ZAF_DIGITS > 3)
	10000,		// 4
#endif
#if (ZAF_DIGITS > 4)
	100000,		// 5
#endif
#if (ZAF_DIGITS > 5)
	1000000,	// 6
#endif
#if (ZAF_DIGITS > 6)
	10000000,	// 7
#endif
#if (ZAF_DIGITS > 7)
	100000000,	// 8
#endif
#if (ZAF_DIGITS > 8)
	1000000000,	// 9
#endif
#if (ZAF_DIGITS > 9)
	10000000000,	// 10
#endif
};

static ZafIChar _bnumSpaceString[] 	= { ' ', 0 };
static ZafIChar _bnumBlankString[] 	= { 0 };
static ZafIChar _bignumStringFormat[]	= { '%', 'B', 0 };

// ----- ZafBignumData ------------------------------------------------------

ZafBignumData::ZafBignumData(void) :
	ZafFormatData()
{
	// Check the printf binding.
	Bind();

	Clear();
}

ZafBignumData::ZafBignumData(long zValue) :
	ZafFormatData()
{
	// Check the printf binding.
	Bind();
	SetBignum(zValue);
}

ZafBignumData::ZafBignumData(const ZafIChar *string, const ZafIChar *format) :
	ZafFormatData()
{
	// Check the printf binding.
	Bind();
	Sscanf(string, (format && format[0]) ? format : _bignumStringFormat);
}

ZafBignumData::ZafBignumData(const ZafBignumData &copy) :
	ZafFormatData(copy)
{
	// Check the printf binding.
	Bind();
	SetBignum(copy);
}

ZafBignumData::~ZafBignumData(void)
{
	// No information needs to be deleted.
}

void ZafBignumData::Bind(void)
{
	// Bind in the sprintf characters.
#if defined(ZAF_INDEPENDENT)
#	define bound zafBignumData_bound
	extern bool bound;
#else
	static bool bound = false;
#endif
	if (!bound)
	{
		// Check for a valid locale.
		if (!zafLocale)
			ZafI18nData::I18nAllocate();

		// Set the lookup characters.
		bound = true;
/* START BLOCK COMMENT
**			ZafStandardArg::SetSprintf('B', ZafBignumData::Format);
**			ZafStandardArg::SetSscanf('B', ZafBignumData::Parse);
END BLOCK COMMENT */
		ZafFormatData::SetSprintf('B', ZafBignumData::Format);
		ZafFormatData::SetSscanf('B', ZafBignumData::Parse);

		// Bind in the real-data lookup characters.
		ZafRealData::Bind();
	}
}

void ZafBignumData::Clear(void)
{
	// Zero out the value.
	PushLevel();
	sign = 0;
	for (int i = 0; i < LENGTHOF(num); i++)
		num[i] = 0;
	SetError(ZAF_ERROR_NONE);
	PopLevel();
}

ZafData *ZafBignumData::Duplicate(void)
{
	return (new ZafBignumData(*this));
}

bool ZafBignumData::IsA(ZafClassID compareID) const
{
	return ((compareID == classID) ? true : ZafFormatData::IsA(compareID));
}

bool ZafBignumData::IsA(ZafClassName compareName) const
{
	return (!strcmp(compareName, className) ? true : ZafFormatData::IsA(compareName));
}

int ZafBignumData::FormattedText(ZafIChar *buffer, int maxLength, const ZafIChar *format) const
{
	// Format the text.
	return (Sprintf(buffer, maxLength, format ? format : _bignumStringFormat));
}

ZafError ZafBignumData::SetBignum(const ZafIChar *buffer, const ZafIChar *format)
{
	// Reset the value.
	PushLevel();
	if (!buffer || !buffer[0])
		Clear();
	else if (!Sscanf(buffer, (format && format[0]) ? format : _bignumStringFormat))
		SetError(ZAF_ERROR_INVALID);
	else
		SetError(ZAF_ERROR_NONE);
	PopLevel();

	// Return the error status.
	return (Error());
}

//---------------------------------------------------------------------------
// Helper routines

// Add two bignums, ignoring sign.  This is used by both add
// and subtract routines, and each defines how the carry is set
// coming in.  Returns a new carry.
int ZafBignumData::DoAddLoop(const ZafNumber *aw, int carry)
{
	if (aw)
		aw += LENGTHOF(num)-1;
	ZafNumber *r = &num[LENGTHOF(num)-1];
	for (int i=0; i < LENGTHOF(num); i++)
	{
		*r += (ZafNumber)carry;
		if (aw)
			*r += *aw--;
		carry = (*r > MAXSTORED);
		if (carry)
			*r -= (ZafNumber)(MAXSTORED+1);
		r--;
	}
	return (carry);
}

// Replace a number with its nines-complement.
void ZafBignumData::NinesComplement(void)
{
	ZafNumber *r = num;
	for (int i=0; i < LENGTHOF(num); i++, r++)
		*r = (ZafNumber)(MAXSTORED - *r);
}

// Copy a number and add to it.
ZafError ZafBignumData::AddSameSign(const ZafBignumData &b)
{
	if (DoAddLoop(b.num, 0))
		return (SetError(ZAF_ERROR_OUT_OF_RANGE));
	return (ZAF_ERROR_NONE);
}

// Add two bignums of different sign (or subtract like signed values).
ZafError ZafBignumData::AddDiffSign(const ZafBignumData &b)
{
	ZafNumber tmpValue = 0;

	int i = 0;
	for (; i < LENGTHOF(num); i++)
		if ((tmpValue = (ZafNumber)(num[i] - b.num[i])) != 0)
			break;
	if (i >= LENGTHOF(num))
	{
		Clear();
		return (ZAF_ERROR_NONE);
	}
	ZafBignumData tmp = b;
	if (tmpValue > 0)
	{
		tmp = *this;
		*this = b;
	}
	sign = tmp.sign;
	// set 9's compliment
	NinesComplement();
	i = DoAddLoop(tmp.num, 1);
	if (i == 0)
	{
		NinesComplement();
		i = DoAddLoop(ZAF_NULLP(ZafNumber), 1);
		sign = 1-sign;
		i = 1-i;
	}
	if (i == 0)
		return (SetError(ZAF_ERROR_OUT_OF_RANGE));
	return (ZAF_ERROR_NONE);
}

// Compare two bignums.  Return appropriate value.
bool ZafBignumData::Compare(const ZafBignumData &b, bool gt, bool ls, bool eq) const
{
	if (sign < b.sign)
		return (gt);
	if (sign > b.sign)
		return (ls);
	for (int i=0; i < LENGTHOF(num); i++)
	{
		if (num[i] > b.num[i])
			return (sign ? ls : gt);
		if (num[i] < b.num[i])
			return (sign ? gt : ls);
	}
	return (eq);
}

// If this bignum is zero, clear the sign flag.
void ZafBignumData::CheckZero(void)
{
	// Don't allow "-0", it is flag for empty
	for (int i=0; i < LENGTHOF(num); i++)
		if (num[i] != 0)
			return;
	sign = 0;
}

//---------------------------------------------------------------------------

void ZafBignumData::Abs(void)
{
	sign = 0;
}

ZafBignumData ZafBignumData::DivMod(const ZafBignumData &div)
// This algorithm comes from 'The Art of Computer Programming, Volume 2,
// Seminumerical Algorithms, Second Edition'; Donald Knuth, page 257,
// algorithm D.  Notation follows the book as close as possible.
{
	// D1
	int i;
	for (i=0; i < LENGTHOF(num); i++)
		if (div.num[i] != 0) break;
	if (i == LENGTHOF(num)-1)
	{
		SetError(ZAF_ERROR_OUT_OF_RANGE);
		return (*this);
	}
#define TOPSIZE	(2*LENGTHOF(num)+1)
	ZafNumber u[TOPSIZE], v[LENGTHOF(num)+1];
	int n = LENGTHOF(num) - i;
	int shift = n- ZAF_NUMBER_DECIMAL/ZAF_DIGITS - 1;
	int k; 
	for (k=0; k < LENGTHOF(v); k++)
		v[k] = 0;
	for (k=i; k < LENGTHOF(num); k++)
		v[k-i+1] = div.num[k];
	for (i=0; i < LENGTHOF(u); i++)
		u[i] = 0;
	for (i=0; i < LENGTHOF(num); i++)
		u[i+1] = num[i];
	ZafNumber d = (ZafNumber)(WHOLE_WORD / (v[1]+1));
	if (d != (ZafNumber)1)
	{
		int ucarry = 0, vcarry = 0;
		for (int l=LENGTHOF(num); l > 0; l--)
		{
			long tmp;
			tmp = u[l];
			tmp *= d;
			tmp += ucarry;
			ucarry = (int)(tmp / WHOLE_WORD);
			u[l] = (ZafNumber)(tmp % WHOLE_WORD);
			tmp = v[l];
			tmp *= d;
			tmp += vcarry;
			vcarry = (int)(tmp / WHOLE_WORD);
			v[l] = (ZafNumber)(tmp % WHOLE_WORD);
		}
	}
	// D2
	int j = 0;
#define m	LENGTHOF(num)
	do {
		// D3
		long qhat, rhat;
		if (u[j] == v[1])
		{
			rhat = WHOLE_WORD - 1;
			qhat = u[j+1];
		}
		else
		{
			// qhat = (u[j] * WHOLE_WORD + u[j+1]) / v[1];
			// rhat = (u[j] * WHOLE_WORD + u[j+1]) rem v[1];
			qhat = u[j];
			qhat *= WHOLE_WORD;
			qhat += u[j+1];
			rhat = qhat % v[1];
			qhat /= v[1];
		}
		while (qhat*v[2] > rhat*WHOLE_WORD + u[j+2])
		{
			qhat--;
			rhat += v[1];
		}
		// D4
		// u[j:j+n] -= qhat * v[1:n];
		int carry = 0;
		for (int l=n; l > 0; l--)
		{
			while (u[l+j] > WHOLE_WORD)
			{
				u[l+j] += WHOLE_WORD;
				u[l+j-1]--;
			}
			ZafNumber tmp = u[l+j];
			while (tmp < (ZafNumber)qhat * v[l])
			{
				tmp += WHOLE_WORD;
				u[l+j-1]--;
			}
			u[l+j] = (ZafNumber)(tmp - qhat * v[l]);
		}
		u[j] -= (ZafNumber)carry;
		// D5
		// q[j] = qhat;
		num[j+shift] = (ZafNumber)qhat;
		if  (carry)
		{
			// D6
			// q[j]--;
			num[j+shift]--;
			// u[j:j+n] += v[1:n];
			for (int l=n; l > 0; l--)
			{
				ZafNumber tmp = u[l+j];
				tmp += v[l];
				while (tmp >= WHOLE_WORD)
				{
					tmp -= WHOLE_WORD;
					u[l+j-1]++;
				}
				u[l+j] = (ZafNumber)tmp;
			}
		}
		// D7
		j++;
	} while (j+shift < m);
	// D8
	// num = q[0:m]		// we did our work into num
	// rem = u[m+1:m+n] / d;
	ZafBignumData rem;
	long tmp = 0;
	for (i=0; i < LENGTHOF(num); i++)
	{
		tmp *= WHOLE_WORD;
		tmp += u[i+1];
		rem.num[i] = (ZafNumber)(tmp / d);
		tmp %= d;
	}
	rem.sign = sign;
	sign = (sign != div.sign);
	return (rem);
}

// Calculate the Floor (nsign = 1) or the Ceiling (nsign = 0).
void ZafBignumData::FloorCeil(int nsign)
{
	int j = LENGTHOF(num) - (ZAF_NUMBER_DECIMAL+ZAF_DIGITS) / ZAF_DIGITS;
	int k = ZAF_NUMBER_DECIMAL % ZAF_DIGITS;
	ZafNumber tmpValue = (ZafNumber)(num[j] % poten[k]);
	num[j] -= tmpValue;
	if (k == 0)
		// Can't use the ?: operator here because GNC++ 2.5.8 is easily confused.
		if (j+1 < LENGTHOF(num))
			tmpValue = num[j+1];
		else
			tmpValue = 0;
	int i = j + 1;
	for (; i < LENGTHOF(num); i++)
		num[i] = 0;
	if ((sign == nsign) && tmpValue != 0)
	{
		ZafNumber n[LENGTHOF(num)];

		for (i=0; i < LENGTHOF(n); i++)
			n[i] = 0;
		n[j] = poten[k];
		DoAddLoop(n, 0);
	}
}

void ZafBignumData::Round(int places)
{
	places = ZAF_NUMBER_DECIMAL - places;
	if (places <= 0)
		return;
	if (places > ZAF_NUMBER_DECIMAL + ZAF_NUMBER_WHOLE)
	{
		Clear();
		return;
	}
	int j = LENGTHOF(num) - (places+ZAF_DIGITS) / ZAF_DIGITS;
	int k = (places+ZAF_DIGITS) % ZAF_DIGITS;
	ZafNumber tmpValue;
	if (k == 0)
	{
		tmpValue = (ZafNumber)(num[j+1] % poten[ZAF_DIGITS]);
		k = ZAF_DIGITS;
	}
	else
	{
		tmpValue = (ZafNumber)(num[j] % poten[k]);
		num[j] -= tmpValue;
	}
	int i = j + 1;
	for (; i < LENGTHOF(num); i++)
		num[i] = 0;
	if (tmpValue >= poten[k] / 2)
	{
		ZafNumber n[LENGTHOF(num)];

		for (i=0; i < LENGTHOF(n); i++)
			n[i] = 0;
		n[j] = (k == ZAF_DIGITS ? poten[0] : poten[k]);
		DoAddLoop(n, 0);
	}
	CheckZero();
}

void ZafBignumData::Truncate(int places)
{
	places = ZAF_NUMBER_DECIMAL - places;
	if (places <= 0)
		return;
	if (places > ZAF_NUMBER_DECIMAL + ZAF_NUMBER_WHOLE)
	{
		Clear();
		return;
	}
	int j = LENGTHOF(num) - (places+ZAF_DIGITS) / ZAF_DIGITS;
	for (int i=j+1; i < LENGTHOF(num); i++)
		num[i] = 0;
#if defined(__SC__) && defined(DOS386)
	// This seems to prevent the optimizer from not compiling the
	// other line right.
	int tmp = poten[places % ZAF_DIGITS];
	num[j] -= (num[j] % tmp);
#else
	num[j] -= (ZafNumber)(num[j] % poten[places % ZAF_DIGITS]);
#endif
	CheckZero();
}

// Support for mixed mode (number op int) operations
void ZafBignumData::Itob(long value)
{
	Clear();

	if (value < 0)
	{
		sign = 1;
		value = -value;
	}
	ZafNumber *numbase = &num[LENGTHOF(num)-1-(ZAF_NUMBER_DECIMAL/ZAF_DIGITS)];
#if ZAF_DIGITS == 4
#	if (ZAF_NUMBER_DECIMAL % ZAF_DIGITS == 0)
	numbase[0]  = (ZafNumber)(value % WHOLE_WORD);
	numbase[-1] = (ZafNumber)((value / WHOLE_WORD) % WHOLE_WORD);
	numbase[-2] = (ZafNumber)((value / WHOLE_WORD) / WHOLE_WORD);
#	else
	long potbase = poten[ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	long potpowr = poten[ZAF_DIGITS-ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	numbase[0]  = (ZafNumber)((value % potpowr) * potbase);
	numbase[-1] = (ZafNumber)((value / potpowr) % WHOLE_WORD);
	numbase[-2] = (ZafNumber)(((value / potpowr) / WHOLE_WORD) % WHOLE_WORD);
	numbase[-3] = (ZafNumber)(((value / potpowr) / WHOLE_WORD) / WHOLE_WORD);
#	endif
#endif
#if ZAF_DIGITS == 8
#	if (ZAF_NUMBER_DECIMAL % ZAF_DIGITS == 0)
	numbase[0]  = (ZafNumber)(value % WHOLE_WORD);
	numbase[-1] = (ZafNumber)(value / WHOLE_WORD);
#	else
	long potbase = poten[ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	long potpowr = poten[ZAF_DIGITS-ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	numbase[0]  = (ZafNumber)((value % potpowr) * potbase);
	numbase[-1] = (ZafNumber)((value / potpowr) % WHOLE_WORD);
	numbase[-2] = (ZafNumber)((value / potpowr) / WHOLE_WORD);
#	endif
#endif
}

//--------------------------------------------------------------------------
// Conversion routines

long ZafBignumData::IValue(void) const
{
	long l;

	const ZafNumber *numbase = &num[LENGTHOF(num)-1-(ZAF_NUMBER_DECIMAL/ZAF_DIGITS)];
#if ZAF_DIGITS == 4
#	if (ZAF_NUMBER_DECIMAL % ZAF_DIGITS == 0)
	l = numbase[0] + (ZafInt32)numbase[-1] * WHOLE_WORD;
#	else
	long potbase = poten[ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	long potpowr = poten[ZAF_DIGITS-ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	l = (numbase[0] / potbase) + ((ZafInt32)numbase[-1] * potpowr) +
		(ZafInt32)(numbase[-2] % potbase) * potpowr * WHOLE_WORD;
#	endif
#endif
#if ZAF_DIGITS == 8
#	if (ZAF_NUMBER_DECIMAL % ZAF_DIGITS == 0)
	l = numbase[0];
#	else
	long potbase = poten[ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	long potpowr = poten[ZAF_DIGITS-ZAF_NUMBER_DECIMAL%ZAF_DIGITS];
	l = (numbase[0] / potbase) + (numbase[-1] % potbase) * potpowr;
#	endif
#endif
	return (sign ? -l : l);
}

ZafError ZafBignumData::SetBignum(const ZafBignumData &copy)
{
	// Reset the value.
	PushLevel();
	memcpy(num, copy.num, sizeof(num));
	sign = copy.sign;
	PopLevel();

	// Return success.
	return (ZAF_ERROR_NONE);
}

ZafError ZafBignumData::SetBignum(long value)
{
	// Reset the value.
	PushLevel();
	Itob(value);
	PopLevel();

	// Return success.
	return (ZAF_ERROR_NONE);
}

// ----- Operators ----------------------------------------------------------

ZafBignumData ZafBignumData::operator++(void)
{
	// Reset the value.
	PushLevel();
	*this += 1L;
	PopLevel();

	// Return a reference pointer.
	return *this;
}

ZafBignumData ZafBignumData::operator++(int)
{
	// Reset the value.
	PushLevel();
	ZafBignumData tmp = *this;
	*this += 1L;
	PopLevel();

	// Return a temporary reference pointer.
	return tmp;
}

ZafBignumData ZafBignumData::operator--(void)
{
	// Reset the value.
	PushLevel();
	*this -= 1L;
	PopLevel();

	// Return a reference pointer.
	return *this;
}

ZafBignumData ZafBignumData::operator--(int)
{
	// Reset the value.
	PushLevel();
	ZafBignumData tmp = *this;
	*this -= 1L;
	PopLevel();

	// Return a temporary reference pointer.
	return tmp;
}

ZafBignumData &ZafBignumData::operator=(const ZafBignumData &number)
{
	SetBignum(number);
	return *this;
}

ZafBignumData &ZafBignumData::operator=(long value)
{
	SetBignum(value);
	return *this;
}

ZafBignumData &ZafBignumData::operator=(double value)
{
	SetBignum(value);
	return *this;
}

ZafBignumData &ZafBignumData::operator+=(const ZafBignumData &number)
{
	// Reset the value.
	PushLevel();
	if (sign == number.sign)
		AddSameSign(number);
	else
		AddDiffSign(number);
	PopLevel();

	// Return a reference pointer.
	return (*this);
}

ZafBignumData &ZafBignumData::operator-=(const ZafBignumData &number)
{
	// Reset the value.
	PushLevel();
	if (sign != number.sign)
		AddSameSign(number);
	else
		AddDiffSign(number);
	PopLevel();

	// Return a reference pointer.
	return (*this);
}

ZafBignumData &ZafBignumData::operator*=(const ZafBignumData &number)
// If we have two 2-word bignum, A and B, we can break the multiplication
// problem down into the following:
//    A = K^3*A0 + K^2*A1 + K*A2 + A3 and
//    B = K^3*B0 + K^2*B1 + K*B2 + B3,
// where K is a half word modulus (sqrt(WHOLE_WORD)).  The solution for
// (A*B) is now:
//    K^6*(A0*B0) +
//    K^5*(A0*B1 + A1*B0) +
//    K^4*(A0*B2 + A1*B1 + A2*B0) +
//    K^3*(A0*B3 + A1*B2 + A2*B1 + A3*B0) +
//    K^2*(A1*B3 + A2*B2 + A3*B1) +
//    K^1*(A2*B3 + A3*B2) +
//    K^0*(A3*B3)
// We can also optimize this by checking for overflow before multiplying
// and not working on the truncated digits.
{
	// Reset the value.
	PushLevel();
#define XTENDED	(2*LENGTHOF(num))
#define RESULT	(2*XTENDED)
	int i, j, carry;
	ZafNumber ax[XTENDED], bx[XTENDED], rx[RESULT], *ap, *rp;
	const ZafNumber *bp;

	// split number, initialize arrays
	for (i=0, ap = &num[0], bp = &number.num[0];
	     i < LENGTHOF(num); i++, ap++, bp++)
	{
		ax[2*i+1] = (ZafNumber)(*ap % MOD_WORD);
		ax[2*i+0] = (ZafNumber)(*ap / MOD_WORD);
		bx[2*i+1] = (ZafNumber)(*bp % MOD_WORD);
		bx[2*i+0] = (ZafNumber)(*bp / MOD_WORD);
	}

	// init for summation
	for (i = 0, rp = rx; i < LENGTHOF(rx); i++, rp++)
		*rp = (ZafNumber)0;

	// cross multiply
	for (i=0, ap = ax; i < LENGTHOF(ax); i++, ap++)
		for (j=0, bp = bx; j < LENGTHOF(bx); j++, bp++)
		{
			// Using temps because of bug in Symantec 7.0 on the Macintosh.
			ZafNumber aTemp = *ap;
			ZafNumber bTemp = *bp;
			rx[i+j+1] += (ZafNumber)(aTemp * bTemp);
		}

	// combine terms (doing this first makes propogate-carry shorter)
	for (i=LENGTHOF(rx)-2; i > 0; i -= 2)
	{
		ax[i >> 1] = (ZafNumber)(rx[i+1] + (rx[i] % MOD_WORD) * MOD_WORD);

		// Not using += because of bug in Symantec 7.0 on the Macintosh.
		rx[i-1] = (ZafNumber)(rx[i-1] + (rx[i] / MOD_WORD));
	}

	// propogate carry
	for (i=LENGTHOF(ax)-1, ap = ax + i; i > 0; i--, ap--)
		if (*ap >= WHOLE_WORD)
		{
			ap[-1] += (ZafNumber)(*ap / WHOLE_WORD);
			*ap %= WHOLE_WORD;
		}
	if (ax[0] >= MOD_WORD)
	{
		SetError(ZAF_ERROR_OUT_OF_RANGE);
		return (*this);
	}

	// cut ZAF_NUMBER_DECIMAL / ZAF_DIGITS words out of result
	// cut ZAF_NUMBER_DECIMAL % ZAF_DIGITS digits out of that result
	// round the whole thing
#if (ZAF_NUMBER_DECIMAL % ZAF_DIGITS == 0)
	carry = ax[LENGTHOF(ax)-(ZAF_NUMBER_DECIMAL/ZAF_DIGITS)] % poten[ZAF_DIGITS-1] >= 5;
#else
	carry = ax[LENGTHOF(ax)-(ZAF_NUMBER_DECIMAL/ZAF_DIGITS)] % poten[ZAF_NUMBER_DECIMAL % ZAF_DIGITS - 1] >= (poten[ZAF_NUMBER_DECIMAL % ZAF_DIGITS] >> 1);
#endif
	for (j=LENGTHOF(num)-1,
	     i=LENGTHOF(ax)-1-(ZAF_NUMBER_DECIMAL/ZAF_DIGITS), ap = ax + i;
	     j >= 0; j--, i--, ap--)
	{
		*ap /= poten[ZAF_NUMBER_DECIMAL % ZAF_DIGITS];
		*ap += (ZafNumber)((ap[1] % poten[ZAF_NUMBER_DECIMAL % ZAF_DIGITS]) * poten[ZAF_DIGITS - ZAF_NUMBER_DECIMAL % ZAF_DIGITS] + carry);
		num[j] = *ap;
		carry = 0;
	}
	sign = (sign != number.sign);
	PopLevel();

	// Return a reference pointer.
	return (*this);
}

ZafBignumData &ZafBignumData::operator/=(const ZafBignumData &number)
{
	// Reset the value.
	PushLevel();
	DivMod(number);
	PopLevel();

	// Return a reference pointer.
	return (*this);
}

ZafBignumData &ZafBignumData::operator%=(const ZafBignumData &number)
{
	// Reset the value.
	PushLevel();
	*this = DivMod(number);
	PopLevel();

	// Return a reference pointer.
	return (*this);
}

// ----- Friend Operators ---------------------------------------------------

ZafBignumData operator+(const ZafBignumData &number1, const ZafBignumData &number2)
{
	ZafBignumData tmp = number1;
	tmp += number2;
	return tmp;
}
ZafBignumData operator+(const ZafBignumData &number, long value) { return (number + ZafBignumData(value)); }
ZafBignumData operator+(long value, const ZafBignumData &number) { return (ZafBignumData(value) + number); }
ZafBignumData operator+(const ZafBignumData &number, double value) { return (number + ZafBignumData(value)); }
ZafBignumData operator+(double value, const ZafBignumData &number) { return (ZafBignumData(value) + number); }

ZafBignumData operator-(const ZafBignumData &number1, const ZafBignumData &number2)
{
	ZafBignumData tmp = number1;
	tmp -= number2;
	return tmp;
}
ZafBignumData operator-(const ZafBignumData &number, long value) { return (number - ZafBignumData(value)); }
ZafBignumData operator-(long value, const ZafBignumData &number) { return (ZafBignumData(value) - number); }
ZafBignumData operator-(const ZafBignumData &number, double value) { return (number - ZafBignumData(value)); }
ZafBignumData operator-(double value, const ZafBignumData &number) { return (ZafBignumData(value) - number); }

ZafBignumData operator*(const ZafBignumData &number1, const ZafBignumData &number2)
{
	ZafBignumData tmp = number1;
	tmp *= number2;
	return tmp;
}
ZafBignumData operator*(const ZafBignumData &number, long value) { return (number * ZafBignumData(value)); }
ZafBignumData operator*(long value, const ZafBignumData &number) { return (ZafBignumData(value) * number); }
ZafBignumData operator*(const ZafBignumData &number, double value) { return (number * ZafBignumData(value)); }
ZafBignumData operator*(double value, const ZafBignumData &number) { return (ZafBignumData(value) * number); }

ZafBignumData operator/(const ZafBignumData &number1, const ZafBignumData &number2)
{
	ZafBignumData tmp = number1;
	tmp /= number2;
	return tmp;
}
ZafBignumData operator/(const ZafBignumData &number, long value) { return (number / ZafBignumData(value)); }
ZafBignumData operator/(long value, const ZafBignumData &number) { return (ZafBignumData(value) / number); }
ZafBignumData operator/(const ZafBignumData &number, double value) { return (number / ZafBignumData(value)); }
ZafBignumData operator/(double value, const ZafBignumData &number) { return (ZafBignumData(value) / number); }

ZafBignumData operator%(const ZafBignumData &number1, const ZafBignumData &number2)
{
	ZafBignumData tmp = number1;
	tmp %= number2;
	return tmp;
}
ZafBignumData operator%(const ZafBignumData &number, long value) { return (number % ZafBignumData(value)); }
ZafBignumData operator%(long value, const ZafBignumData &number) { return (ZafBignumData(value) % number); }
ZafBignumData operator%(const ZafBignumData &number, double value) { return (number % ZafBignumData(value)); }
ZafBignumData operator%(double value, const ZafBignumData &number) { return (ZafBignumData(value) % number); }

ZafBignumData abs(const ZafBignumData &number)
{
	ZafBignumData tmp = number;
	tmp.Abs();
	return (tmp);
}

ZafBignumData ceil(const ZafBignumData &number)
{
	ZafBignumData tmp = number;
	tmp.FloorCeil(0);
	return (tmp);
}

ZafBignumData floor(const ZafBignumData &number)
{
	ZafBignumData tmp = number;
	tmp.FloorCeil(1);
	return (tmp);
}

ZafBignumData round(const ZafBignumData &number, int places)
{
	ZafBignumData tmp = number;
	tmp.Round(places);
	return (tmp);
}

ZafBignumData truncate(const ZafBignumData &number, int places)
{
	ZafBignumData tmp = number;
	tmp.Truncate(places);
	return (tmp);
}

// ----- sprintf/sscanf functions -------------------------------------------

static ZafIChar *Copy(ZafIChar *to, const ZafIChar *from)
{
	if (*from)
	{
		const ZafIChar *_from = from + strlen(from);
		do {
			*--to = *--_from;
		} while (_from != from);
	}
	return (to);
}

void ZafBignumData::Format(va_list *argList, ZafIChar **ptrBuffer,
	ZafIChar, int flags, int width, int prec)
{
	int i, dgt, j, comma;
	ZafNumber tmp = 0;
	const ZafIChar *ps1, *pc, *ps, *ps2;
	const ZafIChar *ss2, *ss, *sc, *ss1;
	const ZafIChar *pt, *cm;
	const ZafIChar *t;
	const char *gp;
	int oldgp;
	const int maxCharValue = 127;

	ZafIChar *buffer = *ptrBuffer;
	ZafBignumData *bignum = va_arg(*argList, ZafBignumData *);
	ps1 = pc = ps = ps2 = ss1 = sc = ss = ss2 = pt = cm = _bnumBlankString;
	if (flags & ZAF_CURRENCYx)
	{
		pt = zafLocale->monDecimalSeparator;
		cm = zafLocale->monThousandsSeparator;
		gp = zafLocale->monGrouping;
		if (bignum->sign)
		{
			if (zafLocale->negCurrencyPrecedes)
			{
				pc = zafLocale->currencySymbol;
				if (zafLocale->negSpaceSeparation || (flags & ZAF_SPACEx))
					ps = _bnumSpaceString;
			}
			else
			{
				sc = zafLocale->currencySymbol;
				if (zafLocale->negSpaceSeparation || (flags & ZAF_SPACEx))
					ss = _bnumSpaceString;
			}
		}
		else
		{
			if (zafLocale->posCurrencyPrecedes)
			{
				pc = zafLocale->currencySymbol;
				if (zafLocale->posSpaceSeparation || (flags & ZAF_SPACEx))
					ps = _bnumSpaceString;
			}
			else
			{
				sc = zafLocale->currencySymbol;
				if (zafLocale->posSpaceSeparation || (flags & ZAF_SPACEx))
					ss = _bnumSpaceString;
			}
		}
		if (prec < 0)
			prec = zafLocale->fractionDigits;
	}
	else
	{
		pt = zafLocale->decimalSeparator;
		cm = zafLocale->thousandsSeparator;
		gp = zafLocale->grouping;
		if (prec < 0)
			prec = ZAF_NUMBER_DECIMAL;
	}
	if (bignum->sign)
	{
		i = zafLocale->negSignPrecedes;
		t = zafLocale->negativeSign;
		if (flags & ZAF_CREDIT)
			i = 0;
	}
	else
	{
		i = zafLocale->posSignPrecedes;
		if (flags & ZAF_PLUS)
			t = zafLocale->positiveSign;
		else
			t = _bnumBlankString;
	}
	switch (i)
	{
	case 0:
		if (bignum->sign)
		{
			ps1 = zafLocale->creditLeftParen;
			ss1 = zafLocale->creditRightParen;
		}
		else
		{
			ps1 = ps2 = _bnumSpaceString;
		}
		break;
	case 1:
		ps1 = t;
		break;
	case 2:
		ss1 = t;
		break;
	case 3:
		ps2 = t;
		break;
	case 4:
		ss2 = t;
		break;
	}
	// bigger than the output string?
	ZafIChar *buff = new ZafIChar[2*(ZAF_NUMBER_WHOLE+prec)];
	ZafIChar *cpos = &buff[(2*(ZAF_NUMBER_WHOLE+prec))-1];
	*cpos = '\0';
	cpos = Copy(cpos, ss1);
	cpos = Copy(cpos, sc);
	cpos = Copy(cpos, ss);
	cpos = Copy(cpos, ss2);

	bool tRound = false;
	t = cpos;		// to see if anything is added
	while (prec > ZAF_NUMBER_DECIMAL)
	{
		*--cpos = '0';
		prec--;
	}
	dgt = ZAF_NUMBER_DECIMAL;
	i = LENGTHOF(bignum->num);
	while (dgt > prec)
	{
		if (dgt % ZAF_DIGITS == 0)
		{
			i--;
			tmp = bignum->num[i];
		}
		if ((dgt - 1) == prec && (tmp % 10) > 4)
			tRound = true;
		tmp /= (ZafNumber)10;
		dgt--;
	}
	while (dgt > 0)
	{
		if (dgt % ZAF_DIGITS == 0)
		{
			i--;
			tmp = bignum->num[i];
		}
		*--cpos = (ZafIChar)((ZafIChar)(tmp % 10) + '0');
		if (tRound)
		{
			if (*cpos == '9')
				*cpos = '0';
			else
			{
				(*cpos)++;
				tRound = false;
			}
		}
		tmp /= (ZafNumber)10;
		dgt--;
	}
	if (cpos != t)
		cpos = Copy(cpos, pt);

	t = cpos;		// to see if anything is added
	j = 0;
	while (j < LENGTHOF(bignum->num) && bignum->num[j] == 0) j++;
	oldgp = (int)*gp;
	if (oldgp == 0 || !(flags & ZAF_COMMAS))
		oldgp = maxCharValue;
	else
		gp++;
	comma = 0;
	bool needsBreak = false;
	while (i >= j)
	{
		if (dgt % ZAF_DIGITS == 0)
		{
			i--;
			tmp = bignum->num[i];
		}
		*--cpos = (ZafIChar)((ZafIChar)(tmp % 10) + '0');
		tmp /= (ZafNumber)10;

/* START BLOCK COMMENT
**			if (i == j && tmp == 0)
END BLOCK COMMENT */
		if (i == j && tmp == 0 && !tRound)
			break;

		if (tRound)
		{
			if (*cpos == '9')
				*cpos = '0';
			else
			{
				(*cpos)++;
				tRound = false;
			}
			if (needsBreak)
				break;
			if (i == j && tmp == 0)
				needsBreak = true;
		}

		comma++;
		if (oldgp != maxCharValue && comma == oldgp)
		{
			cpos = Copy(cpos, cm);
			comma = 0;
			if (*gp)
				oldgp = (int)*gp++;
		}
		dgt--;
	}
	if (cpos == t)
		*--cpos = tRound ? '1' : '0';	// need a leading zero
	cpos = Copy(cpos, ps2);
	cpos = Copy(cpos, ps);
	cpos = Copy(cpos, pc);
	cpos = Copy(cpos, ps1);
	width = (int)(width - strlen(cpos));
	if (flags & ZAF_LADJUST)
	{
		strcpy(buffer, cpos);
		cpos = &buffer[strlen(cpos)];
		while (width > 0)
		{
			*cpos++ = ' ';
			width--;
		}
		*cpos = 0;
	}
	else
	{
		while (width > 0)
		{
			*--cpos = ' ';
			width--;
		}
		strcpy(buffer, cpos);
	}
	buffer += strlen(buffer);
	*ptrBuffer = buffer;
	delete []buff;
}

int ZafBignumData::Parse(va_list *argList, ZafIChar **ptrBuffer,
	ZafIChar, int flags, int, const ZafIChar **)
{
	ZafBignumData *bignum = va_arg(*argList, ZafBignumData *);
	ZafIChar *string = *ptrBuffer;

	bignum->Clear();

	enum ValidStringSym
	{
		decSep = 0,
		monDecSep,
		thouSep,
		monThouSep,
		currencySym,
		posSign,
		negSign,
		creditLeftParen,
		creditRightParen,
		lastSym
	};

	ZafIChar *validStr[lastSym + 1];

	const ZafIChar *decimalstr = zafLocale->decimalSeparator;
	const ZafIChar *monstr = zafLocale->monDecimalSeparator;
	if (!monstr[0])
		monstr = decimalstr;
	const ZafIChar *signstr = zafLocale->negativeSign;

	validStr[decSep] = (ZafIChar *)decimalstr;
	validStr[monDecSep] = (ZafIChar *)monstr;
	validStr[thouSep] = (ZafIChar *)zafLocale->thousandsSeparator;
	validStr[monThouSep] = (ZafIChar *)zafLocale->monThousandsSeparator;
	validStr[currencySym] = (ZafIChar *)zafLocale->currencySymbol;
	validStr[posSign] = (ZafIChar *)zafLocale->positiveSign;
	validStr[negSign] = (ZafIChar *)zafLocale->negativeSign;
	validStr[creditLeftParen] = zafLocale->creditLeftParen ? (ZafIChar *)zafLocale->creditLeftParen :
		(ZafIChar *)ZafLanguageManager::blankString;
	validStr[creditRightParen] = zafLocale->creditRightParen ? (ZafIChar *)zafLocale->creditRightParen :
		(ZafIChar *)ZafLanguageManager::blankString;
	validStr[lastSym] = ZAF_NULLP(ZafIChar);

	if ((flags & ZAF_NOSKIP) == 0)
		while (isspace(*string))
			string++;
	const ZafIChar *tmp = string;
	bignum->sign = (*string == '(');
	int signLen = strlen(signstr);
	while (*tmp && !bignum->sign)
	{
		if (strncmp(tmp, signstr, signLen) == 0)
			bignum->sign = 1;
		tmp++;
	}
	tmp = string;
	int decimal = 0;
#	if defined(ZAF_MACINTOSH)
	unsigned long len;
#	else
	int len;
#	endif
	bool validNum = true;
	int monLen = strlen(monstr);
	int decimalLen = strlen(decimalstr);
	while (*tmp &&
		strncmp(tmp, monstr, monLen) != 0 &&
		strncmp(tmp, decimalstr, decimalLen) != 0)
	{
		validNum = false;
		len = 0;
		if (isdigit(*tmp))
		{
			decimal++;
			tmp++;
		}
		else
		{
			ZafIChar **check;
			for (check = &validStr[decSep]; *check; check++)
			{
				len = strlen(*check);
				if (strncmp(tmp, *check, len) == 0)
					break;
			}
			if (*check == 0)
				break; // Invalid character
			else if (len == 0)
				tmp++;
			else
				tmp += len;
		}			
	}
	if (decimal > ZAF_NUMBER_WHOLE)
	{
		bignum->SetError(ZAF_ERROR_OUT_OF_RANGE);
		return (-1);
	}
	if (decimal == 0 && !validNum)
	{
		bignum->SetError(ZAF_ERROR_INVALID);
		return (-1);
	}
	int i = LENGTHOF(bignum->num) - (decimal + ZAF_NUMBER_DECIMAL + ZAF_DIGITS-1) / ZAF_DIGITS;
	int j = (decimal + ZAF_NUMBER_DECIMAL - 1) % ZAF_DIGITS;
	while (*string && i < LENGTHOF(bignum->num))
	{
		if (isdigit(*string))
		{
			bignum->num[i] += (ZafNumber)(poten[j] * (*string - '0'));
			string++;
		}
		else
		{
			len = 0;
			ZafIChar **check;
			for (check = &validStr[decSep]; *check; check++)
			{
				len = strlen(*check);
				if (strncmp(string, *check, len) == 0)
					break;
			}
			if (*check == 0)
				break; // Invalid character
			else if (len == 0)
				string++;
			else
				string += len;
			j++;
		}
		j--;
		if (j < 0)
		{
			j = ZAF_DIGITS-1;
			i++;
		}
	}
	bignum->CheckZero();
	*ptrBuffer = string;
	return 1;
}

// ----- Persistent functions -----------------------------------------------
#if defined(USE_ZAF_PERSISTENCE)
static ZafIChar _persistentFormat[] = ZAF_ITEXT("%B");

ZafBignumData::ZafBignumData(const ZafIChar *name, ZafDataPersistence &persist) :
	ZafFormatData(name, persist.PushLevel(className, classID, ZAF_PERSIST_FILE))
{
	Bind();

	// Read the data.
	if (persist.Error() == ZAF_ERROR_NONE)
		ZafBignumData::ReadData(persist);

	persist.PopLevel();
	if (persist.Error() != ZAF_ERROR_NONE)
		SetError(persist.Error());
}

ZafElement *ZafBignumData::Read(const ZafIChar *name, ZafDataPersistence &persist)
{
	return (new ZafBignumData(name, persist));
}

void ZafBignumData::ReadData(ZafDataPersistence &persist)
{
	// Read the data.
	ZafIChar bignumString[ZAF_MAXNAMELEN];
	ZafFile *file = persist.CurrentFile();
	*file >> bignumString;

	// Use canonical locale to parse bignum.
	ZafLocaleData *saveLocale = zafLocale;
	zafLocale = zafLocale->canonicalLocale;
	SetBignum(bignumString, _persistentFormat);
	zafLocale = saveLocale;
}

void ZafBignumData::Write(ZafDataPersistence &persist)
{
	// Write the object.
	ZafFormatData::Write(persist.PushLevel(className, classID, ZAF_PERSIST_FILE));
	if (persist.Error() == ZAF_ERROR_NONE)
		ZafBignumData::WriteData(persist);
	persist.PopLevel();
	if (persist.Error() != ZAF_ERROR_NONE)
		SetError(persist.Error());
}

void ZafBignumData::WriteData(ZafDataPersistence &persist)
{
	// Write the data.
	ZafIChar bignumString[ZAF_MAXNAMELEN];
	ZafLocaleData *saveLocale = zafLocale;
	zafLocale = zafLocale->canonicalLocale;
	FormattedText(bignumString, ZAF_MAXNAMELEN, _persistentFormat);
	zafLocale = saveLocale;
	ZafFile *file = persist.CurrentFile();
	*file << bignumString;
}
#endif
