Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(74)

Side by Side Diff: third_party/bigint/BigInteger.cc

Issue 754743003: Modify big integer library (Closed) Base URL: https://pdfium.googlesource.com/pdfium.git@master
Patch Set: Add copyright notice Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
OLDNEW
« no previous file with comments | « pdfium.gyp ('k') | third_party/bigint/BigInteger.hh » ('j') | third_party/bigint/BigUnsigned.hh » ('J')

Powered by Google App Engine
This is Rietveld 408576698