1 // Copyright 2006-2008 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 <stdarg.h> 29 30 #include "v8.h" 31 32 #include "conversions-inl.h" 33 #include "factory.h" 34 #include "scanner.h" 35 36 namespace v8 { 37 namespace internal { 38 39 int HexValue(uc32 c) { 40 if ('0' <= c && c <= '9') 41 return c - '0'; 42 if ('a' <= c && c <= 'f') 43 return c - 'a' + 10; 44 if ('A' <= c && c <= 'F') 45 return c - 'A' + 10; 46 return -1; 47 } 48 49 50 // Provide a common interface to getting a character at a certain 51 // index from a char* or a String object. 52 static inline int GetChar(const char* str, int index) { 53 ASSERT(index >= 0 && index < StrLength(str)); 54 return str[index]; 55 } 56 57 58 static inline int GetChar(String* str, int index) { 59 return str->Get(index); 60 } 61 62 63 static inline int GetLength(const char* str) { 64 return StrLength(str); 65 } 66 67 68 static inline int GetLength(String* str) { 69 return str->length(); 70 } 71 72 73 static inline const char* GetCString(const char* str, int index) { 74 return str + index; 75 } 76 77 78 static inline const char* GetCString(String* str, int index) { 79 int length = str->length(); 80 char* result = NewArray<char>(length + 1); 81 for (int i = index; i < length; i++) { 82 uc16 c = str->Get(i); 83 if (c <= 127) { 84 result[i - index] = static_cast<char>(c); 85 } else { 86 result[i - index] = 127; // Force number parsing to fail. 87 } 88 } 89 result[length - index] = '\0'; 90 return result; 91 } 92 93 94 static inline void ReleaseCString(const char* original, const char* str) { 95 } 96 97 98 static inline void ReleaseCString(String* original, const char* str) { 99 DeleteArray(const_cast<char *>(str)); 100 } 101 102 103 static inline bool IsSpace(const char* str, int index) { 104 ASSERT(index >= 0 && index < StrLength(str)); 105 return Scanner::kIsWhiteSpace.get(str[index]); 106 } 107 108 109 static inline bool IsSpace(String* str, int index) { 110 return Scanner::kIsWhiteSpace.get(str->Get(index)); 111 } 112 113 114 static inline bool SubStringEquals(const char* str, 115 int index, 116 const char* other) { 117 return strncmp(str + index, other, strlen(other)) != 0; 118 } 119 120 121 static inline bool SubStringEquals(String* str, int index, const char* other) { 122 HandleScope scope; 123 int str_length = str->length(); 124 int other_length = StrLength(other); 125 int end = index + other_length < str_length ? 126 index + other_length : 127 str_length; 128 Handle<String> substring = 129 Factory::NewSubString(Handle<String>(str), index, end); 130 return substring->IsEqualTo(Vector<const char>(other, other_length)); 131 } 132 133 134 // Check if a string should be parsed as an octal number. The string 135 // can be either a char* or a String*. 136 template<class S> 137 static bool ShouldParseOctal(S* s, int i) { 138 int index = i; 139 int len = GetLength(s); 140 if (index < len && GetChar(s, index) != '0') return false; 141 142 // If the first real character (following '0') is not an octal 143 // digit, bail out early. This also takes care of numbers of the 144 // forms 0.xxx and 0exxx by not allowing the first 0 to be 145 // interpreted as an octal. 146 index++; 147 if (index < len) { 148 int d = GetChar(s, index) - '0'; 149 if (d < 0 || d > 7) return false; 150 } else { 151 return false; 152 } 153 154 // Traverse all digits (including the first). If there is an octal 155 // prefix which is not a part of a longer decimal prefix, we return 156 // true. Otherwise, false is returned. 157 while (index < len) { 158 int d = GetChar(s, index++) - '0'; 159 if (d == 8 || d == 9) return false; 160 if (d < 0 || d > 7) return true; 161 } 162 return true; 163 } 164 165 166 extern "C" double gay_strtod(const char* s00, const char** se); 167 168 169 // Parse an int from a string starting a given index and in a given 170 // radix. The string can be either a char* or a String*. 171 template <class S> 172 static int InternalStringToInt(S* s, int i, int radix, double* value) { 173 int len = GetLength(s); 174 175 // Setup limits for computing the value. 176 ASSERT(2 <= radix && radix <= 36); 177 int lim_0 = '0' + (radix < 10 ? radix : 10); 178 int lim_a = 'a' + (radix - 10); 179 int lim_A = 'A' + (radix - 10); 180 181 // NOTE: The code for computing the value may seem a bit complex at 182 // first glance. It is structured to use 32-bit multiply-and-add 183 // loops as long as possible to avoid loosing precision. 184 185 double v = 0.0; 186 int j; 187 for (j = i; j < len;) { 188 // Parse the longest part of the string starting at index j 189 // possible while keeping the multiplier, and thus the part 190 // itself, within 32 bits. 191 uint32_t part = 0, multiplier = 1; 192 int k; 193 for (k = j; k < len; k++) { 194 int c = GetChar(s, k); 195 if (c >= '0' && c < lim_0) { 196 c = c - '0'; 197 } else if (c >= 'a' && c < lim_a) { 198 c = c - 'a' + 10; 199 } else if (c >= 'A' && c < lim_A) { 200 c = c - 'A' + 10; 201 } else { 202 break; 203 } 204 205 // Update the value of the part as long as the multiplier fits 206 // in 32 bits. When we can't guarantee that the next iteration 207 // will not overflow the multiplier, we stop parsing the part 208 // by leaving the loop. 209 static const uint32_t kMaximumMultiplier = 0xffffffffU / 36; 210 uint32_t m = multiplier * radix; 211 if (m > kMaximumMultiplier) break; 212 part = part * radix + c; 213 multiplier = m; 214 ASSERT(multiplier > part); 215 } 216 217 // Compute the number of part digits. If no digits were parsed; 218 // we're done parsing the entire string. 219 int digits = k - j; 220 if (digits == 0) break; 221 222 // Update the value and skip the part in the string. 223 ASSERT(multiplier == 224 pow(static_cast<double>(radix), static_cast<double>(digits))); 225 v = v * multiplier + part; 226 j = k; 227 } 228 229 // If the resulting value is larger than 2^53 the value does not fit 230 // in the mantissa of the double and there is a loss of precision. 231 // When the value is larger than 2^53 the rounding depends on the 232 // code generation. If the code generator spills the double value 233 // it uses 64 bits and if it does not it uses 80 bits. 234 // 235 // If there is a potential for overflow we resort to strtod for 236 // radix 10 numbers to get higher precision. For numbers in another 237 // radix we live with the loss of precision. 238 static const double kPreciseConversionLimit = 9007199254740992.0; 239 if (radix == 10 && v > kPreciseConversionLimit) { 240 const char* cstr = GetCString(s, i); 241 const char* end; 242 v = gay_strtod(cstr, &end); 243 ReleaseCString(s, cstr); 244 } 245 246 *value = v; 247 return j; 248 } 249 250 251 int StringToInt(String* str, int index, int radix, double* value) { 252 return InternalStringToInt(str, index, radix, value); 253 } 254 255 256 int StringToInt(const char* str, int index, int radix, double* value) { 257 return InternalStringToInt(const_cast<char*>(str), index, radix, value); 258 } 259 260 261 static const double JUNK_STRING_VALUE = OS::nan_value(); 262 263 264 // Convert a string to a double value. The string can be either a 265 // char* or a String*. 266 template<class S> 267 static double InternalStringToDouble(S* str, 268 int flags, 269 double empty_string_val) { 270 double result = 0.0; 271 int index = 0; 272 273 int len = GetLength(str); 274 275 // Skip leading spaces. 276 while ((index < len) && IsSpace(str, index)) index++; 277 278 // Is the string empty? 279 if (index >= len) return empty_string_val; 280 281 // Get the first character. 282 uint16_t first = GetChar(str, index); 283 284 // Numbers can only start with '-', '+', '.', 'I' (Infinity), or a digit. 285 if (first != '-' && first != '+' && first != '.' && first != 'I' && 286 (first > '9' || first < '0')) { 287 return JUNK_STRING_VALUE; 288 } 289 290 // Compute sign of result based on first character. 291 int sign = 1; 292 if (first == '-') { 293 sign = -1; 294 index++; 295 // String only containing a '-' are junk chars. 296 if (index == len) return JUNK_STRING_VALUE; 297 } 298 299 // do we have a hex number? 300 // (since the string is 0-terminated, it's ok to look one char beyond the end) 301 if ((flags & ALLOW_HEX) != 0 && 302 (index + 1) < len && 303 GetChar(str, index) == '0' && 304 (GetChar(str, index + 1) == 'x' || GetChar(str, index + 1) == 'X')) { 305 index += 2; 306 index = StringToInt(str, index, 16, &result); 307 } else if ((flags & ALLOW_OCTALS) != 0 && ShouldParseOctal(str, index)) { 308 // NOTE: We optimistically try to parse the number as an octal (if 309 // we're allowed to), even though this is not as dictated by 310 // ECMA-262. The reason for doing this is compatibility with IE and 311 // Firefox. 312 index = StringToInt(str, index, 8, &result); 313 } else { 314 const char* cstr = GetCString(str, index); 315 const char* end; 316 // Optimistically parse the number and then, if that fails, 317 // check if it might have been {+,-,}Infinity. 318 result = gay_strtod(cstr, &end); 319 ReleaseCString(str, cstr); 320 if (result != 0.0 || end != cstr) { 321 // It appears that strtod worked 322 index += static_cast<int>(end - cstr); 323 } else { 324 // Check for {+,-,}Infinity 325 bool is_negative = (GetChar(str, index) == '-'); 326 if (GetChar(str, index) == '+' || GetChar(str, index) == '-') 327 index++; 328 if (!SubStringEquals(str, index, "Infinity")) 329 return JUNK_STRING_VALUE; 330 result = is_negative ? -V8_INFINITY : V8_INFINITY; 331 index += 8; 332 } 333 } 334 335 if ((flags & ALLOW_TRAILING_JUNK) == 0) { 336 // skip trailing spaces 337 while ((index < len) && IsSpace(str, index)) index++; 338 // string ending with junk? 339 if (index < len) return JUNK_STRING_VALUE; 340 } 341 342 return sign * result; 343 } 344 345 346 double StringToDouble(String* str, int flags, double empty_string_val) { 347 return InternalStringToDouble(str, flags, empty_string_val); 348 } 349 350 351 double StringToDouble(const char* str, int flags, double empty_string_val) { 352 return InternalStringToDouble(str, flags, empty_string_val); 353 } 354 355 356 extern "C" char* dtoa(double d, int mode, int ndigits, 357 int* decpt, int* sign, char** rve); 358 359 extern "C" void freedtoa(char* s); 360 361 const char* DoubleToCString(double v, Vector<char> buffer) { 362 StringBuilder builder(buffer.start(), buffer.length()); 363 364 switch (fpclassify(v)) { 365 case FP_NAN: 366 builder.AddString("NaN"); 367 break; 368 369 case FP_INFINITE: 370 if (v < 0.0) { 371 builder.AddString("-Infinity"); 372 } else { 373 builder.AddString("Infinity"); 374 } 375 break; 376 377 case FP_ZERO: 378 builder.AddCharacter('0'); 379 break; 380 381 default: { 382 int decimal_point; 383 int sign; 384 385 char* decimal_rep = dtoa(v, 0, 0, &decimal_point, &sign, NULL); 386 int length = StrLength(decimal_rep); 387 388 if (sign) builder.AddCharacter('-'); 389 390 if (length <= decimal_point && decimal_point <= 21) { 391 // ECMA-262 section 9.8.1 step 6. 392 builder.AddString(decimal_rep); 393 builder.AddPadding('0', decimal_point - length); 394 395 } else if (0 < decimal_point && decimal_point <= 21) { 396 // ECMA-262 section 9.8.1 step 7. 397 builder.AddSubstring(decimal_rep, decimal_point); 398 builder.AddCharacter('.'); 399 builder.AddString(decimal_rep + decimal_point); 400 401 } else if (decimal_point <= 0 && decimal_point > -6) { 402 // ECMA-262 section 9.8.1 step 8. 403 builder.AddString("0."); 404 builder.AddPadding('0', -decimal_point); 405 builder.AddString(decimal_rep); 406 407 } else { 408 // ECMA-262 section 9.8.1 step 9 and 10 combined. 409 builder.AddCharacter(decimal_rep[0]); 410 if (length != 1) { 411 builder.AddCharacter('.'); 412 builder.AddString(decimal_rep + 1); 413 } 414 builder.AddCharacter('e'); 415 builder.AddCharacter((decimal_point >= 0) ? '+' : '-'); 416 int exponent = decimal_point - 1; 417 if (exponent < 0) exponent = -exponent; 418 builder.AddFormatted("%d", exponent); 419 } 420 421 freedtoa(decimal_rep); 422 } 423 } 424 return builder.Finalize(); 425 } 426 427 428 const char* IntToCString(int n, Vector<char> buffer) { 429 bool negative = false; 430 if (n < 0) { 431 // We must not negate the most negative int. 432 if (n == kMinInt) return DoubleToCString(n, buffer); 433 negative = true; 434 n = -n; 435 } 436 // Build the string backwards from the least significant digit. 437 int i = buffer.length(); 438 buffer[--i] = '\0'; 439 do { 440 buffer[--i] = '0' + (n % 10); 441 n /= 10; 442 } while (n); 443 if (negative) buffer[--i] = '-'; 444 return buffer.start() + i; 445 } 446 447 448 char* DoubleToFixedCString(double value, int f) { 449 ASSERT(f >= 0); 450 451 bool negative = false; 452 double abs_value = value; 453 if (value < 0) { 454 abs_value = -value; 455 negative = true; 456 } 457 458 if (abs_value >= 1e21) { 459 char arr[100]; 460 Vector<char> buffer(arr, ARRAY_SIZE(arr)); 461 return StrDup(DoubleToCString(value, buffer)); 462 } 463 464 // Find a sufficiently precise decimal representation of n. 465 int decimal_point; 466 int sign; 467 char* decimal_rep = dtoa(abs_value, 3, f, &decimal_point, &sign, NULL); 468 int decimal_rep_length = StrLength(decimal_rep); 469 470 // Create a representation that is padded with zeros if needed. 471 int zero_prefix_length = 0; 472 int zero_postfix_length = 0; 473 474 if (decimal_point <= 0) { 475 zero_prefix_length = -decimal_point + 1; 476 decimal_point = 1; 477 } 478 479 if (zero_prefix_length + decimal_rep_length < decimal_point + f) { 480 zero_postfix_length = decimal_point + f - decimal_rep_length - 481 zero_prefix_length; 482 } 483 484 unsigned rep_length = 485 zero_prefix_length + decimal_rep_length + zero_postfix_length; 486 StringBuilder rep_builder(rep_length + 1); 487 rep_builder.AddPadding('0', zero_prefix_length); 488 rep_builder.AddString(decimal_rep); 489 rep_builder.AddPadding('0', zero_postfix_length); 490 char* rep = rep_builder.Finalize(); 491 freedtoa(decimal_rep); 492 493 // Create the result string by appending a minus and putting in a 494 // decimal point if needed. 495 unsigned result_size = decimal_point + f + 2; 496 StringBuilder builder(result_size + 1); 497 if (negative) builder.AddCharacter('-'); 498 builder.AddSubstring(rep, decimal_point); 499 if (f > 0) { 500 builder.AddCharacter('.'); 501 builder.AddSubstring(rep + decimal_point, f); 502 } 503 DeleteArray(rep); 504 return builder.Finalize(); 505 } 506 507 508 static char* CreateExponentialRepresentation(char* decimal_rep, 509 int exponent, 510 bool negative, 511 int significant_digits) { 512 bool negative_exponent = false; 513 if (exponent < 0) { 514 negative_exponent = true; 515 exponent = -exponent; 516 } 517 518 // Leave room in the result for appending a minus, for a period, the 519 // letter 'e', a minus or a plus depending on the exponent, and a 520 // three digit exponent. 521 unsigned result_size = significant_digits + 7; 522 StringBuilder builder(result_size + 1); 523 524 if (negative) builder.AddCharacter('-'); 525 builder.AddCharacter(decimal_rep[0]); 526 if (significant_digits != 1) { 527 builder.AddCharacter('.'); 528 builder.AddString(decimal_rep + 1); 529 int rep_length = StrLength(decimal_rep); 530 builder.AddPadding('0', significant_digits - rep_length); 531 } 532 533 builder.AddCharacter('e'); 534 builder.AddCharacter(negative_exponent ? '-' : '+'); 535 builder.AddFormatted("%d", exponent); 536 return builder.Finalize(); 537 } 538 539 540 541 char* DoubleToExponentialCString(double value, int f) { 542 // f might be -1 to signal that f was undefined in JavaScript. 543 ASSERT(f >= -1 && f <= 20); 544 545 bool negative = false; 546 if (value < 0) { 547 value = -value; 548 negative = true; 549 } 550 551 // Find a sufficiently precise decimal representation of n. 552 int decimal_point; 553 int sign; 554 char* decimal_rep = NULL; 555 if (f == -1) { 556 decimal_rep = dtoa(value, 0, 0, &decimal_point, &sign, NULL); 557 f = StrLength(decimal_rep) - 1; 558 } else { 559 decimal_rep = dtoa(value, 2, f + 1, &decimal_point, &sign, NULL); 560 } 561 int decimal_rep_length = StrLength(decimal_rep); 562 ASSERT(decimal_rep_length > 0); 563 ASSERT(decimal_rep_length <= f + 1); 564 USE(decimal_rep_length); 565 566 int exponent = decimal_point - 1; 567 char* result = 568 CreateExponentialRepresentation(decimal_rep, exponent, negative, f+1); 569 570 freedtoa(decimal_rep); 571 572 return result; 573 } 574 575 576 char* DoubleToPrecisionCString(double value, int p) { 577 ASSERT(p >= 1 && p <= 21); 578 579 bool negative = false; 580 if (value < 0) { 581 value = -value; 582 negative = true; 583 } 584 585 // Find a sufficiently precise decimal representation of n. 586 int decimal_point; 587 int sign; 588 char* decimal_rep = dtoa(value, 2, p, &decimal_point, &sign, NULL); 589 int decimal_rep_length = StrLength(decimal_rep); 590 ASSERT(decimal_rep_length <= p); 591 592 int exponent = decimal_point - 1; 593 594 char* result = NULL; 595 596 if (exponent < -6 || exponent >= p) { 597 result = 598 CreateExponentialRepresentation(decimal_rep, exponent, negative, p); 599 } else { 600 // Use fixed notation. 601 // 602 // Leave room in the result for appending a minus, a period and in 603 // the case where decimal_point is not positive for a zero in 604 // front of the period. 605 unsigned result_size = (decimal_point <= 0) 606 ? -decimal_point + p + 3 607 : p + 2; 608 StringBuilder builder(result_size + 1); 609 if (negative) builder.AddCharacter('-'); 610 if (decimal_point <= 0) { 611 builder.AddString("0."); 612 builder.AddPadding('0', -decimal_point); 613 builder.AddString(decimal_rep); 614 builder.AddPadding('0', p - decimal_rep_length); 615 } else { 616 const int m = Min(decimal_rep_length, decimal_point); 617 builder.AddSubstring(decimal_rep, m); 618 builder.AddPadding('0', decimal_point - decimal_rep_length); 619 if (decimal_point < p) { 620 builder.AddCharacter('.'); 621 const int extra = negative ? 2 : 1; 622 if (decimal_rep_length > decimal_point) { 623 const int len = StrLength(decimal_rep + decimal_point); 624 const int n = Min(len, p - (builder.position() - extra)); 625 builder.AddSubstring(decimal_rep + decimal_point, n); 626 } 627 builder.AddPadding('0', extra + (p - builder.position())); 628 } 629 } 630 result = builder.Finalize(); 631 } 632 633 freedtoa(decimal_rep); 634 return result; 635 } 636 637 638 char* DoubleToRadixCString(double value, int radix) { 639 ASSERT(radix >= 2 && radix <= 36); 640 641 // Character array used for conversion. 642 static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz"; 643 644 // Buffer for the integer part of the result. 1024 chars is enough 645 // for max integer value in radix 2. We need room for a sign too. 646 static const int kBufferSize = 1100; 647 char integer_buffer[kBufferSize]; 648 integer_buffer[kBufferSize - 1] = '\0'; 649 650 // Buffer for the decimal part of the result. We only generate up 651 // to kBufferSize - 1 chars for the decimal part. 652 char decimal_buffer[kBufferSize]; 653 decimal_buffer[kBufferSize - 1] = '\0'; 654 655 // Make sure the value is positive. 656 bool is_negative = value < 0.0; 657 if (is_negative) value = -value; 658 659 // Get the integer part and the decimal part. 660 double integer_part = floor(value); 661 double decimal_part = value - integer_part; 662 663 // Convert the integer part starting from the back. Always generate 664 // at least one digit. 665 int integer_pos = kBufferSize - 2; 666 do { 667 integer_buffer[integer_pos--] = 668 chars[static_cast<int>(modulo(integer_part, radix))]; 669 integer_part /= radix; 670 } while (integer_part >= 1.0); 671 // Sanity check. 672 ASSERT(integer_pos > 0); 673 // Add sign if needed. 674 if (is_negative) integer_buffer[integer_pos--] = '-'; 675 676 // Convert the decimal part. Repeatedly multiply by the radix to 677 // generate the next char. Never generate more than kBufferSize - 1 678 // chars. 679 // 680 // TODO(1093998): We will often generate a full decimal_buffer of 681 // chars because hitting zero will often not happen. The right 682 // solution would be to continue until the string representation can 683 // be read back and yield the original value. To implement this 684 // efficiently, we probably have to modify dtoa. 685 int decimal_pos = 0; 686 while ((decimal_part > 0.0) && (decimal_pos < kBufferSize - 1)) { 687 decimal_part *= radix; 688 decimal_buffer[decimal_pos++] = 689 chars[static_cast<int>(floor(decimal_part))]; 690 decimal_part -= floor(decimal_part); 691 } 692 decimal_buffer[decimal_pos] = '\0'; 693 694 // Compute the result size. 695 int integer_part_size = kBufferSize - 2 - integer_pos; 696 // Make room for zero termination. 697 unsigned result_size = integer_part_size + decimal_pos; 698 // If the number has a decimal part, leave room for the period. 699 if (decimal_pos > 0) result_size++; 700 // Allocate result and fill in the parts. 701 StringBuilder builder(result_size + 1); 702 builder.AddSubstring(integer_buffer + integer_pos + 1, integer_part_size); 703 if (decimal_pos > 0) builder.AddCharacter('.'); 704 builder.AddSubstring(decimal_buffer, decimal_pos); 705 return builder.Finalize(); 706 } 707 708 709 } } // namespace v8::internal 710