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 |