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 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
112 | 112 |
113 static void TrimToMaxSignificantDigits(Vector<const char> buffer, | 113 static void TrimToMaxSignificantDigits(Vector<const char> buffer, |
114 int exponent, | 114 int exponent, |
115 char* significant_buffer, | 115 char* significant_buffer, |
116 int* significant_exponent) { | 116 int* significant_exponent) { |
117 for (int i = 0; i < kMaxSignificantDecimalDigits - 1; ++i) { | 117 for (int i = 0; i < kMaxSignificantDecimalDigits - 1; ++i) { |
118 significant_buffer[i] = buffer[i]; | 118 significant_buffer[i] = buffer[i]; |
119 } | 119 } |
120 // The input buffer has been trimmed. Therefore the last digit must be | 120 // The input buffer has been trimmed. Therefore the last digit must be |
121 // different from '0'. | 121 // different from '0'. |
122 ASSERT(buffer[buffer.length() - 1] != '0'); | 122 DCHECK_NE(buffer[buffer.length() - 1], '0'); |
123 // Set the last digit to be non-zero. This is sufficient to guarantee | 123 // Set the last digit to be non-zero. This is sufficient to guarantee |
124 // correct rounding. | 124 // correct rounding. |
125 significant_buffer[kMaxSignificantDecimalDigits - 1] = '1'; | 125 significant_buffer[kMaxSignificantDecimalDigits - 1] = '1'; |
126 *significant_exponent = | 126 *significant_exponent = |
127 exponent + (buffer.length() - kMaxSignificantDecimalDigits); | 127 exponent + (buffer.length() - kMaxSignificantDecimalDigits); |
128 } | 128 } |
129 | 129 |
130 // Reads digits from the buffer and converts them to a uint64. | 130 // Reads digits from the buffer and converts them to a uint64. |
131 // Reads in as many digits as fit into a uint64. | 131 // Reads in as many digits as fit into a uint64. |
132 // When the string starts with "1844674407370955161" no further digit is rea
d. | 132 // When the string starts with "1844674407370955161" no further digit is rea
d. |
133 // Since 2^64 = 18446744073709551616 it would still be possible read another | 133 // Since 2^64 = 18446744073709551616 it would still be possible read another |
134 // digit if it was less or equal than 6, but this would complicate the code. | 134 // digit if it was less or equal than 6, but this would complicate the code. |
135 static uint64_t ReadUint64(Vector<const char> buffer, | 135 static uint64_t ReadUint64(Vector<const char> buffer, |
136 int* number_of_read_digits) { | 136 int* number_of_read_digits) { |
137 uint64_t result = 0; | 137 uint64_t result = 0; |
138 int i = 0; | 138 int i = 0; |
139 while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) { | 139 while (i < buffer.length() && result <= (kMaxUint64 / 10 - 1)) { |
140 int digit = buffer[i++] - '0'; | 140 int digit = buffer[i++] - '0'; |
141 ASSERT(0 <= digit && digit <= 9); | 141 DCHECK_LE(0, digit); |
| 142 DCHECK_LE(digit, 9); |
142 result = 10 * result + digit; | 143 result = 10 * result + digit; |
143 } | 144 } |
144 *number_of_read_digits = i; | 145 *number_of_read_digits = i; |
145 return result; | 146 return result; |
146 } | 147 } |
147 | 148 |
148 | 149 |
149 // Reads a DiyFp from the buffer. | 150 // Reads a DiyFp from the buffer. |
150 // The returned DiyFp is not necessarily normalized. | 151 // The returned DiyFp is not necessarily normalized. |
151 // If remaining_decimals is zero then the returned DiyFp is accurate. | 152 // If remaining_decimals is zero then the returned DiyFp is accurate. |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
187 int read_digits; | 188 int read_digits; |
188 // The trimmed input fits into a double. | 189 // The trimmed input fits into a double. |
189 // If the 10^exponent (resp. 10^-exponent) fits into a double too th
en we | 190 // If the 10^exponent (resp. 10^-exponent) fits into a double too th
en we |
190 // can compute the result-double simply by multiplying (resp. dividi
ng) the | 191 // can compute the result-double simply by multiplying (resp. dividi
ng) the |
191 // two numbers. | 192 // two numbers. |
192 // This is possible because IEEE guarantees that floating-point oper
ations | 193 // This is possible because IEEE guarantees that floating-point oper
ations |
193 // return the best possible approximation. | 194 // return the best possible approximation. |
194 if (exponent < 0 && -exponent < kExactPowersOfTenSize) { | 195 if (exponent < 0 && -exponent < kExactPowersOfTenSize) { |
195 // 10^-exponent fits into a double. | 196 // 10^-exponent fits into a double. |
196 *result = static_cast<double>(ReadUint64(trimmed, &read_digits))
; | 197 *result = static_cast<double>(ReadUint64(trimmed, &read_digits))
; |
197 ASSERT(read_digits == trimmed.length()); | 198 DCHECK_EQ(read_digits, trimmed.length()); |
198 *result /= exact_powers_of_ten[-exponent]; | 199 *result /= exact_powers_of_ten[-exponent]; |
199 return true; | 200 return true; |
200 } | 201 } |
201 if (0 <= exponent && exponent < kExactPowersOfTenSize) { | 202 if (0 <= exponent && exponent < kExactPowersOfTenSize) { |
202 // 10^exponent fits into a double. | 203 // 10^exponent fits into a double. |
203 *result = static_cast<double>(ReadUint64(trimmed, &read_digits))
; | 204 *result = static_cast<double>(ReadUint64(trimmed, &read_digits))
; |
204 ASSERT(read_digits == trimmed.length()); | 205 DCHECK_EQ(read_digits, trimmed.length()); |
205 *result *= exact_powers_of_ten[exponent]; | 206 *result *= exact_powers_of_ten[exponent]; |
206 return true; | 207 return true; |
207 } | 208 } |
208 int remaining_digits = | 209 int remaining_digits = |
209 kMaxExactDoubleIntegerDecimalDigits - trimmed.length(); | 210 kMaxExactDoubleIntegerDecimalDigits - trimmed.length(); |
210 if ((0 <= exponent) && | 211 if ((0 <= exponent) && |
211 (exponent - remaining_digits < kExactPowersOfTenSize)) { | 212 (exponent - remaining_digits < kExactPowersOfTenSize)) { |
212 // The trimmed string was short and we can multiply it with | 213 // The trimmed string was short and we can multiply it with |
213 // 10^remaining_digits. As a result the remaining exponent now f
its | 214 // 10^remaining_digits. As a result the remaining exponent now f
its |
214 // into a double too. | 215 // into a double too. |
215 *result = static_cast<double>(ReadUint64(trimmed, &read_digits))
; | 216 *result = static_cast<double>(ReadUint64(trimmed, &read_digits))
; |
216 ASSERT(read_digits == trimmed.length()); | 217 DCHECK_EQ(read_digits, trimmed.length()); |
217 *result *= exact_powers_of_ten[remaining_digits]; | 218 *result *= exact_powers_of_ten[remaining_digits]; |
218 *result *= exact_powers_of_ten[exponent - remaining_digits]; | 219 *result *= exact_powers_of_ten[exponent - remaining_digits]; |
219 return true; | 220 return true; |
220 } | 221 } |
221 } | 222 } |
222 return false; | 223 return false; |
223 } | 224 } |
224 | 225 |
225 | 226 |
226 // Returns 10^exponent as an exact DiyFp. | 227 // Returns 10^exponent as an exact DiyFp. |
227 // The given exponent must be in the range [1; kDecimalExponentDistance[. | 228 // The given exponent must be in the range [1; kDecimalExponentDistance[. |
228 static DiyFp AdjustmentPowerOfTen(int exponent) { | 229 static DiyFp AdjustmentPowerOfTen(int exponent) { |
229 ASSERT(0 < exponent); | 230 DCHECK_LT(0, exponent); |
230 ASSERT(exponent < PowersOfTenCache::kDecimalExponentDistance); | 231 DCHECK_LT(exponent, PowersOfTenCache::kDecimalExponentDistance); |
231 // Simply hardcode the remaining powers for the given decimal exponent | 232 // Simply hardcode the remaining powers for the given decimal exponent |
232 // distance. | 233 // distance. |
233 ASSERT(PowersOfTenCache::kDecimalExponentDistance == 8); | 234 DCHECK_EQ(PowersOfTenCache::kDecimalExponentDistance, 8); |
234 switch (exponent) { | 235 switch (exponent) { |
235 case 1: return DiyFp(UINT64_2PART_C(0xa0000000, 00000000), -60); | 236 case 1: return DiyFp(UINT64_2PART_C(0xa0000000, 00000000), -60); |
236 case 2: return DiyFp(UINT64_2PART_C(0xc8000000, 00000000), -57); | 237 case 2: return DiyFp(UINT64_2PART_C(0xc8000000, 00000000), -57); |
237 case 3: return DiyFp(UINT64_2PART_C(0xfa000000, 00000000), -54); | 238 case 3: return DiyFp(UINT64_2PART_C(0xfa000000, 00000000), -54); |
238 case 4: return DiyFp(UINT64_2PART_C(0x9c400000, 00000000), -50); | 239 case 4: return DiyFp(UINT64_2PART_C(0x9c400000, 00000000), -50); |
239 case 5: return DiyFp(UINT64_2PART_C(0xc3500000, 00000000), -47); | 240 case 5: return DiyFp(UINT64_2PART_C(0xc3500000, 00000000), -47); |
240 case 6: return DiyFp(UINT64_2PART_C(0xf4240000, 00000000), -44); | 241 case 6: return DiyFp(UINT64_2PART_C(0xf4240000, 00000000), -44); |
241 case 7: return DiyFp(UINT64_2PART_C(0x98968000, 00000000), -40); | 242 case 7: return DiyFp(UINT64_2PART_C(0x98968000, 00000000), -40); |
242 default: | 243 default: |
243 UNREACHABLE(); | 244 UNREACHABLE(); |
(...skipping 19 matching lines...) Expand all Loading... |
263 const int kDenominatorLog = 3; | 264 const int kDenominatorLog = 3; |
264 const int kDenominator = 1 << kDenominatorLog; | 265 const int kDenominator = 1 << kDenominatorLog; |
265 // Move the remaining decimals into the exponent. | 266 // Move the remaining decimals into the exponent. |
266 exponent += remaining_decimals; | 267 exponent += remaining_decimals; |
267 int64_t error = (remaining_decimals == 0 ? 0 : kDenominator / 2); | 268 int64_t error = (remaining_decimals == 0 ? 0 : kDenominator / 2); |
268 | 269 |
269 int old_e = input.E(); | 270 int old_e = input.E(); |
270 input.Normalize(); | 271 input.Normalize(); |
271 error <<= old_e - input.E(); | 272 error <<= old_e - input.E(); |
272 | 273 |
273 ASSERT(exponent <= PowersOfTenCache::kMaxDecimalExponent); | 274 DCHECK_LE(exponent, PowersOfTenCache::kMaxDecimalExponent); |
274 if (exponent < PowersOfTenCache::kMinDecimalExponent) { | 275 if (exponent < PowersOfTenCache::kMinDecimalExponent) { |
275 *result = 0.0; | 276 *result = 0.0; |
276 return true; | 277 return true; |
277 } | 278 } |
278 DiyFp cached_power; | 279 DiyFp cached_power; |
279 int cached_decimal_exponent; | 280 int cached_decimal_exponent; |
280 PowersOfTenCache::GetCachedPowerForDecimalExponent(exponent, | 281 PowersOfTenCache::GetCachedPowerForDecimalExponent(exponent, |
281 &cached_power, | 282 &cached_power, |
282 &cached_decimal_expon
ent); | 283 &cached_decimal_expon
ent); |
283 | 284 |
284 if (cached_decimal_exponent != exponent) { | 285 if (cached_decimal_exponent != exponent) { |
285 int adjustment_exponent = exponent - cached_decimal_exponent; | 286 int adjustment_exponent = exponent - cached_decimal_exponent; |
286 DiyFp adjustment_power = AdjustmentPowerOfTen(adjustment_exponent); | 287 DiyFp adjustment_power = AdjustmentPowerOfTen(adjustment_exponent); |
287 input.Multiply(adjustment_power); | 288 input.Multiply(adjustment_power); |
288 if (kMaxUint64DecimalDigits - buffer.length() >= adjustment_exponent
) { | 289 if (kMaxUint64DecimalDigits - buffer.length() >= adjustment_exponent
) { |
289 // The product of input with the adjustment power fits into a 64
bit | 290 // The product of input with the adjustment power fits into a 64
bit |
290 // integer. | 291 // integer. |
291 ASSERT(DiyFp::kSignificandSize == 64); | 292 DCHECK_EQ(DiyFp::kSignificandSize, 64); |
292 } else { | 293 } else { |
293 // The adjustment power is exact. There is hence only an error o
f 0.5. | 294 // The adjustment power is exact. There is hence only an error o
f 0.5. |
294 error += kDenominator / 2; | 295 error += kDenominator / 2; |
295 } | 296 } |
296 } | 297 } |
297 | 298 |
298 input.Multiply(cached_power); | 299 input.Multiply(cached_power); |
299 // The error introduced by a multiplication of a*b equals | 300 // The error introduced by a multiplication of a*b equals |
300 // error_a + error_b + error_a*error_b/2^64 + 0.5 | 301 // error_a + error_b + error_a*error_b/2^64 + 0.5 |
301 // Substituting a with 'input' and b with 'cached_power' we have | 302 // Substituting a with 'input' and b with 'cached_power' we have |
(...skipping 21 matching lines...) Expand all Loading... |
323 int shift_amount = (precision_digits_count + kDenominatorLog) - | 324 int shift_amount = (precision_digits_count + kDenominatorLog) - |
324 DiyFp::kSignificandSize + 1; | 325 DiyFp::kSignificandSize + 1; |
325 input.set_f(input.F() >> shift_amount); | 326 input.set_f(input.F() >> shift_amount); |
326 input.set_e(input.E() + shift_amount); | 327 input.set_e(input.E() + shift_amount); |
327 // We add 1 for the lost precision of error, and kDenominator for | 328 // We add 1 for the lost precision of error, and kDenominator for |
328 // the lost precision of input.f(). | 329 // the lost precision of input.f(). |
329 error = (error >> shift_amount) + 1 + kDenominator; | 330 error = (error >> shift_amount) + 1 + kDenominator; |
330 precision_digits_count -= shift_amount; | 331 precision_digits_count -= shift_amount; |
331 } | 332 } |
332 // We use uint64_ts now. This only works if the DiyFp uses uint64_ts too
. | 333 // We use uint64_ts now. This only works if the DiyFp uses uint64_ts too
. |
333 ASSERT(DiyFp::kSignificandSize == 64); | 334 DCHECK_EQ(DiyFp::kSignificandSize, 64); |
334 ASSERT(precision_digits_count < 64); | 335 DCHECK_LT(precision_digits_count, 64); |
335 uint64_t one64 = 1; | 336 uint64_t one64 = 1; |
336 uint64_t precision_bits_mask = (one64 << precision_digits_count) - 1; | 337 uint64_t precision_bits_mask = (one64 << precision_digits_count) - 1; |
337 uint64_t precision_bits = input.F() & precision_bits_mask; | 338 uint64_t precision_bits = input.F() & precision_bits_mask; |
338 uint64_t half_way = one64 << (precision_digits_count - 1); | 339 uint64_t half_way = one64 << (precision_digits_count - 1); |
339 precision_bits *= kDenominator; | 340 precision_bits *= kDenominator; |
340 half_way *= kDenominator; | 341 half_way *= kDenominator; |
341 DiyFp rounded_input(input.F() >> precision_digits_count, | 342 DiyFp rounded_input(input.F() >> precision_digits_count, |
342 input.E() + precision_digits_count); | 343 input.E() + precision_digits_count); |
343 if (precision_bits >= half_way + error) { | 344 if (precision_bits >= half_way + error) { |
344 rounded_input.set_f(rounded_input.F() + 1); | 345 rounded_input.set_f(rounded_input.F() + 1); |
(...skipping 23 matching lines...) Expand all Loading... |
368 // buffer.length() <= kMaxDecimalSignificantDigits | 369 // buffer.length() <= kMaxDecimalSignificantDigits |
369 static double BignumStrtod(Vector<const char> buffer, | 370 static double BignumStrtod(Vector<const char> buffer, |
370 int exponent, | 371 int exponent, |
371 double guess) { | 372 double guess) { |
372 if (guess == Double::Infinity()) { | 373 if (guess == Double::Infinity()) { |
373 return guess; | 374 return guess; |
374 } | 375 } |
375 | 376 |
376 DiyFp upper_boundary = Double(guess).UpperBoundary(); | 377 DiyFp upper_boundary = Double(guess).UpperBoundary(); |
377 | 378 |
378 ASSERT(buffer.length() + exponent <= kMaxDecimalPower + 1); | 379 DCHECK_LE(buffer.length() + exponent, kMaxDecimalPower + 1); |
379 ASSERT(buffer.length() + exponent > kMinDecimalPower); | 380 DCHECK_GT(buffer.length() + exponent, kMinDecimalPower); |
380 ASSERT(buffer.length() <= kMaxSignificantDecimalDigits); | 381 DCHECK_LE(buffer.length(), kMaxSignificantDecimalDigits); |
381 // Make sure that the Bignum will be able to hold all our numbers. | 382 // Make sure that the Bignum will be able to hold all our numbers. |
382 // Our Bignum implementation has a separate field for exponents. Shifts
will | 383 // Our Bignum implementation has a separate field for exponents. Shifts
will |
383 // consume at most one bigit (< 64 bits). | 384 // consume at most one bigit (< 64 bits). |
384 // ln(10) == 3.3219... | 385 // ln(10) == 3.3219... |
385 ASSERT(((kMaxDecimalPower + 1) * 333 / 100) < Bignum::kMaxSignificantBit
s); | 386 DCHECK_LT(((kMaxDecimalPower + 1) * 333 / 100), Bignum::kMaxSignificantB
its); |
386 Bignum input; | 387 Bignum input; |
387 Bignum boundary; | 388 Bignum boundary; |
388 input.AssignDecimalString(buffer); | 389 input.AssignDecimalString(buffer); |
389 boundary.AssignUInt64(upper_boundary.F()); | 390 boundary.AssignUInt64(upper_boundary.F()); |
390 if (exponent >= 0) { | 391 if (exponent >= 0) { |
391 input.MultiplyByPowerOfTen(exponent); | 392 input.MultiplyByPowerOfTen(exponent); |
392 } else { | 393 } else { |
393 boundary.MultiplyByPowerOfTen(-exponent); | 394 boundary.MultiplyByPowerOfTen(-exponent); |
394 } | 395 } |
395 if (upper_boundary.E() > 0) { | 396 if (upper_boundary.E() > 0) { |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
436 if (DoubleStrtod(trimmed, exponent, &guess) || | 437 if (DoubleStrtod(trimmed, exponent, &guess) || |
437 DiyFpStrtod(trimmed, exponent, &guess)) { | 438 DiyFpStrtod(trimmed, exponent, &guess)) { |
438 return guess; | 439 return guess; |
439 } | 440 } |
440 return BignumStrtod(trimmed, exponent, guess); | 441 return BignumStrtod(trimmed, exponent, guess); |
441 } | 442 } |
442 | 443 |
443 } // namespace double_conversion | 444 } // namespace double_conversion |
444 | 445 |
445 } // namespace WTF | 446 } // namespace WTF |
OLD | NEW |