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 /**

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

    32 * integer.

    33 *

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

    35 *

    36 * @return	The new buffer.

    37 * 

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

    39 *

    40 */

    41 EXPORT_C HBufC8* TInteger::BufferLC() const

    42 	{

    43 	if(IsNegative())

    44 		{

    45 		User::Leave(KErrNegativeExportNotSupported);

    46 		}

    47 	TUint bytes = ByteCount();

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

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

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

    51 

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

    53 	// endian

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

    55 		{

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

    57 		}

    58 	return buf;

    59 	}

    60 

    61 EXPORT_C HBufC8* TInteger::BufferWithNoTruncationLC() const

    62  	{

    63  	if(IsNegative())

    64  		{

    65  		User::Leave(KErrNegativeExportNotSupported);

    66  		}

    67  	

    68  	TUint wordCount = Size();

    69  	TUint bytes = (wordCount)*WORD_SIZE;

    70      

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

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

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

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

    75  		{

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

    77  		}

    78   

    79 	return buf;

    80 	}

    81 

    82 /** 

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

    84 * 

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

    86 *

    87 */

    88 EXPORT_C TUint TInteger::WordCount() const

    89 	{

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

    91 	}

    92 

    93 /**

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

    95 * 

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

    97 * 

    98 */

    99 EXPORT_C TUint TInteger::ByteCount() const

   100 	{

   101 	TUint wordCount = WordCount();

   102 	if(wordCount)

   103 		{

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

   105 		}

   106 	else 

   107 		{

   108 		return 0;

   109 		}

   110 	}

   111 

   112 /** 

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

   114 * 

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

   116 * 

   117 */

   118 EXPORT_C TUint TInteger::BitCount() const

   119 	{

   120 	TUint wordCount = WordCount();

   121 	if(wordCount)

   122 		{

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

   124 		}

   125 	else 

   126 		{

   127 		return 0;

   128 		}

   129 	}

   130 

   131 

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

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

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

   135 //modify the ROM ;)

   136 //word 0: Size of storage in words

   137 //word 1: Pointer to storage

   138 //word 2: LSW of storage

   139 //word 3: MSW of storage

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

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

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

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

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

   145 

   146 /** 

   147  * Gets the TInteger that represents zero

   148  *

   149  * @return	The TInteger representing zero

   150  */

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

   152 	{

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

   154 	}

   155 

   156 /** 

   157  * Gets the TInteger that represents one

   158  *

   159  * @return	The TInteger representing one

   160  */

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

   162 	{

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

   164 	}

   165 	

   166 /** 

   167  * Gets the TInteger that represents two

   168  *

   169  * @return	The TInteger representing two

   170  */

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

   172 	{

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

   174 	}

   175 

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

   177 	{

   178 	RInteger sum;

   179     if (NotNegative())

   180 		{

   181         if (aOperand.NotNegative())

   182             sum = PositiveAddL(*this, aOperand);

   183         else

   184             sum = PositiveSubtractL(*this, aOperand);

   185 		}

   186     else

   187 		{

   188         if (aOperand.NotNegative())

   189             sum = PositiveSubtractL(aOperand, *this);

   190         else

   191 			{

   192             sum = PositiveAddL(*this, aOperand);

   193 			sum.SetSign(TInteger::ENegative);

   194 			}

   195 		}

   196 	return sum;

   197 	}

   198 

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

   200 	{

   201 	RInteger diff;

   202     if (NotNegative())

   203 		{

   204         if (aOperand.NotNegative())

   205             diff = PositiveSubtractL(*this, aOperand);

   206         else

   207             diff = PositiveAddL(*this, aOperand);

   208 		}

   209     else

   210 		{

   211         if (aOperand.NotNegative())

   212 			{

   213             diff = PositiveAddL(*this, aOperand);

   214 			diff.SetSign(TInteger::ENegative);

   215 			}

   216         else

   217             diff = PositiveSubtractL(aOperand, *this);

   218 		}

   219 	return diff;

   220 	}

   221 

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

   223 	{

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

   225 

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

   227 		{

   228 		product.Negate();

   229 		}

   230 	return product;

   231 	}

   232 

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

   234 	{

   235 	RInteger quotient;

   236 	RInteger remainder;

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

   238 	remainder.Close();

   239 	return quotient;

   240 	}

   241 

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

   243 	{

   244 	TUint remainder;

   245 	RInteger quotient;

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

   247 	return quotient;

   248 	}

   249 

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

   251 	{

   252 	RInteger remainder;

   253 	RInteger quotient;

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

   255 	quotient.Close();

   256 	return remainder;

   257 	}

   258 

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

   260 	{

   261 	if(!aOperand)

   262 		{

   263 		User::Leave(KErrDivideByZero);

   264 		}

   265 	return Modulo(*this, aOperand);

   266 	}

   267 

   268 EXPORT_C RInteger TInteger::SquaredL() const

   269 	{

   270 	//PositiveMultiplyL optimises for the squaring case already

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

   272 	return PositiveMultiplyL(*this, *this);

   273 	}

   274 

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

   276 	{

   277 	//See HAC 14.85

   278 

   279 	// 1.1 Precomputation

   280 	// g1 <- g

   281 	// g2 <- g^2

   282 	RInteger g2 = SquaredL();

   283 	CleanupStack::PushL(g2);

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

   285 	CleanupStack::PushL(g1);

   286 	TWindowSlider slider(aExponent);

   287 

   288 	// 1.2 

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

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

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

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

   293 	CleanupStack::Pop(); //g1

   294 	CleanupClosePushL(powerArray);

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

   296 		{

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

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

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

   300 		//set granularity

   301 		powerArray.Append(g2iplus1);

   302 		}

   303 

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

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

   306 	CleanupStack::PushL(A);

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

   308 

   309 	// 3 While i>=0 do:

   310 	while( i>=0 )

   311 		{

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

   313 		if(!aExponent.Bit(i))

   314 			{

   315 			A *= A;

   316 			i--;

   317 			}

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

   319 		// and do:

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

   321 		else

   322 			{

   323 			slider.FindNextWindow(i);

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

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

   326 				{

   327 				A *= A;

   328 				}

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

   330 			i -= slider.Length();

   331 			}

   332 		}

   333 	CleanupStack::Pop(&A);

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

   335 	return A;

   336 	}

   337 

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

   339 	const TInteger& aMod) 

   340 	{

   341 	RInteger product = aA.TimesL(aB);

   342 	CleanupStack::PushL(product);

   343 	RInteger reduced = product.ModuloL(aMod);

   344 	CleanupStack::PopAndDestroy(&product); 

   345 	return reduced;

   346 	}

   347 

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

   349 	const TInteger& aExp, const TInteger& aMod) 

   350 	{

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

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

   353 	CleanupStack::PopAndDestroy(mont);

   354 	return result;

   355 	}

   356 

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

   358 	{

   359 	//Binary GCD algorithm -- see HAC 14.4.1

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

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

   362 	assert(NotNegative());

   363 	assert(aOperand.NotNegative());

   364 

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

   366 	CleanupStack::PushL(x);

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

   368 	CleanupStack::PushL(y);

   369 

   370 	// 1 Ensure x >= y

   371 	if( x < y )

   372 		{

   373 		TClassSwap(x, y);

   374 		}

   375 

   376 	TUint g = 0;

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

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

   379 		{

   380 		x >>= 1;

   381 		y >>= 1;

   382 		++g;

   383 		}

   384 	// 3 while x != 0

   385 	while( x.NotZero() )

   386 		{

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

   388 		while( x.IsEven() )

   389 			{

   390 			x >>= 1;

   391 			}

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

   393 		while( y.IsEven() )

   394 			{

   395 			y >>= 1;

   396 			}

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

   398 		RInteger t = x.MinusL(y);

   399 		t >>= 1;

   400 		t.SetSign(TInteger::EPositive);

   401 

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

   403 		if( x >= y )

   404 			{

   405 			x.Set(t);

   406 			}

   407 		else 

   408 			{

   409 			y.Set(t);

   410 			}

   411 		}

   412 	

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

   414 	//shifting)

   415 	y <<= g;

   416 	CleanupStack::Pop(&y);

   417 	CleanupStack::PopAndDestroy(&x); 

   418 	return y;

   419 	}

   420 

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

   422 	{

   423 	assert(aMod.NotNegative());

   424 

   425 	RInteger result;

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

   427 		{

   428 		RInteger temp = ModuloL(aMod);

   429 		CleanupClosePushL(temp);

   430 		result = temp.InverseModL(aMod);

   431 		CleanupStack::PopAndDestroy(&temp);

   432 		return result;

   433 		}

   434 

   435 	if(aMod.IsEven())

   436 		{

   437 		if( !aMod || IsEven() )

   438 			{

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

   440 			}

   441 		if( *this == One() )

   442 			{

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

   444 			}

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

   446 		CleanupClosePushL(u);

   447 		if(!u)

   448 			{

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

   450 			}

   451 		else 

   452 			{

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

   454 			result = MinusL(u);

   455 			CleanupClosePushL(result);

   456 			result *= aMod;

   457 			++result;

   458 			result /= *this;

   459 			CleanupStack::Pop(&result); 

   460 			}

   461 		CleanupStack::PopAndDestroy(&u);

   462 		return result;

   463 		}

   464 

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

   466 	CleanupClosePushL(result);

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

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

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

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

   471 	workspace.Close();

   472 	CleanupStack::Pop(&result);

   473 

   474 	return result;

   475 	}

   476 

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

   478 	{

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

   480     return *this;

   481 	}

   482 

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

   484 	{

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

   486     return *this;

   487 	}

   488 

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

   490 	{

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

   492 	return *this;

   493 	}

   494 

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

   496 	{

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

   498 	return *this;

   499 	}

   500 

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

   502 	{

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

   504 	return *this;

   505 	}

   506 

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

   508 	{

   509 	TStackInteger64 operand(aOperand);

   510 	*this += operand;

   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 	assert(operand.NotNegative());

   539 	*this %= operand;

   540 	return *this;

   541 	}

   542 

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

   544 	{

   545     if (IsNegative())

   546 		{

   547         if (Increment(Ptr(), Size()))

   548 			{

   549             CleanGrowL(2*Size());

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

   551 			}

   552 		}

   553     else

   554 		{

   555         if (Decrement(Ptr(), Size()))

   556 			{

   557 			this->CopyL(-1);

   558 			}

   559 		}

   560     return *this;	

   561 	}

   562 

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

   564 	{

   565 	if(NotNegative())

   566 		{

   567 		if(Increment(Ptr(), Size()))

   568 			{

   569 			CleanGrowL(2*Size());

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

   571 			}

   572 		}

   573 	else

   574 		{

   575 		DecrementNoCarry(Ptr(), Size());

   576 		if(WordCount()==0)

   577 			{

   578 			this->CopyL(Zero());

   579 			}

   580 		}

   581 	return *this;

   582 	}

   583 

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

   585 	{

   586 	const TUint wordCount = WordCount();

   587 	const TUint shiftWords = aBits / WORD_BITS;

   588 	const TUint shiftBits = aBits % WORD_BITS;

   589 

   590 	CleanGrowL(wordCount+BitsToWords(aBits));

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

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

   593 		shiftBits);

   594 	return *this;

   595 	}

   596 

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

   598 	{

   599 	const TUint wordCount = WordCount();

   600 	const TUint shiftWords = aBits / WORD_BITS;

   601 	const TUint shiftBits = aBits % WORD_BITS;

   602 

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

   604 	if(wordCount > shiftWords)

   605 		{

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

   607 		}

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

   609 		{

   610 		SetSign(EPositive);

   611 		}

   612 	return *this;

   613 	}

   614 

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

   616 	{

   617 	TUint size = WordCount();

   618 	TUint thatSize = aThat.WordCount();

   619 

   620 	if( size == thatSize )

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

   622 	else

   623 		return size > thatSize ? 1 : -1;

   624 	}

   625 

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

   627 	{

   628     if (NotNegative())

   629 		{

   630         if (aThat.NotNegative())

   631             return UnsignedCompare(aThat);

   632         else

   633             return 1;

   634 		}

   635     else

   636 		{

   637         if (aThat.NotNegative())

   638             return -1;

   639         else

   640             return -UnsignedCompare(aThat);

   641 		}

   642 	}

   643 

   644 EXPORT_C TBool TInteger::operator!() const

   645 	{

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

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

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

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

   650 	}

   651 

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

   653 	{

   654 	TStackInteger64 temp(aInteger);

   655 	return SignedCompare(temp);

   656 	}

   657 

   658 /* TBool IsPrimeL(void) const 

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

   660 

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

   662 	{

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

   664 		{

   665 		return 0;

   666 		}

   667 	else 

   668 		{

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

   670 		}

   671 	}

   672 

   673 EXPORT_C void TInteger::SetBit(TUint aBitPos) 

   674 	{

   675 	if( aBitPos/WORD_BITS < Size() )

   676 		{

   677 		ArraySetBit(Ptr(), aBitPos);

   678 		}

   679 	}

   680 

   681 EXPORT_C void TInteger::Negate() 

   682 	{

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

   684 		{

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

   686 		}

   687 	}

   688 

   689 EXPORT_C TInt TInteger::ConvertToLongL(void) const

   690 	{

   691 	if(!IsConvertableToLong())

   692 		{

   693 		User::Leave(KErrTotalLossOfPrecision);

   694 		}

   695 	return ConvertToLong();

   696 	}

   697 

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

   699 	{

   700 	if(aAllowShrink)

   701 		{

   702 		CleanResizeL(aInteger.Size());

   703 		}

   704 	else

   705 		{

   706 		CleanGrowL(aInteger.Size());

   707 		}

   708 	Construct(aInteger);

   709 	}

   710 

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

   712 	{

   713 	if(aAllowShrink)

   714 		{

   715 		CleanResizeL(2);

   716 		}

   717 	else

   718 		{

   719 		CleanGrowL(2);

   720 		}

   721 	Construct(aInteger);

   722 	}

   723 

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

   725 	{

   726 	assert(IsHeapBased());

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

   728 	User::Free(Ptr());

   729 	iPtr = aInteger.iPtr;

   730 	iSize = aInteger.iSize;

   731 	}

   732 

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

   734 	{

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

   736 	const word aSize = aA.Size();

   737 	const word bSize = aB.Size();

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

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

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

   741 

   742 	word carry;

   743 	if (aSize == bSize)

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

   745 	else if (aSize > bSize)

   746 		{

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

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

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

   750 		}

   751 	else

   752 		{

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

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

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

   756 		}

   757 

   758 	if (carry)

   759 		{

   760 		CleanupStack::PushL(sum);

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

   762 		CleanupStack::Pop(&sum);

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

   764 		}

   765 	sum.SetSign(TInteger::EPositive);

   766 	return sum;

   767 	}

   768 

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

   770 	{

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

   772 	unsigned aSize = aA.WordCount();

   773 	aSize += aSize%2;

   774 	unsigned bSize = aB.WordCount();

   775 	bSize += bSize%2;

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

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

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

   779 

   780 	if (aSize == bSize)

   781 		{

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

   783 			{

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

   785 			diff.SetSign(TInteger::EPositive);

   786 			}

   787 		else

   788 			{

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

   790 			diff.SetSign(TInteger::ENegative);

   791 			}

   792 		}

   793 	else if (aSize > bSize)

   794 		{

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

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

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

   798 		assert(!borrow);

   799 		diff.SetSign(TInteger::EPositive);

   800 		}

   801 	else

   802 		{

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

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

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

   806 		assert(!borrow);

   807 		diff.SetSign(TInteger::ENegative);

   808 		}

   809 	return diff;

   810 	}

   811 

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

   813 	{

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

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

   816 

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

   818 	CleanupClosePushL(product);

   819 

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

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

   822 		bSize);

   823 	workspace.Close();

   824 	CleanupStack::Pop(&product);

   825 	return product;

   826 	}

   827 

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

   829 	{

   830 	assert(aDivisor);

   831 	TUint i = aDividend.WordCount();

   832 	TUint remainder = 0;

   833 	while(i--)

   834 		{

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

   836 		}

   837 	return remainder;

   838 	}

   839 

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

   841 	const TInteger& aDividend, TUint aDivisor) const

   842 	{

   843 	assert(aDivisor);

   844 

   845 	TUint i = aDividend.WordCount();

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

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

   848 	aRemainder = 0;

   849 	while(i--)

   850 		{

   851 		aQuotient.Ptr()[i] = 

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

   853 		aRemainder = 

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

   855 		}

   856 	}

   857 

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

   859 	const TInteger& aDividend, TUint aDivisor) const

   860 	{

   861 	if(!aDivisor)

   862 		{

   863 		User::Leave(KErrDivideByZero);

   864 		}

   865 	

   866 	TUint i = aDividend.WordCount();

   867 	aQuotient.CleanNewL(RoundupSize(i));

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

   869 

   870 	if(aDividend.NotNegative())

   871 		{

   872 		aQuotient.SetSign(TInteger::EPositive);

   873 		}

   874 	else

   875 		{

   876 		aQuotient.SetSign(TInteger::ENegative);

   877 		if(aRemainder)

   878 			{

   879 			--aQuotient;

   880 			aRemainder = aDivisor = aRemainder;

   881 			}

   882 		}

   883 	}

   884 

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

   886 	const TInteger &aDividend, const TInteger &aDivisor) const

   887 	{

   888 	unsigned dividendSize = aDividend.WordCount();

   889 	unsigned divisorSize = aDivisor.WordCount();

   890 

   891 	if (!divisorSize)

   892 		{

   893 		User::Leave(KErrDivideByZero);

   894 		}

   895 

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

   897 		{

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

   899 		CleanupStack::PushL(aRemainder);

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

   901 		aRemainder.SetSign(TInteger::EPositive);

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

   903 		CleanupStack::Pop(&aRemainder);

   904 		return;

   905 		}

   906 

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

   908 	divisorSize += divisorSize%2;

   909 

   910 	aRemainder.CleanNewL(divisorSize);

   911 	CleanupStack::PushL(aRemainder);

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

   913 	CleanupStack::PushL(aQuotient);

   914 

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

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

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

   918 	T.Close();

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

   920 	}

   921 

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

   923 	const TInteger& aDividend, const TInteger& aDivisor) const

   924     {

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

   926 

   927     if (aDividend.IsNegative())

   928         {

   929         aQuotient.Negate();

   930         if (aRemainder.NotZero())

   931             {

   932             --aQuotient;

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

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

   935 				aRemainder.Size());

   936             }

   937         }

   938 

   939     if (aDivisor.IsNegative())

   940         aQuotient.Negate();

   941     }

   942 

   943 TInt TInteger::ConvertToLong(void) const

   944 	{

   945 	TUint value = ConvertToUnsignedLong();

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

   947 	}

   948 

   949 TBool TInteger::IsConvertableToLong(void) const

   950 	{

   951 	if(WordCount() > 1)

   952 		{

   953 		return EFalse;

   954 		}

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

   956 	if(Sign() == EPositive)

   957 		{

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

   959 		}

   960 	else

   961 		{

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

   963 		}

   964 	}

   965 

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

   967 	{

   968 	if(!aBits)

   969 		{

   970 		return;

   971 		}

   972 	const TUint bytes = BitsToBytes(aBits);

   973 	const TUint words = BitsToWords(aBits);

   974 	CleanGrowL(words);

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

   976 	TUint bitpos = aBits % BYTE_BITS;

   977 	GenerateRandomBytesL(buf);

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

   979 	if(bitpos)

   980 		{

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

   982 		}

   983 	//set most significant (top) bit 

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

   985 		{

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

   987 		assert(BitCount() == aBits);

   988 		assert(Bit(aBits-1));

   989 		}

   990 	//set 2nd bit from top

   991 	if(aAttr == ETop2BitsSet)

   992 		{

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

   994 		assert(BitCount() == aBits);

   995 		assert(Bit(aBits-1));

   996 		assert(Bit(aBits-2));

   997 		}

   998 	}

   999 

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

  1001 	{

  1002 	assert(aMax > aMin);

  1003 	assert(aMin.NotNegative());

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

  1005 	CleanupStack::PushL(range);

  1006 	range -= aMin;

  1007 	const TUint bits = range.BitCount();

  1008 

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

  1010 	do

  1011 		{

  1012 		RandomizeL(bits, EAllBitsRandom);

  1013 		} 

  1014 	while(*this > range);

  1015 

  1016 	*this += aMin;

  1017 	CleanupStack::PopAndDestroy(&range);

  1018 	}

  1019 

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

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

  1022 

  1023 void TInteger::CreateNewL(TUint aNewSize)

  1024 	{

  1025 	//should only be called on construction

  1026 	assert(!iPtr);

  1027 	

  1028 	TUint newSize = RoundupSize(aNewSize);

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

  1030 	SetSize(newSize);

  1031 	SetHeapBased();

  1032 	}

  1033 

  1034 void TInteger::CleanNewL(TUint aNewSize)

  1035 	{

  1036 	CreateNewL(aNewSize);

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

  1038 	}

  1039 

  1040 void TInteger::CleanGrowL(TUint aNewSize)

  1041 	{

  1042 	assert(IsHeapBased());

  1043 	TUint newSize = RoundupSize(aNewSize);

  1044 	TUint oldSize = Size();

  1045 	if(newSize > oldSize)

  1046 		{

  1047 		TUint* oldPtr = Ptr();

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

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

  1050 		SetSize(newSize);

  1051 		//2) copy old mem to new mem

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

  1053 		//3) zero all old memory

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

  1055 		//4) give back old memory

  1056 		User::Free(oldPtr);

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

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

  1059 		}

  1060 	}

  1061 

  1062 void TInteger::CleanResizeL(TUint aNewSize)

  1063 	{

  1064 	assert(IsHeapBased());

  1065 	TUint newSize = RoundupSize(aNewSize);

  1066 	TUint oldSize = Size();

  1067 	if(newSize > oldSize)

  1068 		{

  1069 		CleanGrowL(aNewSize);

  1070 		}

  1071 	else if(newSize < oldSize)

  1072 		{

  1073 		TUint* oldPtr = Ptr();

  1074 		//1) zero memory above newsize

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

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

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

  1078 		//cell to the heap for other uses.

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

  1080 		SetSize(newSize);

  1081 		}

  1082 	}

  1083 

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

  1085 	{

  1086 	}

  1087 

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

  1089 	{

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

  1091 	if(aValue.Size() > 0)

  1092 		{

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

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

  1095 		//reverse the string by bytes.

  1096 

  1097 		TUint bytes = aValue.Size();

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

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

  1100 

  1101 		//Swap the endianess of the number itself

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

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

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

  1105 			{

  1106 			*i++ = *--j;

  1107 			}

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

  1109 		}

  1110 	else

  1111 		{

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

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

  1114 		}

  1115 	SetSign(EPositive);

  1116 	}

  1117 

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

  1119 	{

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

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

  1122 	if(Size() > aInteger.Size())

  1123 		{

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

  1125 		}

  1126 	SetSign(aInteger.Sign());

  1127 	}

  1128 

  1129 void TInteger::Construct(TInt aInteger)

  1130 	{

  1131 	Construct((TUint)aInteger);

  1132 	if(aInteger < 0)

  1133 		{

  1134 		SetSign(ENegative);

  1135 		Ptr()[0] = -aInteger;