Botan 3.3.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
17namespace Botan {
18
19/**
20* If top bit of arg is set, return ~0. Otherwise return 0.
21*/
22template <typename T>
23inline constexpr T expand_top_bit(T a)
24 requires(std::is_integral<T>::value)
25{
26 return static_cast<T>(0) - (a >> (sizeof(T) * 8 - 1));
27}
28
29/**
30* If arg is zero, return ~0. Otherwise return 0
31*/
32template <typename T>
33inline constexpr T ct_is_zero(T x)
34 requires(std::is_integral<T>::value)
35{
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 <typename T>
45inline constexpr bool is_power_of_2(T arg)
46 requires(std::is_unsigned<T>::value)
47{
48 return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg - 1)) == 0);
49}
50
51/**
52* Return the index of the highest set bit
53* T is an unsigned integer type
54* @param n an integer value
55* @return index of the highest set bit in n
56*/
57template <typename T>
58inline constexpr size_t high_bit(T n)
59 requires(std::is_unsigned<T>::value)
60{
61 size_t hb = 0;
62
63 for(size_t s = 8 * sizeof(T) / 2; s > 0; s /= 2) {
64 const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
65 hb += z;
66 n >>= z;
67 }
68
69 hb += n;
70
71 return hb;
72}
73
74/**
75* Return the number of significant bytes in n
76* @param n an integer value
77* @return number of significant bytes in n
78*/
79template <typename T>
80inline constexpr size_t significant_bytes(T n)
81 requires(std::is_integral<T>::value)
82{
83 size_t b = 0;
84
85 for(size_t s = 8 * sizeof(n) / 2; s >= 8; s /= 2) {
86 const size_t z = s * (~ct_is_zero(n >> s) & 1);
87 b += z / 8;
88 n >>= z;
89 }
90
91 b += (n != 0);
92
93 return b;
94}
95
96/**
97* Count the trailing zero bits in n
98* @param n an integer value
99* @return maximum x st 2^x divides n
100*/
101template <typename T>
102inline constexpr size_t ctz(T n)
103 requires(std::is_integral<T>::value)
104{
105 /*
106 * If n == 0 then this function will compute 8*sizeof(T)-1, so
107 * initialize lb to 1 if n == 0 to produce the expected result.
108 */
109 size_t lb = ct_is_zero(n) & 1;
110
111 for(size_t s = 8 * sizeof(T) / 2; s > 0; s /= 2) {
112 const T mask = (static_cast<T>(1) << s) - 1;
113 const size_t z = s * (ct_is_zero(n & mask) & 1);
114 lb += z;
115 n >>= z;
116 }
117
118 return lb;
119}
120
121template <typename T>
122constexpr uint8_t ceil_log2(T x)
123 requires(std::is_integral<T>::value && sizeof(T) < 32)
124{
125 if(x >> (sizeof(T) * 8 - 1)) {
126 return sizeof(T) * 8;
127 }
128
129 uint8_t result = 0;
130 T compare = 1;
131
132 while(compare < x) {
133 compare <<= 1;
134 result++;
135 }
136
137 return result;
138}
139
140/**
141 * Return the number of bytes necessary to contain @p bits bits.
142 */
143template <typename T>
144inline constexpr T ceil_tobytes(T bits)
145 requires(std::is_integral<T>::value)
146{
147 return (bits + 7) / 8;
148}
149
150// Potentially variable time ctz used for OCB
151inline constexpr size_t var_ctz32(uint32_t n) {
152#if BOTAN_COMPILER_HAS_BUILTIN(__builtin_ctz)
153 if(n == 0) {
154 return 32;
155 }
156 return __builtin_ctz(n);
157#else
158 return ctz<uint32_t>(n);
159#endif
160}
161
162template <typename T>
163inline constexpr T bit_permute_step(T x, T mask, size_t shift) {
164 /*
165 See https://reflectionsonsecurity.wordpress.com/2014/05/11/efficient-bit-permutation-using-delta-swaps/
166 and http://programming.sirrida.de/bit_perm.html
167 */
168 const T swap = ((x >> shift) ^ x) & mask;
169 return (x ^ swap) ^ (swap << shift);
170}
171
172template <typename T>
173inline constexpr void swap_bits(T& x, T& y, T mask, size_t shift) {
174 const T swap = ((x >> shift) ^ y) & mask;
175 x ^= swap << shift;
176 y ^= swap;
177}
178
179template <typename T>
180inline constexpr T choose(T mask, T a, T b) {
181 //return (mask & a) | (~mask & b);
182 return (b ^ (mask & (a ^ b)));
183}
184
185template <typename T>
186inline constexpr T majority(T a, T b, T c) {
187 /*
188 Considering each bit of a, b, c individually
189
190 If a xor b is set, then c is the deciding vote.
191
192 If a xor b is not set then either a and b are both set or both unset.
193 In either case the value of c doesn't matter, and examining b (or a)
194 allows us to determine which case we are in.
195 */
196 return choose(a ^ b, c, b);
197}
198
199} // namespace Botan
200
201#endif
FE_25519 T
Definition ge.cpp:34
constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:45
constexpr size_t var_ctz32(uint32_t n)
Definition bit_ops.h:151
constexpr T choose(T mask, T a, T b)
Definition bit_ops.h:180
constexpr size_t high_bit(T n)
Definition bit_ops.h:58
constexpr void swap_bits(T &x, T &y, T mask, size_t shift)
Definition bit_ops.h:173
constexpr size_t ctz(T n)
Definition bit_ops.h:102
constexpr T majority(T a, T b, T c)
Definition bit_ops.h:186
constexpr T ceil_tobytes(T bits)
Definition bit_ops.h:144
constexpr T ct_is_zero(T x)
Definition bit_ops.h:33
constexpr size_t significant_bytes(T n)
Definition bit_ops.h:80
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:122
constexpr T expand_top_bit(T a)
Definition bit_ops.h:23
constexpr T bit_permute_step(T x, T mask, size_t shift)
Definition bit_ops.h:163