1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
/*
* Bit/Word Operations
* (C) 1999-2008 Jack Lloyd
* (C) Copyright Projet SECRET, INRIA, Rocquencourt
* (C) Bhaskar Biswas and Nicolas Sendrier
* (C) 2014 cryptosource GmbH
* (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#ifndef BOTAN_BIT_OPS_H_
#define BOTAN_BIT_OPS_H_
#include <botan/types.h>
namespace Botan {
/**
* Power of 2 test. T should be an unsigned integer type
* @param arg an integer value
* @return true iff arg is 2^n for some n > 0
*/
template<typename T>
inline constexpr bool is_power_of_2(T arg)
{
return ((arg != 0 && arg != 1) && ((arg & (arg-1)) == 0));
}
/**
* Return the index of the highest set bit
* T is an unsigned integer type
* @param n an integer value
* @return index of the highest set bit in n
*/
template<typename T>
inline size_t high_bit(T n)
{
for(size_t i = 8*sizeof(T); i > 0; --i)
if((n >> (i - 1)) & 0x01)
return i;
return 0;
}
/**
* Return the index of the lowest set bit
* T is an unsigned integer type
* @param n an integer value
* @return index of the lowest set bit in n
*/
template<typename T>
inline size_t low_bit(T n)
{
for(size_t i = 0; i != 8*sizeof(T); ++i)
if((n >> i) & 0x01)
return (i + 1);
return 0;
}
/**
* Return the number of significant bytes in n
* @param n an integer value
* @return number of significant bytes in n
*/
template<typename T>
inline size_t significant_bytes(T n)
{
for(size_t i = 0; i != sizeof(T); ++i)
if(get_byte(i, n))
return sizeof(T)-i;
return 0;
}
/**
* Compute Hamming weights
* @param n an integer value
* @return number of bits in n set to 1
*/
template<typename T>
inline size_t hamming_weight(T n)
{
const uint8_t NIBBLE_WEIGHTS[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
size_t weight = 0;
for(size_t i = 0; i != 2*sizeof(T); ++i)
weight += NIBBLE_WEIGHTS[(n >> (4*i)) & 0x0F];
return weight;
}
/**
* Count the trailing zero bits in n
* @param n an integer value
* @return maximum x st 2^x divides n
*/
template<typename T>
inline size_t ctz(T n)
{
for(size_t i = 0; i != 8*sizeof(T); ++i)
if((n >> i) & 0x01)
return i;
return 8*sizeof(T);
}
#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
template<>
inline size_t ctz(uint32_t n)
{
if(n == 0)
return 32;
return __builtin_ctz(n);
}
template<>
inline size_t ctz(uint64_t n)
{
if(n == 0)
return 64;
return __builtin_ctzll(n);
}
template<>
inline size_t high_bit(uint32_t x)
{
if(x == 0)
return 0;
return (32 - __builtin_clz(x));
}
template<>
inline size_t high_bit(uint64_t x)
{
if(x == 0)
return 0;
return (64 - __builtin_clzll(x));
}
#endif
template<typename T>
size_t ceil_log2(T x)
{
if(x >> (sizeof(T)*8-1))
return sizeof(T)*8;
size_t result = 0;
T compare = 1;
while(compare < x)
{
compare <<= 1;
result++;
}
return result;
}
}
#endif
|
