• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2010 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 "config.h"
29 
30 #include <limits.h>
31 #include <math.h>
32 
33 #include "double-conversion.h"
34 
35 #include "bignum-dtoa.h"
36 #include "double.h"
37 #include "fast-dtoa.h"
38 #include "fixed-dtoa.h"
39 #include "strtod.h"
40 #include "utils.h"
41 
42 namespace WTF {
43 
44 namespace double_conversion {
45 
EcmaScriptConverter()46     const DoubleToStringConverter& DoubleToStringConverter::EcmaScriptConverter() {
47         int flags = UNIQUE_ZERO | EMIT_POSITIVE_EXPONENT_SIGN;
48         static DoubleToStringConverter converter(flags,
49                                                  "Infinity",
50                                                  "NaN",
51                                                  'e',
52                                                  -6, 21,
53                                                  6, 0);
54         return converter;
55     }
56 
57 
HandleSpecialValues(double value,StringBuilder * result_builder) const58     bool DoubleToStringConverter::HandleSpecialValues(
59                                                       double value,
60                                                       StringBuilder* result_builder) const {
61         Double double_inspect(value);
62         if (double_inspect.IsInfinite()) {
63             if (infinity_symbol_ == NULL) return false;
64             if (value < 0) {
65                 result_builder->AddCharacter('-');
66             }
67             result_builder->AddString(infinity_symbol_);
68             return true;
69         }
70         if (double_inspect.IsNan()) {
71             if (nan_symbol_ == NULL) return false;
72             result_builder->AddString(nan_symbol_);
73             return true;
74         }
75         return false;
76     }
77 
78 
CreateExponentialRepresentation(const char * decimal_digits,int length,int exponent,StringBuilder * result_builder) const79     void DoubleToStringConverter::CreateExponentialRepresentation(
80                                                                   const char* decimal_digits,
81                                                                   int length,
82                                                                   int exponent,
83                                                                   StringBuilder* result_builder) const {
84         ASSERT(length != 0);
85         result_builder->AddCharacter(decimal_digits[0]);
86         if (length != 1) {
87             result_builder->AddCharacter('.');
88             result_builder->AddSubstring(&decimal_digits[1], length-1);
89         }
90         result_builder->AddCharacter(exponent_character_);
91         if (exponent < 0) {
92             result_builder->AddCharacter('-');
93             exponent = -exponent;
94         } else {
95             if ((flags_ & EMIT_POSITIVE_EXPONENT_SIGN) != 0) {
96                 result_builder->AddCharacter('+');
97             }
98         }
99         if (exponent == 0) {
100             result_builder->AddCharacter('0');
101             return;
102         }
103         ASSERT(exponent < 1e4);
104         const int kMaxExponentLength = 5;
105         char buffer[kMaxExponentLength + 1];
106         int first_char_pos = kMaxExponentLength;
107         buffer[first_char_pos] = '\0';
108         while (exponent > 0) {
109             buffer[--first_char_pos] = '0' + (exponent % 10);
110             exponent /= 10;
111         }
112         result_builder->AddSubstring(&buffer[first_char_pos],
113                                      kMaxExponentLength - first_char_pos);
114     }
115 
116 
CreateDecimalRepresentation(const char * decimal_digits,int length,int decimal_point,int digits_after_point,StringBuilder * result_builder) const117     void DoubleToStringConverter::CreateDecimalRepresentation(
118                                                               const char* decimal_digits,
119                                                               int length,
120                                                               int decimal_point,
121                                                               int digits_after_point,
122                                                               StringBuilder* result_builder) const {
123         // Create a representation that is padded with zeros if needed.
124         if (decimal_point <= 0) {
125             // "0.00000decimal_rep".
126             result_builder->AddCharacter('0');
127             if (digits_after_point > 0) {
128                 result_builder->AddCharacter('.');
129                 result_builder->AddPadding('0', -decimal_point);
130                 ASSERT(length <= digits_after_point - (-decimal_point));
131                 result_builder->AddSubstring(decimal_digits, length);
132                 int remaining_digits = digits_after_point - (-decimal_point) - length;
133                 result_builder->AddPadding('0', remaining_digits);
134             }
135         } else if (decimal_point >= length) {
136             // "decimal_rep0000.00000" or "decimal_rep.0000"
137             result_builder->AddSubstring(decimal_digits, length);
138             result_builder->AddPadding('0', decimal_point - length);
139             if (digits_after_point > 0) {
140                 result_builder->AddCharacter('.');
141                 result_builder->AddPadding('0', digits_after_point);
142             }
143         } else {
144             // "decima.l_rep000"
145             ASSERT(digits_after_point > 0);
146             result_builder->AddSubstring(decimal_digits, decimal_point);
147             result_builder->AddCharacter('.');
148             ASSERT(length - decimal_point <= digits_after_point);
149             result_builder->AddSubstring(&decimal_digits[decimal_point],
150                                          length - decimal_point);
151             int remaining_digits = digits_after_point - (length - decimal_point);
152             result_builder->AddPadding('0', remaining_digits);
153         }
154         if (digits_after_point == 0) {
155             if ((flags_ & EMIT_TRAILING_DECIMAL_POINT) != 0) {
156                 result_builder->AddCharacter('.');
157             }
158             if ((flags_ & EMIT_TRAILING_ZERO_AFTER_POINT) != 0) {
159                 result_builder->AddCharacter('0');
160             }
161         }
162     }
163 
164 
ToShortest(double value,StringBuilder * result_builder) const165     bool DoubleToStringConverter::ToShortest(double value,
166                                              StringBuilder* result_builder) const {
167         if (Double(value).IsSpecial()) {
168             return HandleSpecialValues(value, result_builder);
169         }
170 
171         int decimal_point;
172         bool sign;
173         const int kDecimalRepCapacity = kBase10MaximalLength + 1;
174         char decimal_rep[kDecimalRepCapacity];
175         int decimal_rep_length;
176 
177         DoubleToAscii(value, SHORTEST, 0, decimal_rep, kDecimalRepCapacity,
178                       &sign, &decimal_rep_length, &decimal_point);
179 
180         bool unique_zero = (flags_ & UNIQUE_ZERO) != 0;
181         if (sign && (value != 0.0 || !unique_zero)) {
182             result_builder->AddCharacter('-');
183         }
184 
185         int exponent = decimal_point - 1;
186         if ((decimal_in_shortest_low_ <= exponent) &&
187             (exponent < decimal_in_shortest_high_)) {
188             CreateDecimalRepresentation(decimal_rep, decimal_rep_length,
189                                         decimal_point,
190                                         Max(0, decimal_rep_length - decimal_point),
191                                         result_builder);
192         } else {
193             CreateExponentialRepresentation(decimal_rep, decimal_rep_length, exponent,
194                                             result_builder);
195         }
196         return true;
197     }
198 
199 
ToFixed(double value,int requested_digits,StringBuilder * result_builder) const200     bool DoubleToStringConverter::ToFixed(double value,
201                                           int requested_digits,
202                                           StringBuilder* result_builder) const {
203         ASSERT(kMaxFixedDigitsBeforePoint == 60);
204         const double kFirstNonFixed = 1e60;
205 
206         if (Double(value).IsSpecial()) {
207             return HandleSpecialValues(value, result_builder);
208         }
209 
210         if (requested_digits > kMaxFixedDigitsAfterPoint) return false;
211         if (value >= kFirstNonFixed || value <= -kFirstNonFixed) return false;
212 
213         // Find a sufficiently precise decimal representation of n.
214         int decimal_point;
215         bool sign;
216         // Add space for the '\0' byte.
217         const int kDecimalRepCapacity =
218         kMaxFixedDigitsBeforePoint + kMaxFixedDigitsAfterPoint + 1;
219         char decimal_rep[kDecimalRepCapacity];
220         int decimal_rep_length;
221         DoubleToAscii(value, FIXED, requested_digits,
222                       decimal_rep, kDecimalRepCapacity,
223                       &sign, &decimal_rep_length, &decimal_point);
224 
225         bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);
226         if (sign && (value != 0.0 || !unique_zero)) {
227             result_builder->AddCharacter('-');
228         }
229 
230         CreateDecimalRepresentation(decimal_rep, decimal_rep_length, decimal_point,
231                                     requested_digits, result_builder);
232         return true;
233     }
234 
235 
ToExponential(double value,int requested_digits,StringBuilder * result_builder) const236     bool DoubleToStringConverter::ToExponential(
237                                                 double value,
238                                                 int requested_digits,
239                                                 StringBuilder* result_builder) const {
240         if (Double(value).IsSpecial()) {
241             return HandleSpecialValues(value, result_builder);
242         }
243 
244         if (requested_digits < -1) return false;
245         if (requested_digits > kMaxExponentialDigits) return false;
246 
247         int decimal_point;
248         bool sign;
249         // Add space for digit before the decimal point and the '\0' character.
250         const int kDecimalRepCapacity = kMaxExponentialDigits + 2;
251         ASSERT(kDecimalRepCapacity > kBase10MaximalLength);
252         char decimal_rep[kDecimalRepCapacity];
253         int decimal_rep_length;
254 
255         if (requested_digits == -1) {
256             DoubleToAscii(value, SHORTEST, 0,
257                           decimal_rep, kDecimalRepCapacity,
258                           &sign, &decimal_rep_length, &decimal_point);
259         } else {
260             DoubleToAscii(value, PRECISION, requested_digits + 1,
261                           decimal_rep, kDecimalRepCapacity,
262                           &sign, &decimal_rep_length, &decimal_point);
263             ASSERT(decimal_rep_length <= requested_digits + 1);
264 
265             for (int i = decimal_rep_length; i < requested_digits + 1; ++i) {
266                 decimal_rep[i] = '0';
267             }
268             decimal_rep_length = requested_digits + 1;
269         }
270 
271         bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);
272         if (sign && (value != 0.0 || !unique_zero)) {
273             result_builder->AddCharacter('-');
274         }
275 
276         int exponent = decimal_point - 1;
277         CreateExponentialRepresentation(decimal_rep,
278                                         decimal_rep_length,
279                                         exponent,
280                                         result_builder);
281         return true;
282     }
283 
284 
ToPrecision(double value,int precision,StringBuilder * result_builder) const285     bool DoubleToStringConverter::ToPrecision(double value,
286                                               int precision,
287                                               StringBuilder* result_builder) const {
288         if (Double(value).IsSpecial()) {
289             return HandleSpecialValues(value, result_builder);
290         }
291 
292         if (precision < kMinPrecisionDigits || precision > kMaxPrecisionDigits) {
293             return false;
294         }
295 
296         // Find a sufficiently precise decimal representation of n.
297         int decimal_point;
298         bool sign;
299         // Add one for the terminating null character.
300         const int kDecimalRepCapacity = kMaxPrecisionDigits + 1;
301         char decimal_rep[kDecimalRepCapacity];
302         int decimal_rep_length;
303 
304         DoubleToAscii(value, PRECISION, precision,
305                       decimal_rep, kDecimalRepCapacity,
306                       &sign, &decimal_rep_length, &decimal_point);
307         ASSERT(decimal_rep_length <= precision);
308 
309         bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);
310         if (sign && (value != 0.0 || !unique_zero)) {
311             result_builder->AddCharacter('-');
312         }
313 
314         // The exponent if we print the number as x.xxeyyy. That is with the
315         // decimal point after the first digit.
316         int exponent = decimal_point - 1;
317 
318         int extra_zero = ((flags_ & EMIT_TRAILING_ZERO_AFTER_POINT) != 0) ? 1 : 0;
319         if ((-decimal_point + 1 > max_leading_padding_zeroes_in_precision_mode_) ||
320             (decimal_point - precision + extra_zero >
321              max_trailing_padding_zeroes_in_precision_mode_)) {
322                 // Fill buffer to contain 'precision' digits.
323                 // Usually the buffer is already at the correct length, but 'DoubleToAscii'
324                 // is allowed to return less characters.
325                 for (int i = decimal_rep_length; i < precision; ++i) {
326                     decimal_rep[i] = '0';
327                 }
328 
329                 CreateExponentialRepresentation(decimal_rep,
330                                                 precision,
331                                                 exponent,
332                                                 result_builder);
333             } else {
334                 CreateDecimalRepresentation(decimal_rep, decimal_rep_length, decimal_point,
335                                             Max(0, precision - decimal_point),
336                                             result_builder);
337             }
338         return true;
339     }
340 
341 
DtoaToBignumDtoaMode(DoubleToStringConverter::DtoaMode dtoa_mode)342     static BignumDtoaMode DtoaToBignumDtoaMode(
343                                                DoubleToStringConverter::DtoaMode dtoa_mode) {
344         switch (dtoa_mode) {
345             case DoubleToStringConverter::SHORTEST:  return BIGNUM_DTOA_SHORTEST;
346             case DoubleToStringConverter::FIXED:     return BIGNUM_DTOA_FIXED;
347             case DoubleToStringConverter::PRECISION: return BIGNUM_DTOA_PRECISION;
348             default:
349                 UNREACHABLE();
350                 return BIGNUM_DTOA_SHORTEST;  // To silence compiler.
351         }
352     }
353 
354 
DoubleToAscii(double v,DtoaMode mode,int requested_digits,char * buffer,int buffer_length,bool * sign,int * length,int * point)355     void DoubleToStringConverter::DoubleToAscii(double v,
356                                                 DtoaMode mode,
357                                                 int requested_digits,
358                                                 char* buffer,
359                                                 int buffer_length,
360                                                 bool* sign,
361                                                 int* length,
362                                                 int* point) {
363         Vector<char> vector(buffer, buffer_length);
364         ASSERT(!Double(v).IsSpecial());
365         ASSERT(mode == SHORTEST || requested_digits >= 0);
366 
367         if (Double(v).Sign() < 0) {
368             *sign = true;
369             v = -v;
370         } else {
371             *sign = false;
372         }
373 
374         if (mode == PRECISION && requested_digits == 0) {
375             vector[0] = '\0';
376             *length = 0;
377             return;
378         }
379 
380         if (v == 0) {
381             vector[0] = '0';
382             vector[1] = '\0';
383             *length = 1;
384             *point = 1;
385             return;
386         }
387 
388         bool fast_worked;
389         switch (mode) {
390             case SHORTEST:
391                 fast_worked = FastDtoa(v, FAST_DTOA_SHORTEST, 0, vector, length, point);
392                 break;
393             case FIXED:
394                 fast_worked = FastFixedDtoa(v, requested_digits, vector, length, point);
395                 break;
396             case PRECISION:
397                 fast_worked = FastDtoa(v, FAST_DTOA_PRECISION, requested_digits,
398                                        vector, length, point);
399                 break;
400             default:
401                 UNREACHABLE();
402                 fast_worked = false;
403         }
404         if (fast_worked) return;
405 
406         // If the fast dtoa didn't succeed use the slower bignum version.
407         BignumDtoaMode bignum_mode = DtoaToBignumDtoaMode(mode);
408         BignumDtoa(v, bignum_mode, requested_digits, vector, length, point);
409         vector[*length] = '\0';
410     }
411 
412 
413     // Maximum number of significant digits in decimal representation.
414     // The longest possible double in decimal representation is
415     // (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074
416     // (768 digits). If we parse a number whose first digits are equal to a
417     // mean of 2 adjacent doubles (that could have up to 769 digits) the result
418     // must be rounded to the bigger one unless the tail consists of zeros, so
419     // we don't need to preserve all the digits.
420     const int kMaxSignificantDigits = 772;
421 
422 
SignedZero(bool sign)423     static double SignedZero(bool sign) {
424         return sign ? -0.0 : 0.0;
425     }
426 
427 
StringToDouble(const char * input,size_t length,size_t * processed_characters_count)428     double StringToDoubleConverter::StringToDouble(
429                                                    const char* input,
430                                                    size_t length,
431                                                    size_t* processed_characters_count) {
432         const char* current = input;
433         const char* end = input + length;
434 
435         *processed_characters_count = 0;
436 
437         // To make sure that iterator dereferencing is valid the following
438         // convention is used:
439         // 1. Each '++current' statement is followed by check for equality to 'end'.
440         // 3. If 'current' becomes equal to 'end' the function returns or goes to
441         // 'parsing_done'.
442         // 4. 'current' is not dereferenced after the 'parsing_done' label.
443         // 5. Code before 'parsing_done' may rely on 'current != end'.
444         if (current == end) return 0.0;
445 
446         // The longest form of simplified number is: "-<significant digits>.1eXXX\0".
447         const int kBufferSize = kMaxSignificantDigits + 10;
448         char buffer[kBufferSize];  // NOLINT: size is known at compile time.
449         int buffer_pos = 0;
450 
451         // Exponent will be adjusted if insignificant digits of the integer part
452         // or insignificant leading zeros of the fractional part are dropped.
453         int exponent = 0;
454         int significant_digits = 0;
455         int insignificant_digits = 0;
456         bool nonzero_digit_dropped = false;
457         bool sign = false;
458 
459         if (*current == '+' || *current == '-') {
460             sign = (*current == '-');
461             ++current;
462             if (current == end) return 0.0;
463         }
464 
465         bool leading_zero = false;
466         if (*current == '0') {
467             ++current;
468             if (current == end) {
469                 *processed_characters_count = current - input;
470                 return SignedZero(sign);
471             }
472 
473             leading_zero = true;
474 
475             // Ignore leading zeros in the integer part.
476             while (*current == '0') {
477                 ++current;
478                 if (current == end) {
479                     *processed_characters_count = current - input;
480                     return SignedZero(sign);
481                 }
482             }
483         }
484 
485         // Copy significant digits of the integer part (if any) to the buffer.
486         while (*current >= '0' && *current <= '9') {
487             if (significant_digits < kMaxSignificantDigits) {
488                 ASSERT(buffer_pos < kBufferSize);
489                 buffer[buffer_pos++] = static_cast<char>(*current);
490                 significant_digits++;
491             } else {
492                 insignificant_digits++;  // Move the digit into the exponential part.
493                 nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
494             }
495             ++current;
496             if (current == end) goto parsing_done;
497         }
498 
499         if (*current == '.') {
500             ++current;
501             if (current == end) {
502                 if (significant_digits == 0 && !leading_zero) {
503                     return 0.0;
504                 } else {
505                     goto parsing_done;
506                 }
507             }
508 
509             if (significant_digits == 0) {
510                 // Integer part consists of 0 or is absent. Significant digits start after
511                 // leading zeros (if any).
512                 while (*current == '0') {
513                     ++current;
514                     if (current == end) {
515                         *processed_characters_count = current - input;
516                         return SignedZero(sign);
517                     }
518                     exponent--;  // Move this 0 into the exponent.
519                 }
520             }
521 
522             // There is a fractional part.
523             while (*current >= '0' && *current <= '9') {
524                 if (significant_digits < kMaxSignificantDigits) {
525                     ASSERT(buffer_pos < kBufferSize);
526                     buffer[buffer_pos++] = static_cast<char>(*current);
527                     significant_digits++;
528                     exponent--;
529                 } else {
530                     // Ignore insignificant digits in the fractional part.
531                     nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
532                 }
533                 ++current;
534                 if (current == end) goto parsing_done;
535             }
536         }
537 
538         if (!leading_zero && exponent == 0 && significant_digits == 0) {
539             // If leading_zeros is true then the string contains zeros.
540             // If exponent < 0 then string was [+-]\.0*...
541             // If significant_digits != 0 the string is not equal to 0.
542             // Otherwise there are no digits in the string.
543             return 0.0;
544         }
545 
546         // Parse exponential part.
547         if (*current == 'e' || *current == 'E') {
548             ++current;
549             if (current == end) {
550                 --current;
551                 goto parsing_done;
552             }
553             char sign = 0;
554             if (*current == '+' || *current == '-') {
555                 sign = static_cast<char>(*current);
556                 ++current;
557                 if (current == end) {
558                     current -= 2;
559                     goto parsing_done;
560                 }
561             }
562 
563             if (*current < '0' || *current > '9') {
564                 if (sign)
565                     --current;
566                 --current;
567                 goto parsing_done;
568             }
569 
570             const int max_exponent = INT_MAX / 2;
571             ASSERT(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2);
572             int num = 0;
573             do {
574                 // Check overflow.
575                 int digit = *current - '0';
576                 if (num >= max_exponent / 10
577                     && !(num == max_exponent / 10 && digit <= max_exponent % 10)) {
578                     num = max_exponent;
579                 } else {
580                     num = num * 10 + digit;
581                 }
582                 ++current;
583             } while (current != end && *current >= '0' && *current <= '9');
584 
585             exponent += (sign == '-' ? -num : num);
586         }
587 
588     parsing_done:
589         exponent += insignificant_digits;
590 
591         if (nonzero_digit_dropped) {
592             buffer[buffer_pos++] = '1';
593             exponent--;
594         }
595 
596         ASSERT(buffer_pos < kBufferSize);
597         buffer[buffer_pos] = '\0';
598 
599         double converted = Strtod(Vector<const char>(buffer, buffer_pos), exponent);
600         *processed_characters_count = current - input;
601         return sign? -converted: converted;
602     }
603 
604 }  // namespace double_conversion
605 
606 } // namespace WTF
607