conversions.cc 35.2 KB
Newer Older
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include <stdarg.h>
29
#include <limits.h>
30 31 32 33

#include "v8.h"

#include "conversions-inl.h"
34
#include "dtoa.h"
35
#include "factory.h"
36
#include "scanner-base.h"
37
#include "strtod.h"
38

39 40
namespace v8 {
namespace internal {
41

42
namespace {
43

44 45 46 47 48
// C++-style iterator adaptor for StringInputBuffer
// (unlike C++ iterators the end-marker has different type).
class StringInputBufferIterator {
 public:
  class EndMarker {};
49

50
  explicit StringInputBufferIterator(StringInputBuffer* buffer);
51

52 53 54 55
  int operator*() const;
  void operator++();
  bool operator==(EndMarker const&) const { return end_; }
  bool operator!=(EndMarker const& m) const { return !end_; }
56

57 58 59 60 61
 private:
  StringInputBuffer* const buffer_;
  int current_;
  bool end_;
};
62 63


64 65 66 67 68 69 70
StringInputBufferIterator::StringInputBufferIterator(
    StringInputBuffer* buffer) : buffer_(buffer) {
  ++(*this);
}

int StringInputBufferIterator::operator*() const {
  return current_;
71 72 73
}


74 75 76 77 78 79
void StringInputBufferIterator::operator++() {
  end_ = !buffer_->has_more();
  if (!end_) {
    current_ = buffer_->GetNext();
  }
}
80 81 82
}


83 84 85 86 87 88 89 90
template <class Iterator, class EndMark>
static bool SubStringEquals(Iterator* current,
                            EndMark end,
                            const char* substring) {
  ASSERT(**current == *substring);
  for (substring++; *substring != '\0'; substring++) {
    ++*current;
    if (*current == end || **current != *substring) return false;
91
  }
92
  ++*current;
93 94 95 96
  return true;
}


97 98 99 100 101 102 103 104
// Maximum number of significant digits in decimal representation.
// The longest possible double in decimal representation is
// (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074
// (768 digits). If we parse a number whose first digits are equal to a
// mean of 2 adjacent doubles (that could have up to 769 digits) the result
// must be rounded to the bigger one unless the tail consists of zeros, so
// we don't need to preserve all the digits.
const int kMaxSignificantDigits = 772;
105 106 107 108 109


static const double JUNK_STRING_VALUE = OS::nan_value();


110 111
// Returns true if a nonspace found and false if the end has reached.
template <class Iterator, class EndMark>
112
static inline bool AdvanceToNonspace(UnicodeCache* unicode_cache,
113 114
                                     Iterator* current,
                                     EndMark end) {
115
  while (*current != end) {
116
    if (!unicode_cache->IsWhiteSpace(**current)) return true;
117 118 119 120 121 122
    ++*current;
  }
  return false;
}


123 124 125 126 127
static bool isDigit(int x, int radix) {
  return (x >= '0' && x <= '9' && x < '0' + radix)
      || (radix > 10 && x >= 'a' && x < 'a' + radix - 10)
      || (radix > 10 && x >= 'A' && x < 'A' + radix - 10);
}
128 129


130 131
static double SignedZero(bool negative) {
  return negative ? -0.0 : 0.0;
132 133 134
}


135 136
// Parsing integers with radix 2, 4, 8, 16, 32. Assumes current != end.
template <int radix_log_2, class Iterator, class EndMark>
137
static double InternalStringToIntDouble(UnicodeCache* unicode_cache,
138
                                        Iterator current,
139
                                        EndMark end,
140
                                        bool negative,
141
                                        bool allow_trailing_junk) {
142
  ASSERT(current != end);
143 144 145 146

  // Skip leading 0s.
  while (*current == '0') {
    ++current;
147
    if (current == end) return SignedZero(negative);
148 149
  }

150 151 152 153 154 155 156 157 158 159 160 161
  int64_t number = 0;
  int exponent = 0;
  const int radix = (1 << radix_log_2);

  do {
    int digit;
    if (*current >= '0' && *current <= '9' && *current < '0' + radix) {
      digit = static_cast<char>(*current) - '0';
    } else if (radix > 10 && *current >= 'a' && *current < 'a' + radix - 10) {
      digit = static_cast<char>(*current) - 'a' + 10;
    } else if (radix > 10 && *current >= 'A' && *current < 'A' + radix - 10) {
      digit = static_cast<char>(*current) - 'A' + 10;
162
    } else {
163
      if (allow_trailing_junk ||
164
          !AdvanceToNonspace(unicode_cache, &current, end)) {
165 166 167 168
        break;
      } else {
        return JUNK_STRING_VALUE;
      }
169 170
    }

171
    number = number * radix + digit;
172
    int overflow = static_cast<int>(number >> 53);
173 174 175 176 177 178 179 180
    if (overflow != 0) {
      // Overflow occurred. Need to determine which direction to round the
      // result.
      int overflow_bits_count = 1;
      while (overflow > 1) {
        overflow_bits_count++;
        overflow >>= 1;
      }
181

182
      int dropped_bits_mask = ((1 << overflow_bits_count) - 1);
183
      int dropped_bits = static_cast<int>(number) & dropped_bits_mask;
184 185
      number >>= overflow_bits_count;
      exponent = overflow_bits_count;
186

187 188 189 190 191 192 193 194
      bool zero_tail = true;
      while (true) {
        ++current;
        if (current == end || !isDigit(*current, radix)) break;
        zero_tail = zero_tail && *current == '0';
        exponent += radix_log_2;
      }

195
      if (!allow_trailing_junk &&
196
          AdvanceToNonspace(unicode_cache, &current, end)) {
197 198
        return JUNK_STRING_VALUE;
      }
199

200 201 202 203 204 205 206 207 208 209
      int middle_value = (1 << (overflow_bits_count - 1));
      if (dropped_bits > middle_value) {
        number++;  // Rounding up.
      } else if (dropped_bits == middle_value) {
        // Rounding to even to consistency with decimals: half-way case rounds
        // up if significant part is odd and down otherwise.
        if ((number & 1) != 0 || !zero_tail) {
          number++;  // Rounding up.
        }
      }
210

211 212 213 214 215 216 217 218 219 220 221 222 223 224
      // Rounding up may cause overflow.
      if ((number & ((int64_t)1 << 53)) != 0) {
        exponent++;
        number >>= 1;
      }
      break;
    }
    ++current;
  } while (current != end);

  ASSERT(number < ((int64_t)1 << 53));
  ASSERT(static_cast<int64_t>(static_cast<double>(number)) == number);

  if (exponent == 0) {
225
    if (negative) {
226 227 228 229
      if (number == 0) return -0.0;
      number = -number;
    }
    return static_cast<double>(number);
230
  }
231 232 233 234

  ASSERT(number != 0);
  // The double could be constructed faster from number (mantissa), exponent
  // and sign. Assuming it's a rare case more simple code is used.
235
  return static_cast<double>(negative ? -number : number) * pow(2.0, exponent);
236 237 238
}


239
template <class Iterator, class EndMark>
240
static double InternalStringToInt(UnicodeCache* unicode_cache,
241 242 243
                                  Iterator current,
                                  EndMark end,
                                  int radix) {
244 245 246
  const bool allow_trailing_junk = true;
  const double empty_string_val = JUNK_STRING_VALUE;

247
  if (!AdvanceToNonspace(unicode_cache, &current, end)) {
248 249
    return empty_string_val;
  }
250

251
  bool negative = false;
252 253 254 255 256
  bool leading_zero = false;

  if (*current == '+') {
    // Ignore leading sign; skip following spaces.
    ++current;
257
    if (current == end) {
258 259
      return JUNK_STRING_VALUE;
    }
260 261
  } else if (*current == '-') {
    ++current;
262
    if (current == end) {
263 264
      return JUNK_STRING_VALUE;
    }
265
    negative = true;
266 267 268 269 270 271
  }

  if (radix == 0) {
    // Radix detection.
    if (*current == '0') {
      ++current;
272
      if (current == end) return SignedZero(negative);
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287
      if (*current == 'x' || *current == 'X') {
        radix = 16;
        ++current;
        if (current == end) return JUNK_STRING_VALUE;
      } else {
        radix = 8;
        leading_zero = true;
      }
    } else {
      radix = 10;
    }
  } else if (radix == 16) {
    if (*current == '0') {
      // Allow "0x" prefix.
      ++current;
288
      if (current == end) return SignedZero(negative);
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303
      if (*current == 'x' || *current == 'X') {
        ++current;
        if (current == end) return JUNK_STRING_VALUE;
      } else {
        leading_zero = true;
      }
    }
  }

  if (radix < 2 || radix > 36) return JUNK_STRING_VALUE;

  // Skip leading zeros.
  while (*current == '0') {
    leading_zero = true;
    ++current;
304
    if (current == end) return SignedZero(negative);
305 306 307 308 309 310 311 312 313 314
  }

  if (!leading_zero && !isDigit(*current, radix)) {
    return JUNK_STRING_VALUE;
  }

  if (IsPowerOf2(radix)) {
    switch (radix) {
      case 2:
        return InternalStringToIntDouble<1>(
315
            unicode_cache, current, end, negative, allow_trailing_junk);
316 317
      case 4:
        return InternalStringToIntDouble<2>(
318
            unicode_cache, current, end, negative, allow_trailing_junk);
319 320
      case 8:
        return InternalStringToIntDouble<3>(
321
            unicode_cache, current, end, negative, allow_trailing_junk);
322 323 324

      case 16:
        return InternalStringToIntDouble<4>(
325
            unicode_cache, current, end, negative, allow_trailing_junk);
326 327 328

      case 32:
        return InternalStringToIntDouble<5>(
329
            unicode_cache, current, end, negative, allow_trailing_junk);
330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353
      default:
        UNREACHABLE();
    }
  }

  if (radix == 10) {
    // Parsing with strtod.
    const int kMaxSignificantDigits = 309;  // Doubles are less than 1.8e308.
    // The buffer may contain up to kMaxSignificantDigits + 1 digits and a zero
    // end.
    const int kBufferSize = kMaxSignificantDigits + 2;
    char buffer[kBufferSize];
    int buffer_pos = 0;
    while (*current >= '0' && *current <= '9') {
      if (buffer_pos <= kMaxSignificantDigits) {
        // If the number has more than kMaxSignificantDigits it will be parsed
        // as infinity.
        ASSERT(buffer_pos < kBufferSize);
        buffer[buffer_pos++] = static_cast<char>(*current);
      }
      ++current;
      if (current == end) break;
    }

354
    if (!allow_trailing_junk &&
355
        AdvanceToNonspace(unicode_cache, &current, end)) {
356 357 358 359
      return JUNK_STRING_VALUE;
    }

    ASSERT(buffer_pos < kBufferSize);
360
    buffer[buffer_pos] = '\0';
361
    Vector<const char> buffer_vector(buffer, buffer_pos);
362
    return negative ? -Strtod(buffer_vector, 0) : Strtod(buffer_vector, 0);
363 364
  }

365 366 367 368
  // The following code causes accumulating rounding error for numbers greater
  // than ~2^56. It's explicitly allowed in the spec: "if R is not 2, 4, 8, 10,
  // 16, or 32, then mathInt may be an implementation-dependent approximation to
  // the mathematical integer value" (15.1.2.2).
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419

  int lim_0 = '0' + (radix < 10 ? radix : 10);
  int lim_a = 'a' + (radix - 10);
  int lim_A = 'A' + (radix - 10);

  // NOTE: The code for computing the value may seem a bit complex at
  // first glance. It is structured to use 32-bit multiply-and-add
  // loops as long as possible to avoid loosing precision.

  double v = 0.0;
  bool done = false;
  do {
    // Parse the longest part of the string starting at index j
    // possible while keeping the multiplier, and thus the part
    // itself, within 32 bits.
    unsigned int part = 0, multiplier = 1;
    while (true) {
      int d;
      if (*current >= '0' && *current < lim_0) {
        d = *current - '0';
      } else if (*current >= 'a' && *current < lim_a) {
        d = *current - 'a' + 10;
      } else if (*current >= 'A' && *current < lim_A) {
        d = *current - 'A' + 10;
      } else {
        done = true;
        break;
      }

      // Update the value of the part as long as the multiplier fits
      // in 32 bits. When we can't guarantee that the next iteration
      // will not overflow the multiplier, we stop parsing the part
      // by leaving the loop.
      const unsigned int kMaximumMultiplier = 0xffffffffU / 36;
      uint32_t m = multiplier * radix;
      if (m > kMaximumMultiplier) break;
      part = part * radix + d;
      multiplier = m;
      ASSERT(multiplier > part);

      ++current;
      if (current == end) {
        done = true;
        break;
      }
    }

    // Update the value and skip the part in the string.
    v = v * multiplier + part;
  } while (!done);

420
  if (!allow_trailing_junk &&
421
      AdvanceToNonspace(unicode_cache, &current, end)) {
422 423 424
    return JUNK_STRING_VALUE;
  }

425
  return negative ? -v : v;
426 427 428
}


429 430 431 432 433 434
// Converts a string to a double value. Assumes the Iterator supports
// the following operations:
// 1. current == end (other ops are not allowed), current != end.
// 2. *current - gets the current character in the sequence.
// 3. ++current (advances the position).
template <class Iterator, class EndMark>
435
static double InternalStringToDouble(UnicodeCache* unicode_cache,
436
                                     Iterator current,
437
                                     EndMark end,
438 439
                                     int flags,
                                     double empty_string_val) {
440 441 442 443 444 445 446 447
  // To make sure that iterator dereferencing is valid the following
  // convention is used:
  // 1. Each '++current' statement is followed by check for equality to 'end'.
  // 2. If AdvanceToNonspace returned false then current == end.
  // 3. If 'current' becomes be equal to 'end' the function returns or goes to
  // 'parsing_done'.
  // 4. 'current' is not dereferenced after the 'parsing_done' label.
  // 5. Code before 'parsing_done' may rely on 'current != end'.
448
  if (!AdvanceToNonspace(unicode_cache, &current, end)) {
449 450
    return empty_string_val;
  }
451 452 453 454 455 456 457 458 459 460 461 462 463 464

  const bool allow_trailing_junk = (flags & ALLOW_TRAILING_JUNK) != 0;

  // The longest form of simplified number is: "-<significant digits>'.1eXXX\0".
  const int kBufferSize = kMaxSignificantDigits + 10;
  char buffer[kBufferSize];  // NOLINT: size is known at compile time.
  int buffer_pos = 0;

  // Exponent will be adjusted if insignificant digits of the integer part
  // or insignificant leading zeros of the fractional part are dropped.
  int exponent = 0;
  int significant_digits = 0;
  int insignificant_digits = 0;
  bool nonzero_digit_dropped = false;
465
  bool fractional_part = false;
466

467
  bool negative = false;
468 469

  if (*current == '+') {
470
    // Ignore leading sign.
471
    ++current;
472
    if (current == end) return JUNK_STRING_VALUE;
473 474
  } else if (*current == '-') {
    ++current;
475
    if (current == end) return JUNK_STRING_VALUE;
476
    negative = true;
477
  }
478

479 480 481 482 483
  static const char kInfinitySymbol[] = "Infinity";
  if (*current == kInfinitySymbol[0]) {
    if (!SubStringEquals(&current, end, kInfinitySymbol)) {
      return JUNK_STRING_VALUE;
    }
484

485
    if (!allow_trailing_junk &&
486
        AdvanceToNonspace(unicode_cache, &current, end)) {
487 488
      return JUNK_STRING_VALUE;
    }
489

490
    ASSERT(buffer_pos == 0);
491
    return negative ? -V8_INFINITY : V8_INFINITY;
492
  }
493

494 495 496
  bool leading_zero = false;
  if (*current == '0') {
    ++current;
497
    if (current == end) return SignedZero(negative);
498

499
    leading_zero = true;
500

501
    // It could be hexadecimal value.
502 503
    if ((flags & ALLOW_HEX) && (*current == 'x' || *current == 'X')) {
      ++current;
504 505 506
      if (current == end || !isDigit(*current, 16)) {
        return JUNK_STRING_VALUE;  // "0x".
      }
507

508
      return InternalStringToIntDouble<4>(unicode_cache,
509
                                          current,
510
                                          end,
511
                                          negative,
512
                                          allow_trailing_junk);
513 514 515 516 517
    }

    // Ignore leading zeros in the integer part.
    while (*current == '0') {
      ++current;
518
      if (current == end) return SignedZero(negative);
519
    }
520 521
  }

522 523 524 525 526 527 528 529 530
  bool octal = leading_zero && (flags & ALLOW_OCTALS) != 0;

  // Copy significant digits of the integer part (if any) to the buffer.
  while (*current >= '0' && *current <= '9') {
    if (significant_digits < kMaxSignificantDigits) {
      ASSERT(buffer_pos < kBufferSize);
      buffer[buffer_pos++] = static_cast<char>(*current);
      significant_digits++;
      // Will later check if it's an octal in the buffer.
531
    } else {
532 533 534 535 536 537 538 539 540 541 542 543 544
      insignificant_digits++;  // Move the digit into the exponential part.
      nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
    }
    octal = octal && *current < '8';
    ++current;
    if (current == end) goto parsing_done;
  }

  if (significant_digits == 0) {
    octal = false;
  }

  if (*current == '.') {
545 546 547
    if (octal && !allow_trailing_junk) return JUNK_STRING_VALUE;
    if (octal) goto parsing_done;

548 549 550
    ++current;
    if (current == end) {
      if (significant_digits == 0 && !leading_zero) {
551
        return JUNK_STRING_VALUE;
552 553 554 555 556 557 558 559 560 561 562
      } else {
        goto parsing_done;
      }
    }

    if (significant_digits == 0) {
      // octal = false;
      // Integer part consists of 0 or is absent. Significant digits start after
      // leading zeros (if any).
      while (*current == '0') {
        ++current;
563
        if (current == end) return SignedZero(negative);
564 565 566 567
        exponent--;  // Move this 0 into the exponent.
      }
    }

568
    // We don't emit a '.', but adjust the exponent instead.
569 570
    fractional_part = true;

571
    // There is a fractional part.
572 573 574 575 576
    while (*current >= '0' && *current <= '9') {
      if (significant_digits < kMaxSignificantDigits) {
        ASSERT(buffer_pos < kBufferSize);
        buffer[buffer_pos++] = static_cast<char>(*current);
        significant_digits++;
577
        exponent--;
578 579 580 581 582 583
      } else {
        // Ignore insignificant digits in the fractional part.
        nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
      }
      ++current;
      if (current == end) goto parsing_done;
584 585 586
    }
  }

587 588 589 590 591 592
  if (!leading_zero && exponent == 0 && significant_digits == 0) {
    // If leading_zeros is true then the string contains zeros.
    // If exponent < 0 then string was [+-]\.0*...
    // If significant_digits != 0 the string is not equal to 0.
    // Otherwise there are no digits in the string.
    return JUNK_STRING_VALUE;
593 594
  }

595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644
  // Parse exponential part.
  if (*current == 'e' || *current == 'E') {
    if (octal) return JUNK_STRING_VALUE;
    ++current;
    if (current == end) {
      if (allow_trailing_junk) {
        goto parsing_done;
      } else {
        return JUNK_STRING_VALUE;
      }
    }
    char sign = '+';
    if (*current == '+' || *current == '-') {
      sign = static_cast<char>(*current);
      ++current;
      if (current == end) {
        if (allow_trailing_junk) {
          goto parsing_done;
        } else {
          return JUNK_STRING_VALUE;
        }
      }
    }

    if (current == end || *current < '0' || *current > '9') {
      if (allow_trailing_junk) {
        goto parsing_done;
      } else {
        return JUNK_STRING_VALUE;
      }
    }

    const int max_exponent = INT_MAX / 2;
    ASSERT(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2);
    int num = 0;
    do {
      // Check overflow.
      int digit = *current - '0';
      if (num >= max_exponent / 10
          && !(num == max_exponent / 10 && digit <= max_exponent % 10)) {
        num = max_exponent;
      } else {
        num = num * 10 + digit;
      }
      ++current;
    } while (current != end && *current >= '0' && *current <= '9');

    exponent += (sign == '-' ? -num : num);
  }

645
  if (!allow_trailing_junk &&
646
      AdvanceToNonspace(unicode_cache, &current, end)) {
647 648 649 650 651 652 653
    return JUNK_STRING_VALUE;
  }

  parsing_done:
  exponent += insignificant_digits;

  if (octal) {
654
    return InternalStringToIntDouble<3>(unicode_cache,
655
                                        buffer,
656
                                        buffer + buffer_pos,
657
                                        negative,
658
                                        allow_trailing_junk);
659 660 661 662
  }

  if (nonzero_digit_dropped) {
    buffer[buffer_pos++] = '1';
663
    exponent--;
664 665 666 667 668
  }

  ASSERT(buffer_pos < kBufferSize);
  buffer[buffer_pos] = '\0';

669
  double converted = Strtod(Vector<const char>(buffer, buffer_pos), exponent);
670
  return negative ? -converted : converted;
671
}
672

673

674 675
double StringToDouble(UnicodeCache* unicode_cache,
                      String* str, int flags, double empty_string_val) {
676 677 678 679
  StringShape shape(str);
  if (shape.IsSequentialAscii()) {
    const char* begin = SeqAsciiString::cast(str)->GetChars();
    const char* end = begin + str->length();
680
    return InternalStringToDouble(unicode_cache, begin, end, flags,
681
                                  empty_string_val);
682 683 684
  } else if (shape.IsSequentialTwoByte()) {
    const uc16* begin = SeqTwoByteString::cast(str)->GetChars();
    const uc16* end = begin + str->length();
685
    return InternalStringToDouble(unicode_cache, begin, end, flags,
686
                                  empty_string_val);
687 688
  } else {
    StringInputBuffer buffer(str);
689
    return InternalStringToDouble(unicode_cache,
690
                                  StringInputBufferIterator(&buffer),
691 692 693 694
                                  StringInputBufferIterator::EndMarker(),
                                  flags,
                                  empty_string_val);
  }
695 696 697
}


698 699 700
double StringToInt(UnicodeCache* unicode_cache,
                   String* str,
                   int radix) {
701 702 703 704
  StringShape shape(str);
  if (shape.IsSequentialAscii()) {
    const char* begin = SeqAsciiString::cast(str)->GetChars();
    const char* end = begin + str->length();
705
    return InternalStringToInt(unicode_cache, begin, end, radix);
706 707 708
  } else if (shape.IsSequentialTwoByte()) {
    const uc16* begin = SeqTwoByteString::cast(str)->GetChars();
    const uc16* end = begin + str->length();
709
    return InternalStringToInt(unicode_cache, begin, end, radix);
710 711
  } else {
    StringInputBuffer buffer(str);
712
    return InternalStringToInt(unicode_cache,
713
                               StringInputBufferIterator(&buffer),
714 715 716 717 718 719
                               StringInputBufferIterator::EndMarker(),
                               radix);
  }
}


720 721
double StringToDouble(UnicodeCache* unicode_cache,
                      const char* str, int flags, double empty_string_val) {
722
  const char* end = str + StrLength(str);
723
  return InternalStringToDouble(unicode_cache, str, end, flags,
724
                                empty_string_val);
725 726 727
}


728 729
double StringToDouble(UnicodeCache* unicode_cache,
                      Vector<const char> str,
730 731 732
                      int flags,
                      double empty_string_val) {
  const char* end = str.start() + str.length();
733
  return InternalStringToDouble(unicode_cache, str.start(), end, flags,
734
                                empty_string_val);
735 736 737
}


738 739
const char* DoubleToCString(double v, Vector<char> buffer) {
  switch (fpclassify(v)) {
740 741 742
    case FP_NAN: return "NaN";
    case FP_INFINITE: return (v < 0.0 ? "-Infinity" : "Infinity");
    case FP_ZERO: return "0";
743
    default: {
744
      StringBuilder builder(buffer.start(), buffer.length());
745 746
      int decimal_point;
      int sign;
747
      const int kV8DtoaBufferCapacity = kBase10MaximalLength + 1;
748
      char decimal_rep[kV8DtoaBufferCapacity];
749
      int length;
750

751 752 753
      DoubleToAscii(v, DTOA_SHORTEST, 0,
                    Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                    &sign, &length, &decimal_point);
754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786

      if (sign) builder.AddCharacter('-');

      if (length <= decimal_point && decimal_point <= 21) {
        // ECMA-262 section 9.8.1 step 6.
        builder.AddString(decimal_rep);
        builder.AddPadding('0', decimal_point - length);

      } else if (0 < decimal_point && decimal_point <= 21) {
        // ECMA-262 section 9.8.1 step 7.
        builder.AddSubstring(decimal_rep, decimal_point);
        builder.AddCharacter('.');
        builder.AddString(decimal_rep + decimal_point);

      } else if (decimal_point <= 0 && decimal_point > -6) {
        // ECMA-262 section 9.8.1 step 8.
        builder.AddString("0.");
        builder.AddPadding('0', -decimal_point);
        builder.AddString(decimal_rep);

      } else {
        // ECMA-262 section 9.8.1 step 9 and 10 combined.
        builder.AddCharacter(decimal_rep[0]);
        if (length != 1) {
          builder.AddCharacter('.');
          builder.AddString(decimal_rep + 1);
        }
        builder.AddCharacter('e');
        builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
        int exponent = decimal_point - 1;
        if (exponent < 0) exponent = -exponent;
        builder.AddFormatted("%d", exponent);
      }
787
    return builder.Finalize();
788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813
    }
  }
}


const char* IntToCString(int n, Vector<char> buffer) {
  bool negative = false;
  if (n < 0) {
    // We must not negate the most negative int.
    if (n == kMinInt) return DoubleToCString(n, buffer);
    negative = true;
    n = -n;
  }
  // Build the string backwards from the least significant digit.
  int i = buffer.length();
  buffer[--i] = '\0';
  do {
    buffer[--i] = '0' + (n % 10);
    n /= 10;
  } while (n);
  if (negative) buffer[--i] = '-';
  return buffer.start() + i;
}


char* DoubleToFixedCString(double value, int f) {
814
  const int kMaxDigitsBeforePoint = 21;
815 816
  const double kFirstNonFixed = 1e21;
  const int kMaxDigitsAfterPoint = 20;
817
  ASSERT(f >= 0);
818
  ASSERT(f <= kMaxDigitsAfterPoint);
819 820 821 822 823 824 825 826

  bool negative = false;
  double abs_value = value;
  if (value < 0) {
    abs_value = -value;
    negative = true;
  }

827 828 829
  // If abs_value has more than kMaxDigitsBeforePoint digits before the point
  // use the non-fixed conversion routine.
  if (abs_value >= kFirstNonFixed) {
830 831 832 833 834 835 836 837
    char arr[100];
    Vector<char> buffer(arr, ARRAY_SIZE(arr));
    return StrDup(DoubleToCString(value, buffer));
  }

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
838
  // Add space for the '\0' byte.
839
  const int kDecimalRepCapacity =
840
      kMaxDigitsBeforePoint + kMaxDigitsAfterPoint + 1;
841 842
  char decimal_rep[kDecimalRepCapacity];
  int decimal_rep_length;
843 844 845
  DoubleToAscii(value, DTOA_FIXED, f,
                Vector<char>(decimal_rep, kDecimalRepCapacity),
                &sign, &decimal_rep_length, &decimal_point);
846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904

  // Create a representation that is padded with zeros if needed.
  int zero_prefix_length = 0;
  int zero_postfix_length = 0;

  if (decimal_point <= 0) {
    zero_prefix_length = -decimal_point + 1;
    decimal_point = 1;
  }

  if (zero_prefix_length + decimal_rep_length < decimal_point + f) {
    zero_postfix_length = decimal_point + f - decimal_rep_length -
                          zero_prefix_length;
  }

  unsigned rep_length =
      zero_prefix_length + decimal_rep_length + zero_postfix_length;
  StringBuilder rep_builder(rep_length + 1);
  rep_builder.AddPadding('0', zero_prefix_length);
  rep_builder.AddString(decimal_rep);
  rep_builder.AddPadding('0', zero_postfix_length);
  char* rep = rep_builder.Finalize();

  // Create the result string by appending a minus and putting in a
  // decimal point if needed.
  unsigned result_size = decimal_point + f + 2;
  StringBuilder builder(result_size + 1);
  if (negative) builder.AddCharacter('-');
  builder.AddSubstring(rep, decimal_point);
  if (f > 0) {
    builder.AddCharacter('.');
    builder.AddSubstring(rep + decimal_point, f);
  }
  DeleteArray(rep);
  return builder.Finalize();
}


static char* CreateExponentialRepresentation(char* decimal_rep,
                                             int exponent,
                                             bool negative,
                                             int significant_digits) {
  bool negative_exponent = false;
  if (exponent < 0) {
    negative_exponent = true;
    exponent = -exponent;
  }

  // Leave room in the result for appending a minus, for a period, the
  // letter 'e', a minus or a plus depending on the exponent, and a
  // three digit exponent.
  unsigned result_size = significant_digits + 7;
  StringBuilder builder(result_size + 1);

  if (negative) builder.AddCharacter('-');
  builder.AddCharacter(decimal_rep[0]);
  if (significant_digits != 1) {
    builder.AddCharacter('.');
    builder.AddString(decimal_rep + 1);
905 906
    int rep_length = StrLength(decimal_rep);
    builder.AddPadding('0', significant_digits - rep_length);
907 908 909 910 911 912 913 914 915 916 917
  }

  builder.AddCharacter('e');
  builder.AddCharacter(negative_exponent ? '-' : '+');
  builder.AddFormatted("%d", exponent);
  return builder.Finalize();
}



char* DoubleToExponentialCString(double value, int f) {
918
  const int kMaxDigitsAfterPoint = 20;
919
  // f might be -1 to signal that f was undefined in JavaScript.
920
  ASSERT(f >= -1 && f <= kMaxDigitsAfterPoint);
921 922 923 924 925 926 927 928 929 930

  bool negative = false;
  if (value < 0) {
    value = -value;
    negative = true;
  }

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
931 932 933 934 935 936 937
  // f corresponds to the digits after the point. There is always one digit
  // before the point. The number of requested_digits equals hence f + 1.
  // And we have to add one character for the null-terminator.
  const int kV8DtoaBufferCapacity = kMaxDigitsAfterPoint + 1 + 1;
  // Make sure that the buffer is big enough, even if we fall back to the
  // shortest representation (which happens when f equals -1).
  ASSERT(kBase10MaximalLength <= kMaxDigitsAfterPoint + 1);
938
  char decimal_rep[kV8DtoaBufferCapacity];
939 940
  int decimal_rep_length;

941
  if (f == -1) {
942 943 944 945
    DoubleToAscii(value, DTOA_SHORTEST, 0,
                  Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                  &sign, &decimal_rep_length, &decimal_point);
    f = decimal_rep_length - 1;
946
  } else {
947 948 949
    DoubleToAscii(value, DTOA_PRECISION, f + 1,
                  Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                  &sign, &decimal_rep_length, &decimal_point);
950 951 952 953 954 955 956 957 958 959 960 961 962
  }
  ASSERT(decimal_rep_length > 0);
  ASSERT(decimal_rep_length <= f + 1);

  int exponent = decimal_point - 1;
  char* result =
      CreateExponentialRepresentation(decimal_rep, exponent, negative, f+1);

  return result;
}


char* DoubleToPrecisionCString(double value, int p) {
963 964 965 966
  const int kMinimalDigits = 1;
  const int kMaximalDigits = 21;
  ASSERT(p >= kMinimalDigits && p <= kMaximalDigits);
  USE(kMinimalDigits);
967 968 969 970 971 972 973 974 975 976

  bool negative = false;
  if (value < 0) {
    value = -value;
    negative = true;
  }

  // Find a sufficiently precise decimal representation of n.
  int decimal_point;
  int sign;
977 978
  // Add one for the terminating null character.
  const int kV8DtoaBufferCapacity = kMaximalDigits + 1;
979
  char decimal_rep[kV8DtoaBufferCapacity];
980 981
  int decimal_rep_length;

982 983 984
  DoubleToAscii(value, DTOA_PRECISION, p,
                Vector<char>(decimal_rep, kV8DtoaBufferCapacity),
                &sign, &decimal_rep_length, &decimal_point);
985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017
  ASSERT(decimal_rep_length <= p);

  int exponent = decimal_point - 1;

  char* result = NULL;

  if (exponent < -6 || exponent >= p) {
    result =
        CreateExponentialRepresentation(decimal_rep, exponent, negative, p);
  } else {
    // Use fixed notation.
    //
    // Leave room in the result for appending a minus, a period and in
    // the case where decimal_point is not positive for a zero in
    // front of the period.
    unsigned result_size = (decimal_point <= 0)
        ? -decimal_point + p + 3
        : p + 2;
    StringBuilder builder(result_size + 1);
    if (negative) builder.AddCharacter('-');
    if (decimal_point <= 0) {
      builder.AddString("0.");
      builder.AddPadding('0', -decimal_point);
      builder.AddString(decimal_rep);
      builder.AddPadding('0', p - decimal_rep_length);
    } else {
      const int m = Min(decimal_rep_length, decimal_point);
      builder.AddSubstring(decimal_rep, m);
      builder.AddPadding('0', decimal_point - decimal_rep_length);
      if (decimal_point < p) {
        builder.AddCharacter('.');
        const int extra = negative ? 2 : 1;
        if (decimal_rep_length > decimal_point) {
1018
          const int len = StrLength(decimal_rep + decimal_point);
1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061
          const int n = Min(len, p - (builder.position() - extra));
          builder.AddSubstring(decimal_rep + decimal_point, n);
        }
        builder.AddPadding('0', extra + (p - builder.position()));
      }
    }
    result = builder.Finalize();
  }

  return result;
}


char* DoubleToRadixCString(double value, int radix) {
  ASSERT(radix >= 2 && radix <= 36);

  // Character array used for conversion.
  static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";

  // Buffer for the integer part of the result. 1024 chars is enough
  // for max integer value in radix 2.  We need room for a sign too.
  static const int kBufferSize = 1100;
  char integer_buffer[kBufferSize];
  integer_buffer[kBufferSize - 1] = '\0';

  // Buffer for the decimal part of the result.  We only generate up
  // to kBufferSize - 1 chars for the decimal part.
  char decimal_buffer[kBufferSize];
  decimal_buffer[kBufferSize - 1] = '\0';

  // Make sure the value is positive.
  bool is_negative = value < 0.0;
  if (is_negative) value = -value;

  // Get the integer part and the decimal part.
  double integer_part = floor(value);
  double decimal_part = value - integer_part;

  // Convert the integer part starting from the back.  Always generate
  // at least one digit.
  int integer_pos = kBufferSize - 2;
  do {
    integer_buffer[integer_pos--] =
1062
        chars[static_cast<int>(modulo(integer_part, radix))];
1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102
    integer_part /= radix;
  } while (integer_part >= 1.0);
  // Sanity check.
  ASSERT(integer_pos > 0);
  // Add sign if needed.
  if (is_negative) integer_buffer[integer_pos--] = '-';

  // Convert the decimal part.  Repeatedly multiply by the radix to
  // generate the next char.  Never generate more than kBufferSize - 1
  // chars.
  //
  // TODO(1093998): We will often generate a full decimal_buffer of
  // chars because hitting zero will often not happen.  The right
  // solution would be to continue until the string representation can
  // be read back and yield the original value.  To implement this
  // efficiently, we probably have to modify dtoa.
  int decimal_pos = 0;
  while ((decimal_part > 0.0) && (decimal_pos < kBufferSize - 1)) {
    decimal_part *= radix;
    decimal_buffer[decimal_pos++] =
        chars[static_cast<int>(floor(decimal_part))];
    decimal_part -= floor(decimal_part);
  }
  decimal_buffer[decimal_pos] = '\0';

  // Compute the result size.
  int integer_part_size = kBufferSize - 2 - integer_pos;
  // Make room for zero termination.
  unsigned result_size = integer_part_size + decimal_pos;
  // If the number has a decimal part, leave room for the period.
  if (decimal_pos > 0) result_size++;
  // Allocate result and fill in the parts.
  StringBuilder builder(result_size + 1);
  builder.AddSubstring(integer_buffer + integer_pos + 1, integer_part_size);
  if (decimal_pos > 0) builder.AddCharacter('.');
  builder.AddSubstring(decimal_buffer, decimal_pos);
  return builder.Finalize();
}


1103 1104 1105 1106
static Mutex* dtoa_lock_one = OS::CreateMutex();
static Mutex* dtoa_lock_zero = OS::CreateMutex();


1107
} }  // namespace v8::internal
1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122


extern "C" {
void ACQUIRE_DTOA_LOCK(int n) {
  ASSERT(n == 0 || n == 1);
  (n == 0 ? v8::internal::dtoa_lock_zero : v8::internal::dtoa_lock_one)->Lock();
}


void FREE_DTOA_LOCK(int n) {
  ASSERT(n == 0 || n == 1);
  (n == 0 ? v8::internal::dtoa_lock_zero : v8::internal::dtoa_lock_one)->
      Unlock();
}
}