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
|
/*
* 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 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)
{
return __builtin_ctz(n);
}
#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
|
