1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/double-conversion/strtod.cc Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,556 @@
1.4 +// Copyright 2010 the V8 project authors. All rights reserved.
1.5 +// Redistribution and use in source and binary forms, with or without
1.6 +// modification, are permitted provided that the following conditions are
1.7 +// met:
1.8 +//
1.9 +// * Redistributions of source code must retain the above copyright
1.10 +// notice, this list of conditions and the following disclaimer.
1.11 +// * Redistributions in binary form must reproduce the above
1.12 +// copyright notice, this list of conditions and the following
1.13 +// disclaimer in the documentation and/or other materials provided
1.14 +// with the distribution.
1.15 +// * Neither the name of Google Inc. nor the names of its
1.16 +// contributors may be used to endorse or promote products derived
1.17 +// from this software without specific prior written permission.
1.18 +//
1.19 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.20 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.21 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.22 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.23 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.24 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.25 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.26 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.27 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.28 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.29 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.30 +
1.31 +#include <stdarg.h>
1.32 +#include <limits.h>
1.33 +
1.34 +#include "strtod.h"
1.35 +#include "bignum.h"
1.36 +#include "cached-powers.h"
1.37 +#include "ieee.h"
1.38 +
1.39 +namespace double_conversion {
1.40 +
1.41 +// 2^53 = 9007199254740992.
1.42 +// Any integer with at most 15 decimal digits will hence fit into a double
1.43 +// (which has a 53bit significand) without loss of precision.
1.44 +static const int kMaxExactDoubleIntegerDecimalDigits = 15;
1.45 +// 2^64 = 18446744073709551616 > 10^19
1.46 +static const int kMaxUint64DecimalDigits = 19;
1.47 +
1.48 +// Max double: 1.7976931348623157 x 10^308
1.49 +// Min non-zero double: 4.9406564584124654 x 10^-324
1.50 +// Any x >= 10^309 is interpreted as +infinity.
1.51 +// Any x <= 10^-324 is interpreted as 0.
1.52 +// Note that 2.5e-324 (despite being smaller than the min double) will be read
1.53 +// as non-zero (equal to the min non-zero double).
1.54 +static const int kMaxDecimalPower = 309;
1.55 +static const int kMinDecimalPower = -324;
1.56 +
1.57 +// 2^64 = 18446744073709551616
1.58 +static const uint64_t kMaxUint64 = UINT64_2PART_C(0xFFFFFFFF, FFFFFFFF);
1.59 +
1.60 +
1.61 +static const double exact_powers_of_ten[] = {
1.62 + 1.0, // 10^0
1.63 + 10.0,
1.64 + 100.0,
1.65 + 1000.0,
1.66 + 10000.0,
1.67 + 100000.0,
1.68 + 1000000.0,
1.69 + 10000000.0,
1.70 + 100000000.0,
1.71 + 1000000000.0,
1.72 + 10000000000.0, // 10^10
1.73 + 100000000000.0,
1.74 + 1000000000000.0,
1.75 + 10000000000000.0,
1.76 + 100000000000000.0,
1.77 + 1000000000000000.0,
1.78 + 10000000000000000.0,
1.79 + 100000000000000000.0,
1.80 + 1000000000000000000.0,
1.81 + 10000000000000000000.0,
1.82 + 100000000000000000000.0, // 10^20
1.83 + 1000000000000000000000.0,
1.84 + // 10^22 = 0x21e19e0c9bab2400000 = 0x878678326eac9 * 2^22
1.85 + 10000000000000000000000.0
1.86 +};
1.87 +static const int kExactPowersOfTenSize = ARRAY_SIZE(exact_powers_of_ten);
1.88 +
1.89 +// Maximum number of significant digits in the decimal representation.
1.90 +// In fact the value is 772 (see conversions.cc), but to give us some margin
1.91 +// we round up to 780.
1.92 +static const int kMaxSignificantDecimalDigits = 780;
1.93 +
1.94 +static Vector<const char> TrimLeadingZeros(Vector<const char> buffer) {
1.95 + for (int i = 0; i < buffer.length(); i++) {
1.96 + if (buffer[i] != '0') {
1.97 + return buffer.SubVector(i, buffer.length());
1.98 + }
1.99 + }
1.100 + return Vector<const char>(buffer.start(), 0);
1.101 +}
1.102 +
1.103 +
1.104 +static Vector<const char> TrimTrailingZeros(Vector<const char> buffer) {
1.105 + for (int i = buffer.length() - 1; i >= 0; --i) {
1.106 + if (buffer[i] != '0') {
1.107 + return buffer.SubVector(0, i + 1);
1.108 + }
1.109 + }
1.110 + return Vector<const char>(buffer.start(), 0);
1.111 +}
1.112 +
1.113 +
1.114 +static void CutToMaxSignificantDigits(Vector<const char> buffer,
1.115 + int exponent,
1.116 + char* significant_buffer,
1.117 + int* significant_exponent) {
1.118 + for (int i = 0; i < kMaxSignificantDecimalDigits - 1; ++i) {
1.119 + significant_buffer[i] = buffer[i];
1.120 + }
1.121 + // The input buffer has been trimmed. Therefore the last digit must be
1.122 + // different from '0'.
1.123 + ASSERT(buffer[buffer.length() - 1] != '0');
1.124 + // Set the last digit to be non-zero. This is sufficient to guarantee
1.125 + // correct rounding.
1.126 + significant_buffer[kMaxSignificantDecimalDigits - 1] = '1';
1.127 + *significant_exponent =
1.128 + exponent + (buffer.length() - kMaxSignificantDecimalDigits);
1.129 +}
1.130 +
1.131 +
1.132 +// Trims the buffer and cuts it to at most kMaxSignificantDecimalDigits.
1.133 +// If possible the input-buffer is reused, but if the buffer needs to be
1.134 +// modified (due to cutting), then the input needs to be copied into the
1.135 +// buffer_copy_space.
1.136 +static void TrimAndCut(Vector<const char> buffer, int exponent,
1.137 + char* buffer_copy_space, int space_size,
1.138 + Vector<const char>* trimmed, int* updated_exponent) {
1.139 + Vector<const char> left_trimmed = TrimLeadingZeros(buffer);
1.140 + Vector<const char> right_trimmed = TrimTrailingZeros(left_trimmed);
1.141 + exponent += left_trimmed.length() - right_trimmed.length();
1.142 + if (right_trimmed.length() > kMaxSignificantDecimalDigits) {
1.143 + ASSERT(space_size >= kMaxSignificantDecimalDigits);
1.144 + CutToMaxSignificantDigits(right_trimmed, exponent,
1.145 + buffer_copy_space, updated_exponent);
1.146 + *trimmed = Vector<const char>(buffer_copy_space,
1.147 + kMaxSignificantDecimalDigits);
1.148 + } else {
1.149 + *trimmed = right_trimmed;
1.150 + *updated_exponent = exponent;
1.151 + }
1.152 +}
1.153 +
1.154 +
1.155 +// Reads digits from the buffer and converts them to a uint64.
1.156 +// Reads in as many digits as fit into a uint64.
1.157 +// When the string starts with "1844674407370955161" no further digit is read.
1.158 +// Since 2^64 = 18446744073709551616 it would still be possible read another
1.159 +// digit if it was less or equal than 6, but this would complicate the code.
1.160 +static uint64_t ReadUint64(Vector<const char> buffer,
1.161 + int* number_of_read_digits) {
1.162 + uint64_t result = 0;
1.163 + int i = 0;
1.164 + while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) {
1.165 + int digit = buffer[i++] - '0';
1.166 + ASSERT(0 <= digit && digit <= 9);
1.167 + result = 10 * result + digit;
1.168 + }
1.169 + *number_of_read_digits = i;
1.170 + return result;
1.171 +}
1.172 +
1.173 +
1.174 +// Reads a DiyFp from the buffer.
1.175 +// The returned DiyFp is not necessarily normalized.
1.176 +// If remaining_decimals is zero then the returned DiyFp is accurate.
1.177 +// Otherwise it has been rounded and has error of at most 1/2 ulp.
1.178 +static void ReadDiyFp(Vector<const char> buffer,
1.179 + DiyFp* result,
1.180 + int* remaining_decimals) {
1.181 + int read_digits;
1.182 + uint64_t significand = ReadUint64(buffer, &read_digits);
1.183 + if (buffer.length() == read_digits) {
1.184 + *result = DiyFp(significand, 0);
1.185 + *remaining_decimals = 0;
1.186 + } else {
1.187 + // Round the significand.
1.188 + if (buffer[read_digits] >= '5') {
1.189 + significand++;
1.190 + }
1.191 + // Compute the binary exponent.
1.192 + int exponent = 0;
1.193 + *result = DiyFp(significand, exponent);
1.194 + *remaining_decimals = buffer.length() - read_digits;
1.195 + }
1.196 +}
1.197 +
1.198 +
1.199 +static bool DoubleStrtod(Vector<const char> trimmed,
1.200 + int exponent,
1.201 + double* result) {
1.202 +#if !defined(DOUBLE_CONVERSION_CORRECT_DOUBLE_OPERATIONS)
1.203 + // On x86 the floating-point stack can be 64 or 80 bits wide. If it is
1.204 + // 80 bits wide (as is the case on Linux) then double-rounding occurs and the
1.205 + // result is not accurate.
1.206 + // We know that Windows32 uses 64 bits and is therefore accurate.
1.207 + // Note that the ARM simulator is compiled for 32bits. It therefore exhibits
1.208 + // the same problem.
1.209 + return false;
1.210 +#endif
1.211 + if (trimmed.length() <= kMaxExactDoubleIntegerDecimalDigits) {
1.212 + int read_digits;
1.213 + // The trimmed input fits into a double.
1.214 + // If the 10^exponent (resp. 10^-exponent) fits into a double too then we
1.215 + // can compute the result-double simply by multiplying (resp. dividing) the
1.216 + // two numbers.
1.217 + // This is possible because IEEE guarantees that floating-point operations
1.218 + // return the best possible approximation.
1.219 + if (exponent < 0 && -exponent < kExactPowersOfTenSize) {
1.220 + // 10^-exponent fits into a double.
1.221 + *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
1.222 + ASSERT(read_digits == trimmed.length());
1.223 + *result /= exact_powers_of_ten[-exponent];
1.224 + return true;
1.225 + }
1.226 + if (0 <= exponent && exponent < kExactPowersOfTenSize) {
1.227 + // 10^exponent fits into a double.
1.228 + *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
1.229 + ASSERT(read_digits == trimmed.length());
1.230 + *result *= exact_powers_of_ten[exponent];
1.231 + return true;
1.232 + }
1.233 + int remaining_digits =
1.234 + kMaxExactDoubleIntegerDecimalDigits - trimmed.length();
1.235 + if ((0 <= exponent) &&
1.236 + (exponent - remaining_digits < kExactPowersOfTenSize)) {
1.237 + // The trimmed string was short and we can multiply it with
1.238 + // 10^remaining_digits. As a result the remaining exponent now fits
1.239 + // into a double too.
1.240 + *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
1.241 + ASSERT(read_digits == trimmed.length());
1.242 + *result *= exact_powers_of_ten[remaining_digits];
1.243 + *result *= exact_powers_of_ten[exponent - remaining_digits];
1.244 + return true;
1.245 + }
1.246 + }
1.247 + return false;
1.248 +}
1.249 +
1.250 +
1.251 +// Returns 10^exponent as an exact DiyFp.
1.252 +// The given exponent must be in the range [1; kDecimalExponentDistance[.
1.253 +static DiyFp AdjustmentPowerOfTen(int exponent) {
1.254 + ASSERT(0 < exponent);
1.255 + ASSERT(exponent < PowersOfTenCache::kDecimalExponentDistance);
1.256 + // Simply hardcode the remaining powers for the given decimal exponent
1.257 + // distance.
1.258 + ASSERT(PowersOfTenCache::kDecimalExponentDistance == 8);
1.259 + switch (exponent) {
1.260 + case 1: return DiyFp(UINT64_2PART_C(0xa0000000, 00000000), -60);
1.261 + case 2: return DiyFp(UINT64_2PART_C(0xc8000000, 00000000), -57);
1.262 + case 3: return DiyFp(UINT64_2PART_C(0xfa000000, 00000000), -54);
1.263 + case 4: return DiyFp(UINT64_2PART_C(0x9c400000, 00000000), -50);
1.264 + case 5: return DiyFp(UINT64_2PART_C(0xc3500000, 00000000), -47);
1.265 + case 6: return DiyFp(UINT64_2PART_C(0xf4240000, 00000000), -44);
1.266 + case 7: return DiyFp(UINT64_2PART_C(0x98968000, 00000000), -40);
1.267 + default:
1.268 + UNREACHABLE();
1.269 + return DiyFp(0, 0);
1.270 + }
1.271 +}
1.272 +
1.273 +
1.274 +// If the function returns true then the result is the correct double.
1.275 +// Otherwise it is either the correct double or the double that is just below
1.276 +// the correct double.
1.277 +static bool DiyFpStrtod(Vector<const char> buffer,
1.278 + int exponent,
1.279 + double* result) {
1.280 + DiyFp input;
1.281 + int remaining_decimals;
1.282 + ReadDiyFp(buffer, &input, &remaining_decimals);
1.283 + // Since we may have dropped some digits the input is not accurate.
1.284 + // If remaining_decimals is different than 0 than the error is at most
1.285 + // .5 ulp (unit in the last place).
1.286 + // We don't want to deal with fractions and therefore keep a common
1.287 + // denominator.
1.288 + const int kDenominatorLog = 3;
1.289 + const int kDenominator = 1 << kDenominatorLog;
1.290 + // Move the remaining decimals into the exponent.
1.291 + exponent += remaining_decimals;
1.292 + int error = (remaining_decimals == 0 ? 0 : kDenominator / 2);
1.293 +
1.294 + int old_e = input.e();
1.295 + input.Normalize();
1.296 + error <<= old_e - input.e();
1.297 +
1.298 + ASSERT(exponent <= PowersOfTenCache::kMaxDecimalExponent);
1.299 + if (exponent < PowersOfTenCache::kMinDecimalExponent) {
1.300 + *result = 0.0;
1.301 + return true;
1.302 + }
1.303 + DiyFp cached_power;
1.304 + int cached_decimal_exponent;
1.305 + PowersOfTenCache::GetCachedPowerForDecimalExponent(exponent,
1.306 + &cached_power,
1.307 + &cached_decimal_exponent);
1.308 +
1.309 + if (cached_decimal_exponent != exponent) {
1.310 + int adjustment_exponent = exponent - cached_decimal_exponent;
1.311 + DiyFp adjustment_power = AdjustmentPowerOfTen(adjustment_exponent);
1.312 + input.Multiply(adjustment_power);
1.313 + if (kMaxUint64DecimalDigits - buffer.length() >= adjustment_exponent) {
1.314 + // The product of input with the adjustment power fits into a 64 bit
1.315 + // integer.
1.316 + ASSERT(DiyFp::kSignificandSize == 64);
1.317 + } else {
1.318 + // The adjustment power is exact. There is hence only an error of 0.5.
1.319 + error += kDenominator / 2;
1.320 + }
1.321 + }
1.322 +
1.323 + input.Multiply(cached_power);
1.324 + // The error introduced by a multiplication of a*b equals
1.325 + // error_a + error_b + error_a*error_b/2^64 + 0.5
1.326 + // Substituting a with 'input' and b with 'cached_power' we have
1.327 + // error_b = 0.5 (all cached powers have an error of less than 0.5 ulp),
1.328 + // error_ab = 0 or 1 / kDenominator > error_a*error_b/ 2^64
1.329 + int error_b = kDenominator / 2;
1.330 + int error_ab = (error == 0 ? 0 : 1); // We round up to 1.
1.331 + int fixed_error = kDenominator / 2;
1.332 + error += error_b + error_ab + fixed_error;
1.333 +
1.334 + old_e = input.e();
1.335 + input.Normalize();
1.336 + error <<= old_e - input.e();
1.337 +
1.338 + // See if the double's significand changes if we add/subtract the error.
1.339 + int order_of_magnitude = DiyFp::kSignificandSize + input.e();
1.340 + int effective_significand_size =
1.341 + Double::SignificandSizeForOrderOfMagnitude(order_of_magnitude);
1.342 + int precision_digits_count =
1.343 + DiyFp::kSignificandSize - effective_significand_size;
1.344 + if (precision_digits_count + kDenominatorLog >= DiyFp::kSignificandSize) {
1.345 + // This can only happen for very small denormals. In this case the
1.346 + // half-way multiplied by the denominator exceeds the range of an uint64.
1.347 + // Simply shift everything to the right.
1.348 + int shift_amount = (precision_digits_count + kDenominatorLog) -
1.349 + DiyFp::kSignificandSize + 1;
1.350 + input.set_f(input.f() >> shift_amount);
1.351 + input.set_e(input.e() + shift_amount);
1.352 + // We add 1 for the lost precision of error, and kDenominator for
1.353 + // the lost precision of input.f().
1.354 + error = (error >> shift_amount) + 1 + kDenominator;
1.355 + precision_digits_count -= shift_amount;
1.356 + }
1.357 + // We use uint64_ts now. This only works if the DiyFp uses uint64_ts too.
1.358 + ASSERT(DiyFp::kSignificandSize == 64);
1.359 + ASSERT(precision_digits_count < 64);
1.360 + uint64_t one64 = 1;
1.361 + uint64_t precision_bits_mask = (one64 << precision_digits_count) - 1;
1.362 + uint64_t precision_bits = input.f() & precision_bits_mask;
1.363 + uint64_t half_way = one64 << (precision_digits_count - 1);
1.364 + precision_bits *= kDenominator;
1.365 + half_way *= kDenominator;
1.366 + DiyFp rounded_input(input.f() >> precision_digits_count,
1.367 + input.e() + precision_digits_count);
1.368 + if (precision_bits >= half_way + error) {
1.369 + rounded_input.set_f(rounded_input.f() + 1);
1.370 + }
1.371 + // If the last_bits are too close to the half-way case than we are too
1.372 + // inaccurate and round down. In this case we return false so that we can
1.373 + // fall back to a more precise algorithm.
1.374 +
1.375 + *result = Double(rounded_input).value();
1.376 + if (half_way - error < precision_bits && precision_bits < half_way + error) {
1.377 + // Too imprecise. The caller will have to fall back to a slower version.
1.378 + // However the returned number is guaranteed to be either the correct
1.379 + // double, or the next-lower double.
1.380 + return false;
1.381 + } else {
1.382 + return true;
1.383 + }
1.384 +}
1.385 +
1.386 +
1.387 +// Returns
1.388 +// - -1 if buffer*10^exponent < diy_fp.
1.389 +// - 0 if buffer*10^exponent == diy_fp.
1.390 +// - +1 if buffer*10^exponent > diy_fp.
1.391 +// Preconditions:
1.392 +// buffer.length() + exponent <= kMaxDecimalPower + 1
1.393 +// buffer.length() + exponent > kMinDecimalPower
1.394 +// buffer.length() <= kMaxDecimalSignificantDigits
1.395 +static int CompareBufferWithDiyFp(Vector<const char> buffer,
1.396 + int exponent,
1.397 + DiyFp diy_fp) {
1.398 + ASSERT(buffer.length() + exponent <= kMaxDecimalPower + 1);
1.399 + ASSERT(buffer.length() + exponent > kMinDecimalPower);
1.400 + ASSERT(buffer.length() <= kMaxSignificantDecimalDigits);
1.401 + // Make sure that the Bignum will be able to hold all our numbers.
1.402 + // Our Bignum implementation has a separate field for exponents. Shifts will
1.403 + // consume at most one bigit (< 64 bits).
1.404 + // ln(10) == 3.3219...
1.405 + ASSERT(((kMaxDecimalPower + 1) * 333 / 100) < Bignum::kMaxSignificantBits);
1.406 + Bignum buffer_bignum;
1.407 + Bignum diy_fp_bignum;
1.408 + buffer_bignum.AssignDecimalString(buffer);
1.409 + diy_fp_bignum.AssignUInt64(diy_fp.f());
1.410 + if (exponent >= 0) {
1.411 + buffer_bignum.MultiplyByPowerOfTen(exponent);
1.412 + } else {
1.413 + diy_fp_bignum.MultiplyByPowerOfTen(-exponent);
1.414 + }
1.415 + if (diy_fp.e() > 0) {
1.416 + diy_fp_bignum.ShiftLeft(diy_fp.e());
1.417 + } else {
1.418 + buffer_bignum.ShiftLeft(-diy_fp.e());
1.419 + }
1.420 + return Bignum::Compare(buffer_bignum, diy_fp_bignum);
1.421 +}
1.422 +
1.423 +
1.424 +// Returns true if the guess is the correct double.
1.425 +// Returns false, when guess is either correct or the next-lower double.
1.426 +static bool ComputeGuess(Vector<const char> trimmed, int exponent,
1.427 + double* guess) {
1.428 + if (trimmed.length() == 0) {
1.429 + *guess = 0.0;
1.430 + return true;
1.431 + }
1.432 + if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) {
1.433 + *guess = Double::Infinity();
1.434 + return true;
1.435 + }
1.436 + if (exponent + trimmed.length() <= kMinDecimalPower) {
1.437 + *guess = 0.0;
1.438 + return true;
1.439 + }
1.440 +
1.441 + if (DoubleStrtod(trimmed, exponent, guess) ||
1.442 + DiyFpStrtod(trimmed, exponent, guess)) {
1.443 + return true;
1.444 + }
1.445 + if (*guess == Double::Infinity()) {
1.446 + return true;
1.447 + }
1.448 + return false;
1.449 +}
1.450 +
1.451 +double Strtod(Vector<const char> buffer, int exponent) {
1.452 + char copy_buffer[kMaxSignificantDecimalDigits];
1.453 + Vector<const char> trimmed;
1.454 + int updated_exponent;
1.455 + TrimAndCut(buffer, exponent, copy_buffer, kMaxSignificantDecimalDigits,
1.456 + &trimmed, &updated_exponent);
1.457 + exponent = updated_exponent;
1.458 +
1.459 + double guess;
1.460 + bool is_correct = ComputeGuess(trimmed, exponent, &guess);
1.461 + if (is_correct) return guess;
1.462 +
1.463 + DiyFp upper_boundary = Double(guess).UpperBoundary();
1.464 + int comparison = CompareBufferWithDiyFp(trimmed, exponent, upper_boundary);
1.465 + if (comparison < 0) {
1.466 + return guess;
1.467 + } else if (comparison > 0) {
1.468 + return Double(guess).NextDouble();
1.469 + } else if ((Double(guess).Significand() & 1) == 0) {
1.470 + // Round towards even.
1.471 + return guess;
1.472 + } else {
1.473 + return Double(guess).NextDouble();
1.474 + }
1.475 +}
1.476 +
1.477 +float Strtof(Vector<const char> buffer, int exponent) {
1.478 + char copy_buffer[kMaxSignificantDecimalDigits];
1.479 + Vector<const char> trimmed;
1.480 + int updated_exponent;
1.481 + TrimAndCut(buffer, exponent, copy_buffer, kMaxSignificantDecimalDigits,
1.482 + &trimmed, &updated_exponent);
1.483 + exponent = updated_exponent;
1.484 +
1.485 + double double_guess;
1.486 + bool is_correct = ComputeGuess(trimmed, exponent, &double_guess);
1.487 +
1.488 + float float_guess = static_cast<float>(double_guess);
1.489 + if (float_guess == double_guess) {
1.490 + // This shortcut triggers for integer values.
1.491 + return float_guess;
1.492 + }
1.493 +
1.494 + // We must catch double-rounding. Say the double has been rounded up, and is
1.495 + // now a boundary of a float, and rounds up again. This is why we have to
1.496 + // look at previous too.
1.497 + // Example (in decimal numbers):
1.498 + // input: 12349
1.499 + // high-precision (4 digits): 1235
1.500 + // low-precision (3 digits):
1.501 + // when read from input: 123
1.502 + // when rounded from high precision: 124.
1.503 + // To do this we simply look at the neigbors of the correct result and see
1.504 + // if they would round to the same float. If the guess is not correct we have
1.505 + // to look at four values (since two different doubles could be the correct
1.506 + // double).
1.507 +
1.508 + double double_next = Double(double_guess).NextDouble();
1.509 + double double_previous = Double(double_guess).PreviousDouble();
1.510 +
1.511 + float f1 = static_cast<float>(double_previous);
1.512 +#if defined(DEBUG)
1.513 + float f2 = float_guess;
1.514 +#endif
1.515 + float f3 = static_cast<float>(double_next);
1.516 + float f4;
1.517 + if (is_correct) {
1.518 + f4 = f3;
1.519 + } else {
1.520 + double double_next2 = Double(double_next).NextDouble();
1.521 + f4 = static_cast<float>(double_next2);
1.522 + }
1.523 + ASSERT(f1 <= f2 && f2 <= f3 && f3 <= f4);
1.524 +
1.525 + // If the guess doesn't lie near a single-precision boundary we can simply
1.526 + // return its float-value.
1.527 + if (f1 == f4) {
1.528 + return float_guess;
1.529 + }
1.530 +
1.531 + ASSERT((f1 != f2 && f2 == f3 && f3 == f4) ||
1.532 + (f1 == f2 && f2 != f3 && f3 == f4) ||
1.533 + (f1 == f2 && f2 == f3 && f3 != f4));
1.534 +
1.535 + // guess and next are the two possible canditates (in the same way that
1.536 + // double_guess was the lower candidate for a double-precision guess).
1.537 + float guess = f1;
1.538 + float next = f4;
1.539 + DiyFp upper_boundary;
1.540 + if (guess == 0.0f) {
1.541 + float min_float = 1e-45f;
1.542 + upper_boundary = Double(static_cast<double>(min_float) / 2).AsDiyFp();
1.543 + } else {
1.544 + upper_boundary = Single(guess).UpperBoundary();
1.545 + }
1.546 + int comparison = CompareBufferWithDiyFp(trimmed, exponent, upper_boundary);
1.547 + if (comparison < 0) {
1.548 + return guess;
1.549 + } else if (comparison > 0) {
1.550 + return next;
1.551 + } else if ((Single(guess).Significand() & 1) == 0) {
1.552 + // Round towards even.
1.553 + return guess;
1.554 + } else {
1.555 + return next;
1.556 + }
1.557 +}
1.558 +
1.559 +} // namespace double_conversion
