1 // Copyright 2010 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 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. 27 28 #include "config.h" 29 30 #include <limits.h> 31 #include <math.h> 32 33 #include "double-conversion.h" 34 35 #include "bignum-dtoa.h" 36 #include "double.h" 37 #include "fast-dtoa.h" 38 #include "fixed-dtoa.h" 39 #include "strtod.h" 40 #include "utils.h" 41 42 namespace WTF { 43 44 namespace double_conversion { 45 46 const DoubleToStringConverter& DoubleToStringConverter::EcmaScriptConverter() { 47 int flags = UNIQUE_ZERO | EMIT_POSITIVE_EXPONENT_SIGN; 48 static DoubleToStringConverter converter(flags, 49 "Infinity", 50 "NaN", 51 'e', 52 -6, 21, 53 6, 0); 54 return converter; 55 } 56 57 58 bool DoubleToStringConverter::HandleSpecialValues( 59 double value, 60 StringBuilder* result_builder) const { 61 Double double_inspect(value); 62 if (double_inspect.IsInfinite()) { 63 if (infinity_symbol_ == NULL) return false; 64 if (value < 0) { 65 result_builder->AddCharacter('-'); 66 } 67 result_builder->AddString(infinity_symbol_); 68 return true; 69 } 70 if (double_inspect.IsNan()) { 71 if (nan_symbol_ == NULL) return false; 72 result_builder->AddString(nan_symbol_); 73 return true; 74 } 75 return false; 76 } 77 78 79 void DoubleToStringConverter::CreateExponentialRepresentation( 80 const char* decimal_digits, 81 int length, 82 int exponent, 83 StringBuilder* result_builder) const { 84 ASSERT(length != 0); 85 result_builder->AddCharacter(decimal_digits[0]); 86 if (length != 1) { 87 result_builder->AddCharacter('.'); 88 result_builder->AddSubstring(&decimal_digits[1], length-1); 89 } 90 result_builder->AddCharacter(exponent_character_); 91 if (exponent < 0) { 92 result_builder->AddCharacter('-'); 93 exponent = -exponent; 94 } else { 95 if ((flags_ & EMIT_POSITIVE_EXPONENT_SIGN) != 0) { 96 result_builder->AddCharacter('+'); 97 } 98 } 99 if (exponent == 0) { 100 result_builder->AddCharacter('0'); 101 return; 102 } 103 ASSERT(exponent < 1e4); 104 const int kMaxExponentLength = 5; 105 char buffer[kMaxExponentLength + 1]; 106 int first_char_pos = kMaxExponentLength; 107 buffer[first_char_pos] = '\0'; 108 while (exponent > 0) { 109 buffer[--first_char_pos] = '0' + (exponent % 10); 110 exponent /= 10; 111 } 112 result_builder->AddSubstring(&buffer[first_char_pos], 113 kMaxExponentLength - first_char_pos); 114 } 115 116 117 void DoubleToStringConverter::CreateDecimalRepresentation( 118 const char* decimal_digits, 119 int length, 120 int decimal_point, 121 int digits_after_point, 122 StringBuilder* result_builder) const { 123 // Create a representation that is padded with zeros if needed. 124 if (decimal_point <= 0) { 125 // "0.00000decimal_rep". 126 result_builder->AddCharacter('0'); 127 if (digits_after_point > 0) { 128 result_builder->AddCharacter('.'); 129 result_builder->AddPadding('0', -decimal_point); 130 ASSERT(length <= digits_after_point - (-decimal_point)); 131 result_builder->AddSubstring(decimal_digits, length); 132 int remaining_digits = digits_after_point - (-decimal_point) - length; 133 result_builder->AddPadding('0', remaining_digits); 134 } 135 } else if (decimal_point >= length) { 136 // "decimal_rep0000.00000" or "decimal_rep.0000" 137 result_builder->AddSubstring(decimal_digits, length); 138 result_builder->AddPadding('0', decimal_point - length); 139 if (digits_after_point > 0) { 140 result_builder->AddCharacter('.'); 141 result_builder->AddPadding('0', digits_after_point); 142 } 143 } else { 144 // "decima.l_rep000" 145 ASSERT(digits_after_point > 0); 146 result_builder->AddSubstring(decimal_digits, decimal_point); 147 result_builder->AddCharacter('.'); 148 ASSERT(length - decimal_point <= digits_after_point); 149 result_builder->AddSubstring(&decimal_digits[decimal_point], 150 length - decimal_point); 151 int remaining_digits = digits_after_point - (length - decimal_point); 152 result_builder->AddPadding('0', remaining_digits); 153 } 154 if (digits_after_point == 0) { 155 if ((flags_ & EMIT_TRAILING_DECIMAL_POINT) != 0) { 156 result_builder->AddCharacter('.'); 157 } 158 if ((flags_ & EMIT_TRAILING_ZERO_AFTER_POINT) != 0) { 159 result_builder->AddCharacter('0'); 160 } 161 } 162 } 163 164 165 bool DoubleToStringConverter::ToShortest(double value, 166 StringBuilder* result_builder) const { 167 if (Double(value).IsSpecial()) { 168 return HandleSpecialValues(value, result_builder); 169 } 170 171 int decimal_point; 172 bool sign; 173 const int kDecimalRepCapacity = kBase10MaximalLength + 1; 174 char decimal_rep[kDecimalRepCapacity]; 175 int decimal_rep_length; 176 177 DoubleToAscii(value, SHORTEST, 0, decimal_rep, kDecimalRepCapacity, 178 &sign, &decimal_rep_length, &decimal_point); 179 180 bool unique_zero = (flags_ & UNIQUE_ZERO) != 0; 181 if (sign && (value != 0.0 || !unique_zero)) { 182 result_builder->AddCharacter('-'); 183 } 184 185 int exponent = decimal_point - 1; 186 if ((decimal_in_shortest_low_ <= exponent) && 187 (exponent < decimal_in_shortest_high_)) { 188 CreateDecimalRepresentation(decimal_rep, decimal_rep_length, 189 decimal_point, 190 Max(0, decimal_rep_length - decimal_point), 191 result_builder); 192 } else { 193 CreateExponentialRepresentation(decimal_rep, decimal_rep_length, exponent, 194 result_builder); 195 } 196 return true; 197 } 198 199 200 bool DoubleToStringConverter::ToFixed(double value, 201 int requested_digits, 202 StringBuilder* result_builder) const { 203 ASSERT(kMaxFixedDigitsBeforePoint == 60); 204 const double kFirstNonFixed = 1e60; 205 206 if (Double(value).IsSpecial()) { 207 return HandleSpecialValues(value, result_builder); 208 } 209 210 if (requested_digits > kMaxFixedDigitsAfterPoint) return false; 211 if (value >= kFirstNonFixed || value <= -kFirstNonFixed) return false; 212 213 // Find a sufficiently precise decimal representation of n. 214 int decimal_point; 215 bool sign; 216 // Add space for the '\0' byte. 217 const int kDecimalRepCapacity = 218 kMaxFixedDigitsBeforePoint + kMaxFixedDigitsAfterPoint + 1; 219 char decimal_rep[kDecimalRepCapacity]; 220 int decimal_rep_length; 221 DoubleToAscii(value, FIXED, requested_digits, 222 decimal_rep, kDecimalRepCapacity, 223 &sign, &decimal_rep_length, &decimal_point); 224 225 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0); 226 if (sign && (value != 0.0 || !unique_zero)) { 227 result_builder->AddCharacter('-'); 228 } 229 230 CreateDecimalRepresentation(decimal_rep, decimal_rep_length, decimal_point, 231 requested_digits, result_builder); 232 return true; 233 } 234 235 236 bool DoubleToStringConverter::ToExponential( 237 double value, 238 int requested_digits, 239 StringBuilder* result_builder) const { 240 if (Double(value).IsSpecial()) { 241 return HandleSpecialValues(value, result_builder); 242 } 243 244 if (requested_digits < -1) return false; 245 if (requested_digits > kMaxExponentialDigits) return false; 246 247 int decimal_point; 248 bool sign; 249 // Add space for digit before the decimal point and the '\0' character. 250 const int kDecimalRepCapacity = kMaxExponentialDigits + 2; 251 ASSERT(kDecimalRepCapacity > kBase10MaximalLength); 252 char decimal_rep[kDecimalRepCapacity]; 253 int decimal_rep_length; 254 255 if (requested_digits == -1) { 256 DoubleToAscii(value, SHORTEST, 0, 257 decimal_rep, kDecimalRepCapacity, 258 &sign, &decimal_rep_length, &decimal_point); 259 } else { 260 DoubleToAscii(value, PRECISION, requested_digits + 1, 261 decimal_rep, kDecimalRepCapacity, 262 &sign, &decimal_rep_length, &decimal_point); 263 ASSERT(decimal_rep_length <= requested_digits + 1); 264 265 for (int i = decimal_rep_length; i < requested_digits + 1; ++i) { 266 decimal_rep[i] = '0'; 267 } 268 decimal_rep_length = requested_digits + 1; 269 } 270 271 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0); 272 if (sign && (value != 0.0 || !unique_zero)) { 273 result_builder->AddCharacter('-'); 274 } 275 276 int exponent = decimal_point - 1; 277 CreateExponentialRepresentation(decimal_rep, 278 decimal_rep_length, 279 exponent, 280 result_builder); 281 return true; 282 } 283 284 285 bool DoubleToStringConverter::ToPrecision(double value, 286 int precision, 287 StringBuilder* result_builder) const { 288 if (Double(value).IsSpecial()) { 289 return HandleSpecialValues(value, result_builder); 290 } 291 292 if (precision < kMinPrecisionDigits || precision > kMaxPrecisionDigits) { 293 return false; 294 } 295 296 // Find a sufficiently precise decimal representation of n. 297 int decimal_point; 298 bool sign; 299 // Add one for the terminating null character. 300 const int kDecimalRepCapacity = kMaxPrecisionDigits + 1; 301 char decimal_rep[kDecimalRepCapacity]; 302 int decimal_rep_length; 303 304 DoubleToAscii(value, PRECISION, precision, 305 decimal_rep, kDecimalRepCapacity, 306 &sign, &decimal_rep_length, &decimal_point); 307 ASSERT(decimal_rep_length <= precision); 308 309 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0); 310 if (sign && (value != 0.0 || !unique_zero)) { 311 result_builder->AddCharacter('-'); 312 } 313 314 // The exponent if we print the number as x.xxeyyy. That is with the 315 // decimal point after the first digit. 316 int exponent = decimal_point - 1; 317 318 int extra_zero = ((flags_ & EMIT_TRAILING_ZERO_AFTER_POINT) != 0) ? 1 : 0; 319 if ((-decimal_point + 1 > max_leading_padding_zeroes_in_precision_mode_) || 320 (decimal_point - precision + extra_zero > 321 max_trailing_padding_zeroes_in_precision_mode_)) { 322 // Fill buffer to contain 'precision' digits. 323 // Usually the buffer is already at the correct length, but 'DoubleToAscii' 324 // is allowed to return less characters. 325 for (int i = decimal_rep_length; i < precision; ++i) { 326 decimal_rep[i] = '0'; 327 } 328 329 CreateExponentialRepresentation(decimal_rep, 330 precision, 331 exponent, 332 result_builder); 333 } else { 334 CreateDecimalRepresentation(decimal_rep, decimal_rep_length, decimal_point, 335 Max(0, precision - decimal_point), 336 result_builder); 337 } 338 return true; 339 } 340 341 342 static BignumDtoaMode DtoaToBignumDtoaMode( 343 DoubleToStringConverter::DtoaMode dtoa_mode) { 344 switch (dtoa_mode) { 345 case DoubleToStringConverter::SHORTEST: return BIGNUM_DTOA_SHORTEST; 346 case DoubleToStringConverter::FIXED: return BIGNUM_DTOA_FIXED; 347 case DoubleToStringConverter::PRECISION: return BIGNUM_DTOA_PRECISION; 348 default: 349 UNREACHABLE(); 350 return BIGNUM_DTOA_SHORTEST; // To silence compiler. 351 } 352 } 353 354 355 void DoubleToStringConverter::DoubleToAscii(double v, 356 DtoaMode mode, 357 int requested_digits, 358 char* buffer, 359 int buffer_length, 360 bool* sign, 361 int* length, 362 int* point) { 363 Vector<char> vector(buffer, buffer_length); 364 ASSERT(!Double(v).IsSpecial()); 365 ASSERT(mode == SHORTEST || requested_digits >= 0); 366 367 if (Double(v).Sign() < 0) { 368 *sign = true; 369 v = -v; 370 } else { 371 *sign = false; 372 } 373 374 if (mode == PRECISION && requested_digits == 0) { 375 vector[0] = '\0'; 376 *length = 0; 377 return; 378 } 379 380 if (v == 0) { 381 vector[0] = '0'; 382 vector[1] = '\0'; 383 *length = 1; 384 *point = 1; 385 return; 386 } 387 388 bool fast_worked; 389 switch (mode) { 390 case SHORTEST: 391 fast_worked = FastDtoa(v, FAST_DTOA_SHORTEST, 0, vector, length, point); 392 break; 393 case FIXED: 394 fast_worked = FastFixedDtoa(v, requested_digits, vector, length, point); 395 break; 396 case PRECISION: 397 fast_worked = FastDtoa(v, FAST_DTOA_PRECISION, requested_digits, 398 vector, length, point); 399 break; 400 default: 401 UNREACHABLE(); 402 fast_worked = false; 403 } 404 if (fast_worked) return; 405 406 // If the fast dtoa didn't succeed use the slower bignum version. 407 BignumDtoaMode bignum_mode = DtoaToBignumDtoaMode(mode); 408 BignumDtoa(v, bignum_mode, requested_digits, vector, length, point); 409 vector[*length] = '\0'; 410 } 411 412 413 // Maximum number of significant digits in decimal representation. 414 // The longest possible double in decimal representation is 415 // (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074 416 // (768 digits). If we parse a number whose first digits are equal to a 417 // mean of 2 adjacent doubles (that could have up to 769 digits) the result 418 // must be rounded to the bigger one unless the tail consists of zeros, so 419 // we don't need to preserve all the digits. 420 const int kMaxSignificantDigits = 772; 421 422 423 static double SignedZero(bool sign) { 424 return sign ? -0.0 : 0.0; 425 } 426 427 428 double StringToDoubleConverter::StringToDouble( 429 const char* input, 430 size_t length, 431 size_t* processed_characters_count) { 432 const char* current = input; 433 const char* end = input + length; 434 435 *processed_characters_count = 0; 436 437 // To make sure that iterator dereferencing is valid the following 438 // convention is used: 439 // 1. Each '++current' statement is followed by check for equality to 'end'. 440 // 3. If 'current' becomes equal to 'end' the function returns or goes to 441 // 'parsing_done'. 442 // 4. 'current' is not dereferenced after the 'parsing_done' label. 443 // 5. Code before 'parsing_done' may rely on 'current != end'. 444 if (current == end) return 0.0; 445 446 // The longest form of simplified number is: "-<significant digits>.1eXXX\0". 447 const int kBufferSize = kMaxSignificantDigits + 10; 448 char buffer[kBufferSize]; // NOLINT: size is known at compile time. 449 int buffer_pos = 0; 450 451 // Exponent will be adjusted if insignificant digits of the integer part 452 // or insignificant leading zeros of the fractional part are dropped. 453 int exponent = 0; 454 int significant_digits = 0; 455 int insignificant_digits = 0; 456 bool nonzero_digit_dropped = false; 457 bool sign = false; 458 459 if (*current == '+' || *current == '-') { 460 sign = (*current == '-'); 461 ++current; 462 if (current == end) return 0.0; 463 } 464 465 bool leading_zero = false; 466 if (*current == '0') { 467 ++current; 468 if (current == end) { 469 *processed_characters_count = current - input; 470 return SignedZero(sign); 471 } 472 473 leading_zero = true; 474 475 // Ignore leading zeros in the integer part. 476 while (*current == '0') { 477 ++current; 478 if (current == end) { 479 *processed_characters_count = current - input; 480 return SignedZero(sign); 481 } 482 } 483 } 484 485 // Copy significant digits of the integer part (if any) to the buffer. 486 while (*current >= '0' && *current <= '9') { 487 if (significant_digits < kMaxSignificantDigits) { 488 ASSERT(buffer_pos < kBufferSize); 489 buffer[buffer_pos++] = static_cast<char>(*current); 490 significant_digits++; 491 } else { 492 insignificant_digits++; // Move the digit into the exponential part. 493 nonzero_digit_dropped = nonzero_digit_dropped || *current != '0'; 494 } 495 ++current; 496 if (current == end) goto parsing_done; 497 } 498 499 if (*current == '.') { 500 ++current; 501 if (current == end) { 502 if (significant_digits == 0 && !leading_zero) { 503 return 0.0; 504 } else { 505 goto parsing_done; 506 } 507 } 508 509 if (significant_digits == 0) { 510 // Integer part consists of 0 or is absent. Significant digits start after 511 // leading zeros (if any). 512 while (*current == '0') { 513 ++current; 514 if (current == end) { 515 *processed_characters_count = current - input; 516 return SignedZero(sign); 517 } 518 exponent--; // Move this 0 into the exponent. 519 } 520 } 521 522 // There is a fractional part. 523 while (*current >= '0' && *current <= '9') { 524 if (significant_digits < kMaxSignificantDigits) { 525 ASSERT(buffer_pos < kBufferSize); 526 buffer[buffer_pos++] = static_cast<char>(*current); 527 significant_digits++; 528 exponent--; 529 } else { 530 // Ignore insignificant digits in the fractional part. 531 nonzero_digit_dropped = nonzero_digit_dropped || *current != '0'; 532 } 533 ++current; 534 if (current == end) goto parsing_done; 535 } 536 } 537 538 if (!leading_zero && exponent == 0 && significant_digits == 0) { 539 // If leading_zeros is true then the string contains zeros. 540 // If exponent < 0 then string was [+-]\.0*... 541 // If significant_digits != 0 the string is not equal to 0. 542 // Otherwise there are no digits in the string. 543 return 0.0; 544 } 545 546 // Parse exponential part. 547 if (*current == 'e' || *current == 'E') { 548 ++current; 549 if (current == end) { 550 --current; 551 goto parsing_done; 552 } 553 char sign = 0; 554 if (*current == '+' || *current == '-') { 555 sign = static_cast<char>(*current); 556 ++current; 557 if (current == end) { 558 current -= 2; 559 goto parsing_done; 560 } 561 } 562 563 if (*current < '0' || *current > '9') { 564 if (sign) 565 --current; 566 --current; 567 goto parsing_done; 568 } 569 570 const int max_exponent = INT_MAX / 2; 571 ASSERT(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2); 572 int num = 0; 573 do { 574 // Check overflow. 575 int digit = *current - '0'; 576 if (num >= max_exponent / 10 577 && !(num == max_exponent / 10 && digit <= max_exponent % 10)) { 578 num = max_exponent; 579 } else { 580 num = num * 10 + digit; 581 } 582 ++current; 583 } while (current != end && *current >= '0' && *current <= '9'); 584 585 exponent += (sign == '-' ? -num : num); 586 } 587 588 parsing_done: 589 exponent += insignificant_digits; 590 591 if (nonzero_digit_dropped) { 592 buffer[buffer_pos++] = '1'; 593 exponent--; 594 } 595 596 ASSERT(buffer_pos < kBufferSize); 597 buffer[buffer_pos] = '\0'; 598 599 double converted = Strtod(Vector<const char>(buffer, buffer_pos), exponent); 600 *processed_characters_count = current - input; 601 return sign? -converted: converted; 602 } 603 604 } // namespace double_conversion 605 606 } // namespace WTF 607
