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