conversions.cc revision 25f6136652d8341ed047e7fc1a450af5bd218ea9 
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#include <limits.h>
30
31#include "v8.h"
32
33#include "conversions-inl.h"
34#include "dtoa.h"
35#include "factory.h"
36#include "scanner.h"
37
38namespace v8 {
39namespace internal {
40
41int HexValue(uc32 c) {
42  if ('0' <= c && c <= '9')
43    return c - '0';
44  if ('a' <= c && c <= 'f')
45    return c - 'a' + 10;
46  if ('A' <= c && c <= 'F')
47    return c - 'A' + 10;
48  return -1;
49}
50
51namespace {
52
53// C++-style iterator adaptor for StringInputBuffer
54// (unlike C++ iterators the end-marker has different type).
55class StringInputBufferIterator {
56 public:
57  class EndMarker {};
58
59  explicit StringInputBufferIterator(StringInputBuffer* buffer);
60
61  int operator*() const;
62  void operator++();
63  bool operator==(EndMarker const&) const { return end_; }
64  bool operator!=(EndMarker const& m) const { return !end_; }
65
66 private:
67  StringInputBuffer* const buffer_;
68  int current_;
69  bool end_;
70};
71
72
73StringInputBufferIterator::StringInputBufferIterator(
74    StringInputBuffer* buffer) : buffer_(buffer) {
75  ++(*this);
76}
77
78int StringInputBufferIterator::operator*() const {
79  return current_;
80}
81
82
83void StringInputBufferIterator::operator++() {
84  end_ = !buffer_->has_more();
85  if (!end_) {
86    current_ = buffer_->GetNext();
87  }
88}
89}
90
91
92template <class Iterator, class EndMark>
93static bool SubStringEquals(Iterator* current,
94                            EndMark end,
95                            const char* substring) {
96  ASSERT(**current == *substring);
97  for (substring++; *substring != '\0'; substring++) {
98    ++*current;
99    if (*current == end || **current != *substring) return false;
100  }
101  ++*current;
102  return true;
103}
104
105
106extern "C" double gay_strtod(const char* s00, const char** se);
107
108// Maximum number of significant digits in decimal representation.
109// The longest possible double in decimal representation is
110// (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074
111// (768 digits). If we parse a number whose first digits are equal to a
112// mean of 2 adjacent doubles (that could have up to 769 digits) the result
113// must be rounded to the bigger one unless the tail consists of zeros, so
114// we don't need to preserve all the digits.
115const int kMaxSignificantDigits = 772;
116
117
118static const double JUNK_STRING_VALUE = OS::nan_value();
119
120
121// Returns true if a nonspace found and false if the end has reached.
122template <class Iterator, class EndMark>
123static inline bool AdvanceToNonspace(Iterator* current, EndMark end) {
124  while (*current != end) {
125    if (!Scanner::kIsWhiteSpace.get(**current)) return true;
126    ++*current;
127  }
128  return false;
129}
130
131
132static bool isDigit(int x, int radix) {
133  return (x >= '0' && x <= '9' && x < '0' + radix)
134      || (radix > 10 && x >= 'a' && x < 'a' + radix - 10)
135      || (radix > 10 && x >= 'A' && x < 'A' + radix - 10);
136}
137
138
139static double SignedZero(bool sign) {
140  return sign ? -0.0 : 0.0;
141}
142
143
144// Parsing integers with radix 2, 4, 8, 16, 32. Assumes current != end.
145template <int radix_log_2, class Iterator, class EndMark>
146static double InternalStringToIntDouble(Iterator current,
147                                        EndMark end,
148                                        bool sign,
149                                        bool allow_trailing_junk) {
150  ASSERT(current != end);
151
152  // Skip leading 0s.
153  while (*current == '0') {
154    ++current;
155    if (current == end) return SignedZero(sign);
156  }
157
158  int64_t number = 0;
159  int exponent = 0;
160  const int radix = (1 << radix_log_2);
161
162  do {
163    int digit;
164    if (*current >= '0' && *current <= '9' && *current < '0' + radix) {
165      digit = static_cast<char>(*current) - '0';
166    } else if (radix > 10 && *current >= 'a' && *current < 'a' + radix - 10) {
167      digit = static_cast<char>(*current) - 'a' + 10;
168    } else if (radix > 10 && *current >= 'A' && *current < 'A' + radix - 10) {
169      digit = static_cast<char>(*current) - 'A' + 10;
170    } else {
171      if (allow_trailing_junk || !AdvanceToNonspace(&current, end)) {
172        break;
173      } else {
174        return JUNK_STRING_VALUE;
175      }
176    }
177
178    number = number * radix + digit;
179    int overflow = static_cast<int>(number >> 53);
180    if (overflow != 0) {
181      // Overflow occurred. Need to determine which direction to round the
182      // result.
183      int overflow_bits_count = 1;
184      while (overflow > 1) {
185        overflow_bits_count++;
186        overflow >>= 1;
187      }
188
189      int dropped_bits_mask = ((1 << overflow_bits_count) - 1);
190      int dropped_bits = static_cast<int>(number) & dropped_bits_mask;
191      number >>= overflow_bits_count;
192      exponent = overflow_bits_count;
193
194      bool zero_tail = true;
195      while (true) {
196        ++current;
197        if (current == end || !isDigit(*current, radix)) break;
198        zero_tail = zero_tail && *current == '0';
199        exponent += radix_log_2;
200      }
201
202      if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
203        return JUNK_STRING_VALUE;
204      }
205
206      int middle_value = (1 << (overflow_bits_count - 1));
207      if (dropped_bits > middle_value) {
208        number++;  // Rounding up.
209      } else if (dropped_bits == middle_value) {
210        // Rounding to even to consistency with decimals: half-way case rounds
211        // up if significant part is odd and down otherwise.
212        if ((number & 1) != 0 || !zero_tail) {
213          number++;  // Rounding up.
214        }
215      }
216
217      // Rounding up may cause overflow.
218      if ((number & ((int64_t)1 << 53)) != 0) {
219        exponent++;
220        number >>= 1;
221      }
222      break;
223    }
224    ++current;
225  } while (current != end);
226
227  ASSERT(number < ((int64_t)1 << 53));
228  ASSERT(static_cast<int64_t>(static_cast<double>(number)) == number);
229
230  if (exponent == 0) {
231    if (sign) {
232      if (number == 0) return -0.0;
233      number = -number;
234    }
235    return static_cast<double>(number);
236  }
237
238  ASSERT(number != 0);
239  // The double could be constructed faster from number (mantissa), exponent
240  // and sign. Assuming it's a rare case more simple code is used.
241  return static_cast<double>(sign ? -number : number) * pow(2.0, exponent);
242}
243
244
245template <class Iterator, class EndMark>
246static double InternalStringToInt(Iterator current, EndMark end, int radix) {
247  const bool allow_trailing_junk = true;
248  const double empty_string_val = JUNK_STRING_VALUE;
249
250  if (!AdvanceToNonspace(&current, end)) return empty_string_val;
251
252  bool sign = false;
253  bool leading_zero = false;
254
255  if (*current == '+') {
256    // Ignore leading sign; skip following spaces.
257    ++current;
258    if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
259  } else if (*current == '-') {
260    ++current;
261    if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
262    sign = true;
263  }
264
265  if (radix == 0) {
266    // Radix detection.
267    if (*current == '0') {
268      ++current;
269      if (current == end) return SignedZero(sign);
270      if (*current == 'x' || *current == 'X') {
271        radix = 16;
272        ++current;
273        if (current == end) return JUNK_STRING_VALUE;
274      } else {
275        radix = 8;
276        leading_zero = true;
277      }
278    } else {
279      radix = 10;
280    }
281  } else if (radix == 16) {
282    if (*current == '0') {
283      // Allow "0x" prefix.
284      ++current;
285      if (current == end) return SignedZero(sign);
286      if (*current == 'x' || *current == 'X') {
287        ++current;
288        if (current == end) return JUNK_STRING_VALUE;
289      } else {
290        leading_zero = true;
291      }
292    }
293  }
294
295  if (radix < 2 || radix > 36) return JUNK_STRING_VALUE;
296
297  // Skip leading zeros.
298  while (*current == '0') {
299    leading_zero = true;
300    ++current;
301    if (current == end) return SignedZero(sign);
302  }
303
304  if (!leading_zero && !isDigit(*current, radix)) {
305    return JUNK_STRING_VALUE;
306  }
307
308  if (IsPowerOf2(radix)) {
309    switch (radix) {
310      case 2:
311        return InternalStringToIntDouble<1>(
312                   current, end, sign, allow_trailing_junk);
313      case 4:
314        return InternalStringToIntDouble<2>(
315                   current, end, sign, allow_trailing_junk);
316      case 8:
317        return InternalStringToIntDouble<3>(
318                   current, end, sign, allow_trailing_junk);
319
320      case 16:
321        return InternalStringToIntDouble<4>(
322                   current, end, sign, allow_trailing_junk);
323
324      case 32:
325        return InternalStringToIntDouble<5>(
326                   current, end, sign, allow_trailing_junk);
327      default:
328        UNREACHABLE();
329    }
330  }
331
332  if (radix == 10) {
333    // Parsing with strtod.
334    const int kMaxSignificantDigits = 309;  // Doubles are less than 1.8e308.
335    // The buffer may contain up to kMaxSignificantDigits + 1 digits and a zero
336    // end.
337    const int kBufferSize = kMaxSignificantDigits + 2;
338    char buffer[kBufferSize];
339    int buffer_pos = 0;
340    while (*current >= '0' && *current <= '9') {
341      if (buffer_pos <= kMaxSignificantDigits) {
342        // If the number has more than kMaxSignificantDigits it will be parsed
343        // as infinity.
344        ASSERT(buffer_pos < kBufferSize);
345        buffer[buffer_pos++] = static_cast<char>(*current);
346      }
347      ++current;
348      if (current == end) break;
349    }
350
351    if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
352      return JUNK_STRING_VALUE;
353    }
354
355    ASSERT(buffer_pos < kBufferSize);
356    buffer[buffer_pos++] = '\0';
357    return sign ? -gay_strtod(buffer, NULL) : gay_strtod(buffer, NULL);
358  }
359
360  // The following code causes accumulating rounding error for numbers greater
361  // than ~2^56. It's explicitly allowed in the spec: "if R is not 2, 4, 8, 10,
362  // 16, or 32, then mathInt may be an implementation-dependent approximation to
363  // the mathematical integer value" (15.1.2.2).
364
365  int lim_0 = '0' + (radix < 10 ? radix : 10);
366  int lim_a = 'a' + (radix - 10);
367  int lim_A = 'A' + (radix - 10);
368
369  // NOTE: The code for computing the value may seem a bit complex at
370  // first glance. It is structured to use 32-bit multiply-and-add
371  // loops as long as possible to avoid loosing precision.
372
373  double v = 0.0;
374  bool done = false;
375  do {
376    // Parse the longest part of the string starting at index j
377    // possible while keeping the multiplier, and thus the part
378    // itself, within 32 bits.
379    unsigned int part = 0, multiplier = 1;
380    while (true) {
381      int d;
382      if (*current >= '0' && *current < lim_0) {
383        d = *current - '0';
384      } else if (*current >= 'a' && *current < lim_a) {
385        d = *current - 'a' + 10;
386      } else if (*current >= 'A' && *current < lim_A) {
387        d = *current - 'A' + 10;
388      } else {
389        done = true;
390        break;
391      }
392
393      // Update the value of the part as long as the multiplier fits
394      // in 32 bits. When we can't guarantee that the next iteration
395      // will not overflow the multiplier, we stop parsing the part
396      // by leaving the loop.
397      const unsigned int kMaximumMultiplier = 0xffffffffU / 36;
398      uint32_t m = multiplier * radix;
399      if (m > kMaximumMultiplier) break;
400      part = part * radix + d;
401      multiplier = m;
402      ASSERT(multiplier > part);
403
404      ++current;
405      if (current == end) {
406        done = true;
407        break;
408      }
409    }
410
411    // Update the value and skip the part in the string.
412    v = v * multiplier + part;
413  } while (!done);
414
415  if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
416    return JUNK_STRING_VALUE;
417  }
418
419  return sign ? -v : v;
420}
421
422
423// Converts a string to a double value. Assumes the Iterator supports
424// the following operations:
425// 1. current == end (other ops are not allowed), current != end.
426// 2. *current - gets the current character in the sequence.
427// 3. ++current (advances the position).
428template <class Iterator, class EndMark>
429static double InternalStringToDouble(Iterator current,
430                                     EndMark end,
431                                     int flags,
432                                     double empty_string_val) {
433  // To make sure that iterator dereferencing is valid the following
434  // convention is used:
435  // 1. Each '++current' statement is followed by check for equality to 'end'.
436  // 2. If AdvanceToNonspace returned false then current == end.
437  // 3. If 'current' becomes be equal to 'end' the function returns or goes to
438  // 'parsing_done'.
439  // 4. 'current' is not dereferenced after the 'parsing_done' label.
440  // 5. Code before 'parsing_done' may rely on 'current != end'.
441  if (!AdvanceToNonspace(&current, end)) return empty_string_val;
442
443  const bool allow_trailing_junk = (flags & ALLOW_TRAILING_JUNK) != 0;
444
445  // The longest form of simplified number is: "-<significant digits>'.1eXXX\0".
446  const int kBufferSize = kMaxSignificantDigits + 10;
447  char buffer[kBufferSize];  // NOLINT: size is known at compile time.
448  int buffer_pos = 0;
449
450  // Exponent will be adjusted if insignificant digits of the integer part
451  // or insignificant leading zeros of the fractional part are dropped.
452  int exponent = 0;
453  int significant_digits = 0;
454  int insignificant_digits = 0;
455  bool nonzero_digit_dropped = false;
456  bool fractional_part = false;
457
458  bool sign = false;
459
460  if (*current == '+') {
461    // Ignore leading sign; skip following spaces.
462    ++current;
463    if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
464  } else if (*current == '-') {
465    buffer[buffer_pos++] = '-';
466    ++current;
467    if (!AdvanceToNonspace(&current, end)) return JUNK_STRING_VALUE;
468    sign = true;
469  }
470
471  static const char kInfinitySymbol[] = "Infinity";
472  if (*current == kInfinitySymbol[0]) {
473    if (!SubStringEquals(&current, end, kInfinitySymbol)) {
474      return JUNK_STRING_VALUE;
475    }
476
477    if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
478      return JUNK_STRING_VALUE;
479    }
480
481    ASSERT(buffer_pos == 0 || buffer[0] == '-');
482    return buffer_pos > 0 ? -V8_INFINITY : V8_INFINITY;
483  }
484
485  bool leading_zero = false;
486  if (*current == '0') {
487    ++current;
488    if (current == end) return SignedZero(sign);
489
490    leading_zero = true;
491
492    // It could be hexadecimal value.
493    if ((flags & ALLOW_HEX) && (*current == 'x' || *current == 'X')) {
494      ++current;
495      if (current == end || !isDigit(*current, 16)) {
496        return JUNK_STRING_VALUE;  // "0x".
497      }
498
499      bool sign = (buffer_pos > 0 && buffer[0] == '-');
500      return InternalStringToIntDouble<4>(current,
501                                          end,
502                                          sign,
503                                          allow_trailing_junk);
504    }
505
506    // Ignore leading zeros in the integer part.
507    while (*current == '0') {
508      ++current;
509      if (current == end) return SignedZero(sign);
510    }
511  }
512
513  bool octal = leading_zero && (flags & ALLOW_OCTALS) != 0;
514
515  // Copy significant digits of the integer part (if any) to the buffer.
516  while (*current >= '0' && *current <= '9') {
517    if (significant_digits < kMaxSignificantDigits) {
518      ASSERT(buffer_pos < kBufferSize);
519      buffer[buffer_pos++] = static_cast<char>(*current);
520      significant_digits++;
521      // Will later check if it's an octal in the buffer.
522    } else {
523      insignificant_digits++;  // Move the digit into the exponential part.
524      nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
525    }
526    octal = octal && *current < '8';
527    ++current;
528    if (current == end) goto parsing_done;
529  }
530
531  if (significant_digits == 0) {
532    octal = false;
533  }
534
535  if (*current == '.') {
536    ++current;
537    if (current == end) {
538      if (significant_digits == 0 && !leading_zero) {
539        return JUNK_STRING_VALUE;
540      } else {
541        goto parsing_done;
542      }
543    }
544
545    if (significant_digits == 0) {
546      // octal = false;
547      // Integer part consists of 0 or is absent. Significant digits start after
548      // leading zeros (if any).
549      while (*current == '0') {
550        ++current;
551        if (current == end) return SignedZero(sign);
552        exponent--;  // Move this 0 into the exponent.
553      }
554    }
555
556    ASSERT(buffer_pos < kBufferSize);
557    buffer[buffer_pos++] = '.';
558    fractional_part = true;
559
560    // There is the fractional part.
561    while (*current >= '0' && *current <= '9') {
562      if (significant_digits < kMaxSignificantDigits) {
563        ASSERT(buffer_pos < kBufferSize);
564        buffer[buffer_pos++] = static_cast<char>(*current);
565        significant_digits++;
566      } else {
567        // Ignore insignificant digits in the fractional part.
568        nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
569      }
570      ++current;
571      if (current == end) goto parsing_done;
572    }
573  }
574
575  if (!leading_zero && exponent == 0 && significant_digits == 0) {
576    // If leading_zeros is true then the string contains zeros.
577    // If exponent < 0 then string was [+-]\.0*...
578    // If significant_digits != 0 the string is not equal to 0.
579    // Otherwise there are no digits in the string.
580    return JUNK_STRING_VALUE;
581  }
582
583  // Parse exponential part.
584  if (*current == 'e' || *current == 'E') {
585    if (octal) return JUNK_STRING_VALUE;
586    ++current;
587    if (current == end) {
588      if (allow_trailing_junk) {
589        goto parsing_done;
590      } else {
591        return JUNK_STRING_VALUE;
592      }
593    }
594    char sign = '+';
595    if (*current == '+' || *current == '-') {
596      sign = static_cast<char>(*current);
597      ++current;
598      if (current == end) {
599        if (allow_trailing_junk) {
600          goto parsing_done;
601        } else {
602          return JUNK_STRING_VALUE;
603        }
604      }
605    }
606
607    if (current == end || *current < '0' || *current > '9') {
608      if (allow_trailing_junk) {
609        goto parsing_done;
610      } else {
611        return JUNK_STRING_VALUE;
612      }
613    }
614
615    const int max_exponent = INT_MAX / 2;
616    ASSERT(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2);
617    int num = 0;
618    do {
619      // Check overflow.
620      int digit = *current - '0';
621      if (num >= max_exponent / 10
622          && !(num == max_exponent / 10 && digit <= max_exponent % 10)) {
623        num = max_exponent;
624      } else {
625        num = num * 10 + digit;
626      }
627      ++current;
628    } while (current != end && *current >= '0' && *current <= '9');
629
630    exponent += (sign == '-' ? -num : num);
631  }
632
633  if (!allow_trailing_junk && AdvanceToNonspace(&current, end)) {
634    return JUNK_STRING_VALUE;
635  }
636
637  parsing_done:
638  exponent += insignificant_digits;
639
640  if (octal) {
641    bool sign = buffer[0] == '-';
642    int start_pos = (sign ? 1 : 0);
643
644    return InternalStringToIntDouble<3>(buffer + start_pos,
645                                        buffer + buffer_pos,
646                                        sign,
647                                        allow_trailing_junk);
648  }
649
650  if (nonzero_digit_dropped) {
651    if (insignificant_digits) buffer[buffer_pos++] = '.';
652    buffer[buffer_pos++] = '1';
653  }
654
655  // If the number has no more than kMaxDigitsInInt digits and doesn't have
656  // fractional part it could be parsed faster (without checks for
657  // spaces, overflow, etc.).
658  const int kMaxDigitsInInt = 9 * sizeof(int) / 4;  // NOLINT
659
660  if (exponent != 0) {
661    ASSERT(buffer_pos < kBufferSize);
662    buffer[buffer_pos++] = 'e';
663    if (exponent < 0) {
664      ASSERT(buffer_pos < kBufferSize);
665      buffer[buffer_pos++] = '-';
666      exponent = -exponent;
667    }
668    if (exponent > 999) exponent = 999;  // Result will be Infinity or 0 or -0.
669
670    const int exp_digits = 3;
671    for (int i = 0; i < exp_digits; i++) {
672      buffer[buffer_pos + exp_digits - 1 - i] = '0' + exponent % 10;
673      exponent /= 10;
674    }
675    ASSERT(exponent == 0);
676    buffer_pos += exp_digits;
677  } else if (!fractional_part && significant_digits <= kMaxDigitsInInt) {
678    if (significant_digits == 0) return SignedZero(sign);
679    ASSERT(buffer_pos > 0);
680    int num = 0;
681    int start_pos = (buffer[0] == '-' ? 1 : 0);
682    for (int i = start_pos; i < buffer_pos; i++) {
683      ASSERT(buffer[i] >= '0' && buffer[i] <= '9');
684      num = 10 * num + (buffer[i] - '0');
685    }
686    return static_cast<double>(start_pos == 0 ? num : -num);
687  }
688
689  ASSERT(buffer_pos < kBufferSize);
690  buffer[buffer_pos] = '\0';
691
692  return gay_strtod(buffer, NULL);
693}
694
695double StringToDouble(String* str, int flags, double empty_string_val) {
696  StringShape shape(str);
697  if (shape.IsSequentialAscii()) {
698    const char* begin = SeqAsciiString::cast(str)->GetChars();
699    const char* end = begin + str->length();
700    return InternalStringToDouble(begin, end, flags, empty_string_val);
701  } else if (shape.IsSequentialTwoByte()) {
702    const uc16* begin = SeqTwoByteString::cast(str)->GetChars();
703    const uc16* end = begin + str->length();
704    return InternalStringToDouble(begin, end, flags, empty_string_val);
705  } else {
706    StringInputBuffer buffer(str);
707    return InternalStringToDouble(StringInputBufferIterator(&buffer),
708                                  StringInputBufferIterator::EndMarker(),
709                                  flags,
710                                  empty_string_val);
711  }
712}
713
714
715double StringToInt(String* str, int radix) {
716  StringShape shape(str);
717  if (shape.IsSequentialAscii()) {
718    const char* begin = SeqAsciiString::cast(str)->GetChars();
719    const char* end = begin + str->length();
720    return InternalStringToInt(begin, end, radix);
721  } else if (shape.IsSequentialTwoByte()) {
722    const uc16* begin = SeqTwoByteString::cast(str)->GetChars();
723    const uc16* end = begin + str->length();
724    return InternalStringToInt(begin, end, radix);
725  } else {
726    StringInputBuffer buffer(str);
727    return InternalStringToInt(StringInputBufferIterator(&buffer),
728                               StringInputBufferIterator::EndMarker(),
729                               radix);
730  }
731}
732
733
734double StringToDouble(const char* str, int flags, double empty_string_val) {
735  const char* end = str + StrLength(str);
736
737  return InternalStringToDouble(str, end, flags, empty_string_val);
738}
739
740
741extern "C" char* dtoa(double d, int mode, int ndigits,
742                      int* decpt, int* sign, char** rve);
743
744extern "C" void freedtoa(char* s);
745
746const char* DoubleToCString(double v, Vector<char> buffer) {
747  StringBuilder builder(buffer.start(), buffer.length());
748
749  switch (fpclassify(v)) {
750    case FP_NAN:
751      builder.AddString("NaN");
752      break;
753
754    case FP_INFINITE:
755      if (v < 0.0) {
756        builder.AddString("-Infinity");
757      } else {
758        builder.AddString("Infinity");
759      }
760      break;
761
762    case FP_ZERO:
763      builder.AddCharacter('0');
764      break;
765
766    default: {
767      int decimal_point;
768      int sign;
769      char* decimal_rep;
770      bool used_gay_dtoa = false;
771      const int kV8DtoaBufferCapacity = kBase10MaximalLength + 1;
772      char v8_dtoa_buffer[kV8DtoaBufferCapacity];
773      int length;
774
775      if (DoubleToAscii(v, DTOA_SHORTEST, 0,
776                        Vector<char>(v8_dtoa_buffer, kV8DtoaBufferCapacity),
777                        &sign, &length, &decimal_point)) {
778        decimal_rep = v8_dtoa_buffer;
779      } else {
780        decimal_rep = dtoa(v, 0, 0, &decimal_point, &sign, NULL);
781        used_gay_dtoa = true;
782        length = StrLength(decimal_rep);
783      }
784
785      if (sign) builder.AddCharacter('-');
786
787      if (length <= decimal_point && decimal_point <= 21) {
788        // ECMA-262 section 9.8.1 step 6.
789        builder.AddString(decimal_rep);
790        builder.AddPadding('0', decimal_point - length);
791
792      } else if (0 < decimal_point && decimal_point <= 21) {
793        // ECMA-262 section 9.8.1 step 7.
794        builder.AddSubstring(decimal_rep, decimal_point);
795        builder.AddCharacter('.');
796        builder.AddString(decimal_rep + decimal_point);
797
798      } else if (decimal_point <= 0 && decimal_point > -6) {
799        // ECMA-262 section 9.8.1 step 8.
800        builder.AddString("0.");
801        builder.AddPadding('0', -decimal_point);
802        builder.AddString(decimal_rep);
803
804      } else {
805        // ECMA-262 section 9.8.1 step 9 and 10 combined.
806        builder.AddCharacter(decimal_rep[0]);
807        if (length != 1) {
808          builder.AddCharacter('.');
809          builder.AddString(decimal_rep + 1);
810        }
811        builder.AddCharacter('e');
812        builder.AddCharacter((decimal_point >= 0) ? '+' : '-');
813        int exponent = decimal_point - 1;
814        if (exponent < 0) exponent = -exponent;
815        builder.AddFormatted("%d", exponent);
816      }
817
818      if (used_gay_dtoa) freedtoa(decimal_rep);
819    }
820  }
821  return builder.Finalize();
822}
823
824
825const char* IntToCString(int n, Vector<char> buffer) {
826  bool negative = false;
827  if (n < 0) {
828    // We must not negate the most negative int.
829    if (n == kMinInt) return DoubleToCString(n, buffer);
830    negative = true;
831    n = -n;
832  }
833  // Build the string backwards from the least significant digit.
834  int i = buffer.length();
835  buffer[--i] = '\0';
836  do {
837    buffer[--i] = '0' + (n % 10);
838    n /= 10;
839  } while (n);
840  if (negative) buffer[--i] = '-';
841  return buffer.start() + i;
842}
843
844
845char* DoubleToFixedCString(double value, int f) {
846  const int kMaxDigitsBeforePoint = 20;
847  const double kFirstNonFixed = 1e21;
848  const int kMaxDigitsAfterPoint = 20;
849  ASSERT(f >= 0);
850  ASSERT(f <= kMaxDigitsAfterPoint);
851
852  bool negative = false;
853  double abs_value = value;
854  if (value < 0) {
855    abs_value = -value;
856    negative = true;
857  }
858
859  // If abs_value has more than kMaxDigitsBeforePoint digits before the point
860  // use the non-fixed conversion routine.
861  if (abs_value >= kFirstNonFixed) {
862    char arr[100];
863    Vector<char> buffer(arr, ARRAY_SIZE(arr));
864    return StrDup(DoubleToCString(value, buffer));
865  }
866
867  // Find a sufficiently precise decimal representation of n.
868  int decimal_point;
869  int sign;
870  // Add space for the '.' and the '\0' byte.
871  const int kDecimalRepCapacity =
872      kMaxDigitsBeforePoint + kMaxDigitsAfterPoint + 2;
873  char decimal_rep[kDecimalRepCapacity];
874  int decimal_rep_length;
875  bool status = DoubleToAscii(value, DTOA_FIXED, f,
876                              Vector<char>(decimal_rep, kDecimalRepCapacity),
877                              &sign, &decimal_rep_length, &decimal_point);
878  USE(status);
879  ASSERT(status);
880
881  // Create a representation that is padded with zeros if needed.
882  int zero_prefix_length = 0;
883  int zero_postfix_length = 0;
884
885  if (decimal_point <= 0) {
886    zero_prefix_length = -decimal_point + 1;
887    decimal_point = 1;
888  }
889
890  if (zero_prefix_length + decimal_rep_length < decimal_point + f) {
891    zero_postfix_length = decimal_point + f - decimal_rep_length -
892                          zero_prefix_length;
893  }
894
895  unsigned rep_length =
896      zero_prefix_length + decimal_rep_length + zero_postfix_length;
897  StringBuilder rep_builder(rep_length + 1);
898  rep_builder.AddPadding('0', zero_prefix_length);
899  rep_builder.AddString(decimal_rep);
900  rep_builder.AddPadding('0', zero_postfix_length);
901  char* rep = rep_builder.Finalize();
902
903  // Create the result string by appending a minus and putting in a
904  // decimal point if needed.
905  unsigned result_size = decimal_point + f + 2;
906  StringBuilder builder(result_size + 1);
907  if (negative) builder.AddCharacter('-');
908  builder.AddSubstring(rep, decimal_point);
909  if (f > 0) {
910    builder.AddCharacter('.');
911    builder.AddSubstring(rep + decimal_point, f);
912  }
913  DeleteArray(rep);
914  return builder.Finalize();
915}
916
917
918static char* CreateExponentialRepresentation(char* decimal_rep,
919                                             int exponent,
920                                             bool negative,
921                                             int significant_digits) {
922  bool negative_exponent = false;
923  if (exponent < 0) {
924    negative_exponent = true;
925    exponent = -exponent;
926  }
927
928  // Leave room in the result for appending a minus, for a period, the
929  // letter 'e', a minus or a plus depending on the exponent, and a
930  // three digit exponent.
931  unsigned result_size = significant_digits + 7;
932  StringBuilder builder(result_size + 1);
933
934  if (negative) builder.AddCharacter('-');
935  builder.AddCharacter(decimal_rep[0]);
936  if (significant_digits != 1) {
937    builder.AddCharacter('.');
938    builder.AddString(decimal_rep + 1);
939    int rep_length = StrLength(decimal_rep);
940    builder.AddPadding('0', significant_digits - rep_length);
941  }
942
943  builder.AddCharacter('e');
944  builder.AddCharacter(negative_exponent ? '-' : '+');
945  builder.AddFormatted("%d", exponent);
946  return builder.Finalize();
947}
948
949
950
951char* DoubleToExponentialCString(double value, int f) {
952  // f might be -1 to signal that f was undefined in JavaScript.
953  ASSERT(f >= -1 && f <= 20);
954
955  bool negative = false;
956  if (value < 0) {
957    value = -value;
958    negative = true;
959  }
960
961  // Find a sufficiently precise decimal representation of n.
962  int decimal_point;
963  int sign;
964  char* decimal_rep = NULL;
965  if (f == -1) {
966    decimal_rep = dtoa(value, 0, 0, &decimal_point, &sign, NULL);
967    f = StrLength(decimal_rep) - 1;
968  } else {
969    decimal_rep = dtoa(value, 2, f + 1, &decimal_point, &sign, NULL);
970  }
971  int decimal_rep_length = StrLength(decimal_rep);
972  ASSERT(decimal_rep_length > 0);
973  ASSERT(decimal_rep_length <= f + 1);
974  USE(decimal_rep_length);
975
976  int exponent = decimal_point - 1;
977  char* result =
978      CreateExponentialRepresentation(decimal_rep, exponent, negative, f+1);
979
980  freedtoa(decimal_rep);
981
982  return result;
983}
984
985
986char* DoubleToPrecisionCString(double value, int p) {
987  ASSERT(p >= 1 && p <= 21);
988
989  bool negative = false;
990  if (value < 0) {
991    value = -value;
992    negative = true;
993  }
994
995  // Find a sufficiently precise decimal representation of n.
996  int decimal_point;
997  int sign;
998  char* decimal_rep = dtoa(value, 2, p, &decimal_point, &sign, NULL);
999  int decimal_rep_length = StrLength(decimal_rep);
1000  ASSERT(decimal_rep_length <= p);
1001
1002  int exponent = decimal_point - 1;
1003
1004  char* result = NULL;
1005
1006  if (exponent < -6 || exponent >= p) {
1007    result =
1008        CreateExponentialRepresentation(decimal_rep, exponent, negative, p);
1009  } else {
1010    // Use fixed notation.
1011    //
1012    // Leave room in the result for appending a minus, a period and in
1013    // the case where decimal_point is not positive for a zero in
1014    // front of the period.
1015    unsigned result_size = (decimal_point <= 0)
1016        ? -decimal_point + p + 3
1017        : p + 2;
1018    StringBuilder builder(result_size + 1);
1019    if (negative) builder.AddCharacter('-');
1020    if (decimal_point <= 0) {
1021      builder.AddString("0.");
1022      builder.AddPadding('0', -decimal_point);
1023      builder.AddString(decimal_rep);
1024      builder.AddPadding('0', p - decimal_rep_length);
1025    } else {
1026      const int m = Min(decimal_rep_length, decimal_point);
1027      builder.AddSubstring(decimal_rep, m);
1028      builder.AddPadding('0', decimal_point - decimal_rep_length);
1029      if (decimal_point < p) {
1030        builder.AddCharacter('.');
1031        const int extra = negative ? 2 : 1;
1032        if (decimal_rep_length > decimal_point) {
1033          const int len = StrLength(decimal_rep + decimal_point);
1034          const int n = Min(len, p - (builder.position() - extra));
1035          builder.AddSubstring(decimal_rep + decimal_point, n);
1036        }
1037        builder.AddPadding('0', extra + (p - builder.position()));
1038      }
1039    }
1040    result = builder.Finalize();
1041  }
1042
1043  freedtoa(decimal_rep);
1044  return result;
1045}
1046
1047
1048char* DoubleToRadixCString(double value, int radix) {
1049  ASSERT(radix >= 2 && radix <= 36);
1050
1051  // Character array used for conversion.
1052  static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1053
1054  // Buffer for the integer part of the result. 1024 chars is enough
1055  // for max integer value in radix 2.  We need room for a sign too.
1056  static const int kBufferSize = 1100;
1057  char integer_buffer[kBufferSize];
1058  integer_buffer[kBufferSize - 1] = '\0';
1059
1060  // Buffer for the decimal part of the result.  We only generate up
1061  // to kBufferSize - 1 chars for the decimal part.
1062  char decimal_buffer[kBufferSize];
1063  decimal_buffer[kBufferSize - 1] = '\0';
1064
1065  // Make sure the value is positive.
1066  bool is_negative = value < 0.0;
1067  if (is_negative) value = -value;
1068
1069  // Get the integer part and the decimal part.
1070  double integer_part = floor(value);
1071  double decimal_part = value - integer_part;
1072
1073  // Convert the integer part starting from the back.  Always generate
1074  // at least one digit.
1075  int integer_pos = kBufferSize - 2;
1076  do {
1077    integer_buffer[integer_pos--] =
1078        chars[static_cast<int>(modulo(integer_part, radix))];
1079    integer_part /= radix;
1080  } while (integer_part >= 1.0);
1081  // Sanity check.
1082  ASSERT(integer_pos > 0);
1083  // Add sign if needed.
1084  if (is_negative) integer_buffer[integer_pos--] = '-';
1085
1086  // Convert the decimal part.  Repeatedly multiply by the radix to
1087  // generate the next char.  Never generate more than kBufferSize - 1
1088  // chars.
1089  //
1090  // TODO(1093998): We will often generate a full decimal_buffer of
1091  // chars because hitting zero will often not happen.  The right
1092  // solution would be to continue until the string representation can
1093  // be read back and yield the original value.  To implement this
1094  // efficiently, we probably have to modify dtoa.
1095  int decimal_pos = 0;
1096  while ((decimal_part > 0.0) && (decimal_pos < kBufferSize - 1)) {
1097    decimal_part *= radix;
1098    decimal_buffer[decimal_pos++] =
1099        chars[static_cast<int>(floor(decimal_part))];
1100    decimal_part -= floor(decimal_part);
1101  }
1102  decimal_buffer[decimal_pos] = '\0';
1103
1104  // Compute the result size.
1105  int integer_part_size = kBufferSize - 2 - integer_pos;
1106  // Make room for zero termination.
1107  unsigned result_size = integer_part_size + decimal_pos;
1108  // If the number has a decimal part, leave room for the period.
1109  if (decimal_pos > 0) result_size++;
1110  // Allocate result and fill in the parts.
1111  StringBuilder builder(result_size + 1);
1112  builder.AddSubstring(integer_buffer + integer_pos + 1, integer_part_size);
1113  if (decimal_pos > 0) builder.AddCharacter('.');
1114  builder.AddSubstring(decimal_buffer, decimal_pos);
1115  return builder.Finalize();
1116}
1117
1118
1119} }  // namespace v8::internal
1120