1 // Copyright 2014 PDFium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Original code by Matt McCutchen, see the LICENSE file. 6 7 #ifndef BIGINTEGER_H 8 #define BIGINTEGER_H 9 10 #include "BigUnsigned.hh" 11 12 /* A BigInteger object represents a signed integer of size limited only by 13 * available memory. BigUnsigneds support most mathematical operators and can 14 * be converted to and from most primitive integer types. 15 * 16 * A BigInteger is just an aggregate of a BigUnsigned and a sign. (It is no 17 * longer derived from BigUnsigned because that led to harmful implicit 18 * conversions.) */ 19 class BigInteger { 20 21 public: 22 typedef BigUnsigned::Blk Blk; 23 typedef BigUnsigned::Index Index; 24 typedef BigUnsigned::CmpRes CmpRes; 25 static const CmpRes 26 less = BigUnsigned::less , 27 equal = BigUnsigned::equal , 28 greater = BigUnsigned::greater; 29 // Enumeration for the sign of a BigInteger. 30 enum Sign { negative = -1, zero = 0, positive = 1 }; 31 32 protected: 33 Sign sign; 34 BigUnsigned mag; 35 36 public: 37 // Constructs zero. 38 BigInteger() : sign(zero), mag() {} 39 40 // Copy constructor 41 BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {}; 42 43 // Assignment operator 44 void operator=(const BigInteger &x); 45 46 // Constructor that copies from a given array of blocks with a sign. 47 BigInteger(const Blk *b, Index blen, Sign s); 48 49 // Nonnegative constructor that copies from a given array of blocks. 50 BigInteger(const Blk *b, Index blen) : mag(b, blen) { 51 sign = mag.isZero() ? zero : positive; 52 } 53 54 // Constructor from a BigUnsigned and a sign 55 BigInteger(const BigUnsigned &x, Sign s); 56 57 // Nonnegative constructor from a BigUnsigned 58 BigInteger(const BigUnsigned &x) : mag(x) { 59 sign = mag.isZero() ? zero : positive; 60 } 61 62 // Constructors from primitive integer types 63 BigInteger(unsigned long x); 64 BigInteger( long x); 65 BigInteger(unsigned int x); 66 BigInteger( int x); 67 BigInteger(unsigned short x); 68 BigInteger( short x); 69 70 /* Converters to primitive integer types 71 * The implicit conversion operators caused trouble, so these are now 72 * named. */ 73 unsigned long toUnsignedLong () const; 74 long toLong () const; 75 unsigned int toUnsignedInt () const; 76 int toInt () const; 77 unsigned short toUnsignedShort() const; 78 short toShort () const; 79 protected: 80 // Helper 81 template <class X> X convertToUnsignedPrimitive() const; 82 template <class X, class UX> X convertToSignedPrimitive() const; 83 public: 84 85 // ACCESSORS 86 Sign getSign() const { return sign; } 87 /* The client can't do any harm by holding a read-only reference to the 88 * magnitude. */ 89 const BigUnsigned &getMagnitude() const { return mag; } 90 91 // Some accessors that go through to the magnitude 92 Index getLength() const { return mag.getLength(); } 93 Index getCapacity() const { return mag.getCapacity(); } 94 Blk getBlock(Index i) const { return mag.getBlock(i); } 95 bool isZero() const { return sign == zero; } // A bit special 96 97 // COMPARISONS 98 99 // Compares this to x like Perl's <=> 100 CmpRes compareTo(const BigInteger &x) const; 101 102 // Ordinary comparison operators 103 bool operator ==(const BigInteger &x) const { 104 return sign == x.sign && mag == x.mag; 105 } 106 bool operator !=(const BigInteger &x) const { return !operator ==(x); }; 107 bool operator < (const BigInteger &x) const { return compareTo(x) == less ; } 108 bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; } 109 bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; } 110 bool operator > (const BigInteger &x) const { return compareTo(x) == greater; } 111 112 // OPERATORS -- See the discussion in BigUnsigned.hh. 113 void add (const BigInteger &a, const BigInteger &b); 114 void subtract(const BigInteger &a, const BigInteger &b); 115 void multiply(const BigInteger &a, const BigInteger &b); 116 /* See the comment on BigUnsigned::divideWithRemainder. Semantics 117 * differ from those of primitive integers when negatives and/or zeros 118 * are involved. */ 119 void divideWithRemainder(const BigInteger &b, BigInteger &q); 120 void negate(const BigInteger &a); 121 122 /* Bitwise operators are not provided for BigIntegers. Use 123 * getMagnitude to get the magnitude and operate on that instead. */ 124 125 BigInteger operator +(const BigInteger &x) const; 126 BigInteger operator -(const BigInteger &x) const; 127 BigInteger operator *(const BigInteger &x) const; 128 BigInteger operator /(const BigInteger &x) const; 129 BigInteger operator %(const BigInteger &x) const; 130 BigInteger operator -() const; 131 132 void operator +=(const BigInteger &x); 133 void operator -=(const BigInteger &x); 134 void operator *=(const BigInteger &x); 135 void operator /=(const BigInteger &x); 136 void operator %=(const BigInteger &x); 137 void flipSign(); 138 139 // INCREMENT/DECREMENT OPERATORS 140 void operator ++( ); 141 void operator ++(int); 142 void operator --( ); 143 void operator --(int); 144 }; 145 146 // NORMAL OPERATORS 147 /* These create an object to hold the result and invoke 148 * the appropriate put-here operation on it, passing 149 * this and x. The new object is then returned. */ 150 inline BigInteger BigInteger::operator +(const BigInteger &x) const { 151 BigInteger ans; 152 ans.add(*this, x); 153 return ans; 154 } 155 inline BigInteger BigInteger::operator -(const BigInteger &x) const { 156 BigInteger ans; 157 ans.subtract(*this, x); 158 return ans; 159 } 160 inline BigInteger BigInteger::operator *(const BigInteger &x) const { 161 BigInteger ans; 162 ans.multiply(*this, x); 163 return ans; 164 } 165 inline BigInteger BigInteger::operator /(const BigInteger &x) const { 166 if (x.isZero()) 167 abort(); 168 BigInteger q, r; 169 r = *this; 170 r.divideWithRemainder(x, q); 171 return q; 172 } 173 inline BigInteger BigInteger::operator %(const BigInteger &x) const { 174 if (x.isZero()) 175 abort(); 176 BigInteger q, r; 177 r = *this; 178 r.divideWithRemainder(x, q); 179 return r; 180 } 181 inline BigInteger BigInteger::operator -() const { 182 BigInteger ans; 183 ans.negate(*this); 184 return ans; 185 } 186 187 /* 188 * ASSIGNMENT OPERATORS 189 * 190 * Now the responsibility for making a temporary copy if necessary 191 * belongs to the put-here operations. See Assignment Operators in 192 * BigUnsigned.hh. 193 */ 194 inline void BigInteger::operator +=(const BigInteger &x) { 195 add(*this, x); 196 } 197 inline void BigInteger::operator -=(const BigInteger &x) { 198 subtract(*this, x); 199 } 200 inline void BigInteger::operator *=(const BigInteger &x) { 201 multiply(*this, x); 202 } 203 inline void BigInteger::operator /=(const BigInteger &x) { 204 if (x.isZero()) 205 abort(); 206 /* The following technique is slightly faster than copying *this first 207 * when x is large. */ 208 BigInteger q; 209 divideWithRemainder(x, q); 210 // *this contains the remainder, but we overwrite it with the quotient. 211 *this = q; 212 } 213 inline void BigInteger::operator %=(const BigInteger &x) { 214 if (x.isZero()) 215 abort(); 216 BigInteger q; 217 // Mods *this by x. Don't care about quotient left in q. 218 divideWithRemainder(x, q); 219 } 220 // This one is trivial 221 inline void BigInteger::flipSign() { 222 sign = Sign(-sign); 223 } 224 225 #endif 226
