Chromium Code Reviews| 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 |