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