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