| // Copyright 2014 PDFium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| // Original code by Matt McCutchen, see the LICENSE file. |
| |
| #ifndef BIGINTEGER_H |
| #define BIGINTEGER_H |
| |
| #include "BigUnsigned.hh" |
| |
| /* A BigInteger object represents a signed integer of size limited only by |
| * available memory. BigUnsigneds support most mathematical operators and can |
| * be converted to and from most primitive integer types. |
| * |
| * A BigInteger is just an aggregate of a BigUnsigned and a sign. (It is no |
| * longer derived from BigUnsigned because that led to harmful implicit |
| * conversions.) */ |
| class BigInteger { |
| |
| public: |
| typedef BigUnsigned::Blk Blk; |
| typedef BigUnsigned::Index Index; |
| typedef BigUnsigned::CmpRes CmpRes; |
| static const CmpRes |
| less = BigUnsigned::less , |
| equal = BigUnsigned::equal , |
| greater = BigUnsigned::greater; |
| // Enumeration for the sign of a BigInteger. |
| enum Sign { negative = -1, zero = 0, positive = 1 }; |
| |
| protected: |
| Sign sign; |
| BigUnsigned mag; |
| |
| public: |
| // Constructs zero. |
| BigInteger() : sign(zero), mag() {} |
| |
| // Copy constructor |
| BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {} |
| |
| // Assignment operator |
| BigInteger& operator=(const BigInteger &x); |
| |
| // Constructor that copies from a given array of blocks with a sign. |
| BigInteger(const Blk *b, Index blen, Sign s); |
| |
| // Nonnegative constructor that copies from a given array of blocks. |
| BigInteger(const Blk *b, Index blen) : mag(b, blen) { |
| sign = mag.isZero() ? zero : positive; |
| } |
| |
| // Constructor from a BigUnsigned and a sign |
| BigInteger(const BigUnsigned &x, Sign s); |
| |
| // Nonnegative constructor from a BigUnsigned |
| BigInteger(const BigUnsigned &x) : mag(x) { |
| sign = mag.isZero() ? zero : positive; |
| } |
| |
| // Constructors from primitive integer types |
| BigInteger(unsigned long x); |
| BigInteger( long x); |
| BigInteger(unsigned int x); |
| BigInteger( int x); |
| BigInteger(unsigned short x); |
| BigInteger( short x); |
| |
| /* Converters to primitive integer types |
| * The implicit conversion operators caused trouble, so these are now |
| * named. */ |
| unsigned long toUnsignedLong () const; |
| long toLong () const; |
| unsigned int toUnsignedInt () const; |
| int toInt () const; |
| unsigned short toUnsignedShort() const; |
| short toShort () const; |
| protected: |
| // Helper |
| template <class X> X convertToUnsignedPrimitive() const; |
| template <class X, class UX> X convertToSignedPrimitive() const; |
| public: |
| |
| // ACCESSORS |
| Sign getSign() const { return sign; } |
| /* The client can't do any harm by holding a read-only reference to the |
| * magnitude. */ |
| const BigUnsigned &getMagnitude() const { return mag; } |
| |
| // Some accessors that go through to the magnitude |
| Index getLength() const { return mag.getLength(); } |
| Index getCapacity() const { return mag.getCapacity(); } |
| Blk getBlock(Index i) const { return mag.getBlock(i); } |
| bool isZero() const { return sign == zero; } // A bit special |
| |
| // COMPARISONS |
| |
| // Compares this to x like Perl's <=> |
| CmpRes compareTo(const BigInteger &x) const; |
| |
| // Ordinary comparison operators |
| bool operator ==(const BigInteger &x) const { |
| return sign == x.sign && mag == x.mag; |
| } |
| bool operator !=(const BigInteger &x) const { return !operator ==(x); } |
| bool operator < (const BigInteger &x) const { return compareTo(x) == less ; } |
| bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; } |
| bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; } |
| bool operator > (const BigInteger &x) const { return compareTo(x) == greater; } |
| |
| // OPERATORS -- See the discussion in BigUnsigned.hh. |
| void add (const BigInteger &a, const BigInteger &b); |
| void subtract(const BigInteger &a, const BigInteger &b); |
| void multiply(const BigInteger &a, const BigInteger &b); |
| /* See the comment on BigUnsigned::divideWithRemainder. Semantics |
| * differ from those of primitive integers when negatives and/or zeros |
| * are involved. */ |
| void divideWithRemainder(const BigInteger &b, BigInteger &q); |
| void negate(const BigInteger &a); |
| |
| /* Bitwise operators are not provided for BigIntegers. Use |
| * getMagnitude to get the magnitude and operate on that instead. */ |
| |
| BigInteger operator +(const BigInteger &x) const; |
| BigInteger operator -(const BigInteger &x) const; |
| BigInteger operator *(const BigInteger &x) const; |
| BigInteger operator /(const BigInteger &x) const; |
| BigInteger operator %(const BigInteger &x) const; |
| BigInteger operator -() const; |
| |
| BigInteger& operator +=(const BigInteger &x); |
| BigInteger& operator -=(const BigInteger &x); |
| BigInteger& operator *=(const BigInteger &x); |
| BigInteger& operator /=(const BigInteger &x); |
| BigInteger& operator %=(const BigInteger &x); |
| void flipSign(); |
| |
| // INCREMENT/DECREMENT OPERATORS |
| BigInteger& operator ++( ); |
| BigInteger operator ++(int); |
| BigInteger& operator --( ); |
| BigInteger operator --(int); |
| }; |
| |
| // NORMAL OPERATORS |
| /* These create an object to hold the result and invoke |
| * the appropriate put-here operation on it, passing |
| * this and x. The new object is then returned. */ |
| inline BigInteger BigInteger::operator +(const BigInteger &x) const { |
| BigInteger ans; |
| ans.add(*this, x); |
| return ans; |
| } |
| inline BigInteger BigInteger::operator -(const BigInteger &x) const { |
| BigInteger ans; |
| ans.subtract(*this, x); |
| return ans; |
| } |
| inline BigInteger BigInteger::operator *(const BigInteger &x) const { |
| BigInteger ans; |
| ans.multiply(*this, x); |
| return ans; |
| } |
| inline BigInteger BigInteger::operator /(const BigInteger &x) const { |
| if (x.isZero()) |
| abort(); |
| BigInteger q, r; |
| r = *this; |
| r.divideWithRemainder(x, q); |
| return q; |
| } |
| inline BigInteger BigInteger::operator %(const BigInteger &x) const { |
| if (x.isZero()) |
| abort(); |
| BigInteger q, r; |
| r = *this; |
| r.divideWithRemainder(x, q); |
| return r; |
| } |
| inline BigInteger BigInteger::operator -() const { |
| BigInteger ans; |
| ans.negate(*this); |
| return ans; |
| } |
| |
| /* |
| * ASSIGNMENT OPERATORS |
| * |
| * Now the responsibility for making a temporary copy if necessary |
| * belongs to the put-here operations. See Assignment Operators in |
| * BigUnsigned.hh. |
| */ |
| inline BigInteger& BigInteger::operator +=(const BigInteger &x) { |
| add(*this, x); |
| return *this; |
| } |
| inline BigInteger& BigInteger::operator -=(const BigInteger &x) { |
| subtract(*this, x); |
| return *this; |
| } |
| inline BigInteger& BigInteger::operator *=(const BigInteger &x) { |
| multiply(*this, x); |
| return *this; |
| } |
| inline BigInteger& BigInteger::operator /=(const BigInteger &x) { |
| if (x.isZero()) |
| abort(); |
| /* The following technique is slightly faster than copying *this first |
| * when x is large. */ |
| BigInteger q; |
| divideWithRemainder(x, q); |
| // *this contains the remainder, but we overwrite it with the quotient. |
| *this = q; |
| return *this; |
| } |
| inline BigInteger& BigInteger::operator %=(const BigInteger &x) { |
| if (x.isZero()) |
| abort(); |
| BigInteger q; |
| // Mods *this by x. Don't care about quotient left in q. |
| divideWithRemainder(x, q); |
| return *this; |
| } |
| // This one is trivial |
| inline void BigInteger::flipSign() { |
| sign = Sign(-sign); |
| } |
| |
| #endif |