blob: 553dae4a2057a114e4d2767bb8470e3eb9bf52df (
plain)
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
|
/*
* 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 {
/**
* If top bit of arg is set, return ~0. Otherwise return 0.
*/
template<typename T>
inline T expand_top_bit(T a)
{
return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
}
/**
* If arg is zero, return ~0. Otherwise return 0
*/
template<typename T>
inline T ct_is_zero(T x)
{
return expand_top_bit<T>(~x & (x - 1));
}
/**
* 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 & static_cast<T>(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)
{
size_t hb = 0;
for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
{
const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
hb += z;
n >>= z;
}
hb += n;
return hb;
}
/**
* 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)
{
size_t b = 0;
for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
{
const size_t z = s * (~ct_is_zero(n >> s) & 1);
b += z/8;
n >>= z;
}
b += (n != 0);
return b;
}
/**
* 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)
{
/*
* If n == 0 then this function will compute 8*sizeof(T)-1, so
* initialize lb to 1 if n == 0 to produce the expected result.
*/
size_t lb = ct_is_zero(n) & 1;
for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
{
const T mask = (static_cast<T>(1) << s) - 1;
const T z = s * (ct_is_zero(n & mask) & 1);
lb += z;
n >>= z;
}
return lb;
}
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;
}
// Potentially variable time ctz used for OCB
inline size_t var_ctz32(uint32_t n)
{
#if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
if(n == 0)
return 32;
return __builtin_ctz(n);
#else
return ctz<uint32_t>(n);
#endif
}
}
#endif
|
