| 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 |