Coverage Report

Created: 2020-05-23 13:54

/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
9.62G
   {
25
9.62G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
9.62G
   }
unsigned char Botan::expand_top_bit<unsigned char>(unsigned char)
Line
Count
Source
24
18.3M
   {
25
18.3M
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
18.3M
   }
unsigned int Botan::expand_top_bit<unsigned int>(unsigned int)
Line
Count
Source
24
895k
   {
25
895k
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
895k
   }
unsigned long Botan::expand_top_bit<unsigned long>(unsigned long)
Line
Count
Source
24
9.60G
   {
25
9.60G
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
9.60G
   }
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
   }
int Botan::expand_top_bit<int>(int)
Line
Count
Source
24
108
   {
25
108
   return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26
108
   }
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
8.37G
   {
34
8.37G
   return expand_top_bit<T>(~x & (x - 1));
35
8.37G
   }
unsigned char Botan::ct_is_zero<unsigned char>(unsigned char)
Line
Count
Source
33
18.3M
   {
34
18.3M
   return expand_top_bit<T>(~x & (x - 1));
35
18.3M
   }
unsigned int Botan::ct_is_zero<unsigned int>(unsigned int)
Line
Count
Source
33
261k
   {
34
261k
   return expand_top_bit<T>(~x & (x - 1));
35
261k
   }
unsigned long Botan::ct_is_zero<unsigned long>(unsigned long)
Line
Count
Source
33
8.35G
   {
34
8.35G
   return expand_top_bit<T>(~x & (x - 1));
35
8.35G
   }
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
   }
int Botan::ct_is_zero<int>(int)
Line
Count
Source
33
108
   {
34
108
   return expand_top_bit<T>(~x & (x - 1));
35
108
   }
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.75M
   {
45
7.75M
   return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0);
46
7.75M
   }
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
9.79M
   {
57
9.79M
   size_t hb = 0;
58
9.79M
59
68.5M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
58.7M
      {
61
58.7M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
58.7M
      hb += z;
63
58.7M
      n >>= z;
64
58.7M
      }
65
9.79M
66
9.79M
   hb += n;
67
9.79M
68
9.79M
   return hb;
69
9.79M
   }
unsigned long Botan::high_bit<unsigned int>(unsigned int)
Line
Count
Source
56
52.2k
   {
57
52.2k
   size_t hb = 0;
58
52.2k
59
313k
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
261k
      {
61
261k
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
261k
      hb += z;
63
261k
      n >>= z;
64
261k
      }
65
52.2k
66
52.2k
   hb += n;
67
52.2k
68
52.2k
   return hb;
69
52.2k
   }
unsigned long Botan::high_bit<unsigned long>(unsigned long)
Line
Count
Source
56
9.74M
   {
57
9.74M
   size_t hb = 0;
58
9.74M
59
68.1M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
58.4M
      {
61
58.4M
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
58.4M
      hb += z;
63
58.4M
      n >>= z;
64
58.4M
      }
65
9.74M
66
9.74M
   hb += n;
67
9.74M
68
9.74M
   return hb;
69
9.74M
   }
unsigned long Botan::high_bit<unsigned char>(unsigned char)
Line
Count
Source
56
36
   {
57
36
   size_t hb = 0;
58
36
59
144
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60
108
      {
61
108
      const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62
108
      hb += z;
63
108
      n >>= z;
64
108
      }
65
36
66
36
   hb += n;
67
36
68
36
   return hb;
69
36
   }
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 size_t significant_bytes(T n)
78
44.2k
   {
79
44.2k
   size_t b = 0;
80
44.2k
81
177k
   for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
82
132k
      {
83
132k
      const size_t z = s * (~ct_is_zero(n >> s) & 1);
84
132k
      b += z/8;
85
132k
      n >>= z;
86
132k
      }
87
44.2k
88
44.2k
   b += (n != 0);
89
44.2k
90
44.2k
   return b;
91
44.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
52.1M
   {
101
52.1M
   /*
102
52.1M
   * If n == 0 then this function will compute 8*sizeof(T)-1, so
103
52.1M
   * initialize lb to 1 if n == 0 to produce the expected result.
104
52.1M
   */
105
52.1M
   size_t lb = ct_is_zero(n) & 1;
106
52.1M
107
365M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
313M
      {
109
313M
      const T mask = (static_cast<T>(1) << s) - 1;
110
313M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
313M
      lb += z;
112
313M
      n >>= z;
113
313M
      }
114
52.1M
115
52.1M
   return lb;
116
52.1M
   }
Unexecuted instantiation: unsigned long Botan::ctz<unsigned int>(unsigned int)
unsigned long Botan::ctz<unsigned long>(unsigned long)
Line
Count
Source
100
52.1M
   {
101
52.1M
   /*
102
52.1M
   * If n == 0 then this function will compute 8*sizeof(T)-1, so
103
52.1M
   * initialize lb to 1 if n == 0 to produce the expected result.
104
52.1M
   */
105
52.1M
   size_t lb = ct_is_zero(n) & 1;
106
52.1M
107
365M
   for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108
313M
      {
109
313M
      const T mask = (static_cast<T>(1) << s) - 1;
110
313M
      const size_t z = s * (ct_is_zero(n & mask) & 1);
111
313M
      lb += z;
112
313M
      n >>= z;
113
313M
      }
114
52.1M
115
52.1M
   return lb;
116
52.1M
   }
117
118
template<typename T>
119
uint8_t ceil_log2(T x)
120
125k
   {
121
125k
   static_assert(sizeof(T) < 32, "Abnormally large scalar");
122
125k
123
125k
   if(x >> (sizeof(T)*8-1))
124
0
      return sizeof(T)*8;
125
125k
126
125k
   uint8_t result = 0;
127
125k
   T compare = 1;
128
125k
129
888k
   while(compare < x)
130
763k
      {
131
763k
      compare <<= 1;
132
763k
      result++;
133
763k
      }
134
125k
135
125k
   return result;
136
125k
   }
137
138
// Potentially variable time ctz used for OCB
139
inline size_t var_ctz32(uint32_t n)
140
5.11k
   {
141
5.11k
#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
142
5.11k
   if(n == 0)
143
0
      return 32;
144
5.11k
   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