Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 namespace Botan {
18
19 /**
20 * If top bit of arg is set, return ~0. Otherwise return 0.
21 */
22 template<typename T>
23 inline T expand_top_bit(T a)
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 */
31 template<typename T>
32 inline 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 */
42 template<typename T>
43 inline 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 */
54 template<typename T>
55 inline 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 */
76 template<typename T>
77 inline 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 */
98 template<typename T>
99 inline 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
118 template<typename T>
119 uint8_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
139 inline 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
150 }
151
152 #endif
Botan::ctz
size_t ctz(T n)
Definition: bit_ops.h:99
Botan::var_ctz32
size_t var_ctz32(uint32_t n)
Definition: bit_ops.h:139
Botan::significant_bytes
size_t significant_bytes(T n)
Definition: bit_ops.h:77
Botan::expand_top_bit
T expand_top_bit(T a)
Definition: bit_ops.h:23
Botan::is_power_of_2
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
Botan::ct_is_zero
T ct_is_zero(T x)
Definition: bit_ops.h:32
Botan::high_bit
size_t high_bit(T n)
Definition: bit_ops.h:55
Botan
Definition: alg_id.cpp:13
T
fe T
Definition: ge.cpp:37
Botan::ceil_log2
uint8_t ceil_log2(T x)
Definition: bit_ops.h:119