1/*
2 * Copyright (C) 2012 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 *     * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include "config.h"
32#include "platform/Decimal.h"
33
34#include "wtf/MathExtras.h"
35#include "wtf/Noncopyable.h"
36#include "wtf/text/StringBuilder.h"
37
38#include <algorithm>
39#include <float.h>
40
41namespace blink {
42
43namespace DecimalPrivate {
44
45static int const ExponentMax = 1023;
46static int const ExponentMin = -1023;
47static int const Precision = 18;
48
49static const uint64_t MaxCoefficient = UINT64_C(0xDE0B6B3A763FFFF); // 999999999999999999 == 18 9's
50
51// This class handles Decimal special values.
52class SpecialValueHandler {
53    WTF_MAKE_NONCOPYABLE(SpecialValueHandler);
54public:
55    enum HandleResult {
56        BothFinite,
57        BothInfinity,
58        EitherNaN,
59        LHSIsInfinity,
60        RHSIsInfinity,
61    };
62
63    SpecialValueHandler(const Decimal& lhs, const Decimal& rhs);
64    HandleResult handle();
65    Decimal value() const;
66
67private:
68    enum Result {
69        ResultIsLHS,
70        ResultIsRHS,
71        ResultIsUnknown,
72    };
73
74    const Decimal& m_lhs;
75    const Decimal& m_rhs;
76    Result m_result;
77};
78
79SpecialValueHandler::SpecialValueHandler(const Decimal& lhs, const Decimal& rhs)
80    : m_lhs(lhs), m_rhs(rhs), m_result(ResultIsUnknown)
81{
82}
83
84SpecialValueHandler::HandleResult SpecialValueHandler::handle()
85{
86    if (m_lhs.isFinite() && m_rhs.isFinite())
87        return BothFinite;
88
89    const Decimal::EncodedData::FormatClass lhsClass = m_lhs.value().formatClass();
90    const Decimal::EncodedData::FormatClass rhsClass = m_rhs.value().formatClass();
91    if (lhsClass == Decimal::EncodedData::ClassNaN) {
92        m_result = ResultIsLHS;
93        return EitherNaN;
94    }
95
96    if (rhsClass == Decimal::EncodedData::ClassNaN) {
97        m_result = ResultIsRHS;
98        return EitherNaN;
99    }
100
101    if (lhsClass == Decimal::EncodedData::ClassInfinity)
102        return rhsClass == Decimal::EncodedData::ClassInfinity ? BothInfinity : LHSIsInfinity;
103
104    if (rhsClass == Decimal::EncodedData::ClassInfinity)
105        return RHSIsInfinity;
106
107    ASSERT_NOT_REACHED();
108    return BothFinite;
109}
110
111Decimal SpecialValueHandler::value() const
112{
113    switch (m_result) {
114    case ResultIsLHS:
115        return m_lhs;
116    case ResultIsRHS:
117        return m_rhs;
118    case ResultIsUnknown:
119    default:
120        ASSERT_NOT_REACHED();
121        return m_lhs;
122    }
123}
124
125// This class is used for 128 bit unsigned integer arithmetic.
126class UInt128 {
127public:
128    UInt128(uint64_t low, uint64_t high)
129        : m_high(high), m_low(low)
130    {
131    }
132
133    UInt128& operator/=(uint32_t);
134
135    uint64_t high() const { return m_high; }
136    uint64_t low() const { return m_low; }
137
138    static UInt128 multiply(uint64_t u, uint64_t v) { return UInt128(u * v, multiplyHigh(u, v)); }
139
140private:
141    static uint32_t highUInt32(uint64_t x) { return static_cast<uint32_t>(x >> 32); }
142    static uint32_t lowUInt32(uint64_t x) { return static_cast<uint32_t>(x & ((static_cast<uint64_t>(1) << 32) - 1)); }
143    static uint64_t makeUInt64(uint32_t low, uint32_t high) { return low | (static_cast<uint64_t>(high) << 32); }
144
145    static uint64_t multiplyHigh(uint64_t, uint64_t);
146
147    uint64_t m_high;
148    uint64_t m_low;
149};
150
151UInt128& UInt128::operator/=(const uint32_t divisor)
152{
153    ASSERT(divisor);
154
155    if (!m_high) {
156        m_low /= divisor;
157        return *this;
158    }
159
160    uint32_t dividend[4];
161    dividend[0] = lowUInt32(m_low);
162    dividend[1] = highUInt32(m_low);
163    dividend[2] = lowUInt32(m_high);
164    dividend[3] = highUInt32(m_high);
165
166    uint32_t quotient[4];
167    uint32_t remainder = 0;
168    for (int i = 3; i >= 0; --i) {
169        const uint64_t work = makeUInt64(dividend[i], remainder);
170        remainder = static_cast<uint32_t>(work % divisor);
171        quotient[i] = static_cast<uint32_t>(work / divisor);
172    }
173    m_low = makeUInt64(quotient[0], quotient[1]);
174    m_high = makeUInt64(quotient[2], quotient[3]);
175    return *this;
176}
177
178// Returns high 64bit of 128bit product.
179uint64_t UInt128::multiplyHigh(uint64_t u, uint64_t v)
180{
181    const uint64_t uLow = lowUInt32(u);
182    const uint64_t uHigh = highUInt32(u);
183    const uint64_t vLow = lowUInt32(v);
184    const uint64_t vHigh = highUInt32(v);
185    const uint64_t partialProduct = uHigh * vLow + highUInt32(uLow * vLow);
186    return uHigh * vHigh + highUInt32(partialProduct) + highUInt32(uLow * vHigh + lowUInt32(partialProduct));
187}
188
189static int countDigits(uint64_t x)
190{
191    int numberOfDigits = 0;
192    for (uint64_t powerOfTen = 1; x >= powerOfTen; powerOfTen *= 10) {
193        ++numberOfDigits;
194        if (powerOfTen >= std::numeric_limits<uint64_t>::max() / 10)
195            break;
196    }
197    return numberOfDigits;
198}
199
200static uint64_t scaleDown(uint64_t x, int n)
201{
202    ASSERT(n >= 0);
203    while (n > 0 && x) {
204        x /= 10;
205        --n;
206    }
207    return x;
208}
209
210static uint64_t scaleUp(uint64_t x, int n)
211{
212    ASSERT(n >= 0);
213    ASSERT(n < Precision);
214
215    uint64_t y = 1;
216    uint64_t z = 10;
217    for (;;) {
218        if (n & 1)
219            y = y * z;
220
221        n >>= 1;
222        if (!n)
223            return x * y;
224
225        z = z * z;
226    }
227}
228
229} // namespace DecimalPrivate
230
231using namespace DecimalPrivate;
232
233Decimal::EncodedData::EncodedData(Sign sign, FormatClass formatClass)
234    : m_coefficient(0)
235    , m_exponent(0)
236    , m_formatClass(formatClass)
237    , m_sign(sign)
238{
239}
240
241Decimal::EncodedData::EncodedData(Sign sign, int exponent, uint64_t coefficient)
242    : m_formatClass(coefficient ? ClassNormal : ClassZero)
243    , m_sign(sign)
244{
245    if (exponent >= ExponentMin && exponent <= ExponentMax) {
246        while (coefficient > MaxCoefficient) {
247            coefficient /= 10;
248            ++exponent;
249        }
250    }
251
252    if (exponent > ExponentMax) {
253        m_coefficient = 0;
254        m_exponent = 0;
255        m_formatClass = ClassInfinity;
256        return;
257    }
258
259    if (exponent < ExponentMin) {
260        m_coefficient = 0;
261        m_exponent = 0;
262        m_formatClass = ClassZero;
263        return;
264    }
265
266    m_coefficient = coefficient;
267    m_exponent = static_cast<int16_t>(exponent);
268}
269
270bool Decimal::EncodedData::operator==(const EncodedData& another) const
271{
272    return m_sign == another.m_sign
273        && m_formatClass == another.m_formatClass
274        && m_exponent == another.m_exponent
275        && m_coefficient == another.m_coefficient;
276}
277
278Decimal::Decimal(int32_t i32)
279    : m_data(i32 < 0 ? Negative : Positive, 0, i32 < 0 ? static_cast<uint64_t>(-static_cast<int64_t>(i32)) : static_cast<uint64_t>(i32))
280{
281}
282
283Decimal::Decimal(Sign sign, int exponent, uint64_t coefficient)
284    : m_data(sign, exponent, coefficient)
285{
286}
287
288Decimal::Decimal(const EncodedData& data)
289    : m_data(data)
290{
291}
292
293Decimal::Decimal(const Decimal& other)
294    : m_data(other.m_data)
295{
296}
297
298Decimal& Decimal::operator=(const Decimal& other)
299{
300    m_data = other.m_data;
301    return *this;
302}
303
304Decimal& Decimal::operator+=(const Decimal& other)
305{
306    m_data = (*this + other).m_data;
307    return *this;
308}
309
310Decimal& Decimal::operator-=(const Decimal& other)
311{
312    m_data = (*this - other).m_data;
313    return *this;
314}
315
316Decimal& Decimal::operator*=(const Decimal& other)
317{
318    m_data = (*this * other).m_data;
319    return *this;
320}
321
322Decimal& Decimal::operator/=(const Decimal& other)
323{
324    m_data = (*this / other).m_data;
325    return *this;
326}
327
328Decimal Decimal::operator-() const
329{
330    if (isNaN())
331        return *this;
332
333    Decimal result(*this);
334    result.m_data.setSign(invertSign(m_data.sign()));
335    return result;
336}
337
338Decimal Decimal::operator+(const Decimal& rhs) const
339{
340    const Decimal& lhs = *this;
341    const Sign lhsSign = lhs.sign();
342    const Sign rhsSign = rhs.sign();
343
344    SpecialValueHandler handler(lhs, rhs);
345    switch (handler.handle()) {
346    case SpecialValueHandler::BothFinite:
347        break;
348
349    case SpecialValueHandler::BothInfinity:
350        return lhsSign == rhsSign ? lhs : nan();
351
352    case SpecialValueHandler::EitherNaN:
353        return handler.value();
354
355    case SpecialValueHandler::LHSIsInfinity:
356        return lhs;
357
358    case SpecialValueHandler::RHSIsInfinity:
359        return rhs;
360    }
361
362    const AlignedOperands alignedOperands = alignOperands(lhs, rhs);
363
364    const uint64_t result = lhsSign == rhsSign
365        ? alignedOperands.lhsCoefficient + alignedOperands.rhsCoefficient
366        : alignedOperands.lhsCoefficient - alignedOperands.rhsCoefficient;
367
368    if (lhsSign == Negative && rhsSign == Positive && !result)
369        return Decimal(Positive, alignedOperands.exponent, 0);
370
371    return static_cast<int64_t>(result) >= 0
372        ? Decimal(lhsSign, alignedOperands.exponent, result)
373        : Decimal(invertSign(lhsSign), alignedOperands.exponent, -static_cast<int64_t>(result));
374}
375
376Decimal Decimal::operator-(const Decimal& rhs) const
377{
378    const Decimal& lhs = *this;
379    const Sign lhsSign = lhs.sign();
380    const Sign rhsSign = rhs.sign();
381
382    SpecialValueHandler handler(lhs, rhs);
383    switch (handler.handle()) {
384    case SpecialValueHandler::BothFinite:
385        break;
386
387    case SpecialValueHandler::BothInfinity:
388        return lhsSign == rhsSign ? nan() : lhs;
389
390    case SpecialValueHandler::EitherNaN:
391        return handler.value();
392
393    case SpecialValueHandler::LHSIsInfinity:
394        return lhs;
395
396    case SpecialValueHandler::RHSIsInfinity:
397        return infinity(invertSign(rhsSign));
398    }
399
400    const AlignedOperands alignedOperands = alignOperands(lhs, rhs);
401
402    const uint64_t result = lhsSign == rhsSign
403        ? alignedOperands.lhsCoefficient - alignedOperands.rhsCoefficient
404        : alignedOperands.lhsCoefficient + alignedOperands.rhsCoefficient;
405
406    if (lhsSign == Negative && rhsSign == Negative && !result)
407        return Decimal(Positive, alignedOperands.exponent, 0);
408
409    return static_cast<int64_t>(result) >= 0
410        ? Decimal(lhsSign, alignedOperands.exponent, result)
411        : Decimal(invertSign(lhsSign), alignedOperands.exponent, -static_cast<int64_t>(result));
412}
413
414Decimal Decimal::operator*(const Decimal& rhs) const
415{
416    const Decimal& lhs = *this;
417    const Sign lhsSign = lhs.sign();
418    const Sign rhsSign = rhs.sign();
419    const Sign resultSign = lhsSign == rhsSign ? Positive : Negative;
420
421    SpecialValueHandler handler(lhs, rhs);
422    switch (handler.handle()) {
423    case SpecialValueHandler::BothFinite: {
424        const uint64_t lhsCoefficient = lhs.m_data.coefficient();
425        const uint64_t rhsCoefficient = rhs.m_data.coefficient();
426        int resultExponent = lhs.exponent() + rhs.exponent();
427        UInt128 work(UInt128::multiply(lhsCoefficient, rhsCoefficient));
428        while (work.high()) {
429            work /= 10;
430            ++resultExponent;
431        }
432        return Decimal(resultSign, resultExponent, work.low());
433    }
434
435    case SpecialValueHandler::BothInfinity:
436        return infinity(resultSign);
437
438    case SpecialValueHandler::EitherNaN:
439        return handler.value();
440
441    case SpecialValueHandler::LHSIsInfinity:
442        return rhs.isZero() ? nan() : infinity(resultSign);
443
444    case SpecialValueHandler::RHSIsInfinity:
445        return lhs.isZero() ? nan() : infinity(resultSign);
446    }
447
448    ASSERT_NOT_REACHED();
449    return nan();
450}
451
452Decimal Decimal::operator/(const Decimal& rhs) const
453{
454    const Decimal& lhs = *this;
455    const Sign lhsSign = lhs.sign();
456    const Sign rhsSign = rhs.sign();
457    const Sign resultSign = lhsSign == rhsSign ? Positive : Negative;
458
459    SpecialValueHandler handler(lhs, rhs);
460    switch (handler.handle()) {
461    case SpecialValueHandler::BothFinite:
462        break;
463
464    case SpecialValueHandler::BothInfinity:
465        return nan();
466
467    case SpecialValueHandler::EitherNaN:
468        return handler.value();
469
470    case SpecialValueHandler::LHSIsInfinity:
471        return infinity(resultSign);
472
473    case SpecialValueHandler::RHSIsInfinity:
474        return zero(resultSign);
475    }
476
477    ASSERT(lhs.isFinite());
478    ASSERT(rhs.isFinite());
479
480    if (rhs.isZero())
481        return lhs.isZero() ? nan() : infinity(resultSign);
482
483    int resultExponent = lhs.exponent() - rhs.exponent();
484
485    if (lhs.isZero())
486        return Decimal(resultSign, resultExponent, 0);
487
488    uint64_t remainder = lhs.m_data.coefficient();
489    const uint64_t divisor = rhs.m_data.coefficient();
490    uint64_t result = 0;
491    while (result < MaxCoefficient / 100) {
492        while (remainder < divisor) {
493            remainder *= 10;
494            result *= 10;
495            --resultExponent;
496        }
497        result += remainder / divisor;
498        remainder %= divisor;
499        if (!remainder)
500            break;
501    }
502
503    if (remainder > divisor / 2)
504        ++result;
505
506    return Decimal(resultSign, resultExponent, result);
507}
508
509bool Decimal::operator==(const Decimal& rhs) const
510{
511    return m_data == rhs.m_data || compareTo(rhs).isZero();
512}
513
514bool Decimal::operator!=(const Decimal& rhs) const
515{
516    if (m_data == rhs.m_data)
517        return false;
518    const Decimal result = compareTo(rhs);
519    if (result.isNaN())
520        return false;
521    return !result.isZero();
522}
523
524bool Decimal::operator<(const Decimal& rhs) const
525{
526    const Decimal result = compareTo(rhs);
527    if (result.isNaN())
528        return false;
529    return !result.isZero() && result.isNegative();
530}
531
532bool Decimal::operator<=(const Decimal& rhs) const
533{
534    if (m_data == rhs.m_data)
535        return true;
536    const Decimal result = compareTo(rhs);
537    if (result.isNaN())
538        return false;
539    return result.isZero() || result.isNegative();
540}
541
542bool Decimal::operator>(const Decimal& rhs) const
543{
544    const Decimal result = compareTo(rhs);
545    if (result.isNaN())
546        return false;
547    return !result.isZero() && result.isPositive();
548}
549
550bool Decimal::operator>=(const Decimal& rhs) const
551{
552    if (m_data == rhs.m_data)
553        return true;
554    const Decimal result = compareTo(rhs);
555    if (result.isNaN())
556        return false;
557    return result.isZero() || !result.isNegative();
558}
559
560Decimal Decimal::abs() const
561{
562    Decimal result(*this);
563    result.m_data.setSign(Positive);
564    return result;
565}
566
567Decimal::AlignedOperands Decimal::alignOperands(const Decimal& lhs, const Decimal& rhs)
568{
569    ASSERT(lhs.isFinite());
570    ASSERT(rhs.isFinite());
571
572    const int lhsExponent = lhs.exponent();
573    const int rhsExponent = rhs.exponent();
574    int exponent = std::min(lhsExponent, rhsExponent);
575    uint64_t lhsCoefficient = lhs.m_data.coefficient();
576    uint64_t rhsCoefficient = rhs.m_data.coefficient();
577
578    if (lhsExponent > rhsExponent) {
579        const int numberOfLHSDigits = countDigits(lhsCoefficient);
580        if (numberOfLHSDigits) {
581            const int lhsShiftAmount = lhsExponent - rhsExponent;
582            const int overflow = numberOfLHSDigits + lhsShiftAmount - Precision;
583            if (overflow <= 0) {
584                lhsCoefficient = scaleUp(lhsCoefficient, lhsShiftAmount);
585            } else {
586                lhsCoefficient = scaleUp(lhsCoefficient, lhsShiftAmount - overflow);
587                rhsCoefficient = scaleDown(rhsCoefficient, overflow);
588                exponent += overflow;
589            }
590        }
591
592    } else if (lhsExponent < rhsExponent) {
593        const int numberOfRHSDigits = countDigits(rhsCoefficient);
594        if (numberOfRHSDigits) {
595            const int rhsShiftAmount = rhsExponent - lhsExponent;
596            const int overflow = numberOfRHSDigits + rhsShiftAmount - Precision;
597            if (overflow <= 0) {
598                rhsCoefficient = scaleUp(rhsCoefficient, rhsShiftAmount);
599            } else {
600                rhsCoefficient = scaleUp(rhsCoefficient, rhsShiftAmount - overflow);
601                lhsCoefficient = scaleDown(lhsCoefficient, overflow);
602                exponent += overflow;
603            }
604        }
605    }
606
607    AlignedOperands alignedOperands;
608    alignedOperands.exponent = exponent;
609    alignedOperands.lhsCoefficient = lhsCoefficient;
610    alignedOperands.rhsCoefficient = rhsCoefficient;
611    return alignedOperands;
612}
613
614static bool isMultiplePowersOfTen(uint64_t coefficient, int n)
615{
616    return !coefficient || !(coefficient % scaleUp(1, n));
617}
618
619// Round toward positive infinity.
620// Note: Mac ports defines ceil(x) as wtf_ceil(x), so we can't use name "ceil" here.
621Decimal Decimal::ceiling() const
622{
623    if (isSpecial())
624        return *this;
625
626    if (exponent() >= 0)
627        return *this;
628
629    uint64_t result = m_data.coefficient();
630    const int numberOfDigits = countDigits(result);
631    const int numberOfDropDigits = -exponent();
632    if (numberOfDigits < numberOfDropDigits)
633        return isPositive() ? Decimal(1) : zero(Positive);
634
635    result = scaleDown(result, numberOfDropDigits);
636    if (isPositive() && !isMultiplePowersOfTen(m_data.coefficient(), numberOfDropDigits))
637        ++result;
638    return Decimal(sign(), 0, result);
639}
640
641Decimal Decimal::compareTo(const Decimal& rhs) const
642{
643    const Decimal result(*this - rhs);
644    switch (result.m_data.formatClass()) {
645    case EncodedData::ClassInfinity:
646        return result.isNegative() ? Decimal(-1) : Decimal(1);
647
648    case EncodedData::ClassNaN:
649    case EncodedData::ClassNormal:
650        return result;
651
652    case EncodedData::ClassZero:
653        return zero(Positive);
654
655    default:
656        ASSERT_NOT_REACHED();
657        return nan();
658    }
659}
660
661// Round toward negative infinity.
662Decimal Decimal::floor() const
663{
664    if (isSpecial())
665        return *this;
666
667    if (exponent() >= 0)
668        return *this;
669
670    uint64_t result = m_data.coefficient();
671    const int numberOfDigits = countDigits(result);
672    const int numberOfDropDigits = -exponent();
673    if (numberOfDigits < numberOfDropDigits)
674        return isPositive() ? zero(Positive) : Decimal(-1);
675
676    result = scaleDown(result, numberOfDropDigits);
677    if (isNegative() && !isMultiplePowersOfTen(m_data.coefficient(), numberOfDropDigits))
678        ++result;
679    return Decimal(sign(), 0, result);
680}
681
682Decimal Decimal::fromDouble(double doubleValue)
683{
684    if (std::isfinite(doubleValue))
685        return fromString(String::numberToStringECMAScript(doubleValue));
686
687    if (std::isinf(doubleValue))
688        return infinity(doubleValue < 0 ? Negative : Positive);
689
690    return nan();
691}
692
693Decimal Decimal::fromString(const String& str)
694{
695    int exponent = 0;
696    Sign exponentSign = Positive;
697    int numberOfDigits = 0;
698    int numberOfDigitsAfterDot = 0;
699    int numberOfExtraDigits = 0;
700    Sign sign = Positive;
701
702    enum {
703        StateDigit,
704        StateDot,
705        StateDotDigit,
706        StateE,
707        StateEDigit,
708        StateESign,
709        StateSign,
710        StateStart,
711        StateZero,
712    } state = StateStart;
713
714#define HandleCharAndBreak(expected, nextState) \
715    if (ch == expected) { \
716        state = nextState; \
717        break; \
718    }
719
720#define HandleTwoCharsAndBreak(expected1, expected2, nextState) \
721    if (ch == expected1 || ch == expected2) { \
722        state = nextState; \
723        break; \
724    }
725
726    uint64_t accumulator = 0;
727    for (unsigned index = 0; index < str.length(); ++index) {
728        const int ch = str[index];
729        switch (state) {
730        case StateDigit:
731            if (ch >= '0' && ch <= '9') {
732                if (numberOfDigits < Precision) {
733                    ++numberOfDigits;
734                    accumulator *= 10;
735                    accumulator += ch - '0';
736                } else {
737                    ++numberOfExtraDigits;
738                }
739                break;
740            }
741
742            HandleCharAndBreak('.', StateDot);
743            HandleTwoCharsAndBreak('E', 'e', StateE);
744            return nan();
745
746        case StateDot:
747        case StateDotDigit:
748            if (ch >= '0' && ch <= '9') {
749                if (numberOfDigits < Precision) {
750                    ++numberOfDigits;
751                    ++numberOfDigitsAfterDot;
752                    accumulator *= 10;
753                    accumulator += ch - '0';
754                }
755                state = StateDotDigit;
756                break;
757            }
758
759            HandleTwoCharsAndBreak('E', 'e', StateE);
760            return nan();
761
762        case StateE:
763            if (ch == '+') {
764                exponentSign = Positive;
765                state = StateESign;
766                break;
767            }
768
769            if (ch == '-') {
770                exponentSign = Negative;
771                state = StateESign;
772                break;
773            }
774
775            if (ch >= '0' && ch <= '9') {
776                exponent = ch - '0';
777                state = StateEDigit;
778                break;
779            }
780
781            return nan();
782
783        case StateEDigit:
784            if (ch >= '0' && ch <= '9') {
785                exponent *= 10;
786                exponent += ch - '0';
787                if (exponent > ExponentMax + Precision) {
788                    if (accumulator)
789                        return exponentSign == Negative ? zero(Positive) : infinity(sign);
790                    return zero(sign);
791                }
792                state = StateEDigit;
793                break;
794            }
795
796            return nan();
797
798        case StateESign:
799            if (ch >= '0' && ch <= '9') {
800                exponent = ch - '0';
801                state = StateEDigit;
802                break;
803            }
804
805            return nan();
806
807        case StateSign:
808            if (ch >= '1' && ch <= '9') {
809                accumulator = ch - '0';
810                numberOfDigits = 1;
811                state = StateDigit;
812                break;
813            }
814
815            HandleCharAndBreak('0', StateZero);
816            return nan();
817
818        case StateStart:
819            if (ch >= '1' && ch <= '9') {
820                accumulator = ch - '0';
821                numberOfDigits = 1;
822                state = StateDigit;
823                break;
824            }
825
826            if (ch == '-') {
827                sign = Negative;
828                state = StateSign;
829                break;
830            }
831
832            if (ch == '+') {
833                sign = Positive;
834                state = StateSign;
835                break;
836            }
837
838            HandleCharAndBreak('0', StateZero);
839            HandleCharAndBreak('.', StateDot);
840            return nan();
841
842        case StateZero:
843            if (ch == '0')
844                break;
845
846            if (ch >= '1' && ch <= '9') {
847                accumulator = ch - '0';
848                numberOfDigits = 1;
849                state = StateDigit;
850                break;
851            }
852
853            HandleCharAndBreak('.', StateDot);
854            HandleTwoCharsAndBreak('E', 'e', StateE);
855            return nan();
856
857        default:
858            ASSERT_NOT_REACHED();
859            return nan();
860        }
861    }
862
863    if (state == StateZero)
864        return zero(sign);
865
866    if (state == StateDigit || state == StateEDigit || state == StateDotDigit) {
867        int resultExponent = exponent * (exponentSign == Negative ? -1 : 1) - numberOfDigitsAfterDot + numberOfExtraDigits;
868        if (resultExponent < ExponentMin)
869            return zero(Positive);
870
871        const int overflow = resultExponent - ExponentMax + 1;
872        if (overflow > 0) {
873            if (overflow + numberOfDigits - numberOfDigitsAfterDot > Precision)
874                return infinity(sign);
875            accumulator = scaleUp(accumulator, overflow);
876            resultExponent -= overflow;
877        }
878
879        return Decimal(sign, resultExponent, accumulator);
880    }
881
882    return nan();
883}
884
885Decimal Decimal::infinity(const Sign sign)
886{
887    return Decimal(EncodedData(sign, EncodedData::ClassInfinity));
888}
889
890Decimal Decimal::nan()
891{
892    return Decimal(EncodedData(Positive, EncodedData::ClassNaN));
893}
894
895Decimal Decimal::remainder(const Decimal& rhs) const
896{
897    const Decimal quotient = *this / rhs;
898    return quotient.isSpecial() ? quotient : *this - (quotient.isNegative() ? quotient.ceiling() : quotient.floor()) * rhs;
899}
900
901Decimal Decimal::round() const
902{
903    if (isSpecial())
904        return *this;
905
906    if (exponent() >= 0)
907        return *this;
908
909    uint64_t result = m_data.coefficient();
910    const int numberOfDigits = countDigits(result);
911    const int numberOfDropDigits = -exponent();
912    if (numberOfDigits < numberOfDropDigits)
913        return zero(Positive);
914
915    result = scaleDown(result, numberOfDropDigits - 1);
916    if (result % 10 >= 5)
917        result += 10;
918    result /= 10;
919    return Decimal(sign(), 0, result);
920}
921
922double Decimal::toDouble() const
923{
924    if (isFinite()) {
925        bool valid;
926        const double doubleValue = toString().toDouble(&valid);
927        return valid ? doubleValue : std::numeric_limits<double>::quiet_NaN();
928    }
929
930    if (isInfinity())
931        return isNegative() ? -std::numeric_limits<double>::infinity() : std::numeric_limits<double>::infinity();
932
933    return std::numeric_limits<double>::quiet_NaN();
934}
935
936String Decimal::toString() const
937{
938    switch (m_data.formatClass()) {
939    case EncodedData::ClassInfinity:
940        return sign() ? "-Infinity" : "Infinity";
941
942    case EncodedData::ClassNaN:
943        return "NaN";
944
945    case EncodedData::ClassNormal:
946    case EncodedData::ClassZero:
947        break;
948
949    default:
950        ASSERT_NOT_REACHED();
951        return "";
952    }
953
954    StringBuilder builder;
955    if (sign())
956        builder.append('-');
957
958    int originalExponent = exponent();
959    uint64_t coefficient = m_data.coefficient();
960
961    if (originalExponent < 0) {
962        const int maxDigits = DBL_DIG;
963        uint64_t lastDigit = 0;
964        while (countDigits(coefficient) > maxDigits) {
965            lastDigit = coefficient % 10;
966            coefficient /= 10;
967            ++originalExponent;
968        }
969
970        if (lastDigit >= 5)
971            ++coefficient;
972
973        while (originalExponent < 0 && coefficient && !(coefficient % 10)) {
974            coefficient /= 10;
975            ++originalExponent;
976        }
977    }
978
979    const String digits = String::number(coefficient);
980    int coefficientLength = static_cast<int>(digits.length());
981    const int adjustedExponent = originalExponent + coefficientLength - 1;
982    if (originalExponent <= 0 && adjustedExponent >= -6) {
983        if (!originalExponent) {
984            builder.append(digits);
985            return builder.toString();
986        }
987
988        if (adjustedExponent >= 0) {
989            for (int i = 0; i < coefficientLength; ++i) {
990                builder.append(digits[i]);
991                if (i == adjustedExponent)
992                    builder.append('.');
993            }
994            return builder.toString();
995        }
996
997        builder.appendLiteral("0.");
998        for (int i = adjustedExponent + 1; i < 0; ++i)
999            builder.append('0');
1000
1001        builder.append(digits);
1002
1003    } else {
1004        builder.append(digits[0]);
1005        while (coefficientLength >= 2 && digits[coefficientLength - 1] == '0')
1006            --coefficientLength;
1007        if (coefficientLength >= 2) {
1008            builder.append('.');
1009            for (int i = 1; i < coefficientLength; ++i)
1010                builder.append(digits[i]);
1011        }
1012
1013        if (adjustedExponent) {
1014            builder.append(adjustedExponent < 0 ? "e" : "e+");
1015            builder.appendNumber(adjustedExponent);
1016        }
1017    }
1018    return builder.toString();
1019}
1020
1021Decimal Decimal::zero(Sign sign)
1022{
1023    return Decimal(EncodedData(sign, EncodedData::ClassZero));
1024}
1025
1026} // namespace blink
1027