--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/crypto/weakcryptospi/source/bigint/bigint.cpp Fri Nov 06 13:21:00 2009 +0200
@@ -0,0 +1,1174 @@
+/*
+* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
+* All rights reserved.
+* This component and the accompanying materials are made available
+* under the terms of the License "Eclipse Public License v1.0"
+* which accompanies this distribution, and is available
+* at the URL "http://www.eclipse.org/legal/epl-v10.html".
+*
+* Initial Contributors:
+* Nokia Corporation - initial contribution.
+*
+* Contributors:
+*
+* Description:
+*
+*/
+
+
+#include <random.h>
+#include <bigint.h>
+#include <e32std.h>
+#include <euserext.h>
+#include <securityerr.h>
+#include "words.h"
+#include "algorithms.h"
+#include "windowslider.h"
+#include "stackinteger.h"
+#include "mont.h"
+
+
+/**
+* Creates a new buffer containing the big-endian binary representation of this
+* integer.
+*
+* Note that it does not support the exporting of negative integers.
+*
+* @return The new buffer.
+*
+* @leave KErrNegativeExportNotSupported If this instance is a negative integer.
+*
+*/
+EXPORT_C HBufC8* TInteger::BufferLC() const
+ {
+ if(IsNegative())
+ {
+ User::Leave(KErrNegativeExportNotSupported);
+ }
+ TUint bytes = ByteCount();
+ HBufC8* buf = HBufC8::NewMaxLC(bytes);
+ TUint8* bufPtr = (TUint8*)(buf->Ptr());
+ TUint8* regPtr = (TUint8*)Ptr();
+
+ // we internally store the number little endian, as a string we want it big
+ // endian
+ for(TUint i=0,j=bytes-1; i<bytes; )
+ {
+ bufPtr[i++] = regPtr[j--];
+ }
+ return buf;
+ }
+
+EXPORT_C HBufC8* TInteger::BufferWithNoTruncationLC() const
+ {
+ if(IsNegative())
+ {
+ User::Leave(KErrNegativeExportNotSupported);
+ }
+
+ TUint wordCount = Size();
+ TUint bytes = (wordCount)*WORD_SIZE;
+
+ HBufC8* buf = HBufC8::NewMaxLC(bytes);
+ TUint8* bufPtr = (TUint8*)(buf->Ptr());
+ TUint8* regPtr = (TUint8*)Ptr();
+ for(TUint i=0,j=bytes-1; i<bytes; )
+ {
+ bufPtr[i++] = regPtr[j--];
+ }
+
+ return buf;
+ }
+
+/**
+* Gets the number of words required to represent this RInteger.
+*
+* @return The size of the integer in words.
+*
+*/
+EXPORT_C TUint TInteger::WordCount() const
+ {
+ return CountWords(Ptr(), Size());
+ }
+
+/**
+* Gets the number of bytes required to represent this RInteger.
+*
+* @return The size of the integer in bytes.
+*
+*/
+EXPORT_C TUint TInteger::ByteCount() const
+ {
+ TUint wordCount = WordCount();
+ if(wordCount)
+ {
+ return (wordCount-1)*WORD_SIZE + BytePrecision((Ptr())[wordCount-1]);
+ }
+ else
+ {
+ return 0;
+ }
+ }
+
+/**
+* Get the number of bits required to represent this RInteger.
+*
+* @return The size of the integer in bits.
+*
+*/
+EXPORT_C TUint TInteger::BitCount() const
+ {
+ TUint wordCount = WordCount();
+ if(wordCount)
+ {
+ return (wordCount-1)*WORD_BITS + BitPrecision(Ptr()[wordCount-1]);
+ }
+ else
+ {
+ return 0;
+ }
+ }
+
+
+//These 3 declarations instantiate a constant 0, 1, 2 for ease of use and
+//quick construction elsewhere in the code. Note that the functions
+//returning references to this static data return const references as you can't
+//modify the ROM ;)
+//word 0: Size of storage in words
+//word 1: Pointer to storage
+//word 2: LSW of storage
+//word 3: MSW of storage
+//Note that the flag bits in word 1 (Ptr()) are zero in the case of a positive
+//stack based integer (SignBit == 0, IsHeapBasedBit == 0)
+const TUint KBigintZero[4] = {2, (TUint)(KBigintZero+2), 0, 0};
+const TUint KBigintOne[4] = {2, (TUint)(KBigintOne+2), 1, 0};
+const TUint KBigintTwo[4] = {2, (TUint)(KBigintTwo+2), 2, 0};
+
+/**
+ * Gets the TInteger that represents zero
+ *
+ * @return The TInteger representing zero
+ */
+EXPORT_C const TInteger& TInteger::Zero(void)
+ {
+ return *reinterpret_cast<const TStackInteger64*>(KBigintZero);
+ }
+
+/**
+ * Gets the TInteger that represents one
+ *
+ * @return The TInteger representing one
+ */
+EXPORT_C const TInteger& TInteger::One(void)
+ {
+ return *reinterpret_cast<const TStackInteger64*>(KBigintOne);
+ }
+
+/**
+ * Gets the TInteger that represents two
+ *
+ * @return The TInteger representing two
+ */
+EXPORT_C const TInteger& TInteger::Two(void)
+ {
+ return *reinterpret_cast<const TStackInteger64*>(KBigintTwo);
+ }
+
+EXPORT_C RInteger TInteger::PlusL(const TInteger& aOperand) const
+ {
+ RInteger sum;
+ if (NotNegative())
+ {
+ if (aOperand.NotNegative())
+ sum = PositiveAddL(*this, aOperand);
+ else
+ sum = PositiveSubtractL(*this, aOperand);
+ }
+ else
+ {
+ if (aOperand.NotNegative())
+ sum = PositiveSubtractL(aOperand, *this);
+ else
+ {
+ sum = PositiveAddL(*this, aOperand);
+ sum.SetSign(TInteger::ENegative);
+ }
+ }
+ return sum;
+ }
+
+EXPORT_C RInteger TInteger::MinusL(const TInteger& aOperand) const
+ {
+ RInteger diff;
+ if (NotNegative())
+ {
+ if (aOperand.NotNegative())
+ diff = PositiveSubtractL(*this, aOperand);
+ else
+ diff = PositiveAddL(*this, aOperand);
+ }
+ else
+ {
+ if (aOperand.NotNegative())
+ {
+ diff = PositiveAddL(*this, aOperand);
+ diff.SetSign(TInteger::ENegative);
+ }
+ else
+ diff = PositiveSubtractL(aOperand, *this);
+ }
+ return diff;
+ }
+
+EXPORT_C RInteger TInteger::TimesL(const TInteger& aOperand) const
+ {
+ RInteger product = PositiveMultiplyL(*this, aOperand);
+
+ if (NotNegative() != aOperand.NotNegative())
+ {
+ product.Negate();
+ }
+ return product;
+ }
+
+EXPORT_C RInteger TInteger::DividedByL(const TInteger& aOperand) const
+ {
+ RInteger quotient;
+ RInteger remainder;
+ DivideL(remainder, quotient, *this, aOperand);
+ remainder.Close();
+ return quotient;
+ }
+
+EXPORT_C RInteger TInteger::ModuloL(const TInteger& aOperand) const
+ {
+ RInteger remainder;
+ RInteger quotient;
+ DivideL(remainder, quotient, *this, aOperand);
+ quotient.Close();
+ return remainder;
+ }
+
+EXPORT_C TUint TInteger::ModuloL(TUint aOperand) const
+ {
+ if(!aOperand)
+ {
+ User::Leave(KErrDivideByZero);
+ }
+ return Modulo(*this, aOperand);
+ }
+
+EXPORT_C RInteger TInteger::ModularMultiplyL(const TInteger& aA, const TInteger& aB,
+ const TInteger& aMod)
+ {
+ RInteger product = aA.TimesL(aB);
+ CleanupStack::PushL(product);
+ RInteger reduced = product.ModuloL(aMod);
+ CleanupStack::PopAndDestroy(&product);
+ return reduced;
+ }
+
+EXPORT_C RInteger TInteger::ModularExponentiateL(const TInteger& aBase,
+ const TInteger& aExp, const TInteger& aMod)
+ {
+ CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aMod);
+ RInteger result = RInteger::NewL(mont->ExponentiateL(aBase, aExp));
+ CleanupStack::PopAndDestroy(mont);
+ return result;
+ }
+
+EXPORT_C RInteger TInteger::GCDL(const TInteger& aOperand) const
+ {
+ //Binary GCD algorithm -- see HAC 14.4.1
+ //with a slight variation -- our g counts shifts rather than actually
+ //shifting. We then do one shift at the end.
+ assert(NotNegative());
+ assert(aOperand.NotNegative());
+
+ RInteger x = RInteger::NewL(*this);
+ CleanupStack::PushL(x);
+ RInteger y = RInteger::NewL(aOperand);
+ CleanupStack::PushL(y);
+
+ // 1 Ensure x >= y
+ if( x < y )
+ {
+ TClassSwap(x, y);
+ }
+
+ TUint g = 0;
+ // 2 while x and y even x <- x/2, y <- y/2
+ while( x.IsEven() && y.IsEven() )
+ {
+ x >>= 1;
+ y >>= 1;
+ ++g;
+ }
+ // 3 while x != 0
+ while( x.NotZero() )
+ {
+ // 3.1 while x even x <- x/2
+ while( x.IsEven() )
+ {
+ x >>= 1;
+ }
+ // 3.2 while y even y <- y/2
+ while( y.IsEven() )
+ {
+ y >>= 1;
+ }
+ // 3.3 t <- abs(x-y)/2
+ RInteger t = x.MinusL(y);
+ t >>= 1;
+ t.SetSign(TInteger::EPositive);
+
+ // 3.4 If x>=y then x <- t else y <- t
+ if( x >= y )
+ {
+ x.Set(t);
+ }
+ else
+ {
+ y.Set(t);
+ }
+ }
+
+ // 4 Return (g*y) (equiv to y<<=g as our g was counting shifts not actually
+ //shifting)
+ y <<= g;
+ CleanupStack::Pop(&y);
+ CleanupStack::PopAndDestroy(&x);
+ return y;
+ }
+
+EXPORT_C RInteger TInteger::InverseModL(const TInteger& aMod) const
+ {
+ assert(aMod.NotNegative());
+
+ RInteger result;
+ if(IsNegative() || *this>=aMod)
+ {
+ RInteger temp = ModuloL(aMod);
+ CleanupClosePushL(temp);
+ result = temp.InverseModL(aMod);
+ CleanupStack::PopAndDestroy(&temp);
+ return result;
+ }
+
+ if(aMod.IsEven())
+ {
+ if( !aMod || IsEven() )
+ {
+ return RInteger::NewL(Zero());
+ }
+ if( *this == One() )
+ {
+ return RInteger::NewL(One());
+ }
+ RInteger u = aMod.InverseModL(*this);
+ CleanupClosePushL(u);
+ if(!u)
+ {
+ result = RInteger::NewL(Zero());
+ }
+ else
+ {
+ //calculates (aMod*(*this-u)+1)/(*this)
+ result = MinusL(u);
+ CleanupClosePushL(result);
+ result *= aMod;
+ ++result;
+ result /= *this;
+ CleanupStack::Pop(&result);
+ }
+ CleanupStack::PopAndDestroy(&u);
+ return result;
+ }
+
+ result = RInteger::NewEmptyL(aMod.Size());
+ CleanupClosePushL(result);
+ RInteger workspace = RInteger::NewEmptyL(aMod.Size() * 4);
+ TUint k = AlmostInverse(result.Ptr(), workspace.Ptr(), Ptr(), Size(),
+ aMod.Ptr(), aMod.Size());
+ DivideByPower2Mod(result.Ptr(), result.Ptr(), k, aMod.Ptr(), aMod.Size());
+ workspace.Close();
+ CleanupStack::Pop(&result);
+
+ return result;
+ }
+
+EXPORT_C TInteger& TInteger::operator+=(const TInteger& aOperand)
+ {
+ this->Set(PlusL(aOperand));
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator-=(const TInteger& aOperand)
+ {
+ this->Set(MinusL(aOperand));
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator*=(const TInteger& aOperand)
+ {
+ this->Set(TimesL(aOperand));
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator/=(const TInteger& aOperand)
+ {
+ this->Set(DividedByL(aOperand));
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator%=(const TInteger& aOperand)
+ {
+ this->Set(ModuloL(aOperand));
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator+=(TInt aOperand)
+ {
+ TStackInteger64 operand(aOperand);
+ *this += operand;
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator-=(TInt aOperand)
+ {
+ TStackInteger64 operand(aOperand);
+ *this -= operand;
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator*=(TInt aOperand)
+ {
+ TStackInteger64 operand(aOperand);
+ *this *= operand;
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator--()
+ {
+ if (IsNegative())
+ {
+ if (Increment(Ptr(), Size()))
+ {
+ CleanGrowL(2*Size());
+ (Ptr())[Size()/2]=1;
+ }
+ }
+ else
+ {
+ if (Decrement(Ptr(), Size()))
+ {
+ this->CopyL(-1);
+ }
+ }
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator++()
+ {
+ if(NotNegative())
+ {
+ if(Increment(Ptr(), Size()))
+ {
+ CleanGrowL(2*Size());
+ (Ptr())[Size()/2]=1;
+ }
+ }
+ else
+ {
+ DecrementNoCarry(Ptr(), Size());
+ if(WordCount()==0)
+ {
+ this->CopyL(Zero());
+ }
+ }
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator <<=(TUint aBits)
+ {
+ const TUint wordCount = WordCount();
+ const TUint shiftWords = aBits / WORD_BITS;
+ const TUint shiftBits = aBits % WORD_BITS;
+
+ CleanGrowL(wordCount+BitsToWords(aBits));
+ ShiftWordsLeftByWords(Ptr(), wordCount + shiftWords, shiftWords);
+ ShiftWordsLeftByBits(Ptr()+shiftWords, wordCount + BitsToWords(shiftBits),
+ shiftBits);
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator >>=(TUint aBits)
+ {
+ const TUint wordCount = WordCount();
+ const TUint shiftWords = aBits / WORD_BITS;
+ const TUint shiftBits = aBits % WORD_BITS;
+
+ ShiftWordsRightByWords(Ptr(), wordCount, shiftWords);
+ if(wordCount > shiftWords)
+ {
+ ShiftWordsRightByBits(Ptr(), wordCount - shiftWords, shiftBits);
+ }
+ if(IsNegative() && WordCount()==0) // avoid negative 0
+ {
+ SetSign(EPositive);
+ }
+ return *this;
+ }
+
+EXPORT_C TInt TInteger::UnsignedCompare(const TInteger& aThat) const
+ {
+ TUint size = WordCount();
+ TUint thatSize = aThat.WordCount();
+
+ if( size == thatSize )
+ return Compare(Ptr(), aThat.Ptr(), size);
+ else
+ return size > thatSize ? 1 : -1;
+ }
+
+EXPORT_C TInt TInteger::SignedCompare(const TInteger& aThat) const
+ {
+ if (NotNegative())
+ {
+ if (aThat.NotNegative())
+ return UnsignedCompare(aThat);
+ else
+ return 1;
+ }
+ else
+ {
+ if (aThat.NotNegative())
+ return -1;
+ else
+ return -UnsignedCompare(aThat);
+ }
+ }
+
+EXPORT_C TBool TInteger::operator!() const
+ {
+ //Ptr()[0] is just a quick way of weeding out non-zero numbers without
+ //doing a full WordCount() == 0. Very good odds that a non-zero number
+ //will have a bit set in the least significant word
+ return IsNegative() ? EFalse : (Ptr()[0]==0 && WordCount()==0);
+ }
+
+EXPORT_C TInt TInteger::SignedCompare(TInt aInteger) const
+ {
+ TStackInteger64 temp(aInteger);
+ return SignedCompare(temp);
+ }
+
+/* TBool IsPrimeL(void) const
+ * and all primality related functions are implemented in primes.cpp */
+
+EXPORT_C TBool TInteger::Bit(TUint aBitPos) const
+ {
+ if( aBitPos/WORD_BITS >= Size() )
+ {
+ return 0;
+ }
+ else
+ {
+ return (((Ptr())[aBitPos/WORD_BITS] >> (aBitPos % WORD_BITS)) & 1);
+ }
+ }
+
+EXPORT_C void TInteger::SetBit(TUint aBitPos)
+ {
+ if( aBitPos/WORD_BITS < Size() )
+ {
+ ArraySetBit(Ptr(), aBitPos);
+ }
+ }
+
+EXPORT_C void TInteger::Negate()
+ {
+ if(!!(*this)) //don't flip sign if *this==0
+ {
+ SetSign(TSign((~Sign())&KSignMask));
+ }
+ }
+
+EXPORT_C void TInteger::CopyL(const TInteger& aInteger, TBool aAllowShrink)
+ {
+ if(aAllowShrink)
+ {
+ CleanResizeL(aInteger.Size());
+ }
+ else
+ {
+ CleanGrowL(aInteger.Size());
+ }
+ Construct(aInteger);
+ }
+
+EXPORT_C void TInteger::CopyL(TInt aInteger, TBool aAllowShrink)
+ {
+ if(aAllowShrink)
+ {
+ CleanResizeL(2);
+ }
+ else
+ {
+ CleanGrowL(2);
+ }
+ Construct(aInteger);
+ }
+
+EXPORT_C void TInteger::Set(const RInteger& aInteger)
+ {
+ assert(IsHeapBased());
+ Mem::FillZ(Ptr(), WordsToBytes(Size()));
+ User::Free(Ptr());
+ iPtr = aInteger.iPtr;
+ iSize = aInteger.iSize;
+ }
+
+RInteger TInteger::PositiveAddL(const TInteger &aA, const TInteger& aB) const
+ {
+ RInteger sum = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));
+ const word aSize = aA.Size();
+ const word bSize = aB.Size();
+ const word* const aReg = aA.Ptr();
+ const word* const bReg = aB.Ptr();
+ word* const sumReg = sum.Ptr();
+
+ word carry;
+ if (aSize == bSize)
+ carry = Add(sumReg, aReg, bReg, aSize);
+ else if (aSize > bSize)
+ {
+ carry = Add(sumReg, aReg, bReg, bSize);
+ CopyWords(sumReg+bSize, aReg+bSize, aSize-bSize);
+ carry = Increment(sumReg+bSize, aSize-bSize, carry);
+ }
+ else
+ {
+ carry = Add(sumReg, aReg, bReg, aSize);
+ CopyWords(sumReg+aSize, bReg+aSize, bSize-aSize);
+ carry = Increment(sumReg+aSize, bSize-aSize, carry);
+ }
+
+ if (carry)
+ {
+ CleanupStack::PushL(sum);
+ sum.CleanGrowL(2*sum.Size());
+ CleanupStack::Pop(&sum);
+ sum.Ptr()[sum.Size()/2] = 1;
+ }
+ sum.SetSign(TInteger::EPositive);
+ return sum;
+ }
+
+RInteger TInteger::PositiveSubtractL(const TInteger &aA, const TInteger& aB) const
+ {
+ RInteger diff = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));
+ unsigned aSize = aA.WordCount();
+ aSize += aSize%2;
+ unsigned bSize = aB.WordCount();
+ bSize += bSize%2;
+ const word* const aReg = aA.Ptr();
+ const word* const bReg = aB.Ptr();
+ word* const diffReg = diff.Ptr();
+
+ if (aSize == bSize)
+ {
+ if (Compare(aReg, bReg, aSize) >= 0)
+ {
+ Subtract(diffReg, aReg, bReg, aSize);
+ diff.SetSign(TInteger::EPositive);
+ }
+ else
+ {
+ Subtract(diffReg, bReg, aReg, aSize);
+ diff.SetSign(TInteger::ENegative);
+ }
+ }
+ else if (aSize > bSize)
+ {
+ word borrow = Subtract(diffReg, aReg, bReg, bSize);
+ CopyWords(diffReg+bSize, aReg+bSize, aSize-bSize);
+ borrow = Decrement(diffReg+bSize, aSize-bSize, borrow);
+ assert(!borrow);
+ diff.SetSign(TInteger::EPositive);
+ }
+ else
+ {
+ word borrow = Subtract(diffReg, bReg, aReg, aSize);
+ CopyWords(diffReg+aSize, bReg+aSize, bSize-aSize);
+ borrow = Decrement(diffReg+aSize, bSize-aSize, borrow);
+ assert(!borrow);
+ diff.SetSign(TInteger::ENegative);
+ }
+ return diff;
+ }
+
+RInteger TInteger::PositiveMultiplyL(const TInteger &aA, const TInteger &aB) const
+ {
+ unsigned aSize = RoundupSize(aA.WordCount());
+ unsigned bSize = RoundupSize(aB.WordCount());
+
+ RInteger product = RInteger::NewEmptyL(aSize+bSize);
+ CleanupClosePushL(product);
+
+ RInteger workspace = RInteger::NewEmptyL(aSize + bSize);
+ AsymmetricMultiply(product.Ptr(), workspace.Ptr(), aA.Ptr(), aSize, aB.Ptr(),
+ bSize);
+ workspace.Close();
+ CleanupStack::Pop(&product);
+ return product;
+ }
+
+TUint TInteger::Modulo(const TInteger& aDividend, TUint aDivisor) const
+ {
+ assert(aDivisor);
+ TUint i = aDividend.WordCount();
+ TUint remainder = 0;
+ while(i--)
+ {
+ remainder = TUint(MAKE_DWORD(aDividend.Ptr()[i], remainder) % aDivisor);
+ }
+ return remainder;
+ }
+
+void TInteger::PositiveDivideL(RInteger &aRemainder, RInteger &aQuotient,
+ const TInteger &aDividend, const TInteger &aDivisor) const
+ {
+ unsigned dividendSize = aDividend.WordCount();
+ unsigned divisorSize = aDivisor.WordCount();
+
+ if (!divisorSize)
+ {
+ User::Leave(KErrDivideByZero);
+ }
+
+ if (aDividend.UnsignedCompare(aDivisor) == -1)
+ {
+ aRemainder.CreateNewL(aDividend.Size());
+ CleanupStack::PushL(aRemainder);
+ aRemainder.CopyL(aDividend); //set remainder to a
+ aRemainder.SetSign(TInteger::EPositive);
+ aQuotient.CleanNewL(2); //Set quotient to zero
+ CleanupStack::Pop(&aRemainder);
+ return;
+ }
+
+ dividendSize += dividendSize%2; // round up to next even number
+ divisorSize += divisorSize%2;
+
+ aRemainder.CleanNewL(divisorSize);
+ CleanupStack::PushL(aRemainder);
+ aQuotient.CleanNewL(dividendSize-divisorSize+2);
+ CleanupStack::PushL(aQuotient);
+
+ RInteger T = RInteger::NewEmptyL(dividendSize+2*divisorSize+4);
+ Divide(aRemainder.Ptr(), aQuotient.Ptr(), T.Ptr(), aDividend.Ptr(),
+ dividendSize, aDivisor.Ptr(), divisorSize);
+ T.Close();
+ CleanupStack::Pop(2, &aRemainder); //aQuotient, aRemainder
+ }
+
+void TInteger::DivideL(RInteger& aRemainder, RInteger& aQuotient,
+ const TInteger& aDividend, const TInteger& aDivisor) const
+ {
+ PositiveDivideL(aRemainder, aQuotient, aDividend, aDivisor);
+
+ if (aDividend.IsNegative())
+ {
+ aQuotient.Negate();
+ if (aRemainder.NotZero())
+ {
+ --aQuotient;
+ assert(aRemainder.Size() <= aDivisor.Size());
+ Subtract(aRemainder.Ptr(), aDivisor.Ptr(), aRemainder.Ptr(),
+ aRemainder.Size());
+ }
+ }
+
+ if (aDivisor.IsNegative())
+ aQuotient.Negate();
+ }
+
+void TInteger::RandomizeL(TUint aBits, TRandomAttribute aAttr)
+ {
+ if(!aBits)
+ {
+ return;
+ }
+ const TUint bytes = BitsToBytes(aBits);
+ const TUint words = BitsToWords(aBits);
+ CleanGrowL(words);
+ TPtr8 buf((TUint8*)(Ptr()), bytes, WordsToBytes(Size()));
+ TUint bitpos = aBits % BYTE_BITS;
+ GenerateRandomBytesL(buf);
+ //mask with 0 all bits above the num requested in the most significant byte
+ if(bitpos)
+ {
+ buf[bytes-1] = TUint8( buf[bytes-1] & ((1L << bitpos) - 1) );
+ }
+ //set most significant (top) bit
+ if(aAttr == ETopBitSet || aAttr == ETop2BitsSet)
+ {
+ SetBit(aBits-1); //Set bit counts from 0
+ assert(BitCount() == aBits);
+ assert(Bit(aBits-1));
+ }
+ //set 2nd bit from top
+ if(aAttr == ETop2BitsSet)
+ {
+ SetBit(aBits-2); //Set bit counts from 0
+ assert(BitCount() == aBits);
+ assert(Bit(aBits-1));
+ assert(Bit(aBits-2));
+ }
+ }
+
+void TInteger::RandomizeL(const TInteger& aMin, const TInteger& aMax)
+ {
+ assert(aMax > aMin);
+ assert(aMin.NotNegative());
+ RInteger range = RInteger::NewL(aMax);
+ CleanupStack::PushL(range);
+ range -= aMin;
+ const TUint bits = range.BitCount();
+
+ //if we find a number < range then aMin+range < aMax
+ do
+ {
+ RandomizeL(bits, EAllBitsRandom);
+ }
+ while(*this > range);
+
+ *this += aMin;
+ CleanupStack::PopAndDestroy(&range);
+ }
+
+/* void PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)
+ * and all primality related functions are implemented in primes.cpp */
+
+void TInteger::CreateNewL(TUint aNewSize)
+ {
+ //should only be called on construction
+ assert(!iPtr);
+
+ TUint newSize = RoundupSize(aNewSize);
+ SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));
+ SetSize(newSize);
+ SetHeapBased();
+ }
+
+void TInteger::CleanNewL(TUint aNewSize)
+ {
+ CreateNewL(aNewSize);
+ Mem::FillZ(Ptr(), WordsToBytes(Size())); //clear integer storage
+ }
+
+void TInteger::CleanGrowL(TUint aNewSize)
+ {
+ assert(IsHeapBased());
+ TUint newSize = RoundupSize(aNewSize);
+ TUint oldSize = Size();
+ if(newSize > oldSize)
+ {
+ TUint* oldPtr = Ptr();
+ //1) allocate new memory and set ptr and size
+ SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));
+ SetSize(newSize);
+ //2) copy old mem to new mem
+ Mem::Copy(Ptr(), oldPtr, WordsToBytes(oldSize));
+ //3) zero all old memory
+ Mem::FillZ(oldPtr, WordsToBytes(oldSize));
+ //4) give back old memory
+ User::Free(oldPtr);
+ //5) zero new memory from end of copy to end of growth
+ Mem::FillZ(Ptr() + oldSize, WordsToBytes(newSize-oldSize));
+ }
+ }
+
+void TInteger::CleanResizeL(TUint aNewSize)
+ {
+ assert(IsHeapBased());
+ TUint newSize = RoundupSize(aNewSize);
+ TUint oldSize = Size();
+ if(newSize > oldSize)
+ {
+ CleanGrowL(aNewSize);
+ }
+ else if(newSize < oldSize)
+ {
+ TUint* oldPtr = Ptr();
+ //1) zero memory above newsize
+ Mem::FillZ(oldPtr+WordsToBytes(aNewSize),WordsToBytes(oldSize-newSize));
+ //2) ReAlloc cell. Since our newsize is less than oldsize, it is
+ //guarenteed not to move. Thus this is just freeing part of our old
+ //cell to the heap for other uses.
+ SetPtr((TUint*)User::ReAllocL(Ptr(), WordsToBytes(newSize)));
+ SetSize(newSize);
+ }
+ }
+
+EXPORT_C TInteger::TInteger() : iSize(0), iPtr(0)
+ {
+ }
+
+void TInteger::Construct(const TDesC8& aValue)
+ {
+ assert(Size() >= BytesToWords(aValue.Size()));
+ if(aValue.Size() > 0)
+ {
+ //People write numbers with the most significant digits first (big
+ //endian) but we store our numbers in little endian. Hence we need to
+ //reverse the string by bytes.
+
+ TUint bytes = aValue.Size();
+ TUint8* i = (TUint8*)Ptr();
+ TUint8* j = (TUint8*)aValue.Ptr() + bytes;
+
+ //Swap the endianess of the number itself
+ // (msb) 01 02 03 04 05 06 (lsb) becomes ->
+ // (lsb) 06 05 04 03 02 01 (msb)
+ while( j != (TUint8*)aValue.Ptr() )
+ {
+ *i++ = *--j;
+ }
+ Mem::FillZ((TUint8*)Ptr() + bytes, WordsToBytes(Size()) - bytes);
+ }
+ else
+ {
+ //if size is zero, we zero the whole register
+ Mem::FillZ((TUint8*)Ptr(), WordsToBytes(Size()));
+ }
+ SetSign(EPositive);
+ }
+
+void TInteger::Construct(const TInteger& aInteger)
+ {
+ assert(Size() >= aInteger.Size());
+ CopyWords(Ptr(), aInteger.Ptr(), aInteger.Size());
+ if(Size() > aInteger.Size())
+ {
+ Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));
+ }
+ SetSign(aInteger.Sign());
+ }
+
+void TInteger::Construct(TInt aInteger)
+ {
+ Construct((TUint)aInteger);
+ if(aInteger < 0)
+ {
+ SetSign(ENegative);
+ Ptr()[0] = -aInteger;
+ }
+ }
+
+void TInteger::Construct(TUint aInteger)
+ {
+ assert(Size() >= 2);
+ SetSign(EPositive);
+ Ptr()[0] = aInteger;
+ Mem::FillZ(Ptr()+1, WordsToBytes(Size()-1));
+ }
+
+void TInteger::ConstructStack(TUint aWords, TUint aInteger)
+ {
+ SetPtr((TUint*)(this)+2);
+ //SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1
+ SetSize(aWords);
+ assert(Size() >= 2);
+ Ptr()[0] = aInteger;
+ Mem::FillZ(&(Ptr()[1]), WordsToBytes(Size()-1));
+ }
+
+void TInteger::ConstructStack(TUint aWords, const TInteger& aInteger)
+ {
+ SetPtr((TUint*)(this)+2);
+ //SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1
+ SetSize(aWords);
+ assert( Size() >= RoundupSize(aInteger.WordCount()) );
+ CopyWords(Ptr(), aInteger.Ptr(), aInteger.Size());
+ Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));
+ }
+
+// Methods are excluded from coverage due to the problem with BullsEye on ONB.
+// Manually verified that these methods are functionally covered.
+#ifdef _BullseyeCoverage
+#pragma suppress_warnings on
+#pragma BullseyeCoverage off
+#pragma suppress_warnings off
+#endif
+
+EXPORT_C TInteger& TInteger::operator/=(TInt aOperand)
+ {
+ TStackInteger64 operand(aOperand);
+ *this /= operand;
+ return *this;
+ }
+
+EXPORT_C TInteger& TInteger::operator%=(TInt aOperand)
+ {
+ TStackInteger64 operand(aOperand);
+ assert(operand.NotNegative());
+ *this %= operand;
+ return *this;
+ }
+
+EXPORT_C TInt TInteger::ConvertToLongL(void) const
+ {
+ if(!IsConvertableToLong())
+ {
+ User::Leave(KErrTotalLossOfPrecision);
+ }
+ return ConvertToLong();
+ }
+
+TInt TInteger::ConvertToLong(void) const
+ {
+ TUint value = ConvertToUnsignedLong();
+ return Sign() == EPositive ? value : -(static_cast<TInt>(value));
+ }
+
+TBool TInteger::IsConvertableToLong(void) const
+ {
+ if(WordCount() > 1)
+ {
+ return EFalse;
+ }
+ TUint value = (Ptr())[0];
+ if(Sign() == EPositive)
+ {
+ return static_cast<TInt>(value) >= 0;
+ }
+ else
+ {
+ return -(static_cast<TInt>(value)) < 0;
+ }
+ }
+
+EXPORT_C RInteger TInteger::SquaredL() const
+ {
+ //PositiveMultiplyL optimises for the squaring case already
+ //Any number squared is positive, no need for negative handling in TimesL
+ return PositiveMultiplyL(*this, *this);
+ }
+
+EXPORT_C RInteger TInteger::DividedByL(TUint aOperand) const
+ {
+ TUint remainder;
+ RInteger quotient;
+ DivideL(remainder, quotient, *this, aOperand);
+ return quotient;
+ }
+
+EXPORT_C RInteger TInteger::ExponentiateL(const TInteger& aExponent) const
+ {
+ //See HAC 14.85
+
+ // 1.1 Precomputation
+ // g1 <- g
+ // g2 <- g^2
+ RInteger g2 = SquaredL();
+ CleanupStack::PushL(g2);
+ RInteger g1 = RInteger::NewL(*this);
+ CleanupStack::PushL(g1);
+ TWindowSlider slider(aExponent);
+
+ // 1.2
+ // For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2
+ TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1
+ RRArray<RInteger> powerArray(count+1); //+1 because we append g1
+ User::LeaveIfError(powerArray.Append(g1));
+ CleanupStack::Pop(); //g1
+ CleanupClosePushL(powerArray);
+ for(TUint k=1; k <= count; k++)
+ {
+ RInteger g2iplus1 = g2.TimesL(powerArray[k-1]);
+ //This append can't fail as the granularity is set high enough
+ //plus we've already called Append once which will alloc to the
+ //set granularity
+ powerArray.Append(g2iplus1);
+ }
+
+ // 2 A <- 1, i <- t
+ RInteger A = RInteger::NewL(One());
+ CleanupStack::PushL(A);
+ TInt i = aExponent.BitCount() - 1;
+
+ // 3 While i>=0 do:
+ while( i>=0 )
+ {
+ // 3.1 If ei == 0 then A <- A^2
+ if(!aExponent.Bit(i))
+ {
+ A *= A;
+ i--;
+ }
+ // 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1
+ // and do:
+ // A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value]
+ else
+ {
+ slider.FindNextWindow(i);
+ assert(slider.Length() >= 1);
+ for(TUint j=0; j<slider.Length(); j++)
+ {
+ A *= A;
+ }
+ A *= powerArray[slider.Value()>>1];
+ i -= slider.Length();
+ }
+ }
+ CleanupStack::Pop(&A);
+ CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2
+ return A;
+ }
+
+void TInteger::DivideL(TUint& aRemainder, RInteger& aQuotient,
+ const TInteger& aDividend, TUint aDivisor) const
+ {
+ if(!aDivisor)
+ {
+ User::Leave(KErrDivideByZero);
+ }
+
+ TUint i = aDividend.WordCount();
+ aQuotient.CleanNewL(RoundupSize(i));
+ PositiveDivide(aRemainder, aQuotient, aDividend, aDivisor);
+
+ if(aDividend.NotNegative())
+ {
+ aQuotient.SetSign(TInteger::EPositive);
+ }
+ else
+ {
+ aQuotient.SetSign(TInteger::ENegative);
+ if(aRemainder)
+ {
+ --aQuotient;
+ aRemainder = aDivisor = aRemainder;
+ }
+ }
+ }
+
+void TInteger::PositiveDivide(TUint& aRemainder, TInteger& aQuotient,
+ const TInteger& aDividend, TUint aDivisor) const
+ {
+ assert(aDivisor);
+
+ TUint i = aDividend.WordCount();
+ assert(aQuotient.Size() >= RoundupSize(i));
+ assert(aQuotient.Sign() == TInteger::EPositive);
+ aRemainder = 0;
+ while(i--)
+ {
+ aQuotient.Ptr()[i] =
+ TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) / aDivisor);
+ aRemainder =
+ TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) % aDivisor);
+ }
+ }