LCOV - code coverage report
Current view: top level - src - fast-dtoa.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 159 169 94.1 %
Date: 2017-04-26 Functions: 8 8 100.0 %

          Line data    Source code
       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
       3             : // found in the LICENSE file.
       4             : 
       5             : #include <stdint.h>
       6             : #include "src/base/logging.h"
       7             : #include "src/utils.h"
       8             : 
       9             : #include "src/fast-dtoa.h"
      10             : 
      11             : #include "src/cached-powers.h"
      12             : #include "src/diy-fp.h"
      13             : #include "src/double.h"
      14             : 
      15             : namespace v8 {
      16             : namespace internal {
      17             : 
      18             : // The minimal and maximal target exponent define the range of w's binary
      19             : // exponent, where 'w' is the result of multiplying the input by a cached power
      20             : // of ten.
      21             : //
      22             : // A different range might be chosen on a different platform, to optimize digit
      23             : // generation, but a smaller range requires more powers of ten to be cached.
      24             : static const int kMinimalTargetExponent = -60;
      25             : static const int kMaximalTargetExponent = -32;
      26             : 
      27             : 
      28             : // Adjusts the last digit of the generated number, and screens out generated
      29             : // solutions that may be inaccurate. A solution may be inaccurate if it is
      30             : // outside the safe interval, or if we ctannot prove that it is closer to the
      31             : // input than a neighboring representation of the same length.
      32             : //
      33             : // Input: * buffer containing the digits of too_high / 10^kappa
      34             : //        * the buffer's length
      35             : //        * distance_too_high_w == (too_high - w).f() * unit
      36             : //        * unsafe_interval == (too_high - too_low).f() * unit
      37             : //        * rest = (too_high - buffer * 10^kappa).f() * unit
      38             : //        * ten_kappa = 10^kappa * unit
      39             : //        * unit = the common multiplier
      40             : // Output: returns true if the buffer is guaranteed to contain the closest
      41             : //    representable number to the input.
      42             : //  Modifies the generated digits in the buffer to approach (round towards) w.
      43     3966850 : static bool RoundWeed(Vector<char> buffer,
      44             :                       int length,
      45             :                       uint64_t distance_too_high_w,
      46             :                       uint64_t unsafe_interval,
      47             :                       uint64_t rest,
      48             :                       uint64_t ten_kappa,
      49             :                       uint64_t unit) {
      50     3966850 :   uint64_t small_distance = distance_too_high_w - unit;
      51     3966850 :   uint64_t big_distance = distance_too_high_w + unit;
      52             :   // Let w_low  = too_high - big_distance, and
      53             :   //     w_high = too_high - small_distance.
      54             :   // Note: w_low < w < w_high
      55             :   //
      56             :   // The real w (* unit) must lie somewhere inside the interval
      57             :   // ]w_low; w_high[ (often written as "(w_low; w_high)")
      58             : 
      59             :   // Basically the buffer currently contains a number in the unsafe interval
      60             :   // ]too_low; too_high[ with too_low < w < too_high
      61             :   //
      62             :   //  too_high - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
      63             :   //                     ^v 1 unit            ^      ^                 ^      ^
      64             :   //  boundary_high ---------------------     .      .                 .      .
      65             :   //                     ^v 1 unit            .      .                 .      .
      66             :   //   - - - - - - - - - - - - - - - - - - -  +  - - + - - - - - -     .      .
      67             :   //                                          .      .         ^       .      .
      68             :   //                                          .  big_distance  .       .      .
      69             :   //                                          .      .         .       .    rest
      70             :   //                              small_distance     .         .       .      .
      71             :   //                                          v      .         .       .      .
      72             :   //  w_high - - - - - - - - - - - - - - - - - -     .         .       .      .
      73             :   //                     ^v 1 unit                   .         .       .      .
      74             :   //  w ----------------------------------------     .         .       .      .
      75             :   //                     ^v 1 unit                   v         .       .      .
      76             :   //  w_low  - - - - - - - - - - - - - - - - - - - - -         .       .      .
      77             :   //                                                           .       .      v
      78             :   //  buffer --------------------------------------------------+-------+--------
      79             :   //                                                           .       .
      80             :   //                                                  safe_interval    .
      81             :   //                                                           v       .
      82             :   //   - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -     .
      83             :   //                     ^v 1 unit                                     .
      84             :   //  boundary_low -------------------------                     unsafe_interval
      85             :   //                     ^v 1 unit                                     v
      86             :   //  too_low  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
      87             :   //
      88             :   //
      89             :   // Note that the value of buffer could lie anywhere inside the range too_low
      90             :   // to too_high.
      91             :   //
      92             :   // boundary_low, boundary_high and w are approximations of the real boundaries
      93             :   // and v (the input number). They are guaranteed to be precise up to one unit.
      94             :   // In fact the error is guaranteed to be strictly less than one unit.
      95             :   //
      96             :   // Anything that lies outside the unsafe interval is guaranteed not to round
      97             :   // to v when read again.
      98             :   // Anything that lies inside the safe interval is guaranteed to round to v
      99             :   // when read again.
     100             :   // If the number inside the buffer lies inside the unsafe interval but not
     101             :   // inside the safe interval then we simply do not know and bail out (returning
     102             :   // false).
     103             :   //
     104             :   // Similarly we have to take into account the imprecision of 'w' when finding
     105             :   // the closest representation of 'w'. If we have two potential
     106             :   // representations, and one is closer to both w_low and w_high, then we know
     107             :   // it is closer to the actual value v.
     108             :   //
     109             :   // By generating the digits of too_high we got the largest (closest to
     110             :   // too_high) buffer that is still in the unsafe interval. In the case where
     111             :   // w_high < buffer < too_high we try to decrement the buffer.
     112             :   // This way the buffer approaches (rounds towards) w.
     113             :   // There are 3 conditions that stop the decrementation process:
     114             :   //   1) the buffer is already below w_high
     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
     117             :   //      away than the current number. In other words:
     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.
     120             :   // Conceptually rest ~= too_high - buffer
     121             :   // We need to do the following tests in this order to avoid over- and
     122             :   // underflows.
     123             :   DCHECK(rest <= unsafe_interval);
     124     8521599 :   while (rest < small_distance &&  // Negated condition 1
     125     5148221 :          unsafe_interval - rest >= ten_kappa &&  // Negated condition 2
     126     3347797 :          (rest + ten_kappa < small_distance ||  // buffer{-1} > w_high
     127     1192400 :           small_distance - rest >= rest + ten_kappa - small_distance)) {
     128     3123850 :     buffer[length - 1]--;
     129             :     rest += ten_kappa;
     130             :   }
     131             : 
     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
     134             :   // representations close to w, but we cannot decide which one is closer.
     135     6578779 :   if (rest < big_distance &&
     136     3211791 :       unsafe_interval - rest >= ten_kappa &&
     137     1199724 :       (rest + ten_kappa < big_distance ||
     138      599862 :        big_distance - rest > rest + ten_kappa - big_distance)) {
     139             :     return false;
     140             :   }
     141             : 
     142             :   // Weeding test.
     143             :   //   The safe interval is [too_low + 2 ulp; too_high - 2 ulp]
     144             :   //   Since too_low = too_high - unsafe_interval this is equivalent to
     145             :   //      [too_high - unsafe_interval + 4 ulp; too_high - 2 ulp]
     146             :   //   Conceptually we have: rest ~= too_high - buffer
     147     3959873 :   return (2 * unit <= rest) && (rest <= unsafe_interval - 4 * unit);
     148             : }
     149             : 
     150             : 
     151             : // Rounds the buffer upwards if the result is closer to v by possibly adding
     152             : // 1 to the buffer. If the precision of the calculation is not sufficient to
     153             : // round correctly, return false.
     154             : // The rounding might shift the whole buffer in which case the kappa is
     155             : // adjusted. For example "99", kappa = 3 might become "10", kappa = 4.
     156             : //
     157             : // If 2*rest > ten_kappa then the buffer needs to be round up.
     158             : // rest can have an error of +/- 1 unit. This function accounts for the
     159             : // imprecision and returns false, if the rounding direction cannot be
     160             : // unambiguously determined.
     161             : //
     162             : // Precondition: rest < ten_kappa.
     163     1218748 : static bool RoundWeedCounted(Vector<char> buffer,
     164             :                              int length,
     165             :                              uint64_t rest,
     166             :                              uint64_t ten_kappa,
     167             :                              uint64_t unit,
     168             :                              int* kappa) {
     169             :   DCHECK(rest < ten_kappa);
     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.
     172             :   //
     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
     175             :   // 10^kappa == 40 then there is no way to tell which way to round.
     176     1218748 :   if (unit >= ten_kappa) return false;
     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
     179             :   // over/underflow.)
     180     1181795 :   if (ten_kappa - unit <= unit) return false;
     181             :   // If 2 * (rest + unit) <= 10^kappa we can safely round down.
     182     1163790 :   if ((ten_kappa - rest > rest) && (ten_kappa - 2 * rest >= 2 * unit)) {
     183             :     return true;
     184             :   }
     185             :   // If 2 * (rest - unit) >= 10^kappa, then we can safely round up.
     186      588060 :   if ((rest > unit) && (ten_kappa - (rest - unit) <= (rest - unit))) {
     187             :     // Increment the last digit recursively until we find a non '9' digit.
     188     1123992 :     buffer[length - 1]++;
     189      623124 :     for (int i = length - 1; i > 0; --i) {
     190      593052 :       if (buffer[i] != '0' + 10) break;
     191       61128 :       buffer[i] = '0';
     192      122256 :       buffer[i - 1]++;
     193             :     }
     194             :     // If the first digit is now '0'+ 10 we had a buffer with all '9's. With the
     195             :     // exception of the first digit all digits are now '0'. Simply switch the
     196             :     // first digit to '1' and adjust the kappa. Example: "99" becomes "10" and
     197             :     // the power (the kappa) is increased.
     198      561996 :     if (buffer[0] == '0' + 10) {
     199        1485 :       buffer[0] = '1';
     200        1485 :       (*kappa) += 1;
     201             :     }
     202             :     return true;
     203             :   }
     204             :   return false;
     205             : }
     206             : 
     207             : 
     208             : static const uint32_t kTen4 = 10000;
     209             : static const uint32_t kTen5 = 100000;
     210             : static const uint32_t kTen6 = 1000000;
     211             : static const uint32_t kTen7 = 10000000;
     212             : static const uint32_t kTen8 = 100000000;
     213             : static const uint32_t kTen9 = 1000000000;
     214             : 
     215             : // Returns the biggest power of ten that is less than or equal than the given
     216             : // number. We furthermore receive the maximum number of bits 'number' has.
     217             : // If number_bits == 0 then 0^-1 is returned
     218             : // The number of bits must be <= 32.
     219             : // Precondition: number < (1 << (number_bits + 1)).
     220     5275791 : static void BiggestPowerTen(uint32_t number,
     221             :                             int number_bits,
     222             :                             uint32_t* power,
     223             :                             int* exponent) {
     224     5275791 :   switch (number_bits) {
     225             :     case 32:
     226             :     case 31:
     227             :     case 30:
     228      458114 :       if (kTen9 <= number) {
     229           0 :         *power = kTen9;
     230           0 :         *exponent = 9;
     231           0 :         break;
     232             :       }  // else fallthrough
     233             :     case 29:
     234             :     case 28:
     235             :     case 27:
     236     1151888 :       if (kTen8 <= number) {
     237      961537 :         *power = kTen8;
     238      961537 :         *exponent = 8;
     239      961537 :         break;
     240             :       }  // else fallthrough
     241             :     case 26:
     242             :     case 25:
     243             :     case 24:
     244      616961 :       if (kTen7 <= number) {
     245      481647 :         *power = kTen7;
     246      481647 :         *exponent = 7;
     247      481647 :         break;
     248             :       }  // else fallthrough
     249             :     case 23:
     250             :     case 22:
     251             :     case 21:
     252             :     case 20:
     253     1519438 :       if (kTen6 <= number) {
     254      687273 :         *power = kTen6;
     255      687273 :         *exponent = 6;
     256      687273 :         break;
     257             :       }  // else fallthrough
     258             :     case 19:
     259             :     case 18:
     260             :     case 17:
     261     1613270 :       if (kTen5 <= number) {
     262     1384471 :         *power = kTen5;
     263     1384471 :         *exponent = 5;
     264     1384471 :         break;
     265             :       }  // else fallthrough
     266             :     case 16:
     267             :     case 15:
     268             :     case 14:
     269      631600 :       if (kTen4 <= number) {
     270      536154 :         *power = kTen4;
     271      536154 :         *exponent = 4;
     272      536154 :         break;
     273             :       }  // else fallthrough
     274             :     case 13:
     275             :     case 12:
     276             :     case 11:
     277             :     case 10:
     278      554555 :       if (1000 <= number) {
     279      393085 :         *power = 1000;
     280      393085 :         *exponent = 3;
     281      393085 :         break;
     282             :       }  // else fallthrough
     283             :     case 9:
     284             :     case 8:
     285             :     case 7:
     286      495814 :       if (100 <= number) {
     287      372350 :         *power = 100;
     288      372350 :         *exponent = 2;
     289      372350 :         break;
     290             :       }  // else fallthrough
     291             :     case 6:
     292             :     case 5:
     293             :     case 4:
     294      459274 :       if (10 <= number) {
     295      366513 :         *power = 10;
     296      366513 :         *exponent = 1;
     297      366513 :         break;
     298             :       }  // else fallthrough
     299             :     case 3:
     300             :     case 2:
     301             :     case 1:
     302       92761 :       if (1 <= number) {
     303       92761 :         *power = 1;
     304       92761 :         *exponent = 0;
     305       92761 :         break;
     306             :       }  // else fallthrough
     307             :     case 0:
     308           0 :       *power = 0;
     309           0 :       *exponent = -1;
     310           0 :       break;
     311             :     default:
     312             :       // Following assignments are here to silence compiler warnings.
     313           0 :       *power = 0;
     314           0 :       *exponent = 0;
     315           0 :       UNREACHABLE();
     316             :   }
     317     5275791 : }
     318             : 
     319             : 
     320             : // Generates the digits of input number w.
     321             : // w is a floating-point number (DiyFp), consisting of a significand and an
     322             : // exponent. Its exponent is bounded by kMinimalTargetExponent and
     323             : // kMaximalTargetExponent.
     324             : //       Hence -60 <= w.e() <= -32.
     325             : //
     326             : // Returns false if it fails, in which case the generated digits in the buffer
     327             : // should not be used.
     328             : // Preconditions:
     329             : //  * low, w and high are correct up to 1 ulp (unit in the last place). That
     330             : //    is, their error must be less than a unit of their last digits.
     331             : //  * low.e() == w.e() == high.e()
     332             : //  * low < w < high, and taking into account their error: low~ <= high~
     333             : //  * kMinimalTargetExponent <= w.e() <= kMaximalTargetExponent
     334             : // Postconditions: returns false if procedure fails.
     335             : //   otherwise:
     336             : //     * buffer is not null-terminated, but len contains the number of digits.
     337             : //     * buffer contains the shortest possible decimal digit-sequence
     338             : //       such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the
     339             : //       correct values of low and high (without their error).
     340             : //     * if more than one decimal representation gives the minimal number of
     341             : //       decimal digits then the one closest to W (where W is the correct value
     342             : //       of w) is chosen.
     343             : // Remark: this procedure takes into account the imprecision of its input
     344             : //   numbers. If the precision is not enough to guarantee all the postconditions
     345             : //   then false is returned. This usually happens rarely (~0.5%).
     346             : //
     347             : // Say, for the sake of example, that
     348             : //   w.e() == -48, and w.f() == 0x1234567890abcdef
     349             : // w's value can be computed by w.f() * 2^w.e()
     350             : // We can obtain w's integral digits by simply shifting w.f() by -w.e().
     351             : //  -> w's integral part is 0x1234
     352             : //  w's fractional part is therefore 0x567890abcdef.
     353             : // Printing w's integral part is easy (simply print 0x1234 in decimal).
     354             : // In order to print its fraction we repeatedly multiply the fraction by 10 and
     355             : // get each digit. Example the first digit after the point would be computed by
     356             : //   (0x567890abcdef * 10) >> 48. -> 3
     357             : // The whole thing becomes slightly more complicated because we want to stop
     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
     360             : // represents w. However we have to pay attention to low, high and w's
     361             : // imprecision.
     362     3966850 : static bool DigitGen(DiyFp low,
     363             :                      DiyFp w,
     364             :                      DiyFp high,
     365             :                      Vector<char> buffer,
     366             :                      int* length,
     367             :                      int* kappa) {
     368             :   DCHECK(low.e() == w.e() && w.e() == high.e());
     369             :   DCHECK(low.f() + 1 <= high.f() - 1);
     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
     372             :   // place).
     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
     375             :   // representation to lie in.
     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
     378             :   // later on.
     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
     381             :   // interval and thus _might_ lie outside the correct interval.
     382             :   uint64_t unit = 1;
     383     3966850 :   DiyFp too_low = DiyFp(low.f() - unit, low.e());
     384     3966850 :   DiyFp too_high = DiyFp(high.f() + unit, high.e());
     385             :   // too_low and too_high are guaranteed to lie outside the interval we want the
     386             :   // generated number in.
     387             :   DiyFp unsafe_interval = DiyFp::Minus(too_high, too_low);
     388             :   // We now cut the input number into two parts: the integral digits and the
     389             :   // fractionals. We will not write any decimal separator though, but adapt
     390             :   // kappa instead.
     391             :   // Reminder: we are currently computing the digits (stored inside the buffer)
     392             :   // such that:   too_low < buffer * 10^kappa < too_high
     393             :   // We use too_high for the digit_generation and stop as soon as possible.
     394             :   // If we stop early we effectively round down.
     395     3966850 :   DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e());
     396             :   // Division by one is a shift.
     397     3966850 :   uint32_t integrals = static_cast<uint32_t>(too_high.f() >> -one.e());
     398             :   // Modulo by one is an and.
     399     3966850 :   uint64_t fractionals = too_high.f() & (one.f() - 1);
     400             :   uint32_t divisor;
     401             :   int divisor_exponent;
     402             :   BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()),
     403     3966850 :                   &divisor, &divisor_exponent);
     404     3966850 :   *kappa = divisor_exponent + 1;
     405     3966850 :   *length = 0;
     406             :   // Loop invariant: buffer = too_high / 10^kappa  (integer division)
     407             :   // The invariant holds for the first iteration: kappa has been initialized
     408             :   // with the divisor exponent + 1. And the divisor is the biggest power of ten
     409             :   // that is smaller than integrals.
     410    24082762 :   while (*kappa > 0) {
     411    21089083 :     int digit = integrals / divisor;
     412    42178166 :     buffer[*length] = '0' + digit;
     413    21089083 :     (*length)++;
     414    21089083 :     integrals %= divisor;
     415    21089083 :     (*kappa)--;
     416             :     // Note that kappa now equals the exponent of the divisor and that the
     417             :     // invariant thus holds again.
     418             :     uint64_t rest =
     419    21089083 :         (static_cast<uint64_t>(integrals) << -one.e()) + fractionals;
     420             :     // Invariant: too_high = buffer * 10^kappa + DiyFp(rest, one.e())
     421             :     // Reminder: unsafe_interval.e() == one.e()
     422    21089083 :     if (rest < unsafe_interval.f()) {
     423             :       // Rounding down (by not emitting the remaining digits) yields a number
     424             :       // that lies within the unsafe interval.
     425             :       return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f(),
     426             :                        unsafe_interval.f(), rest,
     427     1946342 :                        static_cast<uint64_t>(divisor) << -one.e(), unit);
     428             :     }
     429    20115912 :     divisor /= 10;
     430             :   }
     431             : 
     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
     434             :   // 10 and divide by one. We just need to pay attention to multiply associated
     435             :   // data (like the interval or 'unit'), too.
     436             :   // Note that the multiplication by 10 does not overflow, because w.e >= -60
     437             :   // and thus one.e >= -60.
     438             :   DCHECK(one.e() >= -60);
     439             :   DCHECK(fractionals < one.f());
     440             :   DCHECK(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f());
     441             :   while (true) {
     442    30193191 :     fractionals *= 10;
     443    30193191 :     unit *= 10;
     444    30193191 :     unsafe_interval.set_f(unsafe_interval.f() * 10);
     445             :     // Integer division by one.
     446    30193191 :     int digit = static_cast<int>(fractionals >> -one.e());
     447    60386382 :     buffer[*length] = '0' + digit;
     448    30193191 :     (*length)++;
     449    30193191 :     fractionals &= one.f() - 1;  // Modulo by one.
     450    30193191 :     (*kappa)--;
     451    30193191 :     if (fractionals < unsafe_interval.f()) {
     452             :       return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f() * unit,
     453     2993679 :                        unsafe_interval.f(), fractionals, one.f(), unit);
     454             :     }
     455             :   }
     456             : }
     457             : 
     458             : 
     459             : 
     460             : // Generates (at most) requested_digits of input number w.
     461             : // w is a floating-point number (DiyFp), consisting of a significand and an
     462             : // exponent. Its exponent is bounded by kMinimalTargetExponent and
     463             : // kMaximalTargetExponent.
     464             : //       Hence -60 <= w.e() <= -32.
     465             : //
     466             : // Returns false if it fails, in which case the generated digits in the buffer
     467             : // should not be used.
     468             : // Preconditions:
     469             : //  * w is correct up to 1 ulp (unit in the last place). That
     470             : //    is, its error must be strictly less than a unit of its last digit.
     471             : //  * kMinimalTargetExponent <= w.e() <= kMaximalTargetExponent
     472             : //
     473             : // Postconditions: returns false if procedure fails.
     474             : //   otherwise:
     475             : //     * buffer is not null-terminated, but length contains the number of
     476             : //       digits.
     477             : //     * the representation in buffer is the most precise representation of
     478             : //       requested_digits digits.
     479             : //     * buffer contains at most requested_digits digits of w. If there are less
     480             : //       than requested_digits digits then some trailing '0's have been removed.
     481             : //     * kappa is such that
     482             : //            w = buffer * 10^kappa + eps with |eps| < 10^kappa / 2.
     483             : //
     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
     486             : //   then false is returned. This usually happens rarely, but the failure-rate
     487             : //   increases with higher requested_digits.
     488     1308941 : static bool DigitGenCounted(DiyFp w,
     489             :                             int requested_digits,
     490             :                             Vector<char> buffer,
     491             :                             int* length,
     492             :                             int* kappa) {
     493             :   DCHECK(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent);
     494             :   DCHECK(kMinimalTargetExponent >= -60);
     495             :   DCHECK(kMaximalTargetExponent <= -32);
     496             :   // w is assumed to have an error less than 1 unit. Whenever w is scaled we
     497             :   // also scale its error.
     498             :   uint64_t w_error = 1;
     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
     501             :   // instead. Example: instead of writing "1.2" we put "12" into the buffer and
     502             :   // increase kappa by 1.
     503     1308941 :   DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e());
     504             :   // Division by one is a shift.
     505     1308941 :   uint32_t integrals = static_cast<uint32_t>(w.f() >> -one.e());
     506             :   // Modulo by one is an and.
     507     1308941 :   uint64_t fractionals = w.f() & (one.f() - 1);
     508             :   uint32_t divisor;
     509             :   int divisor_exponent;
     510             :   BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()),
     511     1308941 :                   &divisor, &divisor_exponent);
     512     1308941 :   *kappa = divisor_exponent + 1;
     513     1308941 :   *length = 0;
     514             : 
     515             :   // Loop invariant: buffer = w / 10^kappa  (integer division)
     516             :   // The invariant holds for the first iteration: kappa has been initialized
     517             :   // with the divisor exponent + 1. And the divisor is the biggest power of ten
     518             :   // that is smaller than 'integrals'.
     519     7007884 :   while (*kappa > 0) {
     520     6030104 :     int digit = integrals / divisor;
     521    12060208 :     buffer[*length] = '0' + digit;
     522     6030104 :     (*length)++;
     523     6030104 :     requested_digits--;
     524     6030104 :     integrals %= divisor;
     525     6030104 :     (*kappa)--;
     526             :     // Note that kappa now equals the exponent of the divisor and that the
     527             :     // invariant thus holds again.
     528     6030104 :     if (requested_digits == 0) break;
     529     5698943 :     divisor /= 10;
     530             :   }
     531             : 
     532     1308941 :   if (requested_digits == 0) {
     533             :     uint64_t rest =
     534      331161 :         (static_cast<uint64_t>(integrals) << -one.e()) + fractionals;
     535             :     return RoundWeedCounted(buffer, *length, rest,
     536             :                             static_cast<uint64_t>(divisor) << -one.e(), w_error,
     537      331161 :                             kappa);
     538             :   }
     539             : 
     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
     542             :   // 10 and divide by one. We just need to pay attention to multiply associated
     543             :   // data (the 'unit'), too.
     544             :   // Note that the multiplication by 10 does not overflow, because w.e >= -60
     545             :   // and thus one.e >= -60.
     546             :   DCHECK(one.e() >= -60);
     547             :   DCHECK(fractionals < one.f());
     548             :   DCHECK(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f());
     549     9183640 :   while (requested_digits > 0 && fractionals > w_error) {
     550     8205860 :     fractionals *= 10;
     551     8205860 :     w_error *= 10;
     552             :     // Integer division by one.
     553     8205860 :     int digit = static_cast<int>(fractionals >> -one.e());
     554    16411720 :     buffer[*length] = '0' + digit;
     555     8205860 :     (*length)++;
     556     8205860 :     requested_digits--;
     557     8205860 :     fractionals &= one.f() - 1;  // Modulo by one.
     558     8205860 :     (*kappa)--;
     559             :   }
     560      977780 :   if (requested_digits != 0) return false;
     561             :   return RoundWeedCounted(buffer, *length, fractionals, one.f(), w_error,
     562      887587 :                           kappa);
     563             : }
     564             : 
     565             : 
     566             : // Provides a decimal representation of v.
     567             : // Returns true if it succeeds, otherwise the result cannot be trusted.
     568             : // There will be *length digits inside the buffer (not null-terminated).
     569             : // If the function returns true then
     570             : //        v == (double) (buffer * 10^decimal_exponent).
     571             : // The digits in the buffer are the shortest representation possible: no
     572             : // 0.09999999999999999 instead of 0.1. The shorter representation will even be
     573             : // chosen even if the longer one would be closer to v.
     574             : // The last digit will be closest to the actual v. That is, even if several
     575             : // digits might correctly yield 'v' when read again, the closest will be
     576             : // computed.
     577     3966850 : static bool Grisu3(double v,
     578     3966850 :                    Vector<char> buffer,
     579             :                    int* length,
     580             :                    int* decimal_exponent) {
     581     3966850 :   DiyFp w = Double(v).AsNormalizedDiyFp();
     582             :   // boundary_minus and boundary_plus are the boundaries between v and its
     583             :   // closest floating-point neighbors. Any number strictly between
     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.
     586             :   DiyFp boundary_minus, boundary_plus;
     587     3966850 :   Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus);
     588             :   DCHECK(boundary_plus.e() == w.e());
     589             :   DiyFp ten_mk;  // Cached power of ten: 10^-k
     590             :   int mk;        // -k
     591             :   int ten_mk_minimal_binary_exponent =
     592     3966850 :      kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     593             :   int ten_mk_maximal_binary_exponent =
     594     3966850 :      kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     595             :   PowersOfTenCache::GetCachedPowerForBinaryExponentRange(
     596             :       ten_mk_minimal_binary_exponent,
     597             :       ten_mk_maximal_binary_exponent,
     598     3966850 :       &ten_mk, &mk);
     599             :   DCHECK((kMinimalTargetExponent <= w.e() + ten_mk.e() +
     600             :           DiyFp::kSignificandSize) &&
     601             :          (kMaximalTargetExponent >= w.e() + ten_mk.e() +
     602             :           DiyFp::kSignificandSize));
     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.
     605             : 
     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
     608             :   // off by a small amount.
     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
     611             :   //           (f-1) * 2^e < w*10^k < (f+1) * 2^e
     612     7933700 :   DiyFp scaled_w = DiyFp::Times(w, ten_mk);
     613             :   DCHECK(scaled_w.e() ==
     614             :          boundary_plus.e() + ten_mk.e() + DiyFp::kSignificandSize);
     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
     617             :   // compute scaled_boundary_minus/plus by subtracting/adding from
     618             :   // scaled_w. However the code becomes much less readable and the speed
     619             :   // enhancements are not terriffic.
     620     7933700 :   DiyFp scaled_boundary_minus = DiyFp::Times(boundary_minus, ten_mk);
     621     7933700 :   DiyFp scaled_boundary_plus  = DiyFp::Times(boundary_plus,  ten_mk);
     622             : 
     623             :   // DigitGen will generate the digits of scaled_w. Therefore we have
     624             :   // v == (double) (scaled_w * 10^-mk).
     625             :   // Set decimal_exponent == -mk and pass it to DigitGen. If scaled_w is not an
     626             :   // integer than it will be updated. For instance if scaled_w == 1.23 then
     627             :   // the buffer will be filled with "123" und the decimal_exponent will be
     628             :   // decreased by 2.
     629             :   int kappa;
     630             :   bool result = DigitGen(scaled_boundary_minus, scaled_w, scaled_boundary_plus,
     631     3966850 :                          buffer, length, &kappa);
     632     3966850 :   *decimal_exponent = -mk + kappa;
     633     3966850 :   return result;
     634             : }
     635             : 
     636             : 
     637             : // The "counted" version of grisu3 (see above) only generates requested_digits
     638             : // number of digits. This version does not generate the shortest representation,
     639             : // and with enough requested digits 0.1 will at some point print as 0.9999999...
     640             : // Grisu3 is too imprecise for real halfway cases (1.5 will not work) and
     641             : // therefore the rounding strategy for halfway cases is irrelevant.
     642     1308941 : static bool Grisu3Counted(double v,
     643             :                           int requested_digits,
     644     1308941 :                           Vector<char> buffer,
     645             :                           int* length,
     646             :                           int* decimal_exponent) {
     647     1308941 :   DiyFp w = Double(v).AsNormalizedDiyFp();
     648             :   DiyFp ten_mk;  // Cached power of ten: 10^-k
     649             :   int mk;        // -k
     650             :   int ten_mk_minimal_binary_exponent =
     651     1308941 :      kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     652             :   int ten_mk_maximal_binary_exponent =
     653     1308941 :      kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     654             :   PowersOfTenCache::GetCachedPowerForBinaryExponentRange(
     655             :       ten_mk_minimal_binary_exponent,
     656             :       ten_mk_maximal_binary_exponent,
     657     1308941 :       &ten_mk, &mk);
     658             :   DCHECK((kMinimalTargetExponent <= w.e() + ten_mk.e() +
     659             :           DiyFp::kSignificandSize) &&
     660             :          (kMaximalTargetExponent >= w.e() + ten_mk.e() +
     661             :           DiyFp::kSignificandSize));
     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.
     664             : 
     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
     667             :   // off by a small amount.
     668             :   // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w.
     669             :   // In other words: let f = scaled_w.f() and e = scaled_w.e(), then
     670             :   //           (f-1) * 2^e < w*10^k < (f+1) * 2^e
     671     1308941 :   DiyFp scaled_w = DiyFp::Times(w, ten_mk);
     672             : 
     673             :   // We now have (double) (scaled_w * 10^-mk).
     674             :   // DigitGen will generate the first requested_digits digits of scaled_w and
     675             :   // return together with a kappa such that scaled_w ~= buffer * 10^kappa. (It
     676             :   // will not always be exactly the same since DigitGenCounted only produces a
     677             :   // limited number of digits.)
     678             :   int kappa;
     679             :   bool result = DigitGenCounted(scaled_w, requested_digits,
     680     1308941 :                                 buffer, length, &kappa);
     681     1308941 :   *decimal_exponent = -mk + kappa;
     682     1308941 :   return result;
     683             : }
     684             : 
     685             : 
     686     5275791 : bool FastDtoa(double v,
     687             :               FastDtoaMode mode,
     688             :               int requested_digits,
     689             :               Vector<char> buffer,
     690             :               int* length,
     691             :               int* decimal_point) {
     692             :   DCHECK(v > 0);
     693             :   DCHECK(!Double(v).IsSpecial());
     694             : 
     695             :   bool result = false;
     696     5275791 :   int decimal_exponent = 0;
     697     5275791 :   switch (mode) {
     698             :     case FAST_DTOA_SHORTEST:
     699     3966850 :       result = Grisu3(v, buffer, length, &decimal_exponent);
     700     3966850 :       break;
     701             :     case FAST_DTOA_PRECISION:
     702             :       result = Grisu3Counted(v, requested_digits,
     703     1308941 :                              buffer, length, &decimal_exponent);
     704     1308941 :       break;
     705             :     default:
     706           0 :       UNREACHABLE();
     707             :   }
     708     5275791 :   if (result) {
     709     5091209 :     *decimal_point = *length + decimal_exponent;
     710    10182418 :     buffer[*length] = '\0';
     711             :   }
     712     5275791 :   return result;
     713             : }
     714             : 
     715             : }  // namespace internal
     716             : }  // namespace v8

Generated by: LCOV version 1.10