The Battle for Wesnoth  1.19.16+dev
math.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2025
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 <cstdint>
25 #include <limits>
26 #include <vector>
27 #include <algorithm>
28 #include <cassert>
29 
30 template<typename T>
31 constexpr bool is_even(T num) { return num % 2 == 0; }
32 
33 template<typename T>
34 constexpr 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 constexpr 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 constexpr 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 /**
57  * @returns: the number n in [min, min+mod ) so that (n - num) is a multiple of mod.
58  */
59 template<typename T>
60 constexpr T modulo(T num, int mod, T min = 0)
61 {
62  assert(mod > 0);
63  T n = (num - min) % mod;
64  if (n < 0)
65  n += mod;
66  //n is now in [0, mod)
67  n = n + min;
68  return n;
69  // the following properties are easy to verify:
70  // 1) For all m: modulo(num, mod, min) == modulo(num + mod*m, mod, min)
71  // 2) For all 0 <= m < mod: modulo(min + m, mod, min) == min + m
72 }
73 
74 /**
75  * round (base_damage * bonus / divisor) to the closest integer,
76  * but up or down towards base_damage
77  */
78 constexpr int round_damage(double base_damage, int bonus, int divisor) {
79  if (base_damage==0) return 0;
80  const int rounding = divisor / 2 - (bonus <= divisor || divisor==1 ? 0 : 1);
81  return std::max<int>(1, static_cast<int>(base_damage * bonus + rounding) / divisor);
82 }
83 
84 template<typename Cmp>
85 bool in_ranges(const Cmp c, const std::vector<std::pair<Cmp, Cmp>>& ranges)
86 {
87  return std::any_of(ranges.begin(), ranges.end(), [c](const std::pair<Cmp, Cmp>& range) {
88  return range.first <= c && c <= range.second;
89  });
90 }
91 
92 /**
93  * Returns the size, in bits, of an instance of type `T`, providing a
94  * convenient and self-documenting name for the underlying expression:
95  *
96  * sizeof(T) * std::numeric_limits<unsigned char>::digits
97  *
98  * @tparam T The return value is the size, in bits, of an instance of this
99  * type.
100  *
101  * @returns the size, in bits, of an instance of type `T`.
102  */
103 template<typename T>
104 constexpr std::size_t bit_width() {
105  return sizeof(T) * std::numeric_limits<unsigned char>::digits;
106 }
107 
108 /**
109  * Returns the size, in bits, of `x`, providing a convenient and
110  * self-documenting name for the underlying expression:
111  *
112  * sizeof(x) * std::numeric_limits<unsigned char>::digits
113  *
114  * @tparam T The return value is the size, in bits, of the type of this object.
115  *
116  * @returns the size, in bits, of an instance of type `T`.
117  */
118 template<typename T>
119 constexpr std::size_t bit_width(const T&) {
120  return sizeof(T) * std::numeric_limits<unsigned char>::digits;
121 }
122 
123 /**
124  * Returns the quantity of leading `0` bits in `n` — i.e., the quantity of
125  * bits in `n`, minus the 1-based bit index of the most significant `1` bit in
126  * `n`, or minus 0 if `n` is 0.
127  *
128  * @tparam N The type of `n`. This should be a fundamental integer type that
129  * (a) is not wider than `unsigned long long int` (the GCC
130  * count-leading-zeros built-in functions are defined for `unsigned int`,
131  * `unsigned long int`, and `unsigned long long int`), and
132  * (b) is no greater than `INT_MAX` bits in width (the GCC built-in functions
133  * return instances of type `int`);
134  * if `N` does not satisfy these constraints, the return value is undefined.
135  *
136  * @param n An integer upon which to operate.
137  *
138  * @returns the quantity of leading `0` bits in `n`, if `N` satisfies the
139  * above constraints.
140  *
141  * @see count_leading_ones()
142  */
143 template<typename N>
144 constexpr std::enable_if_t<std::is_integral_v<N>, unsigned int> count_leading_zeros(N n) {
145  const auto x = static_cast<std::make_unsigned_t<N>>(n);
146  constexpr decltype(x) mask{1};
147 
148  unsigned int count{0};
149  for(int i = std::numeric_limits<decltype(mask)>::digits - 1; i >= 0; --i) {
150  if(x & (mask << i)) {
151  break;
152  }
153  ++count;
154  }
155 
156  return count;
157 }
158 
159 /**
160  * Returns the quantity of leading `1` bits in `n` — i.e., the quantity of
161  * bits in `n`, minus the 1-based bit index of the most significant `0` bit in
162  * `n`, or minus 0 if `n` contains no `0` bits.
163  *
164  * @tparam N The type of `n`. This should be a fundamental integer type that
165  * (a) is not wider than `unsigned long long int`, and
166  * (b) is no greater than `INT_MAX` bits in width;
167  * if `N` does not satisfy these constraints, the return value is undefined.
168  *
169  * @param n An integer upon which to operate.
170  *
171  * @returns the quantity of leading `1` bits in `n`, if `N` satisfies the
172  * above constraints.
173  *
174  * @see count_leading_zeros()
175  */
176 template<typename N>
177 constexpr unsigned int count_leading_ones(N n) {
178  // Explicitly specify the type for which to instantiate
179  // `count_leading_zeros` in case `~n` is of a different type.
180  return count_leading_zeros<N>(~n);
181 }
182 
183 //Probably not postable.
184 inline int rounded_division(int a, int b)
185 {
186  auto res = std::div(a,b);
187  return 2 * res.rem > b ? (res.quot + 1) : res.quot;
188 }
189 
190 /**
191  * @param n1 The first number to multiply.
192  * @param n2 The second number to multiply.
193  * @return The unsigned result of n1 * n2, then bitshifting the result to the right.
194  */
195 constexpr unsigned fixed_point_multiply(int32_t n1, int32_t n2)
196 {
197  return static_cast<unsigned>((n1 * n2) >> 8);
198 }
199 
200 /**
201  * @param n1 The numerator, which gets bit shifted left.
202  * @param n2 The divisor.
203  * @return n1 bit shifted left then divided by n1.
204  */
205 constexpr int32_t fixed_point_divide(int n1, int n2)
206 {
207  return (n1 << 8) / n2;
208 }
209 
210 /**
211  * If positive, just bit shift.
212  * Else, make positive, bit shift, then make negative again.
213  *
214  * @param n The number to bit shift right.
215  * @return The result of the bit shift.
216  */
217 constexpr int fixed_point_to_int(int32_t n)
218 {
219  if(n > 0)
220  {
221  return n >> 8;
222  }
223  else
224  {
225  return -(-n >> 8);
226  }
227 }
std::size_t i
Definition: function.cpp:1032
constexpr int div100rounded(int num)
Guarantees portable results for division by 100; round half up, to the nearest integer.
Definition: math.hpp:37
constexpr int fixed_point_to_int(int32_t n)
If positive, just bit shift.
Definition: math.hpp:217
constexpr bool is_even(T num)
Definition: math.hpp:31
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:46
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:177
constexpr bool is_odd(T num)
Definition: math.hpp:34
bool in_ranges(const Cmp c, const std::vector< std::pair< Cmp, Cmp >> &ranges)
Definition: math.hpp:85
constexpr unsigned fixed_point_multiply(int32_t n1, int32_t n2)
Definition: math.hpp:195
int rounded_division(int a, int b)
Definition: math.hpp:184
constexpr T modulo(T num, int mod, T min=0)
Definition: math.hpp:60
constexpr int round_damage(double 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:78
constexpr int32_t fixed_point_divide(int n1, int n2)
Definition: math.hpp:205
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:144
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:104
mock_char c
static map_location::direction n
#define b