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