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