Direct-BT v3.3.0-1-gc2d430c
Direct-BT - Direct Bluetooth Programming.
int_math.hpp
Go to the documentation of this file.
1/*
2 * Author: Sven Gothel <sgothel@jausoft.com>
3 * Copyright (c) 2020-2024 Gothel Software e.K.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining
6 * a copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sublicense, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
20 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
21 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
22 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25#ifndef JAU_INT_MATH_HPP_
26#define JAU_INT_MATH_HPP_
27
28#include <cstdint>
29#include <cmath>
30#include <climits>
31
32#include <jau/base_math.hpp>
33#include <jau/int_math_ct.hpp>
34
35namespace jau {
36
37 #define JAU_USE_BUILDIN_OVERFLOW 1
38
39 /** \addtogroup Integer
40 *
41 * @{
42 */
43
44 /**
45 * base_math: arithmetic types, i.e. integral + floating point types
46 * int_math: integral types
47 * float_math: floating point types
48 // *************************************************
49 // *************************************************
50 // *************************************************
51 */
52
53 // Remember: constexpr specifier used in a function or static data member (since C++17) declaration implies inline.
54
55 /** Returns true of the given integer value is zero. */
56 template<class T>
57 typename std::enable_if<std::is_integral_v<T>, bool>::type
58 constexpr is_zero(const T& a) noexcept {
59 return 0 == a;
60 }
61
62 /**
63 * Returns true if both values are equal.
64 *
65 * @tparam T an integral type
66 * @param a value to compare
67 * @param b value to compare
68 */
69 template<class T>
70 typename std::enable_if<std::is_integral_v<T>, bool>::type
71 constexpr equals(const T& a, const T& b) noexcept {
72 return a == b;
73 }
74
75 /**
76 * Returns true if both values are equal, i.e. their absolute delta <= `allowed_deviation`.
77 *
78 * @tparam T an integral type
79 * @param a value to compare
80 * @param b value to compare
81 * @param allowed_deviation allowed deviation
82 */
83 template<class T>
84 typename std::enable_if<std::is_integral_v<T>, bool>::type
85 constexpr equals(const T& a, const T& b, const T& allowed_deviation) noexcept {
86 return std::abs(a - b) <= allowed_deviation;
87 }
88
89 /**
90 * Round up w/ branching in O(1)
91 *
92 * @tparam T an unsigned integral number type
93 * @tparam U an unsigned integral number type
94 * @param n to be aligned number
95 * @param align_to alignment boundary, must not be 0
96 * @return n rounded up to a multiple of align_to
97 */
98 template <typename T, typename U,
99 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T> &&
100 std::is_integral_v<U> && std::is_unsigned_v<U>, bool> = true>
101 constexpr T round_up(const T n, const U align_to) {
102 assert(align_to != 0); // align_to must not be 0
103
104 if(n % align_to) {
105 return n + ( align_to - ( n % align_to ) );
106 } else {
107 return n;
108 }
109 }
110
111 /**
112 * Round down w/ branching in O(1)
113 *
114 * @tparam T an unsigned integral number type
115 * @tparam U an unsigned integral number type
116 * @param n to be aligned number
117 * @param align_to alignment boundary
118 * @return n rounded down to a multiple of align_to
119 */
120 template <typename T, typename U,
121 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T> &&
122 std::is_integral_v<U> && std::is_unsigned_v<U>, bool> = true>
123 constexpr T round_down(T n, U align_to) {
124 return align_to == 0 ? n : ( n - ( n % align_to ) );
125 }
126
127 /**
128 * Power of 2 test (w/o branching ?) in O(1)
129 *
130 * Source: [bithacks Test PowerOf2](http://www.graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
131 *
132 * Branching may occur due to relational operator.
133 *
134 * @tparam T an unsigned integral number type
135 * @param x the unsigned integral number
136 * @return true if arg is 2^n for some n > 0
137 */
138 template <typename T,
139 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T>, bool> = true>
140 constexpr bool is_power_of_2(const T x) noexcept
141 {
142 return 0<x && 0 == ( x & static_cast<T>( x - 1 ) );
143 }
144
145 /**
146 * If the given {@code n} is not is_power_of_2() return next_power_of_2(),
147 * otherwise return {@code n} unchanged.
148 * <pre>
149 * return is_power_of_2(n) ? n : next_power_of_2(n);
150 * </pre>
151 */
152 constexpr uint32_t round_to_power_of_2(const uint32_t n) {
153 return is_power_of_2(n) ? n : ct_next_power_of_2(n);
154 }
155
156 /**
157 * Return the index of the highest set bit w/ branching (loop) in O(n), actually O(n/2).
158 *
159 * @tparam T an unsigned integral number type
160 * @param x value
161 */
162 template <typename T,
163 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T>, bool> = true>
164 inline constexpr nsize_t high_bit(T x)
165 {
166 nsize_t hb = 0;
167 for(nsize_t s = ( CHAR_BIT * sizeof(T) ) >> 1; s > 0; s >>= 1) {
168 const nsize_t z = s * ( ( ~jau::ct_is_zero( x >> s ) ) & 1 );
169 hb += z;
170 x >>= z;
171 }
172 return hb + x;
173 }
174
175 /**
176 * Integer overflow aware addition returning true if overflow occurred,
177 * otherwise false having the result stored in res.
178 *
179 * Implementation uses [Integer Overflow Builtins](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)
180 * if available, otherwise its own implementation.
181 *
182 * @tparam T an integral integer type
183 * @tparam
184 * @param a operand a
185 * @param b operand b
186 * @param res storage for result
187 * @return true if overflow, otherwise false
188 */
189 template <typename T,
190 std::enable_if_t< std::is_integral_v<T>, bool> = true>
191 constexpr bool add_overflow(const T a, const T b, T& res) noexcept
192 {
193#if JAU_USE_BUILDIN_OVERFLOW && ( defined(__GNUC__) || defined(__clang__) )
194 return __builtin_add_overflow(a, b, &res);
195#else
196 // overflow: a + b > R+ -> a > R+ - b, with b >= 0
197 // underflow: a + b < R- -> a < R- - b, with b < 0
198 if ( ( b >= 0 && a > std::numeric_limits<T>::max() - b ) ||
199 ( b < 0 && a < std::numeric_limits<T>::min() - b ) )
200 {
201 return true;
202 } else {
203 res = a + b;
204 return false;
205 }
206#endif
207 }
208
209 /**
210 * Integer overflow aware subtraction returning true if overflow occurred,
211 * otherwise false having the result stored in res.
212 *
213 * Implementation uses [Integer Overflow Builtins](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)
214 * if available, otherwise its own implementation.
215 *
216 * @tparam T an integral integer type
217 * @tparam
218 * @param a operand a
219 * @param b operand b
220 * @param res storage for result
221 * @return true if overflow, otherwise false
222 */
223 template <typename T,
224 std::enable_if_t< std::is_integral_v<T>, bool> = true>
225 constexpr bool sub_overflow(const T a, const T b, T& res) noexcept
226 {
227#if JAU_USE_BUILDIN_OVERFLOW && ( defined(__GNUC__) || defined(__clang__) )
228 return __builtin_sub_overflow(a, b, &res);
229#else
230 // overflow: a - b > R+ -> a > R+ + b, with b < 0
231 // underflow: a - b < R- -> a < R- + b, with b >= 0
232 if ( ( b < 0 && a > std::numeric_limits<T>::max() + b ) ||
233 ( b >= 0 && a < std::numeric_limits<T>::min() + b ) )
234 {
235 return true;
236 } else {
237 res = a - b;
238 return false;
239 }
240#endif
241 }
242
243 /**
244 * Integer overflow aware multiplication returning true if overflow occurred,
245 * otherwise false having the result stored in res.
246 *
247 * Implementation uses [Integer Overflow Builtins](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)
248 * if available, otherwise its own implementation.
249 *
250 * @tparam T an integral integer type
251 * @tparam
252 * @param a operand a
253 * @param b operand b
254 * @param res storage for result
255 * @return true if overflow, otherwise false
256 */
257 template <typename T,
258 std::enable_if_t< std::is_integral_v<T>, bool> = true>
259 constexpr bool mul_overflow(const T a, const T b, T& res) noexcept
260 {
261#if JAU_USE_BUILDIN_OVERFLOW && ( defined(__GNUC__) || defined(__clang__) )
262 return __builtin_mul_overflow(a, b, &res);
263#else
264 // overflow: a * b > R+ -> a > R+ / b
265 if ( ( b > 0 && abs(a) > std::numeric_limits<T>::max() / b ) ||
266 ( b < 0 && abs(a) > std::numeric_limits<T>::min() / b ) )
267 {
268 return true;
269 } else {
270 res = a * b;
271 return false;
272 }
273#endif
274 }
275
276 /**
277 * Returns the greatest common divisor (GCD) of the two given integer values following Euclid's algorithm from Euclid's Elements ~300 BC,
278 * using the absolute positive value of given integers.
279 *
280 * Returns zero if a and b is zero.
281 *
282 * Note implementation uses modulo operator `(a/b)*b + a % b = a `,
283 * i.e. remainder of the integer division - hence implementation uses `abs(a) % abs(b)`
284 * in case the integral T is a signed type (dropped for unsigned).
285 *
286 * Implementation is similar to std::gcd(), however, it uses a fixed common type T
287 * and a while loop instead of compile time evaluation via recursion.
288 *
289 * @tparam T integral type
290 * @tparam
291 * @param a integral value a
292 * @param b integral value b
293 * @return zero if a and b are zero, otherwise the greatest common divisor (GCD) of a and b,
294 */
295 template <typename T,
296 std::enable_if_t< std::is_integral_v<T> &&
297 !std::is_unsigned_v<T>, bool> = true>
298 constexpr T gcd(T a, T b) noexcept
299 {
300 T a_ = abs(a);
301 T b_ = abs(b);
302 while( b_ != 0 ) {
303 const T t = b_;
304 b_ = a_ % b_;
305 a_ = t;
306 }
307 return a_;
308 }
309
310 template <typename T,
311 std::enable_if_t< std::is_integral_v<T> &&
312 std::is_unsigned_v<T>, bool> = true>
313 constexpr T gcd(T a, T b) noexcept
314 {
315 while( b != 0 ) {
316 const T t = b;
317 b = a % b;
318 a = t;
319 }
320 return a;
321 }
322
323 /**
324 * Integer overflow aware calculation of least common multiple (LCM) following Euclid's algorithm from Euclid's Elements ~300 BC.
325 * @tparam T integral type
326 * @tparam
327 * @param result storage for lcm result: zero if a and b are zero, otherwise lcm of a and b
328 * @param a integral value a
329 * @param b integral value b
330 * @return true if overflow, otherwise false for success
331 */
332 template <typename T,
333 std::enable_if_t< std::is_integral_v<T>, bool> = true>
334 constexpr bool lcm_overflow(const T a, const T b, T& result) noexcept
335 {
336 const T _gcd = gcd<T>( a, b );
337 if( 0 < _gcd ) {
338 T r;
339 if( mul_overflow(a, b, r) ) {
340 return true;
341 } else {
342 result = r / _gcd;
343 return false;
344 }
345 } else {
346 result = 0;
347 return false;
348 }
349 }
350
351 /**
352 * Returns the number of decimal digits of the given integral value number using std::log10<T>().<br>
353 * If sign_is_digit == true (default), treats a potential negative sign as a digit.
354 * <pre>
355 * x < 0: 1 + (int) ( log10( -x ) ) + ( sign_is_digit ? 1 : 0 )
356 * x = 0: 1
357 * x > 0: 1 + (int) ( log10( x ) )
358 * </pre>
359 * Implementation uses jau::invert_sign() to have a safe absolute value conversion, if required.
360 * <p>
361 * Convenience method, reusing precomputed sign of value to avoid redundant computations.
362 * </p>
363 * @tparam T an integral integer type
364 * @param x the integral integer
365 * @param x_sign the pre-determined sign of the given value x
366 * @param sign_is_digit if true and value is negative, adds one to result for sign. Defaults to true.
367 * @return digit count
368 */
369 template <typename T,
370 std::enable_if_t< std::is_integral_v<T>, bool> = true>
371 constexpr nsize_t digits10(const T x, const snsize_t x_sign, const bool sign_is_digit=true) noexcept
372 {
373 if( x_sign == 0 ) {
374 return 1;
375 }
376 if( x_sign < 0 ) {
377 return 1 + static_cast<nsize_t>( std::log10<T>( invert_sign<T>( x ) ) ) + ( sign_is_digit ? 1 : 0 );
378 } else {
379 return 1 + static_cast<nsize_t>( std::log10<T>( x ) );
380 }
381 }
382
383 /**
384 * Returns the number of decimal digits of the given integral value number using std::log10<T>().
385 * If sign_is_digit == true (default), treats a potential negative sign as a digit.
386 * <pre>
387 * x < 0: 1 + (int) ( log10( -x ) ) + ( sign_is_digit ? 1 : 0 )
388 * x = 0: 1
389 * x > 0: 1 + (int) ( log10( x ) )
390 * </pre>
391 * Implementation uses jau::invert_sign() to have a safe absolute value conversion, if required.
392 * @tparam T an integral integer type
393 * @param x the integral integer
394 * @param sign_is_digit if true and value is negative, adds one to result for sign. Defaults to true.
395 * @return digit count
396 */
397 template <typename T,
398 std::enable_if_t< std::is_integral_v<T>, bool> = true>
399 constexpr nsize_t digits10(const T x, const bool sign_is_digit=true) noexcept
400 {
401 return digits10<T>(x, jau::sign<T>(x), sign_is_digit);
402 }
403
404 /**@}*/
405
406} // namespace jau
407
408#endif /* JAU_INT_MATH_HPP_ */
constexpr uint32_t ct_next_power_of_2(uint32_t n)
Returns the next higher power of 2 of given unsigned 32-bit n (w/o branching) in O(1) and constant ti...
constexpr T ct_is_zero(T x)
Returns ~0 (2-complement) if arg is zero, otherwise 0 (w/o branching) in O(1) and constant time (CT).
std::enable_if< std::is_floating_point_v< T >, bool >::type constexpr is_zero(const T &a, const T &epsilon=std::numeric_limits< T >::epsilon()) noexcept
Returns true if the given value is less than epsilon, w/ epsilon > 0.
Definition: float_math.hpp:255
std::enable_if< std::is_floating_point_v< T >, bool >::type constexpr equals(const T &a, const T &b, const T &epsilon=std::numeric_limits< T >::epsilon()) noexcept
Returns true if both values are equal, i.e.
Definition: float_math.hpp:394
constexpr T round_up(const T n, const U align_to)
Round up w/ branching in O(1)
Definition: int_math.hpp:101
constexpr nsize_t digits10(const T x, const snsize_t x_sign, const bool sign_is_digit=true) noexcept
Returns the number of decimal digits of the given integral value number using std::log10<T>().
Definition: int_math.hpp:371
constexpr nsize_t high_bit(T x)
Return the index of the highest set bit w/ branching (loop) in O(n), actually O(n/2).
Definition: int_math.hpp:164
constexpr T min(const T x, const T y) noexcept
Returns the minimum of two integrals (w/ branching) in O(1)
Definition: base_math.hpp:177
uint_fast32_t nsize_t
Natural 'size_t' alternative using uint_fast32_t as its natural sized type.
Definition: int_types.hpp:53
constexpr bool mul_overflow(const T a, const T b, T &res) noexcept
Integer overflow aware multiplication returning true if overflow occurred, otherwise false having the...
Definition: int_math.hpp:259
constexpr bool sub_overflow(const T a, const T b, T &res) noexcept
Integer overflow aware subtraction returning true if overflow occurred, otherwise false having the re...
Definition: int_math.hpp:225
int_fast32_t snsize_t
Natural 'ssize_t' alternative using int_fast32_t as its natural sized type.
Definition: int_types.hpp:65
constexpr uint32_t round_to_power_of_2(const uint32_t n)
If the given n is not is_power_of_2() return next_power_of_2(), otherwise return n unchanged.
Definition: int_math.hpp:152
constexpr T gcd(T a, T b) noexcept
Returns the greatest common divisor (GCD) of the two given integer values following Euclid's algorith...
Definition: int_math.hpp:298
constexpr T max(const T x, const T y) noexcept
Returns the maximum of two integrals (w/ branching) in O(1)
Definition: base_math.hpp:191
constexpr T round_down(T n, U align_to)
Round down w/ branching in O(1)
Definition: int_math.hpp:123
constexpr bool add_overflow(const T a, const T b, T &res) noexcept
Integer overflow aware addition returning true if overflow occurred, otherwise false having the resul...
Definition: int_math.hpp:191
constexpr bool lcm_overflow(const T a, const T b, T &result) noexcept
Integer overflow aware calculation of least common multiple (LCM) following Euclid's algorithm from E...
Definition: int_math.hpp:334
constexpr T abs(const T x) noexcept
Returns the absolute value of an arithmetic number (w/ branching) in O(1)
Definition: base_math.hpp:155
constexpr bool is_power_of_2(const T x) noexcept
Power of 2 test (w/o branching ?) in O(1)
Definition: int_math.hpp:140
__pack(...): Produces MSVC, clang and gcc compatible lead-in and -out macros.
Definition: backtrace.hpp:32