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 |