12#ifndef BOTAN_BIT_OPS_H_
13#define BOTAN_BIT_OPS_H_
15#include <botan/types.h>
17#include <botan/compiler.h>
18#include <botan/internal/bswap.h>
19#include <botan/internal/value_barrier.h>
27template <std::
unsigned_
integral T>
30 return static_cast<T
>(0) - top;
36template <std::
unsigned_
integral T>
44template <std::
unsigned_
integral T>
50 const T a = ~x & (x - 1);
52 const size_t mask =
static_cast<size_t>(0) - a_top;
61template <std::
unsigned_
integral T>
63 return (arg != 0) && (arg != 1) && ((arg &
static_cast<T
>(arg - 1)) == 0);
72template <std::
unsigned_
integral T>
76 for(
size_t s = 8 *
sizeof(T) / 2; s > 0; s /= 2) {
83 hb +=
static_cast<size_t>(n);
93template <std::
unsigned_
integral T>
97 for(
size_t s = 8 *
sizeof(T) / 2; s >= 8; s /= 2) {
114template <std::
unsigned_
integral T>
122 for(
size_t s = 8 *
sizeof(T) / 2; s > 0; s /= 2) {
123 const T range = (
static_cast<T
>(1) << s) - 1;
133template <std::
unsigned_
integral T>
136 return static_cast<T
>(
high_bit(n) - 1);
139template <std::
unsigned_
integral T>
141 requires(
sizeof(T) < 32)
143 if(x >> (
sizeof(T) * 8 - 1)) {
144 return sizeof(T) * 8;
166template <std::
unsigned_
integral T>
169 return a / b + ((a % b != 0) ? 1 : 0);
175template <std::
unsigned_
integral T>
177 return (bits + 7) / 8;
182#if BOTAN_COMPILER_HAS_BUILTIN(__builtin_ctzll)
186 return __builtin_ctzll(n);
192template <std::
unsigned_
integral T>
198 const T swap = ((x >> shift) ^ x) & mask;
199 return (x ^ swap) ^ (swap << shift);
202template <std::
unsigned_
integral T>
204 const T swap = ((x >> shift) ^ y) & mask;
216template <std::
unsigned_
integral T>
219 return (b ^ (mask & (a ^ b)));
222template <std::
unsigned_
integral T>
233 return choose(a ^ b, c, b);
239template <std::
unsigned_
integral T>
241 const auto extend = [](uint8_t m) -> T {
243 for(
size_t i = 0; i <
sizeof(T); ++i) {
244 mask |= T(m) << i * 8;
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;
273template <std::
unsigned_
integral T>
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;
306template <u
int8_t POLY, std::
unsigned_
integral T>
309 constexpr T lo_bit = (
static_cast<T
>(-1) / 255);
312 constexpr T mask =
static_cast<T
>(~(lo_bit << 7));
314 constexpr T poly = POLY;
317 while(x > 0 && y > 0) {
321 const T carry = ((x >> 7) & lo_bit) * poly;
322 x = ((x & mask) << 1) ^ carry;
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_FORCE_INLINE
constexpr T value_barrier(T x)
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
BOTAN_FORCE_INLINE constexpr T floor_log2(T n)
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
BOTAN_FORCE_INLINE constexpr T majority(T a, T b, T c)
BOTAN_FORCE_INLINE constexpr void swap_bits(T &x, T &y, T mask, size_t shift)
constexpr T ct_reverse_bits(T b)
BOTAN_FORCE_INLINE constexpr T bit_permute_step(T x, T mask, size_t shift)
constexpr uint8_t ceil_log2(T x)
BOTAN_FORCE_INLINE constexpr size_t significant_bytes(T n)
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
constexpr T reverse_bytes(T x)
BOTAN_FORCE_INLINE constexpr size_t var_ctz64(uint64_t n)
BOTAN_FORCE_INLINE constexpr uint8_t ct_popcount(T x)
constexpr T poly_mul(T x, uint8_t y)
BOTAN_FORCE_INLINE constexpr T choose(T mask, T a, T b)
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
BOTAN_FORCE_INLINE constexpr size_t ct_if_is_zero_ret(T x, size_t s)
BOTAN_FORCE_INLINE constexpr T ct_expand_top_bit(T a)
BOTAN_FORCE_INLINE constexpr size_t ctz(T n)
BOTAN_FORCE_INLINE constexpr T ct_is_zero(T x)