source/maths/Fixed.h

   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 inline T round_away_from_zero(float value)
 103 {
 104         return (T)(value >= 0 ? value + 0.5f : value - 0.5f);
 105 }
 106
 107 template <typename T>
 108 inline T round_away_from_zero(double value)
 109 {
 110         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         constexpr explicit CFixed(T v) : value(v) { }
 125
 126 public:
 127         enum { fract_bits = fract_bits_ };
 128
 129         CFixed() : value(0) { }
 130
 131         static CFixed Zero() { return CFixed(0); }
 132         static CFixed Epsilon() { return CFixed(1); }
 133         static CFixed Pi();
 134
 135         T GetInternalValue() const { return value; }
 136         void SetInternalValue(T n) { value = n; }
 137
 138         // Conversion to/from primitive types:
 139
 140         static constexpr CFixed FromInt(int n)
 141         {
 142                 return CFixed(n << fract_bits);
 143         }
 144
 145         // TODO C++20: this won't be necessary when operator/(int) can be made constexpr.
 146         static constexpr CFixed FromFraction(int n, int d)
 147         {
 148                 return CFixed(static_cast<int>(static_cast<unsigned int>(n) << fract_bits) / d);
 149         }
 150
 151         static constexpr CFixed FromFloat(float n)
 152         {
 153                 if (!std::isfinite(n))
 154                         return CFixed(0);
 155                 float scaled = n * fract_pow2;
 156                 return CFixed(round_away_from_zero<T>(scaled));
 157         }
 158
 159         static constexpr CFixed FromDouble(double n)
 160         {
 161                 if (!std::isfinite(n))
 162                         return CFixed(0);
 163                 double scaled = n * fract_pow2;
 164                 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         float ToFloat() const
 172         {
 173                 return (float)value / (float)fract_pow2;
 174         }
 175
 176         /// Convert to double. Won't be lossy - double can precisely represent all values.
 177         double ToDouble() const
 178         {
 179                 return value / (double)fract_pow2;
 180         }
 181
 182         constexpr int ToInt_RoundToZero() const
 183         {
 184                 if (value > 0)
 185                         return value >> fract_bits;
 186                 else
 187                         return (value + fract_pow2 - 1) >> fract_bits;
 188         }
 189
 190         constexpr int ToInt_RoundToInfinity() const
 191         {
 192                 return (value + fract_pow2 - 1) >> fract_bits;
 193         }
 194
 195         constexpr int ToInt_RoundToNegInfinity() const
 196         {
 197                 return value >> fract_bits;
 198         }
 199
 200         constexpr int ToInt_RoundToNearest() const // (ties to infinity)
 201         {
 202                 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         constexpr bool IsZero() const { return value == 0; }
 210
 211         /// Equality.
 212         constexpr bool operator==(CFixed n) const { return (value == n.value); }
 213
 214         /// Inequality.
 215         constexpr bool operator!=(CFixed n) const { return (value != n.value); }
 216
 217         /// Numeric comparison.
 218         constexpr bool operator<=(CFixed n) const { return (value <= n.value); }
 219
 220         /// Numeric comparison.
 221         constexpr bool operator<(CFixed n) const { return (value < n.value); }
 222
 223         /// Numeric comparison.
 224         constexpr bool operator>=(CFixed n) const { return (value >= n.value); }
 225
 226         /// Numeric comparison.
 227         constexpr bool operator>(CFixed n) const { return (value > n.value); }
 228
 229         // Basic arithmetic:
 230
 231         /// Add a CFixed. Might overflow.
 232         CFixed operator+(CFixed n) const
 233         {
 234                 CheckSignedAdditionOverflow(T, value, n.value, L"Overflow in CFixed::operator+(CFixed n)", L"Underflow in CFixed::operator+(CFixed n)")
 235                 return CFixed(value + n.value);
 236         }
 237
 238         /// Subtract a CFixed. Might overflow.
 239         CFixed operator-(CFixed n) const
 240         {
 241                 CheckSignedSubtractionOverflow(T, value, n.value, L"Overflow in CFixed::operator-(CFixed n)", L"Underflow in CFixed::operator-(CFixed n)")
 242                 return CFixed(value - n.value);
 243         }
 244
 245         /// Add a CFixed. Might overflow.
 246         constexpr CFixed& operator+=(CFixed n) { *this = *this + n; return *this; }
 247
 248         /// Subtract a CFixed. Might overflow.
 249         constexpr CFixed& operator-=(CFixed n) { *this = *this - n; return *this; }
 250
 251         /// Negate a CFixed.
 252         CFixed operator-() const
 253         {
 254                 CheckNegationOverflow(value, T, L"Overflow in CFixed::operator-()")
 255                 return CFixed(-value);
 256         }
 257
 258         CFixed operator>>(int n) const
 259         {
 260                 ASSERT(n >= 0 && n < 32);
 261                 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         CFixed operator/(CFixed n) const
 273         {
 274                 i64 t = (i64)value << fract_bits;
 275                 i64 result = t / (i64)n.value;
 276
 277                 CheckCastOverflow(result, T, L"Overflow in CFixed::operator/(CFixed n)", L"Underflow in CFixed::operator/(CFixed n)")
 278                 return CFixed((T)result);
 279         }
 280
 281         /// Multiply by an integer. Might overflow.
 282         CFixed operator*(int n) const
 283         {
 284                 CheckMultiplicationOverflow(T, value, n, L"Overflow in CFixed::operator*(int n)", L"Underflow in CFixed::operator*(int n)")
 285                 return CFixed(value * n);
 286         }
 287
 288         /// Multiply by an integer. Avoids overflow by clamping to min/max representable value.
 289         constexpr CFixed MultiplyClamp(int n) const
 290         {
 291                 i64 t = (i64)value * n;
 292                 t = std::max((i64)std::numeric_limits<T>::min(), std::min((i64)std::numeric_limits<T>::max(), t));
 293                 return CFixed((i32)t);
 294         }
 295
 296         /// Divide by an integer. Must not have n == 0. Cannot overflow unless n == -1.
 297         CFixed operator/(int n) const
 298         {
 299                 CheckDivisionOverflow(T, value, n, L"Overflow in CFixed::operator/(int n)")
 300                 return CFixed(value / n);
 301         }
 302
 303         /// Mod by a fixed. Must not have n == 0. Result has the same sign as n.
 304         constexpr CFixed operator%(CFixed n) const
 305         {
 306                 T t = value % n.value;
 307                 if (n.value > 0 && t < 0)
 308                         t += n.value;
 309                 else if (n.value < 0 && t > 0)
 310                         t += n.value;
 311
 312                 return CFixed(t);
 313         }
 314
 315         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         CFixed Multiply(CFixed n) const
 322         {
 323                 i64 t = MUL_I64_I32_I32(value, n.value);
 324                 t >>= fract_bits;
 325
 326                 CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
 327                 return CFixed((T)t);
 328         }
 329
 330         /**
 331          * Multiply the value by itself. Might overflow.
 332          */
 333         constexpr CFixed Square() const
 334         {
 335                 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         CFixed MulDiv(CFixed m, CFixed d) const
 342         {
 343                 i64 t = MUL_I64_I32_I32(value, m.value) / static_cast<i64>(d.value);
 344                 CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
 345                 return CFixed((T)t);
 346         }
 347
 348         constexpr CFixed Sqrt() const
 349         {
 350                 if (value <= 0)
 351                         return CFixed(0);
 352                 u32 s = isqrt64((u64)value << fract_bits);
 353                 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         static fixed min() throw() { fixed f; f.SetInternalValue(std::numeric_limits<T>::min()); return f; }
 384         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