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 | |
Tom Sepez
2014/12/03 00:14:19
nit: . at end of sentence.
| |
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 |