diff -r da2ae96f639b -r cd501b96611d crypto/weakcryptospi/source/bigint/primes.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/crypto/weakcryptospi/source/bigint/primes.cpp	Fri Nov 06 13:21:00 2009 +0200
@@ -0,0 +1,450 @@
+/*
+* 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;
+	}