/*!
	@file
	@brief 多倍長整数クラステンプレート実装

	静的に桁を設定できる多倍長整数クラステンプレートの実装

	定義は"MultiInteger.h"

	@author Juna
*/


#ifndef Juna_Multi_Integer_Hpp
#define Juna_Multi_Integer_Hpp


//	以前に"MultiInteger.h"が単独でincludeされていれば
#ifdef Juna_Multi_Integer_H
//	インスタンス化モジュールと判断
	#define MultiInteger_Inline 
#else
//	でないなら普通にインライン定義
	#define MultiInteger_Inline inline
#endif


#include "MultiInteger.h"

namespace Juna {

/*代入**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &MultiInteger<Figure,DT,D2T>::operator=(digit2_t rhs)
{
	Clear();
	Digit[1] = digit_t(rhs >> digit_bit);
	Digit[0] = digit_t(rhs);
	return *this;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &MultiInteger<Figure,DT,D2T>::operator=(uint32 rhs)
{
	switch (sizeof(digit_t))
	{
	case 1:
		Digit[0] = rhs;			Digit[1] = rhs >> 8;
		Digit[2] = rhs >> 16;	Digit[3] = rhs >> 24;
		break;
	case 2:
		Digit[0] = rhs;		Digit[1] = rhs >> 16;
		break;
	default:
		Digit[0] = rhs;
		break;
	}
	int i = (sizeof(int32) + sizeof(digit_t) - 1) / sizeof(digit_t);
	for (;i < Figure;i++)
		Digit[i] = 0;
	return *this;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &MultiInteger<Figure,DT,D2T>::operator=(int32 rhs)
{
	const digit_t fill = 0 - (rhs < 0);
	switch (sizeof(digit_t))
	{
	case 1:
		Digit[0] = rhs;			Digit[1] = rhs >> 8;
		Digit[2] = rhs >> 16;	Digit[3] = rhs >> 24;
		break;
	case 2:
		Digit[0] = rhs;		Digit[1] = rhs >> 16;
		break;
	case 4:
		Digit[0] = rhs;
		break;
	default:
		Digit[0] = fill & ~0xFFFFFFFF | rhs;
		break;
	}
	int i = (sizeof(int32) + sizeof(digit_t) - 1) / sizeof(digit_t);
	for (;i < Figure;i++)
		Digit[i] = fill;
	return *this;
}

/*文字列代入**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &
	MultiInteger<Figure,DT,D2T>::AssignDecimal(const char *string)
{
	const int pow10[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000};
	Clear();
	int figure = 1;
	uint32 tmp = 0;
	for (const char *c = string;'0' <= *c && *c <= '9';c++)
	{
		(tmp *= 10) += *c - '0';
		if (figure == 9)
		{
			(*this *= 1000000000) += tmp;
			figure = 0;tmp = 0;
		}
		figure++;
	}
	(*this *= pow10[figure-1]) += tmp;
	return *this;
}

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &
	MultiInteger<Figure,DT,D2T>::AssignSignedDecimal(const char *string)
{
	bool minus = false;
	if (*string == '+')
		string++;
	else if (*string == '-')
	{
		minus = true;
		string++;
	}
	AssignDecimal(string);
	if (minus)
		SetNegative();
	return *this;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &
	MultiInteger<Figure,DT,D2T>::AssignHex(const char *string)
{
	Clear();
	int figure = 1;
	uint32 tmp = 0;
	if (string[0] == '0' && (string[1] == 'x' || string[1] == 'X'))
		string += 2;
	for (const char *c = string;1;c++)
	{
		if ('0' <= *c && *c <= '9')
			(tmp <<= 4) += *c - '0';
		else if ('A' <= *c && *c <= 'F')
			(tmp <<= 4) += *c - 'A' + 10;
		else if ('a' <= *c && *c <= 'f')
			(tmp <<= 4) += *c - 'a' + 10;
		else
			break;
		if (figure == 8)
		{
			(*this <<= 32) += tmp;
			figure = 0;tmp = 0;
		}
		figure++;
	}
	(*this <<= 4 * (figure - 1)) += tmp;
	return *this;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &
	MultiInteger<Figure,DT,D2T>::AssignOctal(const char *string)
{
	Clear();
	int figure = 1;
	uint32 tmp = 0;
	for (const char *c = string;'0' <= *c && *c <= '7';c++)
	{
		(tmp <<= 3) += *c - '0';
		if (figure == 10)
		{
			(*this <<= 30) += tmp;
			figure = 0;tmp = 0;
		}
		figure++;
	}
	(*this <<= 3 * (figure - 1)) += tmp;
	return *this;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &
	MultiInteger<Figure,DT,D2T>::AssignBinary(const char *string)
{
	Clear();
	int figure = 1;
	uint32 tmp = 0;
	for (const char *c = string;*c == '0' && *c == '1';c++)
	{
		(tmp <<= 1) += *c - '0';
		if (figure == 32)
		{
			(*this <<= 32) += tmp;
			figure = 0;tmp = 0;
		}
		figure++;
	}
	(*this <<= figure - 1) += tmp;
	return *this;
}


/*加算**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
bool MultiInteger<Figure,DT,D2T>::Add(MyType &dest,const MyType &lhs,const MyType &rhs)
{
	digit_t carrier = 0;
	for (int i = 0;i < Figure;i++)
		carrier = SetDigit(dest.Digit[i],digit2_t(lhs[i]) + rhs[i] + carrier);
	return carrier & 1;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
bool MultiInteger<Figure,DT,D2T>::Increment(MyType &dest,const MyType &src)
{
	digit_t carrier = 1;
	for (int i = 0;i < Figure;i++)
		carrier = SetDigit(dest.Digit[i],digit2_t(src[i]) + carrier);
	return carrier & 1;
}

/*減算**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
bool MultiInteger<Figure,DT,D2T>::Subtract(MyType &dest,const MyType &lhs,const MyType &rhs)
{
	bool carrier = 0;
	for (int i = 0;i < Figure;i++)
		carrier = SetDigit(dest.Digit[i],digit2_t(lhs[i]) - rhs[i] - carrier) & 1;
	return carrier;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
bool MultiInteger<Figure,DT,D2T>::Decrement(MyType &dest,const MyType &src)
{
	bool carrier = 1;
	for (int i = 0;i < Figure;i++)
		carrier = SetDigit(dest.Digit[i],src.Digit[i] - carrier) & 1;
	return carrier;
}

/*乗算**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::Multiply(MyType &dest,const MyType &lhs,const MyType &rhs)
{
	dest.Clear();
	for (int i = 0;i < Figure;i++)
	{
		digit_t carrier = 0;
		for (int j = 0;j < Figure - i;j++)
			carrier = SetDigit(dest.Digit[i+j],lhs[i] * rhs[j] + dest[i+j] + carrier);
	}
}

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::MultiplyEx(DoubleType &dest,const MyType &lhs,const MyType &rhs)
{
	dest.Clear();
	for (int i = 0;i < Figure;i++)
	{
		digit_t carrier = 0;
		for (int j = 0;j < Figure;j++)
			carrier = SetDigit(dest.Digit[i+j],lhs[j] * rhs[i] + dest[i+j] + carrier);
		dest.Digit[i + Figure] = carrier;
	}
}

/*除算**************************************************************/
/*剰余**************************************************************/

//	符号無し割り算
/*
	@param[out] quotient 商
	@param[out] remainder 余り
	@param[in] dividend 被除数
	@param[in] divisor 除数

	@pre &divisor != &quotient && &divisor != &remainder && divisor != 0
	@pre &quotient != &remainder
*/
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::DivideEx(
	MyType &quotient,MyType &remainder,
	const MyType &dividend,const MyType &divisor)
{
	const int sor_figure = divisor.GetByteFigure();		//除数の桁
	const int dend_figure = dividend.GetByteFigure();	//被除数の桁
	if (sor_figure == 0)
		throw ;//Zero Divide
	if (dend_figure <= sizeof(digit2_t) && sor_figure <= sizeof(digit2_t))
	{
		digit2_t sor = divisor.GetDigit2();
		digit2_t dend = dividend.GetDigit2();
		quotient = dend / sor;
		remainder = dend % sor;
		return;
	}
	if (sor_figure <= 3)
	{
		const uint32 sor = divisor.GetUInt32();
		const MyType dend = dividend;
		uint32 carrier = 0;
		switch (sor_figure)
		{
		case 3:carrier = dend.GetByteDigit(dend_figure - 2);
		case 2:carrier += dend.GetByteDigit(dend_figure - 1) << 8;
		}
		carrier >>=  24 - (sor_figure  << 3);
		quotient.Clear();
		for (int i = dend_figure - sor_figure;i >= 0;i--)
		{
			uint32 tmp = dend.GetByteDigit(i) + (carrier << 8);
			quotient.SetByteDigit(i,tmp / sor);
			carrier = tmp % sor;
		}
		remainder = carrier;
		return;
	}
	// 除数がたくさん
	int cmp = Compare(dividend.Digit,(dend_figure+sizeof(digit_t)-1) / sizeof(digit_t),
					  divisor.Digit,(sor_figure+sizeof(digit_t)-1) / sizeof(digit_t));
	if (cmp <= 0)	// 被除数がそれ以下
	{
		if (cmp < 0)
		{
			remainder = dividend;
			quotient.Clear();
		}
		else
		{
			remainder.Clear();
			quotient = 1;
		}
		return;
	}

//	大まかな除数（上位三桁）
	const uint32 sor_head = (divisor.GetByteDigit(sor_figure-1) << 16)
						  + (divisor.GetByteDigit(sor_figure-2) << 8)
						  + divisor.GetByteDigit(sor_figure-3);
	remainder = dividend;	// 余り
	quotient.Clear();
// 大まかな余り
	int carrier = (remainder.GetByteDigit(dend_figure-1) << 8)
				+ remainder.GetByteDigit(dend_figure-2);
	for (int i = dend_figure - 3;i >= sor_figure - 3;i--)
	{
		carrier = (carrier << 8) + remainder.GetByteDigit(i);	// 大まか計算用の桁を追加
		int q = carrier / sor_head;	// 大まかに商を求める
		if (q)
		{
			MyType tmp = divisor * q;	// 暫定商から被除数を計算して
			tmp <<= (i - (sor_figure - 3)) * 8;

			while (remainder < tmp)	// 大きすぎたら減らしながら確認
			{
				q--;
				tmp -= (divisor << (i - (sor_figure - 3)) * 8);
			}
			if (!q)
				continue;
			quotient.SetByteDigit(i - (sor_figure - 3),q);	//この桁の商
			remainder -= tmp;	// 商の分だけ余りを減らす
			// 大まか余り更新
			carrier = (remainder.GetByteDigit(i + 2) << 16)
					+ (remainder.GetByteDigit(i + 1) << 8)
					+ remainder.GetByteDigit(i);
		}
	}
	return;
}


/*シフト**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::ShiftLeft(MyType &dest,const MyType &lhs,int rhs)
{
	const int fs = rhs / digit_bit;
	const int bs = rhs & (digit_bit - 1);
	int i;
	if (bs == 0)	//悲しいけど digit_t(x) << (sizeof(digit_t) * 8) は不定なのよね
	{
		for (i = Figure - 1;i >= fs;i--)
			dest.Digit[i] = lhs[i-fs];
	}
	else
	{
		for (i = Figure - 1;i > fs;i--)
			dest.Digit[i] = (lhs[i-fs] << bs) + (lhs[i-fs-1] >> (digit_bit - bs));
		dest.Digit[i--] = lhs[0] << bs;
	}
	for (;i >= 0;i--)
		dest.Digit[i] = 0;
}

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::ShiftRight(MyType &dest,const MyType &lhs,int rhs)
{
	const int fs = rhs / digit_bit;
	const int bs = rhs & (digit_bit - 1);
	int i;
	if (bs == 0)	//悲しいけど digit_t(x) << (sizeof(digit_t) * 8) は不定なのよね
	{
		for (i = 0;i <= Figure - 1 - fs;i++)
			dest.Digit[i] = lhs[i+fs];
	}
	else
	{
		for (i = 0;i < Figure - 1 - fs;i++)
			dest.Digit[i] = (lhs[i+fs] >> bs) + (lhs[i+fs+1] << (digit_bit - bs));
		dest.Digit[i++] = lhs[Figure-1] >> bs;
	}
	for (;i < Figure;i++)
		dest.Digit[i] = 0;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::ArithmeticShiftRight(MyType &dest,const MyType &lhs,int rhs)
{
	const int fs = rhs / digit_bit;
	const int bs = rhs & (digit_bit - 1);
	const digit_t fill = digit_t(0 - ((lhs[Figure-1] >> (digit_bit - 1)) & 1));
	int i;
	if (bs == 0)	//悲しいけど digit_t(x) << (sizeof(digit_t) * 8) は不定なのよね
	{
		for (i = 0;i <= Figure - 1 - fs;i++)
			dest.Digit[i] = lhs[i+fs] >> bs;
	}
	else
	{
		for (i = 0;i < Figure - 1 - fs;i++)
			dest.Digit[i] = (lhs[i+fs] >> bs) + (lhs[i+fs+1] << (digit_bit - bs));
		dest.Digit[i++] = (lhs[Figure-1] >> bs) + (fill << (digit_bit - bs));
	}
	for (;i < Figure;i++)
		dest.Digit[i] = fill;
}

/*ビット**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::Negate(MyType &dest,const MyType &src)
{
	digit_t carrier = 1;
	for (int i = 0;i < Figure;i++)
		carrier = SetDigit(dest.Digit[i],static_cast<byte>(~src[i]) + carrier);
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::BitNot(MyType &dest,const MyType &src)
{
	for (int i = 0;i < Figure;i++)
		dest.Digit[i] = ~src[i];
}

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::BitAnd(MyType &dest,const MyType &lhs,const MyType &rhs)
{
	for (int i = 0;i < Figure;i++)
		dest.Digit[i] = lhs[i] & rhs[i];
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::BitOr(MyType &dest,const MyType &lhs,const MyType &rhs)
{
	for (int i = 0;i < Figure;i++)
		dest.Digit[i] = lhs[i] | rhs[i];
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::BitXor(MyType &dest,const MyType &lhs,const MyType &rhs)
{
	for (int i = 0;i < Figure;i++)
		dest.Digit[i] = lhs[i] ^ rhs[i];
}

/*参照**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
int MultiInteger<Figure,DT,D2T>::GetByteFigure(void) const
{
	int i;
	for (i = Figure * sizeof(digit_t) - 1;i >= 0;i--)
	{
		if ((Digit[i / sizeof(digit_t)] & (0xFF << (i & (sizeof(digit_t) - 1)) * 8)) != 0)
			break;
	}
	return i+1;
}

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
char *MultiInteger<Figure,DT,D2T>::toDecimalString(char *buf,bool comma) const
{
	if (*this == 0)
	{
		buf[0] = '0';buf[1] = '\0';
		return buf;
	}

//	uint32で扱える範囲の1000^n
	const uint32 block_size = 1000000000;
	char *c = buf;
	MyType tmp = *this;

	MyType decimal = 1;
	{
		MultiInteger<Figure+1+3/sizeof(digit_t),digit_t,digit2_t> decimal_plus = block_size;
		while (tmp.Compare(decimal_plus) > 0)
		{
			decimal.Assign(decimal_plus);
			decimal_plus *= block_size;
		}
	}
	{
		MyType q;
		DivideEx(q,tmp,tmp,decimal);
		uint32 n = q.GetUInt32();
		for (uint32 i = block_size/10;i >= 1;i /= 10)
			if (n / i)
			{
				*c++ = ((n / i) % 10) + '0';
				if (comma && (i == 1 || i == 1000 || i == 1000000))
					*c++ = ',';
			}
	}

	while (decimal > 1)
	{
		decimal /= block_size;
		MyType q;
		DivideEx(q,tmp,tmp,decimal);
		uint32 n = q.GetUInt32();
		for (uint32 i = block_size/10;i >= 1;i /= 10)
		{
			*c++ = ((n / i) % 10) + '0';
			if (comma && (i == 1 || i == 1000 || i == 1000000))
				*c++ = ',';
		}
	}
	if (comma)
		c--;
	*c = '\0';
	return buf;
}

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
const char *MultiInteger<Figure,DT,D2T>::GetString(bool signed_) const
{
	static char buf[Figure * sizeof(digit_t) * 4 + 1];
	if (signed_)
		return toSignedDecimalString(buf,false);
	else
		return toDecimalString(buf,false);
}

/*配列代入**************************************************************/

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &MultiInteger<Figure,DT,D2T>::AssignArray(const digit_t *digit,int size)
{
	int i;
	for (i = 0;i < size;i++)
		Digit[i] = digit[i];
	for (;i < Figure;i++)
		Digit[i] = 0;
	return *this;
}
template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
MultiInteger<Figure,DT,D2T> &MultiInteger<Figure,DT,D2T>::AssignSignedArray(const digit_t *digit,int size)
{
	const digit_t fill = 0 - ((digit[size-1] >> (digit_bit - 1)) & 1);
	int i;
	for (i = 0;i < size;i++)
		Digit[i] = digit[i];
	for (;i < Figure;i++)
		Digit[i] = fill;
	return *this;
}


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

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

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::SignedMultiplyEx(DoubleType &dest,const MyType &lhs,const MyType &rhs)
{
	if (lhs.isMinus())
	{
		if (rhs.isMinus())
			MultiplyEx(dest,-lhs,-rhs);
		else
		{
			MultiplyEx(dest,-lhs,rhs);
			dest.SetNegative();
		}
	}
	else
	{
		if (rhs.isMinus())
		{
			MultiplyEx(dest,lhs,-rhs);
			dest.SetNegative();
		}
		else
			MultiplyEx(dest,lhs,rhs);
	}
}

template<int Figure,typename DT,typename D2T>
MultiInteger_Inline
void MultiInteger<Figure,DT,D2T>::SignedDivideEx(
	MyType &quotient,MyType &remainder,
	const MyType &dividend,const MyType &divisor)
{
	if (dividend.isMinus())
	{
		if (divisor.isMinus())
			DivideEx(quotient,remainder,-dividend,-divisor);
		else
		{
			DivideEx(quotient,remainder,-dividend,divisor);
			quotient.SetNegative();
		}
		remainder.SetNegative();
	}
	else
	{
		if (divisor.isMinus())
		{
			DivideEx(quotient,remainder,dividend,-divisor);
			quotient.SetNegative();
		}
		else
			DivideEx(quotient,remainder,dividend,divisor);
	}
}

}//namespace Juna

#endif