/*
* 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 <securityerr.h>
#include "words.h"
#include "primes.h"
#include "algorithms.h"
#include "mont.h"
#include "stackinteger.h"

static TBool IsSmallPrime(TUint aK);

static inline void EliminateComposites(TUint* aS, TUint aPrime, TUint aJ, 
	TUint aMaxIndex)
	{
	for(; aJ<aMaxIndex; aJ+=aPrime)
		ArraySetBit(aS, aJ);
	}

static inline TInt FindLeastSignificantZero(TUint aX)
	{
	aX = ~aX;
	int i = 0;
	if( aX << 16 == 0 ) aX>>=16, i+=16;
	if( aX << 24 == 0 ) aX>>=8, i+=8;
	if( aX << 28 == 0 ) aX>>=4, i+=4;
	if( aX << 30 == 0 ) aX>>=2, i+=2;
	if( aX << 31 == 0 ) ++i;
	return i;
	}

static inline TInt FindFirstPrimeCandidate(TUint* aS, TUint aBitLength)
	{
	assert(aBitLength % WORD_BITS == 0);
	TUint i=0;
	//The empty statement at the end of this is stop warnings in all compilers
	for(; aS[i] == KMaxTUint && i<BitsToWords(aBitLength); i++) {;}

	if(i == BitsToWords(aBitLength))
		return -1;
	else
		{
		assert( FindLeastSignificantZero((TUint)(aS[i])) >= 0 );
		assert( FindLeastSignificantZero((TUint)(aS[i])) <= 31 );
		return i*WORD_BITS + FindLeastSignificantZero((TUint32)(aS[i]));
		}
	}

static inline TUint FindSmallestIndex(TUint aPrime, TUint aRemainder)
	{
	TUint& j = aRemainder;
	if(j)
		{
		j = aPrime - aRemainder;
		if( j & 0x1L )
			{
			//if j is odd then this + j is even so we actually want 
			//the next number for which (this + j % p == 0) st this + j is odd
			//that is: this + j + p == 0 mod p
			j += aPrime;
			}
		//Turn j into an index for a bit array representing odd numbers only
		j>>=1;
		}
	return j;
	}

static inline TUint RabinMillerRounds(TUint aBits) 
	{
	//See HAC Table 4.4
	if(aBits > 1300)
		return 2;
	if (aBits > 850)
		return 3;
	if (aBits > 650)
		return 4;
	if (aBits > 550)
		return 5;
	if (aBits > 450)
		return 6;
	if (aBits > 400)
		return 7;
	if (aBits > 350)
		return 8;
	if (aBits > 300)
		return 9;
	if (aBits > 250)
		return 12;
	if (aBits > 200)
		return 15;
	if (aBits > 150)
		return 18;
	if (aBits > 100)
		return 27;
	//All of the above are optimisations on the worst case.  The worst case
	//chance of odd composite integers being declared prime by Rabin-Miller is
	//(1/4)^t where t is the number of rounds.  Thus, t = 40 means that the
	//chance of declaring a composite integer prime is less than 2^(-80).  See
	//HAC Fact 4.25 and most of chapter 4 for more details.
	return 40;
	}

static TBool HasSmallDivisorL(const TInteger& aPossiblePrime)
	{
	assert(aPossiblePrime.IsOdd());
	//Start checking at the first odd prime, whether it is even should have
	//already been checked
	for( TUint i=1; i < KPrimeTableSize; i++ )
		{
		if( aPossiblePrime.ModuloL(KPrimeTable[i]) == 0 )
			{
			return ETrue;
			}
		}
	return EFalse;
	}

static TBool RabinMillerIterationL(const CMontgomeryStructure& aMont, 
	const TInteger& aProbablePrime, const TInteger& aBase)
	{
	//see HAC 4.24
	const TInteger& n = aProbablePrime;
	assert(n > KLastSmallPrimeSquared);
	assert(n.IsOdd());
	assert(aBase > TInteger::One());

	RInteger nminus1 = n.MinusL(TInteger::One());
	CleanupStack::PushL(nminus1);
	assert(aBase < nminus1);

	// 1) find (s | 2^s*r == n-1) where r is odd
	// we want the largest power of 2 that divides n-1
	TUint s=0;
	for(;;s++)
		{
		if(nminus1.Bit(s))
			{
			break;
			}
		}
	// (r = (n-1) / 2^s) which is equiv to (n-1 >>= s)
	RInteger r = RInteger::NewL(nminus1);
	CleanupStack::PushL(r);
	r >>= s;

	//At no point do we own y, aMont owns it
	const TInteger* y = &(aMont.ExponentiateL(aBase, r));

	TBool probablePrime = EFalse;
	
	TUint j=1;
	if( *y == TInteger::One() || *y == nminus1 )
		{
		probablePrime = ETrue;
		}
	else
		{
		for(j=1; j<s; j++)
			{
			y = &(aMont.SquareL(*y));
			if(*y == nminus1)
				{
				probablePrime = ETrue;
				break;
				}
			}
		}
	CleanupStack::PopAndDestroy(&r);
	CleanupStack::PopAndDestroy(&nminus1);//y,r,nminus1
	return probablePrime;
	}

static TBool RabinMillerTestL(const CMontgomeryStructure& aMont, 
	const TInteger& aProbablePrime, TUint aRounds) 
	{
	const TInteger& n = aProbablePrime;
	assert(n > KLastSmallPrimeSquared);
	
	RInteger nminus2 = n.MinusL(TInteger::Two());
	CleanupStack::PushL(nminus2);

	for(TUint i=0; i<aRounds; i++)
		{
		RInteger base = RInteger::NewRandomL(TInteger::Two(), nminus2);
		CleanupStack::PushL(base);
		if(!RabinMillerIterationL(aMont, n, base))
			{
			CleanupStack::PopAndDestroy(2, &nminus2);//base, nminus2
			return EFalse;
			}
		CleanupStack::PopAndDestroy(&base);
		}
	CleanupStack::PopAndDestroy(&nminus2);
	return ETrue;
	}

static TBool IsStrongProbablePrimeL(const TInteger& aPrime) 
	{
	CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aPrime);
	//This should be using short circuit evaluation
	TBool probablePrime = RabinMillerIterationL(*mont, aPrime, TInteger::Two())
		&& RabinMillerTestL(*mont, aPrime,RabinMillerRounds(aPrime.BitCount()));
	CleanupStack::PopAndDestroy(mont);
	return probablePrime;
	}

/* In the _vast_ majority of cases this simply checks that your chosen random
 * number is >= KLastSmallPrimeSquared and return EFalse and lets the normal
 * prime generation routines handle the situation.  In the case where it is
 * smaller, it generates a provable prime and returns ETrue.  The algorithm for
 * finding a provable prime < KLastPrimeSquared is not the most efficient in the
 * world, but two points come to mind
 * 1) The two if statements hardly _ever_ evaluate to ETrue in real life.
 * 2) Even when it is, the distribution of primes < KLastPrimeSquared is pretty
 * dense, so you aren't going to have check many.
 * This function is essentially here for two reasons:
 * 1) Ensures that it is possible to generate primes < KLastPrimeSquared (the
 * test code does this)
 * 2) Ensures that if you request a prime of a large bit size that there is an
 * even probability distribution across all integers < 2^aBits
 */
TBool TInteger::SmallPrimeRandomizeL(void)
	{
	TBool foundPrime = EFalse;
	//If the random number we've chosen is less than KLastSmallPrime,
	//testing for primality is easy.
	if(*this <= KLastSmallPrime)
		{
		//If Zero or One, or two, next prime number is two
		if(IsZero() || *this == One() || *this == Two())
			{
			CopyL(TInteger::Two());
			foundPrime = ETrue;
			}
		else
			{
			//Make sure any number we bother testing is at least odd
			SetBit(0);
			//Binary search the small primes.
			while(!IsSmallPrime(ConvertToUnsignedLong()))
				{
				//If not prime, add two and try the next odd number.

				//will never carry as the minimum size of an RInteger is 2
				//words.  Much bigger than KLastSmallPrime on 32bit
				//architectures.
				IncrementNoCarry(Ptr(), Size(), 2);
				}
			assert(IsSmallPrime(ConvertToUnsignedLong()));
			foundPrime = ETrue;
			}
		}
	else if(*this <= KLastSmallPrimeSquared)
		{
		//Make sure any number we bother testing is at least odd
		SetBit(0);

		while(HasSmallDivisorL(*this) && *this <= KLastSmallPrimeSquared)
			{
			//If not prime, add two and try the next odd number.

			//will never carry as the minimum size of an RInteger is 2
			//words.  Much bigger than KLastSmallPrime on 32bit
			//architectures.
			IncrementNoCarry(Ptr(), Size(), 2);
			}
		//If we exited while loop because it had no small divisor then it is
		//prime.  Otherwise, we've exceeded the limit of what we can provably
		//generate.  Therefore the normal prime gen routines will be run on it
		//now.
		if(*this < KLastSmallPrimeSquared)
			{
			foundPrime = ETrue;
			}
		}
	//This doesn't mean there is no such prime, simply means that the number
	//wasn't less than KSmallPrimeSquared and needs to be handled by the normal
	//prime generation routines.
	return foundPrime;
	}

void TInteger::PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)
	{
	assert(aBits > 1); 
	
	//"this" is "empty" currently.  Consists of Size() words of 0's.  This is just
	//checking that sign flag is positive as we don't set it later.
	assert(NotNegative());

	//Flag for the whole function saying if we've found a prime
	TBool foundProbablePrime = EFalse;

	//Find 2^aBits + 1 -- any prime we find must be less than this.
	RInteger max = RInteger::NewEmptyL(BitsToWords(aBits)+1);
	CleanupStack::PushL(max);
	max.SetBit(aBits);
	assert(max.BitCount()-1 == aBits);

	// aBits 	| approx number of odd numbers you must try to have a 50% 
	//			chance of finding a prime
	//---------------------------------------------------------
	// 512		| 122		
	// 1024		| 245
	// 2048		| 1023
	//Therefore if we are generating larger than 1024 bit numbers we'll use a
	//bigger bit array to have a better chance of avoiding re-generating it.
	TUint sLength = aBits > 1024 ? 1024 : 512;
	RInteger S = RInteger::NewEmptyL(BitsToWords(sLength));
	CleanupStack::PushL(S);

	while(!foundProbablePrime)
		{
		//Randomly choose aBits
		RandomizeL(aBits, aAttr);

		//If the random number chosen is less than KSmallPrimeSquared, we have a
		//special set of routines.
		if(SmallPrimeRandomizeL())
			{
			foundProbablePrime = ETrue;
			}
		else
			{
			//if it was <= KLastSmallPrimeSquared then it would have been
			//handled by SmallPrimeRandomizeL()
			assert(*this > KLastSmallPrimeSquared);

			//Make sure any number we bother testing is at least odd
			SetBit(0);

			//Ensure that this + 2*sLength < max
			RInteger temp = max.MinusL(*this);
			CleanupStack::PushL(temp);
			++temp;
			temp >>=1;
			if(temp < sLength)
				{
				//if this + 2*sLength >= max then we use a smaller sLength to
				//ensure we don't find a number that is outside of our bounds
				//(and bigger than our allocated memory for this)

				//temp must be less than KMaxTUint as sLength is a TUint 
				sLength = temp.ConvertToUnsignedLong();	
				}
			CleanupStack::PopAndDestroy(&temp);

			//Start at 1 as no point in checking against 2 (all odd numbers)
			for(TUint i=1; i<KPrimeTableSize; i++)
				{
				//no need to call ModuloL as we know KPrimeTable[i] is not 0
				TUint remainder = Modulo(*this, KPrimeTable[i]);
				TUint index = FindSmallestIndex(KPrimeTable[i], remainder);
				EliminateComposites(S.Ptr(), KPrimeTable[i], index, sLength);
				}
			TInt j = FindFirstPrimeCandidate(S.Ptr(), sLength);
			TInt prev = 0;
			for(; j>=0; j=FindFirstPrimeCandidate(S.Ptr(), sLength))
				{
				ArraySetBit(S.Ptr(), j);

				//should never carry as we earlier made sure that 2*j + this < max
				//where max is 1 bit more than we asked for.
				IncrementNoCarry(Ptr(), Size(), 2*(j-prev));

				assert(*this < max);
				assert(!HasSmallDivisorL(*this));

				prev = j;

				if( IsStrongProbablePrimeL(*this) )
					{
					foundProbablePrime = ETrue;
					break;
					}
				}
			//This clears the memory
			S.CopyL(0, EFalse);
			}
		}
	CleanupStack::PopAndDestroy(2, &max);
	}

EXPORT_C TBool TInteger::IsPrimeL(void) const
	{
	if( NotPositive() )
		{
		return EFalse;
		}
	else if( IsEven() )
		{
		return *this == Two();
		}
	else if( *this <= KLastSmallPrime )
		{
		assert(KLastSmallPrime < KMaxTUint);
		return IsSmallPrime(this->ConvertToUnsignedLong());
		}
	else if( *this <= KLastSmallPrimeSquared )
		{
		return !HasSmallDivisorL(*this);
		}
	else 
		{
		return !HasSmallDivisorL(*this) && IsStrongProbablePrimeL(*this);
		}
	}

// Method is excluded from coverage due to the problem with BullsEye on ONB.
// Manually verified that this method is functionally covered.
#ifdef _BullseyeCoverage
#pragma suppress_warnings on
#pragma BullseyeCoverage off
#pragma suppress_warnings off
#endif

static TBool IsSmallPrime(TUint aK) 
	{
	//This is just a binary search of our small prime table.
	TUint l = 0;
	TUint u = KPrimeTableSize;
	while( u > l )
		{
		TUint m = (l+u)>>1;
		TUint p = KPrimeTable[m];
		if(aK < p)
			u = m;
		else if (aK > p)
			l = m + 1;
		else
			return ETrue;
		}
	return EFalse;
	}