The Battle for Wesnoth  1.17.0-dev
math.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2021
3  by David White <dave@whitevine.net>
4  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY.
12 
13  See the COPYING file for more details.
14 */
15 
16 /**
17  * @file
18  * General math utility functions.
19  */
20 
21 #pragma once
22 
23 #include <cmath>
24 #include <cstddef>
25 #include <cstdint>
26 #include <cstdlib>
27 #include <limits>
28 #include <vector>
29 #include <algorithm>
30 #include <cassert>
31 
32 template<typename T>
33 inline bool is_even(T num) { return num % 2 == 0; }
34 
35 template<typename T>
36 inline bool is_odd(T num) { return !is_even(num); }
37 
38 /** Guarantees portable results for division by 100; round half up, to the nearest integer. */
39 inline int div100rounded(int num) {
40  return (num < 0) ? -(((-num) + 50) / 100) : (num + 50) / 100;
41 }
42 
43 /**
44  * Returns base + increment, but will not increase base above max_sum, nor
45  * decrease it below min_sum.
46  * (If base is already below the applicable limit, base will be returned.)
47  */
48 inline int bounded_add(int base, int increment, int max_sum, int min_sum = 0)
49 {
50  if(increment >= 0) {
51  return std::min(base + increment, std::max(base, max_sum));
52  } else {
53  return std::max(base + increment, std::min(base, min_sum));
54  }
55 }
56 
57 
58 /**
59  * @returns: the number n in [min, min+mod ) so that (n - num) is a multiple of mod.
60  */
61 template<typename T>
62 inline T modulo(T num, int mod, T min = 0)
63 {
64  assert(mod > 0);
65  T n = (num - min) % mod;
66  if (n < 0)
67  n += mod;
68  //n is now in [0, mod)
69  n = n + min;
70  return n;
71  // the following properties are easy to verify:
72  // 1) For all m: modulo(num, mod, min) == modulo(num + mod*m, mod, min)
73  // 2) For all 0 <= m < mod: modulo(min + m, mod, min) == min + m
74 }
75 
76 /**
77  * round (base_damage * bonus / divisor) to the closest integer,
78  * but up or down towards base_damage
79  */
80 inline int round_damage(int base_damage, int bonus, int divisor) {
81  if (base_damage==0) return 0;
82  const int rounding = divisor / 2 - (bonus < divisor || divisor==1 ? 0 : 1);
83  return std::max<int>(1, (base_damage * bonus + rounding) / divisor);
84 }
85 
86 template<typename Cmp>
87 bool in_ranges(const Cmp c, const std::vector<std::pair<Cmp, Cmp>>& ranges)
88 {
89  return std::any_of(ranges.begin(), ranges.end(), [c](const std::pair<Cmp, Cmp>& range) {
90  return range.first <= c && c <= range.second;
91  });
92 }
93 
94 /**
95  * Returns the size, in bits, of an instance of type `T`, providing a
96  * convenient and self-documenting name for the underlying expression:
97  *
98  * sizeof(T) * std::numeric_limits<unsigned char>::digits
99  *
100  * @tparam T The return value is the size, in bits, of an instance of this
101  * type.
102  *
103  * @returns the size, in bits, of an instance of type `T`.
104  */
105 template<typename T>
106 inline std::size_t bit_width() {
107  return sizeof(T) * std::numeric_limits<unsigned char>::digits;
108 }
109 
110 /**
111  * Returns the size, in bits, of `x`, providing a convenient and
112  * self-documenting name for the underlying expression:
113  *
114  * sizeof(x) * std::numeric_limits<unsigned char>::digits
115  *
116  * @tparam T The return value is the size, in bits, of the type of this object.
117  *
118  * @returns the size, in bits, of an instance of type `T`.
119  */
120 template<typename T>
121 inline std::size_t bit_width(const T&) {
122  return sizeof(T) * std::numeric_limits<unsigned char>::digits;
123 }
124 
125 /**
126  * Returns the quantity of `1` bits in `n` — i.e., `n`’s population count.
127  *
128  * Algorithm adapted from:
129  * <https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan>
130  *
131  * This algorithm was chosen for relative simplicity, not for speed.
132  *
133  * @tparam N The type of `n`. This should be a fundamental integer type no
134  * greater than `UINT_MAX` bits in width; if it is not, the return value is
135  * undefined.
136  *
137  * @param n An integer upon which to operate.
138  *
139  * @returns the quantity of `1` bits in `n`, if `N` is a fundamental integer
140  * type.
141  */
142 template<typename N>
143 inline unsigned int count_ones(N n) {
144  unsigned int r = 0;
145  while (n) {
146  n &= n-1;
147  ++r;
148  }
149  return r;
150 }
151 
152 // Support functions for `count_leading_zeros`.
153 #if defined(__GNUC__) || defined(__clang__)
154 inline unsigned int count_leading_zeros_impl(
155  unsigned char n, std::size_t w) {
156  // Returns the result of the compiler built-in function, adjusted for
157  // the difference between the width, in bits, of the built-in
158  // function’s parameter’s type (which is `unsigned int`, at the
159  // smallest) and the width, in bits, of the input to this function, as
160  // specified at the call-site in `count_leading_zeros`.
161  return static_cast<unsigned int>(__builtin_clz(n))
162  - static_cast<unsigned int>(
163  bit_width<unsigned int>() - w);
164 }
165 inline unsigned int count_leading_zeros_impl(
166  unsigned short int n, std::size_t w) {
167  return static_cast<unsigned int>(__builtin_clz(n))
168  - static_cast<unsigned int>(
169  bit_width<unsigned int>() - w);
170 }
171 inline unsigned int count_leading_zeros_impl(
172  unsigned int n, std::size_t w) {
173  return static_cast<unsigned int>(__builtin_clz(n))
174  - static_cast<unsigned int>(
175  bit_width<unsigned int>() - w);
176 }
177 inline unsigned int count_leading_zeros_impl(
178  unsigned long int n, std::size_t w) {
179  return static_cast<unsigned int>(__builtin_clzl(n))
180  - static_cast<unsigned int>(
181  bit_width<unsigned long int>() - w);
182 }
183 inline unsigned int count_leading_zeros_impl(
184  unsigned long long int n, std::size_t w) {
185  return static_cast<unsigned int>(__builtin_clzll(n))
186  - static_cast<unsigned int>(
187  bit_width<unsigned long long int>() - w);
188 }
189 inline unsigned int count_leading_zeros_impl(
190  char n, std::size_t w) {
192  static_cast<unsigned char>(n), w);
193 }
194 inline unsigned int count_leading_zeros_impl(
195  signed char n, std::size_t w) {
197  static_cast<unsigned char>(n), w);
198 }
199 inline unsigned int count_leading_zeros_impl(
200  signed short int n, std::size_t w) {
202  static_cast<unsigned short int>(n), w);
203 }
204 inline unsigned int count_leading_zeros_impl(
205  signed int n, std::size_t w) {
207  static_cast<unsigned int>(n), w);
208 }
209 inline unsigned int count_leading_zeros_impl(
210  signed long int n, std::size_t w) {
212  static_cast<unsigned long int>(n), w);
213 }
214 inline unsigned int count_leading_zeros_impl(
215  signed long long int n, std::size_t w) {
217  static_cast<unsigned long long int>(n), w);
218 }
219 #else
220 template<typename N>
221 inline unsigned int count_leading_zeros_impl(N n, std::size_t w) {
222  // Algorithm adapted from:
223  // <http://aggregate.org/MAGIC/#Leading%20Zero%20Count>
224  for (unsigned int shift = 1; shift < w; shift *= 2) {
225  n |= (n >> shift);
226  }
227  return static_cast<unsigned int>(w) - count_ones(n);
228 }
229 #endif
230 
231 /**
232  * Returns the quantity of leading `0` bits in `n` — i.e., the quantity of
233  * bits in `n`, minus the 1-based bit index of the most significant `1` bit in
234  * `n`, or minus 0 if `n` is 0.
235  *
236  * @tparam N The type of `n`. This should be a fundamental integer type that
237  * (a) is not wider than `unsigned long long int` (the GCC
238  * count-leading-zeros built-in functions are defined for `unsigned int`,
239  * `unsigned long int`, and `unsigned long long int`), and
240  * (b) is no greater than `INT_MAX` bits in width (the GCC built-in functions
241  * return instances of type `int`);
242  * if `N` does not satisfy these constraints, the return value is undefined.
243  *
244  * @param n An integer upon which to operate.
245  *
246  * @returns the quantity of leading `0` bits in `n`, if `N` satisfies the
247  * above constraints.
248  *
249  * @see count_leading_ones()
250  */
251 template<typename N>
252 inline unsigned int count_leading_zeros(N n) {
253 #if defined(__GNUC__) || defined(__clang__)
254  // GCC’s `__builtin_clz` returns an undefined value when called with 0
255  // as argument.
256  // [<http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html>]
257  if (n == 0) {
258  // Return the quantity of zero bits in `n` rather than
259  // returning that undefined value.
260  return static_cast<unsigned int>(bit_width(n));
261  }
262 #endif
263  // Dispatch, on the static type of `n`, to one of the
264  // `count_leading_zeros_impl` functions.
265  return count_leading_zeros_impl(n, bit_width(n));
266  // The second argument to `count_leading_zeros_impl` specifies the
267  // width, in bits, of `n`.
268  //
269  // This is necessary because `n` may be widened (or, alas, shrunk),
270  // and thus the information of `n`’s true width may be lost.
271  //
272  // At least, this *was* necessary before there were so many overloads
273  // of `count_leading_zeros_impl`, but I’ve kept it anyway as an extra
274  // precautionary measure, that will (I hope) be optimized out.
275  //
276  // To be clear, `n` would only be shrunk in cases noted above as
277  // having an undefined result.
278 }
279 
280 /**
281  * Returns the quantity of leading `1` bits in `n` — i.e., the quantity of
282  * bits in `n`, minus the 1-based bit index of the most significant `0` bit in
283  * `n`, or minus 0 if `n` contains no `0` bits.
284  *
285  * @tparam N The type of `n`. This should be a fundamental integer type that
286  * (a) is not wider than `unsigned long long int`, and
287  * (b) is no greater than `INT_MAX` bits in width;
288  * if `N` does not satisfy these constraints, the return value is undefined.
289  *
290  * @param n An integer upon which to operate.
291  *
292  * @returns the quantity of leading `1` bits in `n`, if `N` satisfies the
293  * above constraints.
294  *
295  * @see count_leading_zeros()
296  */
297 template<typename N>
298 inline unsigned int count_leading_ones(N n) {
299  // Explicitly specify the type for which to instantiate
300  // `count_leading_zeros` in case `~n` is of a different type.
301  return count_leading_zeros<N>(~n);
302 }
303 
304 //Probably not postable.
305 inline int rounded_division(int a, int b)
306 {
307  auto res = std::div(a,b);
308  return 2 * res.rem > b ? (res.quot + 1) : res.quot;
309 }
310 
311 
312 #if 1
313 typedef int32_t fixed_t;
314 # define fxp_shift 8
315 # define fxp_base (1 << fxp_shift)
316 
317 /** IN: float or int - OUT: fixed_t */
318 # define ftofxp(x) (fixed_t((x) * fxp_base))
319 
320 /** IN: unsigned and fixed_t - OUT: unsigned */
321 # define fxpmult(x,y) (((x)*(y)) >> fxp_shift)
322 
323 /** IN: unsigned and int - OUT: fixed_t */
324 # define fxpdiv(x,y) (((x) << fxp_shift) / (y))
325 
326 /** IN: fixed_t - OUT: int */
327 # define fxptoi(x) ( ((x)>0) ? ((x) >> fxp_shift) : (-((-(x)) >> fxp_shift)) )
328 
329 #else
330 typedef float fixed_t;
331 # define ftofxp(x) (x)
332 # define fxpmult(x,y) ((x)*(y))
333 # define fxpdiv(x,y) (static_cast<float>(x) / static_cast<float>(y))
334 # define fxptoi(x) ( static_cast<int>(x) )
335 #endif
unsigned int count_ones(N n)
Returns the quantity of 1 bits in n — i.e., n’s population count.
Definition: math.hpp:143
unsigned int count_leading_zeros_impl(N n, std::size_t w)
Definition: math.hpp:221
bool is_odd(T num)
Definition: math.hpp:36
#define a
bool in_ranges(const Cmp c, const std::vector< std::pair< Cmp, Cmp >> &ranges)
Definition: math.hpp:87
int rounded_division(int a, int b)
Definition: math.hpp:305
#define b
unsigned int count_leading_ones(N n)
Returns the quantity of leading 1 bits in n — i.e., the quantity of bits in n, minus the 1-based bit...
Definition: math.hpp:298
int div100rounded(int num)
Guarantees portable results for division by 100; round half up, to the nearest integer.
Definition: math.hpp:39
bool is_even(T num)
Definition: math.hpp:33
int32_t fixed_t
Definition: math.hpp:313
int round_damage(int base_damage, int bonus, int divisor)
round (base_damage * bonus / divisor) to the closest integer, but up or down towards base_damage ...
Definition: math.hpp:80
std::size_t bit_width()
Returns the size, in bits, of an instance of type T, providing a convenient and self-documenting name...
Definition: math.hpp:106
unsigned int count_leading_zeros(N n)
Returns the quantity of leading 0 bits in n — i.e., the quantity of bits in n, minus the 1-based bit...
Definition: math.hpp:252
int w
int bounded_add(int base, int increment, int max_sum, int min_sum=0)
Returns base + increment, but will not increase base above max_sum, nor decrease it below min_sum...
Definition: math.hpp:48
mock_char c
static map_location::DIRECTION n
T modulo(T num, int mod, T min=0)
Definition: math.hpp:62