| 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 "BigUnsigned.hh" | 7 #include "BigUnsigned.hh" |
| 8 | 8 |
| 9 // Memory management definitions have moved to the bottom of NumberlikeArray.hh. | 9 // Memory management definitions have moved to the bottom of NumberlikeArray.hh. |
| 10 | 10 |
| (...skipping 177 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 188 } | 188 } |
| 189 | 189 |
| 190 void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { | 190 void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { |
| 191 DTRT_ALIASED(this == &a || this == &b, subtract(a, b)); | 191 DTRT_ALIASED(this == &a || this == &b, subtract(a, b)); |
| 192 if (b.len == 0) { | 192 if (b.len == 0) { |
| 193 // If b is zero, copy a. | 193 // If b is zero, copy a. |
| 194 operator =(a); | 194 operator =(a); |
| 195 return; | 195 return; |
| 196 } else if (a.len < b.len) | 196 } else if (a.len < b.len) |
| 197 // If a is shorter than b, the result is negative. | 197 // If a is shorter than b, the result is negative. |
| 198 #ifdef FOXIT_CHROME_BUILD | |
| 199 abort(); | 198 abort(); |
| 200 #else | |
| 201 throw "BigUnsigned::subtract: " | |
| 202 "Negative result in unsigned calculation"; | |
| 203 #endif | |
| 204 // Some variables... | 199 // Some variables... |
| 205 bool borrowIn, borrowOut; | 200 bool borrowIn, borrowOut; |
| 206 Blk temp; | 201 Blk temp; |
| 207 Index i; | 202 Index i; |
| 208 // Set preliminary length and make room | 203 // Set preliminary length and make room |
| 209 len = a.len; | 204 len = a.len; |
| 210 allocate(len); | 205 allocate(len); |
| 211 // For each block index that is present in both inputs... | 206 // For each block index that is present in both inputs... |
| 212 for (i = 0, borrowIn = false; i < b.len; i++) { | 207 for (i = 0, borrowIn = false; i < b.len; i++) { |
| 213 temp = a.blk[i] - b.blk[i]; | 208 temp = a.blk[i] - b.blk[i]; |
| (...skipping 12 matching lines...) Expand all Loading... |
| 226 // one does not reverse rollover. | 221 // one does not reverse rollover. |
| 227 for (; i < a.len && borrowIn; i++) { | 222 for (; i < a.len && borrowIn; i++) { |
| 228 borrowIn = (a.blk[i] == 0); | 223 borrowIn = (a.blk[i] == 0); |
| 229 blk[i] = a.blk[i] - 1; | 224 blk[i] = a.blk[i] - 1; |
| 230 } | 225 } |
| 231 /* If there's still a borrow, the result is negative. | 226 /* If there's still a borrow, the result is negative. |
| 232 * Throw an exception, but zero out this object so as to leave it in a | 227 * Throw an exception, but zero out this object so as to leave it in a |
| 233 * predictable state. */ | 228 * predictable state. */ |
| 234 if (borrowIn) { | 229 if (borrowIn) { |
| 235 len = 0; | 230 len = 0; |
| 236 #ifdef FOXIT_CHROME_BUILD | |
| 237 abort(); | 231 abort(); |
| 238 #else | |
| 239 throw "BigUnsigned::subtract: Negative result in unsigned calcul
ation"; | |
| 240 #endif | |
| 241 } else | 232 } else |
| 242 // Copy over the rest of the blocks | 233 // Copy over the rest of the blocks |
| 243 for (; i < a.len; i++) | 234 for (; i < a.len; i++) |
| 244 blk[i] = a.blk[i]; | 235 blk[i] = a.blk[i]; |
| 245 // Zap leading zeros | 236 // Zap leading zeros |
| 246 zapLeadingZeros(); | 237 zapLeadingZeros(); |
| 247 } | 238 } |
| 248 | 239 |
| 249 /* | 240 /* |
| 250 * About the multiplication and division algorithms: | 241 * About the multiplication and division algorithms: |
| (...skipping 142 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 393 * "modWithQuotient" might be a better name for this function, but I would | 384 * "modWithQuotient" might be a better name for this function, but I would |
| 394 * rather not change the name now. | 385 * rather not change the name now. |
| 395 */ | 386 */ |
| 396 void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { | 387 void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { |
| 397 /* Defending against aliased calls is more complex than usual because we | 388 /* Defending against aliased calls is more complex than usual because we |
| 398 * are writing to both *this and q. | 389 * are writing to both *this and q. |
| 399 * | 390 * |
| 400 * It would be silly to try to write quotient and remainder to the | 391 * It would be silly to try to write quotient and remainder to the |
| 401 * same variable. Rule that out right away. */ | 392 * same variable. Rule that out right away. */ |
| 402 if (this == &q) | 393 if (this == &q) |
| 403 #ifdef FOXIT_CHROME_BUILD | |
| 404 abort(); | 394 abort(); |
| 405 #else | |
| 406 throw "BigUnsigned::divideWithRemainder: Cannot write quotient a
nd remainder into the same variable"; | |
| 407 #endif | |
| 408 /* Now *this and q are separate, so the only concern is that b might be | 395 /* Now *this and q are separate, so the only concern is that b might be |
| 409 * aliased to one of them. If so, use a temporary copy of b. */ | 396 * aliased to one of them. If so, use a temporary copy of b. */ |
| 410 if (this == &b || &q == &b) { | 397 if (this == &b || &q == &b) { |
| 411 BigUnsigned tmpB(b); | 398 BigUnsigned tmpB(b); |
| 412 divideWithRemainder(tmpB, q); | 399 divideWithRemainder(tmpB, q); |
| 413 return; | 400 return; |
| 414 } | 401 } |
| 415 | 402 |
| 416 /* | 403 /* |
| 417 * Knuth's definition of mod (which this function uses) is somewhat | 404 * Knuth's definition of mod (which this function uses) is somewhat |
| (...skipping 189 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 607 for (; i < a2->len; i++) | 594 for (; i < a2->len; i++) |
| 608 blk[i] = a2->blk[i]; | 595 blk[i] = a2->blk[i]; |
| 609 len = a2->len; | 596 len = a2->len; |
| 610 zapLeadingZeros(); | 597 zapLeadingZeros(); |
| 611 } | 598 } |
| 612 | 599 |
| 613 void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) { | 600 void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) { |
| 614 DTRT_ALIASED(this == &a, bitShiftLeft(a, b)); | 601 DTRT_ALIASED(this == &a, bitShiftLeft(a, b)); |
| 615 if (b < 0) { | 602 if (b < 0) { |
| 616 if (b << 1 == 0) | 603 if (b << 1 == 0) |
| 617 #ifdef FOXIT_CHROME_BUILD | |
| 618 abort(); | 604 abort(); |
| 619 #else | |
| 620 throw "BigUnsigned::bitShiftLeft: " | |
| 621 "Pathological shift amount not implemented"; | |
| 622 #endif | |
| 623 else { | 605 else { |
| 624 bitShiftRight(a, -b); | 606 bitShiftRight(a, -b); |
| 625 return; | 607 return; |
| 626 } | 608 } |
| 627 } | 609 } |
| 628 Index shiftBlocks = b / N; | 610 Index shiftBlocks = b / N; |
| 629 unsigned int shiftBits = b % N; | 611 unsigned int shiftBits = b % N; |
| 630 // + 1: room for high bits nudged left into another block | 612 // + 1: room for high bits nudged left into another block |
| 631 len = a.len + shiftBlocks + 1; | 613 len = a.len + shiftBlocks + 1; |
| 632 allocate(len); | 614 allocate(len); |
| 633 Index i, j; | 615 Index i, j; |
| 634 for (i = 0; i < shiftBlocks; i++) | 616 for (i = 0; i < shiftBlocks; i++) |
| 635 blk[i] = 0; | 617 blk[i] = 0; |
| 636 for (j = 0, i = shiftBlocks; j <= a.len; j++, i++) | 618 for (j = 0, i = shiftBlocks; j <= a.len; j++, i++) |
| 637 blk[i] = getShiftedBlock(a, j, shiftBits); | 619 blk[i] = getShiftedBlock(a, j, shiftBits); |
| 638 // Zap possible leading zero | 620 // Zap possible leading zero |
| 639 if (blk[len - 1] == 0) | 621 if (blk[len - 1] == 0) |
| 640 len--; | 622 len--; |
| 641 } | 623 } |
| 642 | 624 |
| 643 void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) { | 625 void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) { |
| 644 DTRT_ALIASED(this == &a, bitShiftRight(a, b)); | 626 DTRT_ALIASED(this == &a, bitShiftRight(a, b)); |
| 645 if (b < 0) { | 627 if (b < 0) { |
| 646 if (b << 1 == 0) | 628 if (b << 1 == 0) |
| 647 #ifdef FOXIT_CHROME_BUILD | |
| 648 abort(); | 629 abort(); |
| 649 #else | |
| 650 throw "BigUnsigned::bitShiftRight: " | |
| 651 "Pathological shift amount not implemented"; | |
| 652 #endif | |
| 653 else { | 630 else { |
| 654 bitShiftLeft(a, -b); | 631 bitShiftLeft(a, -b); |
| 655 return; | 632 return; |
| 656 } | 633 } |
| 657 } | 634 } |
| 658 // This calculation is wacky, but expressing the shift as a left bit shi
ft | 635 // This calculation is wacky, but expressing the shift as a left bit shi
ft |
| 659 // within each block lets us use getShiftedBlock. | 636 // within each block lets us use getShiftedBlock. |
| 660 Index rightShiftBlocks = (b + N - 1) / N; | 637 Index rightShiftBlocks = (b + N - 1) / N; |
| 661 unsigned int leftShiftBits = N * rightShiftBlocks - b; | 638 unsigned int leftShiftBits = N * rightShiftBlocks - b; |
| 662 // Now (N * rightShiftBlocks - leftShiftBits) == b | 639 // Now (N * rightShiftBlocks - leftShiftBits) == b |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 698 } | 675 } |
| 699 | 676 |
| 700 // Postfix increment: same as prefix | 677 // Postfix increment: same as prefix |
| 701 void BigUnsigned::operator ++(int) { | 678 void BigUnsigned::operator ++(int) { |
| 702 operator ++(); | 679 operator ++(); |
| 703 } | 680 } |
| 704 | 681 |
| 705 // Prefix decrement | 682 // Prefix decrement |
| 706 void BigUnsigned::operator --() { | 683 void BigUnsigned::operator --() { |
| 707 if (len == 0) | 684 if (len == 0) |
| 708 #ifdef FOXIT_CHROME_BUILD | |
| 709 abort(); | 685 abort(); |
| 710 #else | |
| 711 throw "BigUnsigned::operator --(): Cannot decrement an unsigned
zero"; | |
| 712 #endif | |
| 713 Index i; | 686 Index i; |
| 714 bool borrow = true; | 687 bool borrow = true; |
| 715 for (i = 0; borrow; i++) { | 688 for (i = 0; borrow; i++) { |
| 716 borrow = (blk[i] == 0); | 689 borrow = (blk[i] == 0); |
| 717 blk[i]--; | 690 blk[i]--; |
| 718 } | 691 } |
| 719 // Zap possible leading zero (there can only be one) | 692 // Zap possible leading zero (there can only be one) |
| 720 if (blk[len - 1] == 0) | 693 if (blk[len - 1] == 0) |
| 721 len--; | 694 len--; |
| 722 } | 695 } |
| 723 | 696 |
| 724 // Postfix decrement: same as prefix | 697 // Postfix decrement: same as prefix |
| 725 void BigUnsigned::operator --(int) { | 698 void BigUnsigned::operator --(int) { |
| 726 operator --(); | 699 operator --(); |
| 727 } | 700 } |
| OLD | NEW |