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