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 #ifndef BIGUNSIGNED_H | 7 #ifndef BIGUNSIGNED_H |
2 #define BIGUNSIGNED_H | 8 #define BIGUNSIGNED_H |
3 | 9 |
4 #include "NumberlikeArray.hh" | 10 #include "NumberlikeArray.hh" |
5 | 11 |
6 /* A BigUnsigned object represents a nonnegative integer of size limited only by | 12 /* A BigUnsigned object represents a nonnegative integer of size limited only by |
7 * available memory. BigUnsigneds support most mathematical operators and can | 13 * available memory. BigUnsigneds support most mathematical operators and can |
8 * be converted to and from most primitive integer types. | 14 * be converted to and from most primitive integer types. |
9 * | 15 * |
10 * The number is stored as a NumberlikeArray of unsigned longs as if it were | 16 * The number is stored as a NumberlikeArray of unsigned longs as if it were |
11 * written in base 256^sizeof(unsigned long). The least significant block is | 17 * written in base 256^sizeof(unsigned long). The least significant block is |
12 * first, and the length is such that the most significant block is nonzero. */ | 18 * first, and the length is such that the most significant block is nonzero. */ |
13 class BigUnsigned : protected NumberlikeArray<unsigned long> { | 19 class BigUnsigned : protected NumberlikeArray<unsigned long> { |
14 | 20 |
15 public: | 21 public: |
16 // Enumeration for the result of a comparison. | 22 // Enumeration for the result of a comparison. |
17 enum CmpRes { less = -1, equal = 0, greater = 1 }; | 23 enum CmpRes { less = -1, equal = 0, greater = 1 }; |
18 | 24 |
19 // BigUnsigneds are built with a Blk type of unsigned long. | 25 // BigUnsigneds are built with a Blk type of unsigned long. |
20 typedef unsigned long Blk; | 26 typedef unsigned long Blk; |
21 | 27 |
22 typedef NumberlikeArray<Blk>::Index Index; | 28 typedef NumberlikeArray<Blk>::Index Index; |
23 » NumberlikeArray<Blk>::N; | 29 » using NumberlikeArray<Blk>::N; |
24 | 30 |
25 protected: | 31 protected: |
26 // Creates a BigUnsigned with a capacity; for internal use. | 32 // Creates a BigUnsigned with a capacity; for internal use. |
27 BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {} | 33 BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {} |
28 | 34 |
29 // Decreases len to eliminate any leading zero blocks. | 35 // Decreases len to eliminate any leading zero blocks. |
30 void zapLeadingZeros() { | 36 void zapLeadingZeros() { |
31 while (len > 0 && blk[len - 1] == 0) | 37 while (len > 0 && blk[len - 1] == 0) |
32 len--; | 38 len--; |
33 } | 39 } |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
77 short toShort () const; | 83 short toShort () const; |
78 protected: | 84 protected: |
79 // Helpers | 85 // Helpers |
80 template <class X> X convertToSignedPrimitive() const; | 86 template <class X> X convertToSignedPrimitive() const; |
81 template <class X> X convertToPrimitive () const; | 87 template <class X> X convertToPrimitive () const; |
82 public: | 88 public: |
83 | 89 |
84 // BIT/BLOCK ACCESSORS | 90 // BIT/BLOCK ACCESSORS |
85 | 91 |
86 // Expose these from NumberlikeArray directly. | 92 // Expose these from NumberlikeArray directly. |
87 » NumberlikeArray<Blk>::getCapacity; | 93 » using NumberlikeArray<Blk>::getCapacity; |
Tom Sepez
2014/12/03 00:14:19
Why do we need to do this?
Bo Xu
2014/12/03 00:31:22
Otherwise the C++11 compiler complains:"ISO C+11 d
| |
88 » NumberlikeArray<Blk>::getLength; | 94 » using NumberlikeArray<Blk>::getLength; |
89 | 95 |
90 /* Returns the requested block, or 0 if it is beyond the length (as if | 96 /* Returns the requested block, or 0 if it is beyond the length (as if |
91 * the number had 0s infinitely to the left). */ | 97 * the number had 0s infinitely to the left). */ |
92 Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; } | 98 Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; } |
93 /* Sets the requested block. The number grows or shrinks as necessary. */ | 99 /* Sets the requested block. The number grows or shrinks as necessary. */ |
94 void setBlock(Index i, Blk newBlock); | 100 void setBlock(Index i, Blk newBlock); |
95 | 101 |
96 // The number is zero if and only if the canonical length is zero. | 102 // The number is zero if and only if the canonical length is zero. |
97 bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } | 103 bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } |
98 | 104 |
(...skipping 154 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
253 BigUnsigned ans; | 259 BigUnsigned ans; |
254 ans.subtract(*this, x); | 260 ans.subtract(*this, x); |
255 return ans; | 261 return ans; |
256 } | 262 } |
257 inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { | 263 inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { |
258 BigUnsigned ans; | 264 BigUnsigned ans; |
259 ans.multiply(*this, x); | 265 ans.multiply(*this, x); |
260 return ans; | 266 return ans; |
261 } | 267 } |
262 inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { | 268 inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { |
263 » if (x.isZero()) throw "BigUnsigned::operator /: division by zero"; | 269 » if (x.isZero()) |
270 #ifdef FOXIT_CHROME_BUILD | |
271 abort(); | |
272 #else | |
273 throw "BigUnsigned::operator /: division by zero"; | |
274 #endif | |
264 BigUnsigned q, r; | 275 BigUnsigned q, r; |
265 r = *this; | 276 r = *this; |
266 r.divideWithRemainder(x, q); | 277 r.divideWithRemainder(x, q); |
267 return q; | 278 return q; |
268 } | 279 } |
269 inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { | 280 inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { |
270 » if (x.isZero()) throw "BigUnsigned::operator %: division by zero"; | 281 » if (x.isZero()) |
282 #ifdef FOXIT_CHROME_BUILD | |
283 abort(); | |
284 #else | |
285 throw "BigUnsigned::operator %: division by zero"; | |
286 #endif | |
271 BigUnsigned q, r; | 287 BigUnsigned q, r; |
272 r = *this; | 288 r = *this; |
273 r.divideWithRemainder(x, q); | 289 r.divideWithRemainder(x, q); |
274 return r; | 290 return r; |
275 } | 291 } |
276 inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const { | 292 inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const { |
277 BigUnsigned ans; | 293 BigUnsigned ans; |
278 ans.bitAnd(*this, x); | 294 ans.bitAnd(*this, x); |
279 return ans; | 295 return ans; |
280 } | 296 } |
(...skipping 21 matching lines...) Expand all Loading... | |
302 inline void BigUnsigned::operator +=(const BigUnsigned &x) { | 318 inline void BigUnsigned::operator +=(const BigUnsigned &x) { |
303 add(*this, x); | 319 add(*this, x); |
304 } | 320 } |
305 inline void BigUnsigned::operator -=(const BigUnsigned &x) { | 321 inline void BigUnsigned::operator -=(const BigUnsigned &x) { |
306 subtract(*this, x); | 322 subtract(*this, x); |
307 } | 323 } |
308 inline void BigUnsigned::operator *=(const BigUnsigned &x) { | 324 inline void BigUnsigned::operator *=(const BigUnsigned &x) { |
309 multiply(*this, x); | 325 multiply(*this, x); |
310 } | 326 } |
311 inline void BigUnsigned::operator /=(const BigUnsigned &x) { | 327 inline void BigUnsigned::operator /=(const BigUnsigned &x) { |
312 » if (x.isZero()) throw "BigUnsigned::operator /=: division by zero"; | 328 » if (x.isZero()) |
329 #ifdef FOXIT_CHROME_BUILD | |
330 abort(); | |
331 #else | |
332 throw "BigUnsigned::operator /=: division by zero"; | |
333 #endif | |
313 /* The following technique is slightly faster than copying *this first | 334 /* The following technique is slightly faster than copying *this first |
314 * when x is large. */ | 335 * when x is large. */ |
315 BigUnsigned q; | 336 BigUnsigned q; |
316 divideWithRemainder(x, q); | 337 divideWithRemainder(x, q); |
317 // *this contains the remainder, but we overwrite it with the quotient. | 338 // *this contains the remainder, but we overwrite it with the quotient. |
318 *this = q; | 339 *this = q; |
319 } | 340 } |
320 inline void BigUnsigned::operator %=(const BigUnsigned &x) { | 341 inline void BigUnsigned::operator %=(const BigUnsigned &x) { |
321 » if (x.isZero()) throw "BigUnsigned::operator %=: division by zero"; | 342 » if (x.isZero()) |
343 #ifdef FOXIT_CHROME_BUILD | |
344 abort(); | |
345 #else | |
346 throw "BigUnsigned::operator %=: division by zero"; | |
347 #endif | |
322 BigUnsigned q; | 348 BigUnsigned q; |
323 // Mods *this by x. Don't care about quotient left in q. | 349 // Mods *this by x. Don't care about quotient left in q. |
324 divideWithRemainder(x, q); | 350 divideWithRemainder(x, q); |
325 } | 351 } |
326 inline void BigUnsigned::operator &=(const BigUnsigned &x) { | 352 inline void BigUnsigned::operator &=(const BigUnsigned &x) { |
327 bitAnd(*this, x); | 353 bitAnd(*this, x); |
328 } | 354 } |
329 inline void BigUnsigned::operator |=(const BigUnsigned &x) { | 355 inline void BigUnsigned::operator |=(const BigUnsigned &x) { |
330 bitOr(*this, x); | 356 bitOr(*this, x); |
331 } | 357 } |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
365 } | 391 } |
366 } | 392 } |
367 | 393 |
368 /* Ditto, but first check that x is nonnegative. I could have put the check in | 394 /* Ditto, but first check that x is nonnegative. I could have put the check in |
369 * initFromPrimitive and let the compiler optimize it out for unsigned-type | 395 * initFromPrimitive and let the compiler optimize it out for unsigned-type |
370 * instantiations, but I wanted to avoid the warning stupidly issued by g++ for | 396 * instantiations, but I wanted to avoid the warning stupidly issued by g++ for |
371 * a condition that is constant in *any* instantiation, even if not in all. */ | 397 * a condition that is constant in *any* instantiation, even if not in all. */ |
372 template <class X> | 398 template <class X> |
373 void BigUnsigned::initFromSignedPrimitive(X x) { | 399 void BigUnsigned::initFromSignedPrimitive(X x) { |
374 if (x < 0) | 400 if (x < 0) |
401 #ifdef FOXIT_CHROME_BUILD | |
402 abort(); | |
403 #else | |
375 throw "BigUnsigned constructor: " | 404 throw "BigUnsigned constructor: " |
376 "Cannot construct a BigUnsigned from a negative number"; | 405 "Cannot construct a BigUnsigned from a negative number"; |
406 #endif | |
377 else | 407 else |
378 initFromPrimitive(x); | 408 initFromPrimitive(x); |
379 } | 409 } |
380 | 410 |
381 // CONVERSION TO PRIMITIVE INTEGERS | 411 // CONVERSION TO PRIMITIVE INTEGERS |
382 | 412 |
383 /* Template with the same idea as initFromPrimitive. This might be slightly | 413 /* Template with the same idea as initFromPrimitive. This might be slightly |
384 * slower than the previous version with the masks, but it's much shorter and | 414 * slower than the previous version with the masks, but it's much shorter and |
385 * clearer, which is the library's stated goal. */ | 415 * clearer, which is the library's stated goal. */ |
386 template <class X> | 416 template <class X> |
387 X BigUnsigned::convertToPrimitive() const { | 417 X BigUnsigned::convertToPrimitive() const { |
388 if (len == 0) | 418 if (len == 0) |
389 // The number is zero; return zero. | 419 // The number is zero; return zero. |
390 return 0; | 420 return 0; |
391 else if (len == 1) { | 421 else if (len == 1) { |
392 // The single block might fit in an X. Try the conversion. | 422 // The single block might fit in an X. Try the conversion. |
393 X x = X(blk[0]); | 423 X x = X(blk[0]); |
394 // Make sure the result accurately represents the block. | 424 // Make sure the result accurately represents the block. |
395 if (Blk(x) == blk[0]) | 425 if (Blk(x) == blk[0]) |
396 // Successful conversion. | 426 // Successful conversion. |
397 return x; | 427 return x; |
398 // Otherwise fall through. | 428 // Otherwise fall through. |
399 } | 429 } |
430 #ifdef FOXIT_CHROME_BUILD | |
431 abort(); | |
432 #else | |
400 throw "BigUnsigned::to<Primitive>: " | 433 throw "BigUnsigned::to<Primitive>: " |
401 "Value is too big to fit in the requested type"; | 434 "Value is too big to fit in the requested type"; |
435 #endif | |
402 } | 436 } |
403 | 437 |
404 /* Wrap the above in an x >= 0 test to make sure we got a nonnegative result, | 438 /* Wrap the above in an x >= 0 test to make sure we got a nonnegative result, |
405 * not a negative one that happened to convert back into the correct nonnegative | 439 * not a negative one that happened to convert back into the correct nonnegative |
406 * one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again, | 440 * one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again, |
407 * separated to avoid a g++ warning. */ | 441 * separated to avoid a g++ warning. */ |
408 template <class X> | 442 template <class X> |
409 X BigUnsigned::convertToSignedPrimitive() const { | 443 X BigUnsigned::convertToSignedPrimitive() const { |
410 X x = convertToPrimitive<X>(); | 444 X x = convertToPrimitive<X>(); |
411 if (x >= 0) | 445 if (x >= 0) |
412 return x; | 446 return x; |
413 else | 447 else |
448 #ifdef FOXIT_CHROME_BUILD | |
449 abort(); | |
450 #else | |
414 throw "BigUnsigned::to(Primitive): " | 451 throw "BigUnsigned::to(Primitive): " |
415 "Value is too big to fit in the requested type"; | 452 "Value is too big to fit in the requested type"; |
453 #endif | |
416 } | 454 } |
417 | 455 |
418 #endif | 456 #endif |
OLD | NEW |