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 |