1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/security/crypto/weakcrypto/source/bigint/bigint.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,1166 @@
1.4 +/*
1.5 +* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
1.6 +* All rights reserved.
1.7 +* This component and the accompanying materials are made available
1.8 +* under the terms of the License "Eclipse Public License v1.0"
1.9 +* which accompanies this distribution, and is available
1.10 +* at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.11 +*
1.12 +* Initial Contributors:
1.13 +* Nokia Corporation - initial contribution.
1.14 +*
1.15 +* Contributors:
1.16 +*
1.17 +* Description:
1.18 +*
1.19 +*/
1.20 +
1.21 +
1.22 +#include <bigint.h>
1.23 +#include <e32std.h>
1.24 +#include <euserext.h>
1.25 +#include <securityerr.h>
1.26 +#include "words.h"
1.27 +#include "algorithms.h"
1.28 +#include "windowslider.h"
1.29 +#include "stackinteger.h"
1.30 +#include "mont.h"
1.31 +
1.32 +
1.33 +/**
1.34 +* Creates a new buffer containing the big-endian binary representation of this
1.35 +* integer.
1.36 +*
1.37 +* Note that it does not support the exporting of negative integers.
1.38 +*
1.39 +* @return The new buffer.
1.40 +*
1.41 +* @leave KErrNegativeExportNotSupported If this instance is a negative integer.
1.42 +*
1.43 +*/
1.44 +EXPORT_C HBufC8* TInteger::BufferLC() const
1.45 + {
1.46 + if(IsNegative())
1.47 + {
1.48 + User::Leave(KErrNegativeExportNotSupported);
1.49 + }
1.50 + TUint bytes = ByteCount();
1.51 + HBufC8* buf = HBufC8::NewMaxLC(bytes);
1.52 + TUint8* bufPtr = (TUint8*)(buf->Ptr());
1.53 + TUint8* regPtr = (TUint8*)Ptr();
1.54 +
1.55 + // we internally store the number little endian, as a string we want it big
1.56 + // endian
1.57 + for(TUint i=0,j=bytes-1; i<bytes; )
1.58 + {
1.59 + bufPtr[i++] = regPtr[j--];
1.60 + }
1.61 + return buf;
1.62 + }
1.63 +
1.64 +EXPORT_C HBufC8* TInteger::BufferWithNoTruncationLC() const
1.65 + {
1.66 + if(IsNegative())
1.67 + {
1.68 + User::Leave(KErrNegativeExportNotSupported);
1.69 + }
1.70 +
1.71 + TUint wordCount = Size();
1.72 + TUint bytes = (wordCount)*WORD_SIZE;
1.73 +
1.74 + HBufC8* buf = HBufC8::NewMaxLC(bytes);
1.75 + TUint8* bufPtr = (TUint8*)(buf->Ptr());
1.76 + TUint8* regPtr = (TUint8*)Ptr();
1.77 + for(TUint i=0,j=bytes-1; i<bytes; )
1.78 + {
1.79 + bufPtr[i++] = regPtr[j--];
1.80 + }
1.81 +
1.82 + return buf;
1.83 + }
1.84 +
1.85 +/**
1.86 +* Gets the number of words required to represent this RInteger.
1.87 +*
1.88 +* @return The size of the integer in words.
1.89 +*
1.90 +*/
1.91 +EXPORT_C TUint TInteger::WordCount() const
1.92 + {
1.93 + return CountWords(Ptr(), Size());
1.94 + }
1.95 +
1.96 +/**
1.97 +* Gets the number of bytes required to represent this RInteger.
1.98 +*
1.99 +* @return The size of the integer in bytes.
1.100 +*
1.101 +*/
1.102 +EXPORT_C TUint TInteger::ByteCount() const
1.103 + {
1.104 + TUint wordCount = WordCount();
1.105 + if(wordCount)
1.106 + {
1.107 + return (wordCount-1)*WORD_SIZE + BytePrecision((Ptr())[wordCount-1]);
1.108 + }
1.109 + else
1.110 + {
1.111 + return 0;
1.112 + }
1.113 + }
1.114 +
1.115 +/**
1.116 +* Get the number of bits required to represent this RInteger.
1.117 +*
1.118 +* @return The size of the integer in bits.
1.119 +*
1.120 +*/
1.121 +EXPORT_C TUint TInteger::BitCount() const
1.122 + {
1.123 + TUint wordCount = WordCount();
1.124 + if(wordCount)
1.125 + {
1.126 + return (wordCount-1)*WORD_BITS + BitPrecision(Ptr()[wordCount-1]);
1.127 + }
1.128 + else
1.129 + {
1.130 + return 0;
1.131 + }
1.132 + }
1.133 +
1.134 +
1.135 +//These 3 declarations instantiate a constant 0, 1, 2 for ease of use and
1.136 +//quick construction elsewhere in the code. Note that the functions
1.137 +//returning references to this static data return const references as you can't
1.138 +//modify the ROM ;)
1.139 +//word 0: Size of storage in words
1.140 +//word 1: Pointer to storage
1.141 +//word 2: LSW of storage
1.142 +//word 3: MSW of storage
1.143 +//Note that the flag bits in word 1 (Ptr()) are zero in the case of a positive
1.144 +//stack based integer (SignBit == 0, IsHeapBasedBit == 0)
1.145 +const TUint KBigintZero[4] = {2, (TUint)(KBigintZero+2), 0, 0};
1.146 +const TUint KBigintOne[4] = {2, (TUint)(KBigintOne+2), 1, 0};
1.147 +const TUint KBigintTwo[4] = {2, (TUint)(KBigintTwo+2), 2, 0};
1.148 +
1.149 +/**
1.150 + * Gets the TInteger that represents zero
1.151 + *
1.152 + * @return The TInteger representing zero
1.153 + */
1.154 +EXPORT_C const TInteger& TInteger::Zero(void)
1.155 + {
1.156 + return *reinterpret_cast<const TStackInteger64*>(KBigintZero);
1.157 + }
1.158 +
1.159 +/**
1.160 + * Gets the TInteger that represents one
1.161 + *
1.162 + * @return The TInteger representing one
1.163 + */
1.164 +EXPORT_C const TInteger& TInteger::One(void)
1.165 + {
1.166 + return *reinterpret_cast<const TStackInteger64*>(KBigintOne);
1.167 + }
1.168 +
1.169 +/**
1.170 + * Gets the TInteger that represents two
1.171 + *
1.172 + * @return The TInteger representing two
1.173 + */
1.174 +EXPORT_C const TInteger& TInteger::Two(void)
1.175 + {
1.176 + return *reinterpret_cast<const TStackInteger64*>(KBigintTwo);
1.177 + }
1.178 +
1.179 +EXPORT_C RInteger TInteger::PlusL(const TInteger& aOperand) const
1.180 + {
1.181 + RInteger sum;
1.182 + if (NotNegative())
1.183 + {
1.184 + if (aOperand.NotNegative())
1.185 + sum = PositiveAddL(*this, aOperand);
1.186 + else
1.187 + sum = PositiveSubtractL(*this, aOperand);
1.188 + }
1.189 + else
1.190 + {
1.191 + if (aOperand.NotNegative())
1.192 + sum = PositiveSubtractL(aOperand, *this);
1.193 + else
1.194 + {
1.195 + sum = PositiveAddL(*this, aOperand);
1.196 + sum.SetSign(TInteger::ENegative);
1.197 + }
1.198 + }
1.199 + return sum;
1.200 + }
1.201 +
1.202 +EXPORT_C RInteger TInteger::MinusL(const TInteger& aOperand) const
1.203 + {
1.204 + RInteger diff;
1.205 + if (NotNegative())
1.206 + {
1.207 + if (aOperand.NotNegative())
1.208 + diff = PositiveSubtractL(*this, aOperand);
1.209 + else
1.210 + diff = PositiveAddL(*this, aOperand);
1.211 + }
1.212 + else
1.213 + {
1.214 + if (aOperand.NotNegative())
1.215 + {
1.216 + diff = PositiveAddL(*this, aOperand);
1.217 + diff.SetSign(TInteger::ENegative);
1.218 + }
1.219 + else
1.220 + diff = PositiveSubtractL(aOperand, *this);
1.221 + }
1.222 + return diff;
1.223 + }
1.224 +
1.225 +EXPORT_C RInteger TInteger::TimesL(const TInteger& aOperand) const
1.226 + {
1.227 + RInteger product = PositiveMultiplyL(*this, aOperand);
1.228 +
1.229 + if (NotNegative() != aOperand.NotNegative())
1.230 + {
1.231 + product.Negate();
1.232 + }
1.233 + return product;
1.234 + }
1.235 +
1.236 +EXPORT_C RInteger TInteger::DividedByL(const TInteger& aOperand) const
1.237 + {
1.238 + RInteger quotient;
1.239 + RInteger remainder;
1.240 + DivideL(remainder, quotient, *this, aOperand);
1.241 + remainder.Close();
1.242 + return quotient;
1.243 + }
1.244 +
1.245 +EXPORT_C RInteger TInteger::DividedByL(TUint aOperand) const
1.246 + {
1.247 + TUint remainder;
1.248 + RInteger quotient;
1.249 + DivideL(remainder, quotient, *this, aOperand);
1.250 + return quotient;
1.251 + }
1.252 +
1.253 +EXPORT_C RInteger TInteger::ModuloL(const TInteger& aOperand) const
1.254 + {
1.255 + RInteger remainder;
1.256 + RInteger quotient;
1.257 + DivideL(remainder, quotient, *this, aOperand);
1.258 + quotient.Close();
1.259 + return remainder;
1.260 + }
1.261 +
1.262 +EXPORT_C TUint TInteger::ModuloL(TUint aOperand) const
1.263 + {
1.264 + if(!aOperand)
1.265 + {
1.266 + User::Leave(KErrDivideByZero);
1.267 + }
1.268 + return Modulo(*this, aOperand);
1.269 + }
1.270 +
1.271 +EXPORT_C RInteger TInteger::SquaredL() const
1.272 + {
1.273 + //PositiveMultiplyL optimises for the squaring case already
1.274 + //Any number squared is positive, no need for negative handling in TimesL
1.275 + return PositiveMultiplyL(*this, *this);
1.276 + }
1.277 +
1.278 +EXPORT_C RInteger TInteger::ExponentiateL(const TInteger& aExponent) const
1.279 + {
1.280 + //See HAC 14.85
1.281 +
1.282 + // 1.1 Precomputation
1.283 + // g1 <- g
1.284 + // g2 <- g^2
1.285 + RInteger g2 = SquaredL();
1.286 + CleanupStack::PushL(g2);
1.287 + RInteger g1 = RInteger::NewL(*this);
1.288 + CleanupStack::PushL(g1);
1.289 + TWindowSlider slider(aExponent);
1.290 +
1.291 + // 1.2
1.292 + // For i from 1 to (2^(k-1) -1) do g2i+1 <- g2i-1 * g2
1.293 + TUint count = (1 << (slider.WindowSize()-1)) - 1; //2^(k-1) -1
1.294 + RRArray<RInteger> powerArray(count+1); //+1 because we append g1
1.295 + User::LeaveIfError(powerArray.Append(g1));
1.296 + CleanupStack::Pop(); //g1
1.297 + CleanupClosePushL(powerArray);
1.298 + for(TUint k=1; k <= count; k++)
1.299 + {
1.300 + RInteger g2iplus1 = g2.TimesL(powerArray[k-1]);
1.301 + //This append can't fail as the granularity is set high enough
1.302 + //plus we've already called Append once which will alloc to the
1.303 + //set granularity
1.304 + powerArray.Append(g2iplus1);
1.305 + }
1.306 +
1.307 + // 2 A <- 1, i <- t
1.308 + RInteger A = RInteger::NewL(One());
1.309 + CleanupStack::PushL(A);
1.310 + TInt i = aExponent.BitCount() - 1;
1.311 +
1.312 + // 3 While i>=0 do:
1.313 + while( i>=0 )
1.314 + {
1.315 + // 3.1 If ei == 0 then A <- A^2
1.316 + if(!aExponent.Bit(i))
1.317 + {
1.318 + A *= A;
1.319 + i--;
1.320 + }
1.321 + // 3.2 Find longest bitstring ei,ei-1,...,el s.t. i-l+1<=k and el==1
1.322 + // and do:
1.323 + // A <- (A^2^(i-l+1)) * g[the index indicated by the bitstring value]
1.324 + else
1.325 + {
1.326 + slider.FindNextWindow(i);
1.327 + assert(slider.Length() >= 1);
1.328 + for(TUint j=0; j<slider.Length(); j++)
1.329 + {
1.330 + A *= A;
1.331 + }
1.332 + A *= powerArray[slider.Value()>>1];
1.333 + i -= slider.Length();
1.334 + }
1.335 + }
1.336 + CleanupStack::Pop(&A);
1.337 + CleanupStack::PopAndDestroy(2, &g2); //powerArray, g2
1.338 + return A;
1.339 + }
1.340 +
1.341 +EXPORT_C RInteger TInteger::ModularMultiplyL(const TInteger& aA, const TInteger& aB,
1.342 + const TInteger& aMod)
1.343 + {
1.344 + RInteger product = aA.TimesL(aB);
1.345 + CleanupStack::PushL(product);
1.346 + RInteger reduced = product.ModuloL(aMod);
1.347 + CleanupStack::PopAndDestroy(&product);
1.348 + return reduced;
1.349 + }
1.350 +
1.351 +EXPORT_C RInteger TInteger::ModularExponentiateL(const TInteger& aBase,
1.352 + const TInteger& aExp, const TInteger& aMod)
1.353 + {
1.354 + CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aMod);
1.355 + RInteger result = RInteger::NewL(mont->ExponentiateL(aBase, aExp));
1.356 + CleanupStack::PopAndDestroy(mont);
1.357 + return result;
1.358 + }
1.359 +
1.360 +EXPORT_C RInteger TInteger::GCDL(const TInteger& aOperand) const
1.361 + {
1.362 + //Binary GCD algorithm -- see HAC 14.4.1
1.363 + //with a slight variation -- our g counts shifts rather than actually
1.364 + //shifting. We then do one shift at the end.
1.365 + assert(NotNegative());
1.366 + assert(aOperand.NotNegative());
1.367 +
1.368 + RInteger x = RInteger::NewL(*this);
1.369 + CleanupStack::PushL(x);
1.370 + RInteger y = RInteger::NewL(aOperand);
1.371 + CleanupStack::PushL(y);
1.372 +
1.373 + // 1 Ensure x >= y
1.374 + if( x < y )
1.375 + {
1.376 + TClassSwap(x, y);
1.377 + }
1.378 +
1.379 + TUint g = 0;
1.380 + // 2 while x and y even x <- x/2, y <- y/2
1.381 + while( x.IsEven() && y.IsEven() )
1.382 + {
1.383 + x >>= 1;
1.384 + y >>= 1;
1.385 + ++g;
1.386 + }
1.387 + // 3 while x != 0
1.388 + while( x.NotZero() )
1.389 + {
1.390 + // 3.1 while x even x <- x/2
1.391 + while( x.IsEven() )
1.392 + {
1.393 + x >>= 1;
1.394 + }
1.395 + // 3.2 while y even y <- y/2
1.396 + while( y.IsEven() )
1.397 + {
1.398 + y >>= 1;
1.399 + }
1.400 + // 3.3 t <- abs(x-y)/2
1.401 + RInteger t = x.MinusL(y);
1.402 + t >>= 1;
1.403 + t.SetSign(TInteger::EPositive);
1.404 +
1.405 + // 3.4 If x>=y then x <- t else y <- t
1.406 + if( x >= y )
1.407 + {
1.408 + x.Set(t);
1.409 + }
1.410 + else
1.411 + {
1.412 + y.Set(t);
1.413 + }
1.414 + }
1.415 +
1.416 + // 4 Return (g*y) (equiv to y<<=g as our g was counting shifts not actually
1.417 + //shifting)
1.418 + y <<= g;
1.419 + CleanupStack::Pop(&y);
1.420 + CleanupStack::PopAndDestroy(&x);
1.421 + return y;
1.422 + }
1.423 +
1.424 +EXPORT_C RInteger TInteger::InverseModL(const TInteger& aMod) const
1.425 + {
1.426 + assert(aMod.NotNegative());
1.427 +
1.428 + RInteger result;
1.429 + if(IsNegative() || *this>=aMod)
1.430 + {
1.431 + RInteger temp = ModuloL(aMod);
1.432 + CleanupClosePushL(temp);
1.433 + result = temp.InverseModL(aMod);
1.434 + CleanupStack::PopAndDestroy(&temp);
1.435 + return result;
1.436 + }
1.437 +
1.438 + if(aMod.IsEven())
1.439 + {
1.440 + if( !aMod || IsEven() )
1.441 + {
1.442 + return RInteger::NewL(Zero());
1.443 + }
1.444 + if( *this == One() )
1.445 + {
1.446 + return RInteger::NewL(One());
1.447 + }
1.448 + RInteger u = aMod.InverseModL(*this);
1.449 + CleanupClosePushL(u);
1.450 + if(!u)
1.451 + {
1.452 + result = RInteger::NewL(Zero());
1.453 + }
1.454 + else
1.455 + {
1.456 + //calculates (aMod*(*this-u)+1)/(*this)
1.457 + result = MinusL(u);
1.458 + CleanupClosePushL(result);
1.459 + result *= aMod;
1.460 + ++result;
1.461 + result /= *this;
1.462 + CleanupStack::Pop(&result);
1.463 + }
1.464 + CleanupStack::PopAndDestroy(&u);
1.465 + return result;
1.466 + }
1.467 +
1.468 + result = RInteger::NewEmptyL(aMod.Size());
1.469 + CleanupClosePushL(result);
1.470 + RInteger workspace = RInteger::NewEmptyL(aMod.Size() * 4);
1.471 + TUint k = AlmostInverse(result.Ptr(), workspace.Ptr(), Ptr(), Size(),
1.472 + aMod.Ptr(), aMod.Size());
1.473 + DivideByPower2Mod(result.Ptr(), result.Ptr(), k, aMod.Ptr(), aMod.Size());
1.474 + workspace.Close();
1.475 + CleanupStack::Pop(&result);
1.476 +
1.477 + return result;
1.478 + }
1.479 +
1.480 +EXPORT_C TInteger& TInteger::operator+=(const TInteger& aOperand)
1.481 + {
1.482 + this->Set(PlusL(aOperand));
1.483 + return *this;
1.484 + }
1.485 +
1.486 +EXPORT_C TInteger& TInteger::operator-=(const TInteger& aOperand)
1.487 + {
1.488 + this->Set(MinusL(aOperand));
1.489 + return *this;
1.490 + }
1.491 +
1.492 +EXPORT_C TInteger& TInteger::operator*=(const TInteger& aOperand)
1.493 + {
1.494 + this->Set(TimesL(aOperand));
1.495 + return *this;
1.496 + }
1.497 +
1.498 +EXPORT_C TInteger& TInteger::operator/=(const TInteger& aOperand)
1.499 + {
1.500 + this->Set(DividedByL(aOperand));
1.501 + return *this;
1.502 + }
1.503 +
1.504 +EXPORT_C TInteger& TInteger::operator%=(const TInteger& aOperand)
1.505 + {
1.506 + this->Set(ModuloL(aOperand));
1.507 + return *this;
1.508 + }
1.509 +
1.510 +EXPORT_C TInteger& TInteger::operator+=(TInt aOperand)
1.511 + {
1.512 + TStackInteger64 operand(aOperand);
1.513 + *this += operand;
1.514 + return *this;
1.515 + }
1.516 +
1.517 +EXPORT_C TInteger& TInteger::operator-=(TInt aOperand)
1.518 + {
1.519 + TStackInteger64 operand(aOperand);
1.520 + *this -= operand;
1.521 + return *this;
1.522 + }
1.523 +
1.524 +EXPORT_C TInteger& TInteger::operator*=(TInt aOperand)
1.525 + {
1.526 + TStackInteger64 operand(aOperand);
1.527 + *this *= operand;
1.528 + return *this;
1.529 + }
1.530 +
1.531 +EXPORT_C TInteger& TInteger::operator/=(TInt aOperand)
1.532 + {
1.533 + TStackInteger64 operand(aOperand);
1.534 + *this /= operand;
1.535 + return *this;
1.536 + }
1.537 +
1.538 +EXPORT_C TInteger& TInteger::operator%=(TInt aOperand)
1.539 + {
1.540 + TStackInteger64 operand(aOperand);
1.541 + assert(operand.NotNegative());
1.542 + *this %= operand;
1.543 + return *this;
1.544 + }
1.545 +
1.546 +EXPORT_C TInteger& TInteger::operator--()
1.547 + {
1.548 + if (IsNegative())
1.549 + {
1.550 + if (Increment(Ptr(), Size()))
1.551 + {
1.552 + CleanGrowL(2*Size());
1.553 + (Ptr())[Size()/2]=1;
1.554 + }
1.555 + }
1.556 + else
1.557 + {
1.558 + if (Decrement(Ptr(), Size()))
1.559 + {
1.560 + this->CopyL(-1);
1.561 + }
1.562 + }
1.563 + return *this;
1.564 + }
1.565 +
1.566 +EXPORT_C TInteger& TInteger::operator++()
1.567 + {
1.568 + if(NotNegative())
1.569 + {
1.570 + if(Increment(Ptr(), Size()))
1.571 + {
1.572 + CleanGrowL(2*Size());
1.573 + (Ptr())[Size()/2]=1;
1.574 + }
1.575 + }
1.576 + else
1.577 + {
1.578 + DecrementNoCarry(Ptr(), Size());
1.579 + if(WordCount()==0)
1.580 + {
1.581 + this->CopyL(Zero());
1.582 + }
1.583 + }
1.584 + return *this;
1.585 + }
1.586 +
1.587 +EXPORT_C TInteger& TInteger::operator <<=(TUint aBits)
1.588 + {
1.589 + const TUint wordCount = WordCount();
1.590 + const TUint shiftWords = aBits / WORD_BITS;
1.591 + const TUint shiftBits = aBits % WORD_BITS;
1.592 +
1.593 + CleanGrowL(wordCount+BitsToWords(aBits));
1.594 + ShiftWordsLeftByWords(Ptr(), wordCount + shiftWords, shiftWords);
1.595 + ShiftWordsLeftByBits(Ptr()+shiftWords, wordCount + BitsToWords(shiftBits),
1.596 + shiftBits);
1.597 + return *this;
1.598 + }
1.599 +
1.600 +EXPORT_C TInteger& TInteger::operator >>=(TUint aBits)
1.601 + {
1.602 + const TUint wordCount = WordCount();
1.603 + const TUint shiftWords = aBits / WORD_BITS;
1.604 + const TUint shiftBits = aBits % WORD_BITS;
1.605 +
1.606 + ShiftWordsRightByWords(Ptr(), wordCount, shiftWords);
1.607 + if(wordCount > shiftWords)
1.608 + {
1.609 + ShiftWordsRightByBits(Ptr(), wordCount - shiftWords, shiftBits);
1.610 + }
1.611 + if(IsNegative() && WordCount()==0) // avoid negative 0
1.612 + {
1.613 + SetSign(EPositive);
1.614 + }
1.615 + return *this;
1.616 + }
1.617 +
1.618 +EXPORT_C TInt TInteger::UnsignedCompare(const TInteger& aThat) const
1.619 + {
1.620 + TUint size = WordCount();
1.621 + TUint thatSize = aThat.WordCount();
1.622 +
1.623 + if( size == thatSize )
1.624 + return Compare(Ptr(), aThat.Ptr(), size);
1.625 + else
1.626 + return size > thatSize ? 1 : -1;
1.627 + }
1.628 +
1.629 +EXPORT_C TInt TInteger::SignedCompare(const TInteger& aThat) const
1.630 + {
1.631 + if (NotNegative())
1.632 + {
1.633 + if (aThat.NotNegative())
1.634 + return UnsignedCompare(aThat);
1.635 + else
1.636 + return 1;
1.637 + }
1.638 + else
1.639 + {
1.640 + if (aThat.NotNegative())
1.641 + return -1;
1.642 + else
1.643 + return -UnsignedCompare(aThat);
1.644 + }
1.645 + }
1.646 +
1.647 +EXPORT_C TBool TInteger::operator!() const
1.648 + {
1.649 + //Ptr()[0] is just a quick way of weeding out non-zero numbers without
1.650 + //doing a full WordCount() == 0. Very good odds that a non-zero number
1.651 + //will have a bit set in the least significant word
1.652 + return IsNegative() ? EFalse : (Ptr()[0]==0 && WordCount()==0);
1.653 + }
1.654 +
1.655 +EXPORT_C TInt TInteger::SignedCompare(TInt aInteger) const
1.656 + {
1.657 + TStackInteger64 temp(aInteger);
1.658 + return SignedCompare(temp);
1.659 + }
1.660 +
1.661 +/* TBool IsPrimeL(void) const
1.662 + * and all primality related functions are implemented in primes.cpp */
1.663 +
1.664 +EXPORT_C TBool TInteger::Bit(TUint aBitPos) const
1.665 + {
1.666 + if( aBitPos/WORD_BITS >= Size() )
1.667 + {
1.668 + return 0;
1.669 + }
1.670 + else
1.671 + {
1.672 + return (((Ptr())[aBitPos/WORD_BITS] >> (aBitPos % WORD_BITS)) & 1);
1.673 + }
1.674 + }
1.675 +
1.676 +EXPORT_C void TInteger::SetBit(TUint aBitPos)
1.677 + {
1.678 + if( aBitPos/WORD_BITS < Size() )
1.679 + {
1.680 + ArraySetBit(Ptr(), aBitPos);
1.681 + }
1.682 + }
1.683 +
1.684 +EXPORT_C void TInteger::Negate()
1.685 + {
1.686 + if(!!(*this)) //don't flip sign if *this==0
1.687 + {
1.688 + SetSign(TSign((~Sign())&KSignMask));
1.689 + }
1.690 + }
1.691 +
1.692 +EXPORT_C TInt TInteger::ConvertToLongL(void) const
1.693 + {
1.694 + if(!IsConvertableToLong())
1.695 + {
1.696 + User::Leave(KErrTotalLossOfPrecision);
1.697 + }
1.698 + return ConvertToLong();
1.699 + }
1.700 +
1.701 +EXPORT_C void TInteger::CopyL(const TInteger& aInteger, TBool aAllowShrink)
1.702 + {
1.703 + if(aAllowShrink)
1.704 + {
1.705 + CleanResizeL(aInteger.Size());
1.706 + }
1.707 + else
1.708 + {
1.709 + CleanGrowL(aInteger.Size());
1.710 + }
1.711 + Construct(aInteger);
1.712 + }
1.713 +
1.714 +EXPORT_C void TInteger::CopyL(TInt aInteger, TBool aAllowShrink)
1.715 + {
1.716 + if(aAllowShrink)
1.717 + {
1.718 + CleanResizeL(2);
1.719 + }
1.720 + else
1.721 + {
1.722 + CleanGrowL(2);
1.723 + }
1.724 + Construct(aInteger);
1.725 + }
1.726 +
1.727 +EXPORT_C void TInteger::Set(const RInteger& aInteger)
1.728 + {
1.729 + assert(IsHeapBased());
1.730 + Mem::FillZ(Ptr(), WordsToBytes(Size()));
1.731 + User::Free(Ptr());
1.732 + iPtr = aInteger.iPtr;
1.733 + iSize = aInteger.iSize;
1.734 + }
1.735 +
1.736 +RInteger TInteger::PositiveAddL(const TInteger &aA, const TInteger& aB) const
1.737 + {
1.738 + RInteger sum = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));
1.739 + const word aSize = aA.Size();
1.740 + const word bSize = aB.Size();
1.741 + const word* const aReg = aA.Ptr();
1.742 + const word* const bReg = aB.Ptr();
1.743 + word* const sumReg = sum.Ptr();
1.744 +
1.745 + word carry;
1.746 + if (aSize == bSize)
1.747 + carry = Add(sumReg, aReg, bReg, aSize);
1.748 + else if (aSize > bSize)
1.749 + {
1.750 + carry = Add(sumReg, aReg, bReg, bSize);
1.751 + CopyWords(sumReg+bSize, aReg+bSize, aSize-bSize);
1.752 + carry = Increment(sumReg+bSize, aSize-bSize, carry);
1.753 + }
1.754 + else
1.755 + {
1.756 + carry = Add(sumReg, aReg, bReg, aSize);
1.757 + CopyWords(sumReg+aSize, bReg+aSize, bSize-aSize);
1.758 + carry = Increment(sumReg+aSize, bSize-aSize, carry);
1.759 + }
1.760 +
1.761 + if (carry)
1.762 + {
1.763 + CleanupStack::PushL(sum);
1.764 + sum.CleanGrowL(2*sum.Size());
1.765 + CleanupStack::Pop(&sum);
1.766 + sum.Ptr()[sum.Size()/2] = 1;
1.767 + }
1.768 + sum.SetSign(TInteger::EPositive);
1.769 + return sum;
1.770 + }
1.771 +
1.772 +RInteger TInteger::PositiveSubtractL(const TInteger &aA, const TInteger& aB) const
1.773 + {
1.774 + RInteger diff = RInteger::NewEmptyL(CryptoMax(aA.Size(), aB.Size()));
1.775 + unsigned aSize = aA.WordCount();
1.776 + aSize += aSize%2;
1.777 + unsigned bSize = aB.WordCount();
1.778 + bSize += bSize%2;
1.779 + const word* const aReg = aA.Ptr();
1.780 + const word* const bReg = aB.Ptr();
1.781 + word* const diffReg = diff.Ptr();
1.782 +
1.783 + if (aSize == bSize)
1.784 + {
1.785 + if (Compare(aReg, bReg, aSize) >= 0)
1.786 + {
1.787 + Subtract(diffReg, aReg, bReg, aSize);
1.788 + diff.SetSign(TInteger::EPositive);
1.789 + }
1.790 + else
1.791 + {
1.792 + Subtract(diffReg, bReg, aReg, aSize);
1.793 + diff.SetSign(TInteger::ENegative);
1.794 + }
1.795 + }
1.796 + else if (aSize > bSize)
1.797 + {
1.798 + word borrow = Subtract(diffReg, aReg, bReg, bSize);
1.799 + CopyWords(diffReg+bSize, aReg+bSize, aSize-bSize);
1.800 + borrow = Decrement(diffReg+bSize, aSize-bSize, borrow);
1.801 + assert(!borrow);
1.802 + diff.SetSign(TInteger::EPositive);
1.803 + }
1.804 + else
1.805 + {
1.806 + word borrow = Subtract(diffReg, bReg, aReg, aSize);
1.807 + CopyWords(diffReg+aSize, bReg+aSize, bSize-aSize);
1.808 + borrow = Decrement(diffReg+aSize, bSize-aSize, borrow);
1.809 + assert(!borrow);
1.810 + diff.SetSign(TInteger::ENegative);
1.811 + }
1.812 + return diff;
1.813 + }
1.814 +
1.815 +RInteger TInteger::PositiveMultiplyL(const TInteger &aA, const TInteger &aB) const
1.816 + {
1.817 + unsigned aSize = RoundupSize(aA.WordCount());
1.818 + unsigned bSize = RoundupSize(aB.WordCount());
1.819 +
1.820 + RInteger product = RInteger::NewEmptyL(aSize+bSize);
1.821 + CleanupClosePushL(product);
1.822 +
1.823 + RInteger workspace = RInteger::NewEmptyL(aSize + bSize);
1.824 + AsymmetricMultiply(product.Ptr(), workspace.Ptr(), aA.Ptr(), aSize, aB.Ptr(),
1.825 + bSize);
1.826 + workspace.Close();
1.827 + CleanupStack::Pop(&product);
1.828 + return product;
1.829 + }
1.830 +
1.831 +TUint TInteger::Modulo(const TInteger& aDividend, TUint aDivisor) const
1.832 + {
1.833 + assert(aDivisor);
1.834 + TUint i = aDividend.WordCount();
1.835 + TUint remainder = 0;
1.836 + while(i--)
1.837 + {
1.838 + remainder = TUint(MAKE_DWORD(aDividend.Ptr()[i], remainder) % aDivisor);
1.839 + }
1.840 + return remainder;
1.841 + }
1.842 +
1.843 +void TInteger::PositiveDivide(TUint& aRemainder, TInteger& aQuotient,
1.844 + const TInteger& aDividend, TUint aDivisor) const
1.845 + {
1.846 + assert(aDivisor);
1.847 +
1.848 + TUint i = aDividend.WordCount();
1.849 + assert(aQuotient.Size() >= RoundupSize(i));
1.850 + assert(aQuotient.Sign() == TInteger::EPositive);
1.851 + aRemainder = 0;
1.852 + while(i--)
1.853 + {
1.854 + aQuotient.Ptr()[i] =
1.855 + TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) / aDivisor);
1.856 + aRemainder =
1.857 + TUint(MAKE_DWORD(aDividend.Ptr()[i], aRemainder) % aDivisor);
1.858 + }
1.859 + }
1.860 +
1.861 +void TInteger::DivideL(TUint& aRemainder, RInteger& aQuotient,
1.862 + const TInteger& aDividend, TUint aDivisor) const
1.863 + {
1.864 + if(!aDivisor)
1.865 + {
1.866 + User::Leave(KErrDivideByZero);
1.867 + }
1.868 +
1.869 + TUint i = aDividend.WordCount();
1.870 + aQuotient.CleanNewL(RoundupSize(i));
1.871 + PositiveDivide(aRemainder, aQuotient, aDividend, aDivisor);
1.872 +
1.873 + if(aDividend.NotNegative())
1.874 + {
1.875 + aQuotient.SetSign(TInteger::EPositive);
1.876 + }
1.877 + else
1.878 + {
1.879 + aQuotient.SetSign(TInteger::ENegative);
1.880 + if(aRemainder)
1.881 + {
1.882 + --aQuotient;
1.883 + aRemainder = aDivisor = aRemainder;
1.884 + }
1.885 + }
1.886 + }
1.887 +
1.888 +void TInteger::PositiveDivideL(RInteger &aRemainder, RInteger &aQuotient,
1.889 + const TInteger &aDividend, const TInteger &aDivisor) const
1.890 + {
1.891 + unsigned dividendSize = aDividend.WordCount();
1.892 + unsigned divisorSize = aDivisor.WordCount();
1.893 +
1.894 + if (!divisorSize)
1.895 + {
1.896 + User::Leave(KErrDivideByZero);
1.897 + }
1.898 +
1.899 + if (aDividend.UnsignedCompare(aDivisor) == -1)
1.900 + {
1.901 + aRemainder.CreateNewL(aDividend.Size());
1.902 + CleanupStack::PushL(aRemainder);
1.903 + aRemainder.CopyL(aDividend); //set remainder to a
1.904 + aRemainder.SetSign(TInteger::EPositive);
1.905 + aQuotient.CleanNewL(2); //Set quotient to zero
1.906 + CleanupStack::Pop(&aRemainder);
1.907 + return;
1.908 + }
1.909 +
1.910 + dividendSize += dividendSize%2; // round up to next even number
1.911 + divisorSize += divisorSize%2;
1.912 +
1.913 + aRemainder.CleanNewL(divisorSize);
1.914 + CleanupStack::PushL(aRemainder);
1.915 + aQuotient.CleanNewL(dividendSize-divisorSize+2);
1.916 + CleanupStack::PushL(aQuotient);
1.917 +
1.918 + RInteger T = RInteger::NewEmptyL(dividendSize+2*divisorSize+4);
1.919 + Divide(aRemainder.Ptr(), aQuotient.Ptr(), T.Ptr(), aDividend.Ptr(),
1.920 + dividendSize, aDivisor.Ptr(), divisorSize);
1.921 + T.Close();
1.922 + CleanupStack::Pop(2, &aRemainder); //aQuotient, aRemainder
1.923 + }
1.924 +
1.925 +void TInteger::DivideL(RInteger& aRemainder, RInteger& aQuotient,
1.926 + const TInteger& aDividend, const TInteger& aDivisor) const
1.927 + {
1.928 + PositiveDivideL(aRemainder, aQuotient, aDividend, aDivisor);
1.929 +
1.930 + if (aDividend.IsNegative())
1.931 + {
1.932 + aQuotient.Negate();
1.933 + if (aRemainder.NotZero())
1.934 + {
1.935 + --aQuotient;
1.936 + assert(aRemainder.Size() <= aDivisor.Size());
1.937 + Subtract(aRemainder.Ptr(), aDivisor.Ptr(), aRemainder.Ptr(),
1.938 + aRemainder.Size());
1.939 + }
1.940 + }
1.941 +
1.942 + if (aDivisor.IsNegative())
1.943 + aQuotient.Negate();
1.944 + }
1.945 +
1.946 +TInt TInteger::ConvertToLong(void) const
1.947 + {
1.948 + TUint value = ConvertToUnsignedLong();
1.949 + return Sign() == EPositive ? value : -(static_cast<TInt>(value));
1.950 + }
1.951 +
1.952 +TBool TInteger::IsConvertableToLong(void) const
1.953 + {
1.954 + if(WordCount() > 1)
1.955 + {
1.956 + return EFalse;
1.957 + }
1.958 + TUint value = (Ptr())[0];
1.959 + if(Sign() == EPositive)
1.960 + {
1.961 + return static_cast<TInt>(value) >= 0;
1.962 + }
1.963 + else
1.964 + {
1.965 + return -(static_cast<TInt>(value)) < 0;
1.966 + }
1.967 + }
1.968 +
1.969 +void TInteger::RandomizeL(TUint aBits, TRandomAttribute aAttr)
1.970 + {
1.971 + if(!aBits)
1.972 + {
1.973 + return;
1.974 + }
1.975 + const TUint bytes = BitsToBytes(aBits);
1.976 + const TUint words = BitsToWords(aBits);
1.977 + CleanGrowL(words);
1.978 + TPtr8 buf((TUint8*)(Ptr()), bytes, WordsToBytes(Size()));
1.979 + TUint bitpos = aBits % BYTE_BITS;
1.980 + GenerateRandomBytesL(buf);
1.981 + //mask with 0 all bits above the num requested in the most significant byte
1.982 + if(bitpos)
1.983 + {
1.984 + buf[bytes-1] = TUint8( buf[bytes-1] & ((1L << bitpos) - 1) );
1.985 + }
1.986 + //set most significant (top) bit
1.987 + if(aAttr == ETopBitSet || aAttr == ETop2BitsSet)
1.988 + {
1.989 + SetBit(aBits-1); //Set bit counts from 0
1.990 + assert(BitCount() == aBits);
1.991 + assert(Bit(aBits-1));
1.992 + }
1.993 + //set 2nd bit from top
1.994 + if(aAttr == ETop2BitsSet)
1.995 + {
1.996 + SetBit(aBits-2); //Set bit counts from 0
1.997 + assert(BitCount() == aBits);
1.998 + assert(Bit(aBits-1));
1.999 + assert(Bit(aBits-2));
1.1000 + }
1.1001 + }
1.1002 +
1.1003 +void TInteger::RandomizeL(const TInteger& aMin, const TInteger& aMax)
1.1004 + {
1.1005 + assert(aMax > aMin);
1.1006 + assert(aMin.NotNegative());
1.1007 + RInteger range = RInteger::NewL(aMax);
1.1008 + CleanupStack::PushL(range);
1.1009 + range -= aMin;
1.1010 + const TUint bits = range.BitCount();
1.1011 +
1.1012 + //if we find a number < range then aMin+range < aMax
1.1013 + do
1.1014 + {
1.1015 + RandomizeL(bits, EAllBitsRandom);
1.1016 + }
1.1017 + while(*this > range);
1.1018 +
1.1019 + *this += aMin;
1.1020 + CleanupStack::PopAndDestroy(&range);
1.1021 + }
1.1022 +
1.1023 +/* void PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)
1.1024 + * and all primality related functions are implemented in primes.cpp */
1.1025 +
1.1026 +void TInteger::CreateNewL(TUint aNewSize)
1.1027 + {
1.1028 + //should only be called on construction
1.1029 + assert(!iPtr);
1.1030 +
1.1031 + TUint newSize = RoundupSize(aNewSize);
1.1032 + SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));
1.1033 + SetSize(newSize);
1.1034 + SetHeapBased();
1.1035 + }
1.1036 +
1.1037 +void TInteger::CleanNewL(TUint aNewSize)
1.1038 + {
1.1039 + CreateNewL(aNewSize);
1.1040 + Mem::FillZ(Ptr(), WordsToBytes(Size())); //clear integer storage
1.1041 + }
1.1042 +
1.1043 +void TInteger::CleanGrowL(TUint aNewSize)
1.1044 + {
1.1045 + assert(IsHeapBased());
1.1046 + TUint newSize = RoundupSize(aNewSize);
1.1047 + TUint oldSize = Size();
1.1048 + if(newSize > oldSize)
1.1049 + {
1.1050 + TUint* oldPtr = Ptr();
1.1051 + //1) allocate new memory and set ptr and size
1.1052 + SetPtr((TUint*)User::AllocL(WordsToBytes(newSize)));
1.1053 + SetSize(newSize);
1.1054 + //2) copy old mem to new mem
1.1055 + Mem::Copy(Ptr(), oldPtr, WordsToBytes(oldSize));
1.1056 + //3) zero all old memory
1.1057 + Mem::FillZ(oldPtr, WordsToBytes(oldSize));
1.1058 + //4) give back old memory
1.1059 + User::Free(oldPtr);
1.1060 + //5) zero new memory from end of copy to end of growth
1.1061 + Mem::FillZ(Ptr() + oldSize, WordsToBytes(newSize-oldSize));
1.1062 + }
1.1063 + }
1.1064 +
1.1065 +void TInteger::CleanResizeL(TUint aNewSize)
1.1066 + {
1.1067 + assert(IsHeapBased());
1.1068 + TUint newSize = RoundupSize(aNewSize);
1.1069 + TUint oldSize = Size();
1.1070 + if(newSize > oldSize)
1.1071 + {
1.1072 + CleanGrowL(aNewSize);
1.1073 + }
1.1074 + else if(newSize < oldSize)
1.1075 + {
1.1076 + TUint* oldPtr = Ptr();
1.1077 + //1) zero memory above newsize
1.1078 + Mem::FillZ(oldPtr+WordsToBytes(aNewSize),WordsToBytes(oldSize-newSize));
1.1079 + //2) ReAlloc cell. Since our newsize is less than oldsize, it is
1.1080 + //guarenteed not to move. Thus this is just freeing part of our old
1.1081 + //cell to the heap for other uses.
1.1082 + SetPtr((TUint*)User::ReAllocL(Ptr(), WordsToBytes(newSize)));
1.1083 + SetSize(newSize);
1.1084 + }
1.1085 + }
1.1086 +
1.1087 +TInteger::TInteger() : iSize(0), iPtr(0)
1.1088 + {
1.1089 + }
1.1090 +
1.1091 +void TInteger::Construct(const TDesC8& aValue)
1.1092 + {
1.1093 + assert(Size() >= BytesToWords(aValue.Size()));
1.1094 + if(aValue.Size() > 0)
1.1095 + {
1.1096 + //People write numbers with the most significant digits first (big
1.1097 + //endian) but we store our numbers in little endian. Hence we need to
1.1098 + //reverse the string by bytes.
1.1099 +
1.1100 + TUint bytes = aValue.Size();
1.1101 + TUint8* i = (TUint8*)Ptr();
1.1102 + TUint8* j = (TUint8*)aValue.Ptr() + bytes;
1.1103 +
1.1104 + //Swap the endianess of the number itself
1.1105 + // (msb) 01 02 03 04 05 06 (lsb) becomes ->
1.1106 + // (lsb) 06 05 04 03 02 01 (msb)
1.1107 + while( j != (TUint8*)aValue.Ptr() )
1.1108 + {
1.1109 + *i++ = *--j;
1.1110 + }
1.1111 + Mem::FillZ((TUint8*)Ptr() + bytes, WordsToBytes(Size()) - bytes);
1.1112 + }
1.1113 + else
1.1114 + {
1.1115 + //if size is zero, we zero the whole register
1.1116 + Mem::FillZ((TUint8*)Ptr(), WordsToBytes(Size()));
1.1117 + }
1.1118 + SetSign(EPositive);
1.1119 + }
1.1120 +
1.1121 +void TInteger::Construct(const TInteger& aInteger)
1.1122 + {
1.1123 + assert(Size() >= aInteger.Size());
1.1124 + CopyWords(Ptr(), aInteger.Ptr(), aInteger.Size());
1.1125 + if(Size() > aInteger.Size())
1.1126 + {
1.1127 + Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));
1.1128 + }
1.1129 + SetSign(aInteger.Sign());
1.1130 + }
1.1131 +
1.1132 +void TInteger::Construct(TInt aInteger)
1.1133 + {
1.1134 + Construct((TUint)aInteger);
1.1135 + if(aInteger < 0)
1.1136 + {
1.1137 + SetSign(ENegative);
1.1138 + Ptr()[0] = -aInteger;
1.1139 + }
1.1140 + }
1.1141 +
1.1142 +void TInteger::Construct(TUint aInteger)
1.1143 + {
1.1144 + assert(Size() >= 2);
1.1145 + SetSign(EPositive);
1.1146 + Ptr()[0] = aInteger;
1.1147 + Mem::FillZ(Ptr()+1, WordsToBytes(Size()-1));
1.1148 + }
1.1149 +
1.1150 +void TInteger::ConstructStack(TUint aWords, TUint aInteger)
1.1151 + {
1.1152 + SetPtr((TUint*)(this)+2);
1.1153 + //SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1
1.1154 + SetSize(aWords);
1.1155 + assert(Size() >= 2);
1.1156 + Ptr()[0] = aInteger;
1.1157 + Mem::FillZ(&(Ptr()[1]), WordsToBytes(Size()-1));
1.1158 + }
1.1159 +
1.1160 +void TInteger::ConstructStack(TUint aWords, const TInteger& aInteger)
1.1161 + {
1.1162 + SetPtr((TUint*)(this)+2);
1.1163 + //SetStackBased(); //Not strictly needed as stackbased is a 0 at bit 1
1.1164 + SetSize(aWords);
1.1165 + assert( Size() >= RoundupSize(aInteger.WordCount()) );
1.1166 + CopyWords(Ptr(), aInteger.Ptr(), aInteger.Size());
1.1167 + Mem::FillZ(Ptr()+aInteger.Size(), WordsToBytes(Size()-aInteger.Size()));
1.1168 + }
1.1169 +