LCOV - code coverage report
Current view: top level - source/maths - Fixed.h (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 95 100 95.0 %
Date: 2023-01-19 00:18:29 Functions: 41 44 93.2 %

          Line data    Source code
       1             : /* Copyright (C) 2022 Wildfire Games.
       2             :  * This file is part of 0 A.D.
       3             :  *
       4             :  * 0 A.D. is free software: you can redistribute it and/or modify
       5             :  * it under the terms of the GNU General Public License as published by
       6             :  * the Free Software Foundation, either version 2 of the License, or
       7             :  * (at your option) any later version.
       8             :  *
       9             :  * 0 A.D. is distributed in the hope that it will be useful,
      10             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12             :  * GNU General Public License for more details.
      13             :  *
      14             :  * You should have received a copy of the GNU General Public License
      15             :  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
      16             :  */
      17             : 
      18             : #ifndef INCLUDED_FIXED
      19             : #define INCLUDED_FIXED
      20             : 
      21             : #include "lib/types.h"
      22             : #include "maths/Sqrt.h"
      23             : #include "ps/CStrForward.h"
      24             : 
      25             : #ifndef NDEBUG
      26             : #define USE_FIXED_OVERFLOW_CHECKS
      27             : #endif
      28             : 
      29             : #if MSC_VERSION
      30             : // i32*i32 -> i64 multiply: MSVC x86 doesn't optimise i64 multiplies automatically, so use the intrinsic
      31             : #include <intrin.h>
      32             : #define MUL_I64_I32_I32(a, b)\
      33             :     (__emul((a), (b)))
      34             : #define SQUARE_U64_FIXED(a)\
      35             :     static_cast<u64>(__emul((a).GetInternalValue(), (a).GetInternalValue()))
      36             : #else
      37             : #define MUL_I64_I32_I32(a, b)\
      38             :     static_cast<i64>(a) * static_cast<i64>(b)
      39             : #define SQUARE_U64_FIXED(a)\
      40             :     static_cast<u64>(static_cast<i64>((a).GetInternalValue()) * static_cast<i64>((a).GetInternalValue()))
      41             : #endif
      42             : 
      43             : //define overflow macros
      44             : #ifndef USE_FIXED_OVERFLOW_CHECKS
      45             : 
      46             : #define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning)
      47             : #define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning)
      48             : #define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning)
      49             : #define CheckU32CastOverflow(var, targetType, overflowWarning)
      50             : #define CheckUnsignedAdditionOverflow(result, operand, overflowWarning)
      51             : #define CheckUnsignedSubtractionOverflow(result, operand, overflowWarning)
      52             : #define CheckNegationOverflow(var, type, overflowWarning)
      53             : #define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning)
      54             : #define CheckDivisionOverflow(type, left, right, overflowWarning)
      55             : 
      56             : #else // USE_FIXED_OVERFLOW_CHECKS
      57             : 
      58             : #define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning) \
      59             :     if(left > 0 && right < 0 && left > std::numeric_limits<type>::max() + right) \
      60             :         debug_warn(overflowWarning); \
      61             :     else if(left < 0 && right > 0 && left < std::numeric_limits<type>::min() + right) \
      62             :         debug_warn(underflowWarning);
      63             : 
      64             : #define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning) \
      65             :     if(left > 0 && right > 0 && std::numeric_limits<type>::max() - left < right) \
      66             :         debug_warn(overflowWarning); \
      67             :     else if(left < 0 && right < 0 && std::numeric_limits<type>::min() - left > right) \
      68             :         debug_warn(underflowWarning);
      69             : 
      70             : #define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning) \
      71             :     if(var > std::numeric_limits<targetType>::max()) \
      72             :         debug_warn(overflowWarning); \
      73             :     else if(var < std::numeric_limits<targetType>::min()) \
      74             :         debug_warn(underflowWarning);
      75             : 
      76             : #define CheckU32CastOverflow(var, targetType, overflowWarning) \
      77             :     if(var > (u32)std::numeric_limits<targetType>::max()) \
      78             :         debug_warn(overflowWarning);
      79             : 
      80             : #define CheckUnsignedAdditionOverflow(result, operand, overflowWarning) \
      81             :     if(result < operand) \
      82             :         debug_warn(overflowWarning);
      83             : 
      84             : #define CheckUnsignedSubtractionOverflow(result, left, overflowWarning) \
      85             :     if(result > left) \
      86             :         debug_warn(overflowWarning);
      87             : 
      88             : #define CheckNegationOverflow(var, type, overflowWarning) \
      89             :     if(value == std::numeric_limits<type>::min()) \
      90             :         debug_warn(overflowWarning);
      91             : 
      92             : #define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning) \
      93             :     i64 res##left = (i64)left * (i64)right; \
      94             :     CheckCastOverflow(res##left, type, overflowWarning, underflowWarning)
      95             : 
      96             : #define CheckDivisionOverflow(type, left, right, overflowWarning) \
      97             :     if(right == -1) { CheckNegationOverflow(left, type, overflowWarning) }
      98             : 
      99             : #endif // USE_FIXED_OVERFLOW_CHECKS
     100             : 
     101             : template <typename T>
     102      130195 : inline T round_away_from_zero(float value)
     103             : {
     104      130195 :     return (T)(value >= 0 ? value + 0.5f : value - 0.5f);
     105             : }
     106             : 
     107             : template <typename T>
     108       80643 : inline T round_away_from_zero(double value)
     109             : {
     110       80643 :     return (T)(value >= 0 ? value + 0.5 : value - 0.5);
     111             : }
     112             : 
     113             : /**
     114             :  * A simple fixed-point number class.
     115             :  *
     116             :  * Use 'fixed' rather than using this class directly.
     117             :  */
     118             : template<typename T, T max_t, int total_bits, int int_bits, int fract_bits_, int fract_pow2>
     119             : class CFixed
     120             : {
     121             : private:
     122             :     T value;
     123             : 
     124     5147977 :     constexpr explicit CFixed(T v) : value(v) { }
     125             : 
     126             : public:
     127             :     enum { fract_bits = fract_bits_ };
     128             : 
     129      106523 :     CFixed() : value(0) { }
     130             : 
     131      133514 :     static CFixed Zero() { return CFixed(0); }
     132        6244 :     static CFixed Epsilon() { return CFixed(1); }
     133             :     static CFixed Pi();
     134             : 
     135       13916 :     T GetInternalValue() const { return value; }
     136       13847 :     void SetInternalValue(T n) { value = n; }
     137             : 
     138             :     // Conversion to/from primitive types:
     139             : 
     140      956018 :     static constexpr CFixed FromInt(int n)
     141             :     {
     142      956018 :         return CFixed(n << fract_bits);
     143             :     }
     144             : 
     145             :     // TODO C++20: this won't be necessary when operator/(int) can be made constexpr.
     146           4 :     static constexpr CFixed FromFraction(int n, int d)
     147             :     {
     148           8 :         return CFixed(static_cast<int>(static_cast<unsigned int>(n) << fract_bits) / d);
     149             :     }
     150             : 
     151      130198 :     static constexpr CFixed FromFloat(float n)
     152             :     {
     153      130198 :         if (!std::isfinite(n))
     154           3 :             return CFixed(0);
     155      130195 :         float scaled = n * fract_pow2;
     156      130195 :         return CFixed(round_away_from_zero<T>(scaled));
     157             :     }
     158             : 
     159       80646 :     static constexpr CFixed FromDouble(double n)
     160             :     {
     161       80646 :         if (!std::isfinite(n))
     162           3 :             return CFixed(0);
     163       80643 :         double scaled = n * fract_pow2;
     164       80643 :         return CFixed(round_away_from_zero<T>(scaled));
     165             :     }
     166             : 
     167             :     static CFixed FromString(const CStr8& s);
     168             :     static CFixed FromString(const CStrW& s);
     169             : 
     170             :     /// Convert to float. May be lossy - float can't represent all values.
     171         312 :     float ToFloat() const
     172             :     {
     173         312 :         return (float)value / (float)fract_pow2;
     174             :     }
     175             : 
     176             :     /// Convert to double. Won't be lossy - double can precisely represent all values.
     177       90567 :     double ToDouble() const
     178             :     {
     179       90567 :         return value / (double)fract_pow2;
     180             :     }
     181             : 
     182      148744 :     constexpr int ToInt_RoundToZero() const
     183             :     {
     184      148744 :         if (value > 0)
     185      148210 :             return value >> fract_bits;
     186             :         else
     187         534 :             return (value + fract_pow2 - 1) >> fract_bits;
     188             :     }
     189             : 
     190        6641 :     constexpr int ToInt_RoundToInfinity() const
     191             :     {
     192        6641 :         return (value + fract_pow2 - 1) >> fract_bits;
     193             :     }
     194             : 
     195        6647 :     constexpr int ToInt_RoundToNegInfinity() const
     196             :     {
     197        6647 :         return value >> fract_bits;
     198             :     }
     199             : 
     200          14 :     constexpr int ToInt_RoundToNearest() const // (ties to infinity)
     201             :     {
     202          14 :         return (value + fract_pow2/2) >> fract_bits;
     203             :     }
     204             : 
     205             :     /// Returns the shortest string such that FromString will parse to the correct value.
     206             :     CStr8 ToString() const;
     207             : 
     208             :     /// Returns true if the number is precisely 0.
     209        5561 :     constexpr bool IsZero() const { return value == 0; }
     210             : 
     211             :     /// Equality.
     212       65753 :     constexpr bool operator==(CFixed n) const { return (value == n.value); }
     213             : 
     214             :     /// Inequality.
     215          94 :     constexpr bool operator!=(CFixed n) const { return (value != n.value); }
     216             : 
     217             :     /// Numeric comparison.
     218      420465 :     constexpr bool operator<=(CFixed n) const { return (value <= n.value); }
     219             : 
     220             :     /// Numeric comparison.
     221         800 :     constexpr bool operator<(CFixed n) const { return (value < n.value); }
     222             : 
     223             :     /// Numeric comparison.
     224      161632 :     constexpr bool operator>=(CFixed n) const { return (value >= n.value); }
     225             : 
     226             :     /// Numeric comparison.
     227      260975 :     constexpr bool operator>(CFixed n) const { return (value > n.value); }
     228             : 
     229             :     // Basic arithmetic:
     230             : 
     231             :     /// Add a CFixed. Might overflow.
     232      885096 :     CFixed operator+(CFixed n) const
     233             :     {
     234      885096 :         CheckSignedAdditionOverflow(T, value, n.value, L"Overflow in CFixed::operator+(CFixed n)", L"Underflow in CFixed::operator+(CFixed n)")
     235      885096 :         return CFixed(value + n.value);
     236             :     }
     237             : 
     238             :     /// Subtract a CFixed. Might overflow.
     239     1039702 :     CFixed operator-(CFixed n) const
     240             :     {
     241     1039702 :         CheckSignedSubtractionOverflow(T, value, n.value, L"Overflow in CFixed::operator-(CFixed n)", L"Underflow in CFixed::operator-(CFixed n)")
     242     1039702 :         return CFixed(value - n.value);
     243             :     }
     244             : 
     245             :     /// Add a CFixed. Might overflow.
     246      131432 :     constexpr CFixed& operator+=(CFixed n) { *this = *this + n; return *this; }
     247             : 
     248             :     /// Subtract a CFixed. Might overflow.
     249           0 :     constexpr CFixed& operator-=(CFixed n) { *this = *this - n; return *this; }
     250             : 
     251             :     /// Negate a CFixed.
     252         287 :     CFixed operator-() const
     253             :     {
     254         287 :         CheckNegationOverflow(value, T, L"Overflow in CFixed::operator-()")
     255         287 :         return CFixed(-value);
     256             :     }
     257             : 
     258          13 :     CFixed operator>>(int n) const
     259             :     {
     260          13 :         ASSERT(n >= 0 && n < 32);
     261          13 :         return CFixed(value >> n);
     262             :     }
     263             : 
     264             :     CFixed operator<<(int n) const
     265             :     {
     266             :         ASSERT(n >= 0 && n < 32);
     267             :         // TODO: check for overflow
     268             :         return CFixed(value << n);
     269             :     }
     270             : 
     271             :     /// Divide by a CFixed. Must not have n.IsZero(). Might overflow.
     272         896 :     CFixed operator/(CFixed n) const
     273             :     {
     274         896 :         i64 t = (i64)value << fract_bits;
     275         896 :         i64 result = t / (i64)n.value;
     276             : 
     277         896 :         CheckCastOverflow(result, T, L"Overflow in CFixed::operator/(CFixed n)", L"Underflow in CFixed::operator/(CFixed n)")
     278         896 :         return CFixed((T)result);
     279             :     }
     280             : 
     281             :     /// Multiply by an integer. Might overflow.
     282      351303 :     CFixed operator*(int n) const
     283             :     {
     284      351303 :         CheckMultiplicationOverflow(T, value, n, L"Overflow in CFixed::operator*(int n)", L"Underflow in CFixed::operator*(int n)")
     285      351303 :         return CFixed(value * n);
     286             :     }
     287             : 
     288             :     /// Multiply by an integer. Avoids overflow by clamping to min/max representable value.
     289           0 :     constexpr CFixed MultiplyClamp(int n) const
     290             :     {
     291           0 :         i64 t = (i64)value * n;
     292           0 :         t = std::max((i64)std::numeric_limits<T>::min(), std::min((i64)std::numeric_limits<T>::max(), t));
     293           0 :         return CFixed((i32)t);
     294             :     }
     295             : 
     296             :     /// Divide by an integer. Must not have n == 0. Cannot overflow unless n == -1.
     297      514903 :     CFixed operator/(int n) const
     298             :     {
     299      514903 :         CheckDivisionOverflow(T, value, n, L"Overflow in CFixed::operator/(int n)")
     300      514903 :         return CFixed(value / n);
     301             :     }
     302             : 
     303             :     /// Mod by a fixed. Must not have n == 0. Result has the same sign as n.
     304       12602 :     constexpr CFixed operator%(CFixed n) const
     305             :     {
     306       12602 :         T t = value % n.value;
     307       12602 :         if (n.value > 0 && t < 0)
     308        6282 :             t += n.value;
     309        6320 :         else if (n.value < 0 && t > 0)
     310           1 :             t += n.value;
     311             : 
     312       12602 :         return CFixed(t);
     313             :     }
     314             : 
     315         634 :     constexpr CFixed Absolute() const { return CFixed(abs(value)); }
     316             : 
     317             :     /**
     318             :      * Multiply by a CFixed. Likely to overflow if both numbers are large,
     319             :      * so we use an ugly name instead of operator* to make it obvious.
     320             :      */
     321      894740 :     CFixed Multiply(CFixed n) const
     322             :     {
     323      894740 :         i64 t = MUL_I64_I32_I32(value, n.value);
     324      894740 :         t >>= fract_bits;
     325             : 
     326      894740 :         CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
     327      894740 :         return CFixed((T)t);
     328             :     }
     329             : 
     330             :     /**
     331             :      * Multiply the value by itself. Might overflow.
     332             :      */
     333      647810 :     constexpr CFixed Square() const
     334             :     {
     335      647810 :         return (*this).Multiply(*this);
     336             :     }
     337             : 
     338             :     /**
     339             :      * Compute this*m/d. Must not have d == 0. Won't overflow if the result can be represented as a CFixed.
     340             :      */
     341          34 :     CFixed MulDiv(CFixed m, CFixed d) const
     342             :     {
     343          34 :         i64 t = MUL_I64_I32_I32(value, m.value) / static_cast<i64>(d.value);
     344          34 :         CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
     345          34 :         return CFixed((T)t);
     346             :     }
     347             : 
     348           6 :     constexpr CFixed Sqrt() const
     349             :     {
     350           6 :         if (value <= 0)
     351           2 :             return CFixed(0);
     352           4 :         u32 s = isqrt64((u64)value << fract_bits);
     353           4 :         return CFixed(s);
     354             :     }
     355             : 
     356             : private:
     357             :     // Prevent dangerous accidental implicit conversions of floats to ints in certain operations
     358             :     CFixed operator*(float n) const;
     359             :     CFixed operator/(float n) const;
     360             : };
     361             : 
     362             : /**
     363             :  * A fixed-point number class with 1-bit sign, 15-bit integral part, 16-bit fractional part.
     364             :  */
     365             : typedef CFixed<i32, (i32)0x7fffffff, 32, 15, 16, 65536> CFixed_15_16;
     366             : 
     367             : /**
     368             :  * Default fixed-point type used by the engine.
     369             :  */
     370             : typedef CFixed_15_16 fixed;
     371             : 
     372             : namespace std
     373             : {
     374             : /**
     375             :  * std::numeric_limits specialisation, currently just providing min and max
     376             :  */
     377             : template<typename T, T max_t, int total_bits, int int_bits, int fract_bits_, int fract_pow2>
     378             : struct numeric_limits<CFixed<T, max_t, total_bits, int_bits, fract_bits_, fract_pow2> >
     379             : {
     380             :     typedef CFixed<T, max_t, total_bits, int_bits, fract_bits_, fract_pow2> fixed;
     381             : public:
     382             :     static const bool is_specialized = true;
     383          24 :     static fixed min() throw() { fixed f; f.SetInternalValue(std::numeric_limits<T>::min()); return f; }
     384          27 :     static fixed max() throw() { fixed f; f.SetInternalValue(std::numeric_limits<T>::max()); return f; }
     385             : };
     386             : }
     387             : 
     388             : /**
     389             :  * Inaccurate approximation of atan2 over fixed-point numbers.
     390             :  * Maximum error is almost 0.08 radians (4.5 degrees).
     391             :  */
     392             : CFixed_15_16 atan2_approx(CFixed_15_16 y, CFixed_15_16 x);
     393             : 
     394             : /**
     395             :  * Compute sin(a) and cos(a).
     396             :  * Maximum error for -2pi < a < 2pi is almost 0.0005.
     397             :  */
     398             : void sincos_approx(CFixed_15_16 a, CFixed_15_16& sin_out, CFixed_15_16& cos_out);
     399             : 
     400             : #endif // INCLUDED_FIXED

Generated by: LCOV version 1.13