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