LCOV - code coverage report
Current view: top level - src - fast-dtoa.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 160 170 94.1 %
Date: 2019-04-17 Functions: 9 9 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     2133138 : 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     2133138 :   uint64_t small_distance = distance_too_high_w - unit;
      51     2133138 :   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     2132908 :   while (rest < small_distance &&  // Negated condition 1
     125     4779444 :          unsafe_interval - rest >= ten_kappa &&  // Negated condition 2
     126     2387172 :          (rest + ten_kappa < small_distance ||  // buffer{-1} > w_high
     127      851697 :           small_distance - rest >= rest + ten_kappa - small_distance)) {
     128     2221662 :     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     3294864 :   if (rest < big_distance &&
     136     1590933 :       unsafe_interval - rest >= ten_kappa &&
     137      858414 :       (rest + ten_kappa < big_distance ||
     138      429207 :        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     2128033 :   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      936211 : 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      936211 :   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      907799 :   if (ten_kappa - unit <= unit) return false;
     181             :   // If 2 * (rest + unit) <= 10^kappa we can safely round down.
     182      893949 :   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      452104 :   if ((rest > unit) && (ten_kappa - (rest - unit) <= (rest - unit))) {
     187             :     // Increment the last digit recursively until we find a non '9' digit.
     188      864124 :     buffer[length - 1]++;
     189      478865 :     for (int i = length - 1; i > 0; --i) {
     190      911476 :       if (buffer[i] != '0' + 10) break;
     191       46803 :       buffer[i] = '0';
     192       93606 :       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      432062 :     if (buffer[0] == '0' + 10) {
     199        1137 :       buffer[0] = '1';
     200        1137 :       (*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     3138803 : static void BiggestPowerTen(uint32_t number,
     221             :                             int number_bits,
     222             :                             uint32_t* power,
     223             :                             int* exponent) {
     224     3138803 :   switch (number_bits) {
     225             :     case 32:
     226             :     case 31:
     227             :     case 30:
     228       47051 :       if (kTen9 <= number) {
     229           0 :         *power = kTen9;
     230           0 :         *exponent = 9;
     231           0 :         break;
     232             :       }
     233             :       V8_FALLTHROUGH;
     234             :     case 29:
     235             :     case 28:
     236             :     case 27:
     237      304437 :       if (kTen8 <= number) {
     238      218732 :         *power = kTen8;
     239      218732 :         *exponent = 8;
     240      218732 :         break;
     241             :       }
     242             :       V8_FALLTHROUGH;
     243             :     case 26:
     244             :     case 25:
     245             :     case 24:
     246      365127 :       if (kTen7 <= number) {
     247      273486 :         *power = kTen7;
     248      273486 :         *exponent = 7;
     249      273486 :         break;
     250             :       }
     251             :       V8_FALLTHROUGH;
     252             :     case 23:
     253             :     case 22:
     254             :     case 21:
     255             :     case 20:
     256     1032697 :       if (kTen6 <= number) {
     257      473628 :         *power = kTen6;
     258      473628 :         *exponent = 6;
     259      473628 :         break;
     260             :       }
     261             :       V8_FALLTHROUGH;
     262             :     case 19:
     263             :     case 18:
     264             :     case 17:
     265     1056647 :       if (kTen5 <= number) {
     266      906561 :         *power = kTen5;
     267      906561 :         *exponent = 5;
     268      906561 :         break;
     269             :       }
     270             :       V8_FALLTHROUGH;
     271             :     case 16:
     272             :     case 15:
     273             :     case 14:
     274      430296 :       if (kTen4 <= number) {
     275      360882 :         *power = kTen4;
     276      360882 :         *exponent = 4;
     277      360882 :         break;
     278             :       }
     279             :       V8_FALLTHROUGH;
     280             :     case 13:
     281             :     case 12:
     282             :     case 11:
     283             :     case 10:
     284      411073 :       if (1000 <= number) {
     285      291779 :         *power = 1000;
     286      291779 :         *exponent = 3;
     287      291779 :         break;
     288             :       }
     289             :       V8_FALLTHROUGH;
     290             :     case 9:
     291             :     case 8:
     292             :     case 7:
     293      366010 :       if (100 <= number) {
     294      274705 :         *power = 100;
     295      274705 :         *exponent = 2;
     296      274705 :         break;
     297             :       }
     298             :       V8_FALLTHROUGH;
     299             :     case 6:
     300             :     case 5:
     301             :     case 4:
     302      339030 :       if (10 <= number) {
     303      271702 :         *power = 10;
     304      271702 :         *exponent = 1;
     305      271702 :         break;
     306             :       }
     307             :       V8_FALLTHROUGH;
     308             :     case 3:
     309             :     case 2:
     310             :     case 1:
     311       67328 :       if (1 <= number) {
     312       67328 :         *power = 1;
     313       67328 :         *exponent = 0;
     314       67328 :         break;
     315             :       }
     316             :       V8_FALLTHROUGH;
     317             :     case 0:
     318           0 :       *power = 0;
     319           0 :       *exponent = -1;
     320           0 :       break;
     321             :     default:
     322             :       // Following assignments are here to silence compiler warnings.
     323           0 :       *power = 0;
     324           0 :       *exponent = 0;
     325           0 :       UNREACHABLE();
     326             :   }
     327     3138803 : }
     328             : 
     329             : // Generates the digits of input number w.
     330             : // w is a floating-point number (DiyFp), consisting of a significand and an
     331             : // exponent. Its exponent is bounded by kMinimalTargetExponent and
     332             : // kMaximalTargetExponent.
     333             : //       Hence -60 <= w.e() <= -32.
     334             : //
     335             : // Returns false if it fails, in which case the generated digits in the buffer
     336             : // should not be used.
     337             : // Preconditions:
     338             : //  * low, w and high are correct up to 1 ulp (unit in the last place). That
     339             : //    is, their error must be less than a unit of their last digits.
     340             : //  * low.e() == w.e() == high.e()
     341             : //  * low < w < high, and taking into account their error: low~ <= high~
     342             : //  * kMinimalTargetExponent <= w.e() <= kMaximalTargetExponent
     343             : // Postconditions: returns false if procedure fails.
     344             : //   otherwise:
     345             : //     * buffer is not null-terminated, but len contains the number of digits.
     346             : //     * buffer contains the shortest possible decimal digit-sequence
     347             : //       such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the
     348             : //       correct values of low and high (without their error).
     349             : //     * if more than one decimal representation gives the minimal number of
     350             : //       decimal digits then the one closest to W (where W is the correct value
     351             : //       of w) is chosen.
     352             : // Remark: this procedure takes into account the imprecision of its input
     353             : //   numbers. If the precision is not enough to guarantee all the postconditions
     354             : //   then false is returned. This usually happens rarely (~0.5%).
     355             : //
     356             : // Say, for the sake of example, that
     357             : //   w.e() == -48, and w.f() == 0x1234567890ABCDEF
     358             : // w's value can be computed by w.f() * 2^w.e()
     359             : // We can obtain w's integral digits by simply shifting w.f() by -w.e().
     360             : //  -> w's integral part is 0x1234
     361             : //  w's fractional part is therefore 0x567890ABCDEF.
     362             : // Printing w's integral part is easy (simply print 0x1234 in decimal).
     363             : // In order to print its fraction we repeatedly multiply the fraction by 10 and
     364             : // get each digit. Example the first digit after the point would be computed by
     365             : //   (0x567890ABCDEF * 10) >> 48. -> 3
     366             : // The whole thing becomes slightly more complicated because we want to stop
     367             : // once we have enough digits. That is, once the digits inside the buffer
     368             : // represent 'w' we can stop. Everything inside the interval low - high
     369             : // represents w. However we have to pay attention to low, high and w's
     370             : // imprecision.
     371     2133139 : static bool DigitGen(DiyFp low,
     372             :                      DiyFp w,
     373             :                      DiyFp high,
     374             :                      Vector<char> buffer,
     375             :                      int* length,
     376             :                      int* kappa) {
     377             :   DCHECK(low.e() == w.e() && w.e() == high.e());
     378             :   DCHECK(low.f() + 1 <= high.f() - 1);
     379             :   DCHECK(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent);
     380             :   // low, w and high are imprecise, but by less than one ulp (unit in the last
     381             :   // place).
     382             :   // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that
     383             :   // the new numbers are outside of the interval we want the final
     384             :   // representation to lie in.
     385             :   // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield
     386             :   // numbers that are certain to lie in the interval. We will use this fact
     387             :   // later on.
     388             :   // We will now start by generating the digits within the uncertain
     389             :   // interval. Later we will weed out representations that lie outside the safe
     390             :   // interval and thus _might_ lie outside the correct interval.
     391             :   uint64_t unit = 1;
     392     2133139 :   DiyFp too_low = DiyFp(low.f() - unit, low.e());
     393     2133139 :   DiyFp too_high = DiyFp(high.f() + unit, high.e());
     394             :   // too_low and too_high are guaranteed to lie outside the interval we want the
     395             :   // generated number in.
     396             :   DiyFp unsafe_interval = DiyFp::Minus(too_high, too_low);
     397             :   // We now cut the input number into two parts: the integral digits and the
     398             :   // fractionals. We will not write any decimal separator though, but adapt
     399             :   // kappa instead.
     400             :   // Reminder: we are currently computing the digits (stored inside the buffer)
     401             :   // such that:   too_low < buffer * 10^kappa < too_high
     402             :   // We use too_high for the digit_generation and stop as soon as possible.
     403             :   // If we stop early we effectively round down.
     404     2133139 :   DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e());
     405             :   // Division by one is a shift.
     406     2133139 :   uint32_t integrals = static_cast<uint32_t>(too_high.f() >> -one.e());
     407             :   // Modulo by one is an and.
     408     2133139 :   uint64_t fractionals = too_high.f() & (one.f() - 1);
     409             :   uint32_t divisor;
     410             :   int divisor_exponent;
     411     2133139 :   BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()),
     412     2133139 :                   &divisor, &divisor_exponent);
     413     2133138 :   *kappa = divisor_exponent + 1;
     414     2133138 :   *length = 0;
     415             :   // Loop invariant: buffer = too_high / 10^kappa  (integer division)
     416             :   // The invariant holds for the first iteration: kappa has been initialized
     417             :   // with the divisor exponent + 1. And the divisor is the biggest power of ten
     418             :   // that is smaller than integrals.
     419    13892970 :   while (*kappa > 0) {
     420    11834387 :     int digit = integrals / divisor;
     421    23668774 :     buffer[*length] = '0' + digit;
     422    11834387 :     (*length)++;
     423    11834387 :     integrals %= divisor;
     424    11834387 :     (*kappa)--;
     425             :     // Note that kappa now equals the exponent of the divisor and that the
     426             :     // invariant thus holds again.
     427             :     uint64_t rest =
     428    11834387 :         (static_cast<uint64_t>(integrals) << -one.e()) + fractionals;
     429             :     // Invariant: too_high = buffer * 10^kappa + DiyFp(rest, one.e())
     430             :     // Reminder: unsafe_interval.e() == one.e()
     431    11834387 :     if (rest < unsafe_interval.f()) {
     432             :       // Rounding down (by not emitting the remaining digits) yields a number
     433             :       // that lies within the unsafe interval.
     434      149110 :       return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f(),
     435             :                        unsafe_interval.f(), rest,
     436       74555 :                        static_cast<uint64_t>(divisor) << -one.e(), unit);
     437             :     }
     438    11759832 :     divisor /= 10;
     439             :   }
     440             : 
     441             :   // The integrals have been generated. We are at the point of the decimal
     442             :   // separator. In the following loop we simply multiply the remaining digits by
     443             :   // 10 and divide by one. We just need to pay attention to multiply associated
     444             :   // data (like the interval or 'unit'), too.
     445             :   // Note that the multiplication by 10 does not overflow, because w.e >= -60
     446             :   // and thus one.e >= -60.
     447             :   DCHECK_GE(one.e(), -60);
     448             :   DCHECK(fractionals < one.f());
     449             :   DCHECK(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f());
     450             :   while (true) {
     451    21280685 :     fractionals *= 10;
     452    21280685 :     unit *= 10;
     453    21280685 :     unsafe_interval.set_f(unsafe_interval.f() * 10);
     454             :     // Integer division by one.
     455    21280685 :     int digit = static_cast<int>(fractionals >> -one.e());
     456    42561370 :     buffer[*length] = '0' + digit;
     457    21280685 :     (*length)++;
     458    21280685 :     fractionals &= one.f() - 1;  // Modulo by one.
     459    21280685 :     (*kappa)--;
     460    21280685 :     if (fractionals < unsafe_interval.f()) {
     461     2058583 :       return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f() * unit,
     462     2058583 :                        unsafe_interval.f(), fractionals, one.f(), unit);
     463             :     }
     464             :   }
     465             : }
     466             : 
     467             : 
     468             : 
     469             : // Generates (at most) requested_digits of input number w.
     470             : // w is a floating-point number (DiyFp), consisting of a significand and an
     471             : // exponent. Its exponent is bounded by kMinimalTargetExponent and
     472             : // kMaximalTargetExponent.
     473             : //       Hence -60 <= w.e() <= -32.
     474             : //
     475             : // Returns false if it fails, in which case the generated digits in the buffer
     476             : // should not be used.
     477             : // Preconditions:
     478             : //  * w is correct up to 1 ulp (unit in the last place). That
     479             : //    is, its error must be strictly less than a unit of its last digit.
     480             : //  * kMinimalTargetExponent <= w.e() <= kMaximalTargetExponent
     481             : //
     482             : // Postconditions: returns false if procedure fails.
     483             : //   otherwise:
     484             : //     * buffer is not null-terminated, but length contains the number of
     485             : //       digits.
     486             : //     * the representation in buffer is the most precise representation of
     487             : //       requested_digits digits.
     488             : //     * buffer contains at most requested_digits digits of w. If there are less
     489             : //       than requested_digits digits then some trailing '0's have been removed.
     490             : //     * kappa is such that
     491             : //            w = buffer * 10^kappa + eps with |eps| < 10^kappa / 2.
     492             : //
     493             : // Remark: This procedure takes into account the imprecision of its input
     494             : //   numbers. If the precision is not enough to guarantee all the postconditions
     495             : //   then false is returned. This usually happens rarely, but the failure-rate
     496             : //   increases with higher requested_digits.
     497     1005665 : static bool DigitGenCounted(DiyFp w,
     498             :                             int requested_digits,
     499             :                             Vector<char> buffer,
     500             :                             int* length,
     501             :                             int* kappa) {
     502             :   DCHECK(kMinimalTargetExponent <= w.e() && w.e() <= kMaximalTargetExponent);
     503             :   DCHECK_GE(kMinimalTargetExponent, -60);
     504             :   DCHECK_LE(kMaximalTargetExponent, -32);
     505             :   // w is assumed to have an error less than 1 unit. Whenever w is scaled we
     506             :   // also scale its error.
     507             :   uint64_t w_error = 1;
     508             :   // We cut the input number into two parts: the integral digits and the
     509             :   // fractional digits. We don't emit any decimal separator, but adapt kappa
     510             :   // instead. Example: instead of writing "1.2" we put "12" into the buffer and
     511             :   // increase kappa by 1.
     512     1005665 :   DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e());
     513             :   // Division by one is a shift.
     514     1005665 :   uint32_t integrals = static_cast<uint32_t>(w.f() >> -one.e());
     515             :   // Modulo by one is an and.
     516     1005665 :   uint64_t fractionals = w.f() & (one.f() - 1);
     517             :   uint32_t divisor;
     518             :   int divisor_exponent;
     519     1005665 :   BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()),
     520     1005665 :                   &divisor, &divisor_exponent);
     521     1005665 :   *kappa = divisor_exponent + 1;
     522     1005665 :   *length = 0;
     523             : 
     524             :   // Loop invariant: buffer = w / 10^kappa  (integer division)
     525             :   // The invariant holds for the first iteration: kappa has been initialized
     526             :   // with the divisor exponent + 1. And the divisor is the biggest power of ten
     527             :   // that is smaller than 'integrals'.
     528     5386015 :   while (*kappa > 0) {
     529     4634081 :     int digit = integrals / divisor;
     530     9268162 :     buffer[*length] = '0' + digit;
     531     4634081 :     (*length)++;
     532     4634081 :     requested_digits--;
     533     4634081 :     integrals %= divisor;
     534     4634081 :     (*kappa)--;
     535             :     // Note that kappa now equals the exponent of the divisor and that the
     536             :     // invariant thus holds again.
     537     4634081 :     if (requested_digits == 0) break;
     538     4380350 :     divisor /= 10;
     539             :   }
     540             : 
     541     1005665 :   if (requested_digits == 0) {
     542             :     uint64_t rest =
     543      253731 :         (static_cast<uint64_t>(integrals) << -one.e()) + fractionals;
     544      253731 :     return RoundWeedCounted(buffer, *length, rest,
     545             :                             static_cast<uint64_t>(divisor) << -one.e(), w_error,
     546      253731 :                             kappa);
     547             :   }
     548             : 
     549             :   // The integrals have been generated. We are at the point of the decimal
     550             :   // separator. In the following loop we simply multiply the remaining digits by
     551             :   // 10 and divide by one. We just need to pay attention to multiply associated
     552             :   // data (the 'unit'), too.
     553             :   // Note that the multiplication by 10 does not overflow, because w.e >= -60
     554             :   // and thus one.e >= -60.
     555             :   DCHECK_GE(one.e(), -60);
     556             :   DCHECK(fractionals < one.f());
     557             :   DCHECK(V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF) / 10 >= one.f());
     558     7063305 :   while (requested_digits > 0 && fractionals > w_error) {
     559     6311371 :     fractionals *= 10;
     560     6311371 :     w_error *= 10;
     561             :     // Integer division by one.
     562     6311371 :     int digit = static_cast<int>(fractionals >> -one.e());
     563    12622742 :     buffer[*length] = '0' + digit;
     564     6311371 :     (*length)++;
     565     6311371 :     requested_digits--;
     566     6311371 :     fractionals &= one.f() - 1;  // Modulo by one.
     567     6311371 :     (*kappa)--;
     568             :   }
     569      751934 :   if (requested_digits != 0) return false;
     570      682480 :   return RoundWeedCounted(buffer, *length, fractionals, one.f(), w_error,
     571      682480 :                           kappa);
     572             : }
     573             : 
     574             : 
     575             : // Provides a decimal representation of v.
     576             : // Returns true if it succeeds, otherwise the result cannot be trusted.
     577             : // There will be *length digits inside the buffer (not null-terminated).
     578             : // If the function returns true then
     579             : //        v == (double) (buffer * 10^decimal_exponent).
     580             : // The digits in the buffer are the shortest representation possible: no
     581             : // 0.09999999999999999 instead of 0.1. The shorter representation will even be
     582             : // chosen even if the longer one would be closer to v.
     583             : // The last digit will be closest to the actual v. That is, even if several
     584             : // digits might correctly yield 'v' when read again, the closest will be
     585             : // computed.
     586     2133139 : static bool Grisu3(double v,
     587             :                    Vector<char> buffer,
     588             :                    int* length,
     589             :                    int* decimal_exponent) {
     590     2133139 :   DiyFp w = Double(v).AsNormalizedDiyFp();
     591             :   // boundary_minus and boundary_plus are the boundaries between v and its
     592             :   // closest floating-point neighbors. Any number strictly between
     593             :   // boundary_minus and boundary_plus will round to v when convert to a double.
     594             :   // Grisu3 will never output representations that lie exactly on a boundary.
     595             :   DiyFp boundary_minus, boundary_plus;
     596     2133138 :   Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus);
     597             :   DCHECK(boundary_plus.e() == w.e());
     598             :   DiyFp ten_mk;  // Cached power of ten: 10^-k
     599             :   int mk;        // -k
     600             :   int ten_mk_minimal_binary_exponent =
     601     2133138 :      kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     602             :   int ten_mk_maximal_binary_exponent =
     603     2133138 :      kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     604             :   PowersOfTenCache::GetCachedPowerForBinaryExponentRange(
     605             :       ten_mk_minimal_binary_exponent,
     606             :       ten_mk_maximal_binary_exponent,
     607     2133138 :       &ten_mk, &mk);
     608             :   DCHECK((kMinimalTargetExponent <= w.e() + ten_mk.e() +
     609             :           DiyFp::kSignificandSize) &&
     610             :          (kMaximalTargetExponent >= w.e() + ten_mk.e() +
     611             :           DiyFp::kSignificandSize));
     612             :   // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a
     613             :   // 64 bit significand and ten_mk is thus only precise up to 64 bits.
     614             : 
     615             :   // The DiyFp::Times procedure rounds its result, and ten_mk is approximated
     616             :   // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now
     617             :   // off by a small amount.
     618             :   // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w.
     619             :   // In other words: let f = scaled_w.f() and e = scaled_w.e(), then
     620             :   //           (f-1) * 2^e < w*10^k < (f+1) * 2^e
     621             :   DiyFp scaled_w = DiyFp::Times(w, ten_mk);
     622             :   DCHECK(scaled_w.e() ==
     623             :          boundary_plus.e() + ten_mk.e() + DiyFp::kSignificandSize);
     624             :   // In theory it would be possible to avoid some recomputations by computing
     625             :   // the difference between w and boundary_minus/plus (a power of 2) and to
     626             :   // compute scaled_boundary_minus/plus by subtracting/adding from
     627             :   // scaled_w. However the code becomes much less readable and the speed
     628             :   // enhancements are not terriffic.
     629             :   DiyFp scaled_boundary_minus = DiyFp::Times(boundary_minus, ten_mk);
     630             :   DiyFp scaled_boundary_plus  = DiyFp::Times(boundary_plus,  ten_mk);
     631             : 
     632             :   // DigitGen will generate the digits of scaled_w. Therefore we have
     633             :   // v == (double) (scaled_w * 10^-mk).
     634             :   // Set decimal_exponent == -mk and pass it to DigitGen. If scaled_w is not an
     635             :   // integer than it will be updated. For instance if scaled_w == 1.23 then
     636             :   // the buffer will be filled with "123" und the decimal_exponent will be
     637             :   // decreased by 2.
     638             :   int kappa;
     639             :   bool result = DigitGen(scaled_boundary_minus, scaled_w, scaled_boundary_plus,
     640     2133139 :                          buffer, length, &kappa);
     641     2133138 :   *decimal_exponent = -mk + kappa;
     642     2133138 :   return result;
     643             : }
     644             : 
     645             : 
     646             : // The "counted" version of grisu3 (see above) only generates requested_digits
     647             : // number of digits. This version does not generate the shortest representation,
     648             : // and with enough requested digits 0.1 will at some point print as 0.9999999...
     649             : // Grisu3 is too imprecise for real halfway cases (1.5 will not work) and
     650             : // therefore the rounding strategy for halfway cases is irrelevant.
     651     1005665 : static bool Grisu3Counted(double v,
     652             :                           int requested_digits,
     653             :                           Vector<char> buffer,
     654             :                           int* length,
     655             :                           int* decimal_exponent) {
     656     1005665 :   DiyFp w = Double(v).AsNormalizedDiyFp();
     657             :   DiyFp ten_mk;  // Cached power of ten: 10^-k
     658             :   int mk;        // -k
     659             :   int ten_mk_minimal_binary_exponent =
     660     1005665 :      kMinimalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     661             :   int ten_mk_maximal_binary_exponent =
     662     1005665 :      kMaximalTargetExponent - (w.e() + DiyFp::kSignificandSize);
     663             :   PowersOfTenCache::GetCachedPowerForBinaryExponentRange(
     664             :       ten_mk_minimal_binary_exponent,
     665             :       ten_mk_maximal_binary_exponent,
     666     1005665 :       &ten_mk, &mk);
     667             :   DCHECK((kMinimalTargetExponent <= w.e() + ten_mk.e() +
     668             :           DiyFp::kSignificandSize) &&
     669             :          (kMaximalTargetExponent >= w.e() + ten_mk.e() +
     670             :           DiyFp::kSignificandSize));
     671             :   // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a
     672             :   // 64 bit significand and ten_mk is thus only precise up to 64 bits.
     673             : 
     674             :   // The DiyFp::Times procedure rounds its result, and ten_mk is approximated
     675             :   // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now
     676             :   // off by a small amount.
     677             :   // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w.
     678             :   // In other words: let f = scaled_w.f() and e = scaled_w.e(), then
     679             :   //           (f-1) * 2^e < w*10^k < (f+1) * 2^e
     680             :   DiyFp scaled_w = DiyFp::Times(w, ten_mk);
     681             : 
     682             :   // We now have (double) (scaled_w * 10^-mk).
     683             :   // DigitGen will generate the first requested_digits digits of scaled_w and
     684             :   // return together with a kappa such that scaled_w ~= buffer * 10^kappa. (It
     685             :   // will not always be exactly the same since DigitGenCounted only produces a
     686             :   // limited number of digits.)
     687             :   int kappa;
     688             :   bool result = DigitGenCounted(scaled_w, requested_digits,
     689     1005665 :                                 buffer, length, &kappa);
     690     1005665 :   *decimal_exponent = -mk + kappa;
     691     1005665 :   return result;
     692             : }
     693             : 
     694             : 
     695     3138804 : bool FastDtoa(double v,
     696             :               FastDtoaMode mode,
     697             :               int requested_digits,
     698             :               Vector<char> buffer,
     699             :               int* length,
     700             :               int* decimal_point) {
     701             :   DCHECK_GT(v, 0);
     702             :   DCHECK(!Double(v).IsSpecial());
     703             : 
     704             :   bool result = false;
     705     3138804 :   int decimal_exponent = 0;
     706     3138804 :   switch (mode) {
     707             :     case FAST_DTOA_SHORTEST:
     708     2133139 :       result = Grisu3(v, buffer, length, &decimal_exponent);
     709     2133137 :       break;
     710             :     case FAST_DTOA_PRECISION:
     711             :       result = Grisu3Counted(v, requested_digits,
     712     1005665 :                              buffer, length, &decimal_exponent);
     713     1005665 :       break;
     714             :     default:
     715           0 :       UNREACHABLE();
     716             :   }
     717     3138802 :   if (result) {
     718     2997391 :     *decimal_point = *length + decimal_exponent;
     719     5994782 :     buffer[*length] = '\0';
     720             :   }
     721     3138802 :   return result;
     722             : }
     723             : 
     724             : }  // namespace internal
     725      122004 : }  // namespace v8

Generated by: LCOV version 1.10