// BigInt.cpp: implementation of the CBigInt class.
//
//////////////////////////////////////////////////////////////////////
#include "BigInt.h"

const int BYTES = sizeof(unsigned long);
const int NIBBLES = BYTES * 2;
const int BITS = BYTES * 8;
const unsigned long MAXULONG = 0xffffffff;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CBigInt::CBigInt() {
	m_stringBuf = NULL;
	*(m_value = new unsigned long[m_ndw = 1]) = 0;
	if (m_value == NULL) m_ndw = 0;
}

CBigInt::CBigInt(unsigned int Value) {
	m_stringBuf = NULL;
	m_value = new unsigned long[m_ndw = 2];
	if (m_value == NULL) 
		m_ndw = 0;
	else {
		m_value[0] = Value;
		if (IsNegative())
			Expand(1);
	}
}

CBigInt::CBigInt(unsigned long Value) {
	m_stringBuf = NULL;
	m_value = new unsigned long[m_ndw = 1];
	if (m_value == NULL) 
		m_ndw = 0;
	else {
		m_value[0] = Value;
		if (IsNegative())
			Expand(1);
	}
}

CBigInt::CBigInt(const unsigned __int64 &Value) {
	unsigned long HighValue = (unsigned long)(Value >> BITS);
	m_stringBuf = NULL;
	m_value = new unsigned long[m_ndw = HighValue ? 2 : 1];
	if (m_value == NULL) 
		m_ndw = 0;
	else {
		m_value[0] = (unsigned long) (Value & MAXULONG);
		if (HighValue) m_value[1] = HighValue;
		if (IsNegative())
			Expand(1);
	}
}

CBigInt::CBigInt(int Value) {
	m_stringBuf = NULL;
	m_value = new unsigned long[m_ndw = 1];
	if (m_value == NULL) 
		m_ndw = 0;
	else
		m_value[0] = (unsigned long)Value;
}

CBigInt::CBigInt(long Value) {
	m_stringBuf = NULL;
	m_value = new unsigned long[m_ndw = 1];
	if (m_value == NULL) 
		m_ndw = 0;
	else
		m_value[0] = (unsigned long)Value;
}

CBigInt::CBigInt(const __int64 &Value) {
	unsigned long HighValue = (unsigned long)(Value >> BITS);
	if ((Value & 0xffffffff80000000) == 0xffffffff80000000)
		HighValue = 0;
	m_stringBuf = NULL;
	m_value = new unsigned long[m_ndw = HighValue ? 2 : 1];
	if (m_value == NULL) 
		m_ndw = 0;
	else {
		m_value[0] = (unsigned long) (Value & MAXULONG);
		if (HighValue) m_value[1] = (unsigned long) HighValue;
	}
}

CBigInt::CBigInt(const CBigInt &Value) {
	if (Value.IsNull()) {
		m_ndw = 0;
		m_value = NULL;
	}
	else {
		m_value = new unsigned long[m_ndw = Value.m_ndw];
		if (m_value == NULL)
			m_ndw = 0;
		else
			memcpy(m_value, Value.m_value, m_ndw * BYTES);
	}
	m_stringBuf = NULL;
}

CBigInt::CBigInt(const unsigned long *Data, int DataSize) {
	m_value = new unsigned long[m_ndw = DataSize];
	if (m_value == NULL)
		m_ndw = 0;
	else
		memcpy(m_value, Data, DataSize * BYTES);
	m_stringBuf = NULL;
}

CBigInt::CBigInt(const char *szValue) {
	m_ndw = 0;
	m_value = NULL;
	m_stringBuf = NULL;
	switch (*szValue) {
	case '0':
		if (*(szValue + 1) == 'x' || *(szValue + 1) == 'X')
			FromHex(szValue + 2);
		else if (*(szValue + 1) == 'b' || *(szValue + 1) == 'B')
			FromBin(szValue + 2);
		else
			FromOct(szValue + 1);
		break;
	case 0:
		*(m_value = new unsigned long[m_ndw = 1]) = 0;
		break;
	default:
		FromDec(szValue);
		break;
	}
}

CBigInt::~CBigInt() {
	if (!IsNull()) delete [] m_value;
	if (m_stringBuf)
		delete [] m_stringBuf;
}

// Internal Data maintenance
void CBigInt::ExpandTo(int nWords, bool bNegative) {
	if (nWords > m_ndw) {
		unsigned long *tmp = new unsigned long[nWords];
		if (tmp == NULL) {
			MakeNull();
		}
		else {
			memset(tmp, bNegative ? 0xff : 0, nWords * BYTES);
			memcpy(tmp, m_value, m_ndw * BYTES);
			delete [] m_value;
			m_value = tmp;
			m_ndw = nWords;
		}
	}
}

void CBigInt::Optimize() {
	if (!IsNull()) {
		int newlen = m_ndw;
		if (IsNegative()) {
			while (newlen > 1 && m_value[newlen - 1] == MAXULONG)
				newlen--;
			if ((m_value[newlen - 1] & 0x80000000) == 0)
				newlen++;
		} else {
			while (newlen > 1 && m_value[newlen - 1] == 0)
				newlen--;
			if ((m_value[newlen - 1] & 0x80000000) != 0)
				newlen++;
		}
		if (m_ndw != newlen) {
			unsigned long *tmp = new unsigned long[newlen];
			if (tmp != NULL) {
				// We can get away with not etting this object to NULL,
				// as the value remains the same, even if not optimized
				memcpy(tmp, m_value, newlen * BYTES);
				if (IsNegative())
					*(tmp + newlen - 1) |= 0x80000000;
				m_ndw = newlen;
				delete [] m_value;
				m_value = tmp;
			}
		}
	}
}

void CBigInt::Negate() {
	bool bNeg = IsNegative();
	int i;

	if (bNeg)
		operator --();
	for (i = 0; i < m_ndw; ++i)
		m_value[i] = ~m_value[i];
	if (!bNeg)
		operator++();
	else if (m_value[m_ndw - 1] & 0x80000000)
		Expand(1, false);
}

// Conversion Operators
CBigInt::operator bool() const {
	bool rval = false;
	for (int i = 0; i < m_ndw && !rval; ++i)
		rval = m_value[i] != 0;
	return rval;
}

CBigInt::operator __int64() const {
	if (IsNull())
		return (__int64)0;
	if (m_ndw == 1)
		return (__int64)(long)m_value[0];
	return (__int64)((unsigned __int64)m_value[1] << BITS | m_value[0]);
}

CBigInt::operator unsigned __int64() const {
	if (IsNull())
		return (unsigned __int64)0;
	if (m_ndw == 1)
		return (unsigned __int64) m_value[0];
	return (unsigned __int64)m_value[1] << BITS | m_value[0];
}

CBigInt::operator char*() const {
	Format();
	return m_stringBuf;
}

CBigInt::operator const char*() const {
	Format();
	return m_stringBuf;
}

// Unary Operators
CBigInt& CBigInt::operator ++() {
	bool Neg = IsNegative();
	for (int i = 0; i < m_ndw; ++i) {
		if (++m_value[i])
			break;
	}
	if (IsNegative() && !Neg) // Crossed to MSBit being set
		Expand(1);
	return *this;
}

CBigInt CBigInt::operator++(int) {
	CBigInt tmp = *this;
	operator ++();
	return tmp;
}

CBigInt& CBigInt::operator--() {
	bool Neg = IsNegative();
	for (int i = 0; i < m_ndw; ++i) {
		if (m_value[i]--)
			break;
	}
	if (Neg && !IsNegative()) // Crossed to MSBit being cleared
		Expand(1, true);
	return *this;
}

CBigInt CBigInt::operator--(int) {
	CBigInt tmp(*this);
	operator --();
	return tmp;
}

CBigInt CBigInt::operator -() const {
	CBigInt tmp(*this);
	tmp.Negate();
	tmp.Optimize();
	return tmp;
}

CBigInt CBigInt::operator ~() const	{
	CBigInt tmp(*this);
	tmp.Expand(m_ndw - 1);
	if (!tmp.IsNull()) {
		for (int i = 0; i < m_ndw; ++i)
			tmp.m_value[i] = ~m_value[i];
		tmp.Optimize();
	}
	return tmp;
}

bool CBigInt::operator !() const {
	bool rval = true;
	for (int i = 0; i < m_ndw && rval; ++i)
		rval = m_value[i] == 0;
	return rval;
}

// Binary Operators
CBigInt CBigInt::operator +(const CBigInt& Value) const {
	CBigInt A(*this), B(Value);
	unsigned long carry = 0;
	int i;

	if (IsNull() || A.IsNull() || B.IsNull()) {
		A.MakeNull();
		return A;
	}
	if (A.m_ndw < B.m_ndw)
		A.ExpandTo(B.m_ndw, A.IsNegative());
	else if (B.m_ndw < A.m_ndw)
		B.ExpandTo(A.m_ndw, B.IsNegative());

	for (i = 0; i < A.m_ndw; ++i) {

		__int64 t = (__int64)carry + A.m_value[i] + B.m_value[i];
		A.m_value[i] = (unsigned long)(t & MAXULONG);
		carry = (unsigned long)(t >> BITS);
	}
	if (carry || A.IsNegative()) {
		A.Expand(1);
		A.m_value[A.m_ndw - 1] = (unsigned long)carry;
	}
	A.Optimize();
	return A;
}

CBigInt CBigInt ::operator -(const CBigInt& Value) const {
	CBigInt A(*this), B(Value);
	long carry = 0;
	int i;

	if (IsNull() || A.IsNull() || B.IsNull()) {
		A.MakeNull();
		return A;
	}
	if (A.m_ndw < B.m_ndw)
		A.ExpandTo(B.m_ndw, A.IsNegative());
	else if (B.m_ndw < A.m_ndw)
		B.ExpandTo(A.m_ndw, B.IsNegative());

	for (i = 0; i < A.m_ndw; ++i) {
		__int64 t = (__int64)A.m_value[i] - (__int64)B.m_value[i] + (__int64)carry;
		A.m_value[i] = (unsigned long)(t & MAXULONG);
		carry = (unsigned long)(t >> BITS);
	}
	if (carry) {
		A.Expand(1);
		A.m_value[A.m_ndw - 1] = carry;
	}
	A.Optimize();
	return A;
}

CBigInt CBigInt::operator *(const CBigInt& Value) const {
	int i, j;
	CBigInt rval, tmp, A(*this), B(Value);
	bool Neg = false;
	
	if (IsNull() || A.IsNull() || B.IsNull() || rval.IsNull() || tmp.IsNull()) {
		A.MakeNull();
		return A;
	}
	if (A.IsNegative()) {
		A.Negate();
		Neg = true;
	}

	if (B.IsNegative()) {
		B.Negate();
		Neg = !Neg;
	}
	for (i = 0; i < A.m_ndw; ++i) {
		for (j = 0; j < B.m_ndw; ++j) {
			tmp = (unsigned __int64)A.m_value[i] * (unsigned __int64)B.m_value[j];
			rval += tmp << ((i + j) * BITS);
		}
	}
	if (tmp.IsNull())
		rval.MakeNull();
	else {
		if (rval.IsNegative())
			rval.Expand(1);
		rval.Optimize();
		if (Neg)
			rval.Negate();
	}
	return rval;
}

CBigInt CBigInt::operator /(const CBigInt& Value) const {
	CBigInt Quotient;
	Div(Value, &Quotient, NULL);
	return Quotient;
}

CBigInt CBigInt::operator %(const CBigInt& Value) const {
	CBigInt  Remainder;
	Div(Value, NULL, &Remainder);
	return Remainder;
}

CBigInt CBigInt::operator &(const CBigInt& Value) const {
	CBigInt tmpA(*this), tmpB(Value);
	int i;

	if (m_ndw > Value.m_ndw)
		tmpB.ExpandTo(m_ndw, Value.IsNegative());
	else if (Value.m_ndw > m_ndw)
		tmpA.ExpandTo(Value.m_ndw, IsNegative());
	if (tmpA.IsNull() || tmpB.IsNull() || IsNull()) {
		tmpA.MakeNull();
		return tmpA;
	}

	for (i = 0; i < tmpA.m_ndw; ++i)
		tmpA.m_value[i] &= tmpB.m_value[i];
	tmpA.Optimize();
	return tmpA;
}

CBigInt CBigInt::operator |(const CBigInt& Value) const {
	CBigInt tmpA(*this), tmpB(Value);
	int i;

	if (tmpA.m_ndw > tmpB.m_ndw)
		tmpB.ExpandTo(m_ndw, Value.IsNegative());
	else if (tmpB.m_ndw > tmpA.m_ndw)
		tmpA.ExpandTo(Value.m_ndw, IsNegative());

	if (tmpA.IsNull() || tmpB.IsNull() || IsNull())
		tmpA.MakeNull();
	else {
		for (i = 0; i < tmpA.m_ndw; ++i)
			tmpA.m_value[i] |= tmpB.m_value[i];
		tmpA.Optimize();
	}
	return tmpA;
}

CBigInt CBigInt::operator ^(const CBigInt& Value) const {
	CBigInt tmpA(*this), tmpB(Value);
	int i;

	if (m_ndw > Value.m_ndw)
		tmpB.ExpandTo(m_ndw, Value.IsNegative());
	else if (Value.m_ndw > m_ndw)
		tmpA.ExpandTo(Value.m_ndw, IsNegative());

	if (tmpA.IsNull() || tmpB.IsNull() || IsNull())
		tmpA.MakeNull();
	else {
		for (i = 0; i < tmpA.m_ndw; ++i)
			tmpA.m_value[i] ^= tmpB.m_value[i];
		tmpA.Optimize();
	}
	return tmpA;
}

CBigInt CBigInt::operator <<(int nBits) const {
	if (nBits < 0)
		return operator >>(-nBits);
	else {
		CBigInt rval(*this);
		if (rval.IsNull())
			return rval;

		unsigned long carry = 0;
		int i, j;

		j = nBits / BITS;
		if (j) {
			rval.Expand(j);
			if (rval.IsNull())
				return rval;
			memcpy(rval.m_value + j, m_value, m_ndw * BYTES);
			memset(rval.m_value, 0, j * BYTES);
			nBits %= BITS;
		}
		if (nBits) {
			for (i = 0; i < rval.m_ndw; ++i) {
				unsigned long tmp = rval.m_value[i] >> (BITS - nBits);
				rval.m_value[i] <<= nBits;
				rval.m_value[i] |= carry;
				carry = tmp;
			}
			if (carry) {
				rval.Expand(1, IsNegative());
				if (rval.IsNull()) return rval;
				rval.m_value[rval.m_ndw - 1] <<= nBits;
				rval.m_value[rval.m_ndw - 1] |= carry;
			}
		}
		if (IsNegative()) {
			rval.Optimize();
			rval.m_value[rval.m_ndw - 1] |= 0x80000000;
		}
		else if (rval.IsNegative())
			rval.Expand(1);
		return rval;
	}
}

CBigInt CBigInt::operator >>(int nBits) const {
	if (nBits < 0)
		return operator >>(-nBits);
	else {
		CBigInt rval(*this);
		unsigned long carry = 0;
		int i, j;
		if (rval.IsNull())
			return rval;
		j = nBits / BITS;
		if (j) {
			if (j >= m_ndw) {
				rval = 0;
				nBits = 0;
			}
			else {
				unsigned long *tmp = new unsigned long[rval.m_ndw = m_ndw - j];
				if (tmp == NULL) {
					rval.MakeNull();
					return rval;
				}
				memcpy(tmp, m_value + j, rval.m_ndw * BYTES);
				delete [] rval.m_value;
				rval.m_value = tmp;
				nBits %= BITS;
			}
		}

		if (rval.IsNull())
			return rval;
		if (nBits) {
			if (IsNegative())
				carry = MAXULONG << (BITS - nBits);
			for (i = rval.m_ndw - 1; i >= 0; --i) {
				unsigned long tmp = rval.m_value[i] << (BITS - nBits);
				if (tmp == NULL) {
					rval.MakeNull();
					return rval;
				}
				rval.m_value[i] >>= nBits;
				rval.m_value[i] |= carry;
				carry = tmp;
			}
		}
		rval.Optimize();
		return rval;
	}
}

// Logical Operators
bool CBigInt::operator !=(const CBigInt& Value) const {
	bool rval = true;
	for (int i = 0; i < m_ndw && rval; ++i) {
		if (i < Value.m_ndw)
			rval = m_value[i] == Value.m_value[i];
		else
			rval = m_value[i] == (Value.IsNegative() ? MAXULONG : 0L);
	}
	return !rval;
}

bool CBigInt::operator ==(const CBigInt& Value) const {
	bool rval = true;
	for (int i = 0; i < m_ndw && rval; ++i) {
		if (i < Value.m_ndw)
			rval = m_value[i] == Value.m_value[i];
		else
			rval = m_value[i] == (Value.IsNegative() ? MAXULONG : 0L);
	}
	return rval;
}

bool CBigInt::operator <(const CBigInt& Value) const {
	if (IsNegative() == Value.IsNegative()) 
		return (*this - Value).IsNegative();
	return IsNegative();
}

bool CBigInt::operator <=(const CBigInt& Value) const {
	return operator <(Value) || operator ==(Value);
}

bool CBigInt::operator >(const CBigInt& Value) const {
	if (IsNegative() == Value.IsNegative()) 
		return (Value - *this).IsNegative();
	return Value.IsNegative();
}

bool CBigInt::operator >=(const CBigInt& Value) const {
	return operator >(Value) || operator ==(Value);
}

bool CBigInt::operator &&(const CBigInt& Value) const {
	return operator bool() && Value.operator bool();
}

bool CBigInt::operator ||(const CBigInt& Value) const {
	return operator bool() || Value.operator bool();
}

// Assignment Operators
CBigInt& CBigInt::operator =(const CBigInt& Value) {
	MakeNull();
	if (!Value.IsNull()) {
		m_value = new unsigned long[m_ndw = Value.m_ndw];
		if (m_value == NULL)
			m_ndw = 0;
		else
			memcpy(m_value, Value.m_value, m_ndw * BYTES);
	}
	return *this;
}

CBigInt& CBigInt::operator <<=(int nBits) {
	return *this = operator <<(nBits);
}

CBigInt& CBigInt::operator >>=(int nBits) {
	return *this = operator >>(nBits);
}

void CBigInt::Div(const CBigInt &Divisor, CBigInt *Quotient, CBigInt *Remainder) const {
	if (!Divisor) { 		// Divide by zero - force the exception
		_asm {
		  mov EAX, 0
		  div EAX
		}
	}
	else if (operator !()) {
		if (Quotient) *Quotient = 0;
		if (Remainder) *Remainder = 0;
	}
	else if (Divisor.m_ndw == 1) {
		if (Divisor.IsNegative())
			Div((long)Divisor.m_value[0], Quotient, Remainder);
		else
			Div(Divisor.m_value[0], Quotient, Remainder);
	}
	else {
		int i;
		unsigned long mask;
		CBigInt tmpDividend(*this);
		CBigInt tmpDivisor(Divisor);
		CBigInt tmpQuotient, tmpRemainder;
		bool Neg = false;

		if ( tmpDividend.IsNegative() ) {
			Neg = true;
			tmpDividend.Negate();