
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//                        Long number - subtraction                          //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#include "..\include.h"

///////////////////////////////////////////////////////////////////////////////
// sub 2 bignums, store result here (numbers may overlap)

void bignum::Sub(const bignum& num1, const bignum& num2)
{
	// special cases
	if (num1.Equ0()) { this->Neg(num2); return; }
	if (num2.Equ0()) { this->Copy(num1); return; }
	if (num2.Equ1()) { this->Dec(num1); return; }
	if (num2.EquM1()) { this->Inc(num1); return; }
	if (&num1 == &num2) { this->Set0(); return; }

	// prepare length with 2 numbers (dec1, dec2, dec, len1, len2, len)
	BIGPREP2();

	// copy start of decimal part (or negate second number)
	buint cy = 0;
	if (dec1 > dec)
	{
		m_DecNum = dec1;
		this->CopyStr(this->Base(-dec1), num1.Base(-dec1), dec1 - dec);
	}
	else if (dec2 > dec)
	{
		m_DecNum = dec2;
		cy = this->NegStr(this->Base(-dec2), num2.Base(-dec2), dec2 - dec);
	}

	// operation on common data
	const buint* s1 = num1.Base(-dec);
	const buint* s2 = num2.Base(-dec);
	buint* d = this->Base(-dec);
	bint i = dec + len;
	cy = this->SubStr(cy, d, s1, s2, i);
	s1 += i;
	s2 += i;
	d += i;

	// operation on larger part of one number
	if (len1 > len)
	{
		// dst = num1 - ((k=0 or -1) + cy)
		m_IntNum = len1;
		i = len1 - len;
		switch ((int)cy + (int)num2.High())
		{
		case 1: // cy=1, k=0
			cy = this->DecStr(d, s1, i);
			break;

		case -1: // cy=0, k=-1
			cy = this->IncStr(d, s1, i);
			break;

		default: // 0: cy=1, k=-1 / cy=0, k=0
			this->CopyStr(d, s1, i);
		}
		d += i;
	}
	else if (len2 > len)
	{
		// dst = (0 or -1) - num2 - cy
		m_IntNum = len2;
		i = len2 - len;
		if (num1.m_IsNeg)
			cy = this->NegDecStr(cy, d, s2, i); // negate with decrement
		else
		{
			// only negate (start or continue)
			if (cy == 1) // k=0, cy=1
				this->NotStr(d, s2, i);
			else // k=0, cy=0
				cy = this->NegStr(d, s2, i);
		}
		d += i;
	}

	// carry
	len = m_IntNum;
	buint k1 = (len < num1.m_IntNum) ? *num1.Base(len) : num1.High();
	buint k2 = (len < num2.m_IntNum) ? *num2.Base(len) : num2.High();
	buint r = k1 - k2 - cy;
	if (len < m_IntMax)
	{
		m_IntNum = len + 1;
		d[0] = r;
	}

	// sign
	m_IsNeg = (bint)r < 0;
	
	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// sub bignum and signed number, store result here (numbers may overlap)

void bignum::Sub(const bignum& num1, bint num2)
{
	if (num2 < 0)
		this->AddU(num1, -num2);
	else
		this->SubU(num1, num2);
}

///////////////////////////////////////////////////////////////////////////////
// sub bignum and unsigned number, store result here (numbers may overlap)

void bignum::SubU(const bignum& num1, buint num2)
{
	// special cases
	if (num2 == 0) { this->Copy(num1); return; }
	if (num2 == 1) { this->Dec(num1); return; }

	// length of decimal part
	bint i = num1.m_DecNum;
	if (i > m_DecMax) i = m_DecMax;
	m_DecNum = i;

	// copy decimal part
	const buint* s = num1.Base(-i);
	buint* d = this->Base(-i);
	this->CopyStr(d, s, i);
	s += i;
	d += i;

	// length of integer part
	i = num1.m_IntNum;
	if (i > m_IntMax) i = m_IntMax;
	m_IntNum = i;

	// sub number
	buint r;
	buint cy = 0;
	if (i > 0)
	{
		r = *s++;
		cy = (r < num2);
		*d++ = r - num2;
		i--;
	}

	// if source has no integer part
	else
	{
		r = num1.High();
		cy = (r < num2);
		if (m_IntMax > 0)
		{
			m_IntNum = 1;
			*d++ = r - num2;
		}
	}

	// copy rest of integer part
	if (cy == 0)
		this->CopyStr(d, s, i);
	else
		cy = this->DecStr(d, s, i);
	d += i;

	// carry
	i = m_IntNum;
	buint k = (i < num1.m_IntNum) ? *num1.Base(i) : num1.High();
	r = k - cy;
	if (i < m_IntMax)
	{
		m_IntNum = i + 1;
		d[0] = r;
	}

	// sign
	m_IsNeg = (bint)r < 0;

	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// sub bignum and signed number, store result here (numbers may overlap)

void bignum::Sub(bint num1, const bignum& num2)
{
	// special cases
	if (num1 == 0) { this->Neg(num2); return; }
	if (num2.Equ0()) { this->Set(num1); return; }

	// length of decimal part
	bint i = num2.m_DecNum;
	if (i > m_DecMax) i = m_DecMax;
	m_DecNum = i;

	// negate decimal part
	const buint* s = num2.Base(-i);
	buint* d = this->Base(-i);
	buint cy = this->NegStr(d, s, i);
	d += i;
	s += i;

	// length of integer part
	i = num2.m_IntNum;
	if (i > m_IntMax) i = m_IntMax;
	m_IntNum = i;

	// sub number
	buint r;
	if (i > 0)
	{
		r = *s++ + cy;
		cy = (r < cy) ? 1 : 0;
		cy += ((buint)num1 < r);
		*d++ = (buint)num1 - r;
		i--;
	}

	// if source has no integer part
	else
	{
		r = num2.High() + cy;
		cy = (r < cy) ? 1 : 0;
		cy += ((buint)num1 < r);
		if (m_IntMax > 0)
		{
			m_IntNum = 1;
			*d++ = num1 - r;
		}
	}

	// add rest of integer part
	if (i > 0)
	{
		if (num1 < 0)
			cy = this->NegDecStr(cy, d, s, i); // negate with decrement
		else
		{
			if (cy == 1)
				this->NotStr(d, s, i);
			else
				cy = this->NegStr(d, s, i);
		}
		d += i;
	}

	// carry
	i = m_IntNum;
	buint k1 = (buint)((num1 < 0) ? -1 : 0);
	buint k2 = (i < num2.m_IntNum) ? *num2.Base(i) : num2.High();
	r = k1 - k2 - cy;
	if (i < m_IntMax)
	{
		m_IntNum = i + 1;
		d[0] = r;
	}

	// sign
	m_IsNeg = (bint)r < 0;
	
	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// sub unsigned number and bignum, store result here (numbers may overlap)

void bignum::SubU(buint num1, const bignum& num2)
{
	// special cases
	if (num1 == 0) { this->Neg(num2); return; }
	if (num2.Equ0()) { this->SetU(num1); return; }

	// length of decimal part
	bint i = num2.m_DecNum;
	if (i > m_DecMax) i = m_DecMax;
	m_DecNum = i;

	// negate decimal part
	const buint* s = num2.Base(-i);
	buint* d = this->Base(-i);
	buint cy = this->NegStr(d, s, i);
	d += i;
	s += i;

	// length of integer part
	i = num2.m_IntNum;
	if (i > m_IntMax) i = m_IntMax;
	m_IntNum = i;

	// sub number
	buint r;
	if (i > 0)
	{
		r = *s++ + cy;
		cy = (r < cy) ? 1 : 0;
		cy += (num1 < r);
		*d++ = num1 - r;
		i--;
	}

	// if source has no integer part
	else
	{
		r = num2.High() + cy;
		cy = (r < cy) ? 1 : 0;
		cy += (num1 < r);
		if (m_IntMax > 0)
		{
			m_IntNum = 1;
			*d++ = num1 - r;
		}
	}

	// add rest of integer part
	if (i > 0)
	{
		if (cy == 1)
			this->NotStr(d, s, i);
		else
			cy = this->NegStr(d, s, i);
		d += i;
	}

	// carry
	i = m_IntNum;
	buint k = (i < num2.m_IntNum) ? *num2.Base(i) : num2.High();
	r = - (bint)k - cy;
	if (i < m_IntMax)
	{
		m_IntNum = i + 1;
		d[0] = r;
	}

	// sign
	m_IsNeg = (bint)r < 0;
	
	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// sub bignum from this number (numbers may overlap)

void bignum::Sub(const bignum& num)
{
	// special cases
	if (this->Equ0()) { this->Neg(num); return; }
	if (num.Equ0()) { return; }
	if (num.Equ1()) { this->Dec(); return; }
	if (num.EquM1()) { this->Inc(); return; }
	if (this == &num) { this->Set0(); return; }

	// prepare length with 1 number (dec1, dec2, dec, len1, len2, len)
	BIGPREP1();

	// copy start of decimal part (or negate second number)
	buint cy = 0;
	if (dec1 > dec)
	{
		m_DecNum = dec1;
	}
	else if (dec2 > dec)
	{
		m_DecNum = dec2;
		cy = this->NegStr(this->Base(-dec2), num.Base(-dec2), dec2 - dec);
	}

	// operation on common data
	const buint* s = num.Base(-dec);
	buint* d = this->Base(-dec);
	bint i = dec + len;
	buint r;
	cy = this->SubStr(cy, d, s, i);
	s += i;
	d += i;

	// operation on larger part of one number
	if (len1 > len)
	{
		// dst = num1 - ((k=0 or -1) + cy)
		m_IntNum = len1;
		i = len1 - len;
		switch ((int)cy + (int)num.High())
		{
		case 1: // cy=1, k=0
			cy = this->DecStr(d, i);
			break;

		case -1: // cy=0, k=-1
			cy = this->IncStr(d, i);
			break;
		}
		d += i;
	}
	else if (len2 > len)
	{
		// dst = (0 or -1) - num2 - cy
		m_IntNum = len2;
		i = len2 - len;
		if (m_IsNeg)
			cy = this->NegDecStr(cy, d, s, i); // negate with decrement
		else
		{
			// only negate (start or continue)
			if (cy == 1) // k=0, cy=1
				this->NotStr(d, s, i);
			else // k=0, cy=0
				cy = this->NegStr(d, s, i);
		}
		d += i;
	}

	// carry
	len = m_IntNum;
	buint k1 = this->High();
	buint k2 = (len < num.m_IntNum) ? *num.Base(len) : num.High();
	r = k1 - k2 - cy;
	if (len < m_IntMax)
	{
		m_IntNum = len + 1;
		d[0] = r;
	}

	// sign
	m_IsNeg = (bint)r < 0;
	
	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// sub signed number from this number

void bignum::Sub(bint num)
{
	if (num < 0)
		this->AddU(-num);
	else
		this->SubU(num);
}

///////////////////////////////////////////////////////////////////////////////
// sub unsigned number from this number

void bignum::SubU(buint num)
{
	// special cases
	if (num == 0) { return; }
	if (num == 1) { this->Dec(); return; }

	// expand to overflow
	this->ExpInt(m_IntNum + 1);

	// sub number
	buint* d = this->Base();
	buint r;
	buint cy = 0;
	bint i = m_IntNum;
	if (i > 0)
	{
		r = d[0];
		cy = (r < num);
		*d++ = r - num;
		i--;
	}

	// carry
	if (cy != 0) cy = this->DecStr(d, i);

	// overflow
	r = this->High() - cy;

	// sign
	m_IsNeg = (bint)r < 0;

	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// inv sub - subtract this number from bignum (numbers may overlap)

void bignum::InvSub(const bignum& num)
{
	// special cases
	if (this->Equ0()) { this->Copy(num); return; }
	if (num.Equ0()) { this->Neg(); return; }
	if (this->Equ1()) { this->Dec(num); return; }
	if (this->EquM1()) { this->Inc(num); return; }

	// prepare length with 1 number (dec1, dec2, dec, len1, len2, len)
	BIGPREP1();

	// copy start of second decimal part (or negate first number)
	buint cy = 0;
	if (dec1 > dec)
	{
		m_DecNum = dec1;
		cy = this->NegStr(this->Base(-dec1), num.Base(-dec1), dec1 - dec);
	}
	else if (dec2 > dec)
	{
		m_DecNum = dec2;
		this->CopyStr(this->Base(-dec2), num.Base(-dec2), dec2 - dec);
	}

	// operation on common data
	const buint* s = num.Base(-dec);
	buint* d = this->Base(-dec);
	bint i = dec + len;
	buint r;
	cy = this->InvSubStr(cy, d, s, i);
	s += i;
	d += i;

	// operation on larger part of one number
	if (len1 > len)
	{
		// dst = (k=0 or -1) - num1 - cy
		m_IntNum = len1;
		i = len1 - len;
		if (num.m_IsNeg)
			cy = this->NegDecStr(cy, d, i); // negate with decrement
		else
		{
			// only negate (start or continue)
			if (cy == 1) // k=0, cy=1
				this->NotStr(d, i);
			else // k=0, cy=0
				cy = this->NegStr(d, i);
		}
		d += i;
	}
	else if (len2 > len)
	{
		// dst = num2 - (0 or -1) - cy
		m_IntNum = len2;
		i = len1 - len;
		switch ((int)cy + (int)this->High())
		{
		case 1: // cy=1, k=0
			cy = this->DecStr(d, s, i);
			break;

		case -1: // cy=0, k=-1
			cy = this->IncStr(d, s, i);
			break;

		default: // 0: cy=1, k=-1 / cy=0, k=0
			this->CopyStr(d, s, i);
		}
		d += i;
	}

	// carry
	len = m_IntNum;
	buint k1 = this->High();
	buint k2 = (len < num.m_IntNum) ? *num.Base(len) : num.High();
	r = k2 - k1 - cy;
	if (len < m_IntMax)
	{
		m_IntNum = len + 1;
		d[0] = r;
	}

	// sign
	m_IsNeg = (bint)r < 0;
	
	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// inv sub - subtract this number from signed number

void bignum::InvSub(bint num)
{
	// special cases
	if (this->Equ0()) { this->Set(num); return; }
	if (num == 0) { this->Neg(); return; }

	// expand to overflow
	this->ExpInt(m_IntNum + 1);

	// negate decimal part
	bint i = m_DecNum;
	buint* d = this->Base(-i);
	buint cy = this->NegStr(d, i);
	d += i;

	// sub number
	i = m_IntNum;
	buint r;
	if (i > 0)
	{
		r = d[0] + cy;
		cy = (r < cy) ? 1 : 0;
		cy += ((buint)num < r) ? 1 : 0;
		*d++ = (buint)num - r;
		i--;
	}

	// negate rest of number
	if (i > 0)
	{
		if (num < 0)
			cy = this->NegDecStr(cy, d, i); // negate with decrement
		else
		{
			if (cy == 1)
				this->NotStr(d, i);
			else
				cy = this->NegStr(d, i);
		}
		d += i;
	}

	// carry
	bint k = (num < 0) ? -1 : 0;
	r = k - (bint)this->High() - cy;

	// sign
	m_IsNeg = (bint)r < 0;

	// data reduction
	this->Reduce();
}

///////////////////////////////////////////////////////////////////////////////
// inv sub - subtract this number from unsigned number

void bignum::InvSubU(buint num)
{
	// special cases
	if (this->Equ0()) { this->SetU(num); return; }
	if (num == 0) { this->Neg(); return; }

	// expand to overflow
	this->ExpInt(m_IntNum + 1);

	// negate decimal part
	bint i = m_DecNum;
	buint* d = this->Base(-i);
	buint cy = this->NegStr(d, i);
	d += i;

	// sub number
	i = m_IntNum;
	buint r;
	if (i > 0)
	{
		r = d[0] + cy;
		cy = (r < cy) ? 1 : 0;
		cy += (num < r) ? 1 : 0;
		*d++ = num - r;
		i--;
	}

	// negate rest of number
	if (i > 0)
	{
		if (cy == 1)
			this->NotStr(d, i);
		else
			cy = this->NegStr(d, i);
		d += i;
	}

	// carry
	r = - (bint)this->High() - cy;

	// sign
	m_IsNeg = (bint)r < 0;

	// data reduction
	this->Reduce();
}
