00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #include <cstdarg>
00029 #include <climits>
00030
00031 #include "strtod.h"
00032 #include "bignum.h"
00033 #include "cached-powers.h"
00034 #include "ieee.h"
00035
00036 namespace double_conversion {
00037
00038
00039
00040
00041 static const int kMaxExactDoubleIntegerDecimalDigits = 15;
00042
00043 static const int kMaxUint64DecimalDigits = 19;
00044
00045
00046
00047
00048
00049
00050
00051 static const int kMaxDecimalPower = 309;
00052 static const int kMinDecimalPower = -324;
00053
00054
00055 static const uint64_t kMaxUint64 = UINT64_2PART_C(0xFFFFFFFF, FFFFFFFF);
00056
00057
00058 static const double exact_powers_of_ten[] = {
00059 1.0,
00060 10.0,
00061 100.0,
00062 1000.0,
00063 10000.0,
00064 100000.0,
00065 1000000.0,
00066 10000000.0,
00067 100000000.0,
00068 1000000000.0,
00069 10000000000.0,
00070 100000000000.0,
00071 1000000000000.0,
00072 10000000000000.0,
00073 100000000000000.0,
00074 1000000000000000.0,
00075 10000000000000000.0,
00076 100000000000000000.0,
00077 1000000000000000000.0,
00078 10000000000000000000.0,
00079 100000000000000000000.0,
00080 1000000000000000000000.0,
00081
00082 10000000000000000000000.0
00083 };
00084 static const int kExactPowersOfTenSize = ARRAY_SIZE(exact_powers_of_ten);
00085
00086
00087
00088
00089 static const int kMaxSignificantDecimalDigits = 780;
00090
00091 static Vector<const char> TrimLeadingZeros(Vector<const char> buffer) {
00092 for (int i = 0; i < buffer.length(); i++) {
00093 if (buffer[i] != '0') {
00094 return buffer.SubVector(i, buffer.length());
00095 }
00096 }
00097 return Vector<const char>(buffer.start(), 0);
00098 }
00099
00100
00101 static Vector<const char> TrimTrailingZeros(Vector<const char> buffer) {
00102 for (int i = buffer.length() - 1; i >= 0; --i) {
00103 if (buffer[i] != '0') {
00104 return buffer.SubVector(0, i + 1);
00105 }
00106 }
00107 return Vector<const char>(buffer.start(), 0);
00108 }
00109
00110
00111 static void CutToMaxSignificantDigits(Vector<const char> buffer,
00112 int exponent,
00113 char* significant_buffer,
00114 int* significant_exponent) {
00115 for (int i = 0; i < kMaxSignificantDecimalDigits - 1; ++i) {
00116 significant_buffer[i] = buffer[i];
00117 }
00118
00119
00120 ASSERT(buffer[buffer.length() - 1] != '0');
00121
00122
00123 significant_buffer[kMaxSignificantDecimalDigits - 1] = '1';
00124 *significant_exponent =
00125 exponent + (buffer.length() - kMaxSignificantDecimalDigits);
00126 }
00127
00128
00129
00130
00131
00132
00133 static void TrimAndCut(Vector<const char> buffer, int exponent,
00134 char* buffer_copy_space, int space_size,
00135 Vector<const char>* trimmed, int* updated_exponent) {
00136 Vector<const char> left_trimmed = TrimLeadingZeros(buffer);
00137 Vector<const char> right_trimmed = TrimTrailingZeros(left_trimmed);
00138 exponent += left_trimmed.length() - right_trimmed.length();
00139 if (right_trimmed.length() > kMaxSignificantDecimalDigits) {
00140 ASSERT(space_size >= kMaxSignificantDecimalDigits);
00141 CutToMaxSignificantDigits(right_trimmed, exponent,
00142 buffer_copy_space, updated_exponent);
00143 *trimmed = Vector<const char>(buffer_copy_space,
00144 kMaxSignificantDecimalDigits);
00145 } else {
00146 *trimmed = right_trimmed;
00147 *updated_exponent = exponent;
00148 }
00149 }
00150
00151
00152
00153
00154
00155
00156
00157 static uint64_t ReadUint64(Vector<const char> buffer,
00158 int* number_of_read_digits) {
00159 uint64_t result = 0;
00160 int i = 0;
00161 while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) {
00162 int digit = buffer[i++] - '0';
00163 ASSERT(0 <= digit && digit <= 9);
00164 result = 10 * result + digit;
00165 }
00166 *number_of_read_digits = i;
00167 return result;
00168 }
00169
00170
00171
00172
00173
00174
00175 static void ReadDiyFp(Vector<const char> buffer,
00176 DiyFp* result,
00177 int* remaining_decimals) {
00178 int read_digits;
00179 uint64_t significand = ReadUint64(buffer, &read_digits);
00180 if (buffer.length() == read_digits) {
00181 *result = DiyFp(significand, 0);
00182 *remaining_decimals = 0;
00183 } else {
00184
00185 if (buffer[read_digits] >= '5') {
00186 significand++;
00187 }
00188
00189 int exponent = 0;
00190 *result = DiyFp(significand, exponent);
00191 *remaining_decimals = buffer.length() - read_digits;
00192 }
00193 }
00194
00195
00196 static bool DoubleStrtod(Vector<const char> trimmed,
00197 int exponent,
00198 double* result) {
00199 #if !defined(DOUBLE_CONVERSION_CORRECT_DOUBLE_OPERATIONS)
00200
00201
00202
00203
00204
00205
00206 return false;
00207 #endif
00208 if (trimmed.length() <= kMaxExactDoubleIntegerDecimalDigits) {
00209 int read_digits;
00210
00211
00212
00213
00214
00215
00216 if (exponent < 0 && -exponent < kExactPowersOfTenSize) {
00217
00218 *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
00219 ASSERT(read_digits == trimmed.length());
00220 *result /= exact_powers_of_ten[-exponent];
00221 return true;
00222 }
00223 if (0 <= exponent && exponent < kExactPowersOfTenSize) {
00224
00225 *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
00226 ASSERT(read_digits == trimmed.length());
00227 *result *= exact_powers_of_ten[exponent];
00228 return true;
00229 }
00230 int remaining_digits =
00231 kMaxExactDoubleIntegerDecimalDigits - trimmed.length();
00232 if ((0 <= exponent) &&
00233 (exponent - remaining_digits < kExactPowersOfTenSize)) {
00234
00235
00236
00237 *result = static_cast<double>(ReadUint64(trimmed, &read_digits));
00238 ASSERT(read_digits == trimmed.length());
00239 *result *= exact_powers_of_ten[remaining_digits];
00240 *result *= exact_powers_of_ten[exponent - remaining_digits];
00241 return true;
00242 }
00243 }
00244 return false;
00245 }
00246
00247
00248
00249
00250 static DiyFp AdjustmentPowerOfTen(int exponent) {
00251 ASSERT(0 < exponent);
00252 ASSERT(exponent < PowersOfTenCache::kDecimalExponentDistance);
00253
00254
00255 ASSERT(PowersOfTenCache::kDecimalExponentDistance == 8);
00256 switch (exponent) {
00257 case 1: return DiyFp(UINT64_2PART_C(0xa0000000, 00000000), -60);
00258 case 2: return DiyFp(UINT64_2PART_C(0xc8000000, 00000000), -57);
00259 case 3: return DiyFp(UINT64_2PART_C(0xfa000000, 00000000), -54);
00260 case 4: return DiyFp(UINT64_2PART_C(0x9c400000, 00000000), -50);
00261 case 5: return DiyFp(UINT64_2PART_C(0xc3500000, 00000000), -47);
00262 case 6: return DiyFp(UINT64_2PART_C(0xf4240000, 00000000), -44);
00263 case 7: return DiyFp(UINT64_2PART_C(0x98968000, 00000000), -40);
00264 default:
00265 UNREACHABLE();
00266 return DiyFp(0, 0);
00267 }
00268 }
00269
00270
00271
00272
00273
00274 static bool DiyFpStrtod(Vector<const char> buffer,
00275 int exponent,
00276 double* result) {
00277 DiyFp input;
00278 int remaining_decimals;
00279 ReadDiyFp(buffer, &input, &remaining_decimals);
00280
00281
00282
00283
00284
00285 const int kDenominatorLog = 3;
00286 const int kDenominator = 1 << kDenominatorLog;
00287
00288 exponent += remaining_decimals;
00289 int error = (remaining_decimals == 0 ? 0 : kDenominator / 2);
00290
00291 int old_e = input.e();
00292 input.Normalize();
00293 error <<= old_e - input.e();
00294
00295 ASSERT(exponent <= PowersOfTenCache::kMaxDecimalExponent);
00296 if (exponent < PowersOfTenCache::kMinDecimalExponent) {
00297 *result = 0.0;
00298 return true;
00299 }
00300 DiyFp cached_power;
00301 int cached_decimal_exponent;
00302 PowersOfTenCache::GetCachedPowerForDecimalExponent(exponent,
00303 &cached_power,
00304 &cached_decimal_exponent);
00305
00306 if (cached_decimal_exponent != exponent) {
00307 int adjustment_exponent = exponent - cached_decimal_exponent;
00308 DiyFp adjustment_power = AdjustmentPowerOfTen(adjustment_exponent);
00309 input.Multiply(adjustment_power);
00310 if (kMaxUint64DecimalDigits - buffer.length() >= adjustment_exponent) {
00311
00312
00313 ASSERT(DiyFp::kSignificandSize == 64);
00314 } else {
00315
00316 error += kDenominator / 2;
00317 }
00318 }
00319
00320 input.Multiply(cached_power);
00321
00322
00323
00324
00325
00326 int error_b = kDenominator / 2;
00327 int error_ab = (error == 0 ? 0 : 1);
00328 int fixed_error = kDenominator / 2;
00329 error += error_b + error_ab + fixed_error;
00330
00331 old_e = input.e();
00332 input.Normalize();
00333 error <<= old_e - input.e();
00334
00335
00336 int order_of_magnitude = DiyFp::kSignificandSize + input.e();
00337 int effective_significand_size =
00338 Double::SignificandSizeForOrderOfMagnitude(order_of_magnitude);
00339 int precision_digits_count =
00340 DiyFp::kSignificandSize - effective_significand_size;
00341 if (precision_digits_count + kDenominatorLog >= DiyFp::kSignificandSize) {
00342
00343
00344
00345 int shift_amount = (precision_digits_count + kDenominatorLog) -
00346 DiyFp::kSignificandSize + 1;
00347 input.set_f(input.f() >> shift_amount);
00348 input.set_e(input.e() + shift_amount);
00349
00350
00351 error = (error >> shift_amount) + 1 + kDenominator;
00352 precision_digits_count -= shift_amount;
00353 }
00354
00355 ASSERT(DiyFp::kSignificandSize == 64);
00356 ASSERT(precision_digits_count < 64);
00357 uint64_t one64 = 1;
00358 uint64_t precision_bits_mask = (one64 << precision_digits_count) - 1;
00359 uint64_t precision_bits = input.f() & precision_bits_mask;
00360 uint64_t half_way = one64 << (precision_digits_count - 1);
00361 precision_bits *= kDenominator;
00362 half_way *= kDenominator;
00363 DiyFp rounded_input(input.f() >> precision_digits_count,
00364 input.e() + precision_digits_count);
00365 if (precision_bits >= half_way + error) {
00366 rounded_input.set_f(rounded_input.f() + 1);
00367 }
00368
00369
00370
00371
00372 *result = Double(rounded_input).value();
00373 if (half_way - error < precision_bits && precision_bits < half_way + error) {
00374
00375
00376
00377 return false;
00378 } else {
00379 return true;
00380 }
00381 }
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392 static int CompareBufferWithDiyFp(Vector<const char> buffer,
00393 int exponent,
00394 DiyFp diy_fp) {
00395 ASSERT(buffer.length() + exponent <= kMaxDecimalPower + 1);
00396 ASSERT(buffer.length() + exponent > kMinDecimalPower);
00397 ASSERT(buffer.length() <= kMaxSignificantDecimalDigits);
00398
00399
00400
00401
00402 ASSERT(((kMaxDecimalPower + 1) * 333 / 100) < Bignum::kMaxSignificantBits);
00403 Bignum buffer_bignum;
00404 Bignum diy_fp_bignum;
00405 buffer_bignum.AssignDecimalString(buffer);
00406 diy_fp_bignum.AssignUInt64(diy_fp.f());
00407 if (exponent >= 0) {
00408 buffer_bignum.MultiplyByPowerOfTen(exponent);
00409 } else {
00410 diy_fp_bignum.MultiplyByPowerOfTen(-exponent);
00411 }
00412 if (diy_fp.e() > 0) {
00413 diy_fp_bignum.ShiftLeft(diy_fp.e());
00414 } else {
00415 buffer_bignum.ShiftLeft(-diy_fp.e());
00416 }
00417 return Bignum::Compare(buffer_bignum, diy_fp_bignum);
00418 }
00419
00420
00421
00422
00423 static bool ComputeGuess(Vector<const char> trimmed, int exponent,
00424 double* guess) {
00425 if (trimmed.length() == 0) {
00426 *guess = 0.0;
00427 return true;
00428 }
00429 if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) {
00430 *guess = Double::Infinity();
00431 return true;
00432 }
00433 if (exponent + trimmed.length() <= kMinDecimalPower) {
00434 *guess = 0.0;
00435 return true;
00436 }
00437
00438 if (DoubleStrtod(trimmed, exponent, guess) ||
00439 DiyFpStrtod(trimmed, exponent, guess)) {
00440 return true;
00441 }
00442 if (*guess == Double::Infinity()) {
00443 return true;
00444 }
00445 return false;
00446 }
00447
00448 double Strtod(Vector<const char> buffer, int exponent) {
00449 char copy_buffer[kMaxSignificantDecimalDigits];
00450 Vector<const char> trimmed;
00451 int updated_exponent;
00452 TrimAndCut(buffer, exponent, copy_buffer, kMaxSignificantDecimalDigits,
00453 &trimmed, &updated_exponent);
00454 exponent = updated_exponent;
00455
00456 double guess;
00457 bool is_correct = ComputeGuess(trimmed, exponent, &guess);
00458 if (is_correct) return guess;
00459
00460 DiyFp upper_boundary = Double(guess).UpperBoundary();
00461 int comparison = CompareBufferWithDiyFp(trimmed, exponent, upper_boundary);
00462 if (comparison < 0) {
00463 return guess;
00464 } else if (comparison > 0) {
00465 return Double(guess).NextDouble();
00466 } else if ((Double(guess).Significand() & 1) == 0) {
00467
00468 return guess;
00469 } else {
00470 return Double(guess).NextDouble();
00471 }
00472 }
00473
00474 float Strtof(Vector<const char> buffer, int exponent) {
00475 char copy_buffer[kMaxSignificantDecimalDigits];
00476 Vector<const char> trimmed;
00477 int updated_exponent;
00478 TrimAndCut(buffer, exponent, copy_buffer, kMaxSignificantDecimalDigits,
00479 &trimmed, &updated_exponent);
00480 exponent = updated_exponent;
00481
00482 double double_guess;
00483 bool is_correct = ComputeGuess(trimmed, exponent, &double_guess);
00484
00485 float float_guess = static_cast<float>(double_guess);
00486 if (float_guess == double_guess) {
00487
00488 return float_guess;
00489 }
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505 double double_next = Double(double_guess).NextDouble();
00506 double double_previous = Double(double_guess).PreviousDouble();
00507
00508 float f1 = static_cast<float>(double_previous);
00509 #ifndef NDEBUG
00510 float f2 = float_guess;
00511 #endif
00512 float f3 = static_cast<float>(double_next);
00513 float f4;
00514 if (is_correct) {
00515 f4 = f3;
00516 } else {
00517 double double_next2 = Double(double_next).NextDouble();
00518 f4 = static_cast<float>(double_next2);
00519 }
00520 #ifndef NDEBUG
00521 ASSERT(f1 <= f2 && f2 <= f3 && f3 <= f4);
00522 #endif
00523
00524
00525
00526 if (f1 == f4) {
00527 return float_guess;
00528 }
00529
00530 ASSERT((f1 != f2 && f2 == f3 && f3 == f4) ||
00531 (f1 == f2 && f2 != f3 && f3 == f4) ||
00532 (f1 == f2 && f2 == f3 && f3 != f4));
00533
00534
00535
00536 float guess = f1;
00537 float next = f4;
00538 DiyFp upper_boundary;
00539 if (guess == 0.0f) {
00540 float min_float = 1e-45f;
00541 upper_boundary = Double(static_cast<double>(min_float) / 2).AsDiyFp();
00542 } else {
00543 upper_boundary = Single(guess).UpperBoundary();
00544 }
00545 int comparison = CompareBufferWithDiyFp(trimmed, exponent, upper_boundary);
00546 if (comparison < 0) {
00547 return guess;
00548 } else if (comparison > 0) {
00549 return next;
00550 } else if ((Single(guess).Significand() & 1) == 0) {
00551
00552 return guess;
00553 } else {
00554 return next;
00555 }
00556 }
00557
00558 }