/*

* 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 <euserext.h>

#include "algorithms.h"

#include "words.h"

#include "windowslider.h"

#include "mont.h"

CMontgomeryStructure* CMontgomeryStructure::NewL(

	const TInteger& aModulus)

	{

	CMontgomeryStructure* self = CMontgomeryStructure::NewLC(aModulus);

	CleanupStack::Pop(self);

	return self;

	}

CMontgomeryStructure* CMontgomeryStructure::NewLC(

	const TInteger& aModulus)

	{

	CMontgomeryStructure* self = new(ELeave) CMontgomeryStructure;

	CleanupStack::PushL(self);

	self->ConstructL(aModulus);

	return self;

	}

CMontgomeryStructure::~CMontgomeryStructure()

	{

	iModulus.Close();

	iModulusInv.Close();

	iWorkspace.Close();

	iResult.Close();

	}

void CMontgomeryStructure::ConstructL(const TInteger& aModulus)

	{

	User::LeaveIfError(aModulus.IsOdd() ? KErrNone : KErrArgument);

	iModulusInv = RInteger::NewEmptyL(aModulus.Size());

	iWorkspace = RInteger::NewEmptyL(5*aModulus.Size());

	iModulus = RInteger::NewL(aModulus);

	iResult = RInteger::NewEmptyL(aModulus.Size());

	RecursiveInverseModPower2(iModulusInv.Ptr(), iWorkspace.Ptr(), 

		iModulus.Ptr(), iModulus.Size());

	}

CMontgomeryStructure::CMontgomeryStructure()

	{

	}

TInteger& CMontgomeryStructure::ConvertInL(TInteger& aInteger) const

	{

	aInteger <<= WordsToBits(iModulus.Size());

	aInteger %= iModulus;

	return aInteger;

	}

TInteger& CMontgomeryStructure::ConvertOutL(TInteger& aInteger) const

	{

	TUint* const T = iWorkspace.Ptr();

	TUint* const R = aInteger.Ptr();

	const TUint N = iModulus.Size();

	User::LeaveIfError((aInteger.Size() <= N) ? KErrNone : KErrArgument);

	CopyWords(T, aInteger.Ptr(), aInteger.Size());

	SetWords(T + aInteger.Size(), 0, 2*N - aInteger.Size());

	MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);

	return aInteger;

	}

const TInteger& CMontgomeryStructure::ReduceL(

	const TInteger& aInteger) const

	{

	RInteger temp = RInteger::NewL(aInteger);

	CleanupStack::PushL(temp);

	ConvertInL(temp);

	iResult.CopyL(ConvertOutL(temp), EFalse);

	CleanupStack::PopAndDestroy(&temp);

	return iResult;

	}

const TInteger& CMontgomeryStructure::MultiplyL(const TInteger& aA, 

	const TInteger& aB) const

	{

	RInteger a = RInteger::NewL(aA);

	CleanupStack::PushL(a);

	RInteger b = RInteger::NewL(aB);

	CleanupStack::PushL(b);

	DoMultiplyL(iResult, ConvertInL(a), ConvertInL(b));

	ConvertOutL(iResult);

	CleanupStack::PopAndDestroy(&b); 

	CleanupStack::PopAndDestroy(&a); 

	return iResult;

	}

void CMontgomeryStructure::DoMultiplyL(TInteger& aResult, const TInteger& aA,

	const TInteger& aB) const

	{

	User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument);

	TUint* const T = iWorkspace.Ptr();

	TUint* const R = aResult.Ptr();

	const TUint N = iModulus.Size();

	const TUint* const aReg = aA.Ptr();

	const TUint* const bReg = aB.Ptr();

	const TUint aSize = aA.Size();

	const TUint bSize = aB.Size();

	User::LeaveIfError((aSize <= N && bSize <= N) ? KErrNone : KErrArgument);

	AsymmetricMultiply(T, T+2*N, aReg, aSize, bReg, bSize);

	SetWords(T+aSize+bSize, 0, 2*N - aSize - bSize);

	MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);

	}

const TInteger& CMontgomeryStructure::SquareL(const TInteger& aA) const

	{

	RInteger a = RInteger::NewL(aA);

	CleanupStack::PushL(a);

	DoSquareL(iResult, ConvertInL(a));

	ConvertOutL(iResult);

	CleanupStack::PopAndDestroy(&a);

	return iResult;

	}

void CMontgomeryStructure::DoSquareL(TInteger& aResult, const TInteger& aA) const

	{

	User::LeaveIfError((aResult.Size() == iModulus.Size()) ? KErrNone : KErrArgument);

	TUint* const T = iWorkspace.Ptr();

	TUint* const R = aResult.Ptr();

	const TUint N = iModulus.Size();

	const TUint* const aReg = aA.Ptr();

	const TUint aSize = aA.Size();

	User::LeaveIfError((aSize <= N) ? KErrNone : KErrArgument);

	RecursiveSquare(T, T+2*N, aReg, aSize);

	SetWords(T+2*aSize, 0, 2*N-2*aSize);

	MontgomeryReduce(R, T+2*N, T, iModulus.Ptr(), iModulusInv.Ptr(), N);

	}

const TInteger& CMontgomeryStructure::ExponentiateL(

	const TInteger& aBase, const TInteger& aExponent) const

	{

	//See HAC 14.85

	if ((iResult.Size() != iModulus.Size()) ||

		(aBase >= iModulus) ||

		(!aBase.IsPositive()) ||

		(!aExponent.IsPositive()))

		{

		User::Leave(KErrArgument);

		}

	// 1.1 Precomputation

	// g1 <- g

	// g2 <- g^2

	RInteger g2 = RInteger::NewL(aBase);

	CleanupStack::PushL(g2);

	ConvertInL(g2);

	//ConvertIn can shrink g2, because we call DoSquare on g2, g2 must be the same size as the modulus

	g2.CleanGrowL(iModulus.Size());

	RInteger g1 = RInteger::NewL(g2);

	CleanupStack::PushL(g1);

	DoSquareL(g2, g2);

	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 gi = RInteger::NewEmptyL(iModulus.Size());

		DoMultiplyL(gi, g2, powerArray[k-1]);

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

		}

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

	RInteger temp = RInteger::NewL(TInteger::One());

	CleanupStack::PushL(temp);

	ConvertInL(temp);

	RInteger& A = iResult;

	//Set A to one converted in for this modulus without changing the memory size of A (iResult)

	A.CopyL(temp, EFalse); 

	CleanupStack::PopAndDestroy(&temp);

	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))

			{

			DoSquareL(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++)

				{

				DoSquareL(A, A);

				}

			DoMultiplyL(A, A, powerArray[slider.Value()>>1]);

			i -= slider.Length();

			}

		}

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

	return ConvertOutL(A); // A == iResult

	}