OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 13 matching lines...) Expand all Loading... |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include <stdarg.h> | 28 #include <stdarg.h> |
29 #include <limits.h> | 29 #include <limits.h> |
30 | 30 |
31 #include "v8.h" | 31 #include "v8.h" |
32 | 32 |
33 #include "strtod.h" | 33 #include "strtod.h" |
| 34 #include "bignum.h" |
34 #include "cached-powers.h" | 35 #include "cached-powers.h" |
35 #include "double.h" | 36 #include "double.h" |
36 | 37 |
37 namespace v8 { | 38 namespace v8 { |
38 namespace internal { | 39 namespace internal { |
39 | 40 |
40 // 2^53 = 9007199254740992. | 41 // 2^53 = 9007199254740992. |
41 // Any integer with at most 15 decimal digits will hence fit into a double | 42 // Any integer with at most 15 decimal digits will hence fit into a double |
42 // (which has a 53bit significand) without loss of precision. | 43 // (which has a 53bit significand) without loss of precision. |
43 static const int kMaxExactDoubleIntegerDecimalDigits = 15; | 44 static const int kMaxExactDoubleIntegerDecimalDigits = 15; |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
76 1000000000000000.0, | 77 1000000000000000.0, |
77 10000000000000000.0, | 78 10000000000000000.0, |
78 100000000000000000.0, | 79 100000000000000000.0, |
79 1000000000000000000.0, | 80 1000000000000000000.0, |
80 10000000000000000000.0, | 81 10000000000000000000.0, |
81 100000000000000000000.0, // 10^20 | 82 100000000000000000000.0, // 10^20 |
82 1000000000000000000000.0, | 83 1000000000000000000000.0, |
83 // 10^22 = 0x21e19e0c9bab2400000 = 0x878678326eac9 * 2^22 | 84 // 10^22 = 0x21e19e0c9bab2400000 = 0x878678326eac9 * 2^22 |
84 10000000000000000000000.0 | 85 10000000000000000000000.0 |
85 }; | 86 }; |
86 | |
87 static const int kExactPowersOfTenSize = ARRAY_SIZE(exact_powers_of_ten); | 87 static const int kExactPowersOfTenSize = ARRAY_SIZE(exact_powers_of_ten); |
88 | 88 |
89 | 89 // Maximum number of significant digits in the decimal representation. |
90 extern "C" double gay_strtod(const char* s00, const char** se); | 90 // In fact the value is 772 (see conversions.cc), but to give us some margin |
91 | 91 // we round up to 780. |
92 static double old_strtod(Vector<const char> buffer, int exponent) { | 92 static const int kMaxSignificantDecimalDigits = 780; |
93 // gay_strtod is broken on Linux,x86. For numbers with few decimal digits | |
94 // the computation is done using floating-point operations which (on Linux) | |
95 // are prone to double-rounding errors. | |
96 // By adding several zeroes to the buffer gay_strtod falls back to a slower | |
97 // (but correct) algorithm. | |
98 const int kInsertedZeroesCount = 20; | |
99 char gay_buffer[1024]; | |
100 Vector<char> gay_buffer_vector(gay_buffer, sizeof(gay_buffer)); | |
101 int pos = 0; | |
102 for (int i = 0; i < buffer.length(); ++i) { | |
103 gay_buffer_vector[pos++] = buffer[i]; | |
104 } | |
105 for (int i = 0; i < kInsertedZeroesCount; ++i) { | |
106 gay_buffer_vector[pos++] = '0'; | |
107 } | |
108 exponent -= kInsertedZeroesCount; | |
109 gay_buffer_vector[pos++] = 'e'; | |
110 if (exponent < 0) { | |
111 gay_buffer_vector[pos++] = '-'; | |
112 exponent = -exponent; | |
113 } | |
114 const int kNumberOfExponentDigits = 5; | |
115 for (int i = kNumberOfExponentDigits - 1; i >= 0; i--) { | |
116 gay_buffer_vector[pos + i] = exponent % 10 + '0'; | |
117 exponent /= 10; | |
118 } | |
119 pos += kNumberOfExponentDigits; | |
120 gay_buffer_vector[pos] = '\0'; | |
121 return gay_strtod(gay_buffer, NULL); | |
122 } | |
123 | |
124 | 93 |
125 static Vector<const char> TrimLeadingZeros(Vector<const char> buffer) { | 94 static Vector<const char> TrimLeadingZeros(Vector<const char> buffer) { |
126 for (int i = 0; i < buffer.length(); i++) { | 95 for (int i = 0; i < buffer.length(); i++) { |
127 if (buffer[i] != '0') { | 96 if (buffer[i] != '0') { |
128 return buffer.SubVector(i, buffer.length()); | 97 return buffer.SubVector(i, buffer.length()); |
129 } | 98 } |
130 } | 99 } |
131 return Vector<const char>(buffer.start(), 0); | 100 return Vector<const char>(buffer.start(), 0); |
132 } | 101 } |
133 | 102 |
134 | 103 |
135 static Vector<const char> TrimTrailingZeros(Vector<const char> buffer) { | 104 static Vector<const char> TrimTrailingZeros(Vector<const char> buffer) { |
136 for (int i = buffer.length() - 1; i >= 0; --i) { | 105 for (int i = buffer.length() - 1; i >= 0; --i) { |
137 if (buffer[i] != '0') { | 106 if (buffer[i] != '0') { |
138 return buffer.SubVector(0, i + 1); | 107 return buffer.SubVector(0, i + 1); |
139 } | 108 } |
140 } | 109 } |
141 return Vector<const char>(buffer.start(), 0); | 110 return Vector<const char>(buffer.start(), 0); |
142 } | 111 } |
143 | 112 |
144 | 113 |
| 114 static void TrimToMaxSignificantDigits(Vector<const char> buffer, |
| 115 int exponent, |
| 116 char* significant_buffer, |
| 117 int* significant_exponent) { |
| 118 for (int i = 0; i < kMaxSignificantDecimalDigits - 1; ++i) { |
| 119 significant_buffer[i] = buffer[i]; |
| 120 } |
| 121 // The input buffer has been trimmed. Therefore the last digit must be |
| 122 // different from '0'. |
| 123 ASSERT(buffer[buffer.length() - 1] != '0'); |
| 124 // Set the last digit to be non-zero. This is sufficient to guarantee |
| 125 // correct rounding. |
| 126 significant_buffer[kMaxSignificantDecimalDigits - 1] = '1'; |
| 127 *significant_exponent = |
| 128 exponent + (buffer.length() - kMaxSignificantDecimalDigits); |
| 129 } |
| 130 |
145 // Reads digits from the buffer and converts them to a uint64. | 131 // Reads digits from the buffer and converts them to a uint64. |
146 // Reads in as many digits as fit into a uint64. | 132 // Reads in as many digits as fit into a uint64. |
147 // When the string starts with "1844674407370955161" no further digit is read. | 133 // When the string starts with "1844674407370955161" no further digit is read. |
148 // Since 2^64 = 18446744073709551616 it would still be possible read another | 134 // Since 2^64 = 18446744073709551616 it would still be possible read another |
149 // digit if it was less or equal than 6, but this would complicate the code. | 135 // digit if it was less or equal than 6, but this would complicate the code. |
150 static uint64_t ReadUint64(Vector<const char> buffer, | 136 static uint64_t ReadUint64(Vector<const char> buffer, |
151 int* number_of_read_digits) { | 137 int* number_of_read_digits) { |
152 uint64_t result = 0; | 138 uint64_t result = 0; |
153 int i = 0; | 139 int i = 0; |
154 while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) { | 140 while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) { |
(...skipping 212 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
367 // Too imprecise. The caller will have to fall back to a slower version. | 353 // Too imprecise. The caller will have to fall back to a slower version. |
368 // However the returned number is guaranteed to be either the correct | 354 // However the returned number is guaranteed to be either the correct |
369 // double, or the next-lower double. | 355 // double, or the next-lower double. |
370 return false; | 356 return false; |
371 } else { | 357 } else { |
372 return true; | 358 return true; |
373 } | 359 } |
374 } | 360 } |
375 | 361 |
376 | 362 |
| 363 // Returns the correct double for the buffer*10^exponent. |
| 364 // The variable guess should be a close guess that is either the correct double |
| 365 // or its lower neighbor (the nearest double less than the correct one). |
| 366 // Preconditions: |
| 367 // buffer.length() + exponent <= kMaxDecimalPower + 1 |
| 368 // buffer.length() + exponent > kMinDecimalPower |
| 369 // buffer.length() <= kMaxDecimalSignificantDigits |
| 370 static double BignumStrtod(Vector<const char> buffer, |
| 371 int exponent, |
| 372 double guess) { |
| 373 if (guess == V8_INFINITY) { |
| 374 return guess; |
| 375 } |
| 376 |
| 377 DiyFp upper_boundary = Double(guess).UpperBoundary(); |
| 378 |
| 379 ASSERT(buffer.length() + exponent <= kMaxDecimalPower + 1); |
| 380 ASSERT(buffer.length() + exponent > kMinDecimalPower); |
| 381 ASSERT(buffer.length() <= kMaxSignificantDecimalDigits); |
| 382 // Make sure that the Bignum will be able to hold all our numbers. |
| 383 // Our Bignum implementation has a separate field for exponents. Shifts will |
| 384 // consume at most one bigit (< 64 bits). |
| 385 // ln(10) == 3.3219... |
| 386 ASSERT(((kMaxDecimalPower + 1) * 333 / 100) < Bignum::kMaxSignificantBits); |
| 387 Bignum input; |
| 388 Bignum boundary; |
| 389 input.AssignDecimalString(buffer); |
| 390 boundary.AssignUInt64(upper_boundary.f()); |
| 391 if (exponent >= 0) { |
| 392 input.MultiplyByPowerOfTen(exponent); |
| 393 } else { |
| 394 boundary.MultiplyByPowerOfTen(-exponent); |
| 395 } |
| 396 if (upper_boundary.e() > 0) { |
| 397 boundary.ShiftLeft(upper_boundary.e()); |
| 398 } else { |
| 399 input.ShiftLeft(-upper_boundary.e()); |
| 400 } |
| 401 int comparison = Bignum::Compare(input, boundary); |
| 402 if (comparison < 0) { |
| 403 return guess; |
| 404 } else if (comparison > 0) { |
| 405 return Double(guess).NextDouble(); |
| 406 } else if ((Double(guess).Significand() & 1) == 0) { |
| 407 // Round towards even. |
| 408 return guess; |
| 409 } else { |
| 410 return Double(guess).NextDouble(); |
| 411 } |
| 412 } |
| 413 |
| 414 |
377 double Strtod(Vector<const char> buffer, int exponent) { | 415 double Strtod(Vector<const char> buffer, int exponent) { |
378 Vector<const char> left_trimmed = TrimLeadingZeros(buffer); | 416 Vector<const char> left_trimmed = TrimLeadingZeros(buffer); |
379 Vector<const char> trimmed = TrimTrailingZeros(left_trimmed); | 417 Vector<const char> trimmed = TrimTrailingZeros(left_trimmed); |
380 exponent += left_trimmed.length() - trimmed.length(); | 418 exponent += left_trimmed.length() - trimmed.length(); |
381 if (trimmed.length() == 0) return 0.0; | 419 if (trimmed.length() == 0) return 0.0; |
| 420 if (trimmed.length() > kMaxSignificantDecimalDigits) { |
| 421 char significant_buffer[kMaxSignificantDecimalDigits]; |
| 422 int significant_exponent; |
| 423 TrimToMaxSignificantDigits(trimmed, exponent, |
| 424 significant_buffer, &significant_exponent); |
| 425 trimmed = |
| 426 Vector<const char>(significant_buffer, kMaxSignificantDecimalDigits); |
| 427 exponent = significant_exponent; |
| 428 } |
382 if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) return V8_INFINITY; | 429 if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) return V8_INFINITY; |
383 if (exponent + trimmed.length() <= kMinDecimalPower) return 0.0; | 430 if (exponent + trimmed.length() <= kMinDecimalPower) return 0.0; |
384 | 431 |
385 double result; | 432 double guess; |
386 if (DoubleStrtod(trimmed, exponent, &result) || | 433 if (DoubleStrtod(trimmed, exponent, &guess) || |
387 DiyFpStrtod(trimmed, exponent, &result)) { | 434 DiyFpStrtod(trimmed, exponent, &guess)) { |
388 return result; | 435 return guess; |
389 } | 436 } |
390 return old_strtod(trimmed, exponent); | 437 return BignumStrtod(trimmed, exponent, guess); |
391 } | 438 } |
392 | 439 |
393 } } // namespace v8::internal | 440 } } // namespace v8::internal |
OLD | NEW |