Botan 2.19.2
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>
24 {
25 return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26 }
27
28/**
29* If arg is zero, return ~0. Otherwise return 0
30*/
31template<typename T>
32inline T ct_is_zero(T x)
33 {
34 return expand_top_bit<T>(~x & (x - 1));
35 }
36
37/**
38* Power of 2 test. T should be an unsigned integer type
39* @param arg an integer value
40* @return true iff arg is 2^n for some n > 0
41*/
42template<typename T>
43inline constexpr bool is_power_of_2(T arg)
44 {
45 return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0);
46 }
47
48/**
49* Return the index of the highest set bit
50* T is an unsigned integer type
51* @param n an integer value
52* @return index of the highest set bit in n
53*/
54template<typename T>
55inline size_t high_bit(T n)
56 {
57 size_t hb = 0;
58
59 for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60 {
61 const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62 hb += z;
63 n >>= z;
64 }
65
66 hb += n;
67
68 return hb;
69 }
70
71/**
72* Return the number of significant bytes in n
73* @param n an integer value
74* @return number of significant bytes in n
75*/
76template<typename T>
77inline size_t significant_bytes(T n)
78 {
79 size_t b = 0;
80
81 for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
82 {
83 const size_t z = s * (~ct_is_zero(n >> s) & 1);
84 b += z/8;
85 n >>= z;
86 }
87
88 b += (n != 0);
89
90 return b;
91 }
92
93/**
94* Count the trailing zero bits in n
95* @param n an integer value
96* @return maximum x st 2^x divides n
97*/
98template<typename T>
99inline size_t ctz(T n)
100 {
101 /*
102 * If n == 0 then this function will compute 8*sizeof(T)-1, so
103 * initialize lb to 1 if n == 0 to produce the expected result.
104 */
105 size_t lb = ct_is_zero(n) & 1;
106
107 for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108 {
109 const T mask = (static_cast<T>(1) << s) - 1;
110 const size_t z = s * (ct_is_zero(n & mask) & 1);
111 lb += z;
112 n >>= z;
113 }
114
115 return lb;
116 }
117
118template<typename T>
119uint8_t ceil_log2(T x)
120 {
121 static_assert(sizeof(T) < 32, "Abnormally large scalar");
122
123 if(x >> (sizeof(T)*8-1))
124 return sizeof(T)*8;
125
126 uint8_t result = 0;
127 T compare = 1;
128
129 while(compare < x)
130 {
131 compare <<= 1;
132 result++;
133 }
134
135 return result;
136 }
137
138// Potentially variable time ctz used for OCB
139inline size_t var_ctz32(uint32_t n)
140 {
141#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
142 if(n == 0)
143 return 32;
144 return __builtin_ctz(n);
145#else
146 return ctz<uint32_t>(n);
147#endif
148 }
149
150template<typename T>
151inline T bit_permute_step(T x, T mask, size_t shift)
152 {
153 /*
154 See https://reflectionsonsecurity.wordpress.com/2014/05/11/efficient-bit-permutation-using-delta-swaps/
155 and http://programming.sirrida.de/bit_perm.html
156 */
157 const T swap = ((x >> shift) ^ x) & mask;
158 return (x ^ swap) ^ (swap << shift);
159 }
160
161template<typename T>
162inline void swap_bits(T& x, T& y, T mask, size_t shift)
163 {
164 const T swap = ((x >> shift) ^ y) & mask;
165 x ^= swap << shift;
166 y ^= swap;
167 }
168
169}
170
171#endif
fe T
Definition: ge.cpp:37
Definition: alg_id.cpp:13
T expand_top_bit(T a)
Definition: bit_ops.h:23
uint8_t ceil_log2(T x)
Definition: bit_ops.h:119
T bit_permute_step(T x, T mask, size_t shift)
Definition: bit_ops.h:151
void swap_bits(T &x, T &y, T mask, size_t shift)
Definition: bit_ops.h:162
size_t ctz(T n)
Definition: bit_ops.h:99
size_t var_ctz32(uint32_t n)
Definition: bit_ops.h:139
size_t significant_bytes(T n)
Definition: bit_ops.h:77
size_t high_bit(T n)
Definition: bit_ops.h:55
T ct_is_zero(T x)
Definition: bit_ops.h:32
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43