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
|
