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 == 21);
209 const double kFirstNonFixed = 1e21;
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 if (decimal_rep_length < requested_digits + 1) {
271 for (int i = decimal_rep_length; i < requested_digits + 1; ++i)
272 decimal_rep[i] = '0';
273 decimal_rep_length = requested_digits + 1;
274 decimal_rep[decimal_rep_length] = '\0';
275 }
276 }
277
278 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);
279 if (sign && (value != 0.0 || !unique_zero)) {
280 result_builder->AddCharacter('-');
281 }
282
283 int exponent = decimal_point - 1;
284 CreateExponentialRepresentation(decimal_rep,
285 decimal_rep_length,
286 exponent,
287 result_builder);
288 return true;
289}
290
291
292bool DoubleToStringConverter::ToPrecision(double value,
293 int precision,
294 StringBuilder* result_builder) const {
295 if (Double(value).IsSpecial()) {
296 return HandleSpecialValues(value, result_builder);
297 }
298
299 if (precision < kMinPrecisionDigits || precision > kMaxPrecisionDigits) {
300 return false;
301 }
302
303 // Find a sufficiently precise decimal representation of n.
304 int decimal_point;
305 bool sign;
306 // Add one for the terminating null character.
307 const int kDecimalRepCapacity = kMaxPrecisionDigits + 1;
308 char decimal_rep[kDecimalRepCapacity];
309 int decimal_rep_length;
310
311 DoubleToAscii(value, PRECISION, precision,
312 decimal_rep, kDecimalRepCapacity,
313 &sign, &decimal_rep_length, &decimal_point);
314 ASSERT(decimal_rep_length <= precision);
315
316 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);
317 if (sign && (value != 0.0 || !unique_zero)) {
318 result_builder->AddCharacter('-');
319 }
320
321 // The exponent if we print the number as x.xxeyyy. That is with the
322 // decimal point after the first digit.
323 int exponent = decimal_point - 1;
324
325 int extra_zero = ((flags_ & EMIT_TRAILING_ZERO_AFTER_POINT) != 0) ? 1 : 0;
326 if ((-decimal_point + 1 > max_leading_padding_zeroes_in_precision_mode_) ||
327 (decimal_point - precision + extra_zero >
328 max_trailing_padding_zeroes_in_precision_mode_)) {
329 // Fill buffer to contain 'precision' digits.
330 // Usually the buffer is already at the correct length, but 'DoubleToAscii'
331 // is allowed to return less characters.
332 for (int i = decimal_rep_length; i < precision; ++i) {
333 decimal_rep[i] = '0';
334 }
335
336 CreateExponentialRepresentation(decimal_rep,
337 precision,
338 exponent,
339 result_builder);
340 } else {
341 CreateDecimalRepresentation(decimal_rep, decimal_rep_length, decimal_point,
342 Max(0, precision - decimal_point),
343 result_builder);
344 }
345 return true;
346}
347
348
349static BignumDtoaMode DtoaToBignumDtoaMode(
350 DoubleToStringConverter::DtoaMode dtoa_mode) {
351 switch (dtoa_mode) {
352 case DoubleToStringConverter::SHORTEST: return BIGNUM_DTOA_SHORTEST;
353 case DoubleToStringConverter::SHORTEST_SINGLE:
354 return BIGNUM_DTOA_SHORTEST_SINGLE;
355 case DoubleToStringConverter::FIXED: return BIGNUM_DTOA_FIXED;
356 case DoubleToStringConverter::PRECISION: return BIGNUM_DTOA_PRECISION;
357 default:
358 UNREACHABLE();
359 }
360}
361
362
363void DoubleToStringConverter::DoubleToAscii(double v,
364 DtoaMode mode,
365 int requested_digits,
366 char* buffer,
367 int buffer_length,
368 bool* sign,
369 int* length,
370 int* point) {
371 BufferReference<char> bufferReference(buffer, buffer_length);
372 ASSERT(!Double(v).IsSpecial());
373 ASSERT(mode == SHORTEST || mode == SHORTEST_SINGLE || requested_digits >= 0);
374
375 if (Double(v).Sign() < 0) {
376 *sign = true;
377 v = -v;
378 } else {
379 *sign = false;
380 }
381
382 if (mode == PRECISION && requested_digits == 0) {
383 bufferReference[0] = '\0';
384 *length = 0;
385 return;
386 }
387
388 if (v == 0) {
389 bufferReference[0] = '0';
390 bufferReference[1] = '\0';
391 *length = 1;
392 *point = 1;
393 return;
394 }
395
396 bool fast_worked;
397 switch (mode) {
398 case SHORTEST:
399 fast_worked = FastDtoa(v, FAST_DTOA_SHORTEST, 0, bufferReference, length, point);
400 break;
401 case SHORTEST_SINGLE:
402 fast_worked = FastDtoa(v, FAST_DTOA_SHORTEST_SINGLE, 0,
403 bufferReference, length, point);
404 break;
405 case FIXED:
406 fast_worked = FastFixedDtoa(v, requested_digits, bufferReference, length, point);
407 break;
408 case PRECISION:
409 fast_worked = FastDtoa(v, FAST_DTOA_PRECISION, requested_digits,
410 bufferReference, length, point);
411 break;
412 default:
413 fast_worked = false;
414 UNREACHABLE();
415 }
416 if (fast_worked) return;
417
418 // If the fast dtoa didn't succeed use the slower bignum version.
419 BignumDtoaMode bignum_mode = DtoaToBignumDtoaMode(mode);
420 BignumDtoa(v, bignum_mode, requested_digits, bufferReference, length, point);
421 bufferReference[*length] = '\0';
422}
423
424// Maximum number of significant digits in decimal representation.
425// The longest possible double in decimal representation is
426// (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074
427// (768 digits). If we parse a number whose first digits are equal to a
428// mean of 2 adjacent doubles (that could have up to 769 digits) the result
429// must be rounded to the bigger one unless the tail consists of zeros, so
430// we don't need to preserve all the digits.
431const int kMaxSignificantDigits = 772;
432
433
434static double SignedZero(bool sign) {
435 return sign ? -0.0 : 0.0;
436}
437
438
439// Returns true, when the iterator is equal to end.
440template<class Iterator>
441static inline bool Advance(Iterator* it, Iterator& end) {
442 ++(*it);
443 return *it == end;
444}
445
446template <typename FloatingPointType>
447inline FloatingPointType StringToFloatingPointType(BufferReference<const char> buffer, int exponent);
448
449template <>
450inline double StringToFloatingPointType<double>(BufferReference<const char> buffer, int exponent) {
451 return Strtod(buffer, exponent);
452}
453
454template <>
455inline float StringToFloatingPointType<float>(BufferReference<const char> buffer, int exponent) {
456 return Strtof(buffer, exponent);
457}
458
459template <typename FloatingPointType, class Iterator>
460static FloatingPointType StringToIeee(
461 Iterator input,
462 size_t length,
463 size_t* processed_characters_count) {
464 static_assert(std::is_floating_point<FloatingPointType>::value, "Only floating point types are allowed.");
465
466 Iterator current = input;
467 Iterator end = input + length;
468
469 *processed_characters_count = 0;
470
471 // To make sure that iterator dereferencing is valid the following
472 // convention is used:
473 // 1. Each '++current' statement is followed by check for equality to 'end'.
474 // 3. If 'current' becomes equal to 'end' the function returns or goes to
475 // 'parsing_done'.
476 // 4. 'current' is not dereferenced after the 'parsing_done' label.
477 // 5. Code before 'parsing_done' may rely on 'current != end'.
478
479 if (current == end) return 0.0;
480
481 // The longest form of simplified number is: "-<significant digits>.1eXXX\0".
482 const int kBufferSize = kMaxSignificantDigits + 10;
483 char buffer[kBufferSize]; // NOLINT: size is known at compile time.
484 int buffer_pos = 0;
485
486 // Exponent will be adjusted if insignificant digits of the integer part
487 // or insignificant leading zeros of the fractional part are dropped.
488 int exponent = 0;
489 int significant_digits = 0;
490 int insignificant_digits = 0;
491 bool nonzero_digit_dropped = false;
492
493 bool sign = false;
494
495 if (*current == '+' || *current == '-') {
496 sign = (*current == '-');
497 ++current;
498 if (current == end) return 0.0;
499 }
500
501 bool leading_zero = false;
502 if (*current == '0') {
503 if (Advance(&current, end)) {
504 *processed_characters_count = static_cast<size_t>(current - input);
505 return SignedZero(sign);
506 }
507
508 leading_zero = true;
509
510 // Ignore leading zeros in the integer part.
511 while (*current == '0') {
512 if (Advance(&current, end)) {
513 *processed_characters_count = static_cast<size_t>(current - input);
514 return SignedZero(sign);
515 }
516 }
517 }
518
519 // Copy significant digits of the integer part (if any) to the buffer.
520 while (isASCIIDigit(*current)) {
521 if (significant_digits < kMaxSignificantDigits) {
522 ASSERT(buffer_pos < kBufferSize);
523 buffer[buffer_pos++] = static_cast<char>(*current);
524 significant_digits++;
525 } else {
526 insignificant_digits++; // Move the digit into the exponential part.
527 nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
528 }
529 if (Advance(&current, end)) goto parsing_done;
530 }
531
532 if (*current == '.') {
533 if (Advance(&current, end)) {
534 if (significant_digits == 0 && !leading_zero) {
535 return 0.0;
536 } else {
537 goto parsing_done;
538 }
539 }
540
541 if (significant_digits == 0) {
542 // Integer part consists of 0 or is absent. Significant digits start after
543 // leading zeros (if any).
544 while (*current == '0') {
545 if (Advance(&current, end)) {
546 *processed_characters_count = static_cast<size_t>(current - input);
547 return SignedZero(sign);
548 }
549 exponent--; // Move this 0 into the exponent.
550 }
551 }
552
553 // There is a fractional part.
554 // We don't emit a '.', but adjust the exponent instead.
555 while (isASCIIDigit(*current)) {
556 if (significant_digits < kMaxSignificantDigits) {
557 ASSERT(buffer_pos < kBufferSize);
558 buffer[buffer_pos++] = static_cast<char>(*current);
559 significant_digits++;
560 exponent--;
561 } else {
562 // Ignore insignificant digits in the fractional part.
563 nonzero_digit_dropped = nonzero_digit_dropped || *current != '0';
564 }
565 if (Advance(&current, end)) goto parsing_done;
566 }
567 }
568
569 if (!leading_zero && exponent == 0 && significant_digits == 0) {
570 // If leading_zeros is true then the string contains zeros.
571 // If exponent < 0 then string was [+-]\.0*...
572 // If significant_digits != 0 the string is not equal to 0.
573 // Otherwise there are no digits in the string.
574 return 0.0;
575 }
576
577 // Parse exponential part.
578 if (*current == 'e' || *current == 'E') {
579 ++current;
580 if (current == end) {
581 --current;
582 goto parsing_done;
583 }
584 char exponen_sign = 0;
585 if (*current == '+' || *current == '-') {
586 exponen_sign = static_cast<char>(*current);
587 ++current;
588 if (current == end) {
589 current -= 2;
590 goto parsing_done;
591 }
592 }
593
594 if (*current < '0' || *current > '9') {
595 if (exponen_sign)
596 --current;
597 --current;
598 goto parsing_done;
599 }
600
601 const int max_exponent = INT_MAX / 2;
602 ASSERT(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2);
603 int num = 0;
604 do {
605 // Check overflow.
606 int digit = *current - '0';
607 if (num >= max_exponent / 10
608 && !(num == max_exponent / 10 && digit <= max_exponent % 10)) {
609 num = max_exponent;
610 } else {
611 num = num * 10 + digit;
612 }
613 ++current;
614 } while (current != end && isASCIIDigit(*current));
615
616 exponent += (exponen_sign == '-' ? -num : num);
617 }
618
619 parsing_done:
620 exponent += insignificant_digits;
621
622 if (nonzero_digit_dropped) {
623 buffer[buffer_pos++] = '1';
624 exponent--;
625 }
626
627 ASSERT(buffer_pos < kBufferSize);
628 buffer[buffer_pos] = '\0';
629
630 auto converted = StringToFloatingPointType<FloatingPointType>(BufferReference<const char>(buffer, buffer_pos), exponent);
631 *processed_characters_count = static_cast<size_t>(current - input);
632 return sign? -converted: converted;
633}
634
635double StringToDoubleConverter::StringToDouble(
636 const char* buffer,
637 size_t length,
638 size_t* processed_characters_count) {
639 return StringToIeee<double>(buffer, length, processed_characters_count);
640}
641
642
643double StringToDoubleConverter::StringToDouble(
644 const uc16* buffer,
645 size_t length,
646 size_t* processed_characters_count) {
647 return StringToIeee<double>(buffer, length, processed_characters_count);
648}
649
650
651float StringToDoubleConverter::StringToFloat(
652 const char* buffer,
653 size_t length,
654 size_t* processed_characters_count) {
655 return StringToIeee<float>(buffer, length, processed_characters_count);
656}
657
658
659float StringToDoubleConverter::StringToFloat(
660 const uc16* buffer,
661 size_t length,
662 size_t* processed_characters_count) {
663 return StringToIeee<float>(buffer, length, processed_characters_count);
664}
665
666} // namespace double_conversion
667} // namespace WTF
668