The Battle for Wesnoth  1.19.0-dev
math.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2024
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 constexpr bool is_even(T num) { return num % 2 == 0; }
34 
35 template<typename T>
36 constexpr 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 constexpr 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 constexpr 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 constexpr 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 constexpr 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 constexpr 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 constexpr 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 leading `0` bits in `n` — i.e., the quantity of
127  * bits in `n`, minus the 1-based bit index of the most significant `1` bit in
128  * `n`, or minus 0 if `n` is 0.
129  *
130  * @tparam N The type of `n`. This should be a fundamental integer type that
131  * (a) is not wider than `unsigned long long int` (the GCC
132  * count-leading-zeros built-in functions are defined for `unsigned int`,
133  * `unsigned long int`, and `unsigned long long int`), and
134  * (b) is no greater than `INT_MAX` bits in width (the GCC built-in functions
135  * return instances of type `int`);
136  * if `N` does not satisfy these constraints, the return value is undefined.
137  *
138  * @param n An integer upon which to operate.
139  *
140  * @returns the quantity of leading `0` bits in `n`, if `N` satisfies the
141  * above constraints.
142  *
143  * @see count_leading_ones()
144  */
145 template<typename N>
146 constexpr std::enable_if_t<std::is_integral_v<N>, unsigned int> count_leading_zeros(N n) {
147  const auto x = static_cast<std::make_unsigned_t<N>>(n);
148  constexpr decltype(x) mask{1};
149 
150  unsigned int count{0};
151  for(int i = std::numeric_limits<decltype(mask)>::digits - 1; i >= 0; --i) {
152  if(x & (mask << i)) {
153  break;
154  }
155  ++count;
156  }
157 
158  return count;
159 }
160 
161 /**
162  * Returns the quantity of leading `1` bits in `n` — i.e., the quantity of
163  * bits in `n`, minus the 1-based bit index of the most significant `0` bit in
164  * `n`, or minus 0 if `n` contains no `0` bits.
165  *
166  * @tparam N The type of `n`. This should be a fundamental integer type that
167  * (a) is not wider than `unsigned long long int`, and
168  * (b) is no greater than `INT_MAX` bits in width;
169  * if `N` does not satisfy these constraints, the return value is undefined.
170  *
171  * @param n An integer upon which to operate.
172  *
173  * @returns the quantity of leading `1` bits in `n`, if `N` satisfies the
174  * above constraints.
175  *
176  * @see count_leading_zeros()
177  */
178 template<typename N>
179 constexpr unsigned int count_leading_ones(N n) {
180  // Explicitly specify the type for which to instantiate
181  // `count_leading_zeros` in case `~n` is of a different type.
182  return count_leading_zeros<N>(~n);
183 }
184 
185 //Probably not postable.
186 inline int rounded_division(int a, int b)
187 {
188  auto res = std::div(a,b);
189  return 2 * res.rem > b ? (res.quot + 1) : res.quot;
190 }
191 
192 /**
193  * @param n1 The first number to multiply.
194  * @param n2 The second number to multiply.
195  * @return The unsigned result of n1 * n2, then bitshifting the result to the right.
196  */
197 constexpr unsigned fixed_point_multiply(int32_t n1, int32_t n2)
198 {
199  return static_cast<unsigned>((n1 * n2) >> 8);
200 }
201 
202 /**
203  * @param n1 The numerator, which gets bit shifted left.
204  * @param n2 The divisor.
205  * @return n1 bit shifted left then divided by n1.
206  */
207 constexpr int32_t fixed_point_divide(int n1, int n2)
208 {
209  return (n1 << 8) / n2;
210 }
211 
212 /**
213  * If positive, just bit shift.
214  * Else, make positive, bit shift, then make negative again.
215  *
216  * @param n The number to bit shift right.
217  * @return The result of the bit shift.
218  */
219 constexpr int fixed_point_to_int(int32_t n)
220 {
221  if(n > 0)
222  {
223  return n >> 8;
224  }
225  else
226  {
227  return -(-n >> 8);
228  }
229 }
std::size_t i
Definition: function.cpp:968
constexpr int div100rounded(int num)
Guarantees portable results for division by 100; round half up, to the nearest integer.
Definition: math.hpp:39
constexpr int fixed_point_to_int(int32_t n)
If positive, just bit shift.
Definition: math.hpp:219
constexpr bool is_even(T num)
Definition: math.hpp:33
constexpr 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
constexpr 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:179
constexpr 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
constexpr bool is_odd(T num)
Definition: math.hpp:36
bool in_ranges(const Cmp c, const std::vector< std::pair< Cmp, Cmp >> &ranges)
Definition: math.hpp:87
constexpr unsigned fixed_point_multiply(int32_t n1, int32_t n2)
Definition: math.hpp:197
int rounded_division(int a, int b)
Definition: math.hpp:186
constexpr T modulo(T num, int mod, T min=0)
Definition: math.hpp:62
constexpr int32_t fixed_point_divide(int n1, int n2)
Definition: math.hpp:207
constexpr std::enable_if_t< std::is_integral_v< N >, 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:146
constexpr 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
mock_char c
static map_location::DIRECTION n
#define a
#define b