Coverage Report

Created: 2020-11-21 08:34

/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
11.6G
   {
25
11.6G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
11.6G
   }
unsigned long Botan::expand_top_bit<unsigned long>(unsigned long)
Line
Count
Source
24
11.5G
   {
25
11.5G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
11.5G
   }
unsigned char Botan::expand_top_bit<unsigned char>(unsigned char)
Line
Count
Source
24
22.8M
   {
25
22.8M
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
22.8M
   }
unsigned int Botan::expand_top_bit<unsigned int>(unsigned int)
Line
Count
Source
24
665k
   {
25
665k
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
665k
   }
int Botan::expand_top_bit<int>(int)
Line
Count
Source
24
138
   {
25
138
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
138
   }
unsigned short Botan::expand_top_bit<unsigned short>(unsigned short)
Line
Count
Source
24
149k
   {
25
149k
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
149k
   }
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.0G
   {
34
10.0G
   return expand_top_bit<T>(~x & (x - 1));
35
10.0G
   }
unsigned long Botan::ct_is_zero<unsigned long>(unsigned long)
Line
Count
Source
33
10.0G
   {
34
10.0G
   return expand_top_bit<T>(~x & (x - 1));
35
10.0G
   }
unsigned char Botan::ct_is_zero<unsigned char>(unsigned char)
Line
Count
Source
33
22.8M
   {
34
22.8M
   return expand_top_bit<T>(~x & (x - 1));
35
22.8M
   }
unsigned int Botan::ct_is_zero<unsigned int>(unsigned int)
Line
Count
Source
33
290k
   {
34
290k
   return expand_top_bit<T>(~x & (x - 1));
35
290k
   }
int Botan::ct_is_zero<int>(int)
Line
Count
Source
33
138
   {
34
138
   return expand_top_bit<T>(~x & (x - 1));
35
138
   }
unsigned short Botan::ct_is_zero<unsigned short>(unsigned short)
Line
Count
Source
33
74.8k
   {
34
74.8k
   return expand_top_bit<T>(~x & (x - 1));
35
74.8k
   }
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
7.13M
   {
45
7.13M
   return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0);
46
7.13M
   }
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.72M
   {
57
7.72M
   size_t hb = 0;
58
59
54.0M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
46.3M
      {
61
46.3M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
46.3M
      hb += z;
63
46.3M
      n >>= z;
64
46.3M
      }
65
66
7.72M
   hb += n;
67
68
7.72M
   return hb;
69
7.72M
   }
unsigned long Botan::high_bit<unsigned long>(unsigned long)
Line
Count
Source
56
7.67M
   {
57
7.67M
   size_t hb = 0;
58
59
53.7M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
46.0M
      {
61
46.0M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
46.0M
      hb += z;
63
46.0M
      n >>= z;
64
46.0M
      }
65
66
7.67M
   hb += n;
67
68
7.67M
   return hb;
69
7.67M
   }
unsigned long Botan::high_bit<unsigned int>(unsigned int)
Line
Count
Source
56
58.1k
   {
57
58.1k
   size_t hb = 0;
58
59
348k
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
290k
      {
61
290k
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
290k
      hb += z;
63
290k
      n >>= z;
64
290k
      }
65
66
58.1k
   hb += n;
67
68
58.1k
   return hb;
69
58.1k
   }
unsigned long Botan::high_bit<unsigned char>(unsigned char)
Line
Count
Source
56
46
   {
57
46
   size_t hb = 0;
58
59
184
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
138
      {
61
138
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
138
      hb += z;
63
138
      n >>= z;
64
138
      }
65
66
46
   hb += n;
67
68
46
   return hb;
69
46
   }
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
48.9k
   {
79
48.9k
   size_t b = 0;
80
81
195k
   for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
82
146k
      {
83
146k
      const size_t z = s * (~ct_is_zero(n >> s) & 1);
84
146k
      b += z/8;
85
146k
      n >>= z;
86
146k
      }
87
88
48.9k
   b += (n != 0);
89
90
48.9k
   return b;
91
48.9k
   }
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.4M
   {
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.4M
   size_t lb = ct_is_zero(n) & 1;
106
107
422M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
362M
      {
109
362M
      const T mask = (static_cast<T>(1) << s) - 1;
110
362M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
362M
      lb += z;
112
362M
      n >>= z;
113
362M
      }
114
115
60.4M
   return lb;
116
60.4M
   }
unsigned long Botan::ctz<unsigned long>(unsigned long)
Line
Count
Source
100
60.4M
   {
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.4M
   size_t lb = ct_is_zero(n) & 1;
106
107
422M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
362M
      {
109
362M
      const T mask = (static_cast<T>(1) << s) - 1;
110
362M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
362M
      lb += z;
112
362M
      n >>= z;
113
362M
      }
114
115
60.4M
   return lb;
116
60.4M
   }
Unexecuted instantiation: unsigned long Botan::ctz<unsigned int>(unsigned int)
117
118
template<typename T>
119
constexpr uint8_t ceil_log2(T x)
120
143k
   {
121
143k
   static_assert(sizeof(T) < 32, "Abnormally large scalar");
122
123
143k
   if(x >> (sizeof(T)*8-1))
124
0
      return sizeof(T)*8;
125
126
143k
   uint8_t result = 0;
127
143k
   T compare = 1;
128
129
1.01M
   while(compare < x)
130
871k
      {
131
871k
      compare <<= 1;
132
871k
      result++;
133
871k
      }
134
135
143k
   return result;
136
143k
   }
137
138
// Potentially variable time ctz used for OCB
139
inline constexpr size_t var_ctz32(uint32_t n)
140
4.61k
   {
141
4.61k
#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
142
4.61k
   if(n == 0)
143
0
      return 32;
144
4.61k
   return __builtin_ctz(n);
145
#else
146
   return ctz<uint32_t>(n);
147
#endif
148
4.61k
   }
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
}
170
171
#endif