1 // Copyright 2011 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "src/conversions.h" 6 7 #include <limits.h> 8 #include <stdarg.h> 9 #include <cmath> 10 11 #include "src/allocation.h" 12 #include "src/assert-scope.h" 13 #include "src/char-predicates-inl.h" 14 #include "src/codegen.h" 15 #include "src/conversions-inl.h" 16 #include "src/dtoa.h" 17 #include "src/factory.h" 18 #include "src/handles.h" 19 #include "src/list-inl.h" 20 #include "src/strtod.h" 21 #include "src/utils.h" 22 23 #ifndef _STLP_VENDOR_CSTD 24 // STLPort doesn't import fpclassify into the std namespace. 25 using std::fpclassify; 26 #endif 27 28 namespace v8 { 29 namespace internal { 30 31 32 namespace { 33 34 // C++-style iterator adaptor for StringCharacterStream 35 // (unlike C++ iterators the end-marker has different type). 36 class StringCharacterStreamIterator { 37 public: 38 class EndMarker {}; 39 40 explicit StringCharacterStreamIterator(StringCharacterStream* stream); 41 42 uint16_t operator*() const; 43 void operator++(); 44 bool operator==(EndMarker const&) const { return end_; } 45 bool operator!=(EndMarker const& m) const { return !end_; } 46 47 private: 48 StringCharacterStream* const stream_; 49 uint16_t current_; 50 bool end_; 51 }; 52 53 54 StringCharacterStreamIterator::StringCharacterStreamIterator( 55 StringCharacterStream* stream) : stream_(stream) { 56 ++(*this); 57 } 58 59 uint16_t StringCharacterStreamIterator::operator*() const { 60 return current_; 61 } 62 63 64 void StringCharacterStreamIterator::operator++() { 65 end_ = !stream_->HasMore(); 66 if (!end_) { 67 current_ = stream_->GetNext(); 68 } 69 } 70 } // End anonymous namespace. 71 72 73 double StringToDouble(UnicodeCache* unicode_cache, 74 const char* str, int flags, double empty_string_val) { 75 // We cast to const uint8_t* here to avoid instantiating the 76 // InternalStringToDouble() template for const char* as well. 77 const uint8_t* start = reinterpret_cast<const uint8_t*>(str); 78 const uint8_t* end = start + StrLength(str); 79 return InternalStringToDouble(unicode_cache, start, end, flags, 80 empty_string_val); 81 } 82 83 84 double StringToDouble(UnicodeCache* unicode_cache, 85 Vector<const uint8_t> str, 86 int flags, 87 double empty_string_val) { 88 // We cast to const uint8_t* here to avoid instantiating the 89 // InternalStringToDouble() template for const char* as well. 90 const uint8_t* start = reinterpret_cast<const uint8_t*>(str.start()); 91 const uint8_t* end = start + str.length(); 92 return InternalStringToDouble(unicode_cache, start, end, flags, 93 empty_string_val); 94 } 95 96 97 double StringToDouble(UnicodeCache* unicode_cache, 98 Vector<const uc16> str, 99 int flags, 100 double empty_string_val) { 101 const uc16* end = str.start() + str.length(); 102 return InternalStringToDouble(unicode_cache, str.start(), end, flags, 103 empty_string_val); 104 } 105 106 107 // Converts a string into an integer. 108 double StringToInt(UnicodeCache* unicode_cache, 109 Vector<const uint8_t> vector, 110 int radix) { 111 return InternalStringToInt( 112 unicode_cache, vector.start(), vector.start() + vector.length(), radix); 113 } 114 115 116 double StringToInt(UnicodeCache* unicode_cache, 117 Vector<const uc16> vector, 118 int radix) { 119 return InternalStringToInt( 120 unicode_cache, vector.start(), vector.start() + vector.length(), radix); 121 } 122 123 124 const char* DoubleToCString(double v, Vector<char> buffer) { 125 switch (fpclassify(v)) { 126 case FP_NAN: return "NaN"; 127 case FP_INFINITE: return (v < 0.0 ? "-Infinity" : "Infinity"); 128 case FP_ZERO: return "0"; 129 default: { 130 SimpleStringBuilder builder(buffer.start(), buffer.length()); 131 int decimal_point; 132 int sign; 133 const int kV8DtoaBufferCapacity = kBase10MaximalLength + 1; 134 char decimal_rep[kV8DtoaBufferCapacity]; 135 int length; 136 137 DoubleToAscii(v, DTOA_SHORTEST, 0, 138 Vector<char>(decimal_rep, kV8DtoaBufferCapacity), 139 &sign, &length, &decimal_point); 140 141 if (sign) builder.AddCharacter('-'); 142 143 if (length <= decimal_point && decimal_point <= 21) { 144 // ECMA-262 section 9.8.1 step 6. 145 builder.AddString(decimal_rep); 146 builder.AddPadding('0', decimal_point - length); 147 148 } else if (0 < decimal_point && decimal_point <= 21) { 149 // ECMA-262 section 9.8.1 step 7. 150 builder.AddSubstring(decimal_rep, decimal_point); 151 builder.AddCharacter('.'); 152 builder.AddString(decimal_rep + decimal_point); 153 154 } else if (decimal_point <= 0 && decimal_point > -6) { 155 // ECMA-262 section 9.8.1 step 8. 156 builder.AddString("0."); 157 builder.AddPadding('0', -decimal_point); 158 builder.AddString(decimal_rep); 159 160 } else { 161 // ECMA-262 section 9.8.1 step 9 and 10 combined. 162 builder.AddCharacter(decimal_rep[0]); 163 if (length != 1) { 164 builder.AddCharacter('.'); 165 builder.AddString(decimal_rep + 1); 166 } 167 builder.AddCharacter('e'); 168 builder.AddCharacter((decimal_point >= 0) ? '+' : '-'); 169 int exponent = decimal_point - 1; 170 if (exponent < 0) exponent = -exponent; 171 builder.AddDecimalInteger(exponent); 172 } 173 return builder.Finalize(); 174 } 175 } 176 } 177 178 179 const char* IntToCString(int n, Vector<char> buffer) { 180 bool negative = false; 181 if (n < 0) { 182 // We must not negate the most negative int. 183 if (n == kMinInt) return DoubleToCString(n, buffer); 184 negative = true; 185 n = -n; 186 } 187 // Build the string backwards from the least significant digit. 188 int i = buffer.length(); 189 buffer[--i] = '\0'; 190 do { 191 buffer[--i] = '0' + (n % 10); 192 n /= 10; 193 } while (n); 194 if (negative) buffer[--i] = '-'; 195 return buffer.start() + i; 196 } 197 198 199 char* DoubleToFixedCString(double value, int f) { 200 const int kMaxDigitsBeforePoint = 21; 201 const double kFirstNonFixed = 1e21; 202 const int kMaxDigitsAfterPoint = 20; 203 DCHECK(f >= 0); 204 DCHECK(f <= kMaxDigitsAfterPoint); 205 206 bool negative = false; 207 double abs_value = value; 208 if (value < 0) { 209 abs_value = -value; 210 negative = true; 211 } 212 213 // If abs_value has more than kMaxDigitsBeforePoint digits before the point 214 // use the non-fixed conversion routine. 215 if (abs_value >= kFirstNonFixed) { 216 char arr[100]; 217 Vector<char> buffer(arr, arraysize(arr)); 218 return StrDup(DoubleToCString(value, buffer)); 219 } 220 221 // Find a sufficiently precise decimal representation of n. 222 int decimal_point; 223 int sign; 224 // Add space for the '\0' byte. 225 const int kDecimalRepCapacity = 226 kMaxDigitsBeforePoint + kMaxDigitsAfterPoint + 1; 227 char decimal_rep[kDecimalRepCapacity]; 228 int decimal_rep_length; 229 DoubleToAscii(value, DTOA_FIXED, f, 230 Vector<char>(decimal_rep, kDecimalRepCapacity), 231 &sign, &decimal_rep_length, &decimal_point); 232 233 // Create a representation that is padded with zeros if needed. 234 int zero_prefix_length = 0; 235 int zero_postfix_length = 0; 236 237 if (decimal_point <= 0) { 238 zero_prefix_length = -decimal_point + 1; 239 decimal_point = 1; 240 } 241 242 if (zero_prefix_length + decimal_rep_length < decimal_point + f) { 243 zero_postfix_length = decimal_point + f - decimal_rep_length - 244 zero_prefix_length; 245 } 246 247 unsigned rep_length = 248 zero_prefix_length + decimal_rep_length + zero_postfix_length; 249 SimpleStringBuilder rep_builder(rep_length + 1); 250 rep_builder.AddPadding('0', zero_prefix_length); 251 rep_builder.AddString(decimal_rep); 252 rep_builder.AddPadding('0', zero_postfix_length); 253 char* rep = rep_builder.Finalize(); 254 255 // Create the result string by appending a minus and putting in a 256 // decimal point if needed. 257 unsigned result_size = decimal_point + f + 2; 258 SimpleStringBuilder builder(result_size + 1); 259 if (negative) builder.AddCharacter('-'); 260 builder.AddSubstring(rep, decimal_point); 261 if (f > 0) { 262 builder.AddCharacter('.'); 263 builder.AddSubstring(rep + decimal_point, f); 264 } 265 DeleteArray(rep); 266 return builder.Finalize(); 267 } 268 269 270 static char* CreateExponentialRepresentation(char* decimal_rep, 271 int exponent, 272 bool negative, 273 int significant_digits) { 274 bool negative_exponent = false; 275 if (exponent < 0) { 276 negative_exponent = true; 277 exponent = -exponent; 278 } 279 280 // Leave room in the result for appending a minus, for a period, the 281 // letter 'e', a minus or a plus depending on the exponent, and a 282 // three digit exponent. 283 unsigned result_size = significant_digits + 7; 284 SimpleStringBuilder builder(result_size + 1); 285 286 if (negative) builder.AddCharacter('-'); 287 builder.AddCharacter(decimal_rep[0]); 288 if (significant_digits != 1) { 289 builder.AddCharacter('.'); 290 builder.AddString(decimal_rep + 1); 291 int rep_length = StrLength(decimal_rep); 292 builder.AddPadding('0', significant_digits - rep_length); 293 } 294 295 builder.AddCharacter('e'); 296 builder.AddCharacter(negative_exponent ? '-' : '+'); 297 builder.AddDecimalInteger(exponent); 298 return builder.Finalize(); 299 } 300 301 302 char* DoubleToExponentialCString(double value, int f) { 303 const int kMaxDigitsAfterPoint = 20; 304 // f might be -1 to signal that f was undefined in JavaScript. 305 DCHECK(f >= -1 && f <= kMaxDigitsAfterPoint); 306 307 bool negative = false; 308 if (value < 0) { 309 value = -value; 310 negative = true; 311 } 312 313 // Find a sufficiently precise decimal representation of n. 314 int decimal_point; 315 int sign; 316 // f corresponds to the digits after the point. There is always one digit 317 // before the point. The number of requested_digits equals hence f + 1. 318 // And we have to add one character for the null-terminator. 319 const int kV8DtoaBufferCapacity = kMaxDigitsAfterPoint + 1 + 1; 320 // Make sure that the buffer is big enough, even if we fall back to the 321 // shortest representation (which happens when f equals -1). 322 DCHECK(kBase10MaximalLength <= kMaxDigitsAfterPoint + 1); 323 char decimal_rep[kV8DtoaBufferCapacity]; 324 int decimal_rep_length; 325 326 if (f == -1) { 327 DoubleToAscii(value, DTOA_SHORTEST, 0, 328 Vector<char>(decimal_rep, kV8DtoaBufferCapacity), 329 &sign, &decimal_rep_length, &decimal_point); 330 f = decimal_rep_length - 1; 331 } else { 332 DoubleToAscii(value, DTOA_PRECISION, f + 1, 333 Vector<char>(decimal_rep, kV8DtoaBufferCapacity), 334 &sign, &decimal_rep_length, &decimal_point); 335 } 336 DCHECK(decimal_rep_length > 0); 337 DCHECK(decimal_rep_length <= f + 1); 338 339 int exponent = decimal_point - 1; 340 char* result = 341 CreateExponentialRepresentation(decimal_rep, exponent, negative, f+1); 342 343 return result; 344 } 345 346 347 char* DoubleToPrecisionCString(double value, int p) { 348 const int kMinimalDigits = 1; 349 const int kMaximalDigits = 21; 350 DCHECK(p >= kMinimalDigits && p <= kMaximalDigits); 351 USE(kMinimalDigits); 352 353 bool negative = false; 354 if (value < 0) { 355 value = -value; 356 negative = true; 357 } 358 359 // Find a sufficiently precise decimal representation of n. 360 int decimal_point; 361 int sign; 362 // Add one for the terminating null character. 363 const int kV8DtoaBufferCapacity = kMaximalDigits + 1; 364 char decimal_rep[kV8DtoaBufferCapacity]; 365 int decimal_rep_length; 366 367 DoubleToAscii(value, DTOA_PRECISION, p, 368 Vector<char>(decimal_rep, kV8DtoaBufferCapacity), 369 &sign, &decimal_rep_length, &decimal_point); 370 DCHECK(decimal_rep_length <= p); 371 372 int exponent = decimal_point - 1; 373 374 char* result = NULL; 375 376 if (exponent < -6 || exponent >= p) { 377 result = 378 CreateExponentialRepresentation(decimal_rep, exponent, negative, p); 379 } else { 380 // Use fixed notation. 381 // 382 // Leave room in the result for appending a minus, a period and in 383 // the case where decimal_point is not positive for a zero in 384 // front of the period. 385 unsigned result_size = (decimal_point <= 0) 386 ? -decimal_point + p + 3 387 : p + 2; 388 SimpleStringBuilder builder(result_size + 1); 389 if (negative) builder.AddCharacter('-'); 390 if (decimal_point <= 0) { 391 builder.AddString("0."); 392 builder.AddPadding('0', -decimal_point); 393 builder.AddString(decimal_rep); 394 builder.AddPadding('0', p - decimal_rep_length); 395 } else { 396 const int m = Min(decimal_rep_length, decimal_point); 397 builder.AddSubstring(decimal_rep, m); 398 builder.AddPadding('0', decimal_point - decimal_rep_length); 399 if (decimal_point < p) { 400 builder.AddCharacter('.'); 401 const int extra = negative ? 2 : 1; 402 if (decimal_rep_length > decimal_point) { 403 const int len = StrLength(decimal_rep + decimal_point); 404 const int n = Min(len, p - (builder.position() - extra)); 405 builder.AddSubstring(decimal_rep + decimal_point, n); 406 } 407 builder.AddPadding('0', extra + (p - builder.position())); 408 } 409 } 410 result = builder.Finalize(); 411 } 412 413 return result; 414 } 415 416 char* DoubleToRadixCString(double value, int radix) { 417 DCHECK(radix >= 2 && radix <= 36); 418 DCHECK(std::isfinite(value)); 419 DCHECK_NE(0.0, value); 420 // Character array used for conversion. 421 static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz"; 422 423 // Temporary buffer for the result. We start with the decimal point in the 424 // middle and write to the left for the integer part and to the right for the 425 // fractional part. 1024 characters for the exponent and 52 for the mantissa 426 // either way, with additional space for sign, decimal point and string 427 // termination should be sufficient. 428 static const int kBufferSize = 2200; 429 char buffer[kBufferSize]; 430 int integer_cursor = kBufferSize / 2; 431 int fraction_cursor = integer_cursor; 432 433 bool negative = value < 0; 434 if (negative) value = -value; 435 436 // Split the value into an integer part and a fractional part. 437 double integer = std::floor(value); 438 double fraction = value - integer; 439 // We only compute fractional digits up to the input double's precision. 440 double delta = 0.5 * (Double(value).NextDouble() - value); 441 delta = std::max(Double(0.0).NextDouble(), delta); 442 DCHECK_GT(delta, 0.0); 443 if (fraction > delta) { 444 // Insert decimal point. 445 buffer[fraction_cursor++] = '.'; 446 do { 447 // Shift up by one digit. 448 fraction *= radix; 449 delta *= radix; 450 // Write digit. 451 int digit = static_cast<int>(fraction); 452 buffer[fraction_cursor++] = chars[digit]; 453 // Calculate remainder. 454 fraction -= digit; 455 // Round to even. 456 if (fraction > 0.5 || (fraction == 0.5 && (digit & 1))) { 457 if (fraction + delta > 1) { 458 // We need to back trace already written digits in case of carry-over. 459 while (true) { 460 fraction_cursor--; 461 if (fraction_cursor == kBufferSize / 2) { 462 CHECK_EQ('.', buffer[fraction_cursor]); 463 // Carry over to the integer part. 464 integer += 1; 465 break; 466 } 467 char c = buffer[fraction_cursor]; 468 // Reconstruct digit. 469 int digit = c > '9' ? (c - 'a' + 10) : (c - '0'); 470 if (digit + 1 < radix) { 471 buffer[fraction_cursor++] = chars[digit + 1]; 472 break; 473 } 474 } 475 break; 476 } 477 } 478 } while (fraction > delta); 479 } 480 481 // Compute integer digits. Fill unrepresented digits with zero. 482 while (Double(integer / radix).Exponent() > 0) { 483 integer /= radix; 484 buffer[--integer_cursor] = '0'; 485 } 486 do { 487 double remainder = modulo(integer, radix); 488 buffer[--integer_cursor] = chars[static_cast<int>(remainder)]; 489 integer = (integer - remainder) / radix; 490 } while (integer > 0); 491 492 // Add sign and terminate string. 493 if (negative) buffer[--integer_cursor] = '-'; 494 buffer[fraction_cursor++] = '\0'; 495 DCHECK_LT(fraction_cursor, kBufferSize); 496 DCHECK_LE(0, integer_cursor); 497 // Allocate new string as return value. 498 char* result = NewArray<char>(fraction_cursor - integer_cursor); 499 memcpy(result, buffer + integer_cursor, fraction_cursor - integer_cursor); 500 return result; 501 } 502 503 504 // ES6 18.2.4 parseFloat(string) 505 double StringToDouble(UnicodeCache* unicode_cache, Handle<String> string, 506 int flags, double empty_string_val) { 507 Handle<String> flattened = String::Flatten(string); 508 { 509 DisallowHeapAllocation no_gc; 510 String::FlatContent flat = flattened->GetFlatContent(); 511 DCHECK(flat.IsFlat()); 512 if (flat.IsOneByte()) { 513 return StringToDouble(unicode_cache, flat.ToOneByteVector(), flags, 514 empty_string_val); 515 } else { 516 return StringToDouble(unicode_cache, flat.ToUC16Vector(), flags, 517 empty_string_val); 518 } 519 } 520 } 521 522 523 bool IsSpecialIndex(UnicodeCache* unicode_cache, String* string) { 524 // Max length of canonical double: -X.XXXXXXXXXXXXXXXXX-eXXX 525 const int kBufferSize = 24; 526 const int length = string->length(); 527 if (length == 0 || length > kBufferSize) return false; 528 uint16_t buffer[kBufferSize]; 529 String::WriteToFlat(string, buffer, 0, length); 530 // If the first char is not a digit or a '-' or we can't match 'NaN' or 531 // '(-)Infinity', bailout immediately. 532 int offset = 0; 533 if (!IsDecimalDigit(buffer[0])) { 534 if (buffer[0] == '-') { 535 if (length == 1) return false; // Just '-' is bad. 536 if (!IsDecimalDigit(buffer[1])) { 537 if (buffer[1] == 'I' && length == 9) { 538 // Allow matching of '-Infinity' below. 539 } else { 540 return false; 541 } 542 } 543 offset++; 544 } else if (buffer[0] == 'I' && length == 8) { 545 // Allow matching of 'Infinity' below. 546 } else if (buffer[0] == 'N' && length == 3) { 547 // Match NaN. 548 return buffer[1] == 'a' && buffer[2] == 'N'; 549 } else { 550 return false; 551 } 552 } 553 // Expected fast path: key is an integer. 554 static const int kRepresentableIntegerLength = 15; // (-)XXXXXXXXXXXXXXX 555 if (length - offset <= kRepresentableIntegerLength) { 556 const int initial_offset = offset; 557 bool matches = true; 558 for (; offset < length; offset++) { 559 matches &= IsDecimalDigit(buffer[offset]); 560 } 561 if (matches) { 562 // Match 0 and -0. 563 if (buffer[initial_offset] == '0') return initial_offset == length - 1; 564 return true; 565 } 566 } 567 // Slow path: test DoubleToString(StringToDouble(string)) == string. 568 Vector<const uint16_t> vector(buffer, length); 569 double d = StringToDouble(unicode_cache, vector, NO_FLAGS); 570 if (std::isnan(d)) return false; 571 // Compute reverse string. 572 char reverse_buffer[kBufferSize + 1]; // Result will be /0 terminated. 573 Vector<char> reverse_vector(reverse_buffer, arraysize(reverse_buffer)); 574 const char* reverse_string = DoubleToCString(d, reverse_vector); 575 for (int i = 0; i < length; ++i) { 576 if (static_cast<uint16_t>(reverse_string[i]) != buffer[i]) return false; 577 } 578 return true; 579 } 580 } // namespace internal 581 } // namespace v8 582