Botan 3.9.0
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 <concepts>
20
21namespace Botan {
22
23/**
24* If top bit of arg is set, return ~0. Otherwise return 0.
25*/
26template <std::unsigned_integral T>
28 return static_cast<T>(0) - (a >> (sizeof(T) * 8 - 1));
29}
30
31/**
32* If arg is zero, return ~0. Otherwise return 0
33*/
34template <std::unsigned_integral T>
36 return expand_top_bit<T>(~x & (x - 1));
37}
38
39/**
40* Power of 2 test. T should be an unsigned integer type
41* @param arg an integer value
42* @return true iff arg is 2^n for some n > 0
43*/
44template <std::unsigned_integral T>
45BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg) {
46 return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg - 1)) == 0);
47}
48
49/**
50* Return the index of the highest set bit
51* T is an unsigned integer type
52* @param n an integer value
53* @return index of the highest set bit in n
54*/
55template <std::unsigned_integral T>
56BOTAN_FORCE_INLINE constexpr size_t high_bit(T n) {
57 size_t hb = 0;
58
59 for(size_t s = 8 * sizeof(T) / 2; s > 0; s /= 2) {
60 const size_t z = s * ((~ct_is_zero<T>(n >> s)) & 1);
61 hb += z;
62 n >>= z;
63 }
64
65 hb += n;
66
67 return hb;
68}
69
70/**
71* Return the number of significant bytes in n
72* @param n an integer value
73* @return number of significant bytes in n
74*/
75template <std::unsigned_integral T>
77 size_t b = 0;
78
79 for(size_t s = 8 * sizeof(T) / 2; s >= 8; s /= 2) {
80 const size_t z = s * (~ct_is_zero(n >> s) & 1);
81 b += z / 8;
82 n >>= z;
83 }
84
85 b += (n != 0);
86
87 return b;
88}
89
90/**
91* Count the trailing zero bits in n
92* @param n an integer value
93* @return maximum x st 2^x divides n
94*/
95template <std::unsigned_integral T>
96BOTAN_FORCE_INLINE constexpr size_t ctz(T n) {
97 /*
98 * If n == 0 then this function will compute 8*sizeof(T)-1, so
99 * initialize lb to 1 if n == 0 to produce the expected result.
100 */
101 size_t lb = ct_is_zero(n) & 1;
102
103 for(size_t s = 8 * sizeof(T) / 2; s > 0; s /= 2) {
104 const T mask = (static_cast<T>(1) << s) - 1;
105 const size_t z = s * (ct_is_zero(n & mask) & 1);
106 lb += z;
107 n >>= z;
108 }
109
110 return lb;
111}
112
113template <std::unsigned_integral T>
115 BOTAN_ARG_CHECK(n != 0, "log2(0) is not defined");
116 return static_cast<T>(high_bit(n) - 1);
117}
118
119template <std::unsigned_integral T>
120constexpr uint8_t ceil_log2(T x)
121 requires(sizeof(T) < 32)
122{
123 if(x >> (sizeof(T) * 8 - 1)) {
124 return sizeof(T) * 8;
125 }
126
127 uint8_t result = 0;
128 T compare = 1;
129
130 while(compare < x) {
131 compare <<= 1;
132 result++;
133 }
134
135 return result;
136}
137
138/**
139 * Ceil of an unsigned integer division. @p b must not be zero.
140 *
141 * @param a divident
142 * @param b divisor
143 *
144 * @returns ceil(a/b)
145 */
146template <std::unsigned_integral T>
147BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b) {
148 return (a + b - 1) / b;
149}
150
151/**
152 * Return the number of bytes necessary to contain @p bits bits.
153 */
154template <std::unsigned_integral T>
155BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits) {
156 return (bits + 7) / 8;
157}
158
159// Potentially variable time ctz used for OCB
160BOTAN_FORCE_INLINE constexpr size_t var_ctz32(uint32_t n) {
161#if BOTAN_COMPILER_HAS_BUILTIN(__builtin_ctz)
162 if(n == 0) {
163 return 32;
164 }
165 return __builtin_ctz(n);
166#else
167 return ctz<uint32_t>(n);
168#endif
169}
170
171template <std::unsigned_integral T>
172BOTAN_FORCE_INLINE constexpr T bit_permute_step(T x, T mask, size_t shift) {
173 /*
174 See https://reflectionsonsecurity.wordpress.com/2014/05/11/efficient-bit-permutation-using-delta-swaps/
175 and http://programming.sirrida.de/bit_perm.html
176 */
177 const T swap = ((x >> shift) ^ x) & mask;
178 return (x ^ swap) ^ (swap << shift);
179}
180
181template <std::unsigned_integral T>
182BOTAN_FORCE_INLINE constexpr void swap_bits(T& x, T& y, T mask, size_t shift) {
183 const T swap = ((x >> shift) ^ y) & mask;
184 x ^= swap << shift;
185 y ^= swap;
186}
187
188/**
189* Bitwise selection
190*
191* If mask is |1| returns a
192* If mask is |0| returns b
193* If mask is some other value returns a or b depending on the bit
194*/
195template <std::unsigned_integral T>
196BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b) {
197 //return (mask & a) | (~mask & b);
198 return (b ^ (mask & (a ^ b)));
199}
200
201template <std::unsigned_integral T>
202BOTAN_FORCE_INLINE constexpr T majority(T a, T b, T c) {
203 /*
204 Considering each bit of a, b, c individually
205
206 If a xor b is set, then c is the deciding vote.
207
208 If a xor b is not set then either a and b are both set or both unset.
209 In either case the value of c doesn't matter, and examining b (or a)
210 allows us to determine which case we are in.
211 */
212 return choose(a ^ b, c, b);
213}
214
215/**
216 * @returns the reversed bits in @p b.
217 */
218template <std::unsigned_integral T>
219inline constexpr T ct_reverse_bits(T b) {
220 auto extend = [](uint8_t m) -> T {
221 T mask = 0;
222 for(size_t i = 0; i < sizeof(T); ++i) {
223 mask |= T(m) << i * 8;
224 }
225 return mask;
226 };
227
228 // First reverse bits in each byte...
229 // From: https://stackoverflow.com/a/2602885
230 b = (b & extend(0xF0)) >> 4 | (b & extend(0x0F)) << 4;
231 b = (b & extend(0xCC)) >> 2 | (b & extend(0x33)) << 2;
232 b = (b & extend(0xAA)) >> 1 | (b & extend(0x55)) << 1;
233
234 // ... then swap the bytes
235 return reverse_bytes(b);
236}
237
238/**
239 * Calculates the number of 1-bits in an unsigned integer in constant-time.
240 * This operation is also known as "population count" or hamming weight.
241 *
242 * Modern compilers will recognize this pattern and replace it by a hardware
243 * instruction, if available. This is the SWAR (SIMD within a register)
244 * algorithm. See: https://nimrod.blog/posts/algorithms-behind-popcount/#swar-algorithm
245 *
246 * Note: C++20 provides std::popcount(), but there's no guarantee that this
247 * is implemented in constant-time.
248 *
249 * @param x an unsigned integer
250 * @returns the number of 1-bits in the provided value
251 */
252template <std::unsigned_integral T>
253BOTAN_FORCE_INLINE constexpr uint8_t ct_popcount(T x) {
254 constexpr size_t s = sizeof(T);
255 static_assert(s <= 8, "T is not a suitable unsigned integer value");
256 if constexpr(s == 8) {
257 x = x - ((x >> 1) & 0x5555555555555555);
258 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
259 x = (x + (x >> 4)) & 0xF0F0F0F0F0F0F0F;
260 return (x * 0x101010101010101) >> 56;
261 } else if constexpr(s == 4) {
262 x = x - ((x >> 1) & 0x55555555);
263 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
264 x = (x + (x >> 4)) & 0x0F0F0F0F;
265 return (x * 0x01010101) >> 24;
266 } else {
267 // s < 4
268 return ct_popcount(static_cast<uint32_t>(x));
269 }
270}
271
272} // namespace Botan
273
274#endif
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_FORCE_INLINE
Definition compiler.h:87
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:45
BOTAN_FORCE_INLINE constexpr T floor_log2(T n)
Definition bit_ops.h:114
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
Definition bit_ops.h:147
BOTAN_FORCE_INLINE constexpr T majority(T a, T b, T c)
Definition bit_ops.h:202
BOTAN_FORCE_INLINE constexpr void swap_bits(T &x, T &y, T mask, size_t shift)
Definition bit_ops.h:182
constexpr T ct_reverse_bits(T b)
Definition bit_ops.h:219
BOTAN_FORCE_INLINE constexpr T bit_permute_step(T x, T mask, size_t shift)
Definition bit_ops.h:172
BOTAN_FORCE_INLINE constexpr size_t var_ctz32(uint32_t n)
Definition bit_ops.h:160
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:120
BOTAN_FORCE_INLINE constexpr size_t significant_bytes(T n)
Definition bit_ops.h:76
constexpr T reverse_bytes(T x)
Definition bswap.h:27
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
Definition bit_ops.h:155
BOTAN_FORCE_INLINE constexpr uint8_t ct_popcount(T x)
Definition bit_ops.h:253
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:196
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:56
BOTAN_FORCE_INLINE constexpr size_t ctz(T n)
Definition bit_ops.h:96
BOTAN_FORCE_INLINE constexpr T ct_is_zero(T x)
Definition bit_ops.h:35
BOTAN_FORCE_INLINE constexpr T expand_top_bit(T a)
Definition bit_ops.h:27