michael@0: /*
michael@0:  * Copyright (C) 2012 Google Inc. All rights reserved.
michael@0:  *
michael@0:  * Redistribution and use in source and binary forms, with or without
michael@0:  * modification, are permitted provided that the following conditions are
michael@0:  * met:
michael@0:  *
michael@0:  *     * Redistributions of source code must retain the above copyright
michael@0:  * notice, this list of conditions and the following disclaimer.
michael@0:  *     * Redistributions in binary form must reproduce the above
michael@0:  * copyright notice, this list of conditions and the following disclaimer
michael@0:  * in the documentation and/or other materials provided with the
michael@0:  * distribution.
michael@0:  *     * Neither the name of Google Inc. nor the names of its
michael@0:  * contributors may be used to endorse or promote products derived from
michael@0:  * this software without specific prior written permission.
michael@0:  *
michael@0:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
michael@0:  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
michael@0:  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
michael@0:  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
michael@0:  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
michael@0:  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
michael@0:  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
michael@0:  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
michael@0:  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
michael@0:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
michael@0:  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0:  */
michael@0: 
michael@0: #include "Decimal.h"
michael@0: #include "moz-decimal-utils.h"
michael@0: 
michael@0: #include <algorithm>
michael@0: #include <float.h>
michael@0: 
michael@0: using namespace moz_decimal_utils;
michael@0: 
michael@0: namespace WebCore {
michael@0: 
michael@0: namespace DecimalPrivate {
michael@0: 
michael@0: static int const ExponentMax = 1023;
michael@0: static int const ExponentMin = -1023;
michael@0: static int const Precision = 18;
michael@0: 
michael@0: static const uint64_t MaxCoefficient = UINT64_C(0x16345785D89FFFF); // 999999999999999999 == 18 9's
michael@0: 
michael@0: // This class handles Decimal special values.
michael@0: class SpecialValueHandler {
michael@0:     WTF_MAKE_NONCOPYABLE(SpecialValueHandler);
michael@0: public:
michael@0:     enum HandleResult {
michael@0:         BothFinite,
michael@0:         BothInfinity,
michael@0:         EitherNaN,
michael@0:         LHSIsInfinity,
michael@0:         RHSIsInfinity,
michael@0:     };
michael@0: 
michael@0:     SpecialValueHandler(const Decimal& lhs, const Decimal& rhs);
michael@0:     HandleResult handle();
michael@0:     Decimal value() const;
michael@0: 
michael@0: private:
michael@0:     enum Result {
michael@0:         ResultIsLHS,
michael@0:         ResultIsRHS,
michael@0:         ResultIsUnknown,
michael@0:     };
michael@0: 
michael@0:     const Decimal& m_lhs;
michael@0:     const Decimal& m_rhs;
michael@0:     Result m_result;
michael@0: };
michael@0: 
michael@0: SpecialValueHandler::SpecialValueHandler(const Decimal& lhs, const Decimal& rhs)
michael@0:     : m_lhs(lhs), m_rhs(rhs), m_result(ResultIsUnknown)
michael@0: {
michael@0: }
michael@0: 
michael@0: SpecialValueHandler::HandleResult SpecialValueHandler::handle()
michael@0: {
michael@0:     if (m_lhs.isFinite() && m_rhs.isFinite())
michael@0:         return BothFinite;
michael@0: 
michael@0:     const Decimal::EncodedData::FormatClass lhsClass = m_lhs.value().formatClass();
michael@0:     const Decimal::EncodedData::FormatClass rhsClass = m_rhs.value().formatClass();
michael@0:     if (lhsClass == Decimal::EncodedData::ClassNaN) {
michael@0:         m_result = ResultIsLHS;
michael@0:         return EitherNaN;
michael@0:      }
michael@0: 
michael@0:     if (rhsClass == Decimal::EncodedData::ClassNaN) {
michael@0:         m_result = ResultIsRHS;
michael@0:         return EitherNaN;
michael@0:      }
michael@0: 
michael@0:     if (lhsClass == Decimal::EncodedData::ClassInfinity)
michael@0:         return rhsClass == Decimal::EncodedData::ClassInfinity ? BothInfinity : LHSIsInfinity;
michael@0: 
michael@0:     if (rhsClass == Decimal::EncodedData::ClassInfinity)
michael@0:         return RHSIsInfinity;
michael@0: 
michael@0:     ASSERT_NOT_REACHED();
michael@0:     return BothFinite;
michael@0: }
michael@0: 
michael@0: Decimal SpecialValueHandler::value() const
michael@0: {
michael@0:     switch (m_result) {
michael@0:     case ResultIsLHS:
michael@0:         return m_lhs;
michael@0:     case ResultIsRHS:
michael@0:         return m_rhs;
michael@0:     case ResultIsUnknown:
michael@0:     default:
michael@0:         ASSERT_NOT_REACHED();
michael@0:         return m_lhs;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // This class is used for 128 bit unsigned integer arithmetic.
michael@0: class UInt128 {
michael@0: public:
michael@0:     UInt128(uint64_t low, uint64_t high)
michael@0:         : m_high(high), m_low(low)
michael@0:     {
michael@0:     }
michael@0: 
michael@0:     UInt128& operator/=(uint32_t);
michael@0: 
michael@0:     uint64_t high() const { return m_high; }
michael@0:     uint64_t low() const { return m_low; }
michael@0: 
michael@0:     static UInt128 multiply(uint64_t u, uint64_t v) { return UInt128(u * v, multiplyHigh(u, v)); }
michael@0: 
michael@0: private:
michael@0:     static uint32_t highUInt32(uint64_t x) { return static_cast<uint32_t>(x >> 32); }
michael@0:     static uint32_t lowUInt32(uint64_t x) { return static_cast<uint32_t>(x & ((static_cast<uint64_t>(1) << 32) - 1)); }
michael@0:     bool isZero() const { return !m_low && !m_high; }
michael@0:     static uint64_t makeUInt64(uint32_t low, uint32_t high) { return low | (static_cast<uint64_t>(high) << 32); }
michael@0: 
michael@0:     static uint64_t multiplyHigh(uint64_t, uint64_t);
michael@0: 
michael@0:     uint64_t m_high;
michael@0:     uint64_t m_low;
michael@0: };
michael@0: 
michael@0: UInt128& UInt128::operator/=(const uint32_t divisor)
michael@0: {
michael@0:     ASSERT(divisor);
michael@0: 
michael@0:     if (!m_high) {
michael@0:         m_low /= divisor;
michael@0:         return *this;
michael@0:     }
michael@0: 
michael@0:     uint32_t dividend[4];
michael@0:     dividend[0] = lowUInt32(m_low);
michael@0:     dividend[1] = highUInt32(m_low);
michael@0:     dividend[2] = lowUInt32(m_high);
michael@0:     dividend[3] = highUInt32(m_high);
michael@0: 
michael@0:     uint32_t quotient[4];
michael@0:     uint32_t remainder = 0;
michael@0:     for (int i = 3; i >= 0; --i) {
michael@0:         const uint64_t work = makeUInt64(dividend[i], remainder);
michael@0:         remainder = static_cast<uint32_t>(work % divisor);
michael@0:         quotient[i] = static_cast<uint32_t>(work / divisor);
michael@0:     }
michael@0:     m_low = makeUInt64(quotient[0], quotient[1]);
michael@0:     m_high = makeUInt64(quotient[2], quotient[3]);
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: // Returns high 64bit of 128bit product.
michael@0: uint64_t UInt128::multiplyHigh(uint64_t u, uint64_t v)
michael@0: {
michael@0:     const uint64_t uLow = lowUInt32(u);
michael@0:     const uint64_t uHigh = highUInt32(u);
michael@0:     const uint64_t vLow = lowUInt32(v);
michael@0:     const uint64_t vHigh = highUInt32(v);
michael@0:     const uint64_t partialProduct = uHigh * vLow + highUInt32(uLow * vLow);
michael@0:     return uHigh * vHigh + highUInt32(partialProduct) + highUInt32(uLow * vHigh + lowUInt32(partialProduct));
michael@0: }
michael@0: 
michael@0: static int countDigits(uint64_t x)
michael@0: {
michael@0:     int numberOfDigits = 0;
michael@0:     for (uint64_t powerOfTen = 1; x >= powerOfTen; powerOfTen *= 10) {
michael@0:         ++numberOfDigits;
michael@0:         if (powerOfTen >= std::numeric_limits<uint64_t>::max() / 10)
michael@0:             break;
michael@0:     }
michael@0:     return numberOfDigits;
michael@0: }
michael@0: 
michael@0: static uint64_t scaleDown(uint64_t x, int n)
michael@0: {
michael@0:     ASSERT(n >= 0);
michael@0:     while (n > 0 && x) {
michael@0:         x /= 10;
michael@0:         --n;
michael@0:     }
michael@0:     return x;
michael@0: }
michael@0: 
michael@0: static uint64_t scaleUp(uint64_t x, int n)
michael@0: {
michael@0:     ASSERT(n >= 0);
michael@0:     ASSERT(n < Precision);
michael@0: 
michael@0:     uint64_t y = 1;
michael@0:     uint64_t z = 10;
michael@0:     for (;;) {
michael@0:         if (n & 1)
michael@0:             y = y * z;
michael@0: 
michael@0:         n >>= 1;
michael@0:         if (!n)
michael@0:             return x * y;
michael@0: 
michael@0:         z = z * z;
michael@0:     }
michael@0: }
michael@0: 
michael@0: } // namespace DecimalPrivate
michael@0: 
michael@0: using namespace DecimalPrivate;
michael@0: 
michael@0: Decimal::EncodedData::EncodedData(Sign sign, FormatClass formatClass)
michael@0:     : m_coefficient(0)
michael@0:     , m_exponent(0)
michael@0:     , m_formatClass(formatClass)
michael@0:     , m_sign(sign)
michael@0: {
michael@0: }
michael@0: 
michael@0: Decimal::EncodedData::EncodedData(Sign sign, int exponent, uint64_t coefficient)
michael@0:     : m_formatClass(coefficient ? ClassNormal : ClassZero)
michael@0:     , m_sign(sign)
michael@0: {
michael@0:     if (exponent >= ExponentMin && exponent <= ExponentMax) {
michael@0:         while (coefficient > MaxCoefficient) {
michael@0:             coefficient /= 10;
michael@0:             ++exponent;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (exponent > ExponentMax) {
michael@0:         m_coefficient = 0;
michael@0:         m_exponent = 0;
michael@0:         m_formatClass = ClassInfinity;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if (exponent < ExponentMin) {
michael@0:         m_coefficient = 0;
michael@0:         m_exponent = 0;
michael@0:         m_formatClass = ClassZero;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     m_coefficient = coefficient;
michael@0:     m_exponent = static_cast<int16_t>(exponent);
michael@0: }
michael@0: 
michael@0: bool Decimal::EncodedData::operator==(const EncodedData& another) const
michael@0: {
michael@0:     return m_sign == another.m_sign
michael@0:         && m_formatClass == another.m_formatClass
michael@0:         && m_exponent == another.m_exponent
michael@0:         && m_coefficient == another.m_coefficient;
michael@0: }
michael@0: 
michael@0: Decimal::Decimal(int32_t i32)
michael@0:     : m_data(i32 < 0 ? Negative : Positive, 0, i32 < 0 ? static_cast<uint64_t>(-static_cast<int64_t>(i32)) : static_cast<uint64_t>(i32))
michael@0: {
michael@0: }
michael@0: 
michael@0: Decimal::Decimal(Sign sign, int exponent, uint64_t coefficient)
michael@0:     : m_data(sign, coefficient ? exponent : 0, coefficient)
michael@0: {
michael@0: }
michael@0: 
michael@0: Decimal::Decimal(const EncodedData& data)
michael@0:     : m_data(data)
michael@0: {
michael@0: }
michael@0: 
michael@0: Decimal::Decimal(const Decimal& other)
michael@0:     : m_data(other.m_data)
michael@0: {
michael@0: }
michael@0: 
michael@0: Decimal& Decimal::operator=(const Decimal& other)
michael@0: {
michael@0:     m_data = other.m_data;
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: Decimal& Decimal::operator+=(const Decimal& other)
michael@0: {
michael@0:     m_data = (*this + other).m_data;
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: Decimal& Decimal::operator-=(const Decimal& other)
michael@0: {
michael@0:     m_data = (*this - other).m_data;
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: Decimal& Decimal::operator*=(const Decimal& other)
michael@0: {
michael@0:     m_data = (*this * other).m_data;
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: Decimal& Decimal::operator/=(const Decimal& other)
michael@0: {
michael@0:     m_data = (*this / other).m_data;
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: Decimal Decimal::operator-() const
michael@0: {
michael@0:     if (isNaN())
michael@0:         return *this;
michael@0: 
michael@0:     Decimal result(*this);
michael@0:     result.m_data.setSign(invertSign(m_data.sign()));
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: Decimal Decimal::operator+(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal& lhs = *this;
michael@0:     const Sign lhsSign = lhs.sign();
michael@0:     const Sign rhsSign = rhs.sign();
michael@0: 
michael@0:     SpecialValueHandler handler(lhs, rhs);
michael@0:     switch (handler.handle()) {
michael@0:     case SpecialValueHandler::BothFinite:
michael@0:         break;
michael@0: 
michael@0:     case SpecialValueHandler::BothInfinity:
michael@0:         return lhsSign == rhsSign ? lhs : nan();
michael@0: 
michael@0:     case SpecialValueHandler::EitherNaN:
michael@0:         return handler.value();
michael@0: 
michael@0:     case SpecialValueHandler::LHSIsInfinity:
michael@0:         return lhs;
michael@0: 
michael@0:     case SpecialValueHandler::RHSIsInfinity:
michael@0:         return rhs;
michael@0:     }
michael@0: 
michael@0:     const AlignedOperands alignedOperands = alignOperands(lhs, rhs);
michael@0: 
michael@0:     const uint64_t result = lhsSign == rhsSign
michael@0:         ? alignedOperands.lhsCoefficient + alignedOperands.rhsCoefficient
michael@0:         : alignedOperands.lhsCoefficient - alignedOperands.rhsCoefficient;
michael@0: 
michael@0:     if (lhsSign == Negative && rhsSign == Positive && !result)
michael@0:         return Decimal(Positive, alignedOperands.exponent, 0);
michael@0: 
michael@0:     return static_cast<int64_t>(result) >= 0
michael@0:         ? Decimal(lhsSign, alignedOperands.exponent, result)
michael@0:         : Decimal(invertSign(lhsSign), alignedOperands.exponent, -static_cast<int64_t>(result));
michael@0: }
michael@0: 
michael@0: Decimal Decimal::operator-(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal& lhs = *this;
michael@0:     const Sign lhsSign = lhs.sign();
michael@0:     const Sign rhsSign = rhs.sign();
michael@0: 
michael@0:     SpecialValueHandler handler(lhs, rhs);
michael@0:     switch (handler.handle()) {
michael@0:     case SpecialValueHandler::BothFinite:
michael@0:         break;
michael@0: 
michael@0:     case SpecialValueHandler::BothInfinity:
michael@0:         return lhsSign == rhsSign ? nan() : lhs;
michael@0: 
michael@0:     case SpecialValueHandler::EitherNaN:
michael@0:         return handler.value();
michael@0: 
michael@0:     case SpecialValueHandler::LHSIsInfinity:
michael@0:         return lhs;
michael@0: 
michael@0:     case SpecialValueHandler::RHSIsInfinity:
michael@0:         return infinity(invertSign(rhsSign));
michael@0:     }
michael@0: 
michael@0:     const AlignedOperands alignedOperands = alignOperands(lhs, rhs);
michael@0: 
michael@0:     const uint64_t result = lhsSign == rhsSign
michael@0:         ? alignedOperands.lhsCoefficient - alignedOperands.rhsCoefficient
michael@0:         : alignedOperands.lhsCoefficient + alignedOperands.rhsCoefficient;
michael@0: 
michael@0:     if (lhsSign == Negative && rhsSign == Negative && !result)
michael@0:         return Decimal(Positive, alignedOperands.exponent, 0);
michael@0: 
michael@0:     return static_cast<int64_t>(result) >= 0
michael@0:         ? Decimal(lhsSign, alignedOperands.exponent, result)
michael@0:         : Decimal(invertSign(lhsSign), alignedOperands.exponent, -static_cast<int64_t>(result));
michael@0: }
michael@0: 
michael@0: Decimal Decimal::operator*(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal& lhs = *this;
michael@0:     const Sign lhsSign = lhs.sign();
michael@0:     const Sign rhsSign = rhs.sign();
michael@0:     const Sign resultSign = lhsSign == rhsSign ? Positive : Negative;
michael@0: 
michael@0:     SpecialValueHandler handler(lhs, rhs);
michael@0:     switch (handler.handle()) {
michael@0:     case SpecialValueHandler::BothFinite: {
michael@0:         const uint64_t lhsCoefficient = lhs.m_data.coefficient();
michael@0:         const uint64_t rhsCoefficient = rhs.m_data.coefficient();
michael@0:         int resultExponent = lhs.exponent() + rhs.exponent();
michael@0:         UInt128 work(UInt128::multiply(lhsCoefficient, rhsCoefficient));
michael@0:         while (work.high()) {
michael@0:             work /= 10;
michael@0:             ++resultExponent;
michael@0:         }
michael@0:         return Decimal(resultSign, resultExponent, work.low());
michael@0:     }
michael@0: 
michael@0:     case SpecialValueHandler::BothInfinity:
michael@0:         return infinity(resultSign);
michael@0: 
michael@0:     case SpecialValueHandler::EitherNaN:
michael@0:         return handler.value();
michael@0: 
michael@0:     case SpecialValueHandler::LHSIsInfinity:
michael@0:         return rhs.isZero() ? nan() : infinity(resultSign);
michael@0: 
michael@0:     case SpecialValueHandler::RHSIsInfinity:
michael@0:         return lhs.isZero() ? nan() : infinity(resultSign);
michael@0:     }
michael@0: 
michael@0:     ASSERT_NOT_REACHED();
michael@0:     return nan();
michael@0: }
michael@0: 
michael@0: Decimal Decimal::operator/(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal& lhs = *this;
michael@0:     const Sign lhsSign = lhs.sign();
michael@0:     const Sign rhsSign = rhs.sign();
michael@0:     const Sign resultSign = lhsSign == rhsSign ? Positive : Negative;
michael@0: 
michael@0:     SpecialValueHandler handler(lhs, rhs);
michael@0:     switch (handler.handle()) {
michael@0:     case SpecialValueHandler::BothFinite:
michael@0:         break;
michael@0: 
michael@0:     case SpecialValueHandler::BothInfinity:
michael@0:         return nan();
michael@0: 
michael@0:     case SpecialValueHandler::EitherNaN:
michael@0:         return handler.value();
michael@0: 
michael@0:     case SpecialValueHandler::LHSIsInfinity:
michael@0:         return infinity(resultSign);
michael@0: 
michael@0:     case SpecialValueHandler::RHSIsInfinity:
michael@0:         return zero(resultSign);
michael@0:     }
michael@0: 
michael@0:     ASSERT(lhs.isFinite());
michael@0:     ASSERT(rhs.isFinite());
michael@0: 
michael@0:     if (rhs.isZero())
michael@0:         return lhs.isZero() ? nan() : infinity(resultSign);
michael@0: 
michael@0:     int resultExponent = lhs.exponent() - rhs.exponent();
michael@0: 
michael@0:     if (lhs.isZero())
michael@0:         return Decimal(resultSign, resultExponent, 0);
michael@0: 
michael@0:     uint64_t remainder = lhs.m_data.coefficient();
michael@0:     const uint64_t divisor = rhs.m_data.coefficient();
michael@0:     uint64_t result = 0;
michael@0:     while (result < MaxCoefficient / 100) {
michael@0:         while (remainder < divisor) {
michael@0:             remainder *= 10;
michael@0:             result *= 10;
michael@0:             --resultExponent;
michael@0:         }
michael@0:         result += remainder / divisor;
michael@0:         remainder %= divisor;
michael@0:         if (!remainder)
michael@0:             break;
michael@0:     }
michael@0: 
michael@0:     if (remainder > divisor / 2)
michael@0:         ++result;
michael@0: 
michael@0:     return Decimal(resultSign, resultExponent, result);
michael@0: }
michael@0: 
michael@0: bool Decimal::operator==(const Decimal& rhs) const
michael@0: {
michael@0:     if (isNaN() || rhs.isNaN())
michael@0:         return false;
michael@0:     return m_data == rhs.m_data || compareTo(rhs).isZero();
michael@0: }
michael@0: 
michael@0: bool Decimal::operator!=(const Decimal& rhs) const
michael@0: {
michael@0:     if (isNaN() || rhs.isNaN())
michael@0:         return true;
michael@0:     if (m_data == rhs.m_data)
michael@0:         return false;
michael@0:     const Decimal result = compareTo(rhs);
michael@0:     if (result.isNaN())
michael@0:         return false;
michael@0:     return !result.isZero();
michael@0: }
michael@0: 
michael@0: bool Decimal::operator<(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal result = compareTo(rhs);
michael@0:     if (result.isNaN())
michael@0:         return false;
michael@0:     return !result.isZero() && result.isNegative();
michael@0: }
michael@0: 
michael@0: bool Decimal::operator<=(const Decimal& rhs) const
michael@0: {
michael@0:     if (isNaN() || rhs.isNaN())
michael@0:         return false;
michael@0:     if (m_data == rhs.m_data)
michael@0:         return true;
michael@0:     const Decimal result = compareTo(rhs);
michael@0:     if (result.isNaN())
michael@0:         return false;
michael@0:     return result.isZero() || result.isNegative();
michael@0: }
michael@0: 
michael@0: bool Decimal::operator>(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal result = compareTo(rhs);
michael@0:     if (result.isNaN())
michael@0:         return false;
michael@0:     return !result.isZero() && result.isPositive();
michael@0: }
michael@0: 
michael@0: bool Decimal::operator>=(const Decimal& rhs) const
michael@0: {
michael@0:     if (isNaN() || rhs.isNaN())
michael@0:         return false;
michael@0:     if (m_data == rhs.m_data)
michael@0:         return true;
michael@0:     const Decimal result = compareTo(rhs);
michael@0:     if (result.isNaN())
michael@0:         return false;
michael@0:     return result.isZero() || !result.isNegative();
michael@0: }
michael@0: 
michael@0: Decimal Decimal::abs() const
michael@0: {
michael@0:     Decimal result(*this);
michael@0:     result.m_data.setSign(Positive);
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: Decimal::AlignedOperands Decimal::alignOperands(const Decimal& lhs, const Decimal& rhs)
michael@0: {
michael@0:     ASSERT(lhs.isFinite());
michael@0:     ASSERT(rhs.isFinite());
michael@0: 
michael@0:     const int lhsExponent = lhs.exponent();
michael@0:     const int rhsExponent = rhs.exponent();
michael@0:     int exponent = std::min(lhsExponent, rhsExponent);
michael@0:     uint64_t lhsCoefficient = lhs.m_data.coefficient();
michael@0:     uint64_t rhsCoefficient = rhs.m_data.coefficient();
michael@0: 
michael@0:     if (lhsExponent > rhsExponent) {
michael@0:         const int numberOfLHSDigits = countDigits(lhsCoefficient);
michael@0:         if (numberOfLHSDigits) {
michael@0:             const int lhsShiftAmount = lhsExponent - rhsExponent;
michael@0:             const int overflow = numberOfLHSDigits + lhsShiftAmount - Precision;
michael@0:             if (overflow <= 0)
michael@0:                 lhsCoefficient = scaleUp(lhsCoefficient, lhsShiftAmount);
michael@0:             else {
michael@0:                 lhsCoefficient = scaleUp(lhsCoefficient, lhsShiftAmount - overflow);
michael@0:                 rhsCoefficient = scaleDown(rhsCoefficient, overflow);
michael@0:                 exponent += overflow;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:     } else if (lhsExponent < rhsExponent) {
michael@0:         const int numberOfRHSDigits = countDigits(rhsCoefficient);
michael@0:         if (numberOfRHSDigits) {
michael@0:             const int rhsShiftAmount = rhsExponent - lhsExponent;
michael@0:             const int overflow = numberOfRHSDigits + rhsShiftAmount - Precision;
michael@0:             if (overflow <= 0)
michael@0:                 rhsCoefficient = scaleUp(rhsCoefficient, rhsShiftAmount);
michael@0:             else {
michael@0:                 rhsCoefficient = scaleUp(rhsCoefficient, rhsShiftAmount - overflow);
michael@0:                 lhsCoefficient = scaleDown(lhsCoefficient, overflow);
michael@0:                 exponent += overflow;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     AlignedOperands alignedOperands;
michael@0:     alignedOperands.exponent = exponent;
michael@0:     alignedOperands.lhsCoefficient = lhsCoefficient;
michael@0:     alignedOperands.rhsCoefficient = rhsCoefficient;
michael@0:     return alignedOperands;
michael@0: }
michael@0: 
michael@0: // Round toward positive infinity.
michael@0: // Note: Mac ports defines ceil(x) as wtf_ceil(x), so we can't use name "ceil" here.
michael@0: Decimal Decimal::ceiling() const
michael@0: {
michael@0:     if (isSpecial())
michael@0:         return *this;
michael@0: 
michael@0:     if (exponent() >= 0)
michael@0:         return *this;
michael@0: 
michael@0:     uint64_t coefficient = m_data.coefficient();
michael@0:     const int numberOfDigits = countDigits(coefficient);
michael@0:     const int numberOfDropDigits = -exponent();
michael@0:     if (numberOfDigits < numberOfDropDigits)
michael@0:         return isPositive() ? Decimal(1) : zero(Positive);
michael@0: 
michael@0:     uint64_t result = scaleDown(coefficient, numberOfDropDigits);
michael@0:     uint64_t droppedDigits = coefficient - scaleUp(result, numberOfDropDigits);
michael@0:     if (droppedDigits && isPositive())
michael@0:         result += 1;
michael@0:     return Decimal(sign(), 0, result);
michael@0: }
michael@0: 
michael@0: Decimal Decimal::compareTo(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal result(*this - rhs);
michael@0:     switch (result.m_data.formatClass()) {
michael@0:     case EncodedData::ClassInfinity:
michael@0:         return result.isNegative() ? Decimal(-1) : Decimal(1);
michael@0: 
michael@0:     case EncodedData::ClassNaN:
michael@0:     case EncodedData::ClassNormal:
michael@0:         return result;
michael@0: 
michael@0:     case EncodedData::ClassZero:
michael@0:         return zero(Positive);
michael@0: 
michael@0:     default:
michael@0:         ASSERT_NOT_REACHED();
michael@0:         return nan();
michael@0:     }
michael@0: }
michael@0: 
michael@0: // Round toward negative infinity.
michael@0: Decimal Decimal::floor() const
michael@0: {
michael@0:     if (isSpecial())
michael@0:         return *this;
michael@0: 
michael@0:     if (exponent() >= 0)
michael@0:         return *this;
michael@0: 
michael@0:     uint64_t coefficient = m_data.coefficient();
michael@0:     const int numberOfDigits = countDigits(coefficient);
michael@0:     const int numberOfDropDigits = -exponent();
michael@0:     if (numberOfDigits < numberOfDropDigits)
michael@0:         return isPositive() ? zero(Positive) : Decimal(-1);
michael@0: 
michael@0:     uint64_t result = scaleDown(coefficient, numberOfDropDigits);
michael@0:     uint64_t droppedDigits = coefficient - scaleUp(result, numberOfDropDigits);
michael@0:     if (droppedDigits && isNegative()) {
michael@0:         result += 1;
michael@0:     }
michael@0:     return Decimal(sign(), 0, result);
michael@0: }
michael@0: 
michael@0: Decimal Decimal::fromDouble(double doubleValue)
michael@0: {
michael@0:     if (std::isfinite(doubleValue))
michael@0:         return fromString(mozToString(doubleValue));
michael@0: 
michael@0:     if (std::isinf(doubleValue))
michael@0:         return infinity(doubleValue < 0 ? Negative : Positive);
michael@0: 
michael@0:     return nan();
michael@0: }
michael@0: 
michael@0: Decimal Decimal::fromString(const String& str)
michael@0: {
michael@0:     int exponent = 0;
michael@0:     Sign exponentSign = Positive;
michael@0:     int numberOfDigits = 0;
michael@0:     int numberOfDigitsAfterDot = 0;
michael@0:     int numberOfExtraDigits = 0;
michael@0:     Sign sign = Positive;
michael@0: 
michael@0:     enum {
michael@0:         StateDigit,
michael@0:         StateDot,
michael@0:         StateDotDigit,
michael@0:         StateE,
michael@0:         StateEDigit,
michael@0:         StateESign,
michael@0:         StateSign,
michael@0:         StateStart,
michael@0:         StateZero,
michael@0:     } state = StateStart;
michael@0: 
michael@0: #define HandleCharAndBreak(expected, nextState) \
michael@0:     if (ch == expected) { \
michael@0:         state = nextState; \
michael@0:         break; \
michael@0:     }
michael@0: 
michael@0: #define HandleTwoCharsAndBreak(expected1, expected2, nextState) \
michael@0:     if (ch == expected1 || ch == expected2) { \
michael@0:         state = nextState; \
michael@0:         break; \
michael@0:     }
michael@0: 
michael@0:     uint64_t accumulator = 0;
michael@0:     for (unsigned index = 0; index < str.length(); ++index) {
michael@0:         const int ch = str[index];
michael@0:         switch (state) {
michael@0:         case StateDigit:
michael@0:             if (ch >= '0' && ch <= '9') {
michael@0:                 if (numberOfDigits < Precision) {
michael@0:                     ++numberOfDigits;
michael@0:                     accumulator *= 10;
michael@0:                     accumulator += ch - '0';
michael@0:                 } else
michael@0:                     ++numberOfExtraDigits;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             HandleCharAndBreak('.', StateDot);
michael@0:             HandleTwoCharsAndBreak('E', 'e', StateE);
michael@0:             return nan();
michael@0: 
michael@0:         case StateDot:
michael@0:             if (ch >= '0' && ch <= '9') {
michael@0:                 if (numberOfDigits < Precision) {
michael@0:                     ++numberOfDigits;
michael@0:                     ++numberOfDigitsAfterDot;
michael@0:                     accumulator *= 10;
michael@0:                     accumulator += ch - '0';
michael@0:                 }
michael@0:                 state = StateDotDigit;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:         case StateDotDigit:
michael@0:             if (ch >= '0' && ch <= '9') {
michael@0:                 if (numberOfDigits < Precision) {
michael@0:                     ++numberOfDigits;
michael@0:                     ++numberOfDigitsAfterDot;
michael@0:                     accumulator *= 10;
michael@0:                     accumulator += ch - '0';
michael@0:                 }
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             HandleTwoCharsAndBreak('E', 'e', StateE);
michael@0:             return nan();
michael@0: 
michael@0:         case StateE:
michael@0:             if (ch == '+') {
michael@0:                 exponentSign = Positive;
michael@0:                 state = StateESign;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             if (ch == '-') {
michael@0:                 exponentSign = Negative;
michael@0:                 state = StateESign;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             if (ch >= '0' && ch <= '9') {
michael@0:                 exponent = ch - '0';
michael@0:                 state = StateEDigit;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             return nan();
michael@0: 
michael@0:         case StateEDigit:
michael@0:             if (ch >= '0' && ch <= '9') {
michael@0:                 exponent *= 10;
michael@0:                 exponent += ch - '0';
michael@0:                 if (exponent > ExponentMax + Precision) {
michael@0:                     if (accumulator)
michael@0:                         return exponentSign == Negative ? zero(Positive) : infinity(sign);
michael@0:                     return zero(sign);
michael@0:                 }
michael@0:                 state = StateEDigit;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             return nan();
michael@0: 
michael@0:         case StateESign:
michael@0:             if (ch >= '0' && ch <= '9') {
michael@0:                 exponent = ch - '0';
michael@0:                 state = StateEDigit;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             return nan();
michael@0: 
michael@0:         case StateSign:
michael@0:             if (ch >= '1' && ch <= '9') {
michael@0:                 accumulator = ch - '0';
michael@0:                 numberOfDigits = 1;
michael@0:                 state = StateDigit;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             HandleCharAndBreak('0', StateZero);
michael@0:             return nan();
michael@0: 
michael@0:         case StateStart:
michael@0:             if (ch >= '1' && ch <= '9') {
michael@0:                 accumulator = ch - '0';
michael@0:                 numberOfDigits = 1;
michael@0:                 state = StateDigit;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             if (ch == '-') {
michael@0:                 sign = Negative;
michael@0:                 state = StateSign;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             if (ch == '+') {
michael@0:                 sign = Positive;
michael@0:                 state = StateSign;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             HandleCharAndBreak('0', StateZero);
michael@0:             HandleCharAndBreak('.', StateDot);
michael@0:             return nan();
michael@0: 
michael@0:         case StateZero:
michael@0:             if (ch == '0')
michael@0:                 break;
michael@0: 
michael@0:             if (ch >= '1' && ch <= '9') {
michael@0:                 accumulator = ch - '0';
michael@0:                 numberOfDigits = 1;
michael@0:                 state = StateDigit;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             HandleCharAndBreak('.', StateDot);
michael@0:             HandleTwoCharsAndBreak('E', 'e', StateE);
michael@0:             return nan();
michael@0: 
michael@0:         default:
michael@0:             ASSERT_NOT_REACHED();
michael@0:             return nan();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (state == StateZero)
michael@0:         return zero(sign);
michael@0: 
michael@0:     if (state == StateDigit || state == StateEDigit || state == StateDotDigit) {
michael@0:         int resultExponent = exponent * (exponentSign == Negative ? -1 : 1) - numberOfDigitsAfterDot + numberOfExtraDigits;
michael@0:         if (resultExponent < ExponentMin)
michael@0:             return zero(Positive);
michael@0: 
michael@0:         const int overflow = resultExponent - ExponentMax + 1;
michael@0:         if (overflow > 0) {
michael@0:             if (overflow + numberOfDigits - numberOfDigitsAfterDot > Precision)
michael@0:                 return infinity(sign);
michael@0:             accumulator = scaleUp(accumulator, overflow);
michael@0:             resultExponent -= overflow;
michael@0:         }
michael@0: 
michael@0:         return Decimal(sign, resultExponent, accumulator);
michael@0:     }
michael@0: 
michael@0:     return nan();
michael@0: }
michael@0: 
michael@0: Decimal Decimal::infinity(const Sign sign)
michael@0: {
michael@0:     return Decimal(EncodedData(sign, EncodedData::ClassInfinity));
michael@0: }
michael@0: 
michael@0: Decimal Decimal::nan()
michael@0: {
michael@0:     return Decimal(EncodedData(Positive, EncodedData::ClassNaN));
michael@0: }
michael@0: 
michael@0: Decimal Decimal::remainder(const Decimal& rhs) const
michael@0: {
michael@0:     const Decimal quotient = *this / rhs;
michael@0:     return quotient.isSpecial() ? quotient : *this - (quotient.isNegative() ? quotient.ceiling() : quotient.floor()) * rhs;
michael@0: }
michael@0: 
michael@0: Decimal Decimal::round() const
michael@0: {
michael@0:     if (isSpecial())
michael@0:         return *this;
michael@0: 
michael@0:     if (exponent() >= 0)
michael@0:         return *this;
michael@0: 
michael@0:     uint64_t result = m_data.coefficient();
michael@0:     const int numberOfDigits = countDigits(result);
michael@0:     const int numberOfDropDigits = -exponent();
michael@0:     if (numberOfDigits < numberOfDropDigits)
michael@0:         return zero(Positive);
michael@0: 
michael@0:     // We're implementing round-half-away-from-zero, so we only need the one
michael@0:     // (the most significant) fractional digit:
michael@0:     result = scaleDown(result, numberOfDropDigits - 1);
michael@0:     if (result % 10 >= 5)
michael@0:         result += 10;
michael@0:     result /= 10;
michael@0:     return Decimal(sign(), 0, result);
michael@0: }
michael@0: 
michael@0: double Decimal::toDouble() const
michael@0: {
michael@0:     if (isFinite()) {
michael@0:         bool valid;
michael@0:         const double doubleValue = mozToDouble(toString(), &valid);
michael@0:         return valid ? doubleValue : std::numeric_limits<double>::quiet_NaN();
michael@0:     }
michael@0: 
michael@0:     if (isInfinity())
michael@0:         return isNegative() ? -std::numeric_limits<double>::infinity() : std::numeric_limits<double>::infinity();
michael@0: 
michael@0:     return std::numeric_limits<double>::quiet_NaN();
michael@0: }
michael@0: 
michael@0: String Decimal::toString() const
michael@0: {
michael@0:     switch (m_data.formatClass()) {
michael@0:     case EncodedData::ClassInfinity:
michael@0:         return sign() ? "-Infinity" : "Infinity";
michael@0: 
michael@0:     case EncodedData::ClassNaN:
michael@0:         return "NaN";
michael@0: 
michael@0:     case EncodedData::ClassNormal:
michael@0:     case EncodedData::ClassZero:
michael@0:         break;
michael@0: 
michael@0:     default:
michael@0:         ASSERT_NOT_REACHED();
michael@0:         return "";
michael@0:     }
michael@0: 
michael@0:     StringBuilder builder;
michael@0:     if (sign())
michael@0:         builder.append('-');
michael@0: 
michael@0:     int originalExponent = exponent();
michael@0:     uint64_t coefficient = m_data.coefficient();
michael@0: 
michael@0:     if (originalExponent < 0) {
michael@0:         const int maxDigits = DBL_DIG;
michael@0:         uint64_t lastDigit = 0;
michael@0:         while (countDigits(coefficient) > maxDigits) {
michael@0:             lastDigit = coefficient % 10;
michael@0:             coefficient /= 10;
michael@0:             ++originalExponent;
michael@0:         }
michael@0: 
michael@0:         if (lastDigit >= 5)
michael@0:             ++coefficient;
michael@0: 
michael@0:         while (originalExponent < 0 && coefficient && !(coefficient % 10)) {
michael@0:             coefficient /= 10;
michael@0:             ++originalExponent;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     const String digits = mozToString(coefficient);
michael@0:     int coefficientLength = static_cast<int>(digits.length());
michael@0:     const int adjustedExponent = originalExponent + coefficientLength - 1;
michael@0:     if (originalExponent <= 0 && adjustedExponent >= -6) {
michael@0:         if (!originalExponent) {
michael@0:             builder.append(digits);
michael@0:             return builder.toString();
michael@0:         }
michael@0: 
michael@0:         if (adjustedExponent >= 0) {
michael@0:             for (int i = 0; i < coefficientLength; ++i) {
michael@0:                 builder.append(digits[i]);
michael@0:                 if (i == adjustedExponent)
michael@0:                     builder.append('.');
michael@0:             }
michael@0:             return builder.toString();
michael@0:         }
michael@0: 
michael@0:         builder.appendLiteral("0.");
michael@0:         for (int i = adjustedExponent + 1; i < 0; ++i)
michael@0:             builder.append('0');
michael@0: 
michael@0:         builder.append(digits);
michael@0: 
michael@0:     } else {
michael@0:         builder.append(digits[0]);
michael@0:         while (coefficientLength >= 2 && digits[coefficientLength - 1] == '0')
michael@0:             --coefficientLength;
michael@0:         if (coefficientLength >= 2) {
michael@0:             builder.append('.');
michael@0:             for (int i = 1; i < coefficientLength; ++i)
michael@0:                 builder.append(digits[i]);
michael@0:         }
michael@0: 
michael@0:         if (adjustedExponent) {
michael@0:             builder.append(adjustedExponent < 0 ? "e" : "e+");
michael@0:             builder.appendNumber(adjustedExponent);
michael@0:         }
michael@0:     }
michael@0:     return builder.toString();
michael@0: }
michael@0: 
michael@0: bool Decimal::toString(char* strBuf, size_t bufLength) const
michael@0: {
michael@0:   ASSERT(bufLength > 0);
michael@0:   String str = toString();
michael@0:   size_t length = str.copy(strBuf, bufLength);
michael@0:   if (length < bufLength) {
michael@0:     strBuf[length] = '\0';
michael@0:     return true;
michael@0:   }
michael@0:   strBuf[bufLength - 1] = '\0';
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: Decimal Decimal::zero(Sign sign)
michael@0: {
michael@0:     return Decimal(EncodedData(sign, EncodedData::ClassZero));
michael@0: }
michael@0: 
michael@0: } // namespace WebCore
michael@0: