--- a/crypto/weakcrypto/source/bigint/bigint.cpp Tue Aug 31 17:00:08 2010 +0300
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,1166 +0,0 @@
-/*
-* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
-* All rights reserved.
-* This component and the accompanying materials are made available
-* under the terms of the License "Eclipse Public License v1.0"
-* which accompanies this distribution, and is available
-* at the URL "http://www.eclipse.org/legal/epl-v10.html".
-*
-* Initial Contributors:
-* Nokia Corporation - initial contribution.
-*
-* Contributors:
-*
-* Description:
-*
-*/
-
-
-#include <bigint.h>
-#include <e32std.h>
-#include <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::DividedByL(TUint aOperand) const
- {
- TUint remainder;
- RInteger quotient;
- DivideL(remainder, quotient, *this, aOperand);
- 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::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::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;
- }
-
-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/=(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 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 TInt TInteger::ConvertToLongL(void) const
- {
- if(!IsConvertableToLong())
- {
- User::Leave(KErrTotalLossOfPrecision);
- }
- return ConvertToLong();
- }
-
-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::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);
- }
- }
-
-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::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();
- }
-
-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;
- }
- }
-
-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);
- }
- }
-
-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()));
- }
-