/*

* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).

* All rights reserved.

* This component and the accompanying materials are made available

* under the terms of the License "Eclipse Public License v1.0"

* which accompanies this distribution, and is available

* at the URL "http://www.eclipse.org/legal/epl-v10.html".

*

* Initial Contributors:

* Nokia Corporation - initial contribution.

*

* Contributors:

*

* Description: 

*

*/

#include <bigint.h>

#include <e32std.h>

#include <euserext.h>

#include <securityerr.h>

#include "words.h"

#include "algorithms.h"

#include "windowslider.h"

#include "stackinteger.h"

#include "mont.h"

/**

* Creates a new buffer containing the big-endian binary representation of this

* integer.

*

* Note that it does not support the exporting of negative integers.

*

* @return	The new buffer.

* 

* @leave KErrNegativeExportNotSupported	If this instance is a negative integer.

*

* @publishedPartner

* @released

*/

EXPORT_C HBufC8* TInteger::BufferLC() const

	{

	if(IsNegative())

		{

		User::Leave(KErrNegativeExportNotSupported);

		}

	TUint bytes = ByteCount();

	HBufC8* buf = HBufC8::NewMaxLC(bytes);

	TUint8* bufPtr = (TUint8*)(buf->Ptr());

	TUint8* regPtr = (TUint8*)Ptr();

	// we internally store the number little endian, as a string we want it big

	// endian

	for(TUint i=0,j=bytes-1; i<bytes; )

		{

		bufPtr[i++] = regPtr[j--];

		}

	return buf;

	}

EXPORT_C HBufC8* TInteger::BufferWithNoTruncationLC() const

 	{

 	if(IsNegative())

 		{

 		User::Leave(KErrNegativeExportNotSupported);

 		}

 	TUint wordCount = Size();

 	TUint bytes = (wordCount)*WORD_SIZE;

  	HBufC8* buf = HBufC8::NewMaxLC(bytes);

 	TUint8* bufPtr = (TUint8*)(buf->Ptr());

	TUint8* regPtr = (TUint8*)Ptr();

	for(TUint i=0,j=bytes-1; i<bytes; )

 		{

 		bufPtr[i++] = regPtr[j--];

 		}

	return buf;

	}

/** 

* Gets the number of words required to represent this RInteger.

* 

* @return	The size of the integer in words.

*

* @publishedPartner

* @released

*/

EXPORT_C TUint TInteger::WordCount() const

	{

	return CountWords(Ptr(), Size());

	}

/**

* Gets the number of bytes required to represent this RInteger.

* 

* @return	The size of the integer in bytes.

* 

* @publishedPartner

* @released

*/

EXPORT_C TUint TInteger::ByteCount() const

	{

	TUint wordCount = WordCount();

	if(wordCount)

		{

		return (wordCount-1)*WORD_SIZE + BytePrecision((Ptr())[wordCount-1]);

		}

	else 

		{

		return 0;

		}

	}

/** 

* Get the number of bits required to represent this RInteger.

* 

* @return	The size of the integer in bits.

* 

* @publishedPartner

* @released

*/

EXPORT_C TUint TInteger::BitCount() const

	{

	TUint wordCount = WordCount();

	if(wordCount)

		{

		return (wordCount-1)*WORD_BITS + BitPrecision(Ptr()[wordCount-1]);

		}

	else 

		{

		return 0;

		}

	}

//These 3 declarations instantiate a constant 0, 1, 2 for ease of use and

//quick construction elsewhere in the code.  Note that the functions

//returning references to this static data return const references as you can't

//modify the ROM ;)

//word 0: Size of storage in words

//word 1: Pointer to storage

//word 2: LSW of storage

//word 3: MSW of storage

//Note that the flag bits in word 1 (Ptr()) are zero in the case of a positive

//stack based integer (SignBit == 0, IsHeapBasedBit == 0)

const TUint KBigintZero[4] = {2, (TUint)(KBigintZero+2), 0, 0};

const TUint KBigintOne[4] = {2, (TUint)(KBigintOne+2), 1, 0};

const TUint KBigintTwo[4] = {2, (TUint)(KBigintTwo+2), 2, 0};

/** 

 * Gets the TInteger that represents zero

 *

 * @return	The TInteger representing zero

 */

EXPORT_C const TInteger& TInteger::Zero(void)

	{

	return *reinterpret_cast<const TStackInteger64*>(KBigintZero);

	}

/** 

 * Gets the TInteger that represents one

 *

 * @return	The TInteger representing one

 */

EXPORT_C const TInteger& TInteger::One(void)

	{

	return *reinterpret_cast<const TStackInteger64*>(KBigintOne);

	}

/** 

 * Gets the TInteger that represents two

 *

 * @return	The TInteger representing two

 */

EXPORT_C const TInteger& TInteger::Two(void)

	{

	return *reinterpret_cast<const TStackInteger64*>(KBigintTwo);

	}

EXPORT_C RInteger TInteger::PlusL(const TInteger& aOperand) const

	{

	RInteger sum;

    if (NotNegative())

		{

        if (aOperand.NotNegative())

            sum = PositiveAddL(*this, aOperand);

        else

            sum = PositiveSubtractL(*this, aOperand);

		}

    else

		{

        if (aOperand.NotNegative())

            sum = PositiveSubtractL(aOperand, *this);

        else

			{

            sum = PositiveAddL(*this, aOperand);

			sum.SetSign(TInteger::ENegative);

			}

		}

	return sum;

	}

EXPORT_C RInteger TInteger::MinusL(const TInteger& aOperand) const

	{

	RInteger diff;

    if (NotNegative())

		{

        if (aOperand.NotNegative())

            diff = PositiveSubtractL(*this, aOperand);

        else

            diff = PositiveAddL(*this, aOperand);

		}

    else

		{

        if (aOperand.NotNegative())

			{

            diff = PositiveAddL(*this, aOperand);

			diff.SetSign(TInteger::ENegative);

			}

        else

            diff = PositiveSubtractL(aOperand, *this);

		}

	return diff;

	}

EXPORT_C RInteger TInteger::TimesL(const TInteger& aOperand) const

	{

	RInteger product = PositiveMultiplyL(*this, aOperand);

	if (NotNegative() != aOperand.NotNegative())

		{

		product.Negate();

		}

	return product;

	}

EXPORT_C RInteger TInteger::DividedByL(const TInteger& aOperand) const

	{

	RInteger quotient;

	RInteger remainder;

	DivideL(remainder, quotient, *this, aOperand);

	remainder.Close();

	return quotient;

	}

EXPORT_C RInteger TInteger::DividedByL(TUint aOperand) const

	{

	TUint remainder;

	RInteger quotient;

	DivideL(remainder, quotient, *this, aOperand);

	return quotient;

	}

EXPORT_C RInteger TInteger::ModuloL(const TInteger& aOperand) const

	{

	RInteger remainder;

	RInteger quotient;

	DivideL(remainder, quotient, *this, aOperand);

	quotient.Close();

	return remainder;

	}

EXPORT_C TUint TInteger::ModuloL(TUint aOperand) const

	{

	if(!aOperand)

		{

		User::Leave(KErrDivideByZero);

		}

	return Modulo(*this, aOperand);

	}

EXPORT_C RInteger TInteger::SquaredL() const

	{

	//PositiveMultiplyL optimises for the squaring case already

	//Any number squared is positive, no need for negative handling in TimesL

	return PositiveMultiplyL(*this, *this);

	}

EXPORT_C RInteger TInteger::ExponentiateL(const TInteger& aExponent) const

	{

	//See HAC 14.85

	// 1.1 Precomputation

	// g1 <- g

	// g2 <- g^2

	RInteger g2 = SquaredL();

	CleanupStack::PushL(g2);

	RInteger g1 = RInteger::NewL(*this);

	CleanupStack::PushL(g1);

	TWindowSlider slider(aExponent);

	// 1.2 

	// For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2

	TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1

	RRArray<RInteger> powerArray(count+1); //+1 because we append g1

	User::LeaveIfError(powerArray.Append(g1));

	CleanupStack::Pop(); //g1

	CleanupClosePushL(powerArray);

	for(TUint k=1; k <= count; k++)

		{

		RInteger g2iplus1 = g2.TimesL(powerArray[k-1]);

		//This append can't fail as the granularity is set high enough

		//plus we've already called Append once which will alloc to the 

		//set granularity

		powerArray.Append(g2iplus1);

		}

	// 2 A <- 1, i <- t

	RInteger A = RInteger::NewL(One());

	CleanupStack::PushL(A);

	TInt i = aExponent.BitCount() - 1;

	// 3 While i>=0 do:

	while( i>=0 )

		{

		// 3.1 If ei == 0 then A <- A^2

		if(!aExponent.Bit(i))

			{

			A *= A;

			i--;

			}

		// 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1

		// and do:

		// A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value]

		else

			{

			slider.FindNextWindow(i);

			assert(slider.Length() >= 1);

			for(TUint j=0; j<slider.Length(); j++)

				{

				A *= A;

				}

			A *= powerArray[slider.Value()>>1];

			i -= slider.Length();

			}

		}

	CleanupStack::Pop(&A);

	CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2

	return A;

	}

EXPORT_C RInteger TInteger::ModularMultiplyL(const TInteger& aA, const TInteger& aB,

	const TInteger& aMod) 

	{

	RInteger product = aA.TimesL(aB);

	CleanupStack::PushL(product);

	RInteger reduced = product.ModuloL(aMod);

	CleanupStack::PopAndDestroy(&product); 

	return reduced;

	}

EXPORT_C RInteger TInteger::ModularExponentiateL(const TInteger& aBase, 

	const TInteger& aExp, const TInteger& aMod) 

	{

	CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aMod);

	RInteger result = RInteger::NewL(mont->ExponentiateL(aBase, aExp));

	CleanupStack::PopAndDestroy(mont);

	return result;

	}

EXPORT_C RInteger TInteger::GCDL(const TInteger& aOperand) const

	{

	//Binary GCD algorithm -- see HAC 14.4.1

	//with a slight variation -- our g counts shifts rather than actually

	//shifting.  We then do one shift at the end.

	assert(NotNegative());

	assert(aOperand.NotNegative());

	RInteger x = RInteger::NewL(*this);

	CleanupStack::PushL(x);

	RInteger y = RInteger::NewL(aOperand);

	CleanupStack::PushL(y);

	// 1 Ensure x >= y

	if( x < y )

		{

		TClassSwap(x, y);

		}

	TUint g = 0;

	// 2 while x and y even x <- x/2, y <- y/2

	while( x.IsEven() && y.IsEven() )

		{

		x >>= 1;

		y >>= 1;

		++g;

		}

	// 3 while x != 0

	while( x.NotZero() )

		{

		// 3.1 while x even x <- x/2

		while( x.IsEven() )

			{

			x >>= 1;

			}

		// 3.2 while y even y <- y/2

		while( y.IsEven() )

			{

			y >>= 1;

			}

		// 3.3 t <- abs(x-y)/2

		RInteger t = x.MinusL(y);

		t >>= 1;

		t.SetSign(TInteger::EPositive);

		// 3.4 If x>=y then x <- t else y <- t

		if( x >= y )

			{

			x.Set(t);

			}

		else 

			{

			y.Set(t);

			}

		}

	// 4 Return (g*y) (equiv to y<<=g as our g was counting shifts not actually

	//shifting)

	y <<= g;

	CleanupStack::Pop(&y);

	CleanupStack::PopAndDestroy(&x); 

	return y;

	}

EXPORT_C RInteger TInteger::InverseModL(const TInteger& aMod) const

	{

	assert(aMod.NotNegative());

	RInteger result;

	if(IsNegative() || *this>=aMod)

		{

		RInteger temp = ModuloL(aMod);

		CleanupClosePushL(temp);

		result = temp.InverseModL(aMod);

		CleanupStack::PopAndDestroy(&temp);

		return result;

		}

	if(aMod.IsEven())

		{

		if( !aMod || IsEven() )

			{

			return RInteger::NewL(Zero());

			}

		if( *this == One() )

			{

			return RInteger::NewL(One());

			}

		RInteger u = aMod.InverseModL(*this); 

		CleanupClosePushL(u);

		if(!u)

			{

			result = RInteger::NewL(Zero());

			}

		else 

			{

			//calculates (aMod*(*this-u)+1)/(*this) 

			result = MinusL(u);

			CleanupClosePushL(result);

			result *= aMod;

			++result;

			result /= *this;

			CleanupStack::Pop(&result); 

			}

		CleanupStack::PopAndDestroy(&u);

		return result;

		}

	result = RInteger::NewEmptyL(aMod.Size());

	CleanupClosePushL(result);

	RInteger workspace = RInteger::NewEmptyL(aMod.Size() * 4);

	TUint k = AlmostInverse(result.Ptr(), workspace.Ptr(), Ptr(), Size(),

		aMod.Ptr(), aMod.Size());

	DivideByPower2Mod(result.Ptr(), result.Ptr(), k, aMod.Ptr(), aMod.Size());

	workspace.Close();

	CleanupStack::Pop(&result);

	return result;

	}

EXPORT_C TInteger& TInteger::operator+=(const TInteger& aOperand)

	{

	this->Set(PlusL(aOperand));

    return *this;

	}

EXPORT_C TInteger& TInteger::operator-=(const TInteger& aOperand)

	{

	this->Set(MinusL(aOperand));

    return *this;

	}

EXPORT_C TInteger& TInteger::operator*=(const TInteger& aOperand)

	{

	this->Set(TimesL(aOperand));

	return *this;

	}

EXPORT_C TInteger& TInteger::operator/=(const TInteger& aOperand)

	{

	this->Set(DividedByL(aOperand));

	return *this;

	}

EXPORT_C TInteger& TInteger::operator%=(const TInteger& aOperand)

	{

	this->Set(ModuloL(aOperand));

	return *this;

	}

EXPORT_C TInteger& TInteger::operator+=(TInt aOperand)

	{

	TStackInteger64 operand(aOperand);

	*this += operand;

	return *this;

	}

EXPORT_C TInteger& TInteger::operator-=(TInt aOperand)

	{

	TStackInteger64 operand(aOperand);

	*this -= operand;

	return *this;

	}

EXPORT_C TInteger& TInteger::operator*=(TInt aOperand)