
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//                               Long number                                 //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#include "..\include.h"

// temporary numbers (be aware of multitask - use TryLock to find free number!)
bignum	BigTempNum[BIGTEMPNUM]; // temporary numbers
CLock BigTempLock[BIGTEMPNUM]; // locks of numbers

///////////////////////////////////////////////////////////////////////////////
// get temporary number (return index)

int GetBigTemp()
{
	int i = 0;
	for (;;)
	{
		if (BigTempLock[i].TryLock()) return i;
		i++;
		if (i == BIGTEMPNUM)
		{
			i = 0;
			::Sleep(5);
		}
	}
}

///////////////////////////////////////////////////////////////////////////////
// free temporary number (-1=invalid)

void FreeBigTemp(int inx)
{
	if ((u32)inx < BIGTEMPNUM) BigTempLock[inx].Unlock();
}

///////////////////////////////////////////////////////////////////////////////
// constructor (intsize/decize = size of integer/decimal part in bytes)

bignum::bignum()
{
	m_Data = NULL;
	m_IntMax = 0;
	m_DecMax = 0;
	this->SetMaxSize(BIGDEFINT, BIGDEFDEC);
}

bignum::bignum(bint intsize, bint decsize)
{
	m_Data = NULL;
	m_IntMax = 0;
	m_DecMax = 0;
	this->SetMaxSize(intsize, decsize);
}

bignum::bignum(LPCTSTR text)
{
	m_Data = NULL;
	m_IntMax = 0;
	m_DecMax = 0;

	// length of text
	int len = (int)::strlen(text);
	if (len < 1)
	{
		this->SetMaxSize(BIGDEFINT, BIGDEFDEC);
		return;
	}

	// sign
	LPCTSTR t = text;
	if ((*t == '+') || (*t == '-')) t++;

	// calculate integer digits
	int intnum = 0;
	char ch;
	for (;;)
	{
		ch = *t;
		if ((ch < '0') || (ch > '9')) break;
		intnum++;
		t++;
	}

	// decimal
	if (*t == '.') t++;

	// calculate decimal digits
	int decnum = 0;
	for (;;)
	{
		ch = *t;
		if ((ch < '0') || (ch > '9')) break;
		decnum++;
		t++;
	}

	// initialize buffer
	this->SetMaxSize(((bint)((intnum + 5)*BITPERDIG)+7)/8, ((bint)((decnum + 10)*BITPERDIG)+7)/8);

	// load number
	this->FromTextBuf(text, len);
}

///////////////////////////////////////////////////////////////////////////////
// desctructor

bignum::~bignum()
{
	free(m_Data);
}

///////////////////////////////////////////////////////////////////////////////
// initialize max. size of number and set content to 0
// intsize/decsize = size of integer/decimal part in bytes
// decrease = decrease size if needed

void bignum::SetMaxSize(bint intsize, bint decsize, bool decrease /* = true */)
{
	// required new size in entries
	bint intmax = (intsize + BIGSIZE64-1)/BIGSIZE64*BIGSIZE64/BIGSIZE;
	if (intmax < 1) intmax = 1;
	bint decmax = (decsize + BIGSIZE64-1)/BIGSIZE64*BIGSIZE64/BIGSIZE;
	if (decmax < 0) decmax = 0;
	bint lenmax = intmax + decmax;

	// set to 0
	m_IntNum = 0;
	m_DecNum = 0;
	m_IsNeg = false;

	// buffer size is OK
	bint oldlen = m_IntMax + m_DecMax;
	if (!decrease && (lenmax <= oldlen))
	{
		m_DecMax = decmax;
		m_IntMax = oldlen - decmax;
		return;
	}

	// delete old buffer
	free(m_Data);
	m_Data = NULL;

	// create new buffer
	buint* d = (buint*)malloc(lenmax*BIGSIZE);
	if (d == NULL)
	{
		fprintf(stderr, "\rMEMORY ERROR!\n");
		exit(200);
	}

	// set data
	m_Data = d;
	m_IntMax = intmax;
	m_DecMax = decmax;
}

///////////////////////////////////////////////////////////////////////////////
// expand integer part

void bignum::ExpInt(bint intnum)
{
	if (intnum > m_IntMax) intnum = m_IntMax;
	bint n = intnum - m_IntNum;
	if (n > 0)
	{
		buint k = this->IsNeg() ? BIGMAX : 0;
		buint* d = this->Base(m_IntNum);
		m_IntNum = intnum;
		for (; n > 0; n--) *d++ = k;
	}
}

///////////////////////////////////////////////////////////////////////////////
// expand decimal part

void bignum::ExpDec(bint decnum)
{
	if (decnum > m_DecMax) decnum = m_DecMax;
	bint n = decnum - m_DecNum;
	if (n > 0)
	{
		buint* d = this->Base(-decnum);
		m_DecNum = decnum;
		for (; n > 0; n--) *d++ = 0;
	}
}

///////////////////////////////////////////////////////////////////////////////
// reduce integer part

void bignum::RedInt()
{
	bint n = m_IntNum;
	buint* d = this->Base(n - 1);
	buint k = this->IsNeg() ? BIGMAX : 0;
	for (; n > 0; n--)
	{
		if (*d != k) break;
		d--;
	}
	m_IntNum = n;
}

///////////////////////////////////////////////////////////////////////////////
// reduce decimal part

void bignum::RedDec()
{
	bint n = m_DecNum;
	buint* d = this->Base(-n);
	for (; n > 0; n--)
	{
		if (*d != 0) break;
		d++;
	}
	m_DecNum = n;
}

///////////////////////////////////////////////////////////////////////////////
// cut integer high bits to valid result
/*
void bignum::CutInt(bint bits)
{
	bint b = (m_IntNum - 1) * BIGBITS;
	buint h = this->High();
	buint* d = this->Base(m_IntNum - 1);

	for (; b >= bits; b -= BIGBITS)
	{
		*d = h;
		d--;
	}

	bits -= b;
	if ((b >= 0) && (bits < BIGBITS))
	{
		if (m_IsNeg)
		{
			*d = *d | (h << bits);
		}
		else
		{
			*d = *d & (BIGMAX >> (BIGBITS - bits));
		}
	}

	this->RedInt();
}
*/
///////////////////////////////////////////////////////////////////////////////
// copy from another number (does not resize buffer size and limits)

void bignum::Copy(const bignum& num)
{
	if (this == &num) return;

	// prepare length of integer part
	bint intnum = num.m_IntNum;
	if (intnum > m_IntMax) intnum = m_IntMax;
	m_IntNum = intnum;

	// prepare length of decimal part
	bint decnum = num.m_DecNum;
	if (decnum > m_DecMax) decnum = m_DecMax;
	m_DecNum = decnum;

	// total length
	bint len = intnum + decnum;

	// copy data
	const buint* s = num.Base(-decnum);
	buint* d = this->Base(-decnum);
	this->CopyStr(d, s, len);

	// negative flag
	m_IsNeg = num.m_IsNeg;

	// reduce
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// duplicate number, returns exact copy of this number (creates new number using malloc)

bignum* bignum::Dup() const
{
	bignum* d = new bignum(m_IntMax*BIGSIZE, m_DecMax*BIGSIZE);
	if (d == NULL)
	{
		fprintf(stderr, "\rMEMORY ERROR!\n");
		exit(200);
	}

	d->m_IntNum = m_IntNum;
	d->m_DecNum = m_DecNum;
	d->m_IsNeg = m_IsNeg;
	this->CopyStr(d->m_Data, m_Data, m_IntMax + m_DecMax);

	return d;
}

///////////////////////////////////////////////////////////////////////////////
// exchange two numbers

void bignum::Exchange(bignum& num)
{
	bint intmax = num.m_IntMax;
	bint decmax = num.m_DecMax;
	bint intnum = num.m_IntNum;
	bint decnum = num.m_DecNum;
	bool isneg = num.m_IsNeg;
	buint* data = num.m_Data;

	num.m_IntMax = m_IntMax;
	num.m_DecMax = m_DecMax;
	num.m_IntNum = m_IntNum;
	num.m_DecNum = m_DecNum;
	num.m_IsNeg = m_IsNeg;
	num.m_Data = m_Data;

	m_IntMax = intmax;
	m_DecMax = decmax;
	m_IntNum = intnum;
	m_DecNum = decnum;
	m_IsNeg = isneg;
	m_Data = data;
}

///////////////////////////////////////////////////////////////////////////////
// get integer value with limitation

buint bignum::UIntVal() const
{
	bint len = m_IntNum;
	if (len == 1) return m_Data[m_DecMax];
	if ((len == 0) || m_IsNeg) return 0;
	return (buint)-1;	
}

bint bignum::IntVal() const
{
	bint len = m_IntNum;
	if (len == 1)
	{
		bint res = (bint)m_Data[m_DecMax];
		if (m_IsNeg)
			return (res >= 0) ? ((buint)1 << (BIGBITS-1)) : res;
		else
			return (res < 0) ? (((buint)1 << (BIGBITS-1))-1) : res;
	}
	if (len == 0) return m_IsNeg ? -1 : 0;
	return (bint)((buint)1 << (BIGBITS-1));
}

buint bignum::UIntAbs() const
{
	bint len = m_IntNum;
	if (len == 1)
	{
		buint res = m_Data[m_DecMax];
		if (m_IsNeg)
			return (res == 0) ? (buint)-1 : ((~m_Data[m_DecMax])+1);
		else
			return res;
	}
	if (len == 0) return m_IsNeg ? 1 : 0;
	return (buint)-1;	
}

///////////////////////////////////////////////////////////////////////////////
// set number to 0

void bignum::Set0()
{
	m_IntNum = 0;
	m_DecNum = 0;
	m_IsNeg = false;
}

///////////////////////////////////////////////////////////////////////////////
// set number to 1

void bignum::Set1()
{
	if (m_IntMax > 0)
	{
		m_IntNum = 1;
		*this->Base() = 1;
	}
	m_DecNum = 0;
	m_IsNeg = false;
}

///////////////////////////////////////////////////////////////////////////////
// set number to -1

void bignum::SetM1()
{
	m_IntNum = 0;
	m_DecNum = 0;
	m_IsNeg = true;
}

///////////////////////////////////////////////////////////////////////////////
// set signed number

void bignum::Set(bint n)
{
	if (m_IntMax > 0)
	{
		m_IntNum = 1;
		*this->Base() = (buint)n;
	}

	m_DecNum = 0;
	m_IsNeg = (n < 0);
	this->RedInt();
}

///////////////////////////////////////////////////////////////////////////////
// set unsigned number

void bignum::SetU(buint n)
{
	if (m_IntMax > 0)
	{
		m_IntNum = 1;
		*this->Base() = n;
	}

	m_DecNum = 0;
	m_IsNeg = false;
	this->RedInt();
}

///////////////////////////////////////////////////////////////////////////////
// fill with a pattern (default = overflow = maximal positive number,
// intmax/decmax = max. length in number of entries)

void bignum::Fill(buint val /* = BIGMAX */, bool neg /* = false */, bint intmax /* = -1 */, bint decmax /* = -1 */)
{
	if ((intmax < 0) || (intmax > m_IntMax)) intmax = m_IntMax;
	if (intmax > m_IntNum) m_IntNum = intmax;
	if ((decmax < 0) || (decmax > m_DecMax)) decmax = m_DecMax;
	if (decmax > m_DecNum) m_DecNum = decmax;
	m_IsNeg = neg;
	this->FillStr(this->Base(-decmax), val, intmax + decmax);
}

///////////////////////////////////////////////////////////////////////////////
// scan equal pattern in UP direction (off = offset from number base of first entry;
// returns length of equal data in number of entries)

bint bignum::ScanEqu(buint val /* = 0 */, bint off /* = 0 */)
{
	if (m_IntNum + m_DecNum == 0) return 0;
	if (off > m_IntNum - 1) off = m_IntNum - 1;
	if (off < -m_DecNum) off = -m_DecNum;
	return this->ScanEquStr(this->Base(off), val, m_IntNum - off);
}

///////////////////////////////////////////////////////////////////////////////
// scan not equal pattern in UP direction (off = offset from number base of first entry;
// returns length of not equal data in number of entries)

bint bignum::ScanNEqu(buint val /* = 0 */, bint off /* = 0 */)
{
	if (m_IntNum + m_DecNum == 0) return 0;
	if (off > m_IntNum - 1) off = m_IntNum - 1;
	if (off < -m_DecNum) off = -m_DecNum;
	return this->ScanNEquStr(this->Base(off), val, m_IntNum - off);
}

///////////////////////////////////////////////////////////////////////////////
// compare if numbers are equals

bool bignum::CompEqu(const bignum& num) const
{
	// identical numbers
	if (this == &num) return true;

	// compare length of numbers
	bint len = m_IntNum;
	bint dec = m_DecNum;
	if ((len != num.m_IntNum) || (dec != num.m_DecNum)) return false;

	// compare content
	return this->CompEquStr(this->Base(-dec), num.Base(-dec), len + dec) == len + dec;
}

///////////////////////////////////////////////////////////////////////////////
// compare with another number (returns COMP_LE,...)

int bignum::Comp(const bignum& num) const
{
	// different signs
	bool neg1 = m_IsNeg;
	bool neg2 = num.m_IsNeg;
	int res = neg1 ? COMP_LE : COMP_GR;
	if (neg1 != neg2) return res;

	// different integer lengths (signs are equal)
	bint len1 = m_IntNum;
	bint len2 = num.m_IntNum;
	if (len1 != len2) return (len1 > len2) ? res : -res;

	// length of common part (lengths of integer parts are equal)
	bint dec1 = m_DecNum;
	bint dec2 = num.m_DecNum;
	bint dec = dec1;
	if (dec > dec2) dec = dec2;
	buint len = dec + len1;

	// compare common part
	res = this->CompStr(this->Base(-dec), num.Base(-dec), len);
	if (res != COMP_EQ) return res;

	// common parts are equal, compare length of rest of decimal parts
	if (dec1 != dec2) return (dec1 > dec2) ? COMP_GR : COMP_LE;

	// numbers are equal
	return COMP_EQ;
}

///////////////////////////////////////////////////////////////////////////////
// compare with signed number (returns COMP_LE,...)

int bignum::Comp(bint num) const
{
	// compare signs
	bool neg1 = m_IsNeg;
	bool neg2 = (num < 0);
	if (neg1 && !neg2) return COMP_LE;
	if (!neg1 && neg2) return COMP_GR;

	// compare integer length (signs are equal)
	bint len = m_IntNum;
	if (len > 1) return neg1 ? COMP_LE : COMP_GR;

	// length is 1
	if (len == 1)
	{
		buint k = *this->Base();
		buint k2 = (buint)num;
		if (k < k2) return COMP_LE;
		if (k > k2) return COMP_GR;

		// integer part is equal, but yet some decimals
		return (m_DecNum > 0) ? COMP_GR : COMP_EQ;
	}

	// zero length, this number is = -1 or 0
	if (neg1) // = -1
	{
		if (num > -1) return COMP_LE;
		if (num < -1) return COMP_GR;
	}
	else // = 0
	{
		if (num > 0) return COMP_LE;
		if (num < 0) return COMP_GR;
	}

	// integer part is equal, but yet some decimals
	return (m_DecNum > 0) ? COMP_GR : COMP_EQ;
}

///////////////////////////////////////////////////////////////////////////////
// compare with unsigned number (returns COMP_LE,...)

int bignum::CompU(buint num) const
{
	// compare sign
	if (m_IsNeg) return COMP_LE;

	// compare integer length
	bint len = m_IntNum;
	if (len > 1) return COMP_GR;

	// length is 1
	if (len == 1)
	{
		buint k = *this->Base();
		if (k < num) return COMP_LE;
		if (k > num) return COMP_GR;

		// integer part is equal, but yet some decimals
		return (m_DecNum > 0) ? COMP_GR : COMP_EQ;
	}

	// zero length, this number is = 0
	if (num == 0) return (m_DecNum > 0) ? COMP_GR : COMP_EQ;
	return COMP_LE;
}

///////////////////////////////////////////////////////////////////////////////
// negate number, this = -this

void bignum::Neg()
{
	// zero will stay unchanged
	if (this->Equ0()) return;

	// negate
	this->NegStr(this->Base(-m_DecNum), m_IntNum + m_DecNum);

	// flip sign
	m_IsNeg = !m_IsNeg;

	// reduce
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// negate number, this = -num

void bignum::Neg(const bignum& num)
{
	// prepare length of integer part
	bint intnum = num.m_IntNum;
	if (intnum > m_IntMax) intnum = m_IntMax;
	m_IntNum = intnum;

	// prepare length of decimal part
	bint decnum = num.m_DecNum;
	if (decnum > m_DecMax) decnum = m_DecMax;
	m_DecNum = decnum;

	// total length
	bint len = intnum + decnum;

	// negate
	buint cy = this->NegStr(this->Base(-decnum), num.Base(-decnum), len);

	// flip sign (number is 0 if cy=0)
	m_IsNeg = cy ? !num.m_IsNeg : false;

	// reduce
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// increment

void bignum::Inc()
{
	// expand
	this->ExpInt(m_IntNum + 1);

	// increment
	buint cy = this->IncStr(this->Base(), m_IntNum);

	// carry from -1 to 0
	if (cy) m_IsNeg = false;

	// reduce
	this->RedInt();
}

void bignum::Inc(const bignum& num)
{
	// copy decimal part
	bint len = num.m_DecNum;
	if (len > m_DecMax) len = m_DecMax;
	m_DecNum = len;
	this->CopyStr(this->Base(-len), num.Base(-len), len);

	// increment integer part
	len = num.m_IntNum;
	if (len > m_IntMax) len = m_IntMax;
	m_IntNum = len;
	buint cy = this->IncStr(this->Base(), num.Base(), len);

	// carry and sign
	m_IsNeg = num.m_IsNeg;
	if (cy != 0)
	{
		if (len < m_IntMax)
		{
			m_IntNum = len + 1;
			*this->Base(len) = m_IsNeg ? 0 : 1;
		}
		m_IsNeg = false;
	}

	// reduce
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// decrement

void bignum::Dec()
{
	// expand
	this->ExpInt(m_IntNum + 1);

	// decrement
	buint cy = this->DecStr(this->Base(), m_IntNum);

	// carry from 0 to -1
	if (cy) m_IsNeg = true;

	// reduce
	this->RedInt();
}

void bignum::Dec(const bignum& num)
{
	// copy decimal part
	bint len = num.m_DecNum;
	if (len > m_DecMax) len = m_DecMax;
	m_DecNum = len;
	this->CopyStr(this->Base(-len), num.Base(-len), len);

	// deccrement integer part
	len = num.m_IntNum;
	if (len > m_IntMax) len = m_IntMax;
	m_IntNum = len;
	buint cy = this->DecStr(this->Base(), num.Base(), len);

	// carry and sign
	m_IsNeg = num.m_IsNeg;
	if (cy != 0)
	{
		if (len < m_IntMax)
		{
			m_IntNum = len + 1;
			*this->Base(len) = m_IsNeg ? (buint)-2 : BIGMAX;
		}
		m_IsNeg = true;
	}

	// reduce
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// get number of valid bits of integer part (without highest sign bit)

bint bignum::IntBits() const
{
	bint i = m_IntNum;
	int bits = 0;
	if (i > 0)
	{
		i--;
#if BIGBITS > 32
		bits = ::Bits64(m_IsNeg ? ~*this->Base(i) : *this->Base(i));
#else
		bits = ::Bits32(m_IsNeg ? ~*this->Base(i) : *this->Base(i));
#endif
	}
	return i*BIGBITS + bits;
}

///////////////////////////////////////////////////////////////////////////////
// get number of valid bits of decimal part

bint bignum::DecBits() const
{
	bint i = m_DecNum;
	int bits = 0;
	if (i > 0)
	{
#if BIGBITS > 32
		bits = ::HighBits64(*this->Base(-i));
#else
		bits = ::HighBits32(*this->Base(-i));
#endif
		i--;
	}
	return i*BIGBITS + bits;
}

///////////////////////////////////////////////////////////////////////////////
// floor, nearest less or equal integer (round down)

void bignum::Floor(const bignum& num)
{
	bint len = num.m_IntNum;
	if (len > m_IntMax) len = m_IntMax;
	m_IntNum = len;
	m_DecNum = 0;
	this->CopyStr(this->Base(), num.Base(), len);
	m_IsNeg = num.m_IsNeg;
	this->RedInt();
}

///////////////////////////////////////////////////////////////////////////////
// ceiling, nearest greater or equal integer (round up)

void bignum::Ceil()
{
	if (m_DecNum > 0) this->Inc();
	m_DecNum = 0;
}

void bignum::Ceil(const bignum& num)
{
	this->Floor(num);
	if (num.m_DecNum > 0) this->Inc();
}

///////////////////////////////////////////////////////////////////////////////
// fraction, without floor integer

void bignum::Fract(const bignum& num)
{
	m_IntNum = 0;
	m_IsNeg = false;
	bint dec = num.m_DecNum;
	if (dec > m_DecMax) dec = m_DecMax;
	this->CopyStr(this->Base(-dec), num.Base(-dec), dec);
	this->RedDec();
}

///////////////////////////////////////////////////////////////////////////////
// round to nearest integer

void bignum::Round()
{
	bint dec = m_DecNum;
	if (dec > 0)
	{
		if ((bint)*this->Base(-1) < 0) this->Inc();
		m_DecNum = 0;
	}
}

void bignum::Round(const bignum& num)
{
	this->Floor(num);
	if ((num.m_DecNum > 0) && ((bint)*num.Base(-1) < 0)) this->Inc();
}

///////////////////////////////////////////////////////////////////////////////
// round to nearest integer towards zero (2.2 -> 2, -2.2 -> -2)

void bignum::Integer()
{
	if (m_IsNeg)
		this->Ceil();
	else
		this->Floor();
}

void bignum::Integer(const bignum& num)
{
	if (num.m_IsNeg)
		this->Ceil(num);
	else
		this->Floor(num);
}

///////////////////////////////////////////////////////////////////////////////
// convert to ASCIIZ text into buffer of size approx. 1 + 2.4*size in bytes,
// returns number of digits
// decmax = max. number of decimal digits (-1=unlimited)

bint bignum::ToTextBuf(char* buf, bint bufsize, bint decmax /* = -1 */) const
{
	// invalid buffer
	if ((bufsize <= 0) || (buf == NULL)) return 0;

	if (bufsize == 1)
	{
		buf[0] = 0;
		return 0;
	}

	// number is zero
	if (this->Equ0())
	{
		buf[0] = '0';
		buf[1] = 0;
		return 1;
	}

	// prepare copy of number
	int ti = GetBigTemp();
	bignum* t = &BigTempNum[ti];
	t->SetMaxSize(this->IntSize(), this->DecSize(), false);

	// prepare sign
	bint bufN = 0;
	if (m_IsNeg)
	{
		buf[0] = '-';
		bufN = 1;
		t->Neg(*this);
	}
	else
		t->Copy(*this);

	// zero integer
	if (t->m_IntNum == 0)
	{
		if (bufN < bufsize-1) buf[bufN++] = '0';
	}

	// decode integer digits
	else
	{
		bint olddec = t->m_DecNum;
		t->m_DecNum = 0;

		bint digN = 0;
		char dig;

#ifdef OPTIMISE
		buint grp = 0; // group of 19 digits
		buint tmp;
		int grpN = 0; // number of digits in group

		while (((t->m_IntNum != 0) || (grpN > 0)) && (digN < bufsize-1-bufN))
		{
			if (grpN == 0)
			{
#if	BIGBITS > 32
#ifdef X86
				grp = t->DivUInt(10000000000000000000);
				grpN = 19;
#else // X86
				grp = t->DivUInt(1000000000);
				grpN = 9;
#endif // X86
#else // BIGBITS
				grp = t->DivUInt(10000);
				grpN = 4;
#endif // BIGBITS
			}

			tmp = grp/10;
			dig = (char)(grp - tmp*10);
			grp = tmp;
			grpN--;
			if ((t->m_IntNum == 0) && (grp == 0)) grpN = 0;

			digN++;
			buf[bufsize - digN] = dig + '0';
		}
#else // OPTIMISE
		while ((t->m_IntNum != 0) && (digN < bufsize-1-bufN))
		{
			dig = (char)t->DivUInt(10);
			digN++;
			buf[bufsize - digN] = dig + '0';
		}
#endif // OPTIMISE

		t->m_DecNum = olddec;
		memmove(&buf[bufN], &buf[bufsize - digN], digN*sizeof(char));
		bufN += digN;
	}

	// decode decimal digits
	if (decmax < 0)
	{
		decmax = t->DecMaxDig();
		if ((t->m_DecNum == t->m_DecMax) && (decmax > 0)) decmax--;
	}

	bool isdec = false;
	if ((t->m_DecNum > 0) && (decmax != 0))
	{
		if (bufN < bufsize-1)
		{
			isdec = true;
			buf[bufN++] = '.';
		}

#ifdef OPTIMISE
		char dig;
		buint grp = 0; // group of 19 digits
		int grpN = 0; // number of digits in group
		buint grpdiv = 1;

		while (((t->m_DecNum != 0) || (grpN > 0)) && (decmax != 0) && (bufN < bufsize-1))
		{
			if (grpN == 0)
			{
				if ((decmax < 20) || (t->m_DecNum == 0))
				{
					grpdiv = 10;
					grpN = 1;
				}
				else
				{
#if	BIGBITS > 32
#ifdef X86
					grpdiv = 10000000000000000000;
					grpN = 19;
#else // X86
					grpdiv = 1000000000;
					grpN = 9;
#endif // X86
#else // BIGBITS
					grpdiv = 10000;
					grpN = 4;
#endif // BIGBITS
				}

				t->m_IntNum = 0;
				t->MulU(grpdiv);
				grp = t->UIntVal();
			}

			grpdiv /= 10;
			dig = (char)(grp/grpdiv);
			grp -= dig*grpdiv;
			grpN--;
			if ((t->m_DecNum == 0) && (grp == 0)) grpN = 0;

			buf[bufN++] = dig + '0';
			decmax--;
		}
#else // OPTIMISE
		while ((t->m_DecNum != 0) && (decmax != 0) && (bufN < bufsize-1))
		{
			t->m_IntNum = 0;
			t->Mul(10);
			buf[bufN++] = (char)(t->UIntVal() + '0');
			decmax--;
		}
#endif // OPTIMISE
	}

	// round result
	if ((t->m_DecNum != 0) && ((bint)*t->Base(-1) < 0))
	{
		bint i = bufN - 1;
		for (; i >= 0; i--)
		{
			if ((buf[i] >= '0') && (buf[i] <= '9'))
			{
				buf[i]++;
				if (buf[i] != '9'+1) break;
				buf[i] = '0';
			}
		}

		// overflow to higher digit
		if (i < 0)
		{
			i = 0;
			if (buf[0] == '-') i++;
			bint n = bufN - i;
			if (bufN == bufsize-1)
				n--;
			else
				bufN++;
			memmove(&buf[i+1], &buf[i], n);
			buf[i] = '1';
		}
	}

	// reduce trailing zeroes
	if (isdec)
	{
		bint i = bufN-1;
		while (buf[i--] == '0') bufN--;
	}

	buf[bufN] = 0;

	FreeBigTemp(ti);

	return bufN;
}

CText bignum::ToText(bint decmax /* = -1 */) const
{
	int len = (int)(this->LenDig() + 20);
	CText txt;
	if (!txt.SetLength(len)) return txt;
	len = (int)this->ToTextBuf(txt.DataData(), len, decmax);
	txt.SetLength(len);
	return txt;
}

///////////////////////////////////////////////////////////////////////////////
// convert number from text (len=text length, -1=unlimited, terminate by 0, returns processed characters)

bint bignum::FromTextBuf(const char* text, bint len /* = -1 */)
{
	// must be 1 word of integer
	if (m_IntMax == 0) return 0;

	// prepare number buffers (t=integer part, this=decimal part)
	int ti = GetBigTemp();
	bignum* t = &BigTempNum[ti];
	t->SetMaxSize(this->IntSize(), 0, false);
	this->Set0();

	bint len0 = len;

	// get sign
	bool sign = false;
	char ch;
	while ((len != 0) && (*text != 0))
	{
		ch = *text++;
		len--;

		if (ch == '-')
			sign = !sign;
		else if ((ch != '+') && (ch > ' '))
		{
			text--;
			len++;
			break;
		}
	}

	// get integral part of number
#ifdef OPTIMISE
	buint grp = 0; // group of 9 digits
	int grpN = 0; // number of digits in group

	while ((len != 0) && (*text != 0))
	{
		ch = *text++;
		len--;
		grpN++;

		if ((ch >= '0') && (ch <= '9'))
		{
			grp *= 10;
			grp += ch - '0';

#if	BIGBITS > 32
#ifdef X86
			if (grpN == 19)
			{
				t->MulU(10000000000000000000);
#else // X86
			if (grpN == 9)
			{
				t->MulU(1000000000);
#endif // X86
#else // BIGBITS
			if (grpN == 4)
			{
				t->MulU(10000);
#endif // BIGBITS
				t->AddU(grp);
				grp = 0;
				grpN = 0;
			}
			continue;
		}
		break;
	}

	// reset unfinished group
	text -= grpN;
	len += grpN;

#endif // OPTIMISE

	// get rest of digits
	while ((len != 0) && (*text != 0))
	{
		ch = *text++;
		len--;

		if ((ch >= '0') && (ch <= '9'))
		{
			t->MulU(10);
			t->AddU(ch - '0');
			continue;
		}

		text--;
		len++;
		break;
	}

	// decimal separator
	if ((len != 0) && (*text != 0))
	{
		ch = *text++;
		len--;

		if (ch == '.')
		{
			// find end of decimal
			bint n = 0;
			while ((len != 0) && (*text != 0))
			{
				ch = *text;
				if ((ch < '0') || (ch > '9')) break;

				text++;
				len--;
				n++;
			}

			// add decimals
#ifdef OPTIMISE
			buint grp; // group of 9 digits

#if	BIGBITS > 32
#ifdef X86
			for (; n >= 19; n -= 19)
			{
				text -= 19;

				grp = text[0] - '0';
				grp *= 10; grp += text[1] - '0';
				grp *= 10; grp += text[2] - '0';
				grp *= 10; grp += text[3] - '0';
				grp *= 10; grp += text[4] - '0';
				grp *= 10; grp += text[5] - '0';
				grp *= 10; grp += text[6] - '0';
				grp *= 10; grp += text[7] - '0';
				grp *= 10; grp += text[8] - '0';
				grp *= 10; grp += text[9] - '0';
				grp *= 10; grp += text[10] - '0';
				grp *= 10; grp += text[11] - '0';
				grp *= 10; grp += text[12] - '0';
				grp *= 10; grp += text[13] - '0';
				grp *= 10; grp += text[14] - '0';
				grp *= 10; grp += text[15] - '0';
				grp *= 10; grp += text[16] - '0';
				grp *= 10; grp += text[17] - '0';
				grp *= 10; grp += text[18] - '0';
		
				*this->Base() = grp;
				m_IntNum = 1;
				this->DivU(10000000000000000000);
			}
#else // X86
			for (; n >= 9; n -= 9)
			{
				text -= 9;

				grp = text[0] - '0';
				grp *= 10; grp += text[1] - '0';
				grp *= 10; grp += text[2] - '0';
				grp *= 10; grp += text[3] - '0';
				grp *= 10; grp += text[4] - '0';
				grp *= 10; grp += text[5] - '0';
				grp *= 10; grp += text[6] - '0';
				grp *= 10; grp += text[7] - '0';
				grp *= 10; grp += text[8] - '0';
		
				*this->Base() = grp;
				m_IntNum = 1;
				this->DivU(1000000000);
			}
#endif // X86
#else // BIGBITS
			for (; n >= 4; n -= 4)
			{
				text -= 4;

				grp = text[0] - '0';
				grp *= 10; grp += text[1] - '0';
				grp *= 10; grp += text[2] - '0';
				grp *= 10; grp += text[3] - '0';
		
				*this->Base() = grp;
				m_IntNum = 1;
				this->DivU(10000);
			}
#endif // BIGBTIS

#endif // OPTIMISE

			for (; n > 0; n--)
			{
				text--;
				ch = *text;
				*this->Base() = ch - '0';
				m_IntNum = 1;
				this->DivU(10);
			}
		}
		else
		{
			text--;
			len++;
		}
	}

	// sum integer and decimal part
	t->RedInt();
	this->Reduce();
	this->Add(*t);

	// free temporary number
	FreeBigTemp(ti);

	// negate
	if (sign) this->Neg();

	return len0 - len;
}

///////////////////////////////////////////////////////////////////////////////
// convert number from text (returns new position)

int bignum::FromText(const CText& text, int pos)
{
	int len = text.Length();
	if (pos < 0) pos = 0;
	if (pos >= len)
	{
		this->Set0();
		return len;
	}
	return (int)this->FromTextBuf(text.DataData() + pos, len - pos) + pos;
}

///////////////////////////////////////////////////////////////////////////////
// raw random number (maxint/maxdec/minint/mindec = max./min. number of digits of integer/decimal part)

void bignum::RandRaw(bint maxint, bint maxdec, bint minint /* = 1 */, bint mindec /* = 0 */)
{
	// size in number of entries
	bint intmax = ((bint)(maxint*BYTEPERDIG+0.999) + BIGSIZE64-1)/BIGSIZE64*BIGSIZE64/BIGSIZE;
	bint intmin = ((bint)(minint*BYTEPERDIG+0.999) + BIGSIZE64-1)/BIGSIZE64*BIGSIZE64/BIGSIZE;
	bint decmax = ((bint)(maxdec*BYTEPERDIG+0.999) + BIGSIZE64-1)/BIGSIZE64*BIGSIZE64/BIGSIZE;
	bint decmin = ((bint)(mindec*BYTEPERDIG+0.999) + BIGSIZE64-1)/BIGSIZE64*BIGSIZE64/BIGSIZE;

	if (intmax > m_IntMax) intmax = m_IntMax;
	if (intmax < 1) intmax = 1;
	if (intmin > intmax) intmin = intmax;
	if (intmin < 1) intmin = 1;

	if (decmax > m_DecMax) decmax = m_DecMax;
	if (decmax < 0) decmax = 0;
	if (decmin > decmax) decmin = decmax;
	if (decmin < 0) decmin = 0;

#if BIGBITS <= 32
	intmax = 2*((bint)::Rand((intmax+1)/2 - (intmin+1)/2) + (intmin+1)/2);
	decmax = 2*((bint)::Rand((decmax+1)/2 - (decmin+1)/2) + (decmin+1)/2);
#else
	intmax = (bint)::Rand(intmax - intmin) + intmin;
	decmax = (bint)::Rand(decmax - decmin) + decmin;
#endif

	m_IntNum = intmax;
	m_DecNum = decmax;

	// generate number
	buint* d = this->Base(-decmax);
	bint i = intmax + decmax;
	for (; i > 0; i--)
	{
#if BIGBITS > 32
		*d++ = ::Rand();
#else
		u64 kk = ::Rand();
		*d++ = (buint)kk;
		if (i > 1)
		{
			*d++ = (buint)(kk >> 32);
			i--;
		}
#endif
	}

	// sign
	m_IsNeg = ::Rand(1) > 0;

	this->Reduce();
}
