/* Martin Johne 2006 */
#include "LargeInteger.h"
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>

//#define DEBUG_LARGE_INT

#ifdef DEBUG_LARGE_INT
	#include <stdio.h>
#endif

/********************************************************************/
/********************************************************************
/* construktors
/********************************************************************/

CLargeInteger::CLargeInteger(unsigned short sizeInBytes):
	negative(0), pOutString(0)
{
#ifdef DEBUG_LARGE_INT
	printf("-init-0\n");
#endif
	sizeShorts = (sizeInBytes >> 1) + (sizeInBytes % 2);
	if (sizeShorts < 6) sizeShorts = 6; // at least 48 bit
	pNumber   = new unsigned short[sizeShorts];
	memset(pNumber, 0,/* sizeof(unsigned short) **/ sizeShorts << 1);
}

/********************************************************************/

CLargeInteger::CLargeInteger(unsigned long initialValue, unsigned short sizeInBytes):
	negative(0), pOutString(0)
{
#ifdef DEBUG_LARGE_INT
	printf("-init_num-\n");
#endif
	sizeShorts = (sizeInBytes >> 1) + (sizeInBytes % 2);
	if (sizeShorts < 6) sizeShorts = 6; // at least 48 bit
	pNumber   = new unsigned short[sizeShorts];
	memset(pNumber, 0, /*sizeof(unsigned short) **/ sizeShorts << 1);
	*pNumber       = (unsigned short) (initialValue & 0x0000FFFF);
	*(pNumber + 1) = (unsigned short)((initialValue & 0xFFFF0000)>>16);
}

/********************************************************************/

// copy constructor
CLargeInteger::CLargeInteger(const CLargeInteger &copy):
	pOutString(0)
{
#ifdef DEBUG_LARGE_INT
	printf("-copy-\n");
#endif
	negative  = copy.negative;
	sizeShorts = copy.sizeShorts;
	pNumber   = new unsigned short[sizeShorts];
	memcpy(pNumber, copy.pNumber, /*sizeof(unsigned short) * */sizeShorts << 1);
}

/********************************************************************
/* destructor
/********************************************************************/

CLargeInteger::~CLargeInteger(void)
{
#ifdef DEBUG_LARGE_INT
	printf("-destr-\n");
#endif
	delete[] this->pNumber;
	delete[] this->pOutString;
}

/********************************************************************/
/********************************************************************
/* Operators
/********************************************************************/

bool CLargeInteger::operator == (const unsigned short number)
{
	if ( *(pNumber) == number )
	{
		for ( int i = 1; i < sizeShorts; i++ )
			if ( *(pNumber + i) ) return false;
	}
	else return false;

	return true;
}


/********************************************************************/

bool CLargeInteger::operator > (const CLargeInteger &compareLarger)
{
	unsigned short loopLen;

	if ( compareLarger.sizeShorts > sizeShorts )
	{
		for ( int i = compareLarger.sizeShorts - 1; i > sizeShorts - 1; i-- )
			if ( compareLarger.pNumber[i] ) return true;
		loopLen = sizeShorts - 1;
	}
	else
	{
		for ( int i = sizeShorts - 1; i > compareLarger.sizeShorts - 1; i-- )
			if ( pNumber[i] ) return true;
		loopLen = compareLarger.sizeShorts - 1;
	}

	for (int i = loopLen; i >= 0; i--)
		if ( pNumber[i] > compareLarger.pNumber[i] ) return true; 
		else if ( pNumber[i] < compareLarger.pNumber[i] ) return false;


	return false;
}

/********************************************************************/

bool CLargeInteger::operator < (const CLargeInteger &compareSmaller)
{
	unsigned short loopLen;

	if ( compareSmaller.sizeShorts > sizeShorts )
	{
		for ( int i = compareSmaller.sizeShorts - 1; i > sizeShorts - 1; i-- )
			if ( compareSmaller.pNumber[i] ) return false;
		loopLen = sizeShorts - 1;
	}
	else
	{
		for ( int i = sizeShorts - 1; i > compareSmaller.sizeShorts - 1; i-- )
			if ( pNumber[i] ) return false;
		loopLen = compareSmaller.sizeShorts - 1;
	}

	for (int i = loopLen; i >= 0; i--)
		if ( pNumber[i] < compareSmaller.pNumber[i] ) return true; 
		else if ( pNumber[i] > compareSmaller.pNumber[i] ) return false;

	return false;
}

/********************************************************************/

CLargeInteger& CLargeInteger::operator = (const CLargeInteger &assign)
{
	if (this != &assign) 
	{
#ifdef DEBUG_LARGE_INT
		printf("-assign_c-\n");
#endif
		negative = assign.negative;
	
		if (assign.sizeShorts >= sizeShorts)
            memcpy(pNumber, assign.pNumber, /*sizeof(unsigned short) */ sizeShorts << 1);
		else
		{
			memset(pNumber, 0, /*sizeof(unsigned short) * */ sizeShorts << 1);
			memcpy(pNumber, assign.pNumber, /*sizeof(unsigned short) *  */ assign.sizeShorts << 1);
		}
	}
	return *this;
}

/********************************************************************/

CLargeInteger& CLargeInteger::operator = (const unsigned long assign)
{
#ifdef DEBUG_LARGE_INT
		printf("-assign_i-\n");
#endif	
	memset((pNumber + 2), 0, /*sizeof(unsigned short) * */ (sizeShorts - 2) << 1 );

	*(pNumber)     = (unsigned short) (assign & 0x0000FFFF);
	*(pNumber + 1) = (unsigned short)((assign & 0xFFFF0000 ) >> 16);		

	return *this;
}

/********************************************************************/

CLargeInteger CLargeInteger::operator + (const CLargeInteger &add)
{
#ifdef DEBUG_LARGE_INT
		printf("-add_c-\n");
#endif
   	CLargeInteger tmp(add.sizeShorts>sizeShorts?add.sizeShorts << 1:sizeShorts << 1 );

	register unsigned long carry = 0;
	int loopLen = add.sizeShorts<sizeShorts?add.sizeShorts:sizeShorts;

	for (int i = 0; i < loopLen ; i++)
	{
		carry = *(pNumber + i) + *(add.pNumber + i) + carry;
		
		*(tmp.pNumber + i) = (unsigned short)(carry & 0x0000FFFF);
		carry = (carry & 0xFFFF0000) >> 16;
	}

	return tmp;
}

/********************************************************************/

CLargeInteger CLargeInteger::operator + (const unsigned long add)
{
#ifdef DEBUG_LARGE_INT
		printf("-add_i-\n");
#endif
	CLargeInteger tmp(add, sizeShorts << 1);
	register unsigned long carry = 0;

	for (int i = 0 ; i < sizeShorts; i++)
	{
		carry = *(pNumber + i) + *(tmp.pNumber + i) + carry;

		*(tmp.pNumber + i) = (unsigned short)(carry & 0x0000FFFF);
		carry = (carry & 0xFFFF0000) >> 16;
	}
	return tmp;
}

/********************************************************************/

CLargeInteger& CLargeInteger::operator += (const unsigned long add)
{
#ifdef DEBUG_LARGE_INT
		printf("-add+_i-\n");
#endif
	register unsigned long carry = add & 0x0000FFFF;

	for (int i = 0 ; i < sizeShorts; i++)
	{
		carry = *(pNumber + i) + carry;
		if (i == 1) carry += (add & 0xFFFF0000) >> 16;

		*(pNumber + i) = (unsigned short)(carry & 0x0000FFFF);
		carry = (carry & 0xFFFF0000) >> 16;
	}
	return *this;
}

/********************************************************************/

CLargeInteger& CLargeInteger::operator += (const CLargeInteger &add)
{
#ifdef DEBUG_LARGE_INT
		printf("-add+_c-\n");
#endif

	register unsigned long carry = 0;
	int loopLen = add.sizeShorts<sizeShorts?add.sizeShorts:sizeShorts;

	for (int i = 0; i < loopLen ; i++)
	{
		carry = *(pNumber + i) + *(add.pNumber + i) + carry;
		
		*(pNumber + i) = (unsigned short)(carry & 0x0000FFFF);//unsigned short(carry % 0x10000);
		carry = (carry & 0xFFFF0000) >> 16;
	}

	return *this;
}

CLargeInteger& CLargeInteger::operator ++ (void)
{
	register unsigned long carry = 1;

	for (int i = 0; i < this->sizeShorts ; i++)
	{
		carry = *(pNumber + i) + carry;
		*(pNumber + i) = (unsigned short)(carry & 0x0000FFFF);
		carry = (carry & 0xFFFF0000) >> 16;
		if ( carry == 0 ) return *this;
	}

	return *this;
}


/********************************************************************/

CLargeInteger CLargeInteger::operator * (const CLargeInteger &mul)
{
#ifdef DEBUG_LARGE_INT
		printf("-mul_c_invoke-\n");
#endif
	CLargeInteger tmp(mul.sizeShorts>sizeShorts?mul.sizeShorts << 1 :sizeShorts << 1);
	int loopLen = mul.sizeShorts<sizeShorts?mul.sizeShorts:sizeShorts;
	
	register unsigned long carry = 0;
	unsigned long  prod;
	unsigned short mulLow;
	
	for (unsigned short j = 0; j < loopLen; j++)
		for (unsigned short i = 0 ; i < loopLen - j; i++)
		{
			prod    = *(pNumber + j) * *(mul.pNumber + i);
			mulLow  = (unsigned short)(prod & 0x0000FFFF);					// low part of product
			carry   = (*(tmp.pNumber + i + j) + carry + mulLow);			// add old carry and low part to temp part
			*(tmp.pNumber + i + j) = (unsigned short)(carry & 0x0000FFFF);	// low part of addition is new temp part
			carry   = ((carry % 0xFFFF0000) >> 16) + ((prod % 0xFFFF0000) >> 16);	// new carry is high part of product plus high part of addition
		}

	return tmp;
}

/********************************************************************/

CLargeInteger& CLargeInteger::operator *= (const CLargeInteger &mul)
{
#ifdef DEBUG_LARGE_INT
		printf("-mul*=_c_invoke-\n");
#endif
	CLargeInteger tmp(mul.sizeShorts>sizeShorts?mul.sizeShorts << 1:sizeShorts << 1);
	int loopLen = mul.sizeShorts<sizeShorts?mul.sizeShorts:sizeShorts;
	
	register unsigned long carry = 0;
	unsigned long  prod;
	unsigned short mulLow;
	
	for (unsigned short j = 0; j < loopLen; j++)
		for (unsigned short i = 0 ; i < loopLen - j; i++)
		{
			prod    = *(pNumber + j) * *(mul.pNumber + i);
			mulLow  = (unsigned short)(prod & 0x0000FFFF);					// low part of product
			carry   = (*(tmp.pNumber + i + j) + carry + mulLow);			// add old carry and low part to temp part
			*(tmp.pNumber + i + j) = (unsigned short)(carry & 0x0000FFFF);	// low part of addition is new temp part
			carry   = ((carry & 0xFFFF0000) >> 16) + ((prod & 0xFFFF0000) >> 16);	// new carry is high part of product plus high part of addition
		}

	*this = tmp;

	return *this;
}

/********************************************************************/

CLargeInteger CLargeInteger::operator ^ (long exponent)
{
	#ifdef DEBUG_LARGE_INT
		printf("-pow\n");
	#endif
	
	if (exponent == 0) return CLargeInteger(0, this->sizeShorts << 2);
	if (exponent == 1) return *this;

	CLargeInteger result(1, this->sizeShorts << 2);
	CLargeInteger tmp(*this);

	while(exponent)
	{
		if (exponent & 1)
			result*=tmp;
		exponent>>=1;
		if (!exponent) break;
		tmp*=tmp;
	}

	return result;
}

/********************************************************************/

CLargeInteger& CLargeInteger::operator ^= (long exponent)
{
	#ifdef DEBUG_LARGE_INT
		printf("-pow+\n");
	#endif
	
	if (exponent == 0) { *this = 0; return *this; }
	if (exponent == 1) return *this;

	CLargeInteger tmp(*this);
	*this=1;

	while(exponent)
	{
		if (exponent & 1)
			*this*=tmp;
		exponent>>=1;
		if (!exponent) break;
		tmp*=tmp;
	}

	return *this;
}


CLargeInteger CLargeInteger::operator / (const CLargeInteger &div)
{



	CLargeInteger tmp(div.sizeShorts>sizeShorts?div.sizeShorts << 1:sizeShorts << 1);



	/*	int loopLen = mul.sizeShorts<sizeShorts?mul.sizeShorts:sizeShorts;
	
	register unsigned long carry = 0;
	unsigned long  prod;
	unsigned short mulLow;
	
	for (unsigned short j = 0; j < loopLen; j++)
		for (unsigned short i = 0 ; i < loopLen - j; i++)
		{
			prod    = *(pNumber + j) * *(mul.pNumber + i);
			mulLow  = (unsigned short)(prod % 0x10000);				// low part of product
			carry   = (*(tmp.pNumber + i + j) + carry + mulLow);	// add old carry and low part to temp part
			*(tmp.pNumber + i + j) = (unsigned short)(carry % 0x10000);	// low part of addition is new temp part
			carry   = (carry / 0x10000 + prod / 0x10000);					// new carry is high part of product plus high part of addition
		}
*/
	return tmp;
}

/********************************************************************/
/********************************************************************
/* methods
/********************************************************************/


unsigned short CLargeInteger::divideAndGiveCarry(unsigned short divisor)
{
	unsigned long carry = 0;
	
	for (int i = sizeShorts - 1; i >= 0; i--)
	{
		carry<<=16;
		carry += *(pNumber + i);
		*(pNumber + i) = (unsigned short)(carry / divisor);
		carry = (carry % divisor);
	}
	return (unsigned short)carry; // modulo value
}

/********************************************************************/

CLargeInteger CLargeInteger::pow(CLargeInteger &base, unsigned long exponent)
{
	#ifdef DEBUG_LARGE_INT
		printf("-pow_c\n");
		int mulcount = 0;
	#endif
	
	if (exponent == 0) return CLargeInteger(0, base.sizeShorts);
	if (exponent == 1) return base;

	CLargeInteger result(1, base.sizeShorts<<2);
	CLargeInteger tmp(base);

	while(exponent)
	{
		if (exponent & 1)
		{
			result*=tmp;
			#ifdef DEBUG_LARGE_INT
				mulcount++;
			#endif
		}
		exponent>>=1;
		if (!exponent) break;
		tmp*=tmp;
		#ifdef DEBUG_LARGE_INT
			mulcount++;
		#endif
	}
	
	#ifdef DEBUG_LARGE_INT
		printf("-pow_c------------->mulcount: %d\n", mulcount);
	#endif

	return result;
}

/********************************************************************/

void CLargeInteger::pow(unsigned long exponent)
{
	#ifdef DEBUG_LARGE_INT
		printf("-pow_self\n");
		int mulcount = 0;
	#endif

	if ( exponent == 0 )
	{
		*this = 1;
		return;
	}
	if ( exponent == 1 ) return;

	CLargeInteger tmp(*this);
	CLargeInteger base(*this);
	unsigned long resultExponent;
	char init = 1;

	while(exponent)
	{
		if (exponent == 1)
		{
			*this*=base;
			#ifdef DEBUG_LARGE_INT
				mulcount++;
				printf("-pow_c------------->mulcount: %d\n", mulcount);
			#endif
			return;
		}

		resultExponent = 1;

		while(resultExponent < exponent)
			if ( (resultExponent * 2) <= exponent )
			{
				if (init) *this*=*this; else tmp *= tmp;
				resultExponent*=2;
				#ifdef DEBUG_LARGE_INT
					mulcount++;
				#endif
			}
			else break;
		
		if (!init) 
		{
			*this*=tmp;
			#ifdef DEBUG_LARGE_INT
				mulcount++;
			#endif
		}
		else init = 0;

		exponent-=resultExponent;
		if (!exponent) break;
		tmp=base;
	}
	
	#ifdef DEBUG_LARGE_INT
		printf("-pow_c------------->mulcount: %d\n", mulcount);
	#endif

}

/********************************************************************/

void CLargeInteger::setZero()
{
	memset(pNumber, 0, /*sizeof(unsigned short) * */ sizeShorts << 1);
}

/********************************************************************/

void CLargeInteger::shiftLeftMax16(unsigned shift)
{
	if ( shift > 16 )
	{
		printf("Shifting values larger than are 16 not allowed in CLargeInteger::shifLeftMax16(unsigned shift).");
		abort();
	}
	
	unsigned short lastShort;
	unsigned long actualShort;

	lastShort = pNumber[0];
	pNumber[0]<<=shift;

	for ( unsigned short i = 1; i < sizeShorts; i++ )
	{
		actualShort = pNumber[i];
		actualShort <<= 16;
		actualShort |= lastShort;
		lastShort = pNumber[i];
		actualShort <<= shift;
        pNumber[i] = (unsigned short)(( actualShort & 0xFFFF0000 ) >> 16);
	}
}

/********************************************************************/

void CLargeInteger::shiftRightMax16(unsigned shift)
{
	if ( shift > 16 )
	{
		printf("Shifting values larger than are 16 not allowed in CLargeInteger::shifRightMax16(unsigned shift).");
		abort();
	}
	
	unsigned long lastShort;
	unsigned long actualShort;

	lastShort = pNumber[sizeShorts-1];
	pNumber[sizeShorts-1]>>=shift;

	for ( long i = sizeShorts - 2; i >= 0; i-- )
	{
		actualShort = pNumber[i];
		//actualShort <<= 16;
		actualShort |= ( lastShort << 16 );
		lastShort = pNumber[i];
		actualShort >>= shift;
        pNumber[i] = (unsigned short)( actualShort & 0x0000FFFF );
	}
}

/********************************************************************/

const char* CLargeInteger::toHexString()
{
	if (!pOutString) pOutString = new char[((sizeShorts * 1600 ) / 330 + 3) + ((sizeShorts * 1600 ) / 330 + 3) / 3];

	int pos = 0;
	int period = 1;

	// not nessecary but useful
	if ( *this == 0 )
	{
		*(pOutString) = '0';
		*(pOutString + 1) = '\0';
		return pOutString;
	}

	CLargeInteger largeIntCopy( *this );
	    
	// print Number into char string
	for ( ; ; pos++)
	{
		*(pOutString + pos) = (char)largeIntCopy.divideAndGiveCarry(16);
		if (*(pOutString + pos) < 10) *(pOutString + pos)+='0'; else *(pOutString + pos)+='A' - 10;

		if ( largeIntCopy == 0 ) break;
		if ( !(period % 4))
		{
			pos++;
			*(pOutString + pos) = '.';
		}
		period++;
	}
	
	// swap direction of char string
	char tmp;
	for ( int i = 0; i < (pos + 1) / 2; i++)
	{
		tmp =*(pOutString + i);
		*(pOutString + i) = *(pOutString + pos - i);
		*(pOutString + pos - i) = tmp;
	}
	
	// terminate string
	*(pOutString + pos + 1) = '\0';

	return pOutString;
}

/********************************************************************/

const char* CLargeInteger::toBinString()
{
	delete[] pOutString;
	pOutString = new char[sizeShorts * 2 * 8 + ( sizeShorts * 2 * 8 ) / 8 + 2];

	int pos = 0;
	int period = 1;

	// not nessecary but useful
	if ( *this == 0 )
	{
		*(pOutString) = '0';
		*(pOutString + 1) = '\0';
		return pOutString;
	}

	CLargeInteger largeIntCopy( *this );
	    
	// print Number into char string
	for ( ; ; pos++)
	{
		*(pOutString + pos) = (char)largeIntCopy.divideAndGiveCarry(2) + '0';
		
		if ( largeIntCopy == 0 ) break;
		if ( !(period % 8))
		{
			pos++;
			*(pOutString + pos) = '.';
		}
		period++;
	}
	
	// swap direction of char string
	char tmp;
	for ( int i = 0; i < (pos + 1) / 2; i++)
	{
		tmp =*(pOutString + i);
		*(pOutString + i) = *(pOutString + pos - i);
		*(pOutString + pos - i) = tmp;
	}
	
	// terminate string
	*(pOutString + pos + 1) = '\0';

	return pOutString;
}

/********************************************************************/

const char* CLargeInteger::toString()
{
#ifdef DEBUG_LARGE_INT
		printf("-toString_invoke-\n");
#endif
	if (!pOutString) pOutString = new char[((sizeShorts * 1600 ) / 330 + 3) + ((sizeShorts * 1600 ) / 330 + 3) / 3]; // 2 * 8 * 100 / 330

	int pos = 0;
	int period = 1;

	// not nessecary but useful
	if ( *this == 0 )
	{
		*(pOutString) = '0';
		*(pOutString + 1) = '\0';
		return pOutString;
	}

	CLargeInteger largeIntCopy( *this );
	    
	// print Number into char string
	for ( ; ; pos++)
	{

		*(pOutString + pos) = (char)('0' + largeIntCopy.divideAndGiveCarry(10));
		//*(pNumber) = *(pNumber) / 10;
		if ( largeIntCopy == 0 ) break;
		if ( !(period % 3))
		{
			pos++;
			*(pOutString + pos) = '.';
		}
		period++;
	}
	// swap direction of char string
	char tmp;
	for ( int i = 0; i < (pos + 1) / 2; i++)
	{
		tmp =*(pOutString + i);
		*(pOutString + i) = *(pOutString + pos - i);
		*(pOutString + pos - i) = tmp;
	}
	
	// terminate string
	*(pOutString + pos + 1) = '\0';

#ifdef DEBUG_LARGE_INT
		printf("-toString_returning-\n");
#endif

	return pOutString;
}



