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>
26template <std::
unsigned_
integral T>
28 return static_cast<T
>(0) - (a >> (
sizeof(T) * 8 - 1));
34template <std::
unsigned_
integral T>
44template <std::
unsigned_
integral T>
46 return (arg != 0) && (arg != 1) && ((arg &
static_cast<T
>(arg - 1)) == 0);
55template <std::
unsigned_
integral T>
59 for(
size_t s = 8 *
sizeof(T) / 2; s > 0; s /= 2) {
75template <std::
unsigned_
integral T>
79 for(
size_t s = 8 *
sizeof(T) / 2; s >= 8; s /= 2) {
95template <std::
unsigned_
integral T>
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);
113template <std::
unsigned_
integral T>
116 return static_cast<T
>(
high_bit(n) - 1);
119template <std::
unsigned_
integral T>
121 requires(
sizeof(T) < 32)
123 if(x >> (
sizeof(T) * 8 - 1)) {
124 return sizeof(T) * 8;
146template <std::
unsigned_
integral T>
148 return (a + b - 1) / b;
154template <std::
unsigned_
integral T>
156 return (bits + 7) / 8;
161#if BOTAN_COMPILER_HAS_BUILTIN(__builtin_ctz)
165 return __builtin_ctz(n);
171template <std::
unsigned_
integral T>
177 const T swap = ((x >> shift) ^ x) & mask;
178 return (x ^ swap) ^ (swap << shift);
181template <std::
unsigned_
integral T>
183 const T swap = ((x >> shift) ^ y) & mask;
195template <std::
unsigned_
integral T>
198 return (b ^ (mask & (a ^ b)));
201template <std::
unsigned_
integral T>
212 return choose(a ^ b, c, b);
218template <std::
unsigned_
integral T>
220 auto extend = [](uint8_t m) -> T {
222 for(
size_t i = 0; i <
sizeof(T); ++i) {
223 mask |= T(m) << i * 8;
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;
252template <std::
unsigned_
integral T>
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;
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_FORCE_INLINE
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)
BOTAN_FORCE_INLINE constexpr size_t var_ctz32(uint32_t n)
constexpr uint8_t ceil_log2(T x)
BOTAN_FORCE_INLINE constexpr size_t significant_bytes(T n)
constexpr T reverse_bytes(T x)
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
BOTAN_FORCE_INLINE constexpr uint8_t ct_popcount(T x)
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 ctz(T n)
BOTAN_FORCE_INLINE constexpr T ct_is_zero(T x)
BOTAN_FORCE_INLINE constexpr T expand_top_bit(T a)