/src/botan/build/include/botan/internal/bit_ops.h
Line | Count | Source (jump to first uncovered line) |
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 constexpr T expand_top_bit(T a) |
24 | 9.46G | { |
25 | 9.46G | return static_cast<T>(0) - (a >> (sizeof(T)*8-1)); |
26 | 9.46G | } unsigned long Botan::expand_top_bit<unsigned long>(unsigned long) Line | Count | Source | 24 | 9.39G | { | 25 | 9.39G | return static_cast<T>(0) - (a >> (sizeof(T)*8-1)); | 26 | 9.39G | } |
unsigned char Botan::expand_top_bit<unsigned char>(unsigned char) Line | Count | Source | 24 | 72.4M | { | 25 | 72.4M | return static_cast<T>(0) - (a >> (sizeof(T)*8-1)); | 26 | 72.4M | } |
unsigned int Botan::expand_top_bit<unsigned int>(unsigned int) Line | Count | Source | 24 | 937k | { | 25 | 937k | return static_cast<T>(0) - (a >> (sizeof(T)*8-1)); | 26 | 937k | } |
unsigned short Botan::expand_top_bit<unsigned short>(unsigned short) Line | Count | Source | 24 | 68.3k | { | 25 | 68.3k | return static_cast<T>(0) - (a >> (sizeof(T)*8-1)); | 26 | 68.3k | } |
int Botan::expand_top_bit<int>(int) Line | Count | Source | 24 | 126 | { | 25 | 126 | return static_cast<T>(0) - (a >> (sizeof(T)*8-1)); | 26 | 126 | } |
|
27 | | |
28 | | /** |
29 | | * If arg is zero, return ~0. Otherwise return 0 |
30 | | */ |
31 | | template<typename T> |
32 | | inline constexpr T ct_is_zero(T x) |
33 | 8.13G | { |
34 | 8.13G | return expand_top_bit<T>(~x & (x - 1)); |
35 | 8.13G | } unsigned long Botan::ct_is_zero<unsigned long>(unsigned long) Line | Count | Source | 33 | 8.09G | { | 34 | 8.09G | return expand_top_bit<T>(~x & (x - 1)); | 35 | 8.09G | } |
unsigned char Botan::ct_is_zero<unsigned char>(unsigned char) Line | Count | Source | 33 | 37.1M | { | 34 | 37.1M | return expand_top_bit<T>(~x & (x - 1)); | 35 | 37.1M | } |
unsigned int Botan::ct_is_zero<unsigned int>(unsigned int) Line | Count | Source | 33 | 225k | { | 34 | 225k | return expand_top_bit<T>(~x & (x - 1)); | 35 | 225k | } |
unsigned short Botan::ct_is_zero<unsigned short>(unsigned short) Line | Count | Source | 33 | 34.0k | { | 34 | 34.0k | return expand_top_bit<T>(~x & (x - 1)); | 35 | 34.0k | } |
int Botan::ct_is_zero<int>(int) Line | Count | Source | 33 | 126 | { | 34 | 126 | return expand_top_bit<T>(~x & (x - 1)); | 35 | 126 | } |
|
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 | 6.95M | { |
45 | 6.95M | return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0); |
46 | 6.95M | } |
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 constexpr size_t high_bit(T n) |
56 | 7.59M | { |
57 | 7.59M | size_t hb = 0; |
58 | | |
59 | 53.1M | for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2) |
60 | 45.5M | { |
61 | 45.5M | const size_t z = s * ((~ct_is_zero(n >> s)) & 1); |
62 | 45.5M | hb += z; |
63 | 45.5M | n >>= z; |
64 | 45.5M | } |
65 | | |
66 | 7.59M | hb += n; |
67 | | |
68 | 7.59M | return hb; |
69 | 7.59M | } unsigned long Botan::high_bit<unsigned long>(unsigned long) Line | Count | Source | 56 | 7.55M | { | 57 | 7.55M | size_t hb = 0; | 58 | | | 59 | 52.8M | for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2) | 60 | 45.3M | { | 61 | 45.3M | const size_t z = s * ((~ct_is_zero(n >> s)) & 1); | 62 | 45.3M | hb += z; | 63 | 45.3M | n >>= z; | 64 | 45.3M | } | 65 | | | 66 | 7.55M | hb += n; | 67 | | | 68 | 7.55M | return hb; | 69 | 7.55M | } |
unsigned long Botan::high_bit<unsigned int>(unsigned int) Line | Count | Source | 56 | 45.0k | { | 57 | 45.0k | size_t hb = 0; | 58 | | | 59 | 270k | for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2) | 60 | 225k | { | 61 | 225k | const size_t z = s * ((~ct_is_zero(n >> s)) & 1); | 62 | 225k | hb += z; | 63 | 225k | n >>= z; | 64 | 225k | } | 65 | | | 66 | 45.0k | hb += n; | 67 | | | 68 | 45.0k | return hb; | 69 | 45.0k | } |
unsigned long Botan::high_bit<unsigned char>(unsigned char) Line | Count | Source | 56 | 42 | { | 57 | 42 | size_t hb = 0; | 58 | | | 59 | 168 | for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2) | 60 | 126 | { | 61 | 126 | const size_t z = s * ((~ct_is_zero(n >> s)) & 1); | 62 | 126 | hb += z; | 63 | 126 | n >>= z; | 64 | 126 | } | 65 | | | 66 | 42 | hb += n; | 67 | | | 68 | 42 | return hb; | 69 | 42 | } |
Unexecuted instantiation: unsigned long Botan::high_bit<unsigned short>(unsigned short) |
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 constexpr size_t significant_bytes(T n) |
78 | 43.5k | { |
79 | 43.5k | size_t b = 0; |
80 | | |
81 | 174k | for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2) |
82 | 130k | { |
83 | 130k | const size_t z = s * (~ct_is_zero(n >> s) & 1); |
84 | 130k | b += z/8; |
85 | 130k | n >>= z; |
86 | 130k | } |
87 | | |
88 | 43.5k | b += (n != 0); |
89 | | |
90 | 43.5k | return b; |
91 | 43.5k | } |
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 constexpr size_t ctz(T n) |
100 | 60.3M | { |
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 | 60.3M | size_t lb = ct_is_zero(n) & 1; |
106 | | |
107 | 422M | for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2) |
108 | 361M | { |
109 | 361M | const T mask = (static_cast<T>(1) << s) - 1; |
110 | 361M | const size_t z = s * (ct_is_zero(n & mask) & 1); |
111 | 361M | lb += z; |
112 | 361M | n >>= z; |
113 | 361M | } |
114 | | |
115 | 60.3M | return lb; |
116 | 60.3M | } unsigned long Botan::ctz<unsigned long>(unsigned long) Line | Count | Source | 100 | 60.3M | { | 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 | 60.3M | size_t lb = ct_is_zero(n) & 1; | 106 | | | 107 | 422M | for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2) | 108 | 361M | { | 109 | 361M | const T mask = (static_cast<T>(1) << s) - 1; | 110 | 361M | const size_t z = s * (ct_is_zero(n & mask) & 1); | 111 | 361M | lb += z; | 112 | 361M | n >>= z; | 113 | 361M | } | 114 | | | 115 | 60.3M | return lb; | 116 | 60.3M | } |
Unexecuted instantiation: unsigned long Botan::ctz<unsigned int>(unsigned int) |
117 | | |
118 | | template<typename T> |
119 | | constexpr uint8_t ceil_log2(T x) |
120 | 124k | { |
121 | 124k | static_assert(sizeof(T) < 32, "Abnormally large scalar"); |
122 | | |
123 | 124k | if(x >> (sizeof(T)*8-1)) |
124 | 0 | return sizeof(T)*8; |
125 | | |
126 | 124k | uint8_t result = 0; |
127 | 124k | T compare = 1; |
128 | | |
129 | 876k | while(compare < x) |
130 | 752k | { |
131 | 752k | compare <<= 1; |
132 | 752k | result++; |
133 | 752k | } |
134 | | |
135 | 124k | return result; |
136 | 124k | } |
137 | | |
138 | | // Potentially variable time ctz used for OCB |
139 | | inline constexpr size_t var_ctz32(uint32_t n) |
140 | 646 | { |
141 | 646 | #if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG) |
142 | 646 | if(n == 0) |
143 | 0 | return 32; |
144 | 646 | return __builtin_ctz(n); |
145 | | #else |
146 | | return ctz<uint32_t>(n); |
147 | | #endif |
148 | 646 | } |
149 | | |
150 | | template<typename T> |
151 | | inline constexpr T bit_permute_step(T x, T mask, size_t shift) |
152 | 0 | { |
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 | 0 | const T swap = ((x >> shift) ^ x) & mask; |
158 | 0 | return (x ^ swap) ^ (swap << shift); |
159 | 0 | } |
160 | | |
161 | | template<typename T> |
162 | | inline constexpr void swap_bits(T& x, T& y, T mask, size_t shift) |
163 | 0 | { |
164 | 0 | const T swap = ((x >> shift) ^ y) & mask; |
165 | 0 | x ^= swap << shift; |
166 | 0 | y ^= swap; |
167 | 0 | } |
168 | | |
169 | | template<typename T> |
170 | | inline constexpr T choose(T mask, T a, T b) |
171 | 10.9G | { |
172 | | //return (mask & a) | (~mask & b); |
173 | 10.9G | return (b ^ (mask & (a ^ b))); |
174 | 10.9G | } unsigned long Botan::choose<unsigned long>(unsigned long, unsigned long, unsigned long) Line | Count | Source | 171 | 10.7G | { | 172 | | //return (mask & a) | (~mask & b); | 173 | 10.7G | return (b ^ (mask & (a ^ b))); | 174 | 10.7G | } |
unsigned char Botan::choose<unsigned char>(unsigned char, unsigned char, unsigned char) Line | Count | Source | 171 | 71.0M | { | 172 | | //return (mask & a) | (~mask & b); | 173 | 71.0M | return (b ^ (mask & (a ^ b))); | 174 | 71.0M | } |
unsigned int Botan::choose<unsigned int>(unsigned int, unsigned int, unsigned int) Line | Count | Source | 171 | 115M | { | 172 | | //return (mask & a) | (~mask & b); | 173 | 115M | return (b ^ (mask & (a ^ b))); | 174 | 115M | } |
Unexecuted instantiation: unsigned short Botan::choose<unsigned short>(unsigned short, unsigned short, unsigned short) |
175 | | |
176 | | template<typename T> |
177 | | inline constexpr T majority(T a, T b, T c) |
178 | 64.8M | { |
179 | | /* |
180 | | Considering each bit of a, b, c individually |
181 | | |
182 | | If a xor b is set, then c is the deciding vote. |
183 | | |
184 | | If a xor b is not set then either a and b are both set or both unset. |
185 | | In either case the value of c doesn't matter, and examining b (or a) |
186 | | allows us to determine which case we are in. |
187 | | */ |
188 | 64.8M | return choose(a ^ b, c, b); |
189 | 64.8M | } unsigned int Botan::majority<unsigned int>(unsigned int, unsigned int, unsigned int) Line | Count | Source | 178 | 57.2M | { | 179 | | /* | 180 | | Considering each bit of a, b, c individually | 181 | | | 182 | | If a xor b is set, then c is the deciding vote. | 183 | | | 184 | | If a xor b is not set then either a and b are both set or both unset. | 185 | | In either case the value of c doesn't matter, and examining b (or a) | 186 | | allows us to determine which case we are in. | 187 | | */ | 188 | 57.2M | return choose(a ^ b, c, b); | 189 | 57.2M | } |
unsigned long Botan::majority<unsigned long>(unsigned long, unsigned long, unsigned long) Line | Count | Source | 178 | 7.62M | { | 179 | | /* | 180 | | Considering each bit of a, b, c individually | 181 | | | 182 | | If a xor b is set, then c is the deciding vote. | 183 | | | 184 | | If a xor b is not set then either a and b are both set or both unset. | 185 | | In either case the value of c doesn't matter, and examining b (or a) | 186 | | allows us to determine which case we are in. | 187 | | */ | 188 | 7.62M | return choose(a ^ b, c, b); | 189 | 7.62M | } |
|
190 | | |
191 | | } |
192 | | |
193 | | #endif |