Pyrogenesis HEAD
Pyrogenesis, a RTS Engine
Fixed.h
Go to the documentation of this file.
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
101template <typename T>
102inline T round_away_from_zero(float value)
103{
104 return (T)(value >= 0 ? value + 0.5f : value - 0.5f);
105}
106
107template <typename T>
108inline 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 */
118template<typename T, T max_t, int total_bits, int int_bits, int fract_bits_, int fract_pow2>
120{
121private:
123
124 constexpr explicit CFixed(T v) : value(v) { }
125
126public:
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.
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.
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.
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.
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 */
322 {
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 */
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
356private:
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 */
365typedef CFixed<i32, (i32)0x7fffffff, 32, 15, 16, 65536> CFixed_15_16;
366
367/**
368 * Default fixed-point type used by the engine.
369 */
371
372namespace std
373{
374/**
375 * std::numeric_limits specialisation, currently just providing min and max
376 */
377template<typename T, T max_t, int total_bits, int int_bits, int fract_bits_, int fract_pow2>
378struct numeric_limits<CFixed<T, max_t, total_bits, int_bits, fract_bits_, fract_pow2> >
379{
381public:
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 */
393
394/**
395 * Compute sin(a) and cos(a).
396 * Maximum error for -2pi < a < 2pi is almost 0.0005.
397 */
398void sincos_approx(CFixed_15_16 a, CFixed_15_16& sin_out, CFixed_15_16& cos_out);
399
400#endif // INCLUDED_FIXED
#define MUL_I64_I32_I32(a, b)
Definition: Fixed.h:37
#define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning)
Definition: Fixed.h:70
T round_away_from_zero(float value)
Definition: Fixed.h:102
CFixed_15_16 atan2_approx(CFixed_15_16 y, CFixed_15_16 x)
Inaccurate approximation of atan2 over fixed-point numbers.
Definition: Fixed.cpp:147
#define CheckNegationOverflow(var, type, overflowWarning)
Definition: Fixed.h:88
#define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning)
Definition: Fixed.h:64
void sincos_approx(CFixed_15_16 a, CFixed_15_16 &sin_out, CFixed_15_16 &cos_out)
Compute sin(a) and cos(a).
Definition: Fixed.cpp:187
#define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning)
Definition: Fixed.h:58
CFixed_15_16 fixed
Default fixed-point type used by the engine.
Definition: Fixed.h:370
#define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning)
Definition: Fixed.h:92
#define CheckDivisionOverflow(type, left, right, overflowWarning)
Definition: Fixed.h:96
u32 isqrt64(u64 n)
64-bit integer square root.
Definition: Sqrt.cpp:23
A simple fixed-point number class.
Definition: Fixed.h:120
CFixed operator-(CFixed n) const
Subtract a CFixed. Might overflow.
Definition: Fixed.h:239
void SetInternalValue(T n)
Definition: Fixed.h:136
static constexpr CFixed FromFraction(int n, int d)
Definition: Fixed.h:146
double ToDouble() const
Convert to double. Won't be lossy - double can precisely represent all values.
Definition: Fixed.h:177
constexpr CFixed Absolute() const
Definition: Fixed.h:315
CStr8 ToString() const
Returns the shortest string such that FromString will parse to the correct value.
Definition: Fixed.cpp:96
constexpr CFixed MultiplyClamp(int n) const
Multiply by an integer. Avoids overflow by clamping to min/max representable value.
Definition: Fixed.h:289
CFixed operator/(int n) const
Divide by an integer. Must not have n == 0. Cannot overflow unless n == -1.
Definition: Fixed.h:297
static CFixed Zero()
Definition: Fixed.h:131
constexpr bool operator<(CFixed n) const
Numeric comparison.
Definition: Fixed.h:221
float ToFloat() const
Convert to float. May be lossy - float can't represent all values.
Definition: Fixed.h:171
static constexpr CFixed FromFloat(float n)
Definition: Fixed.h:151
CFixed()
Definition: Fixed.h:129
constexpr CFixed(T v)
Definition: Fixed.h:124
constexpr CFixed & operator+=(CFixed n)
Add a CFixed. Might overflow.
Definition: Fixed.h:246
constexpr bool operator==(CFixed n) const
Equality.
Definition: Fixed.h:212
constexpr bool operator<=(CFixed n) const
Numeric comparison.
Definition: Fixed.h:218
constexpr CFixed Square() const
Multiply the value by itself.
Definition: Fixed.h:333
constexpr CFixed & operator-=(CFixed n)
Subtract a CFixed. Might overflow.
Definition: Fixed.h:249
constexpr int ToInt_RoundToInfinity() const
Definition: Fixed.h:190
CFixed Multiply(CFixed n) const
Multiply by a CFixed.
Definition: Fixed.h:321
CFixed operator<<(int n) const
Definition: Fixed.h:264
constexpr CFixed Sqrt() const
Definition: Fixed.h:348
constexpr int ToInt_RoundToNearest() const
Definition: Fixed.h:200
CFixed operator-() const
Negate a CFixed.
Definition: Fixed.h:252
CFixed operator/(float n) const
CFixed MulDiv(CFixed m, CFixed d) const
Compute this*m/d.
Definition: Fixed.h:341
constexpr int ToInt_RoundToNegInfinity() const
Definition: Fixed.h:195
constexpr bool operator>=(CFixed n) const
Numeric comparison.
Definition: Fixed.h:224
constexpr bool operator!=(CFixed n) const
Inequality.
Definition: Fixed.h:215
CFixed operator+(CFixed n) const
Add a CFixed. Might overflow.
Definition: Fixed.h:232
CFixed operator/(CFixed n) const
Divide by a CFixed. Must not have n.IsZero(). Might overflow.
Definition: Fixed.h:272
constexpr bool IsZero() const
Returns true if the number is precisely 0.
Definition: Fixed.h:209
T GetInternalValue() const
Definition: Fixed.h:135
static constexpr CFixed FromDouble(double n)
Definition: Fixed.h:159
constexpr CFixed operator%(CFixed n) const
Mod by a fixed. Must not have n == 0. Result has the same sign as n.
Definition: Fixed.h:304
constexpr int ToInt_RoundToZero() const
Definition: Fixed.h:182
@ fract_bits
Definition: Fixed.h:127
T value
Definition: Fixed.h:122
CFixed operator*(float n) const
static constexpr CFixed FromInt(int n)
Definition: Fixed.h:140
constexpr bool operator>(CFixed n) const
Numeric comparison.
Definition: Fixed.h:227
static CFixed Epsilon()
Definition: Fixed.h:132
static CFixed FromString(const CStr8 &s)
Definition: Fixed.cpp:27
CFixed operator*(int n) const
Multiply by an integer. Might overflow.
Definition: Fixed.h:282
static CFixed Pi()
Definition: Fixed.cpp:182
CFixed operator>>(int n) const
Definition: Fixed.h:258
#define ASSERT(expr)
same as ENSURE in debug mode, does nothing in release mode.
Definition: debug.h:305
Definition: ShaderDefines.cpp:31
#define T(string_literal)
Definition: secure_crt.cpp:77
CFixed< T, max_t, total_bits, int_bits, fract_bits_, fract_pow2 > fixed
Definition: Fixed.h:380
uint64_t u64
Definition: types.h:40
int32_t i32
Definition: types.h:34
int64_t i64
Definition: types.h:35
uint32_t u32
Definition: types.h:39