Decimal.cpp   [plain text]

/*
 * Copyright (C) 2012 Google Inc. All rights reserved.
 * Copyright (C) 2013 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "Decimal.h"

#include <algorithm>
#include <float.h>

#include <wtf/Assertions.h>
#include <wtf/MathExtras.h>
#include <wtf/Noncopyable.h>
#include <wtf/text/StringBuilder.h>

namespace WebCore {

namespace DecimalPrivate {

static int const ExponentMax = 1023;
static int const ExponentMin = -1023;
static int const Precision = 18;

static const uint64_t MaxCoefficient = UINT64_C(0x16345785D89FFFF); // 999999999999999999 == 18 9's

// This class handles Decimal special values.
class SpecialValueHandler {
    WTF_MAKE_NONCOPYABLE(SpecialValueHandler);
public:
    enum HandleResult {
        BothFinite,
        BothInfinity,
        EitherNaN,
        LHSIsInfinity,
        RHSIsInfinity,
    };

    SpecialValueHandler(const Decimal& lhs, const Decimal& rhs);
    HandleResult handle();
    Decimal value() const;

private:
    enum Result {
        ResultIsLHS,
        ResultIsRHS,
        ResultIsUnknown,
    };

    const Decimal& m_lhs;
    const Decimal& m_rhs;
    Result m_result;
};

SpecialValueHandler::SpecialValueHandler(const Decimal& lhs, const Decimal& rhs)
    : m_lhs(lhs), m_rhs(rhs), m_result(ResultIsUnknown)
{
}

SpecialValueHandler::HandleResult SpecialValueHandler::handle()
{
    if (m_lhs.isFinite() && m_rhs.isFinite())
        return BothFinite;

    const Decimal::EncodedData::FormatClass lhsClass = m_lhs.value().formatClass();
    const Decimal::EncodedData::FormatClass rhsClass = m_rhs.value().formatClass();
    if (lhsClass == Decimal::EncodedData::ClassNaN) {
        m_result = ResultIsLHS;
        return EitherNaN;
     }

    if (rhsClass == Decimal::EncodedData::ClassNaN) {
        m_result = ResultIsRHS;
        return EitherNaN;
     }

    if (lhsClass == Decimal::EncodedData::ClassInfinity)
        return rhsClass == Decimal::EncodedData::ClassInfinity ? BothInfinity : LHSIsInfinity;

    if (rhsClass == Decimal::EncodedData::ClassInfinity)
        return RHSIsInfinity;

    ASSERT_NOT_REACHED();
    return BothFinite;
}

Decimal SpecialValueHandler::value() const
{
    switch (m_result) {
    case ResultIsLHS:
        return m_lhs;
    case ResultIsRHS:
        return m_rhs;
    case ResultIsUnknown:
    default:
        ASSERT_NOT_REACHED();
        return m_lhs;
    }
}

// This class is used for 128 bit unsigned integer arithmetic.
class UInt128 {
public:
    UInt128(uint64_t low, uint64_t high)
        : m_high(high), m_low(low)
    {
    }

    UInt128& operator/=(uint32_t);

    uint64_t high() const { return m_high; }
    uint64_t low() const { return m_low; }

    static UInt128 multiply(uint64_t u, uint64_t v) { return UInt128(u * v, multiplyHigh(u, v)); }

private:
    static uint32_t highUInt32(uint64_t x) { return static_cast<uint32_t>(x >> 32); }
    static uint32_t lowUInt32(uint64_t x) { return static_cast<uint32_t>(x & ((static_cast<uint64_t>(1) << 32) - 1)); }
    bool isZero() const { return !m_low && !m_high; }
    static uint64_t makeUInt64(uint32_t low, uint32_t high) { return low | (static_cast<uint64_t>(high) << 32); }

    static uint64_t multiplyHigh(uint64_t, uint64_t);

    uint64_t m_high;
    uint64_t m_low;
};

UInt128& UInt128::operator/=(const uint32_t divisor)
{
    ASSERT(divisor);

    if (!m_high) {
        m_low /= divisor;
        return *this;
    }

    uint32_t dividend[4];
    dividend[0] = lowUInt32(m_low);
    dividend[1] = highUInt32(m_low);
    dividend[2] = lowUInt32(m_high);
    dividend[3] = highUInt32(m_high);

    uint32_t quotient[4];
    uint32_t remainder = 0;
    for (int i = 3; i >= 0; --i) {
        const uint64_t work = makeUInt64(dividend[i], remainder);
        remainder = static_cast<uint32_t>(work % divisor);
        quotient[i] = static_cast<uint32_t>(work / divisor);
    }
    m_low = makeUInt64(quotient[0], quotient[1]);
    m_high = makeUInt64(quotient[2], quotient[3]);
    return *this;
}

// Returns high 64bit of 128bit product.
uint64_t UInt128::multiplyHigh(uint64_t u, uint64_t v)
{
    const uint64_t uLow = lowUInt32(u);
    const uint64_t uHigh = highUInt32(u);
    const uint64_t vLow = lowUInt32(v);
    const uint64_t vHigh = highUInt32(v);
    const uint64_t partialProduct = uHigh * vLow + highUInt32(uLow * vLow);
    return uHigh * vHigh + highUInt32(partialProduct) + highUInt32(uLow * vHigh + lowUInt32(partialProduct));
}

static int countDigits(uint64_t x)
{
    int numberOfDigits = 0;
    for (uint64_t powerOfTen = 1; x >= powerOfTen; powerOfTen *= 10) {
        ++numberOfDigits;
        if (powerOfTen >= std::numeric_limits<uint64_t>::max() / 10)
            break;
    }
    return numberOfDigits;
}

static uint64_t scaleDown(uint64_t x, int n)
{
    ASSERT(n >= 0);
    while (n > 0 && x) {
        x /= 10;
        --n;
    }
    return x;
}

static uint64_t scaleUp(uint64_t x, int n)
{
    ASSERT(n >= 0);
    ASSERT(n < Precision);

    uint64_t y = 1;
    uint64_t z = 10;
    for (;;) {
        if (n & 1)
            y = y * z;

        n >>= 1;
        if (!n)
            return x * y;

        z = z * z;
    }
}

} // namespace DecimalPrivate

using namespace DecimalPrivate;

Decimal::EncodedData::EncodedData(Sign sign, FormatClass formatClass)
    : m_coefficient(0)
    , m_exponent(0)
    , m_formatClass(formatClass)
    , m_sign(sign)
{
}

Decimal::EncodedData::EncodedData(Sign sign, int exponent, uint64_t coefficient)
    : m_formatClass(coefficient ? ClassNormal : ClassZero)
    , m_sign(sign)
{
    if (exponent >= ExponentMin && exponent <= ExponentMax) {
        while (coefficient > MaxCoefficient) {
            coefficient /= 10;
            ++exponent;
        }
    }

    if (exponent > ExponentMax) {
        m_coefficient = 0;
        m_exponent = 0;
        m_formatClass = ClassInfinity;
        return;
    }

    if (exponent < ExponentMin) {
        m_coefficient = 0;
        m_exponent = 0;
        m_formatClass = ClassZero;
        return;
    }

    m_coefficient = coefficient;
    m_exponent = static_cast<int16_t>(exponent);
}

bool Decimal::EncodedData::operator==(const EncodedData& another) const
{
    return m_sign == another.m_sign
        && m_formatClass == another.m_formatClass
        && m_exponent == another.m_exponent
        && m_coefficient == another.m_coefficient;
}

Decimal::Decimal(int32_t i32)
    : m_data(i32 < 0 ? Negative : Positive, 0, i32 < 0 ? static_cast<uint64_t>(-static_cast<int64_t>(i32)) : static_cast<uint64_t>(i32))
{
}

Decimal::Decimal(Sign sign, int exponent, uint64_t coefficient)
    : m_data(sign, exponent, coefficient)
{
}

Decimal::Decimal(const EncodedData& data)
    : m_data(data)
{
}

Decimal::Decimal(const Decimal& other)
    : m_data(other.m_data)
{
}

Decimal& Decimal::operator=(const Decimal& other)
{
    m_data = other.m_data;
    return *this;
}

Decimal& Decimal::operator+=(const Decimal& other)
{
    m_data = (*this + other).m_data;
    return *this;
}

Decimal& Decimal::operator-=(const Decimal& other)
{
    m_data = (*this - other).m_data;
    return *this;
}

Decimal& Decimal::operator*=(const Decimal& other)
{
    m_data = (*this * other).m_data;
    return *this;
}

Decimal& Decimal::operator/=(const Decimal& other)
{
    m_data = (*this / other).m_data;
    return *this;
}

Decimal Decimal::operator-() const
{
    if (isNaN())
        return *this;

    Decimal result(*this);
    result.m_data.setSign(invertSign(m_data.sign()));
    return result;
}

Decimal Decimal::operator+(const Decimal& rhs) const
{
    const Decimal& lhs = *this;
    const Sign lhsSign = lhs.sign();
    const Sign rhsSign = rhs.sign();

    SpecialValueHandler handler(lhs, rhs);
    switch (handler.handle()) {
    case SpecialValueHandler::BothFinite:
        break;

    case SpecialValueHandler::BothInfinity:
        return lhsSign == rhsSign ? lhs : nan();

    case SpecialValueHandler::EitherNaN:
        return handler.value();

    case SpecialValueHandler::LHSIsInfinity:
        return lhs;

    case SpecialValueHandler::RHSIsInfinity:
        return rhs;
    }

    const AlignedOperands alignedOperands = alignOperands(lhs, rhs);

    const uint64_t result = lhsSign == rhsSign
        ? alignedOperands.lhsCoefficient + alignedOperands.rhsCoefficient
        : alignedOperands.lhsCoefficient - alignedOperands.rhsCoefficient;

    if (lhsSign == Negative && rhsSign == Positive && !result)
        return Decimal(Positive, alignedOperands.exponent, 0);

    return static_cast<int64_t>(result) >= 0
        ? Decimal(lhsSign, alignedOperands.exponent, result)
        : Decimal(invertSign(lhsSign), alignedOperands.exponent, -static_cast<int64_t>(result));
}

Decimal Decimal::operator-(const Decimal& rhs) const
{
    const Decimal& lhs = *this;
    const Sign lhsSign = lhs.sign();
    const Sign rhsSign = rhs.sign();

    SpecialValueHandler handler(lhs, rhs);
    switch (handler.handle()) {
    case SpecialValueHandler::BothFinite:
        break;

    case SpecialValueHandler::BothInfinity:
        return lhsSign == rhsSign ? nan() : lhs;

    case SpecialValueHandler::EitherNaN:
        return handler.value();

    case SpecialValueHandler::LHSIsInfinity:
        return lhs;

    case SpecialValueHandler::RHSIsInfinity:
        return infinity(invertSign(rhsSign));
    }

    const AlignedOperands alignedOperands = alignOperands(lhs, rhs);

    const uint64_t result = lhsSign == rhsSign
        ? alignedOperands.lhsCoefficient - alignedOperands.rhsCoefficient
        : alignedOperands.lhsCoefficient + alignedOperands.rhsCoefficient;

    if (lhsSign == Negative && rhsSign == Negative && !result)
        return Decimal(Positive, alignedOperands.exponent, 0);

    return static_cast<int64_t>(result) >= 0
        ? Decimal(lhsSign, alignedOperands.exponent, result)
        : Decimal(invertSign(lhsSign), alignedOperands.exponent, -static_cast<int64_t>(result));
}

Decimal Decimal::operator*(const Decimal& rhs) const
{
    const Decimal& lhs = *this;
    const Sign lhsSign = lhs.sign();
    const Sign rhsSign = rhs.sign();
    const Sign resultSign = lhsSign == rhsSign ? Positive : Negative;

    SpecialValueHandler handler(lhs, rhs);
    switch (handler.handle()) {
    case SpecialValueHandler::BothFinite: {
        const uint64_t lhsCoefficient = lhs.m_data.coefficient();
        const uint64_t rhsCoefficient = rhs.m_data.coefficient();
        int resultExponent = lhs.exponent() + rhs.exponent();
        UInt128 work(UInt128::multiply(lhsCoefficient, rhsCoefficient));
        while (work.high()) {
            work /= 10;
            ++resultExponent;
        }
        return Decimal(resultSign, resultExponent, work.low());
    }

    case SpecialValueHandler::BothInfinity:
        return infinity(resultSign);

    case SpecialValueHandler::EitherNaN:
        return handler.value();

    case SpecialValueHandler::LHSIsInfinity:
        return rhs.isZero() ? nan() : infinity(resultSign);

    case SpecialValueHandler::RHSIsInfinity:
        return lhs.isZero() ? nan() : infinity(resultSign);
    }

    ASSERT_NOT_REACHED();
    return nan();
}

Decimal Decimal::operator/(const Decimal& rhs) const
{
    const Decimal& lhs = *this;
    const Sign lhsSign = lhs.sign();
    const Sign rhsSign = rhs.sign();
    const Sign resultSign = lhsSign == rhsSign ? Positive : Negative;

    SpecialValueHandler handler(lhs, rhs);
    switch (handler.handle()) {
    case SpecialValueHandler::BothFinite:
        break;

    case SpecialValueHandler::BothInfinity:
        return nan();

    case SpecialValueHandler::EitherNaN:
        return handler.value();

    case SpecialValueHandler::LHSIsInfinity:
        return infinity(resultSign);

    case SpecialValueHandler::RHSIsInfinity:
        return zero(resultSign);
    }

    ASSERT(lhs.isFinite());
    ASSERT(rhs.isFinite());

    if (rhs.isZero())
        return lhs.isZero() ? nan() : infinity(resultSign);

    int resultExponent = lhs.exponent() - rhs.exponent();

    if (lhs.isZero())
        return Decimal(resultSign, resultExponent, 0);

    uint64_t remainder = lhs.m_data.coefficient();
    const uint64_t divisor = rhs.m_data.coefficient();
    uint64_t result = 0;
    while (result < MaxCoefficient / 100) {
        while (remainder < divisor) {
            remainder *= 10;
            result *= 10;
            --resultExponent;
        }
        result += remainder / divisor;
        remainder %= divisor;
        if (!remainder)
            break;
    }

    if (remainder > divisor / 2)
        ++result;

    return Decimal(resultSign, resultExponent, result);
}

bool Decimal::operator==(const Decimal& rhs) const
{
    return m_data == rhs.m_data || compareTo(rhs).isZero();
}

bool Decimal::operator!=(const Decimal& rhs) const
{
    if (m_data == rhs.m_data)
        return false;
    const Decimal result = compareTo(rhs);
    if (result.isNaN())
        return false;
    return !result.isZero();
}

bool Decimal::operator<(const Decimal& rhs) const
{
    const Decimal result = compareTo(rhs);
    if (result.isNaN())
        return false;
    return !result.isZero() && result.isNegative();
}

bool Decimal::operator<=(const Decimal& rhs) const
{
    if (m_data == rhs.m_data)
        return true;
    const Decimal result = compareTo(rhs);
    if (result.isNaN())
        return false;
    return result.isZero() || result.isNegative();
}

bool Decimal::operator>(const Decimal& rhs) const
{
    const Decimal result = compareTo(rhs);
    if (result.isNaN())
        return false;
    return !result.isZero() && result.isPositive();
}

bool Decimal::operator>=(const Decimal& rhs) const
{
    if (m_data == rhs.m_data)
        return true;
    const Decimal result = compareTo(rhs);
    if (result.isNaN())
        return false;
    return result.isZero() || !result.isNegative();
}

Decimal Decimal::abs() const
{
    Decimal result(*this);
    result.m_data.setSign(Positive);
    return result;
}

Decimal::AlignedOperands Decimal::alignOperands(const Decimal& lhs, const Decimal& rhs)
{
    ASSERT(lhs.isFinite());
    ASSERT(rhs.isFinite());

    const int lhsExponent = lhs.exponent();
    const int rhsExponent = rhs.exponent();
    int exponent = std::min(lhsExponent, rhsExponent);
    uint64_t lhsCoefficient = lhs.m_data.coefficient();
    uint64_t rhsCoefficient = rhs.m_data.coefficient();

    if (lhsExponent > rhsExponent) {
        const int numberOfLHSDigits = countDigits(lhsCoefficient);
        if (numberOfLHSDigits) {
            const int lhsShiftAmount = lhsExponent - rhsExponent;
            const int overflow = numberOfLHSDigits + lhsShiftAmount - Precision;
            if (overflow <= 0)
                lhsCoefficient = scaleUp(lhsCoefficient, lhsShiftAmount);
            else {
                lhsCoefficient = scaleUp(lhsCoefficient, lhsShiftAmount - overflow);
                rhsCoefficient = scaleDown(rhsCoefficient, overflow);
                exponent += overflow;
            }
        }

    } else if (lhsExponent < rhsExponent) {
        const int numberOfRHSDigits = countDigits(rhsCoefficient);
        if (numberOfRHSDigits) {
            const int rhsShiftAmount = rhsExponent - lhsExponent;
            const int overflow = numberOfRHSDigits + rhsShiftAmount - Precision;
            if (overflow <= 0)
                rhsCoefficient = scaleUp(rhsCoefficient, rhsShiftAmount);
            else {
                rhsCoefficient = scaleUp(rhsCoefficient, rhsShiftAmount - overflow);
                lhsCoefficient = scaleDown(lhsCoefficient, overflow);
                exponent += overflow;
            }
        }
    }

    AlignedOperands alignedOperands;
    alignedOperands.exponent = exponent;
    alignedOperands.lhsCoefficient = lhsCoefficient;
    alignedOperands.rhsCoefficient = rhsCoefficient;
    return alignedOperands;
}

// Round toward positive infinity.
// Note: Mac ports defines ceil(x) as wtf_ceil(x), so we can't use name "ceil" here.
Decimal Decimal::ceiling() const
{
    if (isSpecial())
        return *this;

    if (exponent() >= 0)
        return *this;

    uint64_t result = m_data.coefficient();
    const int numberOfDigits = countDigits(result);
    const int numberOfDropDigits = -exponent();
    if (numberOfDigits < numberOfDropDigits)
        return isPositive() ? Decimal(1) : zero(Positive);

    result = scaleDown(result, numberOfDropDigits - 1);
    if (sign() == Positive && result % 10 > 0)
        result += 10;
    result /= 10;
    return Decimal(sign(), 0, result);
}

Decimal Decimal::compareTo(const Decimal& rhs) const
{
    const Decimal result(*this - rhs);
    switch (result.m_data.formatClass()) {
    case EncodedData::ClassInfinity:
        return result.isNegative() ? Decimal(-1) : Decimal(1);

    case EncodedData::ClassNaN:
    case EncodedData::ClassNormal:
        return result;

    case EncodedData::ClassZero:
        return zero(Positive);

    default:
        ASSERT_NOT_REACHED();
        return nan();
    }
}

// Round toward negative infinity.
Decimal Decimal::floor() const
{
    if (isSpecial())
        return *this;

    if (exponent() >= 0)
        return *this;

    uint64_t result = m_data.coefficient();
    const int numberOfDigits = countDigits(result);
    const int numberOfDropDigits = -exponent();
    if (numberOfDigits < numberOfDropDigits)
        return isPositive() ? zero(Positive) : Decimal(-1);

    result = scaleDown(result, numberOfDropDigits - 1);
    if (isNegative() && result % 10 > 0)
        result += 10;
    result /= 10;
    return Decimal(sign(), 0, result);
}

Decimal Decimal::fromDouble(double doubleValue)
{
    if (std::isfinite(doubleValue))
        return fromString(String::numberToStringECMAScript(doubleValue));

    if (std::isinf(doubleValue))
        return infinity(doubleValue < 0 ? Negative : Positive);

    return nan();
}

Decimal Decimal::fromString(const String& str)
{
    int exponent = 0;
    Sign exponentSign = Positive;
    int numberOfDigits = 0;
    int numberOfDigitsAfterDot = 0;
    int numberOfExtraDigits = 0;
    Sign sign = Positive;

    enum {
        StateDigit,
        StateDot,
        StateDotDigit,
        StateE,
        StateEDigit,
        StateESign,
        StateSign,
        StateStart,
        StateZero,
    } state = StateStart;

#define HandleCharAndBreak(expected, nextState) \
    if (ch == expected) { \
        state = nextState; \
        break; \
    }

#define HandleTwoCharsAndBreak(expected1, expected2, nextState) \
    if (ch == expected1 || ch == expected2) { \
        state = nextState; \
        break; \
    }

    uint64_t accumulator = 0;
    for (unsigned index = 0; index < str.length(); ++index) {
        const int ch = str[index];
        switch (state) {
        case StateDigit:
            if (isASCIIDigit(ch)) {
                if (numberOfDigits < Precision) {
                    ++numberOfDigits;
                    accumulator *= 10;
                    accumulator += ch - '0';
                } else
                    ++numberOfExtraDigits;
                break;
            }

            HandleCharAndBreak('.', StateDot);
            HandleTwoCharsAndBreak('E', 'e', StateE);
            return nan();

        case StateDot:
            if (isASCIIDigit(ch)) {
                if (numberOfDigits < Precision) {
                    ++numberOfDigits;
                    ++numberOfDigitsAfterDot;
                    accumulator *= 10;
                    accumulator += ch - '0';
                }
                state = StateDotDigit;
                break;
            }
            // FIXME: <http://webkit.org/b/127667> Decimal::fromString's EBNF documentation does not match implementation
            FALLTHROUGH;

        case StateDotDigit:
            if (isASCIIDigit(ch)) {
                if (numberOfDigits < Precision) {
                    ++numberOfDigits;
                    ++numberOfDigitsAfterDot;
                    accumulator *= 10;
                    accumulator += ch - '0';
                }
                break;
            }

            HandleTwoCharsAndBreak('E', 'e', StateE);
            return nan();

        case StateE:
            if (ch == '+') {
                exponentSign = Positive;
                state = StateESign;
                break;
            }

            if (ch == '-') {
                exponentSign = Negative;
                state = StateESign;
                break;
            }

            if (isASCIIDigit(ch)) {
                exponent = ch - '0';
                state = StateEDigit;
                break;
            }

            return nan();

        case StateEDigit:
            if (isASCIIDigit(ch)) {
                exponent *= 10;
                exponent += ch - '0';
                if (exponent > ExponentMax + Precision) {
                    if (accumulator)
                        return exponentSign == Negative ? zero(Positive) : infinity(sign);
                    return zero(sign);
                }
                state = StateEDigit;
                break;
            }

            return nan();

        case StateESign:
            if (isASCIIDigit(ch)) {
                exponent = ch - '0';
                state = StateEDigit;
                break;
            }

            return nan();

        case StateSign:
            if (ch >= '1' && ch <= '9') {
                accumulator = ch - '0';
                numberOfDigits = 1;
                state = StateDigit;
                break;
            }

            HandleCharAndBreak('0', StateZero);
            HandleCharAndBreak('.', StateDot);
            return nan();

        case StateStart:
            if (ch >= '1' && ch <= '9') {
                accumulator = ch - '0';
                numberOfDigits = 1;
                state = StateDigit;
                break;
            }

            if (ch == '-') {
                sign = Negative;
                state = StateSign;
                break;
            }

            if (ch == '+') {
                sign = Positive;
                state = StateSign;
                break;
            }

            HandleCharAndBreak('0', StateZero);
            HandleCharAndBreak('.', StateDot);
            return nan();

        case StateZero:
            if (ch == '0')
                break;

            if (ch >= '1' && ch <= '9') {
                accumulator = ch - '0';
                numberOfDigits = 1;
                state = StateDigit;
                break;
            }

            HandleCharAndBreak('.', StateDot);
            HandleTwoCharsAndBreak('E', 'e', StateE);
            return nan();

        default:
            ASSERT_NOT_REACHED();
            return nan();
        }
    }

    if (state == StateZero)
        return zero(sign);

    if (state == StateDigit || state == StateDot || state == StateDotDigit || state == StateEDigit) {
        int resultExponent = exponent * (exponentSign == Negative ? -1 : 1) - numberOfDigitsAfterDot + numberOfExtraDigits;
        if (resultExponent < ExponentMin)
            return zero(Positive);

        const int overflow = resultExponent - ExponentMax + 1;
        if (overflow > 0) {
            if (overflow + numberOfDigits - numberOfDigitsAfterDot > Precision)
                return infinity(sign);
            accumulator = scaleUp(accumulator, overflow);
            resultExponent -= overflow;
        }

        return Decimal(sign, resultExponent, accumulator);
    }

    return nan();
}

Decimal Decimal::infinity(const Sign sign)
{
    return Decimal(EncodedData(sign, EncodedData::ClassInfinity));
}

Decimal Decimal::nan()
{
    return Decimal(EncodedData(Positive, EncodedData::ClassNaN));
}

Decimal Decimal::remainder(const Decimal& rhs) const
{
    const Decimal quotient = *this / rhs;
    return quotient.isSpecial() ? quotient : *this - (quotient.isNegative() ? quotient.ceiling() : quotient.floor()) * rhs;
}

Decimal Decimal::round() const
{
    if (isSpecial())
        return *this;

    if (exponent() >= 0)
        return *this;

    uint64_t result = m_data.coefficient();
    const int numberOfDigits = countDigits(result);
    const int numberOfDropDigits = -exponent();
    if (numberOfDigits < numberOfDropDigits)
        return zero(Positive);

    result = scaleDown(result, numberOfDropDigits - 1);
    if (result % 10 >= 5)
        result += 10;
    result /= 10;
    return Decimal(sign(), 0, result);
}

double Decimal::toDouble() const
{
    if (isFinite()) {
        bool valid;
        const double doubleValue = toString().toDouble(&valid);
        return valid ? doubleValue : std::numeric_limits<double>::quiet_NaN();
    }

    if (isInfinity())
        return isNegative() ? -std::numeric_limits<double>::infinity() : std::numeric_limits<double>::infinity();

    return std::numeric_limits<double>::quiet_NaN();
}

String Decimal::toString() const
{
    switch (m_data.formatClass()) {
    case EncodedData::ClassInfinity:
        return sign() ? ASCIILiteral("-Infinity") : ASCIILiteral("Infinity");

    case EncodedData::ClassNaN:
        return ASCIILiteral("NaN");

    case EncodedData::ClassNormal:
    case EncodedData::ClassZero:
        break;

    default:
        ASSERT_NOT_REACHED();
        return emptyString();
    }

    StringBuilder builder;
    if (sign())
        builder.append('-');

    int originalExponent = exponent();
    uint64_t coefficient = m_data.coefficient();

    if (originalExponent < 0) {
        const int maxDigits = DBL_DIG;
        uint64_t lastDigit = 0;
        while (countDigits(coefficient) > maxDigits) {
            lastDigit = coefficient % 10;
            coefficient /= 10;
            ++originalExponent;
        }

        if (lastDigit >= 5)
            ++coefficient;

        while (originalExponent < 0 && coefficient && !(coefficient % 10)) {
            coefficient /= 10;
            ++originalExponent;
        }
    }

    const String digits = String::number(coefficient);
    int coefficientLength = static_cast<int>(digits.length());
    const int adjustedExponent = originalExponent + coefficientLength - 1;
    if (originalExponent <= 0 && adjustedExponent >= -6) {
        if (!originalExponent) {
            builder.append(digits);
            return builder.toString();
        }

        if (adjustedExponent >= 0) {
            for (int i = 0; i < coefficientLength; ++i) {
                builder.append(digits[i]);
                if (i == adjustedExponent)
                    builder.append('.');
            }
            return builder.toString();
        }

        builder.appendLiteral("0.");
        for (int i = adjustedExponent + 1; i < 0; ++i)
            builder.append('0');

        builder.append(digits);

    } else {
        builder.append(digits[0]);
        while (coefficientLength >= 2 && digits[coefficientLength - 1] == '0')
            --coefficientLength;
        if (coefficientLength >= 2) {
            builder.append('.');
            for (int i = 1; i < coefficientLength; ++i)
                builder.append(digits[i]);
        }

        if (adjustedExponent) {
            builder.append(adjustedExponent < 0 ? "e" : "e+");
            builder.appendNumber(adjustedExponent);
        }
    }
    return builder.toString();
}

Decimal Decimal::zero(Sign sign)
{
    return Decimal(EncodedData(sign, EncodedData::ClassZero));
}

} // namespace WebCore