| OLD | NEW |
| 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 |
| 1 #include "BigInteger.hh" | 7 #include "BigInteger.hh" |
| 2 | 8 |
| 3 void BigInteger::operator =(const BigInteger &x) { | 9 void BigInteger::operator =(const BigInteger &x) { |
| 4 // Calls like a = a have no effect | 10 // Calls like a = a have no effect |
| 5 if (this == &x) | 11 if (this == &x) |
| 6 return; | 12 return; |
| 7 // Copy sign | 13 // Copy sign |
| 8 sign = x.sign; | 14 sign = x.sign; |
| 9 // Copy the rest | 15 // Copy the rest |
| 10 mag = x.mag; | 16 mag = x.mag; |
| 11 } | 17 } |
| 12 | 18 |
| 13 BigInteger::BigInteger(const Blk *b, Index blen, Sign s) : mag(b, blen) { | 19 BigInteger::BigInteger(const Blk *b, Index blen, Sign s) : mag(b, blen) { |
| 14 switch (s) { | 20 switch (s) { |
| 15 case zero: | 21 case zero: |
| 16 if (!mag.isZero()) | 22 if (!mag.isZero()) |
| 23 #ifdef FOXIT_CHROME_BUILD |
| 24 abort(); |
| 25 #else |
| 17 throw "BigInteger::BigInteger(const Blk *, Index, Sign):
Cannot use a sign of zero with a nonzero magnitude"; | 26 throw "BigInteger::BigInteger(const Blk *, Index, Sign):
Cannot use a sign of zero with a nonzero magnitude"; |
| 27 #endif |
| 18 sign = zero; | 28 sign = zero; |
| 19 break; | 29 break; |
| 20 case positive: | 30 case positive: |
| 21 case negative: | 31 case negative: |
| 22 // If the magnitude is zero, force the sign to zero. | 32 // If the magnitude is zero, force the sign to zero. |
| 23 sign = mag.isZero() ? zero : s; | 33 sign = mag.isZero() ? zero : s; |
| 24 break; | 34 break; |
| 25 default: | 35 default: |
| 26 /* g++ seems to be optimizing out this case on the assumption | 36 /* g++ seems to be optimizing out this case on the assumption |
| 27 * that the sign is a valid member of the enumeration. Oh well.
*/ | 37 * that the sign is a valid member of the enumeration. Oh well.
*/ |
| 38 #ifdef FOXIT_CHROME_BUILD |
| 39 abort(); |
| 40 #else |
| 28 throw "BigInteger::BigInteger(const Blk *, Index, Sign): Invalid
sign"; | 41 throw "BigInteger::BigInteger(const Blk *, Index, Sign): Invalid
sign"; |
| 42 #endif |
| 29 } | 43 } |
| 30 } | 44 } |
| 31 | 45 |
| 32 BigInteger::BigInteger(const BigUnsigned &x, Sign s) : mag(x) { | 46 BigInteger::BigInteger(const BigUnsigned &x, Sign s) : mag(x) { |
| 33 switch (s) { | 47 switch (s) { |
| 34 case zero: | 48 case zero: |
| 35 if (!mag.isZero()) | 49 if (!mag.isZero()) |
| 50 #ifdef FOXIT_CHROME_BUILD |
| 51 abort(); |
| 52 #else |
| 36 throw "BigInteger::BigInteger(const BigUnsigned &, Sign)
: Cannot use a sign of zero with a nonzero magnitude"; | 53 throw "BigInteger::BigInteger(const BigUnsigned &, Sign)
: Cannot use a sign of zero with a nonzero magnitude"; |
| 54 #endif |
| 37 sign = zero; | 55 sign = zero; |
| 38 break; | 56 break; |
| 39 case positive: | 57 case positive: |
| 40 case negative: | 58 case negative: |
| 41 // If the magnitude is zero, force the sign to zero. | 59 // If the magnitude is zero, force the sign to zero. |
| 42 sign = mag.isZero() ? zero : s; | 60 sign = mag.isZero() ? zero : s; |
| 43 break; | 61 break; |
| 44 default: | 62 default: |
| 45 /* g++ seems to be optimizing out this case on the assumption | 63 /* g++ seems to be optimizing out this case on the assumption |
| 46 * that the sign is a valid member of the enumeration. Oh well.
*/ | 64 * that the sign is a valid member of the enumeration. Oh well.
*/ |
| 65 #ifdef FOXIT_CHROME_BUILD |
| 66 abort(); |
| 67 #else |
| 47 throw "BigInteger::BigInteger(const BigUnsigned &, Sign): Invali
d sign"; | 68 throw "BigInteger::BigInteger(const BigUnsigned &, Sign): Invali
d sign"; |
| 69 #endif |
| 48 } | 70 } |
| 49 } | 71 } |
| 50 | 72 |
| 51 /* CONSTRUCTION FROM PRIMITIVE INTEGERS | 73 /* CONSTRUCTION FROM PRIMITIVE INTEGERS |
| 52 * Same idea as in BigUnsigned.cc, except that negative input results in a | 74 * Same idea as in BigUnsigned.cc, except that negative input results in a |
| 53 * negative BigInteger instead of an exception. */ | 75 * negative BigInteger instead of an exception. */ |
| 54 | 76 |
| 55 // Done longhand to let us use initialization. | 77 // Done longhand to let us use initialization. |
| 56 BigInteger::BigInteger(unsigned long x) : mag(x) { sign = mag.isZero() ? zero :
positive; } | 78 BigInteger::BigInteger(unsigned long x) : mag(x) { sign = mag.isZero() ? zero :
positive; } |
| 57 BigInteger::BigInteger(unsigned int x) : mag(x) { sign = mag.isZero() ? zero :
positive; } | 79 BigInteger::BigInteger(unsigned int x) : mag(x) { sign = mag.isZero() ? zero :
positive; } |
| (...skipping 27 matching lines...) Expand all Loading... |
| 85 * BigInteger::convertToUnsignedPrimitive to avoid requiring BigUnsigned to | 107 * BigInteger::convertToUnsignedPrimitive to avoid requiring BigUnsigned to |
| 86 * declare BigInteger. */ | 108 * declare BigInteger. */ |
| 87 template <class X> | 109 template <class X> |
| 88 inline X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a) { | 110 inline X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a) { |
| 89 return a.convertToPrimitive<X>(); | 111 return a.convertToPrimitive<X>(); |
| 90 } | 112 } |
| 91 | 113 |
| 92 template <class X> | 114 template <class X> |
| 93 X BigInteger::convertToUnsignedPrimitive() const { | 115 X BigInteger::convertToUnsignedPrimitive() const { |
| 94 if (sign == negative) | 116 if (sign == negative) |
| 117 #ifdef FOXIT_CHROME_BUILD |
| 118 abort(); |
| 119 #else |
| 95 throw "BigInteger::to<Primitive>: " | 120 throw "BigInteger::to<Primitive>: " |
| 96 "Cannot convert a negative integer to an unsigned type"; | 121 "Cannot convert a negative integer to an unsigned type"; |
| 122 #endif |
| 97 else | 123 else |
| 98 return convertBigUnsignedToPrimitiveAccess<X>(mag); | 124 return convertBigUnsignedToPrimitiveAccess<X>(mag); |
| 99 } | 125 } |
| 100 | 126 |
| 101 /* Similar to BigUnsigned::convertToPrimitive, but split into two cases for | 127 /* Similar to BigUnsigned::convertToPrimitive, but split into two cases for |
| 102 * nonnegative and negative numbers. */ | 128 * nonnegative and negative numbers. */ |
| 103 template <class X, class UX> | 129 template <class X, class UX> |
| 104 X BigInteger::convertToSignedPrimitive() const { | 130 X BigInteger::convertToSignedPrimitive() const { |
| 105 if (sign == zero) | 131 if (sign == zero) |
| 106 return 0; | 132 return 0; |
| 107 else if (mag.getLength() == 1) { | 133 else if (mag.getLength() == 1) { |
| 108 // The single block might fit in an X. Try the conversion. | 134 // The single block might fit in an X. Try the conversion. |
| 109 Blk b = mag.getBlock(0); | 135 Blk b = mag.getBlock(0); |
| 110 if (sign == positive) { | 136 if (sign == positive) { |
| 111 X x = X(b); | 137 X x = X(b); |
| 112 if (x >= 0 && Blk(x) == b) | 138 if (x >= 0 && Blk(x) == b) |
| 113 return x; | 139 return x; |
| 114 } else { | 140 } else { |
| 115 X x = -X(b); | 141 X x = -X(b); |
| 116 /* UX(...) needed to avoid rejecting conversion of | 142 /* UX(...) needed to avoid rejecting conversion of |
| 117 * -2^15 to a short. */ | 143 * -2^15 to a short. */ |
| 118 if (x < 0 && Blk(UX(-x)) == b) | 144 if (x < 0 && Blk(UX(-x)) == b) |
| 119 return x; | 145 return x; |
| 120 } | 146 } |
| 121 // Otherwise fall through. | 147 // Otherwise fall through. |
| 122 } | 148 } |
| 149 #ifdef FOXIT_CHROME_BUILD |
| 150 abort(); |
| 151 #else |
| 123 throw "BigInteger::to<Primitive>: " | 152 throw "BigInteger::to<Primitive>: " |
| 124 "Value is too big to fit in the requested type"; | 153 "Value is too big to fit in the requested type"; |
| 154 #endif |
| 125 } | 155 } |
| 126 | 156 |
| 127 unsigned long BigInteger::toUnsignedLong () const { return convertToUnsignedPri
mitive<unsigned long > (); } | 157 unsigned long BigInteger::toUnsignedLong () const { return convertToUnsignedPri
mitive<unsigned long > (); } |
| 128 unsigned int BigInteger::toUnsignedInt () const { return convertToUnsignedPri
mitive<unsigned int > (); } | 158 unsigned int BigInteger::toUnsignedInt () const { return convertToUnsignedPri
mitive<unsigned int > (); } |
| 129 unsigned short BigInteger::toUnsignedShort() const { return convertToUnsignedPri
mitive<unsigned short> (); } | 159 unsigned short BigInteger::toUnsignedShort() const { return convertToUnsignedPri
mitive<unsigned short> (); } |
| 130 long BigInteger::toLong () const { return convertToSignedPrimi
tive <long , unsigned long> (); } | 160 long BigInteger::toLong () const { return convertToSignedPrimi
tive <long , unsigned long> (); } |
| 131 int BigInteger::toInt () const { return convertToSignedPrimi
tive <int , unsigned int> (); } | 161 int BigInteger::toInt () const { return convertToSignedPrimi
tive <int , unsigned int> (); } |
| 132 short BigInteger::toShort () const { return convertToSignedPrimi
tive <short, unsigned short>(); } | 162 short BigInteger::toShort () const { return convertToSignedPrimi
tive <short, unsigned short>(); } |
| 133 | 163 |
| 134 // COMPARISON | 164 // COMPARISON |
| 135 BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const { | 165 BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const { |
| 136 // A greater sign implies a greater number | 166 // A greater sign implies a greater number |
| 137 if (sign < x.sign) | 167 if (sign < x.sign) |
| 138 return less; | 168 return less; |
| 139 else if (sign > x.sign) | 169 else if (sign > x.sign) |
| 140 return greater; | 170 return greater; |
| 141 else switch (sign) { | 171 else switch (sign) { |
| 142 // If the signs are the same... | 172 // If the signs are the same... |
| 143 case zero: | 173 case zero: |
| 144 return equal; // Two zeros are equal | 174 return equal; // Two zeros are equal |
| 145 case positive: | 175 case positive: |
| 146 // Compare the magnitudes | 176 // Compare the magnitudes |
| 147 return mag.compareTo(x.mag); | 177 return mag.compareTo(x.mag); |
| 148 case negative: | 178 case negative: |
| 149 // Compare the magnitudes, but return the opposite result | 179 // Compare the magnitudes, but return the opposite result |
| 150 return CmpRes(-mag.compareTo(x.mag)); | 180 return CmpRes(-mag.compareTo(x.mag)); |
| 151 default: | 181 default: |
| 182 #ifdef FOXIT_CHROME_BUILD |
| 183 abort(); |
| 184 #else |
| 152 throw "BigInteger internal error"; | 185 throw "BigInteger internal error"; |
| 186 #endif |
| 153 } | 187 } |
| 154 } | 188 } |
| 155 | 189 |
| 156 /* COPY-LESS OPERATIONS | 190 /* COPY-LESS OPERATIONS |
| 157 * These do some messing around to determine the sign of the result, | 191 * These do some messing around to determine the sign of the result, |
| 158 * then call one of BigUnsigned's copy-less operations. */ | 192 * then call one of BigUnsigned's copy-less operations. */ |
| 159 | 193 |
| 160 // See remarks about aliased calls in BigUnsigned.cc . | 194 // See remarks about aliased calls in BigUnsigned.cc . |
| 161 #define DTRT_ALIASED(cond, op) \ | 195 #define DTRT_ALIASED(cond, op) \ |
| 162 if (cond) { \ | 196 if (cond) { \ |
| (...skipping 111 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 274 * === === === === | 308 * === === === === |
| 275 * 4 3 1 1 | 309 * 4 3 1 1 |
| 276 * -4 3 -2 2 | 310 * -4 3 -2 2 |
| 277 * 4 -3 -2 -2 | 311 * 4 -3 -2 -2 |
| 278 * -4 -3 1 -1 | 312 * -4 -3 1 -1 |
| 279 */ | 313 */ |
| 280 void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { | 314 void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { |
| 281 // Defend against aliased calls; | 315 // Defend against aliased calls; |
| 282 // same idea as in BigUnsigned::divideWithRemainder . | 316 // same idea as in BigUnsigned::divideWithRemainder . |
| 283 if (this == &q) | 317 if (this == &q) |
| 318 #ifdef FOXIT_CHROME_BUILD |
| 319 abort(); |
| 320 #else |
| 284 throw "BigInteger::divideWithRemainder: Cannot write quotient an
d remainder into the same variable"; | 321 throw "BigInteger::divideWithRemainder: Cannot write quotient an
d remainder into the same variable"; |
| 322 #endif |
| 285 if (this == &b || &q == &b) { | 323 if (this == &b || &q == &b) { |
| 286 BigInteger tmpB(b); | 324 BigInteger tmpB(b); |
| 287 divideWithRemainder(tmpB, q); | 325 divideWithRemainder(tmpB, q); |
| 288 return; | 326 return; |
| 289 } | 327 } |
| 290 | 328 |
| 291 // Division by zero gives quotient 0 and remainder *this | 329 // Division by zero gives quotient 0 and remainder *this |
| 292 if (b.sign == zero) { | 330 if (b.sign == zero) { |
| 293 q.mag = 0; | 331 q.mag = 0; |
| 294 q.sign = zero; | 332 q.sign = zero; |
| (...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 396 mag++; | 434 mag++; |
| 397 sign = negative; | 435 sign = negative; |
| 398 } | 436 } |
| 399 } | 437 } |
| 400 | 438 |
| 401 // Postfix decrement: same as prefix | 439 // Postfix decrement: same as prefix |
| 402 void BigInteger::operator --(int) { | 440 void BigInteger::operator --(int) { |
| 403 operator --(); | 441 operator --(); |
| 404 } | 442 } |
| 405 | 443 |
| OLD | NEW |