/* [<][>][^][v][top][bottom][index][help] */
/* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
*
* The contents of this file are subject to the Mozilla Public License Version
* 1.1 (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* The Original Code is [Open Source Virtual Machine.].
*
* The Initial Developer of the Original Code is
* Adobe System Incorporated.
* Portions created by the Initial Developer are Copyright (C) 1993-2006
* the Initial Developer. All Rights Reserved.
*
* Contributor(s):
* Adobe AS3 Team
*
* Alternatively, the contents of this file may be used under the terms of
* either the GNU General Public License Version 2 or later (the "GPL"), or
* the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
* in which case the provisions of the GPL or the LGPL are applicable instead
* of those above. If you wish to allow use of your version of this file only
* under the terms of either the GPL or the LGPL, and not to allow others to
* use your version of this file under the terms of the MPL, indicate your
* decision by deleting the provisions above and replace them with the notice
* and other provisions required by the GPL or the LGPL. If you do not delete
* the provisions above, a recipient may use your version of this file under
* the terms of any one of the MPL, the GPL or the LGPL.
*
* ***** END LICENSE BLOCK ***** */
#ifndef __avmplus_BigInteger__
#define __avmplus_BigInteger__
//
// BigInteger is an implementation of arbitrary precision integers. This class is used by the
// D2A class in mathutils.h to print doubles to greater than 15 digits of precision. It has
// been implemented with that use in mind, so if you want to use it for some other purpose
// be aware that certain basic features have not been implemented: divide() assumes the result
// is a single digit, there is no support for negative values, and subtract() assumes that the
// term being subtracted from is larger than the operand.
//
// By far, memory allocation is the gating speed factor. D2A never uses more than 8 or so values
// during a given run, so a simple memoryCache is used to keep 8 temporaries around for quick reuse.
// This would likely have to be adjusted for more general use.
namespace avmplus
{
class BigInteger
{
public:
// Memory management
// --------------------------------------------------------
BigInteger()
{
numWords = 0;
}
~BigInteger()
{
}
inline void setFromInteger(int32 initVal)
{
wordBuffer[0] = initVal;
numWords = 1;
}
void setFromDouble(double value);
void setFromBigInteger(const BigInteger* from, int32 offset, int32 amount);
double doubleValueOf() const; // returns double approximation of this integer
// operations
// --------------------------------------------------------
// Compare (sum = this+offset) vs other. if sum > other, return 1. if sum < other,
// return -1, else return 0. Note that all terms are assumed to be positive.
int32 compare(const BigInteger *other) const;
// same as above, but compare this+offset with other.
int32 compareOffset(const BigInteger *other, const BigInteger *offset)
{
BigInteger tempInt;
tempInt.setFromInteger(0);
add(offset,&tempInt);
return tempInt.compare(other);
}
// Add or subtract one BigInteger from another. isAdd determines if + or - is performed.
// If result is specified, write result into it (allows for reuse of temporaries), else
// allocate a new BigInteger for the result.
BigInteger* addOrSubtract(const BigInteger* other, bool isAdd, BigInteger* result) const;
// syntactic sugar for simple case of adding two BigIntegers
inline BigInteger* add(const BigInteger* other, BigInteger* result) const
{
return addOrSubtract(other, true, result);
}
// syntactic sugar for simple case of subtracting two BigIntegers
inline BigInteger* subtract(const BigInteger* other, BigInteger* result) const
{
return addOrSubtract(other, false, result);
}
// Increment this by other. other is assumed to be positive
inline void incrementBy(const BigInteger* other)
{
BigInteger tempInt;
tempInt.setFromInteger(0);
addOrSubtract(other,true,&tempInt);
copyFrom(&tempInt);
}
// Decrement this by other. other is assumed to be positive and smaller than this.
inline void decrementBy(const BigInteger* other)
{
BigInteger tempInt;
tempInt.setFromInteger(0);
addOrSubtract(other,false,&tempInt);
copyFrom(&tempInt);
}
// Shift a BigInteger by <shiftBy> bits to right or left. If
// result is not NULL, write result into it, else allocate a new BigInteger.
BigInteger* rshift(uint32 shiftBy, BigInteger* result) const;
BigInteger* lshift(uint32 shiftBy, BigInteger* result) const;
// Same as above but store result back into "this"
void lshiftBy(uint32 shiftBy)
{
BigInteger tempInt;
tempInt.setFromInteger(0);
lshift(shiftBy,&tempInt);
copyFrom(&tempInt);
}
void rshiftBy(uint32 shiftBy)
{
BigInteger tempInt;
tempInt.setFromInteger(0);
rshift(shiftBy,&tempInt);
copyFrom(&tempInt);
}
// Multiply this by an integer factor and add an integer increment. Store result back in this.
// Note, the addition is essentially free
void multAndIncrementBy( int32 factor, int32 addition);
inline void multBy( int32 factor)
{
multAndIncrementBy(factor,0);
}
// Shorthand for multiplying this by a double valued factor (and storing result back in this).
inline void multBy(double factor)
{
BigInteger bigFactor;
bigFactor.setFromDouble(factor);
multBy(&bigFactor);
}
// Multiply by another BigInteger. If optional arg result is not null, reuse it for
// result, else allocate a new result.
// (note, despite the name "smallerNum", argument does not need to be smaller than this).
BigInteger* mult(const BigInteger* other, BigInteger* result) const;
void multBy(const BigInteger *other)
{
BigInteger tempInt;
tempInt.setFromInteger(0);
mult(other,&tempInt);
copyFrom(&tempInt);
}
// divide this by divisor, put the remainder (i.e. this % divisor) into residual. If optional third argument result
// is not null, use it to store the result of the div, else allocate a new BigInteger for the result.
// Note: this has been hard to get right. If bugs do show up, use divideByReciprocalMethod instead
// Note2: this is optimized for the types of numerator/denominators generated by D2A. It will not work when
// the result would be a value bigger than 9. For general purpose BigInteger division, use divideByReciprocalMethod.
BigInteger* quickDivMod(const BigInteger* divisor, BigInteger* modResult, BigInteger* divResult);
/* Thought this would be faster than the above, but its not */
BigInteger* divideByReciprocalMethod(const BigInteger* divisor, BigInteger* modResult, BigInteger* divResult);
uint32 lg2() const;
// q = this->divBy(divisor) is equilvalent to: q = this->divMod(divisor,remainderResult); this = remainderResult;
BigInteger* divBy(const BigInteger* divisor, BigInteger* divResult);
// copy words from another BigInteger. By default, copy all words into this. If copyOffsetWords
// is not -1, then copy numCopyWords starting at word copyOffsetWords.
void copyFrom(const BigInteger *other, int32 copyOffsetWords=-1, int32 numCopyWords=-1)
{
int32 numCopy = (numCopyWords == -1) ? other->numWords : numCopyWords;
int32 copyOffset = (copyOffsetWords == -1) ? 0 : copyOffsetWords;
copyBuffer(other->wordBuffer+copyOffset, numCopy);
}
// Data members
// --------------------------------------------------------
static const int kMaxBigIntegerBufferSize=128;
uint32 wordBuffer[kMaxBigIntegerBufferSize+2];
int32 numWords;
private:
// sign; Simplifications are made assuming all numbers are positive
// Utility methods
// --------------------------------------------------------
// set value to a simple integer
inline void setValue(uint32 val)
{
this->numWords = 1;
this->wordBuffer[0] = val;
}
// copy wordBuffer from another BigInteger
inline void copyBuffer(const uint32 *newBuff, int32 size)
{
numWords = size;
AvmAssert(newBuff != wordBuffer);
AvmAssert(numWords <= kMaxBigIntegerBufferSize);
VMPI_memcpy(wordBuffer, newBuff, numWords*sizeof(uint32));
}
inline void setNumWords( int32 newNumWords,bool initToZero=false)
{
int32 oldNumWords = numWords;
numWords = newNumWords;
AvmAssert(numWords <= kMaxBigIntegerBufferSize);
if (initToZero && oldNumWords < numWords)
{
for( int32 x = oldNumWords-1; x < numWords; x++)
wordBuffer[x] = 0;
}
}
// remove leading zero words from number.
inline void trimLeadingZeros()
{
int32 x;
for( x = numWords-1; x >= 0 && wordBuffer[x] == 0; x--)
;
this->numWords = (x == -1) ? 1 : x+1; // make sure a zero value has numWords = 1
}
};
}
#endif // __avmplus_BigInteger__