diff options
Diffstat (limited to 'include/llvm/Support/ScaledNumber.h')
| -rw-r--r-- | include/llvm/Support/ScaledNumber.h | 897 |
1 files changed, 897 insertions, 0 deletions
diff --git a/include/llvm/Support/ScaledNumber.h b/include/llvm/Support/ScaledNumber.h new file mode 100644 index 0000000..2bd7e74 --- /dev/null +++ b/include/llvm/Support/ScaledNumber.h @@ -0,0 +1,897 @@ +//===- llvm/Support/ScaledNumber.h - Support for scaled numbers -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains functions (and a class) useful for working with scaled +// numbers -- in particular, pairs of integers where one represents digits and +// another represents a scale. The functions are helpers and live in the +// namespace ScaledNumbers. The class ScaledNumber is useful for modelling +// certain cost metrics that need simple, integer-like semantics that are easy +// to reason about. +// +// These might remind you of soft-floats. If you want one of those, you're in +// the wrong place. Look at include/llvm/ADT/APFloat.h instead. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_SCALEDNUMBER_H +#define LLVM_SUPPORT_SCALEDNUMBER_H + +#include "llvm/Support/MathExtras.h" + +#include <algorithm> +#include <cstdint> +#include <limits> +#include <string> +#include <tuple> +#include <utility> + +namespace llvm { +namespace ScaledNumbers { + +/// \brief Maximum scale; same as APFloat for easy debug printing. +const int32_t MaxScale = 16383; + +/// \brief Maximum scale; same as APFloat for easy debug printing. +const int32_t MinScale = -16382; + +/// \brief Get the width of a number. +template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; } + +/// \brief Conditionally round up a scaled number. +/// +/// Given \c Digits and \c Scale, round up iff \c ShouldRound is \c true. +/// Always returns \c Scale unless there's an overflow, in which case it +/// returns \c 1+Scale. +/// +/// \pre adding 1 to \c Scale will not overflow INT16_MAX. +template <class DigitsT> +inline std::pair<DigitsT, int16_t> getRounded(DigitsT Digits, int16_t Scale, + bool ShouldRound) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + if (ShouldRound) + if (!++Digits) + // Overflow. + return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1); + return std::make_pair(Digits, Scale); +} + +/// \brief Convenience helper for 32-bit rounding. +inline std::pair<uint32_t, int16_t> getRounded32(uint32_t Digits, int16_t Scale, + bool ShouldRound) { + return getRounded(Digits, Scale, ShouldRound); +} + +/// \brief Convenience helper for 64-bit rounding. +inline std::pair<uint64_t, int16_t> getRounded64(uint64_t Digits, int16_t Scale, + bool ShouldRound) { + return getRounded(Digits, Scale, ShouldRound); +} + +/// \brief Adjust a 64-bit scaled number down to the appropriate width. +/// +/// \pre Adding 64 to \c Scale will not overflow INT16_MAX. +template <class DigitsT> +inline std::pair<DigitsT, int16_t> getAdjusted(uint64_t Digits, + int16_t Scale = 0) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + const int Width = getWidth<DigitsT>(); + if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max()) + return std::make_pair(Digits, Scale); + + // Shift right and round. + int Shift = 64 - Width - countLeadingZeros(Digits); + return getRounded<DigitsT>(Digits >> Shift, Scale + Shift, + Digits & (UINT64_C(1) << (Shift - 1))); +} + +/// \brief Convenience helper for adjusting to 32 bits. +inline std::pair<uint32_t, int16_t> getAdjusted32(uint64_t Digits, + int16_t Scale = 0) { + return getAdjusted<uint32_t>(Digits, Scale); +} + +/// \brief Convenience helper for adjusting to 64 bits. +inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits, + int16_t Scale = 0) { + return getAdjusted<uint64_t>(Digits, Scale); +} + +/// \brief Multiply two 64-bit integers to create a 64-bit scaled number. +/// +/// Implemented with four 64-bit integer multiplies. +std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS); + +/// \brief Multiply two 32-bit integers to create a 32-bit scaled number. +/// +/// Implemented with one 64-bit integer multiply. +template <class DigitsT> +inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX)) + return getAdjusted<DigitsT>(uint64_t(LHS) * RHS); + + return multiply64(LHS, RHS); +} + +/// \brief Convenience helper for 32-bit product. +inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) { + return getProduct(LHS, RHS); +} + +/// \brief Convenience helper for 64-bit product. +inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) { + return getProduct(LHS, RHS); +} + +/// \brief Divide two 64-bit integers to create a 64-bit scaled number. +/// +/// Implemented with long division. +/// +/// \pre \c Dividend and \c Divisor are non-zero. +std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor); + +/// \brief Divide two 32-bit integers to create a 32-bit scaled number. +/// +/// Implemented with one 64-bit integer divide/remainder pair. +/// +/// \pre \c Dividend and \c Divisor are non-zero. +std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor); + +/// \brief Divide two 32-bit numbers to create a 32-bit scaled number. +/// +/// Implemented with one 64-bit integer divide/remainder pair. +/// +/// Returns \c (DigitsT_MAX, MaxScale) for divide-by-zero (0 for 0/0). +template <class DigitsT> +std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8, + "expected 32-bit or 64-bit digits"); + + // Check for zero. + if (!Dividend) + return std::make_pair(0, 0); + if (!Divisor) + return std::make_pair(std::numeric_limits<DigitsT>::max(), MaxScale); + + if (getWidth<DigitsT>() == 64) + return divide64(Dividend, Divisor); + return divide32(Dividend, Divisor); +} + +/// \brief Convenience helper for 32-bit quotient. +inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend, + uint32_t Divisor) { + return getQuotient(Dividend, Divisor); +} + +/// \brief Convenience helper for 64-bit quotient. +inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend, + uint64_t Divisor) { + return getQuotient(Dividend, Divisor); +} + +/// \brief Implementation of getLg() and friends. +/// +/// Returns the rounded lg of \c Digits*2^Scale and an int specifying whether +/// this was rounded up (1), down (-1), or exact (0). +/// +/// Returns \c INT32_MIN when \c Digits is zero. +template <class DigitsT> +inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + if (!Digits) + return std::make_pair(INT32_MIN, 0); + + // Get the floor of the lg of Digits. + int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1; + + // Get the actual floor. + int32_t Floor = Scale + LocalFloor; + if (Digits == UINT64_C(1) << LocalFloor) + return std::make_pair(Floor, 0); + + // Round based on the next digit. + assert(LocalFloor >= 1); + bool Round = Digits & UINT64_C(1) << (LocalFloor - 1); + return std::make_pair(Floor + Round, Round ? 1 : -1); +} + +/// \brief Get the lg (rounded) of a scaled number. +/// +/// Get the lg of \c Digits*2^Scale. +/// +/// Returns \c INT32_MIN when \c Digits is zero. +template <class DigitsT> int32_t getLg(DigitsT Digits, int16_t Scale) { + return getLgImpl(Digits, Scale).first; +} + +/// \brief Get the lg floor of a scaled number. +/// +/// Get the floor of the lg of \c Digits*2^Scale. +/// +/// Returns \c INT32_MIN when \c Digits is zero. +template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) { + auto Lg = getLgImpl(Digits, Scale); + return Lg.first - (Lg.second > 0); +} + +/// \brief Get the lg ceiling of a scaled number. +/// +/// Get the ceiling of the lg of \c Digits*2^Scale. +/// +/// Returns \c INT32_MIN when \c Digits is zero. +template <class DigitsT> int32_t getLgCeiling(DigitsT Digits, int16_t Scale) { + auto Lg = getLgImpl(Digits, Scale); + return Lg.first + (Lg.second < 0); +} + +/// \brief Implementation for comparing scaled numbers. +/// +/// Compare two 64-bit numbers with different scales. Given that the scale of +/// \c L is higher than that of \c R by \c ScaleDiff, compare them. Return -1, +/// 1, and 0 for less than, greater than, and equal, respectively. +/// +/// \pre 0 <= ScaleDiff < 64. +int compareImpl(uint64_t L, uint64_t R, int ScaleDiff); + +/// \brief Compare two scaled numbers. +/// +/// Compare two scaled numbers. Returns 0 for equal, -1 for less than, and 1 +/// for greater than. +template <class DigitsT> +int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + // Check for zero. + if (!LDigits) + return RDigits ? -1 : 0; + if (!RDigits) + return 1; + + // Check for the scale. Use getLgFloor to be sure that the scale difference + // is always lower than 64. + int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale); + if (lgL != lgR) + return lgL < lgR ? -1 : 1; + + // Compare digits. + if (LScale < RScale) + return compareImpl(LDigits, RDigits, RScale - LScale); + + return -compareImpl(RDigits, LDigits, LScale - RScale); +} + +/// \brief Match scales of two numbers. +/// +/// Given two scaled numbers, match up their scales. Change the digits and +/// scales in place. Shift the digits as necessary to form equivalent numbers, +/// losing precision only when necessary. +/// +/// If the output value of \c LDigits (\c RDigits) is \c 0, the output value of +/// \c LScale (\c RScale) is unspecified. +/// +/// As a convenience, returns the matching scale. If the output value of one +/// number is zero, returns the scale of the other. If both are zero, which +/// scale is returned is unspecifed. +template <class DigitsT> +int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, + int16_t &RScale) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + if (LScale < RScale) + // Swap arguments. + return matchScales(RDigits, RScale, LDigits, LScale); + if (!LDigits) + return RScale; + if (!RDigits || LScale == RScale) + return LScale; + + // Now LScale > RScale. Get the difference. + int32_t ScaleDiff = int32_t(LScale) - RScale; + if (ScaleDiff >= 2 * getWidth<DigitsT>()) { + // Don't bother shifting. RDigits will get zero-ed out anyway. + RDigits = 0; + return LScale; + } + + // Shift LDigits left as much as possible, then shift RDigits right. + int32_t ShiftL = std::min<int32_t>(countLeadingZeros(LDigits), ScaleDiff); + assert(ShiftL < getWidth<DigitsT>() && "can't shift more than width"); + + int32_t ShiftR = ScaleDiff - ShiftL; + if (ShiftR >= getWidth<DigitsT>()) { + // Don't bother shifting. RDigits will get zero-ed out anyway. + RDigits = 0; + return LScale; + } + + LDigits <<= ShiftL; + RDigits >>= ShiftR; + + LScale -= ShiftL; + RScale += ShiftR; + assert(LScale == RScale && "scales should match"); + return LScale; +} + +/// \brief Get the sum of two scaled numbers. +/// +/// Get the sum of two scaled numbers with as much precision as possible. +/// +/// \pre Adding 1 to \c LScale (or \c RScale) will not overflow INT16_MAX. +template <class DigitsT> +std::pair<DigitsT, int16_t> getSum(DigitsT LDigits, int16_t LScale, + DigitsT RDigits, int16_t RScale) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + // Check inputs up front. This is only relevent if addition overflows, but + // testing here should catch more bugs. + assert(LScale < INT16_MAX && "scale too large"); + assert(RScale < INT16_MAX && "scale too large"); + + // Normalize digits to match scales. + int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale); + + // Compute sum. + DigitsT Sum = LDigits + RDigits; + if (Sum >= RDigits) + return std::make_pair(Sum, Scale); + + // Adjust sum after arithmetic overflow. + DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1); + return std::make_pair(HighBit | Sum >> 1, Scale + 1); +} + +/// \brief Convenience helper for 32-bit sum. +inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale, + uint32_t RDigits, int16_t RScale) { + return getSum(LDigits, LScale, RDigits, RScale); +} + +/// \brief Convenience helper for 64-bit sum. +inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale, + uint64_t RDigits, int16_t RScale) { + return getSum(LDigits, LScale, RDigits, RScale); +} + +/// \brief Get the difference of two scaled numbers. +/// +/// Get LHS minus RHS with as much precision as possible. +/// +/// Returns \c (0, 0) if the RHS is larger than the LHS. +template <class DigitsT> +std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale, + DigitsT RDigits, int16_t RScale) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + // Normalize digits to match scales. + const DigitsT SavedRDigits = RDigits; + const int16_t SavedRScale = RScale; + matchScales(LDigits, LScale, RDigits, RScale); + + // Compute difference. + if (LDigits <= RDigits) + return std::make_pair(0, 0); + if (RDigits || !SavedRDigits) + return std::make_pair(LDigits - RDigits, LScale); + + // Check if RDigits just barely lost its last bit. E.g., for 32-bit: + // + // 1*2^32 - 1*2^0 == 0xffffffff != 1*2^32 + const auto RLgFloor = getLgFloor(SavedRDigits, SavedRScale); + if (!compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>())) + return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor); + + return std::make_pair(LDigits, LScale); +} + +/// \brief Convenience helper for 32-bit difference. +inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits, + int16_t LScale, + uint32_t RDigits, + int16_t RScale) { + return getDifference(LDigits, LScale, RDigits, RScale); +} + +/// \brief Convenience helper for 64-bit difference. +inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits, + int16_t LScale, + uint64_t RDigits, + int16_t RScale) { + return getDifference(LDigits, LScale, RDigits, RScale); +} + +} // end namespace ScaledNumbers +} // end namespace llvm + +namespace llvm { + +class raw_ostream; +class ScaledNumberBase { +public: + static const int DefaultPrecision = 10; + + static void dump(uint64_t D, int16_t E, int Width); + static raw_ostream &print(raw_ostream &OS, uint64_t D, int16_t E, int Width, + unsigned Precision); + static std::string toString(uint64_t D, int16_t E, int Width, + unsigned Precision); + static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); } + static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); } + static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); } + + static std::pair<uint64_t, bool> splitSigned(int64_t N) { + if (N >= 0) + return std::make_pair(N, false); + uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N); + return std::make_pair(Unsigned, true); + } + static int64_t joinSigned(uint64_t U, bool IsNeg) { + if (U > uint64_t(INT64_MAX)) + return IsNeg ? INT64_MIN : INT64_MAX; + return IsNeg ? -int64_t(U) : int64_t(U); + } +}; + +/// \brief Simple representation of a scaled number. +/// +/// ScaledNumber is a number represented by digits and a scale. It uses simple +/// saturation arithmetic and every operation is well-defined for every value. +/// It's somewhat similar in behaviour to a soft-float, but is *not* a +/// replacement for one. If you're doing numerics, look at \a APFloat instead. +/// Nevertheless, we've found these semantics useful for modelling certain cost +/// metrics. +/// +/// The number is split into a signed scale and unsigned digits. The number +/// represented is \c getDigits()*2^getScale(). In this way, the digits are +/// much like the mantissa in the x87 long double, but there is no canonical +/// form so the same number can be represented by many bit representations. +/// +/// ScaledNumber is templated on the underlying integer type for digits, which +/// is expected to be unsigned. +/// +/// Unlike APFloat, ScaledNumber does not model architecture floating point +/// behaviour -- while this might make it a little faster and easier to reason +/// about, it certainly makes it more dangerous for general numerics. +/// +/// ScaledNumber is totally ordered. However, there is no canonical form, so +/// there are multiple representations of most scalars. E.g.: +/// +/// ScaledNumber(8u, 0) == ScaledNumber(4u, 1) +/// ScaledNumber(4u, 1) == ScaledNumber(2u, 2) +/// ScaledNumber(2u, 2) == ScaledNumber(1u, 3) +/// +/// ScaledNumber implements most arithmetic operations. Precision is kept +/// where possible. Uses simple saturation arithmetic, so that operations +/// saturate to 0.0 or getLargest() rather than under or overflowing. It has +/// some extra arithmetic for unit inversion. 0.0/0.0 is defined to be 0.0. +/// Any other division by 0.0 is defined to be getLargest(). +/// +/// As a convenience for modifying the exponent, left and right shifting are +/// both implemented, and both interpret negative shifts as positive shifts in +/// the opposite direction. +/// +/// Scales are limited to the range accepted by x87 long double. This makes +/// it trivial to add functionality to convert to APFloat (this is already +/// relied on for the implementation of printing). +/// +/// Possible (and conflicting) future directions: +/// +/// 1. Turn this into a wrapper around \a APFloat. +/// 2. Share the algorithm implementations with \a APFloat. +/// 3. Allow \a ScaledNumber to represent a signed number. +template <class DigitsT> class ScaledNumber : ScaledNumberBase { +public: + static_assert(!std::numeric_limits<DigitsT>::is_signed, + "only unsigned floats supported"); + + typedef DigitsT DigitsType; + +private: + typedef std::numeric_limits<DigitsType> DigitsLimits; + + static const int Width = sizeof(DigitsType) * 8; + static_assert(Width <= 64, "invalid integer width for digits"); + +private: + DigitsType Digits; + int16_t Scale; + +public: + ScaledNumber() : Digits(0), Scale(0) {} + + ScaledNumber(DigitsType Digits, int16_t Scale) + : Digits(Digits), Scale(Scale) {} + +private: + ScaledNumber(const std::pair<uint64_t, int16_t> &X) + : Digits(X.first), Scale(X.second) {} + +public: + static ScaledNumber getZero() { return ScaledNumber(0, 0); } + static ScaledNumber getOne() { return ScaledNumber(1, 0); } + static ScaledNumber getLargest() { + return ScaledNumber(DigitsLimits::max(), ScaledNumbers::MaxScale); + } + static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); } + static ScaledNumber getInverse(uint64_t N) { + return get(N).invert(); + } + static ScaledNumber getFraction(DigitsType N, DigitsType D) { + return getQuotient(N, D); + } + + int16_t getScale() const { return Scale; } + DigitsType getDigits() const { return Digits; } + + /// \brief Convert to the given integer type. + /// + /// Convert to \c IntT using simple saturating arithmetic, truncating if + /// necessary. + template <class IntT> IntT toInt() const; + + bool isZero() const { return !Digits; } + bool isLargest() const { return *this == getLargest(); } + bool isOne() const { + if (Scale > 0 || Scale <= -Width) + return false; + return Digits == DigitsType(1) << -Scale; + } + + /// \brief The log base 2, rounded. + /// + /// Get the lg of the scalar. lg 0 is defined to be INT32_MIN. + int32_t lg() const { return ScaledNumbers::getLg(Digits, Scale); } + + /// \brief The log base 2, rounded towards INT32_MIN. + /// + /// Get the lg floor. lg 0 is defined to be INT32_MIN. + int32_t lgFloor() const { return ScaledNumbers::getLgFloor(Digits, Scale); } + + /// \brief The log base 2, rounded towards INT32_MAX. + /// + /// Get the lg ceiling. lg 0 is defined to be INT32_MIN. + int32_t lgCeiling() const { + return ScaledNumbers::getLgCeiling(Digits, Scale); + } + + bool operator==(const ScaledNumber &X) const { return compare(X) == 0; } + bool operator<(const ScaledNumber &X) const { return compare(X) < 0; } + bool operator!=(const ScaledNumber &X) const { return compare(X) != 0; } + bool operator>(const ScaledNumber &X) const { return compare(X) > 0; } + bool operator<=(const ScaledNumber &X) const { return compare(X) <= 0; } + bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; } + + bool operator!() const { return isZero(); } + + /// \brief Convert to a decimal representation in a string. + /// + /// Convert to a string. Uses scientific notation for very large/small + /// numbers. Scientific notation is used roughly for numbers outside of the + /// range 2^-64 through 2^64. + /// + /// \c Precision indicates the number of decimal digits of precision to use; + /// 0 requests the maximum available. + /// + /// As a special case to make debugging easier, if the number is small enough + /// to convert without scientific notation and has more than \c Precision + /// digits before the decimal place, it's printed accurately to the first + /// digit past zero. E.g., assuming 10 digits of precision: + /// + /// 98765432198.7654... => 98765432198.8 + /// 8765432198.7654... => 8765432198.8 + /// 765432198.7654... => 765432198.8 + /// 65432198.7654... => 65432198.77 + /// 5432198.7654... => 5432198.765 + std::string toString(unsigned Precision = DefaultPrecision) { + return ScaledNumberBase::toString(Digits, Scale, Width, Precision); + } + + /// \brief Print a decimal representation. + /// + /// Print a string. See toString for documentation. + raw_ostream &print(raw_ostream &OS, + unsigned Precision = DefaultPrecision) const { + return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision); + } + void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); } + + ScaledNumber &operator+=(const ScaledNumber &X) { + std::tie(Digits, Scale) = + ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale); + // Check for exponent past MaxScale. + if (Scale > ScaledNumbers::MaxScale) + *this = getLargest(); + return *this; + } + ScaledNumber &operator-=(const ScaledNumber &X) { + std::tie(Digits, Scale) = + ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale); + return *this; + } + ScaledNumber &operator*=(const ScaledNumber &X); + ScaledNumber &operator/=(const ScaledNumber &X); + ScaledNumber &operator<<=(int16_t Shift) { + shiftLeft(Shift); + return *this; + } + ScaledNumber &operator>>=(int16_t Shift) { + shiftRight(Shift); + return *this; + } + +private: + void shiftLeft(int32_t Shift); + void shiftRight(int32_t Shift); + + /// \brief Adjust two floats to have matching exponents. + /// + /// Adjust \c this and \c X to have matching exponents. Returns the new \c X + /// by value. Does nothing if \a isZero() for either. + /// + /// The value that compares smaller will lose precision, and possibly become + /// \a isZero(). + ScaledNumber matchScales(ScaledNumber X) { + ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale); + return X; + } + +public: + /// \brief Scale a large number accurately. + /// + /// Scale N (multiply it by this). Uses full precision multiplication, even + /// if Width is smaller than 64, so information is not lost. + uint64_t scale(uint64_t N) const; + uint64_t scaleByInverse(uint64_t N) const { + // TODO: implement directly, rather than relying on inverse. Inverse is + // expensive. + return inverse().scale(N); + } + int64_t scale(int64_t N) const { + std::pair<uint64_t, bool> Unsigned = splitSigned(N); + return joinSigned(scale(Unsigned.first), Unsigned.second); + } + int64_t scaleByInverse(int64_t N) const { + std::pair<uint64_t, bool> Unsigned = splitSigned(N); + return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second); + } + + int compare(const ScaledNumber &X) const { + return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale); + } + int compareTo(uint64_t N) const { + ScaledNumber Scaled = get(N); + int Compare = compare(Scaled); + if (Width == 64 || Compare != 0) + return Compare; + + // Check for precision loss. We know *this == RoundTrip. + uint64_t RoundTrip = Scaled.template toInt<uint64_t>(); + return N == RoundTrip ? 0 : RoundTrip < N ? -1 : 1; + } + int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); } + + ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; } + ScaledNumber inverse() const { return ScaledNumber(*this).invert(); } + +private: + static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) { + return ScaledNumbers::getProduct(LHS, RHS); + } + static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) { + return ScaledNumbers::getQuotient(Dividend, Divisor); + } + + static int countLeadingZerosWidth(DigitsType Digits) { + if (Width == 64) + return countLeadingZeros64(Digits); + if (Width == 32) + return countLeadingZeros32(Digits); + return countLeadingZeros32(Digits) + Width - 32; + } + + /// \brief Adjust a number to width, rounding up if necessary. + /// + /// Should only be called for \c Shift close to zero. + /// + /// \pre Shift >= MinScale && Shift + 64 <= MaxScale. + static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) { + assert(Shift >= ScaledNumbers::MinScale && "Shift should be close to 0"); + assert(Shift <= ScaledNumbers::MaxScale - 64 && + "Shift should be close to 0"); + auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(N, Shift); + return Adjusted; + } + + static ScaledNumber getRounded(ScaledNumber P, bool Round) { + // Saturate. + if (P.isLargest()) + return P; + + return ScaledNumbers::getRounded(P.Digits, P.Scale, Round); + } +}; + +#define SCALED_NUMBER_BOP(op, base) \ + template <class DigitsT> \ + ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L, \ + const ScaledNumber<DigitsT> &R) { \ + return ScaledNumber<DigitsT>(L) base R; \ + } +SCALED_NUMBER_BOP(+, += ) +SCALED_NUMBER_BOP(-, -= ) +SCALED_NUMBER_BOP(*, *= ) +SCALED_NUMBER_BOP(/, /= ) +SCALED_NUMBER_BOP(<<, <<= ) +SCALED_NUMBER_BOP(>>, >>= ) +#undef SCALED_NUMBER_BOP + +template <class DigitsT> +raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) { + return X.print(OS, 10); +} + +#define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2) \ + template <class DigitsT> \ + bool operator op(const ScaledNumber<DigitsT> &L, T1 R) { \ + return L.compareTo(T2(R)) op 0; \ + } \ + template <class DigitsT> \ + bool operator op(T1 L, const ScaledNumber<DigitsT> &R) { \ + return 0 op R.compareTo(T2(L)); \ + } +#define SCALED_NUMBER_COMPARE_TO(op) \ + SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t) \ + SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t) \ + SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t) \ + SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t) +SCALED_NUMBER_COMPARE_TO(< ) +SCALED_NUMBER_COMPARE_TO(> ) +SCALED_NUMBER_COMPARE_TO(== ) +SCALED_NUMBER_COMPARE_TO(!= ) +SCALED_NUMBER_COMPARE_TO(<= ) +SCALED_NUMBER_COMPARE_TO(>= ) +#undef SCALED_NUMBER_COMPARE_TO +#undef SCALED_NUMBER_COMPARE_TO_TYPE + +template <class DigitsT> +uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const { + if (Width == 64 || N <= DigitsLimits::max()) + return (get(N) * *this).template toInt<uint64_t>(); + + // Defer to the 64-bit version. + return ScaledNumber<uint64_t>(Digits, Scale).scale(N); +} + +template <class DigitsT> +template <class IntT> +IntT ScaledNumber<DigitsT>::toInt() const { + typedef std::numeric_limits<IntT> Limits; + if (*this < 1) + return 0; + if (*this >= Limits::max()) + return Limits::max(); + + IntT N = Digits; + if (Scale > 0) { + assert(size_t(Scale) < sizeof(IntT) * 8); + return N << Scale; + } + if (Scale < 0) { + assert(size_t(-Scale) < sizeof(IntT) * 8); + return N >> -Scale; + } + return N; +} + +template <class DigitsT> +ScaledNumber<DigitsT> &ScaledNumber<DigitsT>:: +operator*=(const ScaledNumber &X) { + if (isZero()) + return *this; + if (X.isZero()) + return *this = X; + + // Save the exponents. + int32_t Scales = int32_t(Scale) + int32_t(X.Scale); + + // Get the raw product. + *this = getProduct(Digits, X.Digits); + + // Combine with exponents. + return *this <<= Scales; +} +template <class DigitsT> +ScaledNumber<DigitsT> &ScaledNumber<DigitsT>:: +operator/=(const ScaledNumber &X) { + if (isZero()) + return *this; + if (X.isZero()) + return *this = getLargest(); + + // Save the exponents. + int32_t Scales = int32_t(Scale) - int32_t(X.Scale); + + // Get the raw quotient. + *this = getQuotient(Digits, X.Digits); + + // Combine with exponents. + return *this <<= Scales; +} +template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) { + if (!Shift || isZero()) + return; + assert(Shift != INT32_MIN); + if (Shift < 0) { + shiftRight(-Shift); + return; + } + + // Shift as much as we can in the exponent. + int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale); + Scale += ScaleShift; + if (ScaleShift == Shift) + return; + + // Check this late, since it's rare. + if (isLargest()) + return; + + // Shift the digits themselves. + Shift -= ScaleShift; + if (Shift > countLeadingZerosWidth(Digits)) { + // Saturate. + *this = getLargest(); + return; + } + + Digits <<= Shift; + return; +} + +template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) { + if (!Shift || isZero()) + return; + assert(Shift != INT32_MIN); + if (Shift < 0) { + shiftLeft(-Shift); + return; + } + + // Shift as much as we can in the exponent. + int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale); + Scale -= ScaleShift; + if (ScaleShift == Shift) + return; + + // Shift the digits themselves. + Shift -= ScaleShift; + if (Shift >= Width) { + // Saturate. + *this = getZero(); + return; + } + + Digits >>= Shift; + return; +} + +template <typename T> struct isPodLike; +template <typename T> struct isPodLike<ScaledNumber<T>> { + static const bool value = true; +}; + +} // end namespace llvm + +#endif |