Coverage Report

Created: 2020-06-30 13:58

/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 T expand_top_bit(T a)
24
10.7G
   {
25
10.7G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
10.7G
   }
unsigned long Botan::expand_top_bit<unsigned long>(unsigned long)
Line
Count
Source
24
10.7G
   {
25
10.7G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
10.7G
   }
unsigned char Botan::expand_top_bit<unsigned char>(unsigned char)
Line
Count
Source
24
20.6M
   {
25
20.6M
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
20.6M
   }
unsigned int Botan::expand_top_bit<unsigned int>(unsigned int)
Line
Count
Source
24
997k
   {
25
997k
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
997k
   }
int Botan::expand_top_bit<int>(int)
Line
Count
Source
24
153
   {
25
153
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
153
   }
unsigned short Botan::expand_top_bit<unsigned short>(unsigned short)
Line
Count
Source
24
152k
   {
25
152k
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
152k
   }
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
9.30G
   {
34
9.30G
   return expand_top_bit<T>(~x & (x - 1));
35
9.30G
   }
unsigned long Botan::ct_is_zero<unsigned long>(unsigned long)
Line
Count
Source
33
9.28G
   {
34
9.28G
   return expand_top_bit<T>(~x & (x - 1));
35
9.28G
   }
unsigned char Botan::ct_is_zero<unsigned char>(unsigned char)
Line
Count
Source
33
20.6M
   {
34
20.6M
   return expand_top_bit<T>(~x & (x - 1));
35
20.6M
   }
unsigned int Botan::ct_is_zero<unsigned int>(unsigned int)
Line
Count
Source
33
299k
   {
34
299k
   return expand_top_bit<T>(~x & (x - 1));
35
299k
   }
int Botan::ct_is_zero<int>(int)
Line
Count
Source
33
153
   {
34
153
   return expand_top_bit<T>(~x & (x - 1));
35
153
   }
unsigned short Botan::ct_is_zero<unsigned short>(unsigned short)
Line
Count
Source
33
76.1k
   {
34
76.1k
   return expand_top_bit<T>(~x & (x - 1));
35
76.1k
   }
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.80M
   {
45
8.80M
   return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0);
46
8.80M
   }
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
11.1M
   {
57
11.1M
   size_t hb = 0;
58
11.1M
59
77.8M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
66.7M
      {
61
66.7M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
66.7M
      hb += z;
63
66.7M
      n >>= z;
64
66.7M
      }
65
11.1M
66
11.1M
   hb += n;
67
11.1M
68
11.1M
   return hb;
69
11.1M
   }
unsigned long Botan::high_bit<unsigned long>(unsigned long)
Line
Count
Source
56
11.0M
   {
57
11.0M
   size_t hb = 0;
58
11.0M
59
77.5M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
66.4M
      {
61
66.4M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
66.4M
      hb += z;
63
66.4M
      n >>= z;
64
66.4M
      }
65
11.0M
66
11.0M
   hb += n;
67
11.0M
68
11.0M
   return hb;
69
11.0M
   }
unsigned long Botan::high_bit<unsigned int>(unsigned int)
Line
Count
Source
56
59.9k
   {
57
59.9k
   size_t hb = 0;
58
59.9k
59
359k
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
299k
      {
61
299k
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
299k
      hb += z;
63
299k
      n >>= z;
64
299k
      }
65
59.9k
66
59.9k
   hb += n;
67
59.9k
68
59.9k
   return hb;
69
59.9k
   }
Unexecuted instantiation: unsigned long Botan::high_bit<unsigned short>(unsigned short)
unsigned long Botan::high_bit<unsigned char>(unsigned char)
Line
Count
Source
56
51
   {
57
51
   size_t hb = 0;
58
51
59
204
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
153
      {
61
153
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
153
      hb += z;
63
153
      n >>= z;
64
153
      }
65
51
66
51
   hb += n;
67
51
68
51
   return hb;
69
51
   }
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
50.2k
   {
79
50.2k
   size_t b = 0;
80
50.2k
81
201k
   for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
82
150k
      {
83
150k
      const size_t z = s * (~ct_is_zero(n >> s) & 1);
84
150k
      b += z/8;
85
150k
      n >>= z;
86
150k
      }
87
50.2k
88
50.2k
   b += (n != 0);
89
50.2k
90
50.2k
   return b;
91
50.2k
   }
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
57.5M
   {
101
57.5M
   /*
102
57.5M
   * If n == 0 then this function will compute 8*sizeof(T)-1, so
103
57.5M
   * initialize lb to 1 if n == 0 to produce the expected result.
104
57.5M
   */
105
57.5M
   size_t lb = ct_is_zero(n) & 1;
106
57.5M
107
403M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
345M
      {
109
345M
      const T mask = (static_cast<T>(1) << s) - 1;
110
345M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
345M
      lb += z;
112
345M
      n >>= z;
113
345M
      }
114
57.5M
115
57.5M
   return lb;
116
57.5M
   }
unsigned long Botan::ctz<unsigned long>(unsigned long)
Line
Count
Source
100
57.5M
   {
101
57.5M
   /*
102
57.5M
   * If n == 0 then this function will compute 8*sizeof(T)-1, so
103
57.5M
   * initialize lb to 1 if n == 0 to produce the expected result.
104
57.5M
   */
105
57.5M
   size_t lb = ct_is_zero(n) & 1;
106
57.5M
107
403M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
345M
      {
109
345M
      const T mask = (static_cast<T>(1) << s) - 1;
110
345M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
345M
      lb += z;
112
345M
      n >>= z;
113
345M
      }
114
57.5M
115
57.5M
   return lb;
116
57.5M
   }
Unexecuted instantiation: unsigned long Botan::ctz<unsigned int>(unsigned int)
117
118
template<typename T>
119
uint8_t ceil_log2(T x)
120
139k
   {
121
139k
   static_assert(sizeof(T) < 32, "Abnormally large scalar");
122
139k
123
139k
   if(x >> (sizeof(T)*8-1))
124
0
      return sizeof(T)*8;
125
139k
126
139k
   uint8_t result = 0;
127
139k
   T compare = 1;
128
139k
129
984k
   while(compare < x)
130
845k
      {
131
845k
      compare <<= 1;
132
845k
      result++;
133
845k
      }
134
139k
135
139k
   return result;
136
139k
   }
137
138
// Potentially variable time ctz used for OCB
139
inline size_t var_ctz32(uint32_t n)
140
5.05k
   {
141
5.05k
#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
142
5.05k
   if(n == 0)
143
0
      return 32;
144
5.05k
   return __builtin_ctz(n);
145
#else
146
   return ctz<uint32_t>(n);
147
#endif
148
   }
149
150
template<typename T>
151
inline T bit_permute_step(T x, T mask, size_t shift)
152
0
   {
153
0
   /*
154
0
   See https://reflectionsonsecurity.wordpress.com/2014/05/11/efficient-bit-permutation-using-delta-swaps/
155
0
   and http://programming.sirrida.de/bit_perm.html
156
0
   */
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 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