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

Side by Side Diff: src/fast-dtoa.cc

Issue 430503007: Rename ASSERT* to DCHECK*. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: REBASE and fixes Created 6 years, 4 months 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 | Annotate | Revision Log
« no previous file with comments | « src/factory.cc ('k') | src/field-index.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2011 the V8 project authors. All rights reserved. 1 // Copyright 2011 the V8 project 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 #include "include/v8stdint.h" 5 #include "include/v8stdint.h"
6 #include "src/base/logging.h" 6 #include "src/base/logging.h"
7 #include "src/utils.h" 7 #include "src/utils.h"
8 8
9 #include "src/fast-dtoa.h" 9 #include "src/fast-dtoa.h"
10 10
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after
113 // There are 3 conditions that stop the decrementation process: 113 // There are 3 conditions that stop the decrementation process:
114 // 1) the buffer is already below w_high 114 // 1) the buffer is already below w_high
115 // 2) decrementing the buffer would make it leave the unsafe interval 115 // 2) decrementing the buffer would make it leave the unsafe interval
116 // 3) decrementing the buffer would yield a number below w_high and farther 116 // 3) decrementing the buffer would yield a number below w_high and farther
117 // away than the current number. In other words: 117 // away than the current number. In other words:
118 // (buffer{-1} < w_high) && w_high - buffer{-1} > buffer - w_high 118 // (buffer{-1} < w_high) && w_high - buffer{-1} > buffer - w_high
119 // Instead of using the buffer directly we use its distance to too_high. 119 // Instead of using the buffer directly we use its distance to too_high.
120 // Conceptually rest ~= too_high - buffer 120 // Conceptually rest ~= too_high - buffer
121 // We need to do the following tests in this order to avoid over- and 121 // We need to do the following tests in this order to avoid over- and
122 // underflows. 122 // underflows.
123 ASSERT(rest <= unsafe_interval); 123 DCHECK(rest <= unsafe_interval);
124 while (rest < small_distance && // Negated condition 1 124 while (rest < small_distance && // Negated condition 1
125 unsafe_interval - rest >= ten_kappa && // Negated condition 2 125 unsafe_interval - rest >= ten_kappa && // Negated condition 2
126 (rest + ten_kappa < small_distance || // buffer{-1} > w_high 126 (rest + ten_kappa < small_distance || // buffer{-1} > w_high
127 small_distance - rest >= rest + ten_kappa - small_distance)) { 127 small_distance - rest >= rest + ten_kappa - small_distance)) {
128 buffer[length - 1]--; 128 buffer[length - 1]--;
129 rest += ten_kappa; 129 rest += ten_kappa;
130 } 130 }
131 131
132 // We have approached w+ as much as possible. We now test if approaching w- 132 // We have approached w+ as much as possible. We now test if approaching w-
133 // would require changing the buffer. If yes, then we have two possible 133 // would require changing the buffer. If yes, then we have two possible
(...skipping 25 matching lines...) Expand all
159 // imprecision and returns false, if the rounding direction cannot be 159 // imprecision and returns false, if the rounding direction cannot be
160 // unambiguously determined. 160 // unambiguously determined.
161 // 161 //
162 // Precondition: rest < ten_kappa. 162 // Precondition: rest < ten_kappa.
163 static bool RoundWeedCounted(Vector<char> buffer, 163 static bool RoundWeedCounted(Vector<char> buffer,
164 int length, 164 int length,
165 uint64_t rest, 165 uint64_t rest,
166 uint64_t ten_kappa, 166 uint64_t ten_kappa,
167 uint64_t unit, 167 uint64_t unit,
168 int* kappa) { 168 int* kappa) {
169 ASSERT(rest < ten_kappa); 169 DCHECK(rest < ten_kappa);
170 // The following tests are done in a specific order to avoid overflows. They 170 // The following tests are done in a specific order to avoid overflows. They
171 // will work correctly with any uint64 values of rest < ten_kappa and unit. 171 // will work correctly with any uint64 values of rest < ten_kappa and unit.
172 // 172 //
173 // If the unit is too big, then we don't know which way to round. For example 173 // If the unit is too big, then we don't know which way to round. For example
174 // a unit of 50 means that the real number lies within rest +/- 50. If 174 // a unit of 50 means that the real number lies within rest +/- 50. If
175 // 10^kappa == 40 then there is no way to tell which way to round. 175 // 10^kappa == 40 then there is no way to tell which way to round.
176 if (unit >= ten_kappa) return false; 176 if (unit >= ten_kappa) return false;
177 // Even if unit is just half the size of 10^kappa we are already completely 177 // Even if unit is just half the size of 10^kappa we are already completely
178 // lost. (And after the previous test we know that the expression will not 178 // lost. (And after the previous test we know that the expression will not
179 // over/underflow.) 179 // over/underflow.)
(...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after
358 // once we have enough digits. That is, once the digits inside the buffer 358 // once we have enough digits. That is, once the digits inside the buffer
359 // represent 'w' we can stop. Everything inside the interval low - high 359 // represent 'w' we can stop. Everything inside the interval low - high
360 // represents w. However we have to pay attention to low, high and w's 360 // represents w. However we have to pay attention to low, high and w's
361 // imprecision. 361 // imprecision.
362 static bool DigitGen(DiyFp low, 362 static bool DigitGen(DiyFp low,
363 DiyFp w, 363 DiyFp w,
364 DiyFp high, 364 DiyFp high,
365 Vector<char> buffer, 365 Vector<char> buffer,
366 int* length, 366 int* length,
367 int* kappa) { 367 int* kappa) {
368 ASSERT(low.e() == w.e() && w.e() == high.e()); 368 DCHECK(low.e() == w.e() && w.e() == high.e());
369 ASSERT(low.f() + 1 <= high.f() - 1); 369 DCHECK(low.f() + 1 <= high.f() - 1);
370 ASSERT(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent); 370 DCHECK(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent);
371 // low, w and high are imprecise, but by less than one ulp (unit in the last 371 // low, w and high are imprecise, but by less than one ulp (unit in the last
372 // place). 372 // place).
373 // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that 373 // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that
374 // the new numbers are outside of the interval we want the final 374 // the new numbers are outside of the interval we want the final
375 // representation to lie in. 375 // representation to lie in.
376 // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield 376 // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield
377 // numbers that are certain to lie in the interval. We will use this fact 377 // numbers that are certain to lie in the interval. We will use this fact
378 // later on. 378 // later on.
379 // We will now start by generating the digits within the uncertain 379 // We will now start by generating the digits within the uncertain
380 // interval. Later we will weed out representations that lie outside the safe 380 // interval. Later we will weed out representations that lie outside the safe
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after
428 } 428 }
429 divisor /= 10; 429 divisor /= 10;
430 } 430 }
431 431
432 // The integrals have been generated. We are at the point of the decimal 432 // The integrals have been generated. We are at the point of the decimal
433 // separator. In the following loop we simply multiply the remaining digits by 433 // separator. In the following loop we simply multiply the remaining digits by
434 // 10 and divide by one. We just need to pay attention to multiply associated 434 // 10 and divide by one. We just need to pay attention to multiply associated
435 // data (like the interval or 'unit'), too. 435 // data (like the interval or 'unit'), too.
436 // Note that the multiplication by 10 does not overflow, because w.e >= -60 436 // Note that the multiplication by 10 does not overflow, because w.e >= -60
437 // and thus one.e >= -60. 437 // and thus one.e >= -60.
438 ASSERT(one.e() >= -60); 438 DCHECK(one.e() >= -60);
439 ASSERT(fractionals < one.f()); 439 DCHECK(fractionals < one.f());
440 ASSERT(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f()); 440 DCHECK(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f());
441 while (true) { 441 while (true) {
442 fractionals *= 10; 442 fractionals *= 10;
443 unit *= 10; 443 unit *= 10;
444 unsafe_interval.set_f(unsafe_interval.f() * 10); 444 unsafe_interval.set_f(unsafe_interval.f() * 10);
445 // Integer division by one. 445 // Integer division by one.
446 int digit = static_cast<int>(fractionals >> -one.e()); 446 int digit = static_cast<int>(fractionals >> -one.e());
447 buffer[*length] = '0' + digit; 447 buffer[*length] = '0' + digit;
448 (*length)++; 448 (*length)++;
449 fractionals &= one.f() - 1; // Modulo by one. 449 fractionals &= one.f() - 1; // Modulo by one.
450 (*kappa)--; 450 (*kappa)--;
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
483 // 483 //
484 // Remark: This procedure takes into account the imprecision of its input 484 // Remark: This procedure takes into account the imprecision of its input
485 // numbers. If the precision is not enough to guarantee all the postconditions 485 // numbers. If the precision is not enough to guarantee all the postconditions
486 // then false is returned. This usually happens rarely, but the failure-rate 486 // then false is returned. This usually happens rarely, but the failure-rate
487 // increases with higher requested_digits. 487 // increases with higher requested_digits.
488 static bool DigitGenCounted(DiyFp w, 488 static bool DigitGenCounted(DiyFp w,
489 int requested_digits, 489 int requested_digits,
490 Vector<char> buffer, 490 Vector<char> buffer,
491 int* length, 491 int* length,
492 int* kappa) { 492 int* kappa) {
493 ASSERT(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent); 493 DCHECK(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent);
494 ASSERT(kMinimalTargetExponent >= -60); 494 DCHECK(kMinimalTargetExponent >= -60);
495 ASSERT(kMaximalTargetExponent <= -32); 495 DCHECK(kMaximalTargetExponent <= -32);
496 // w is assumed to have an error less than 1 unit. Whenever w is scaled we 496 // w is assumed to have an error less than 1 unit. Whenever w is scaled we
497 // also scale its error. 497 // also scale its error.
498 uint64_t w_error = 1; 498 uint64_t w_error = 1;
499 // We cut the input number into two parts: the integral digits and the 499 // We cut the input number into two parts: the integral digits and the
500 // fractional digits. We don't emit any decimal separator, but adapt kappa 500 // fractional digits. We don't emit any decimal separator, but adapt kappa
501 // instead. Example: instead of writing "1.2" we put "12" into the buffer and 501 // instead. Example: instead of writing "1.2" we put "12" into the buffer and
502 // increase kappa by 1. 502 // increase kappa by 1.
503 DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e()); 503 DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e());
504 // Division by one is a shift. 504 // Division by one is a shift.
505 uint32_t integrals = static_cast<uint32_t>(w.f() >> -one.e()); 505 uint32_t integrals = static_cast<uint32_t>(w.f() >> -one.e());
(...skipping 30 matching lines...) Expand all
536 static_cast<uint64_t>(divisor) << -one.e(), w_error, 536 static_cast<uint64_t>(divisor) << -one.e(), w_error,
537 kappa); 537 kappa);
538 } 538 }
539 539
540 // The integrals have been generated. We are at the point of the decimal 540 // The integrals have been generated. We are at the point of the decimal
541 // separator. In the following loop we simply multiply the remaining digits by 541 // separator. In the following loop we simply multiply the remaining digits by
542 // 10 and divide by one. We just need to pay attention to multiply associated 542 // 10 and divide by one. We just need to pay attention to multiply associated
543 // data (the 'unit'), too. 543 // data (the 'unit'), too.
544 // Note that the multiplication by 10 does not overflow, because w.e >= -60 544 // Note that the multiplication by 10 does not overflow, because w.e >= -60
545 // and thus one.e >= -60. 545 // and thus one.e >= -60.
546 ASSERT(one.e() >= -60); 546 DCHECK(one.e() >= -60);
547 ASSERT(fractionals < one.f()); 547 DCHECK(fractionals < one.f());
548 ASSERT(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f()); 548 DCHECK(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f());
549 while (requested_digits > 0 && fractionals > w_error) { 549 while (requested_digits > 0 && fractionals > w_error) {
550 fractionals *= 10; 550 fractionals *= 10;
551 w_error *= 10; 551 w_error *= 10;
552 // Integer division by one. 552 // Integer division by one.
553 int digit = static_cast<int>(fractionals >> -one.e()); 553 int digit = static_cast<int>(fractionals >> -one.e());
554 buffer[*length] = '0' + digit; 554 buffer[*length] = '0' + digit;
555 (*length)++; 555 (*length)++;
556 requested_digits--; 556 requested_digits--;
557 fractionals &= one.f() - 1; // Modulo by one. 557 fractionals &= one.f() - 1; // Modulo by one.
558 (*kappa)--; 558 (*kappa)--;
(...skipping 19 matching lines...) Expand all
578 Vector<char> buffer, 578 Vector<char> buffer,
579 int* length, 579 int* length,
580 int* decimal_exponent) { 580 int* decimal_exponent) {
581 DiyFp w = Double(v).AsNormalizedDiyFp(); 581 DiyFp w = Double(v).AsNormalizedDiyFp();
582 // boundary_minus and boundary_plus are the boundaries between v and its 582 // boundary_minus and boundary_plus are the boundaries between v and its
583 // closest floating-point neighbors. Any number strictly between 583 // closest floating-point neighbors. Any number strictly between
584 // boundary_minus and boundary_plus will round to v when convert to a double. 584 // boundary_minus and boundary_plus will round to v when convert to a double.
585 // Grisu3 will never output representations that lie exactly on a boundary. 585 // Grisu3 will never output representations that lie exactly on a boundary.
586 DiyFp boundary_minus, boundary_plus; 586 DiyFp boundary_minus, boundary_plus;
587 Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus); 587 Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus);
588 ASSERT(boundary_plus.e() == w.e()); 588 DCHECK(boundary_plus.e() == w.e());
589 DiyFp ten_mk; // Cached power of ten: 10^-k 589 DiyFp ten_mk; // Cached power of ten: 10^-k
590 int mk; // -k 590 int mk; // -k
591 int ten_mk_minimal_binary_exponent = 591 int ten_mk_minimal_binary_exponent =
592 kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize); 592 kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize);
593 int ten_mk_maximal_binary_exponent = 593 int ten_mk_maximal_binary_exponent =
594 kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize); 594 kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize);
595 PowersOfTenCache::GetCachedPowerForBinaryExponentRange( 595 PowersOfTenCache::GetCachedPowerForBinaryExponentRange(
596 ten_mk_minimal_binary_exponent, 596 ten_mk_minimal_binary_exponent,
597 ten_mk_maximal_binary_exponent, 597 ten_mk_maximal_binary_exponent,
598 &ten_mk, &mk); 598 &ten_mk, &mk);
599 ASSERT((kMinimalTargetExponent <= w.e() + ten_mk.e() + 599 DCHECK((kMinimalTargetExponent <= w.e() + ten_mk.e() +
600 DiyFp::kSignificandSize) && 600 DiyFp::kSignificandSize) &&
601 (kMaximalTargetExponent >= w.e() + ten_mk.e() + 601 (kMaximalTargetExponent >= w.e() + ten_mk.e() +
602 DiyFp::kSignificandSize)); 602 DiyFp::kSignificandSize));
603 // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a 603 // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a
604 // 64 bit significand and ten_mk is thus only precise up to 64 bits. 604 // 64 bit significand and ten_mk is thus only precise up to 64 bits.
605 605
606 // The DiyFp::Times procedure rounds its result, and ten_mk is approximated 606 // The DiyFp::Times procedure rounds its result, and ten_mk is approximated
607 // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now 607 // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now
608 // off by a small amount. 608 // off by a small amount.
609 // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w. 609 // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w.
610 // In other words: let f = scaled_w.f() and e = scaled_w.e(), then 610 // In other words: let f = scaled_w.f() and e = scaled_w.e(), then
611 // (f-1) * 2^e < w*10^k < (f+1) * 2^e 611 // (f-1) * 2^e < w*10^k < (f+1) * 2^e
612 DiyFp scaled_w = DiyFp::Times(w, ten_mk); 612 DiyFp scaled_w = DiyFp::Times(w, ten_mk);
613 ASSERT(scaled_w.e() == 613 DCHECK(scaled_w.e() ==
614 boundary_plus.e() + ten_mk.e() + DiyFp::kSignificandSize); 614 boundary_plus.e() + ten_mk.e() + DiyFp::kSignificandSize);
615 // In theory it would be possible to avoid some recomputations by computing 615 // In theory it would be possible to avoid some recomputations by computing
616 // the difference between w and boundary_minus/plus (a power of 2) and to 616 // the difference between w and boundary_minus/plus (a power of 2) and to
617 // compute scaled_boundary_minus/plus by subtracting/adding from 617 // compute scaled_boundary_minus/plus by subtracting/adding from
618 // scaled_w. However the code becomes much less readable and the speed 618 // scaled_w. However the code becomes much less readable and the speed
619 // enhancements are not terriffic. 619 // enhancements are not terriffic.
620 DiyFp scaled_boundary_minus = DiyFp::Times(boundary_minus, ten_mk); 620 DiyFp scaled_boundary_minus = DiyFp::Times(boundary_minus, ten_mk);
621 DiyFp scaled_boundary_plus = DiyFp::Times(boundary_plus, ten_mk); 621 DiyFp scaled_boundary_plus = DiyFp::Times(boundary_plus, ten_mk);
622 622
623 // DigitGen will generate the digits of scaled_w. Therefore we have 623 // DigitGen will generate the digits of scaled_w. Therefore we have
(...skipping 24 matching lines...) Expand all
648 DiyFp ten_mk; // Cached power of ten: 10^-k 648 DiyFp ten_mk; // Cached power of ten: 10^-k
649 int mk; // -k 649 int mk; // -k
650 int ten_mk_minimal_binary_exponent = 650 int ten_mk_minimal_binary_exponent =
651 kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize); 651 kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize);
652 int ten_mk_maximal_binary_exponent = 652 int ten_mk_maximal_binary_exponent =
653 kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize); 653 kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize);
654 PowersOfTenCache::GetCachedPowerForBinaryExponentRange( 654 PowersOfTenCache::GetCachedPowerForBinaryExponentRange(
655 ten_mk_minimal_binary_exponent, 655 ten_mk_minimal_binary_exponent,
656 ten_mk_maximal_binary_exponent, 656 ten_mk_maximal_binary_exponent,
657 &ten_mk, &mk); 657 &ten_mk, &mk);
658 ASSERT((kMinimalTargetExponent <= w.e() + ten_mk.e() + 658 DCHECK((kMinimalTargetExponent <= w.e() + ten_mk.e() +
659 DiyFp::kSignificandSize) && 659 DiyFp::kSignificandSize) &&
660 (kMaximalTargetExponent >= w.e() + ten_mk.e() + 660 (kMaximalTargetExponent >= w.e() + ten_mk.e() +
661 DiyFp::kSignificandSize)); 661 DiyFp::kSignificandSize));
662 // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a 662 // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a
663 // 64 bit significand and ten_mk is thus only precise up to 64 bits. 663 // 64 bit significand and ten_mk is thus only precise up to 64 bits.
664 664
665 // The DiyFp::Times procedure rounds its result, and ten_mk is approximated 665 // The DiyFp::Times procedure rounds its result, and ten_mk is approximated
666 // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now 666 // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now
667 // off by a small amount. 667 // off by a small amount.
668 // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w. 668 // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w.
(...skipping 13 matching lines...) Expand all
682 return result; 682 return result;
683 } 683 }
684 684
685 685
686 bool FastDtoa(double v, 686 bool FastDtoa(double v,
687 FastDtoaMode mode, 687 FastDtoaMode mode,
688 int requested_digits, 688 int requested_digits,
689 Vector<char> buffer, 689 Vector<char> buffer,
690 int* length, 690 int* length,
691 int* decimal_point) { 691 int* decimal_point) {
692 ASSERT(v > 0); 692 DCHECK(v > 0);
693 ASSERT(!Double(v).IsSpecial()); 693 DCHECK(!Double(v).IsSpecial());
694 694
695 bool result = false; 695 bool result = false;
696 int decimal_exponent = 0; 696 int decimal_exponent = 0;
697 switch (mode) { 697 switch (mode) {
698 case FAST_DTOA_SHORTEST: 698 case FAST_DTOA_SHORTEST:
699 result = Grisu3(v, buffer, length, &decimal_exponent); 699 result = Grisu3(v, buffer, length, &decimal_exponent);
700 break; 700 break;
701 case FAST_DTOA_PRECISION: 701 case FAST_DTOA_PRECISION:
702 result = Grisu3Counted(v, requested_digits, 702 result = Grisu3Counted(v, requested_digits,
703 buffer, length, &decimal_exponent); 703 buffer, length, &decimal_exponent);
704 break; 704 break;
705 default: 705 default:
706 UNREACHABLE(); 706 UNREACHABLE();
707 } 707 }
708 if (result) { 708 if (result) {
709 *decimal_point = *length + decimal_exponent; 709 *decimal_point = *length + decimal_exponent;
710 buffer[*length] = '\0'; 710 buffer[*length] = '\0';
711 } 711 }
712 return result; 712 return result;
713 } 713 }
714 714
715 } } // namespace v8::internal 715 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/factory.cc ('k') | src/field-index.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698