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

Side by Side Diff: third_party/bigint/BigUnsigned.hh

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
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698