Coverage Report

Created: 2022-06-23 06:44

/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
12.3G
   {
25
12.3G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
12.3G
   }
unsigned long Botan::expand_top_bit<unsigned long>(unsigned long)
Line
Count
Source
24
12.3G
   {
25
12.3G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
12.3G
   }
unsigned char Botan::expand_top_bit<unsigned char>(unsigned char)
Line
Count
Source
24
69.8M
   {
25
69.8M
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
69.8M
   }
unsigned int Botan::expand_top_bit<unsigned int>(unsigned int)
Line
Count
Source
24
260k
   {
25
260k
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
260k
   }
int Botan::expand_top_bit<int>(int)
Line
Count
Source
24
102
   {
25
102
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
102
   }
unsigned short Botan::expand_top_bit<unsigned short>(unsigned short)
Line
Count
Source
24
94.1k
   {
25
94.1k
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
94.1k
   }
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
10.1G
   {
34
10.1G
   return expand_top_bit<T>(~x & (x - 1));
35
10.1G
   }
unsigned long Botan::ct_is_zero<unsigned long>(unsigned long)
Line
Count
Source
33
10.1G
   {
34
10.1G
   return expand_top_bit<T>(~x & (x - 1));
35
10.1G
   }
unsigned char Botan::ct_is_zero<unsigned char>(unsigned char)
Line
Count
Source
33
38.7M
   {
34
38.7M
   return expand_top_bit<T>(~x & (x - 1));
35
38.7M
   }
unsigned int Botan::ct_is_zero<unsigned int>(unsigned int)
Line
Count
Source
33
260k
   {
34
260k
   return expand_top_bit<T>(~x & (x - 1));
35
260k
   }
int Botan::ct_is_zero<int>(int)
Line
Count
Source
33
102
   {
34
102
   return expand_top_bit<T>(~x & (x - 1));
35
102
   }
unsigned short Botan::ct_is_zero<unsigned short>(unsigned short)
Line
Count
Source
33
46.9k
   {
34
46.9k
   return expand_top_bit<T>(~x & (x - 1));
35
46.9k
   }
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
8.35M
   {
45
8.35M
   return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0);
46
8.35M
   }
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
12.1M
   {
57
12.1M
   size_t hb = 0;
58
59
85.0M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
72.8M
      {
61
72.8M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
72.8M
      hb += z;
63
72.8M
      n >>= z;
64
72.8M
      }
65
66
12.1M
   hb += n;
67
68
12.1M
   return hb;
69
12.1M
   }
unsigned long Botan::high_bit<unsigned long>(unsigned long)
Line
Count
Source
56
12.1M
   {
57
12.1M
   size_t hb = 0;
58
59
84.7M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
72.6M
      {
61
72.6M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
72.6M
      hb += z;
63
72.6M
      n >>= z;
64
72.6M
      }
65
66
12.1M
   hb += n;
67
68
12.1M
   return hb;
69
12.1M
   }
unsigned long Botan::high_bit<unsigned int>(unsigned int)
Line
Count
Source
56
52.0k
   {
57
52.0k
   size_t hb = 0;
58
59
312k
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
260k
      {
61
260k
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
260k
      hb += z;
63
260k
      n >>= z;
64
260k
      }
65
66
52.0k
   hb += n;
67
68
52.0k
   return hb;
69
52.0k
   }
unsigned long Botan::high_bit<unsigned char>(unsigned char)
Line
Count
Source
56
34
   {
57
34
   size_t hb = 0;
58
59
136
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
102
      {
61
102
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
102
      hb += z;
63
102
      n >>= z;
64
102
      }
65
66
34
   hb += n;
67
68
34
   return hb;
69
34
   }
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
45.7k
   {
79
45.7k
   size_t b = 0;
80
81
183k
   for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
82
137k
      {
83
137k
      const size_t z = s * (~ct_is_zero(n >> s) & 1);
84
137k
      b += z/8;
85
137k
      n >>= z;
86
137k
      }
87
88
45.7k
   b += (n != 0);
89
90
45.7k
   return b;
91
45.7k
   }
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
70.9M
   {
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
70.9M
   size_t lb = ct_is_zero(n) & 1;
106
107
496M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
425M
      {
109
425M
      const T mask = (static_cast<T>(1) << s) - 1;
110
425M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
425M
      lb += z;
112
425M
      n >>= z;
113
425M
      }
114
115
70.9M
   return lb;
116
70.9M
   }
unsigned long Botan::ctz<unsigned long>(unsigned long)
Line
Count
Source
100
70.9M
   {
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
70.9M
   size_t lb = ct_is_zero(n) & 1;
106
107
496M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
425M
      {
109
425M
      const T mask = (static_cast<T>(1) << s) - 1;
110
425M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
425M
      lb += z;
112
425M
      n >>= z;
113
425M
      }
114
115
70.9M
   return lb;
116
70.9M
   }
Unexecuted instantiation: unsigned long Botan::ctz<unsigned int>(unsigned int)
117
118
template<typename T>
119
constexpr uint8_t ceil_log2(T x)
120
107k
   {
121
107k
   static_assert(sizeof(T) < 32, "Abnormally large scalar");
122
123
107k
   if(x >> (sizeof(T)*8-1))
124
0
      return sizeof(T)*8;
125
126
107k
   uint8_t result = 0;
127
107k
   T compare = 1;
128
129
757k
   while(compare < x)
130
649k
      {
131
649k
      compare <<= 1;
132
649k
      result++;
133
649k
      }
134
135
107k
   return result;
136
107k
   }
137
138
// Potentially variable time ctz used for OCB
139
inline constexpr size_t var_ctz32(uint32_t n)
140
1.04k
   {
141
1.04k
#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
142
1.04k
   if(n == 0)
143
0
      return 32;
144
1.04k
   return __builtin_ctz(n);
145
#else
146
   return ctz<uint32_t>(n);
147
#endif
148
1.04k
   }
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
13.9G
   {
172
   //return (mask & a) | (~mask & b);
173
13.9G
   return (b ^ (mask & (a ^ b)));
174
13.9G
   }
unsigned long Botan::choose<unsigned long>(unsigned long, unsigned long, unsigned long)
Line
Count
Source
171
13.7G
   {
172
   //return (mask & a) | (~mask & b);
173
13.7G
   return (b ^ (mask & (a ^ b)));
174
13.7G
   }
unsigned char Botan::choose<unsigned char>(unsigned char, unsigned char, unsigned char)
Line
Count
Source
171
68.5M
   {
172
   //return (mask & a) | (~mask & b);
173
68.5M
   return (b ^ (mask & (a ^ b)));
174
68.5M
   }
unsigned int Botan::choose<unsigned int>(unsigned int, unsigned int, unsigned int)
Line
Count
Source
171
125M
   {
172
   //return (mask & a) | (~mask & b);
173
125M
   return (b ^ (mask & (a ^ b)));
174
125M
   }
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
74.0M
   {
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
74.0M
   return choose(a ^ b, c, b);
189
74.0M
   }
unsigned int Botan::majority<unsigned int>(unsigned int, unsigned int, unsigned int)
Line
Count
Source
178
62.6M
   {
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
62.6M
   return choose(a ^ b, c, b);
189
62.6M
   }
unsigned long Botan::majority<unsigned long>(unsigned long, unsigned long, unsigned long)
Line
Count
Source
178
11.4M
   {
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
11.4M
   return choose(a ^ b, c, b);
189
11.4M
   }
190
191
}
192
193
#endif