Direct-BT v3.3.0-1-gc2d430c
Direct-BT - Direct Bluetooth Programming.
int_math_ct.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_CT_HPP_
26#define JAU_INT_MATH_CT_HPP_
27
28#include <cstdint>
29#include <climits>
30
31#include <jau/int_types.hpp>
32#include <jau/cpp_pragma.hpp>
33
34namespace jau {
35
36 /** @defgroup ConstantTime Constant Time (CT) Integral Operations
37 * Integral integer operations in constant time (CT), see also and meta-group \ref Math
38 *
39 * @{
40 */
41
42 /**
43 // *************************************************
44 // *************************************************
45 // *************************************************
46 */
47
48 // Remember: constexpr specifier used in a function or static data member (since C++17) declaration implies inline.
49
50 /**
51 * Returns the value of the sign function (w/o branching) in O(1) and constant time (CT)
52 * <pre>
53 * -1 for x < 0
54 * 0 for x = 0
55 * 1 for x > 0
56 * </pre>
57 * Implementation is type safe.
58 *
59 * Branching may occur due to relational operator.
60 *
61 * @tparam T an integral number type
62 * @param x the number
63 * @return function result
64 */
65 template <typename T,
66 std::enable_if_t< std::is_integral_v<T>, bool> = true>
67 constexpr int ct_sign(const T x) noexcept
68 {
69 return (x != 0) | -(int)((std::make_unsigned_t<T>)((T)x) >> (sizeof(T) * CHAR_BIT - 1));
70 // return (int) ( (T(0) < x) - (x < T(0)) );
71 }
72
73 /**
74 * Returns the absolute value of an arithmetic number (w/o branching) in O(1) and constant time (CT),
75 * while ct_abs(INT_MIN) is undefined behavior (UB) instead of being mapped correctly to INT_MAX like jau::abs() does, see above.
76 *
77 * This implementation is equivalent to std::abs(), i.e. unsafe
78 *
79 * - signed integral uses 2-complement branch-less conversion, [bithacks Integer-Abs](http://www.graphics.stanford.edu/~seander/bithacks.html#IntegerAbs)
80 * - signed floating-point uses x * sign(x)
81 * - unsigned just returns the value
82 *
83 * This implementation uses 2-complement branch-less conversion, [bithacks Integer-Abs](http://www.graphics.stanford.edu/~seander/bithacks.html#IntegerAbs)
84 *
85 * Note: On an x86_64 architecture abs() w/ branching is of equal speed or even faster.
86 *
87 * @tparam T an arithmetic number type
88 * @param x the number
89 * @return function result
90 */
91 template <typename T,
92 std::enable_if_t< std::is_arithmetic_v<T> &&
93 std::is_integral_v<T> &&
94 !std::is_unsigned_v<T>, bool> = true>
95 constexpr T ct_abs(const T x) noexcept
96 {
97 using unsigned_T = std::make_unsigned_t<T>;
98 const T mask = x >> ( sizeof(T) * CHAR_BIT - 1 );
100 PRAGMA_DISABLE_WARNING_INT_OVERFLOW
101 return static_cast<unsigned_T>( ( x + mask ) ^ mask ); // clang 15: int overflow on UB (constrained in API doc)
103 }
104 template <typename T,
105 std::enable_if_t< std::is_arithmetic_v<T> &&
106 !std::is_integral_v<T> &&
107 !std::is_unsigned_v<T>, bool> = true>
108 constexpr T ct_abs(const T x) noexcept
109 {
110 return x * jau::ct_sign<T>(x);
111 }
112 template <typename T,
113 std::enable_if_t< std::is_arithmetic_v<T> &&
114 std::is_unsigned_v<T>, bool> = true>
115 constexpr T ct_abs(const T x) noexcept
116 {
117 return x;
118 }
119
120 /**
121 * Returns the minimum of two integrals for `MIN <= x - y <= MAX` (w/o branching) in O(1) and constant time (CT).
122 *
123 * Source: [bithacks Test IntegerMinOrMax](http://www.graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax)
124 *
125 * Note: On an x86_64 architecture min() w/ branching is of equal speed or even faster.
126 *
127 * @tparam T an integral number type
128 * @param x one number
129 * @param x the other number
130 */
131 template <typename T,
132 std::enable_if_t< std::is_integral_v<T>, bool> = true>
133 constexpr T ct_min(const T x, const T y) noexcept
134 {
135 return y + ( (x - y) & ( (x - y) >> ( sizeof(T) * CHAR_BIT - 1 ) ) );
136 }
137
138 /**
139 * Returns the maximum of two integrals for `MIN <= x - y <= MAX` (w/o branching) in O(1) and constant time (CT).
140 *
141 * Source: [bithacks Test IntegerMinOrMax](http://www.graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax)
142 *
143 * Note: On an x86_64 architecture max() w/ branching is of equal speed or even faster.
144 *
145 * @tparam T an integral number type
146 * @param x one number
147 * @param x the other number
148 */
149 template <typename T,
150 std::enable_if_t< std::is_integral_v<T>, bool> = true>
151 constexpr T ct_max(const T x, const T y) noexcept
152 {
153 return x - ( (x - y) & ( (x - y) >> ( sizeof(T) * CHAR_BIT - 1 ) ) );
154 }
155
156 /**
157 * Returns constrained integral value to lie between given min- and maximum value for `MIN <= x - y <= MAX`
158 * (w/o branching) in O(1) and constant time (CT).
159 *
160 * Implementation returns `ct_min(ct_max(x, min_val), max_val)`, analog to GLSL's clamp()
161 *
162 * Note: On an x86_64 architecture clamp() w/ branching is of equal speed or even faster.
163 *
164 * @tparam T an integral number type
165 * @param x one number
166 * @param min_val the minimum limes, inclusive
167 * @param max_val the maximum limes, inclusive
168 */
169 template <typename T,
170 std::enable_if_t< std::is_integral_v<T>, bool> = true>
171 constexpr T ct_clamp(const T x, const T min_val, const T max_val) noexcept
172 {
173 return jau::ct_min<T>(jau::ct_max<T>(x, min_val), max_val);
174 }
175
176 /**
177 * Returns merged `a_if_masked` bits selected by `mask` `1` bits and `b_if_unmasked` bits selected by `mask` `0` bits
178 * (w/o branching) in O(1) and constant time (CT).
179 *
180 * Source: [bithacks MaskedMerge](http://www.graphics.stanford.edu/~seander/bithacks.html#MaskedMerge)
181 *
182 * @tparam T an unsigned integral number type
183 * @param mask 1 where bits from `a_if_masked` should be selected; 0 where from `b_if_unmasked`.
184 * @param a_if_masked value to merge in masked bits
185 * @param b_if_unmasked value to merge in non-masked bits
186 */
187 template <typename T,
188 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T>, bool> = true>
189 constexpr T ct_masked_merge(T mask, T a_if_masked, T b_if_unmasked) {
190 return b_if_unmasked ^ ( mask & ( a_if_masked ^ b_if_unmasked ) );
191 }
192
193 /**
194 * Returns the next higher power of 2 of given unsigned 32-bit {@code n}
195 * (w/o branching) in O(1) and constant time (CT).
196 * <p>
197 * Source: [bithacks RoundUpPowerOf2](http://www.graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2)
198 * </p>
199 */
200 constexpr uint32_t ct_next_power_of_2(uint32_t n) {
201 n--;
202 n |= n >> 1;
203 n |= n >> 2;
204 n |= n >> 4;
205 n |= n >> 8;
206 n |= n >> 16;
207 return n + 1;
208 }
209
210 /**
211 * Returns the number of set bits within given 32bit integer
212 * (w/o branching) in O(1) and constant time (CT).
213 *
214 * Uses a <i>HAKEM 169 Bit Count</i> inspired implementation:
215 * <pre>
216 * http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
217 * http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169
218 * http://tekpool.wordpress.com/category/bit-count/
219 * https://github.com/aistrate/HackersDelight/blob/master/Original/HDcode/pop.c.txt
220 * https://github.com/aistrate/HackersDelight/blob/master/Original/HDcode/newCode/popDiff.c.txt
221 * </pre>
222 */
223 constexpr uint32_t ct_bit_count(uint32_t n) noexcept {
224 // Note: Original used 'unsigned int',
225 // hence we use the unsigned right-shift '>>>'
226 /**
227 * Original using 'unsigned' right-shift and modulo
228 *
229 const uint32_t c = n
230 - ( (n >> 1) & 033333333333 )
231 - ( (n >> 2) & 011111111111 );
232 return ( ( c + ( c >> 3 ) ) & 030707070707 ) % 63;
233 *
234 */
235 // Hackers Delight, Figure 5-2, pop1 of pop.c.txt (or popDiff.c.txt in git repo)
236 n = n - ((n >> 1) & 0x55555555);
237 n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
238 n = (n + (n >> 4)) & 0x0f0f0f0f;
239 n = n + (n >> 8);
240 n = n + (n >> 16);
241 return n & 0x3f;
242 }
243
244 /**
245 * Returns ~0 (2-complement) if top bit of arg is set, otherwise 0
246 * (w/o branching) in O(1) and constant time (CT).
247 *
248 * @tparam T an unsigned integral number type
249 */
250 template <typename T,
251 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T>, bool> = true>
252 inline constexpr T ct_expand_top_bit(T x)
253 {
254 return T(0) - ( x >> ( sizeof(T) * CHAR_BIT - 1 ) );
255 }
256
257 /**
258 * Returns ~0 (2-complement) if arg is zero, otherwise 0
259 * (w/o branching) in O(1) and constant time (CT).
260 *
261 * @tparam T an unsigned integral number type
262 */
263 template <typename T,
264 std::enable_if_t< std::is_integral_v<T> && std::is_unsigned_v<T>, bool> = true>
265 inline constexpr T ct_is_zero(T x)
266 {
267 return jau::ct_expand_top_bit<T>( ~x & (x - 1) );
268 }
269
270 /**@}*/
271
272} // namespace jau
273
274#endif /* JAU_INT_MATH_CT_HPP_ */
constexpr uint32_t ct_bit_count(uint32_t n) noexcept
Returns the number of set bits within given 32bit integer (w/o branching) in O(1) and constant time (...
constexpr T ct_expand_top_bit(T x)
Returns ~0 (2-complement) if top bit of arg is set, otherwise 0 (w/o branching) in O(1) and constant ...
constexpr T ct_clamp(const T x, const T min_val, const T max_val) noexcept
Returns constrained integral value to lie between given min- and maximum value for MIN <= x - y <= MA...
constexpr int ct_sign(const T x) noexcept
Returns the value of the sign function (w/o branching) in O(1) and constant time (CT)
Definition: int_math_ct.hpp:67
constexpr T ct_abs(const T x) noexcept
Returns the absolute value of an arithmetic number (w/o branching) in O(1) and constant time (CT),...
Definition: int_math_ct.hpp:95
constexpr T ct_max(const T x, const T y) noexcept
Returns the maximum of two integrals for MIN <= x - y <= MAX (w/o branching) in O(1) and constant tim...
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).
constexpr T ct_masked_merge(T mask, T a_if_masked, T b_if_unmasked)
Returns merged a_if_masked bits selected by mask 1 bits and b_if_unmasked bits selected by mask 0 bit...
constexpr T ct_min(const T x, const T y) noexcept
Returns the minimum of two integrals for MIN <= x - y <= MAX (w/o branching) in O(1) and constant tim...
#define PRAGMA_DISABLE_WARNING_PUSH
Definition: cpp_pragma.hpp:76
#define PRAGMA_DISABLE_WARNING_POP
Definition: cpp_pragma.hpp:77
__pack(...): Produces MSVC, clang and gcc compatible lead-in and -out macros.
Definition: backtrace.hpp:32