| OLD | NEW |
| 1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 163 | 163 |
| 164 void Bignum::AddUInt64(uint64_t operand) { | 164 void Bignum::AddUInt64(uint64_t operand) { |
| 165 if (operand == 0) return; | 165 if (operand == 0) return; |
| 166 Bignum other; | 166 Bignum other; |
| 167 other.AssignUInt64(operand); | 167 other.AssignUInt64(operand); |
| 168 AddBignum(other); | 168 AddBignum(other); |
| 169 } | 169 } |
| 170 | 170 |
| 171 | 171 |
| 172 void Bignum::AddBignum(const Bignum& other) { | 172 void Bignum::AddBignum(const Bignum& other) { |
| 173 ASSERT(IsClamped()); | 173 DCHECK(IsClamped()); |
| 174 ASSERT(other.IsClamped()); | 174 DCHECK(other.IsClamped()); |
| 175 | 175 |
| 176 // If this has a greater exponent than other append zero-bigits to this. | 176 // If this has a greater exponent than other append zero-bigits to this. |
| 177 // After this call exponent_ <= other.exponent_. | 177 // After this call exponent_ <= other.exponent_. |
| 178 Align(other); | 178 Align(other); |
| 179 | 179 |
| 180 // There are two possibilities: | 180 // There are two possibilities: |
| 181 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) | 181 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) |
| 182 // bbbbb 00000000 | 182 // bbbbb 00000000 |
| 183 // ---------------- | 183 // ---------------- |
| 184 // ccccccccccc 0000 | 184 // ccccccccccc 0000 |
| 185 // or | 185 // or |
| 186 // aaaaaaaaaa 0000 | 186 // aaaaaaaaaa 0000 |
| 187 // bbbbbbbbb 0000000 | 187 // bbbbbbbbb 0000000 |
| 188 // ----------------- | 188 // ----------------- |
| 189 // cccccccccccc 0000 | 189 // cccccccccccc 0000 |
| 190 // In both cases we might need a carry bigit. | 190 // In both cases we might need a carry bigit. |
| 191 | 191 |
| 192 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); | 192 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); |
| 193 Chunk carry = 0; | 193 Chunk carry = 0; |
| 194 int bigit_pos = other.exponent_ - exponent_; | 194 int bigit_pos = other.exponent_ - exponent_; |
| 195 ASSERT(bigit_pos >= 0); | 195 ASSERT(bigit_pos >= 0); |
| 196 for (int i = 0; i < other.used_digits_; ++i) { | 196 for (int i = 0; i < other.used_digits_; ++i) { |
| 197 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; | 197 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; |
| 198 bigits_[bigit_pos] = sum & kBigitMask; | 198 bigits_[bigit_pos] = sum & kBigitMask; |
| 199 carry = sum >> kBigitSize; | 199 carry = sum >> kBigitSize; |
| 200 bigit_pos++; | 200 bigit_pos++; |
| 201 } | 201 } |
| 202 | 202 |
| 203 while (carry != 0) { | 203 while (carry != 0) { |
| 204 Chunk sum = bigits_[bigit_pos] + carry; | 204 Chunk sum = bigits_[bigit_pos] + carry; |
| 205 bigits_[bigit_pos] = sum & kBigitMask; | 205 bigits_[bigit_pos] = sum & kBigitMask; |
| 206 carry = sum >> kBigitSize; | 206 carry = sum >> kBigitSize; |
| 207 bigit_pos++; | 207 bigit_pos++; |
| 208 } | 208 } |
| 209 used_digits_ = Max(bigit_pos, used_digits_); | 209 used_digits_ = Max(bigit_pos, used_digits_); |
| 210 ASSERT(IsClamped()); | 210 DCHECK(IsClamped()); |
| 211 } | 211 } |
| 212 | 212 |
| 213 | 213 |
| 214 void Bignum::SubtractBignum(const Bignum& other) { | 214 void Bignum::SubtractBignum(const Bignum& other) { |
| 215 ASSERT(IsClamped()); | 215 DCHECK(IsClamped()); |
| 216 ASSERT(other.IsClamped()); | 216 DCHECK(other.IsClamped()); |
| 217 // We require this to be bigger than other. | 217 // We require this to be bigger than other. |
| 218 ASSERT(LessEqual(other, *this)); | 218 ASSERT(LessEqual(other, *this)); |
| 219 | 219 |
| 220 Align(other); | 220 Align(other); |
| 221 | 221 |
| 222 int offset = other.exponent_ - exponent_; | 222 int offset = other.exponent_ - exponent_; |
| 223 Chunk borrow = 0; | 223 Chunk borrow = 0; |
| 224 int i; | 224 int i; |
| 225 for (i = 0; i < other.used_digits_; ++i) { | 225 for (i = 0; i < other.used_digits_; ++i) { |
| 226 ASSERT((borrow == 0) || (borrow == 1)); | 226 ASSERT((borrow == 0) || (borrow == 1)); |
| 227 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; | 227 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; |
| 228 bigits_[i + offset] = difference & kBigitMask; | 228 bigits_[i + offset] = difference & kBigitMask; |
| 229 borrow = difference >> (kChunkSize - 1); | 229 borrow = difference >> (kChunkSize - 1); |
| 230 } | 230 } |
| 231 while (borrow != 0) { | 231 while (borrow != 0) { |
| 232 Chunk difference = bigits_[i + offset] - borrow; | 232 Chunk difference = bigits_[i + offset] - borrow; |
| 233 bigits_[i + offset] = difference & kBigitMask; | 233 bigits_[i + offset] = difference & kBigitMask; |
| 234 borrow = difference >> (kChunkSize - 1); | 234 borrow = difference >> (kChunkSize - 1); |
| 235 ++i; | 235 ++i; |
| 236 } | 236 } |
| 237 Clamp(); | 237 Clamp(); |
| 238 } | 238 } |
| 239 | 239 |
| (...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 334 remaining_exponent -= 13; | 334 remaining_exponent -= 13; |
| 335 } | 335 } |
| 336 if (remaining_exponent > 0) { | 336 if (remaining_exponent > 0) { |
| 337 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); | 337 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); |
| 338 } | 338 } |
| 339 ShiftLeft(exponent); | 339 ShiftLeft(exponent); |
| 340 } | 340 } |
| 341 | 341 |
| 342 | 342 |
| 343 void Bignum::Square() { | 343 void Bignum::Square() { |
| 344 ASSERT(IsClamped()); | 344 DCHECK(IsClamped()); |
| 345 int product_length = 2 * used_digits_; | 345 int product_length = 2 * used_digits_; |
| 346 EnsureCapacity(product_length); | 346 EnsureCapacity(product_length); |
| 347 | 347 |
| 348 // Comba multiplication: compute each column separately. | 348 // Comba multiplication: compute each column separately. |
| 349 // Example: r = a2a1a0 * b2b1b0. | 349 // Example: r = a2a1a0 * b2b1b0. |
| 350 // r = 1 * a0b0 + | 350 // r = 1 * a0b0 + |
| 351 // 10 * (a1b0 + a0b1) + | 351 // 10 * (a1b0 + a0b1) + |
| 352 // 100 * (a2b0 + a1b1 + a0b2) + | 352 // 100 * (a2b0 + a1b1 + a0b2) + |
| 353 // 1000 * (a2b1 + a1b2) + | 353 // 1000 * (a2b1 + a1b2) + |
| 354 // 10000 * a2b2 | 354 // 10000 * a2b2 |
| 355 // | 355 // |
| 356 // In the worst case we have to accumulate nb-digits products of digit*d
igit. | 356 // In the worst case we have to accumulate nb-digits products of |
| 357 // | 357 // digit*digit. |
| 358 // Assert that the additional number of bits in a DoubleChunk are enough
to | 358 // |
| 359 // sum up used_digits of Bigit*Bigit. | 359 // Assert that the additional number of bits in a DoubleChunk are enough |
| 360 if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { | 360 // to sum up used_digits of Bigit*Bigit. |
| 361 UNIMPLEMENTED(); | 361 if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { |
| 362 UNIMPLEMENTED(); |
| 362 } | 363 } |
| 363 DoubleChunk accumulator = 0; | 364 DoubleChunk accumulator = 0; |
| 364 // First shift the digits so we don't overwrite them. | 365 // First shift the digits so we don't overwrite them. |
| 365 int copy_offset = used_digits_; | 366 int copy_offset = used_digits_; |
| 366 for (int i = 0; i < used_digits_; ++i) { | 367 for (int i = 0; i < used_digits_; ++i) { |
| 367 bigits_[copy_offset + i] = bigits_[i]; | 368 bigits_[copy_offset + i] = bigits_[i]; |
| 368 } | 369 } |
| 369 // We have two loops to avoid some 'if's in the loop. | 370 // We have two loops to avoid some 'if's in the loop. |
| 370 for (int i = 0; i < used_digits_; ++i) { | 371 for (int i = 0; i < used_digits_; ++i) { |
| 371 // Process temporary digit i with power i. | 372 // Process temporary digit i with power i. |
| (...skipping 108 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 480 mask >>= 1; | 481 mask >>= 1; |
| 481 } | 482 } |
| 482 | 483 |
| 483 // And finally add the saved shifts. | 484 // And finally add the saved shifts. |
| 484 ShiftLeft(shifts * power_exponent); | 485 ShiftLeft(shifts * power_exponent); |
| 485 } | 486 } |
| 486 | 487 |
| 487 | 488 |
| 488 // Precondition: this/other < 16bit. | 489 // Precondition: this/other < 16bit. |
| 489 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { | 490 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { |
| 490 ASSERT(IsClamped()); | 491 DCHECK(IsClamped()); |
| 491 ASSERT(other.IsClamped()); | 492 DCHECK(other.IsClamped()); |
| 492 ASSERT(other.used_digits_ > 0); | 493 ASSERT(other.used_digits_ > 0); |
| 493 | 494 |
| 494 // Easy case: if we have less digits than the divisor than the result is
0. | 495 // Easy case: if we have less digits than the divisor than the result is |
| 495 // Note: this handles the case where this == 0, too. | 496 // 0. Note: this handles the case where this == 0, too. |
| 496 if (BigitLength() < other.BigitLength()) { | 497 if (BigitLength() < other.BigitLength()) { |
| 497 return 0; | 498 return 0; |
| 498 } | 499 } |
| 499 | 500 |
| 500 Align(other); | 501 Align(other); |
| 501 | 502 |
| 502 uint16_t result = 0; | 503 uint16_t result = 0; |
| 503 | 504 |
| 504 // Start by removing multiples of 'other' until both numbers have the sa
me | 505 // Start by removing multiples of 'other' until both numbers have the sa
me |
| 505 // number of digits. | 506 // number of digits. |
| 506 while (BigitLength() > other.BigitLength()) { | 507 while (BigitLength() > other.BigitLength()) { |
| 507 // This naive approach is extremely inefficient if the this divided
other | 508 // This naive approach is extremely inefficient if the this divided
other |
| (...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 562 | 563 |
| 563 | 564 |
| 564 static char HexCharOfValue(uint8_t value) { | 565 static char HexCharOfValue(uint8_t value) { |
| 565 ASSERT(0 <= value && value <= 16); | 566 ASSERT(0 <= value && value <= 16); |
| 566 if (value < 10) return value + '0'; | 567 if (value < 10) return value + '0'; |
| 567 return value - 10 + 'A'; | 568 return value - 10 + 'A'; |
| 568 } | 569 } |
| 569 | 570 |
| 570 | 571 |
| 571 bool Bignum::ToHexString(char* buffer, int buffer_size) const { | 572 bool Bignum::ToHexString(char* buffer, int buffer_size) const { |
| 572 ASSERT(IsClamped()); | 573 DCHECK(IsClamped()); |
| 573 // Each bigit must be printable as separate hex-character. | 574 // Each bigit must be printable as separate hex-character. |
| 574 ASSERT(kBigitSize % 4 == 0); | 575 ASSERT(kBigitSize % 4 == 0); |
| 575 const int kHexCharsPerBigit = kBigitSize / 4; | 576 const int kHexCharsPerBigit = kBigitSize / 4; |
| 576 | 577 |
| 577 if (used_digits_ == 0) { | 578 if (used_digits_ == 0) { |
| 578 if (buffer_size < 2) return false; | 579 if (buffer_size < 2) |
| 579 buffer[0] = '0'; | 580 return false; |
| 580 buffer[1] = '\0'; | 581 buffer[0] = '0'; |
| 581 return true; | 582 buffer[1] = '\0'; |
| 583 return true; |
| 582 } | 584 } |
| 583 // We add 1 for the terminating '\0' character. | 585 // We add 1 for the terminating '\0' character. |
| 584 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + | 586 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + |
| 585 SizeInHexChars(bigits_[used_digits_ - 1]) + 1; | 587 SizeInHexChars(bigits_[used_digits_ - 1]) + 1; |
| 586 if (needed_chars > buffer_size) return false; | 588 if (needed_chars > buffer_size) return false; |
| 587 int string_index = needed_chars - 1; | 589 int string_index = needed_chars - 1; |
| 588 buffer[string_index--] = '\0'; | 590 buffer[string_index--] = '\0'; |
| 589 for (int i = 0; i < exponent_; ++i) { | 591 for (int i = 0; i < exponent_; ++i) { |
| 590 for (int j = 0; j < kHexCharsPerBigit; ++j) { | 592 for (int j = 0; j < kHexCharsPerBigit; ++j) { |
| 591 buffer[string_index--] = '0'; | 593 buffer[string_index--] = '0'; |
| (...skipping 17 matching lines...) Expand all Loading... |
| 609 | 611 |
| 610 | 612 |
| 611 Bignum::Chunk Bignum::BigitAt(int index) const { | 613 Bignum::Chunk Bignum::BigitAt(int index) const { |
| 612 if (index >= BigitLength()) return 0; | 614 if (index >= BigitLength()) return 0; |
| 613 if (index < exponent_) return 0; | 615 if (index < exponent_) return 0; |
| 614 return bigits_[index - exponent_]; | 616 return bigits_[index - exponent_]; |
| 615 } | 617 } |
| 616 | 618 |
| 617 | 619 |
| 618 int Bignum::Compare(const Bignum& a, const Bignum& b) { | 620 int Bignum::Compare(const Bignum& a, const Bignum& b) { |
| 619 ASSERT(a.IsClamped()); | 621 DCHECK(a.IsClamped()); |
| 620 ASSERT(b.IsClamped()); | 622 DCHECK(b.IsClamped()); |
| 621 int bigit_length_a = a.BigitLength(); | 623 int bigit_length_a = a.BigitLength(); |
| 622 int bigit_length_b = b.BigitLength(); | 624 int bigit_length_b = b.BigitLength(); |
| 623 if (bigit_length_a < bigit_length_b) return -1; | 625 if (bigit_length_a < bigit_length_b) |
| 624 if (bigit_length_a > bigit_length_b) return +1; | 626 return -1; |
| 625 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i
) { | 627 if (bigit_length_a > bigit_length_b) |
| 626 Chunk bigit_a = a.BigitAt(i); | 628 return +1; |
| 627 Chunk bigit_b = b.BigitAt(i); | 629 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); |
| 628 if (bigit_a < bigit_b) return -1; | 630 --i) { |
| 629 if (bigit_a > bigit_b) return +1; | 631 Chunk bigit_a = a.BigitAt(i); |
| 630 // Otherwise they are equal up to this digit. Try the next digit. | 632 Chunk bigit_b = b.BigitAt(i); |
| 633 if (bigit_a < bigit_b) |
| 634 return -1; |
| 635 if (bigit_a > bigit_b) |
| 636 return +1; |
| 637 // Otherwise they are equal up to this digit. Try the next digit. |
| 631 } | 638 } |
| 632 return 0; | 639 return 0; |
| 633 } | 640 } |
| 634 | 641 |
| 635 | 642 |
| 636 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { | 643 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { |
| 637 ASSERT(a.IsClamped()); | 644 DCHECK(a.IsClamped()); |
| 638 ASSERT(b.IsClamped()); | 645 DCHECK(b.IsClamped()); |
| 639 ASSERT(c.IsClamped()); | 646 DCHECK(c.IsClamped()); |
| 640 if (a.BigitLength() < b.BigitLength()) { | 647 if (a.BigitLength() < b.BigitLength()) { |
| 641 return PlusCompare(b, a, c); | 648 return PlusCompare(b, a, c); |
| 642 } | 649 } |
| 643 if (a.BigitLength() + 1 < c.BigitLength()) return -1; | 650 if (a.BigitLength() + 1 < c.BigitLength()) return -1; |
| 644 if (a.BigitLength() > c.BigitLength()) return +1; | 651 if (a.BigitLength() > c.BigitLength()) return +1; |
| 645 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' t
han | 652 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' t
han |
| 646 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the
one | 653 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the
one |
| 647 // of 'a'. | 654 // of 'a'. |
| 648 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength())
{ | 655 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength())
{ |
| 649 return -1; | 656 return -1; |
| 650 } | 657 } |
| 651 | 658 |
| (...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 759 bigits_[i] = difference & kBigitMask; | 766 bigits_[i] = difference & kBigitMask; |
| 760 borrow = difference >> (kChunkSize - 1); | 767 borrow = difference >> (kChunkSize - 1); |
| 761 } | 768 } |
| 762 Clamp(); | 769 Clamp(); |
| 763 } | 770 } |
| 764 | 771 |
| 765 | 772 |
| 766 } // namespace double_conversion | 773 } // namespace double_conversion |
| 767 | 774 |
| 768 } // namespace WTF | 775 } // namespace WTF |
| OLD | NEW |