Fixed.h

Go to the documentation of this file.

/* Copyright (C) 2022 Wildfire Games.
 * This file is part of 0 A.D.
 *
 * 0 A.D. is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * 0 A.D. is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef INCLUDED_FIXED
#define INCLUDED_FIXED

#include "lib/types.h"
#include "maths/Sqrt.h"
#include "ps/CStrForward.h"

#ifndef NDEBUG
#define USE_FIXED_OVERFLOW_CHECKS
#endif

#if MSC_VERSION
// i32*i32 -> i64 multiply: MSVC x86 doesn't optimise i64 multiplies automatically, so use the intrinsic
#include <intrin.h>
#define MUL_I64_I32_I32(a, b)\
    (__emul((a), (b)))
#define SQUARE_U64_FIXED(a)\
    static_cast<u64>(__emul((a).GetInternalValue(), (a).GetInternalValue()))
#else
#define MUL_I64_I32_I32(a, b)\
    static_cast<i64>(a) * static_cast<i64>(b)
#define SQUARE_U64_FIXED(a)\
    static_cast<u64>(static_cast<i64>((a).GetInternalValue()) * static_cast<i64>((a).GetInternalValue()))
#endif

//define overflow macros
#ifndef USE_FIXED_OVERFLOW_CHECKS

#define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning)
#define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning)
#define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning)
#define CheckU32CastOverflow(var, targetType, overflowWarning)
#define CheckUnsignedAdditionOverflow(result, operand, overflowWarning)
#define CheckUnsignedSubtractionOverflow(result, operand, overflowWarning)
#define CheckNegationOverflow(var, type, overflowWarning)
#define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning)
#define CheckDivisionOverflow(type, left, right, overflowWarning)

#else // USE_FIXED_OVERFLOW_CHECKS

#define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning) \
    if(left > 0 && right < 0 && left > std::numeric_limits<type>::max() + right) \
        debug_warn(overflowWarning); \
    else if(left < 0 && right > 0 && left < std::numeric_limits<type>::min() + right) \
        debug_warn(underflowWarning);

#define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning) \
    if(left > 0 && right > 0 && std::numeric_limits<type>::max() - left < right) \
        debug_warn(overflowWarning); \
    else if(left < 0 && right < 0 && std::numeric_limits<type>::min() - left > right) \
        debug_warn(underflowWarning);

#define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning) \
    if(var > std::numeric_limits<targetType>::max()) \
        debug_warn(overflowWarning); \
    else if(var < std::numeric_limits<targetType>::min()) \
        debug_warn(underflowWarning);

#define CheckU32CastOverflow(var, targetType, overflowWarning) \
    if(var > (u32)std::numeric_limits<targetType>::max()) \
        debug_warn(overflowWarning);

#define CheckUnsignedAdditionOverflow(result, operand, overflowWarning) \
    if(result < operand) \
        debug_warn(overflowWarning);

#define CheckUnsignedSubtractionOverflow(result, left, overflowWarning) \
    if(result > left) \
        debug_warn(overflowWarning);

#define CheckNegationOverflow(var, type, overflowWarning) \
    if(value == std::numeric_limits<type>::min()) \
        debug_warn(overflowWarning);

#define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning) \
    i64 res##left = (i64)left * (i64)right; \
    CheckCastOverflow(res##left, type, overflowWarning, underflowWarning)

#define CheckDivisionOverflow(type, left, right, overflowWarning) \
    if(right == -1) { CheckNegationOverflow(left, type, overflowWarning) }

#endif // USE_FIXED_OVERFLOW_CHECKS

template <typename T>
inline T round_away_from_zero(float value)
{
    return (T)(value >= 0 ? value + 0.5f : value - 0.5f);
}

template <typename T>
inline T round_away_from_zero(double value)
{
    return (T)(value >= 0 ? value + 0.5 : value - 0.5);
}

/**
 * A simple fixed-point number class.
 *
 * Use 'fixed' rather than using this class directly.
 */
template<typename T, T max_t, int total_bits, int int_bits, int fract_bits_, int fract_pow2>
class CFixed
{
private:
    T value;

    constexpr explicit CFixed(T v) : value(v) { }

public:
    enum { fract_bits = fract_bits_ };

    CFixed() : value(0) { }

    static CFixed Zero() { return CFixed(0); }
    static CFixed Epsilon() { return CFixed(1); }
    static CFixed Pi();

    T GetInternalValue() const { return value; }
    void SetInternalValue(T n) { value = n; }

    // Conversion to/from primitive types:

    static constexpr CFixed FromInt(int n)
    {
        return CFixed(n << fract_bits);
    }

    // TODO C++20: this won't be necessary when operator/(int) can be made constexpr.
    static constexpr CFixed FromFraction(int n, int d)
    {
        return CFixed(static_cast<int>(static_cast<unsigned int>(n) << fract_bits) / d);
    }

    static constexpr CFixed FromFloat(float n)
    {
        if (!std::isfinite(n))
            return CFixed(0);
        float scaled = n * fract_pow2;
        return CFixed(round_away_from_zero<T>(scaled));
    }

    static constexpr CFixed FromDouble(double n)
    {
        if (!std::isfinite(n))
            return CFixed(0);
        double scaled = n * fract_pow2;
        return CFixed(round_away_from_zero<T>(scaled));
    }

    static CFixed FromString(const CStr8& s);
    static CFixed FromString(const CStrW& s);

    /// Convert to float. May be lossy - float can't represent all values.
    float ToFloat() const
    {
        return (float)value / (float)fract_pow2;
    }

    /// Convert to double. Won't be lossy - double can precisely represent all values.
    double ToDouble() const
    {
        return value / (double)fract_pow2;
    }

    constexpr int ToInt_RoundToZero() const
    {
        if (value > 0)
            return value >> fract_bits;
        else
            return (value + fract_pow2 - 1) >> fract_bits;
    }

    constexpr int ToInt_RoundToInfinity() const
    {
        return (value + fract_pow2 - 1) >> fract_bits;
    }

    constexpr int ToInt_RoundToNegInfinity() const
    {
        return value >> fract_bits;
    }

    constexpr int ToInt_RoundToNearest() const // (ties to infinity)
    {
        return (value + fract_pow2/2) >> fract_bits;
    }

    /// Returns the shortest string such that FromString will parse to the correct value.
    CStr8 ToString() const;

    /// Returns true if the number is precisely 0.
    constexpr bool IsZero() const { return value == 0; }

    /// Equality.
    constexpr bool operator==(CFixed n) const { return (value == n.value); }

    /// Inequality.
    constexpr bool operator!=(CFixed n) const { return (value != n.value); }

    /// Numeric comparison.
    constexpr bool operator<=(CFixed n) const { return (value <= n.value); }

    /// Numeric comparison.
    constexpr bool operator<(CFixed n) const { return (value < n.value); }

    /// Numeric comparison.
    constexpr bool operator>=(CFixed n) const { return (value >= n.value); }

    /// Numeric comparison.
    constexpr bool operator>(CFixed n) const { return (value > n.value); }

    // Basic arithmetic:

    /// Add a CFixed. Might overflow.
    CFixed operator+(CFixed n) const
    {
        CheckSignedAdditionOverflow(T, value, n.value, L"Overflow in CFixed::operator+(CFixed n)", L"Underflow in CFixed::operator+(CFixed n)")
        return CFixed(value + n.value);
    }

    /// Subtract a CFixed. Might overflow.
    CFixed operator-(CFixed n) const
    {
        CheckSignedSubtractionOverflow(T, value, n.value, L"Overflow in CFixed::operator-(CFixed n)", L"Underflow in CFixed::operator-(CFixed n)")
        return CFixed(value - n.value);
    }

    /// Add a CFixed. Might overflow.
    constexpr CFixed& operator+=(CFixed n) { *this = *this + n; return *this; }

    /// Subtract a CFixed. Might overflow.
    constexpr CFixed& operator-=(CFixed n) { *this = *this - n; return *this; }

    /// Negate a CFixed.
    CFixed operator-() const
    {
        CheckNegationOverflow(value, T, L"Overflow in CFixed::operator-()")
        return CFixed(-value);
    }

    CFixed operator>>(int n) const
    {
        ASSERT(n >= 0 && n < 32);
        return CFixed(value >> n);
    }

    CFixed operator<<(int n) const
    {
        ASSERT(n >= 0 && n < 32);
        // TODO: check for overflow
        return CFixed(value << n);
    }

    /// Divide by a CFixed. Must not have n.IsZero(). Might overflow.
    CFixed operator/(CFixed n) const
    {
        i64 t = (i64)value << fract_bits;
        i64 result = t / (i64)n.value;

        CheckCastOverflow(result, T, L"Overflow in CFixed::operator/(CFixed n)", L"Underflow in CFixed::operator/(CFixed n)")
        return CFixed((T)result);
    }

    /// Multiply by an integer. Might overflow.
    CFixed operator*(int n) const
    {
        CheckMultiplicationOverflow(T, value, n, L"Overflow in CFixed::operator*(int n)", L"Underflow in CFixed::operator*(int n)")
        return CFixed(value * n);
    }

    /// Multiply by an integer. Avoids overflow by clamping to min/max representable value.
    constexpr CFixed MultiplyClamp(int n) const
    {
        i64 t = (i64)value * n;
        t = std::max((i64)std::numeric_limits<T>::min(), std::min((i64)std::numeric_limits<T>::max(), t));
        return CFixed((i32)t);
    }

    /// Divide by an integer. Must not have n == 0. Cannot overflow unless n == -1.
    CFixed operator/(int n) const
    {
        CheckDivisionOverflow(T, value, n, L"Overflow in CFixed::operator/(int n)")
        return CFixed(value / n);
    }

    /// Mod by a fixed. Must not have n == 0. Result has the same sign as n.
    constexpr CFixed operator%(CFixed n) const
    {
        T t = value % n.value;
        if (n.value > 0 && t < 0)
            t += n.value;
        else if (n.value < 0 && t > 0)
            t += n.value;

        return CFixed(t);
    }

    constexpr CFixed Absolute() const { return CFixed(abs(value)); }

    /**
     * Multiply by a CFixed. Likely to overflow if both numbers are large,
     * so we use an ugly name instead of operator* to make it obvious.
     */
    CFixed Multiply(CFixed n) const
    {
        i64 t = MUL_I64_I32_I32(value, n.value);
        t >>= fract_bits;

        CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
        return CFixed((T)t);
    }

    /**
     * Multiply the value by itself. Might overflow.
     */
    constexpr CFixed Square() const
    {
        return (*this).Multiply(*this);
    }

    /**
     * Compute this*m/d. Must not have d == 0. Won't overflow if the result can be represented as a CFixed.
     */
    CFixed MulDiv(CFixed m, CFixed d) const
    {
        i64 t = MUL_I64_I32_I32(value, m.value) / static_cast<i64>(d.value);
        CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
        return CFixed((T)t);
    }

    constexpr CFixed Sqrt() const
    {
        if (value <= 0)
            return CFixed(0);
        u32 s = isqrt64((u64)value << fract_bits);
        return CFixed(s);
    }

private:
    // Prevent dangerous accidental implicit conversions of floats to ints in certain operations
    CFixed operator*(float n) const;
    CFixed operator/(float n) const;
};

/**
 * A fixed-point number class with 1-bit sign, 15-bit integral part, 16-bit fractional part.
 */
typedef CFixed<i32, (i32)0x7fffffff, 32, 15, 16, 65536> CFixed_15_16;

/**
 * Default fixed-point type used by the engine.
 */
typedef CFixed_15_16 fixed;

namespace std
{
/**
 * std::numeric_limits specialisation, currently just providing min and max
 */
template<typename T, T max_t, int total_bits, int int_bits, int fract_bits_, int fract_pow2>
struct numeric_limits<CFixed<T, max_t, total_bits, int_bits, fract_bits_, fract_pow2> >
{
    typedef CFixed<T, max_t, total_bits, int_bits, fract_bits_, fract_pow2> fixed;
public:
    static const bool is_specialized = true;
    static fixed min() throw() { fixed f; f.SetInternalValue(std::numeric_limits<T>::min()); return f; }
    static fixed max() throw() { fixed f; f.SetInternalValue(std::numeric_limits<T>::max()); return f; }
};
}

/**
 * Inaccurate approximation of atan2 over fixed-point numbers.
 * Maximum error is almost 0.08 radians (4.5 degrees).
 */
CFixed_15_16 atan2_approx(CFixed_15_16 y, CFixed_15_16 x);

/**
 * Compute sin(a) and cos(a).
 * Maximum error for -2pi < a < 2pi is almost 0.0005.
 */
void sincos_approx(CFixed_15_16 a, CFixed_15_16& sin_out, CFixed_15_16& cos_out);

#endif // INCLUDED_FIXED