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 <bigint.h>

    20 #include <e32std.h>

    21 #include <euserext.h>

    22 #include <securityerr.h>

    23 #include "words.h"

    24 #include "algorithms.h"

    25 #include "windowslider.h"

    26 #include "stackinteger.h"

    27 #include "mont.h"

    28 

    29 /**

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

    31 * integer.

    32 *

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

    34 *

    35 * @return	The new buffer.

    36 * 

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

    38 *

    39 * @publishedPartner

    40 * @released

    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 * @publishedPartner

    89 * @released

    90 */

    91 EXPORT_C TUint TInteger::WordCount() const

    92 	{

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

    94 	}

    95 

    96 /**

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

    98 * 

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

   100 * 

   101 * @publishedPartner

   102 * @released

   103 */

   104 EXPORT_C TUint TInteger::ByteCount() const

   105 	{

   106 	TUint wordCount = WordCount();

   107 	if(wordCount)

   108 		{

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

   110 		}

   111 	else 

   112 		{

   113 		return 0;

   114 		}

   115 	}

   116 

   117 /** 

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

   119 * 

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

   121 * 

   122 * @publishedPartner

   123 * @released

   124 */

   125 EXPORT_C TUint TInteger::BitCount() const

   126 	{

   127 	TUint wordCount = WordCount();

   128 	if(wordCount)

   129 		{

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

   131 		}

   132 	else 

   133 		{

   134 		return 0;

   135 		}

   136 	}

   137 

   138 

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

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

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

   142 //modify the ROM ;)

   143 //word 0: Size of storage in words

   144 //word 1: Pointer to storage

   145 //word 2: LSW of storage

   146 //word 3: MSW of storage

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

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

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

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

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

   152 

   153 /** 

   154  * Gets the TInteger that represents zero

   155  *

   156  * @return	The TInteger representing zero

   157  */

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

   159 	{

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

   161 	}

   162 

   163 /** 

   164  * Gets the TInteger that represents one

   165  *

   166  * @return	The TInteger representing one

   167  */

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

   169 	{

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

   171 	}

   172 	

   173 /** 

   174  * Gets the TInteger that represents two

   175  *

   176  * @return	The TInteger representing two

   177  */

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

   179 	{

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

   181 	}

   182 

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

   184 	{

   185 	RInteger sum;

   186     if (NotNegative())

   187 		{

   188         if (aOperand.NotNegative())

   189             sum = PositiveAddL(*this, aOperand);

   190         else

   191             sum = PositiveSubtractL(*this, aOperand);

   192 		}

   193     else

   194 		{

   195         if (aOperand.NotNegative())

   196             sum = PositiveSubtractL(aOperand, *this);

   197         else

   198 			{

   199             sum = PositiveAddL(*this, aOperand);

   200 			sum.SetSign(TInteger::ENegative);

   201 			}

   202 		}

   203 	return sum;

   204 	}

   205 

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

   207 	{

   208 	RInteger diff;

   209     if (NotNegative())

   210 		{

   211         if (aOperand.NotNegative())

   212             diff = PositiveSubtractL(*this, aOperand);

   213         else

   214             diff = PositiveAddL(*this, aOperand);

   215 		}

   216     else

   217 		{

   218         if (aOperand.NotNegative())

   219 			{

   220             diff = PositiveAddL(*this, aOperand);

   221 			diff.SetSign(TInteger::ENegative);

   222 			}

   223         else

   224             diff = PositiveSubtractL(aOperand, *this);

   225 		}

   226 	return diff;

   227 	}

   228 

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

   230 	{

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

   232 

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

   234 		{

   235 		product.Negate();

   236 		}

   237 	return product;

   238 	}

   239 

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

   241 	{

   242 	RInteger quotient;

   243 	RInteger remainder;

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

   245 	remainder.Close();

   246 	return quotient;

   247 	}

   248 

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

   250 	{

   251 	TUint remainder;

   252 	RInteger quotient;

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

   254 	return quotient;

   255 	}

   256 

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

   258 	{

   259 	RInteger remainder;

   260 	RInteger quotient;

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

   262 	quotient.Close();

   263 	return remainder;

   264 	}

   265 

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

   267 	{

   268 	if(!aOperand)

   269 		{

   270 		User::Leave(KErrDivideByZero);

   271 		}

   272 	return Modulo(*this, aOperand);

   273 	}

   274 

   275 EXPORT_C RInteger TInteger::SquaredL() const

   276 	{

   277 	//PositiveMultiplyL optimises for the squaring case already

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

   279 	return PositiveMultiplyL(*this, *this);

   280 	}

   281 

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

   283 	{

   284 	//See HAC 14.85

   285 

   286 	// 1.1 Precomputation

   287 	// g1 <- g

   288 	// g2 <- g^2

   289 	RInteger g2 = SquaredL();

   290 	CleanupStack::PushL(g2);

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

   292 	CleanupStack::PushL(g1);

   293 	TWindowSlider slider(aExponent);

   294 

   295 	// 1.2 

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

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

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

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

   300 	CleanupStack::Pop(); //g1

   301 	CleanupClosePushL(powerArray);

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

   303 		{

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

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

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

   307 		//set granularity

   308 		powerArray.Append(g2iplus1);

   309 		}

   310 

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

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

   313 	CleanupStack::PushL(A);

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

   315 

   316 	// 3 While i>=0 do:

   317 	while( i>=0 )

   318 		{

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

   320 		if(!aExponent.Bit(i))

   321 			{

   322 			A *= A;

   323 			i--;

   324 			}

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

   326 		// and do:

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

   328 		else

   329 			{

   330 			slider.FindNextWindow(i);

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

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

   333 				{

   334 				A *= A;

   335 				}

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

   337 			i -= slider.Length();

   338 			}

   339 		}

   340 	CleanupStack::Pop(&A);

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

   342 	return A;

   343 	}

   344 

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

   346 	const TInteger& aMod) 

   347 	{

   348 	RInteger product = aA.TimesL(aB);

   349 	CleanupStack::PushL(product);

   350 	RInteger reduced = product.ModuloL(aMod);

   351 	CleanupStack::PopAndDestroy(&product); 

   352 	return reduced;

   353 	}

   354 

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

   356 	const TInteger& aExp, const TInteger& aMod) 

   357 	{

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

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

   360 	CleanupStack::PopAndDestroy(mont);

   361 	return result;

   362 	}

   363 

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

   365 	{

   366 	//Binary GCD algorithm -- see HAC 14.4.1

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

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

   369 	assert(NotNegative());

   370 	assert(aOperand.NotNegative());

   371 

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

   373 	CleanupStack::PushL(x);

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

   375 	CleanupStack::PushL(y);

   376 

   377 	// 1 Ensure x >= y

   378 	if( x < y )

   379 		{

   380 		TClassSwap(x, y);

   381 		}

   382 

   383 	TUint g = 0;

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

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

   386 		{

   387 		x >>= 1;

   388 		y >>= 1;

   389 		++g;

   390 		}

   391 	// 3 while x != 0

   392 	while( x.NotZero() )

   393 		{

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

   395 		while( x.IsEven() )

   396 			{

   397 			x >>= 1;

   398 			}

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

   400 		while( y.IsEven() )

   401 			{

   402 			y >>= 1;

   403 			}

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

   405 		RInteger t = x.MinusL(y);

   406 		t >>= 1;

   407 		t.SetSign(TInteger::EPositive);

   408 

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

   410 		if( x >= y )

   411 			{

   412 			x.Set(t);

   413 			}

   414 		else 

   415 			{

   416 			y.Set(t);

   417 			}

   418 		}

   419 	

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

   421 	//shifting)

   422 	y <<= g;

   423 	CleanupStack::Pop(&y);

   424 	CleanupStack::PopAndDestroy(&x); 

   425 	return y;

   426 	}

   427 

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

   429 	{

   430 	assert(aMod.NotNegative());

   431 

   432 	RInteger result;

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

   434 		{

   435 		RInteger temp = ModuloL(aMod);

   436 		CleanupClosePushL(temp);

   437 		result = temp.InverseModL(aMod);

   438 		CleanupStack::PopAndDestroy(&temp);

   439 		return result;

   440 		}

   441 

   442 	if(aMod.IsEven())

   443 		{

   444 		if( !aMod || IsEven() )

   445 			{

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

   447 			}

   448 		if( *this == One() )

   449 			{

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

   451 			}

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

   453 		CleanupClosePushL(u);

   454 		if(!u)

   455 			{

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

   457 			}

   458 		else 

   459 			{

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

   461 			result = MinusL(u);

   462 			CleanupClosePushL(result);

   463 			result *= aMod;

   464 			++result;

   465 			result /= *this;

   466 			CleanupStack::Pop(&result); 

   467 			}

   468 		CleanupStack::PopAndDestroy(&u);

   469 		return result;

   470 		}

   471 

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

   473 	CleanupClosePushL(result);

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

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

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

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

   478 	workspace.Close();

   479 	CleanupStack::Pop(&result);

   480 

   481 	return result;

   482 	}

   483 

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

   485 	{

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

   487     return *this;

   488 	}

   489 

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

   491 	{

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

   493     return *this;

   494 	}

   495 

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

   497 	{

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

   499 	return *this;

   500 	}

   501 

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

   503 	{

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

   505 	return *this;

   506 	}

   507 

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

   509 	{

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

   511 	return *this;

   512 	}

   513 

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

   515 	{

   516 	TStackInteger64 operand(aOperand);

   517 	*this += operand;

   518 	return *this;

   519 	}

   520 

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

   522 	{

   523 	TStackInteger64 operand(aOperand);

   524 	*this -= operand;

   525 	return *this;

   526 	}

   527 

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

   529 	{

   530 	TStackInteger64 operand(aOperand);

   531 	*this *= operand;

   532 	return *this;

   533 	}

   534 

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

   536 	{

   537 	TStackInteger64 operand(aOperand);

   538 	*this /= operand;

   539 	return *this;

   540 	}

   541 

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

   543 	{

   544 	TStackInteger64 operand(aOperand);

   545 	assert(operand.NotNegative());

   546 	*this %= operand;

   547 	return *this;

   548 	}

   549 

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

   551 	{

   552     if (IsNegative())

   553 		{

   554         if (Increment(Ptr(), Size()))

   555 			{

   556             CleanGrowL(2*Size());

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

   558 			}

   559 		}

   560     else

   561 		{

   562         if (Decrement(Ptr(), Size()))

   563 			{

   564 			this->CopyL(-1);

   565 			}

   566 		}

   567     return *this;	

   568 	}

   569 

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

   571 	{

   572 	if(NotNegative())

   573 		{

   574 		if(Increment(Ptr(), Size()))

   575 			{

   576 			CleanGrowL(2*Size());

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

   578 			}

   579 		}

   580 	else

   581 		{

   582 		DecrementNoCarry(Ptr(), Size());

   583 		if(WordCount()==0)

   584 			{

   585 			this->CopyL(Zero());

   586 			}

   587 		}

   588 	return *this;

   589 	}

   590 

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

   592 	{

   593 	const TUint wordCount = WordCount();

   594 	const TUint shiftWords = aBits / WORD_BITS;

   595 	const TUint shiftBits = aBits % WORD_BITS;

   596 

   597 	CleanGrowL(wordCount+BitsToWords(aBits));

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

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

   600 		shiftBits);

   601 	return *this;

   602 	}

   603 

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

   605 	{

   606 	const TUint wordCount = WordCount();

   607 	const TUint shiftWords = aBits / WORD_BITS;

   608 	const TUint shiftBits = aBits % WORD_BITS;

   609 

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

   611 	if(wordCount > shiftWords)

   612 		{

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

   614 		}

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

   616 		{

   617 		SetSign(EPositive);

   618 		}

   619 	return *this;

   620 	}

   621 

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

   623 	{

   624 	TUint size = WordCount();

   625 	TUint thatSize = aThat.WordCount();

   626 

   627 	if( size == thatSize )

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

   629 	else

   630 		return size > thatSize ? 1 : -1;

   631 	}

   632 

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

   634 	{

   635     if (NotNegative())

   636 		{

   637         if (aThat.NotNegative())

   638             return UnsignedCompare(aThat);

   639         else

   640             return 1;

   641 		}

   642     else

   643 		{

   644         if (aThat.NotNegative())

   645             return -1;

   646         else

   647             return -UnsignedCompare(aThat);

   648 		}

   649 	}

   650 

   651 EXPORT_C TBool TInteger::operator!() const

   652 	{

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

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

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

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

   657 	}

   658 

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

   660 	{

   661 	TStackInteger64 temp(aInteger);

   662 	return SignedCompare(temp);

   663 	}

   664 

   665 /* TBool IsPrimeL(void) const 

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

   667 

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

   669 	{

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

   671 		{

   672 		return 0;

   673 		}

   674 	else 

   675 		{

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

   677 		}

   678 	}

   679 

   680 EXPORT_C void TInteger::SetBit(TUint aBitPos) 

   681 	{

   682 	if( aBitPos/WORD_BITS < Size() )

   683 		{

   684 		ArraySetBit(Ptr(), aBitPos);

   685 		}

   686 	}

   687 

   688 EXPORT_C void TInteger::Negate() 

   689 	{

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

   691 		{

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

   693 		}

   694 	}

   695 

   696 EXPORT_C TInt TInteger::ConvertToLongL(void) const

   697 	{

   698 	if(!IsConvertableToLong())

   699 		{

   700 		User::Leave(KErrTotalLossOfPrecision);

   701 		}

   702 	return ConvertToLong();

   703 	}

   704 

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

   706 	{

   707 	if(aAllowShrink)

   708 		{

   709 		CleanResizeL(aInteger.Size());

   710 		}

   711 	else

   712 		{

   713 		CleanGrowL(aInteger.Size());

   714 		}

   715 	Construct(aInteger);

   716 	}

   717 

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

   719 	{

   720 	if(aAllowShrink)

   721 		{

   722 		CleanResizeL(2);

   723 		}

   724 	else

   725 		{

   726 		CleanGrowL(2);

   727 		}

   728 	Construct(aInteger);

   729 	}

   730 

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

   732 	{

   733 	assert(IsHeapBased());

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

   735 	User::Free(Ptr());

   736 	iPtr = aInteger.iPtr;

   737 	iSize = aInteger.iSize;

   738 	}

   739 

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

   741 	{

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

   743 	const word aSize = aA.Size();

   744 	const word bSize = aB.Size();

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

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

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

   748 

   749 	word carry;

   750 	if (aSize == bSize)

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

   752 	else if (aSize > bSize)

   753 		{

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

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

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

   757 		}

   758 	else

   759 		{

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

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

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

   763 		}

   764 

   765 	if (carry)

   766 		{

   767 		CleanupStack::PushL(sum);

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

   769 		CleanupStack::Pop(&sum);

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

   771 		}

   772 	sum.SetSign(TInteger::EPositive);

   773 	return sum;

   774 	}

   775 

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

   777 	{

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

   779 	unsigned aSize = aA.WordCount();

   780 	aSize += aSize%2;

   781 	unsigned bSize = aB.WordCount();

   782 	bSize += bSize%2;

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

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

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

   786 

   787 	if (aSize == bSize)

   788 		{

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

   790 			{

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

   792 			diff.SetSign(TInteger::EPositive);

   793 			}

   794 		else

   795 			{

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

   797 			diff.SetSign(TInteger::ENegative);

   798 			}

   799 		}

   800 	else if (aSize > bSize)

   801 		{

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

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

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

   805 		assert(!borrow);

   806 		diff.SetSign(TInteger::EPositive);

   807 		}

   808 	else

   809 		{

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

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

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

   813 		assert(!borrow);

   814 		diff.SetSign(TInteger::ENegative);

   815 		}

   816 	return diff;

   817 	}

   818 

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

   820 	{

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

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

   823 

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

   825 	CleanupClosePushL(product);

   826 

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

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

   829 		bSize);

   830 	workspace.Close();

   831 	CleanupStack::Pop(&product);

   832 	return product;

   833 	}

   834 

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

   836 	{

   837 	assert(aDivisor);

   838 	TUint i = aDividend.WordCount();

   839 	TUint remainder = 0;

   840 	while(i--)

   841 		{

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

   843 		}

   844 	return remainder;

   845 	}

   846 

   847 void TInteger::PositiveDivide(TUint& aRemainder, TInteger& aQuotient, 

   848 	const TInteger& aDividend, TUint aDivisor) const

   849 	{

   850 	assert(aDivisor);

   851 

   852 	TUint i = aDividend.WordCount();

   853 	assert(aQuotient.Size() >= RoundupSize(i));

   854 	assert(aQuotient.Sign() == TInteger::EPositive);

   855 	aRemainder = 0;

   856 	while(i--)

   857 		{

   858 		aQuotient.Ptr()[i] = 

   859 			TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) / aDivisor);

   860 		aRemainder = 

   861 			TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) % aDivisor);

   862 		}

   863 	}

   864 

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

   866 	const TInteger& aDividend, TUint aDivisor) const

   867 	{

   868 	if(!aDivisor)

   869 		{

   870 		User::Leave(KErrDivideByZero);

   871 		}

   872 	

   873 	TUint i = aDividend.WordCount();

   874 	aQuotient.CleanNewL(RoundupSize(i));

   875 	PositiveDivide(aRemainder, aQuotient, aDividend, aDivisor);

   876 

   877 	if(aDividend.NotNegative())

   878 		{

   879 		aQuotient.SetSign(TInteger::EPositive);

   880 		}

   881 	else

   882 		{

   883 		aQuotient.SetSign(TInteger::ENegative);

   884 		if(aRemainder)

   885 			{

   886 			--aQuotient;

   887 			aRemainder = aDivisor = aRemainder;

   888 			}

   889 		}

   890 	}

   891 

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

   893 	const TInteger &aDividend, const TInteger &aDivisor) const

   894 	{

   895 	unsigned dividendSize = aDividend.WordCount();

   896 	unsigned divisorSize = aDivisor.WordCount();

   897 

   898 	if (!divisorSize)

   899 		{

   900 		User::Leave(KErrDivideByZero);

   901 		}

   902 

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

   904 		{

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

   906 		CleanupStack::PushL(aRemainder);

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

   908 		aRemainder.SetSign(TInteger::EPositive);

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

   910 		CleanupStack::Pop(&aRemainder);

   911 		return;

   912 		}

   913 

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

   915 	divisorSize += divisorSize%2;

   916 

   917 	aRemainder.CleanNewL(divisorSize);

   918 	CleanupStack::PushL(aRemainder);

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

   920 	CleanupStack::PushL(aQuotient);

   921 

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

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

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

   925 	T.Close();

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

   927 	}

   928 

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

   930 	const TInteger& aDividend, const TInteger& aDivisor) const

   931     {

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

   933 

   934     if (aDividend.IsNegative())

   935         {

   936         aQuotient.Negate();

   937         if (aRemainder.NotZero())

   938             {

   939             --aQuotient;

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

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

   942 				aRemainder.Size());

   943             }

   944         }

   945 

   946     if (aDivisor.IsNegative())

   947         aQuotient.Negate();

   948     }

   949 

   950 TInt TInteger::ConvertToLong(void) const

   951 	{

   952 	TUint value = ConvertToUnsignedLong();

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

   954 	}

   955 

   956 TBool TInteger::IsConvertableToLong(void) const

   957 	{

   958 	if(WordCount() > 1)

   959 		{

   960 		return EFalse;

   961 		}

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

   963 	if(Sign() == EPositive)

   964 		{

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

   966 		}

   967 	else

   968 		{

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

   970 		}

   971 	}

   972 

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

   974 	{

   975 	if(!aBits)

   976 		{

   977 		return;

   978 		}

   979 	const TUint bytes = BitsToBytes(aBits);

   980 	const TUint words = BitsToWords(aBits);

   981 	CleanGrowL(words);

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

   983 	TUint bitpos = aBits % BYTE_BITS;

   984 	GenerateRandomBytesL(buf);

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

   986 	if(bitpos)

   987 		{

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

   989 		}

   990 	//set most significant (top) bit 

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

   992 		{

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

   994 		assert(BitCount() == aBits);

   995 		assert(Bit(aBits-1));

   996 		}

   997 	//set 2nd bit from top

   998 	if(aAttr == ETop2BitsSet)

   999 		{

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

  1001 		assert(BitCount() == aBits);

  1002 		assert(Bit(aBits-1));

  1003 		assert(Bit(aBits-2));

  1004 		}

  1005 	}

  1006 

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

  1008 	{

  1009 	assert(aMax > aMin);

  1010 	assert(aMin.NotNegative());

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

  1012 	CleanupStack::PushL(range);

  1013 	range -= aMin;

  1014 	const TUint bits = range.BitCount();

  1015 

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

  1017 	do

  1018 		{

  1019 		RandomizeL(bits, EAllBitsRandom);

  1020 		} 

  1021 	while(*this > range);

  1022 

  1023 	*this += aMin;

  1024 	CleanupStack::PopAndDestroy(&range);

  1025 	}

  1026 

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

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

  1029 

  1030 void TInteger::CreateNewL(TUint aNewSize)

  1031 	{

  1032 	//should only be called on construction

  1033 	assert(!iPtr);

  1034 	

  1035 	TUint newSize = RoundupSize(aNewSize);

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

  1037 	SetSize(newSize);

  1038 	SetHeapBased();

  1039 	}

  1040 

  1041 void TInteger::CleanNewL(TUint aNewSize)

  1042 	{

  1043 	CreateNewL(aNewSize);

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

  1045 	}

  1046 

  1047 void TInteger::CleanGrowL(TUint aNewSize)

  1048 	{

  1049 	assert(IsHeapBased());

  1050 	TUint newSize = RoundupSize(aNewSize);

  1051 	TUint oldSize = Size();

  1052 	if(newSize > oldSize)

  1053 		{

  1054 		TUint* oldPtr = Ptr();

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

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

  1057 		SetSize(newSize);

  1058 		//2) copy old mem to new mem

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

  1060 		//3) zero all old memory

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

  1062 		//4) give back old memory

  1063 		User::Free(oldPtr);

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

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

  1066 		}

  1067 	}

  1068 

  1069 void TInteger::CleanResizeL(TUint aNewSize)

  1070 	{

  1071 	assert(IsHeapBased());

  1072 	TUint newSize = RoundupSize(aNewSize);

  1073 	TUint oldSize = Size();

  1074 	if(newSize > oldSize)

  1075 		{

  1076 		CleanGrowL(aNewSize);

  1077 		}

  1078 	else if(newSize < oldSize)

  1079 		{

  1080 		TUint* oldPtr = Ptr();

  1081 		//1) zero memory above newsize

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

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

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

  1085 		//cell to the heap for other uses.

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

  1087 		SetSize(newSize);

  1088 		}

  1089 	}

  1090 

  1091 TInteger::TInteger() : iSize(0), iPtr(0)

  1092 	{

  1093 	}

  1094 

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

  1096 	{

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

  1098 	if(aValue.Size() > 0)

  1099 		{

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

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

  1102 		//reverse the string by bytes.

  1103 

  1104 		TUint bytes = aValue.Size();

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

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

  1107 

  1108 		//Swap the endianess of the number itself

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

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

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

  1112 			{

  1113 			*i++ = *--j;

  1114 			}

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

  1116 		}

  1117 	else

  1118 		{

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

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

  1121 		}

  1122 	SetSign(EPositive);

  1123 	}

  1124 

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

  1126 	{

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

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

  1129 	if(Size() > aInteger.Size())

  1130 		{

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

  1132 		}

  1133 	SetSign(aInteger.Sign());

  1134 	}

  1135