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