1 /*

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

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

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

     6 * which accompanies this distribution, and is available

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

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: 

    15 *

    16 */

    17 

    18 

    19 #include <random.h>

    20 #include <bigint.h>

    21 #include <e32std.h>

    22 #include <euserext.h>

    23 #include <securityerr.h>

    24 #include "words.h"

    25 #include "algorithms.h"

    26 #include "windowslider.h"

    27 #include "stackinteger.h"

    28 #include "mont.h"

    29 

    30 

    31 /**

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

    33 * integer.

    34 *

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

    36 *

    37 * @return	The new buffer.

    38 * 

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

    40 *

    41 */

    42 EXPORT_C HBufC8* TInteger::BufferLC() const

    43 	{

    44 	if(IsNegative())

    45 		{

    46 		User::Leave(KErrNegativeExportNotSupported);

    47 		}

    48 	TUint bytes = ByteCount();

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

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

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

    52 

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

    54 	// endian

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

    56 		{

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

    58 		}

    59 	return buf;

    60 	}

    61 

    62 EXPORT_C HBufC8* TInteger::BufferWithNoTruncationLC() const

    63  	{

    64  	if(IsNegative())

    65  		{

    66  		User::Leave(KErrNegativeExportNotSupported);

    67  		}

    68  	

    69  	TUint wordCount = Size();

    70  	TUint bytes = (wordCount)*WORD_SIZE;

    71      

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

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

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

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

    76  		{

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

    78  		}

    79   

    80 	return buf;

    81 	}

    82 

    83 /** 

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

    85 * 

    86 * @return	The size of the integer in words.

    87 *

    88 */

    89 EXPORT_C TUint TInteger::WordCount() const

    90 	{

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

    92 	}

    93 

    94 /**

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

    96 * 

    97 * @return	The size of the integer in bytes.

    98 * 

    99 */

   100 EXPORT_C TUint TInteger::ByteCount() const

   101 	{

   102 	TUint wordCount = WordCount();

   103 	if(wordCount)

   104 		{

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

   106 		}

   107 	else 

   108 		{

   109 		return 0;

   110 		}

   111 	}

   112 

   113 /** 

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

   115 * 

   116 * @return	The size of the integer in bits.

   117 * 

   118 */

   119 EXPORT_C TUint TInteger::BitCount() const

   120 	{

   121 	TUint wordCount = WordCount();

   122 	if(wordCount)

   123 		{

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

   125 		}

   126 	else 

   127 		{

   128 		return 0;

   129 		}

   130 	}

   131 

   132 

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

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

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

   136 //modify the ROM ;)

   137 //word 0: Size of storage in words

   138 //word 1: Pointer to storage

   139 //word 2: LSW of storage

   140 //word 3: MSW of storage

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

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

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

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

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

   146 

   147 /** 

   148  * Gets the TInteger that represents zero

   149  *

   150  * @return	The TInteger representing zero

   151  */

   152 EXPORT_C const TInteger& TInteger::Zero(void)

   153 	{

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

   155 	}

   156 

   157 /** 

   158  * Gets the TInteger that represents one

   159  *

   160  * @return	The TInteger representing one

   161  */

   162 EXPORT_C const TInteger& TInteger::One(void)

   163 	{

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

   165 	}

   166 	

   167 /** 

   168  * Gets the TInteger that represents two

   169  *

   170  * @return	The TInteger representing two

   171  */

   172 EXPORT_C const TInteger& TInteger::Two(void)

   173 	{

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

   175 	}

   176 

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

   178 	{

   179 	RInteger sum;

   180     if (NotNegative())

   181 		{

   182         if (aOperand.NotNegative())

   183             sum = PositiveAddL(*this, aOperand);

   184         else

   185             sum = PositiveSubtractL(*this, aOperand);

   186 		}

   187     else

   188 		{

   189         if (aOperand.NotNegative())

   190             sum = PositiveSubtractL(aOperand, *this);

   191         else

   192 			{

   193             sum = PositiveAddL(*this, aOperand);

   194 			sum.SetSign(TInteger::ENegative);

   195 			}

   196 		}

   197 	return sum;

   198 	}

   199 

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

   201 	{

   202 	RInteger diff;

   203     if (NotNegative())

   204 		{

   205         if (aOperand.NotNegative())

   206             diff = PositiveSubtractL(*this, aOperand);

   207         else

   208             diff = PositiveAddL(*this, aOperand);

   209 		}

   210     else

   211 		{

   212         if (aOperand.NotNegative())

   213 			{

   214             diff = PositiveAddL(*this, aOperand);

   215 			diff.SetSign(TInteger::ENegative);

   216 			}

   217         else

   218             diff = PositiveSubtractL(aOperand, *this);

   219 		}

   220 	return diff;

   221 	}

   222 

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

   224 	{

   225 	RInteger product = PositiveMultiplyL(*this, aOperand);

   226 

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

   228 		{

   229 		product.Negate();

   230 		}

   231 	return product;

   232 	}

   233 

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

   235 	{

   236 	RInteger quotient;

   237 	RInteger remainder;

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

   239 	remainder.Close();

   240 	return quotient;

   241 	}

   242 

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

   244 	{

   245 	RInteger remainder;

   246 	RInteger quotient;

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

   248 	quotient.Close();

   249 	return remainder;

   250 	}

   251 

   252 EXPORT_C TUint TInteger::ModuloL(TUint aOperand) const

   253 	{

   254 	if(!aOperand)

   255 		{

   256 		User::Leave(KErrDivideByZero);

   257 		}

   258 	return Modulo(*this, aOperand);

   259 	}

   260 

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

   262 	const TInteger& aMod) 

   263 	{

   264 	RInteger product = aA.TimesL(aB);

   265 	CleanupStack::PushL(product);

   266 	RInteger reduced = product.ModuloL(aMod);

   267 	CleanupStack::PopAndDestroy(&product); 

   268 	return reduced;

   269 	}

   270 

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

   272 	const TInteger& aExp, const TInteger& aMod) 

   273 	{

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

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

   276 	CleanupStack::PopAndDestroy(mont);

   277 	return result;

   278 	}

   279 

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

   281 	{

   282 	//Binary GCD algorithm -- see HAC 14.4.1

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

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

   285 	assert(NotNegative());

   286 	assert(aOperand.NotNegative());

   287 

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

   289 	CleanupStack::PushL(x);

   290 	RInteger y = RInteger::NewL(aOperand);

   291 	CleanupStack::PushL(y);

   292 

   293 	// 1 Ensure x >= y

   294 	if( x < y )

   295 		{

   296 		TClassSwap(x, y);

   297 		}

   298 

   299 	TUint g = 0;

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

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

   302 		{

   303 		x >>= 1;

   304 		y >>= 1;

   305 		++g;

   306 		}

   307 	// 3 while x != 0

   308 	while( x.NotZero() )

   309 		{

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

   311 		while( x.IsEven() )

   312 			{

   313 			x >>= 1;

   314 			}

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

   316 		while( y.IsEven() )

   317 			{

   318 			y >>= 1;

   319 			}

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

   321 		RInteger t = x.MinusL(y);

   322 		t >>= 1;

   323 		t.SetSign(TInteger::EPositive);

   324 

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

   326 		if( x >= y )

   327 			{

   328 			x.Set(t);

   329 			}

   330 		else 

   331 			{

   332 			y.Set(t);

   333 			}

   334 		}

   335 	

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

   337 	//shifting)

   338 	y <<= g;

   339 	CleanupStack::Pop(&y);

   340 	CleanupStack::PopAndDestroy(&x); 

   341 	return y;

   342 	}

   343 

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

   345 	{

   346 	assert(aMod.NotNegative());

   347 

   348 	RInteger result;

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

   350 		{

   351 		RInteger temp = ModuloL(aMod);

   352 		CleanupClosePushL(temp);

   353 		result = temp.InverseModL(aMod);

   354 		CleanupStack::PopAndDestroy(&temp);

   355 		return result;

   356 		}

   357 

   358 	if(aMod.IsEven())

   359 		{

   360 		if( !aMod || IsEven() )

   361 			{

   362 			return RInteger::NewL(Zero());

   363 			}

   364 		if( *this == One() )

   365 			{

   366 			return RInteger::NewL(One());

   367 			}

   368 		RInteger u = aMod.InverseModL(*this); 

   369 		CleanupClosePushL(u);

   370 		if(!u)

   371 			{

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

   373 			}

   374 		else 

   375 			{

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

   377 			result = MinusL(u);

   378 			CleanupClosePushL(result);

   379 			result *= aMod;

   380 			++result;

   381 			result /= *this;

   382 			CleanupStack::Pop(&result); 

   383 			}

   384 		CleanupStack::PopAndDestroy(&u);

   385 		return result;

   386 		}

   387 

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

   389 	CleanupClosePushL(result);

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

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

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

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

   394 	workspace.Close();

   395 	CleanupStack::Pop(&result);

   396 

   397 	return result;

   398 	}

   399 

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

   401 	{

   402 	this->Set(PlusL(aOperand));

   403     return *this;

   404 	}

   405 

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

   407 	{

   408 	this->Set(MinusL(aOperand));

   409     return *this;

   410 	}

   411 

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

   413 	{

   414 	this->Set(TimesL(aOperand));

   415 	return *this;

   416 	}

   417 

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

   419 	{

   420 	this->Set(DividedByL(aOperand));

   421 	return *this;

   422 	}

   423 

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

   425 	{

   426 	this->Set(ModuloL(aOperand));

   427 	return *this;

   428 	}

   429 

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

   431 	{

   432 	TStackInteger64 operand(aOperand);

   433 	*this += operand;

   434 	return *this;

   435 	}

   436 

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

   438 	{

   439 	TStackInteger64 operand(aOperand);

   440 	*this -= operand;

   441 	return *this;

   442 	}

   443 

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

   445 	{

   446 	TStackInteger64 operand(aOperand);

   447 	*this *= operand;

   448 	return *this;

   449 	}

   450 

   451 EXPORT_C TInteger& TInteger::operator--()

   452 	{

   453     if (IsNegative())

   454 		{

   455         if (Increment(Ptr(), Size()))

   456 			{

   457             CleanGrowL(2*Size());

   458             (Ptr())[Size()/2]=1;

   459 			}

   460 		}

   461     else

   462 		{

   463         if (Decrement(Ptr(), Size()))

   464 			{

   465 			this->CopyL(-1);

   466 			}

   467 		}

   468     return *this;	

   469 	}

   470 

   471 EXPORT_C TInteger& TInteger::operator++()

   472 	{

   473 	if(NotNegative())

   474 		{

   475 		if(Increment(Ptr(), Size()))

   476 			{

   477 			CleanGrowL(2*Size());

   478 			(Ptr())[Size()/2]=1;

   479 			}

   480 		}

   481 	else

   482 		{

   483 		DecrementNoCarry(Ptr(), Size());

   484 		if(WordCount()==0)

   485 			{

   486 			this->CopyL(Zero());

   487 			}

   488 		}

   489 	return *this;

   490 	}

   491 

   492 EXPORT_C TInteger& TInteger::operator <<=(TUint aBits)

   493 	{

   494 	const TUint wordCount = WordCount();

   495 	const TUint shiftWords = aBits / WORD_BITS;

   496 	const TUint shiftBits = aBits % WORD_BITS;

   497 

   498 	CleanGrowL(wordCount+BitsToWords(aBits));

   499 	ShiftWordsLeftByWords(Ptr(), wordCount + shiftWords, shiftWords);

   500 	ShiftWordsLeftByBits(Ptr()+shiftWords, wordCount + BitsToWords(shiftBits), 

   501 		shiftBits);

   502 	return *this;

   503 	}

   504 

   505 EXPORT_C TInteger& TInteger::operator >>=(TUint aBits)

   506 	{

   507 	const TUint wordCount = WordCount();

   508 	const TUint shiftWords = aBits / WORD_BITS;

   509 	const TUint shiftBits = aBits % WORD_BITS;

   510 

   511 	ShiftWordsRightByWords(Ptr(), wordCount, shiftWords);

   512 	if(wordCount > shiftWords)

   513 		{

   514 		ShiftWordsRightByBits(Ptr(), wordCount - shiftWords, shiftBits);

   515 		}

   516 	if(IsNegative() && WordCount()==0) // avoid negative 0

   517 		{

   518 		SetSign(EPositive);

   519 		}

   520 	return *this;

   521 	}

   522 

   523 EXPORT_C TInt TInteger::UnsignedCompare(const TInteger& aThat) const

   524 	{

   525 	TUint size = WordCount();

   526 	TUint thatSize = aThat.WordCount();

   527 

   528 	if( size == thatSize )

   529 		return Compare(Ptr(), aThat.Ptr(), size);

   530 	else

   531 		return size > thatSize ? 1 : -1;

   532 	}

   533 

   534 EXPORT_C TInt TInteger::SignedCompare(const TInteger& aThat) const

   535 	{

   536     if (NotNegative())

   537 		{

   538         if (aThat.NotNegative())

   539             return UnsignedCompare(aThat);

   540         else

   541             return 1;

   542 		}

   543     else

   544 		{

   545         if (aThat.NotNegative())

   546             return -1;

   547         else

   548             return -UnsignedCompare(aThat);

   549 		}

   550 	}

   551 

   552 EXPORT_C TBool TInteger::operator!() const

   553 	{

   554 	//Ptr()[0] is just a quick way of weeding out non-zero numbers without

   555 	//doing a full WordCount() == 0.  Very good odds that a non-zero number

   556 	//will have a bit set in the least significant word

   557 	return IsNegative() ? EFalse : (Ptr()[0]==0 && WordCount()==0);

   558 	}

   559 

   560 EXPORT_C TInt TInteger::SignedCompare(TInt aInteger) const

   561 	{

   562 	TStackInteger64 temp(aInteger);

   563 	return SignedCompare(temp);

   564 	}

   565 

   566 /* TBool IsPrimeL(void) const 

   567  * and all primality related functions are implemented in primes.cpp */

   568 

   569 EXPORT_C TBool TInteger::Bit(TUint aBitPos) const

   570 	{

   571 	if( aBitPos/WORD_BITS >= Size() )

   572 		{

   573 		return 0;

   574 		}

   575 	else 

   576 		{

   577 		return (((Ptr())[aBitPos/WORD_BITS] >> (aBitPos % WORD_BITS)) & 1);

   578 		}

   579 	}

   580 

   581 EXPORT_C void TInteger::SetBit(TUint aBitPos) 

   582 	{

   583 	if( aBitPos/WORD_BITS < Size() )

   584 		{

   585 		ArraySetBit(Ptr(), aBitPos);

   586 		}

   587 	}

   588 

   589 EXPORT_C void TInteger::Negate() 

   590 	{

   591 	if(!!(*this)) //don't flip sign if *this==0

   592 		{

   593 		SetSign(TSign((~Sign())&KSignMask));

   594 		}

   595 	}

   596 

   597 EXPORT_C void TInteger::CopyL(const TInteger& aInteger, TBool aAllowShrink)

   598 	{

   599 	if(aAllowShrink)

   600 		{

   601 		CleanResizeL(aInteger.Size());

   602 		}

   603 	else

   604 		{

   605 		CleanGrowL(aInteger.Size());

   606 		}

   607 	Construct(aInteger);

   608 	}

   609 

   610 EXPORT_C void TInteger::CopyL(TInt aInteger, TBool aAllowShrink)

   611 	{

   612 	if(aAllowShrink)

   613 		{

   614 		CleanResizeL(2);

   615 		}

   616 	else

   617 		{

   618 		CleanGrowL(2);

   619 		}

   620 	Construct(aInteger);

   621 	}

   622 

   623 EXPORT_C void TInteger::Set(const RInteger& aInteger)

   624 	{

   625 	assert(IsHeapBased());

   626 	Mem::FillZ(Ptr(), WordsToBytes(Size()));

   627 	User::Free(Ptr());

   628 	iPtr = aInteger.iPtr;

   629 	iSize = aInteger.iSize;

   630 	}

   631 

   632 RInteger TInteger::PositiveAddL(const TInteger &aA, const TInteger& aB) const

   633 	{

   634 	RInteger sum = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));

   635 	const word aSize = aA.Size();

   636 	const word bSize = aB.Size();

   637 	const word* const aReg = aA.Ptr();

   638 	const word* const bReg = aB.Ptr();

   639 	word* const sumReg = sum.Ptr();

   640 

   641 	word carry;

   642 	if (aSize == bSize)

   643 		carry = Add(sumReg, aReg, bReg, aSize);

   644 	else if (aSize > bSize)

   645 		{

   646 		carry = Add(sumReg, aReg, bReg, bSize);

   647 		CopyWords(sumReg+bSize, aReg+bSize, aSize-bSize);

   648 		carry = Increment(sumReg+bSize, aSize-bSize, carry);

   649 		}

   650 	else

   651 		{

   652 		carry = Add(sumReg, aReg, bReg, aSize);

   653 		CopyWords(sumReg+aSize, bReg+aSize, bSize-aSize);

   654 		carry = Increment(sumReg+aSize, bSize-aSize, carry);

   655 		}

   656 

   657 	if (carry)

   658 		{

   659 		CleanupStack::PushL(sum);

   660 		sum.CleanGrowL(2*sum.Size());

   661 		CleanupStack::Pop(&sum);

   662 		sum.Ptr()[sum.Size()/2] = 1;

   663 		}

   664 	sum.SetSign(TInteger::EPositive);

   665 	return sum;

   666 	}

   667 

   668 RInteger TInteger::PositiveSubtractL(const TInteger &aA, const TInteger& aB) const

   669 	{

   670 	RInteger diff = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));

   671 	unsigned aSize = aA.WordCount();

   672 	aSize += aSize%2;

   673 	unsigned bSize = aB.WordCount();

   674 	bSize += bSize%2;

   675 	const word* const aReg = aA.Ptr();

   676 	const word* const bReg = aB.Ptr();

   677 	word* const diffReg = diff.Ptr();

   678 

   679 	if (aSize == bSize)

   680 		{

   681 		if (Compare(aReg, bReg, aSize) >= 0)

   682 			{

   683 			Subtract(diffReg, aReg, bReg, aSize);

   684 			diff.SetSign(TInteger::EPositive);

   685 			}

   686 		else

   687 			{

   688 			Subtract(diffReg, bReg, aReg, aSize);

   689 			diff.SetSign(TInteger::ENegative);

   690 			}

   691 		}

   692 	else if (aSize > bSize)

   693 		{

   694 		word borrow = Subtract(diffReg, aReg, bReg, bSize);

   695 		CopyWords(diffReg+bSize, aReg+bSize, aSize-bSize);

   696 		borrow = Decrement(diffReg+bSize, aSize-bSize, borrow);

   697 		assert(!borrow);

   698 		diff.SetSign(TInteger::EPositive);

   699 		}

   700 	else

   701 		{

   702 		word borrow = Subtract(diffReg, bReg, aReg, aSize);

   703 		CopyWords(diffReg+aSize, bReg+aSize, bSize-aSize);

   704 		borrow = Decrement(diffReg+aSize, bSize-aSize, borrow);

   705 		assert(!borrow);

   706 		diff.SetSign(TInteger::ENegative);

   707 		}

   708 	return diff;

   709 	}

   710 

   711 RInteger TInteger::PositiveMultiplyL(const TInteger &aA, const TInteger &aB) const

   712 	{

   713 	unsigned aSize = RoundupSize(aA.WordCount());

   714 	unsigned bSize = RoundupSize(aB.WordCount());

   715 

   716 	RInteger product = RInteger::NewEmptyL(aSize+bSize);

   717 	CleanupClosePushL(product);

   718 

   719 	RInteger workspace = RInteger::NewEmptyL(aSize + bSize);

   720 	AsymmetricMultiply(product.Ptr(), workspace.Ptr(), aA.Ptr(), aSize, aB.Ptr(), 

   721 		bSize);

   722 	workspace.Close();

   723 	CleanupStack::Pop(&product);

   724 	return product;

   725 	}

   726 

   727 TUint TInteger::Modulo(const TInteger& aDividend, TUint aDivisor) const

   728 	{

   729 	assert(aDivisor);

   730 	TUint i = aDividend.WordCount();

   731 	TUint remainder = 0;

   732 	while(i--)

   733 		{

   734 		remainder = TUint(MAKE_DWORD(aDividend.Ptr()[i], remainder) % aDivisor);

   735 		}

   736 	return remainder;

   737 	}

   738 

   739 void TInteger::PositiveDivideL(RInteger &aRemainder, RInteger &aQuotient,

   740 	const TInteger &aDividend, const TInteger &aDivisor) const

   741 	{

   742 	unsigned dividendSize = aDividend.WordCount();

   743 	unsigned divisorSize = aDivisor.WordCount();

   744 

   745 	if (!divisorSize)

   746 		{

   747 		User::Leave(KErrDivideByZero);

   748 		}

   749 

   750 	if (aDividend.UnsignedCompare(aDivisor) == -1)

   751 		{

   752 		aRemainder.CreateNewL(aDividend.Size());

   753 		CleanupStack::PushL(aRemainder);

   754 		aRemainder.CopyL(aDividend); //set remainder to a

   755 		aRemainder.SetSign(TInteger::EPositive);

   756 		aQuotient.CleanNewL(2); //Set quotient to zero

   757 		CleanupStack::Pop(&aRemainder);

   758 		return;

   759 		}

   760 

   761 	dividendSize += dividendSize%2;	// round up to next even number

   762 	divisorSize += divisorSize%2;

   763 

   764 	aRemainder.CleanNewL(divisorSize);

   765 	CleanupStack::PushL(aRemainder);

   766 	aQuotient.CleanNewL(dividendSize-divisorSize+2);

   767 	CleanupStack::PushL(aQuotient);

   768 

   769 	RInteger T = RInteger::NewEmptyL(dividendSize+2*divisorSize+4);

   770 	Divide(aRemainder.Ptr(), aQuotient.Ptr(), T.Ptr(), aDividend.Ptr(), 

   771 		dividendSize, aDivisor.Ptr(), divisorSize);

   772 	T.Close();

   773 	CleanupStack::Pop(2, &aRemainder); //aQuotient, aRemainder

   774 	}

   775 

   776 void TInteger::DivideL(RInteger& aRemainder, RInteger& aQuotient, 

   777 	const TInteger& aDividend, const TInteger& aDivisor) const

   778     {

   779     PositiveDivideL(aRemainder, aQuotient, aDividend, aDivisor);

   780 

   781     if (aDividend.IsNegative())

   782         {

   783         aQuotient.Negate();

   784         if (aRemainder.NotZero())

   785             {

   786             --aQuotient;

   787 			assert(aRemainder.Size() <= aDivisor.Size());

   788 			Subtract(aRemainder.Ptr(), aDivisor.Ptr(), aRemainder.Ptr(), 

   789 				aRemainder.Size());

   790             }

   791         }

   792 

   793     if (aDivisor.IsNegative())

   794         aQuotient.Negate();

   795     }

   796 

   797 void TInteger::RandomizeL(TUint aBits, TRandomAttribute aAttr)

   798 	{

   799 	if(!aBits)

   800 		{

   801 		return;

   802 		}

   803 	const TUint bytes = BitsToBytes(aBits);

   804 	const TUint words = BitsToWords(aBits);

   805 	CleanGrowL(words);

   806 	TPtr8 buf((TUint8*)(Ptr()), bytes, WordsToBytes(Size()));

   807 	TUint bitpos = aBits % BYTE_BITS;

   808 	GenerateRandomBytesL(buf);

   809 	//mask with 0 all bits above the num requested in the most significant byte

   810 	if(bitpos)

   811 		{

   812 		buf[bytes-1] = TUint8( buf[bytes-1] & ((1L << bitpos) - 1) );

   813 		}

   814 	//set most significant (top) bit 

   815 	if(aAttr == ETopBitSet || aAttr == ETop2BitsSet)

   816 		{

   817 		SetBit(aBits-1); //Set bit counts from 0

   818 		assert(BitCount() == aBits);

   819 		assert(Bit(aBits-1));

   820 		}

   821 	//set 2nd bit from top

   822 	if(aAttr == ETop2BitsSet)

   823 		{

   824 		SetBit(aBits-2); //Set bit counts from 0

   825 		assert(BitCount() == aBits);

   826 		assert(Bit(aBits-1));

   827 		assert(Bit(aBits-2));

   828 		}

   829 	}

   830 

   831 void TInteger::RandomizeL(const TInteger& aMin, const TInteger& aMax)

   832 	{

   833 	assert(aMax > aMin);

   834 	assert(aMin.NotNegative());

   835 	RInteger range = RInteger::NewL(aMax);

   836 	CleanupStack::PushL(range);

   837 	range -= aMin;

   838 	const TUint bits = range.BitCount();

   839 

   840 	//if we find a number < range then aMin+range < aMax 

   841 	do

   842 		{

   843 		RandomizeL(bits, EAllBitsRandom);

   844 		} 

   845 	while(*this > range);

   846 

   847 	*this += aMin;

   848 	CleanupStack::PopAndDestroy(&range);

   849 	}

   850 

   851 /* void PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)

   852  * and all primality related functions are implemented in primes.cpp */

   853 

   854 void TInteger::CreateNewL(TUint aNewSize)

   855 	{

   856 	//should only be called on construction

   857 	assert(!iPtr);

   858 	

   859 	TUint newSize = RoundupSize(aNewSize);

   860 	SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));

   861 	SetSize(newSize);

   862 	SetHeapBased();

   863 	}

   864 

   865 void TInteger::CleanNewL(TUint aNewSize)

   866 	{

   867 	CreateNewL(aNewSize);

   868 	Mem::FillZ(Ptr(), WordsToBytes(Size())); //clear integer storage

   869 	}

   870 

   871 void TInteger::CleanGrowL(TUint aNewSize)

   872 	{

   873 	assert(IsHeapBased());

   874 	TUint newSize = RoundupSize(aNewSize);

   875 	TUint oldSize = Size();

   876 	if(newSize > oldSize)

   877 		{

   878 		TUint* oldPtr = Ptr();

   879 		//1) allocate new memory and set ptr and size

   880 		SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));

   881 		SetSize(newSize);

   882 		//2) copy old mem to new mem

   883 		Mem::Copy(Ptr(), oldPtr, WordsToBytes(oldSize));

   884 		//3) zero all old memory

   885 		Mem::FillZ(oldPtr, WordsToBytes(oldSize));

   886 		//4) give back old memory

   887 		User::Free(oldPtr);

   888 		//5) zero new memory from end of copy to end of growth

   889 		Mem::FillZ(Ptr() + oldSize, WordsToBytes(newSize-oldSize));

   890 		}

   891 	}

   892 

   893 void TInteger::CleanResizeL(TUint aNewSize)

   894 	{

   895 	assert(IsHeapBased());

   896 	TUint newSize = RoundupSize(aNewSize);

   897 	TUint oldSize = Size();

   898 	if(newSize > oldSize)

   899 		{

   900 		CleanGrowL(aNewSize);

   901 		}

   902 	else if(newSize < oldSize)

   903 		{

   904 		TUint* oldPtr = Ptr();

   905 		//1) zero memory above newsize

   906 		Mem::FillZ(oldPtr+WordsToBytes(aNewSize),WordsToBytes(oldSize-newSize));

   907 		//2) ReAlloc cell.  Since our newsize is less than oldsize, it is

   908 		//guarenteed not to move.  Thus this is just freeing part of our old

   909 		//cell to the heap for other uses.

   910 		SetPtr((TUint*)User::ReAllocL(Ptr(), WordsToBytes(newSize)));

   911 		SetSize(newSize);

   912 		}

   913 	}

   914 

   915 EXPORT_C TInteger::TInteger() : iSize(0), iPtr(0)

   916 	{

   917 	}

   918 

   919 void TInteger::Construct(const TDesC8& aValue)

   920 	{

   921 	assert(Size() >= BytesToWords(aValue.Size()));

   922 	if(aValue.Size() > 0)

   923 		{

   924 		//People write numbers with the most significant digits first (big

   925 		//endian) but we store our numbers in little endian.  Hence we need to

   926 		//reverse the string by bytes.

   927 

   928 		TUint bytes = aValue.Size();

   929 		TUint8* i = (TUint8*)Ptr();

   930 		TUint8* j = (TUint8*)aValue.Ptr() + bytes;

   931 

   932 		//Swap the endianess of the number itself

   933 		// (msb) 01 02 03 04 05 06 (lsb) becomes ->

   934 		// (lsb) 06 05 04 03 02 01 (msb)

   935 		while( j != (TUint8*)aValue.Ptr() )

   936 			{

   937 			*i++ = *--j;

   938 			}

   939 		Mem::FillZ((TUint8*)Ptr() + bytes, WordsToBytes(Size()) - bytes);

   940 		}

   941 	else

   942 		{

   943 		//if size is zero, we zero the whole register

   944 		Mem::FillZ((TUint8*)Ptr(), WordsToBytes(Size()));

   945 		}

   946 	SetSign(EPositive);

   947 	}

   948 

   949 void TInteger::Construct(const TInteger& aInteger)

   950 	{

   951 	assert(Size() >= aInteger.Size());

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

   953 	if(Size() > aInteger.Size())

   954 		{

   955 		Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));

   956 		}

   957 	SetSign(aInteger.Sign());

   958 	}

   959 

   960 void TInteger::Construct(TInt aInteger)

   961 	{

   962 	Construct((TUint)aInteger);

   963 	if(aInteger < 0)

   964 		{

   965 		SetSign(ENegative);

   966 		Ptr()[0] = -aInteger;

   967 		}

   968 	}

   969 

   970 void TInteger::Construct(TUint aInteger)

   971 	{

   972 	assert(Size() >= 2);

   973 	SetSign(EPositive);

   974 	Ptr()[0] = aInteger;

   975 	Mem::FillZ(Ptr()+1, WordsToBytes(Size()-1));

   976 	}

   977 

   978 void TInteger::ConstructStack(TUint aWords, TUint aInteger)

   979 	{

   980 	SetPtr((TUint*)(this)+2);

   981 	//SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1

   982 	SetSize(aWords);

   983 	assert(Size() >= 2);

   984 	Ptr()[0] = aInteger;

   985 	Mem::FillZ(&(Ptr()[1]), WordsToBytes(Size()-1));

   986 	}

   987 

   988 void TInteger::ConstructStack(TUint aWords, const TInteger& aInteger)

   989 	{

   990 	SetPtr((TUint*)(this)+2);

   991 	//SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1

   992 	SetSize(aWords);

   993 	assert( Size() >= RoundupSize(aInteger.WordCount()) );

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

   995 	Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));

   996 	}

   997 

   998 // Methods are excluded from coverage due to the problem with BullsEye on ONB.

   999 // Manually verified that these methods are functionally covered.

  1000 #ifdef _BullseyeCoverage

  1001 #pragma suppress_warnings on

  1002 #pragma BullseyeCoverage off

  1003 #pragma suppress_warnings off

  1004 #endif

  1005 

  1006 EXPORT_C TInteger& TInteger::operator/=(TInt aOperand)

  1007 	{

  1008 	TStackInteger64 operand(aOperand);

  1009 	*this /= operand;

  1010 	return *this;

  1011 	}

  1012 

  1013 EXPORT_C TInteger& TInteger::operator%=(TInt aOperand)

  1014 	{

  1015 	TStackInteger64 operand(aOperand);

  1016 	assert(operand.NotNegative());

  1017 	*this %= operand;

  1018 	return *this;

  1019 	}

  1020 

  1021 EXPORT_C TInt TInteger::ConvertToLongL(void) const

  1022 	{

  1023 	if(!IsConvertableToLong())

  1024 		{

  1025 		User::Leave(KErrTotalLossOfPrecision);

  1026 		}

  1027 	return ConvertToLong();

  1028 	}

  1029 

  1030 TInt TInteger::ConvertToLong(void) const

  1031 	{

  1032 	TUint value = ConvertToUnsignedLong();

  1033 	return Sign() == EPositive ? value : -(static_cast<TInt>(value));

  1034 	}

  1035 

  1036 TBool TInteger::IsConvertableToLong(void) const

  1037 	{

  1038 	if(WordCount() > 1)

  1039 		{

  1040 		return EFalse;

  1041 		}

  1042 	TUint value = (Ptr())[0];

  1043 	if(Sign() == EPositive)

  1044 		{

  1045 		return static_cast<TInt>(value) >= 0;

  1046 		}

  1047 	else

  1048 		{

  1049 		return -(static_cast<TInt>(value)) < 0;

  1050 		}

  1051 	}

  1052 

  1053 EXPORT_C RInteger TInteger::SquaredL() const

  1054 	{

  1055 	//PositiveMultiplyL optimises for the squaring case already

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

  1057 	return PositiveMultiplyL(*this, *this);

  1058 	}

  1059 

  1060 EXPORT_C RInteger TInteger::DividedByL(TUint aOperand) const

  1061 	{

  1062 	TUint remainder;

  1063 	RInteger quotient;

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

  1065 	return quotient;

  1066 	}

  1067 

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

  1069 	{

  1070 	//See HAC 14.85

  1071 

  1072 	// 1.1 Precomputation

  1073 	// g1 <- g

  1074 	// g2 <- g^2

  1075 	RInteger g2 = SquaredL();

  1076 	CleanupStack::PushL(g2);

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

  1078 	CleanupStack::PushL(g1);

  1079 	TWindowSlider slider(aExponent);

  1080 

  1081 	// 1.2 

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

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

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

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

  1086 	CleanupStack::Pop(); //g1

  1087 	CleanupClosePushL(powerArray);

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

  1089 		{

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

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

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

  1093 		//set granularity

  1094 		powerArray.Append(g2iplus1);

  1095 		}

  1096 

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

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

  1099 	CleanupStack::PushL(A);

  1100 	TInt i = aExponent.BitCount() - 1;

  1101 

  1102 	// 3 While i>=0 do:

  1103 	while( i>=0 )

  1104 		{

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

  1106 		if(!aExponent.Bit(i))

  1107 			{

  1108 			A *= A;

  1109 			i--;

  1110 			}

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

  1112 		// and do:

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

  1114 		else

  1115 			{

  1116 			slider.FindNextWindow(i);

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

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

  1119 				{

  1120 				A *= A;

  1121 				}

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

  1123 			i -= slider.Length();

  1124 			}

  1125 		}

  1126 	CleanupStack::Pop(&A);

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

  1128 	return A;

  1129 	}

  1130 

  1131 void TInteger::DivideL(TUint& aRemainder, RInteger& aQuotient,

  1132 	const TInteger& aDividend, TUint aDivisor) const

  1133 	{

  1134 	if(!aDivisor)