Botan 3.14.1
Crypto and TLS for C&
bit_ops.h
Go to the documentation of this file.
1/*
2* Bit/Word Operations
3* (C) 1999-2008 Jack Lloyd
4* (C) Copyright Projet SECRET, INRIA, Rocquencourt
5* (C) Bhaskar Biswas and Nicolas Sendrier
6* (C) 2014 cryptosource GmbH
7* (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
8*
9* Botan is released under the Simplified BSD License (see license.txt)
10*/
11
12#ifndef BOTAN_BIT_OPS_H_
13#define BOTAN_BIT_OPS_H_
14
15#include <botan/types.h>
16
17#include <botan/compiler.h>
18#include <botan/internal/bswap.h>
19#include <botan/internal/value_barrier.h>
20#include <concepts>
21
22namespace Botan {
23
24/**
25* If top bit of arg is set, return |1| (all bits set). Otherwise return |0| (all bits unset)
26*/
27template <std::unsigned_integral T>
29 const T top = CT::value_barrier<T>(a >> (sizeof(T) * 8 - 1));
30 return static_cast<T>(0) - top;
31}
32
33/**
34* If arg is zero, return |1|. Otherwise return |0|
35*/
36template <std::unsigned_integral T>
38 return ct_expand_top_bit<T>(~x & (x - 1));
39}
40
41/**
42* If arg is zero, return the size_t `s`. Otherwise return the size_t zero.
43*/
44template <std::unsigned_integral T>
45BOTAN_FORCE_INLINE constexpr size_t ct_if_is_zero_ret(T x, size_t s) {
46 /*
47 Similar to `return ct_is_zero(x) & s` but has to account for possibility that
48 sizeof(T) is smaller than sizeof(size_t) which would lead to incomplete masking
49 */
50 const T a = ~x & (x - 1);
51 const size_t a_top = static_cast<size_t>(CT::value_barrier<T>(a >> (sizeof(T) * 8 - 1)));
52 const size_t mask = static_cast<size_t>(0) - a_top;
53 return mask & s;
54}
55
56/**
57* Power of 2 test. T should be an unsigned integer type
58* @param arg an integer value
59* @return true iff arg is 2^n for some n > 0
60*/
61template <std::unsigned_integral T>
62BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg) {
63 return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg - 1)) == 0);
64}
65
66/**
67* Return the index of the highest set bit
68* T is an unsigned integer type
69* @param n an integer value
70* @return index of the highest set bit in n
71*/
72template <std::unsigned_integral T>
73BOTAN_FORCE_INLINE constexpr size_t high_bit(T n) {
74 size_t hb = 0;
75
76 for(size_t s = 8 * sizeof(T) / 2; s > 0; s /= 2) {
77 // Equivalent to: ((n >> s) == 0) ? 0 : s;
78 const size_t z = s - ct_if_is_zero_ret<T>(n >> s, s);
79 hb += z;
80 n >>= z;
81 }
82
83 hb += static_cast<size_t>(n);
84
85 return hb;
86}
87
88/**
89* Return the number of significant bytes in n
90* @param n an integer value
91* @return number of significant bytes in n
92*/
93template <std::unsigned_integral T>
95 size_t b = 0;
96
97 for(size_t s = 8 * sizeof(T) / 2; s >= 8; s /= 2) {
98 // Equivalent to: ((n >> s) == 0) ? 0 : s;
99 const size_t z = s - ct_if_is_zero_ret<T>(n >> s, s);
100 b += z / 8;
101 n >>= z;
102 }
103
104 b += (n != 0);
105
106 return b;
107}
108
109/**
110* Count the trailing zero bits in n
111* @param n an integer value
112* @return maximum x st 2^x divides n
113*/
114template <std::unsigned_integral T>
115BOTAN_FORCE_INLINE constexpr size_t ctz(T n) {
116 /*
117 * If n == 0 then this function will compute 8*sizeof(T)-1, so
118 * initialize lb to 1 if n == 0 to produce the expected result.
119 */
120 size_t lb = ct_if_is_zero_ret<T>(n, 1);
121
122 for(size_t s = 8 * sizeof(T) / 2; s > 0; s /= 2) {
123 const T range = (static_cast<T>(1) << s) - 1;
124 // Equivalent to: ((n & range) == 0) ? s : 0;
125 const size_t z = ct_if_is_zero_ret<T>(n & range, s);
126 lb += z;
127 n >>= z;
128 }
129
130 return lb;
131}
132
133template <std::unsigned_integral T>
135 BOTAN_ARG_CHECK(n != 0, "log2(0) is not defined");
136 return static_cast<T>(high_bit(n) - 1);
137}
138
139template <std::unsigned_integral T>
140constexpr uint8_t ceil_log2(T x)
141 requires(sizeof(T) < 32)
142{
143 if(x >> (sizeof(T) * 8 - 1)) {
144 return sizeof(T) * 8;
145 }
146
147 uint8_t result = 0;
148 T compare = 1;
149
150 while(compare < x) {
151 compare <<= 1;
152 result++;
153 }
154
155 return result;
156}
157
158/**
159 * Ceil of an unsigned integer division. @p b must not be zero.
160 *
161 * @param a divident
162 * @param b divisor
163 *
164 * @returns ceil(a/b)
165 */
166template <std::unsigned_integral T>
167BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b) {
168 // Same as `(a + b - 1) / b` but avoids possible overflow
169 return a / b + ((a % b != 0) ? 1 : 0);
170}
171
172/**
173 * Return the number of bytes necessary to contain @p bits bits.
174 */
175template <std::unsigned_integral T>
176BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits) {
177 return (bits + 7) / 8;
178}
179
180// Potentially variable time ctz used for OCB
181BOTAN_FORCE_INLINE constexpr size_t var_ctz64(uint64_t n) {
182#if BOTAN_COMPILER_HAS_BUILTIN(__builtin_ctzll)
183 if(n == 0) {
184 return 64;
185 }
186 return __builtin_ctzll(n);
187#else
188 return ctz<uint64_t>(n);
189#endif
190}
191
192template <std::unsigned_integral T>
193BOTAN_FORCE_INLINE constexpr T bit_permute_step(T x, T mask, size_t shift) {
194 /*
195 See https://reflectionsonsecurity.wordpress.com/2014/05/11/efficient-bit-permutation-using-delta-swaps/
196 and http://programming.sirrida.de/bit_perm.html
197 */
198 const T swap = ((x >> shift) ^ x) & mask;
199 return (x ^ swap) ^ (swap << shift);
200}
201
202template <std::unsigned_integral T>
203BOTAN_FORCE_INLINE constexpr void swap_bits(T& x, T& y, T mask, size_t shift) {
204 const T swap = ((x >> shift) ^ y) & mask;
205 x ^= swap << shift;
206 y ^= swap;
207}
208
209/**
210* Bitwise selection
211*
212* If mask is |1| returns a
213* If mask is |0| returns b
214* If mask is some other value returns a or b depending on the bit
215*/
216template <std::unsigned_integral T>
217BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b) {
218 //return (mask & a) | (~mask & b);
219 return (b ^ (mask & (a ^ b)));
220}
221
222template <std::unsigned_integral T>
223BOTAN_FORCE_INLINE constexpr T majority(T a, T b, T c) {
224 /*
225 Considering each bit of a, b, c individually
226
227 If a xor b is set, then c is the deciding vote.
228
229 If a xor b is not set then either a and b are both set or both unset.
230 In either case the value of c doesn't matter, and examining b (or a)
231 allows us to determine which case we are in.
232 */
233 return choose(a ^ b, c, b);
234}
235
236/**
237 * @returns the reversed bits in @p b.
238 */
239template <std::unsigned_integral T>
240inline constexpr T ct_reverse_bits(T b) {
241 const auto extend = [](uint8_t m) -> T {
242 T mask = 0;
243 for(size_t i = 0; i < sizeof(T); ++i) {
244 mask |= T(m) << i * 8;
245 }
246 return mask;
247 };
248
249 // First reverse bits in each byte...
250 // From: https://stackoverflow.com/a/2602885
251 b = (b & extend(0xF0)) >> 4 | (b & extend(0x0F)) << 4;
252 b = (b & extend(0xCC)) >> 2 | (b & extend(0x33)) << 2;
253 b = (b & extend(0xAA)) >> 1 | (b & extend(0x55)) << 1;
254
255 // ... then swap the bytes
256 return reverse_bytes(b);
257}
258
259/**
260 * Calculates the number of 1-bits in an unsigned integer in constant-time.
261 * This operation is also known as "population count" or hamming weight.
262 *
263 * Modern compilers will recognize this pattern and replace it by a hardware
264 * instruction, if available. This is the SWAR (SIMD within a register)
265 * algorithm. See: https://nimrod.blog/posts/algorithms-behind-popcount/#swar-algorithm
266 *
267 * Note: C++20 provides std::popcount(), but there's no guarantee that this
268 * is implemented in constant-time.
269 *
270 * @param x an unsigned integer
271 * @returns the number of 1-bits in the provided value
272 */
273template <std::unsigned_integral T>
274BOTAN_FORCE_INLINE constexpr uint8_t ct_popcount(T x) {
275 constexpr size_t s = sizeof(T);
276 static_assert(s <= 8, "T is not a suitable unsigned integer value");
277 if constexpr(s == 8) {
278 x = x - ((x >> 1) & 0x5555555555555555);
279 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
280 x = (x + (x >> 4)) & 0xF0F0F0F0F0F0F0F;
281 return (x * 0x101010101010101) >> 56;
282 } else if constexpr(s == 4) {
283 x = x - ((x >> 1) & 0x55555555);
284 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
285 x = (x + (x >> 4)) & 0x0F0F0F0F;
286 return (x * 0x01010101) >> 24;
287 } else {
288 // s < 4
289 return ct_popcount(static_cast<uint32_t>(x));
290 }
291}
292
293/**
294* Compile-time polynomial multiplication in GF(2^8) modulo an irreducible
295* polynomial POLY
296*
297* When T is larger than a byte, the function computes the product of each byte
298* of T and returns the packed result.
299*
300* This function is intended only for use at compile-time, and in particular
301* should not be used with secret inputs.
302*
303* TODO(Botan4) this function should be consteval, but that hits bugs in
304* older versions of GCC and Clang.
305*/
306template <uint8_t POLY, std::unsigned_integral T>
307constexpr T poly_mul(T x, uint8_t y) {
308 // The constant 0x010101... as a T
309 constexpr T lo_bit = (static_cast<T>(-1) / 255);
310
311 // The constant 0x7F7F7F... as a T
312 constexpr T mask = static_cast<T>(~(lo_bit << 7));
313
314 constexpr T poly = POLY;
315
316 T r = 0;
317 while(x > 0 && y > 0) {
318 if((y & 1) != 0) {
319 r ^= x;
320 }
321 const T carry = ((x >> 7) & lo_bit) * poly;
322 x = ((x & mask) << 1) ^ carry;
323 y >>= 1;
324 }
325 return r;
326}
327
328} // namespace Botan
329
330#endif
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
constexpr T value_barrier(T x)
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:62
BOTAN_FORCE_INLINE constexpr T floor_log2(T n)
Definition bit_ops.h:134
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
Definition bit_ops.h:167
BOTAN_FORCE_INLINE constexpr T majority(T a, T b, T c)
Definition bit_ops.h:223
BOTAN_FORCE_INLINE constexpr void swap_bits(T &x, T &y, T mask, size_t shift)
Definition bit_ops.h:203
constexpr T ct_reverse_bits(T b)
Definition bit_ops.h:240
BOTAN_FORCE_INLINE constexpr T bit_permute_step(T x, T mask, size_t shift)
Definition bit_ops.h:193
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:140
BOTAN_FORCE_INLINE constexpr size_t significant_bytes(T n)
Definition bit_ops.h:94
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
Definition bit_ops.h:176
constexpr T reverse_bytes(T x)
Definition bswap.h:25
BOTAN_FORCE_INLINE constexpr size_t var_ctz64(uint64_t n)
Definition bit_ops.h:181
BOTAN_FORCE_INLINE constexpr uint8_t ct_popcount(T x)
Definition bit_ops.h:274
constexpr T poly_mul(T x, uint8_t y)
Definition bit_ops.h:307
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:217
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:73
BOTAN_FORCE_INLINE constexpr size_t ct_if_is_zero_ret(T x, size_t s)
Definition bit_ops.h:45
BOTAN_FORCE_INLINE constexpr T ct_expand_top_bit(T a)
Definition bit_ops.h:28
BOTAN_FORCE_INLINE constexpr size_t ctz(T n)
Definition bit_ops.h:115
BOTAN_FORCE_INLINE constexpr T ct_is_zero(T x)
Definition bit_ops.h:37