src/v8/src/strtod.cc

   1 // Copyright 2012 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 <stdarg.h>
   6 #include <cmath>
   7
   8 #include "src/v8.h"
   9
  10 #include "src/bignum.h"
  11 #include "src/cached-powers.h"
  12 #include "src/double.h"
  13 #include "src/globals.h"
  14 #include "src/strtod.h"
  15 #include "src/utils.h"
  16
  17 namespace v8 {
  18 namespace internal {
  19
  20 // 2^53 = 9007199254740992.
  21 // Any integer with at most 15 decimal digits will hence fit into a double
  22 // (which has a 53bit significand) without loss of precision.
  23 static const int kMaxExactDoubleIntegerDecimalDigits = 15;
  24 // 2^64 = 18446744073709551616 > 10^19
  25 static const int kMaxUint64DecimalDigits = 19;
  26
  27 // Max double: 1.7976931348623157 x 10^308
  28 // Min non-zero double: 4.9406564584124654 x 10^-324
  29 // Any x >= 10^309 is interpreted as +infinity.
  30 // Any x <= 10^-324 is interpreted as 0.
  31 // Note that 2.5e-324 (despite being smaller than the min double) will be read
  32 // as non-zero (equal to the min non-zero double).
  33 static const int kMaxDecimalPower = 309;
  34 static const int kMinDecimalPower = -324;
  35
  36 // 2^64 = 18446744073709551616
  37 static const uint64_t kMaxUint64 = V8_2PART_UINT64_C(0xFFFFFFFF, FFFFFFFF);
  38
  39
  40 static const double exact_powers_of_ten[] = {
  41   1.0,  // 10^0
  42   10.0,
  43   100.0,
  44   1000.0,
  45   10000.0,
  46   100000.0,
  47   1000000.0,
  48   10000000.0,
  49   100000000.0,
  50   1000000000.0,
  51   10000000000.0,  // 10^10
  52   100000000000.0,
  53   1000000000000.0,
  54   10000000000000.0,
  55   100000000000000.0,
  56   1000000000000000.0,
  57   10000000000000000.0,
  58   100000000000000000.0,
  59   1000000000000000000.0,
  60   10000000000000000000.0,
  61   100000000000000000000.0,  // 10^20
  62   1000000000000000000000.0,
  63   // 10^22 = 0x21e19e0c9bab2400000 = 0x878678326eac9 * 2^22
  64   10000000000000000000000.0
  65 };
  66 static const int kExactPowersOfTenSize = arraysize(exact_powers_of_ten);
  67
  68 // Maximum number of significant digits in the decimal representation.
  69 // In fact the value is 772 (see conversions.cc), but to give us some margin
  70 // we round up to 780.
  71 static const int kMaxSignificantDecimalDigits = 780;
  72
  73 static Vector<const char> TrimLeadingZeros(Vector<const char> buffer) {
  74   for (int i = 0; i < buffer.length(); i++) {
  75     if (buffer[i] != '0') {
  76       return buffer.SubVector(i, buffer.length());
  77     }
  78   }
  79   return Vector<const char>(buffer.start(), 0);
  80 }
  81
  82
  83 static Vector<const char> TrimTrailingZeros(Vector<const char> buffer) {
  84   for (int i = buffer.length() - 1; i >= 0; --i) {
  85     if (buffer[i] != '0') {
  86       return buffer.SubVector(0, i + 1);
  87     }
  88   }
  89   return Vector<const char>(buffer.start(), 0);
  90 }
  91
  92
  93 static void TrimToMaxSignificantDigits(Vector<const char> buffer,
  94                                        int exponent,
  95                                        char* significant_buffer,
  96                                        int* significant_exponent) {
  97   for (int i = 0; i < kMaxSignificantDecimalDigits - 1; ++i) {
  98     significant_buffer[i] = buffer[i];
  99   }
 100   // The input buffer has been trimmed. Therefore the last digit must be
 101   // different from '0'.
 102   DCHECK(buffer[buffer.length() - 1] != '0');
 103   // Set the last digit to be non-zero. This is sufficient to guarantee
 104   // correct rounding.
 105   significant_buffer[kMaxSignificantDecimalDigits - 1] = '1';
 106   *significant_exponent =
 107       exponent + (buffer.length() - kMaxSignificantDecimalDigits);
 108 }
 109
 110
 111 // Reads digits from the buffer and converts them to a uint64.
 112 // Reads in as many digits as fit into a uint64.
 113 // When the string starts with "1844674407370955161" no further digit is read.
 114 // Since 2^64 = 18446744073709551616 it would still be possible read another
 115 // digit if it was less or equal than 6, but this would complicate the code.
 116 static uint64_t ReadUint64(Vector<const char> buffer,
 117                            int* number_of_read_digits) {
 118   uint64_t result = 0;
 119   int i = 0;
 120   while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) {
 121     int digit = buffer[i++] - '0';
 122     DCHECK(0 <= digit && digit <= 9);
 123     result = 10 * result + digit;
 124   }
 125   *number_of_read_digits = i;
 126   return result;
 127 }
 128
 129
 130 // Reads a DiyFp from the buffer.
 131 // The returned DiyFp is not necessarily normalized.
 132 // If remaining_decimals is zero then the returned DiyFp is accurate.
 133 // Otherwise it has been rounded and has error of at most 1/2 ulp.
 134 static void ReadDiyFp(Vector<const char> buffer,
 135                       DiyFp* result,
 136                       int* remaining_decimals) {
 137   int read_digits;
 138   uint64_t significand = ReadUint64(buffer, &read_digits);
 139   if (buffer.length() == read_digits) {
 140     *result = DiyFp(significand, 0);
 141     *remaining_decimals = 0;
 142   } else {
 143     // Round the significand.
 144     if (buffer[read_digits] >= '5') {
 145       significand++;
 146     }
 147     // Compute the binary exponent.
 148     int exponent = 0;
 149     *result = DiyFp(significand, exponent);
 150     *remaining_decimals = buffer.length() - read_digits;
 151   }
 152 }
 153
 154
 155 static bool DoubleStrtod(Vector<const char> trimmed,
 156                          int exponent,
 157                          double* result) {
 158 #if (V8_TARGET_ARCH_IA32 || V8_TARGET_ARCH_X87 || defined(USE_SIMULATOR)) && \
 159     !defined(_MSC_VER)
 160   // On x86 the floating-point stack can be 64 or 80 bits wide. If it is
 161   // 80 bits wide (as is the case on Linux) then double-rounding occurs and the
 162   // result is not accurate.
 163   // We know that Windows32 with MSVC, unlike with MinGW32, uses 64 bits and is
 164   // therefore accurate.
 165   // Note that the ARM and MIPS simulators are compiled for 32bits. They
 166   // therefore exhibit the same problem.
 167   return false;
 168 #endif
 169   if (trimmed.length() <= kMaxExactDoubleIntegerDecimalDigits) {
 170     int read_digits;
 171     // The trimmed input fits into a double.
 172     // If the 10^exponent (resp. 10^-exponent) fits into a double too then we
 173     // can compute the result-double simply by multiplying (resp. dividing) the
 174     // two numbers.
 175     // This is possible because IEEE guarantees that floating-point operations
 176     // return the best possible approximation.
 177     if (exponent < 0 && -exponent < kExactPowersOfTenSize) {
 178       // 10^-exponent fits into a double.
 179       *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
 180       DCHECK(read_digits == trimmed.length());
 181       *result /= exact_powers_of_ten[-exponent];
 182       return true;
 183     }
 184     if (0 <= exponent && exponent < kExactPowersOfTenSize) {
 185       // 10^exponent fits into a double.
 186       *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
 187       DCHECK(read_digits == trimmed.length());
 188       *result *= exact_powers_of_ten[exponent];
 189       return true;
 190     }
 191     int remaining_digits =
 192         kMaxExactDoubleIntegerDecimalDigits - trimmed.length();
 193     if ((0 <= exponent) &&
 194         (exponent - remaining_digits < kExactPowersOfTenSize)) {
 195       // The trimmed string was short and we can multiply it with
 196       // 10^remaining_digits. As a result the remaining exponent now fits
 197       // into a double too.
 198       *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
 199       DCHECK(read_digits == trimmed.length());
 200       *result *= exact_powers_of_ten[remaining_digits];
 201       *result *= exact_powers_of_ten[exponent - remaining_digits];
 202       return true;
 203     }
 204   }
 205   return false;
 206 }
 207
 208
 209 // Returns 10^exponent as an exact DiyFp.
 210 // The given exponent must be in the range [1; kDecimalExponentDistance[.
 211 static DiyFp AdjustmentPowerOfTen(int exponent) {
 212   DCHECK(0 < exponent);
 213   DCHECK(exponent < PowersOfTenCache::kDecimalExponentDistance);
 214   // Simply hardcode the remaining powers for the given decimal exponent
 215   // distance.
 216   DCHECK(PowersOfTenCache::kDecimalExponentDistance == 8);
 217   switch (exponent) {
 218     case 1: return DiyFp(V8_2PART_UINT64_C(0xa0000000, 00000000), -60);
 219     case 2: return DiyFp(V8_2PART_UINT64_C(0xc8000000, 00000000), -57);
 220     case 3: return DiyFp(V8_2PART_UINT64_C(0xfa000000, 00000000), -54);
 221     case 4: return DiyFp(V8_2PART_UINT64_C(0x9c400000, 00000000), -50);
 222     case 5: return DiyFp(V8_2PART_UINT64_C(0xc3500000, 00000000), -47);
 223     case 6: return DiyFp(V8_2PART_UINT64_C(0xf4240000, 00000000), -44);
 224     case 7: return DiyFp(V8_2PART_UINT64_C(0x98968000, 00000000), -40);
 225     default:
 226       UNREACHABLE();
 227       return DiyFp(0, 0);
 228   }
 229 }
 230
 231
 232 // If the function returns true then the result is the correct double.
 233 // Otherwise it is either the correct double or the double that is just below
 234 // the correct double.
 235 static bool DiyFpStrtod(Vector<const char> buffer,
 236                         int exponent,
 237                         double* result) {
 238   DiyFp input;
 239   int remaining_decimals;
 240   ReadDiyFp(buffer, &input, &remaining_decimals);
 241   // Since we may have dropped some digits the input is not accurate.
 242   // If remaining_decimals is different than 0 than the error is at most
 243   // .5 ulp (unit in the last place).
 244   // We don't want to deal with fractions and therefore keep a common
 245   // denominator.
 246   const int kDenominatorLog = 3;
 247   const int kDenominator = 1 << kDenominatorLog;
 248   // Move the remaining decimals into the exponent.
 249   exponent += remaining_decimals;
 250   int64_t error = (remaining_decimals == 0 ? 0 : kDenominator / 2);
 251
 252   int old_e = input.e();
 253   input.Normalize();
 254   error <<= old_e - input.e();
 255
 256   DCHECK(exponent <= PowersOfTenCache::kMaxDecimalExponent);
 257   if (exponent < PowersOfTenCache::kMinDecimalExponent) {
 258     *result = 0.0;
 259     return true;
 260   }
 261   DiyFp cached_power;
 262   int cached_decimal_exponent;
 263   PowersOfTenCache::GetCachedPowerForDecimalExponent(exponent,
 264                                                      &cached_power,
 265                                                      &cached_decimal_exponent);
 266
 267   if (cached_decimal_exponent != exponent) {
 268     int adjustment_exponent = exponent - cached_decimal_exponent;
 269     DiyFp adjustment_power = AdjustmentPowerOfTen(adjustment_exponent);
 270     input.Multiply(adjustment_power);
 271     if (kMaxUint64DecimalDigits - buffer.length() >= adjustment_exponent) {
 272       // The product of input with the adjustment power fits into a 64 bit
 273       // integer.
 274       DCHECK(DiyFp::kSignificandSize == 64);
 275     } else {
 276       // The adjustment power is exact. There is hence only an error of 0.5.
 277       error += kDenominator / 2;
 278     }
 279   }
 280
 281   input.Multiply(cached_power);
 282   // The error introduced by a multiplication of a*b equals
 283   //   error_a + error_b + error_a*error_b/2^64 + 0.5
 284   // Substituting a with 'input' and b with 'cached_power' we have
 285   //   error_b = 0.5  (all cached powers have an error of less than 0.5 ulp),
 286   //   error_ab = 0 or 1 / kDenominator > error_a*error_b/ 2^64
 287   int error_b = kDenominator / 2;
 288   int error_ab = (error == 0 ? 0 : 1);  // We round up to 1.
 289   int fixed_error = kDenominator / 2;
 290   error += error_b + error_ab + fixed_error;
 291
 292   old_e = input.e();
 293   input.Normalize();
 294   error <<= old_e - input.e();
 295
 296   // See if the double's significand changes if we add/subtract the error.
 297   int order_of_magnitude = DiyFp::kSignificandSize + input.e();
 298   int effective_significand_size =
 299       Double::SignificandSizeForOrderOfMagnitude(order_of_magnitude);
 300   int precision_digits_count =
 301       DiyFp::kSignificandSize - effective_significand_size;
 302   if (precision_digits_count + kDenominatorLog >= DiyFp::kSignificandSize) {
 303     // This can only happen for very small denormals. In this case the
 304     // half-way multiplied by the denominator exceeds the range of an uint64.
 305     // Simply shift everything to the right.
 306     int shift_amount = (precision_digits_count + kDenominatorLog) -
 307         DiyFp::kSignificandSize + 1;
 308     input.set_f(input.f() >> shift_amount);
 309     input.set_e(input.e() + shift_amount);
 310     // We add 1 for the lost precision of error, and kDenominator for
 311     // the lost precision of input.f().
 312     error = (error >> shift_amount) + 1 + kDenominator;
 313     precision_digits_count -= shift_amount;
 314   }
 315   // We use uint64_ts now. This only works if the DiyFp uses uint64_ts too.
 316   DCHECK(DiyFp::kSignificandSize == 64);
 317   DCHECK(precision_digits_count < 64);
 318   uint64_t one64 = 1;
 319   uint64_t precision_bits_mask = (one64 << precision_digits_count) - 1;
 320   uint64_t precision_bits = input.f() & precision_bits_mask;
 321   uint64_t half_way = one64 << (precision_digits_count - 1);
 322   precision_bits *= kDenominator;
 323   half_way *= kDenominator;
 324   DiyFp rounded_input(input.f() >> precision_digits_count,
 325                       input.e() + precision_digits_count);
 326   if (precision_bits >= half_way + error) {
 327     rounded_input.set_f(rounded_input.f() + 1);
 328   }
 329   // If the last_bits are too close to the half-way case than we are too
 330   // inaccurate and round down. In this case we return false so that we can
 331   // fall back to a more precise algorithm.
 332
 333   *result = Double(rounded_input).value();
 334   if (half_way - error < precision_bits && precision_bits < half_way + error) {
 335     // Too imprecise. The caller will have to fall back to a slower version.
 336     // However the returned number is guaranteed to be either the correct
 337     // double, or the next-lower double.
 338     return false;
 339   } else {
 340     return true;
 341   }
 342 }
 343
 344
 345 // Returns the correct double for the buffer*10^exponent.
 346 // The variable guess should be a close guess that is either the correct double
 347 // or its lower neighbor (the nearest double less than the correct one).
 348 // Preconditions:
 349 //   buffer.length() + exponent <= kMaxDecimalPower + 1
 350 //   buffer.length() + exponent > kMinDecimalPower
 351 //   buffer.length() <= kMaxDecimalSignificantDigits
 352 static double BignumStrtod(Vector<const char> buffer,
 353                            int exponent,
 354                            double guess) {
 355   if (guess == V8_INFINITY) {
 356     return guess;
 357   }
 358
 359   DiyFp upper_boundary = Double(guess).UpperBoundary();
 360
 361   DCHECK(buffer.length() + exponent <= kMaxDecimalPower + 1);
 362   DCHECK(buffer.length() + exponent > kMinDecimalPower);
 363   DCHECK(buffer.length() <= kMaxSignificantDecimalDigits);
 364   // Make sure that the Bignum will be able to hold all our numbers.
 365   // Our Bignum implementation has a separate field for exponents. Shifts will
 366   // consume at most one bigit (< 64 bits).
 367   // ln(10) == 3.3219...
 368   DCHECK(((kMaxDecimalPower + 1) * 333 / 100) < Bignum::kMaxSignificantBits);
 369   Bignum input;
 370   Bignum boundary;
 371   input.AssignDecimalString(buffer);
 372   boundary.AssignUInt64(upper_boundary.f());
 373   if (exponent >= 0) {
 374     input.MultiplyByPowerOfTen(exponent);
 375   } else {
 376     boundary.MultiplyByPowerOfTen(-exponent);
 377   }
 378   if (upper_boundary.e() > 0) {
 379     boundary.ShiftLeft(upper_boundary.e());
 380   } else {
 381     input.ShiftLeft(-upper_boundary.e());
 382   }
 383   int comparison = Bignum::Compare(input, boundary);
 384   if (comparison < 0) {
 385     return guess;
 386   } else if (comparison > 0) {
 387     return Double(guess).NextDouble();
 388   } else if ((Double(guess).Significand() & 1) == 0) {
 389     // Round towards even.
 390     return guess;
 391   } else {
 392     return Double(guess).NextDouble();
 393   }
 394 }
 395
 396
 397 double Strtod(Vector<const char> buffer, int exponent) {
 398   Vector<const char> left_trimmed = TrimLeadingZeros(buffer);
 399   Vector<const char> trimmed = TrimTrailingZeros(left_trimmed);
 400   exponent += left_trimmed.length() - trimmed.length();
 401   if (trimmed.length() == 0) return 0.0;
 402   if (trimmed.length() > kMaxSignificantDecimalDigits) {
 403     char significant_buffer[kMaxSignificantDecimalDigits];
 404     int significant_exponent;
 405     TrimToMaxSignificantDigits(trimmed, exponent,
 406                                significant_buffer, &significant_exponent);
 407     return Strtod(Vector<const char>(significant_buffer,
 408                                      kMaxSignificantDecimalDigits),
 409                   significant_exponent);
 410   }
 411   if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) return V8_INFINITY;
 412   if (exponent + trimmed.length() <= kMinDecimalPower) return 0.0;
 413
 414   double guess;
 415   if (DoubleStrtod(trimmed, exponent, &guess) ||
 416       DiyFpStrtod(trimmed, exponent, &guess)) {
 417     return guess;
 418   }
 419   return BignumStrtod(trimmed, exponent, guess);
 420 }
 421
 422 } }  // namespace v8::internal