Botan  2.9.0
Crypto and TLS for C++11
bit_ops.h
Go to the documentation of this file.
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  {
25  return static_cast<T>(0) - (a >> (sizeof(T)*8-1));
26  }
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  {
34  return expand_top_bit<T>(~x & (x - 1));
35  }
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  {
45  return (arg != 0) && (arg != 1) && ((arg & static_cast<T>(arg-1)) == 0);
46  }
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  {
57  size_t hb = 0;
58 
59  for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
60  {
61  const size_t z = s * ((~ct_is_zero(n >> s)) & 1);
62  hb += z;
63  n >>= z;
64  }
65 
66  hb += n;
67 
68  return hb;
69  }
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  {
79  size_t b = 0;
80 
81  for(size_t s = 8*sizeof(n) / 2; s >= 8; s /= 2)
82  {
83  const size_t z = s * (~ct_is_zero(n >> s) & 1);
84  b += z/8;
85  n >>= z;
86  }
87 
88  b += (n != 0);
89 
90  return b;
91  }
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  {
101  /*
102  * If n == 0 then this function will compute 8*sizeof(T)-1, so
103  * initialize lb to 1 if n == 0 to produce the expected result.
104  */
105  size_t lb = ct_is_zero(n) & 1;
106 
107  for(size_t s = 8*sizeof(T) / 2; s > 0; s /= 2)
108  {
109  const T mask = (static_cast<T>(1) << s) - 1;
110  const size_t z = s * (ct_is_zero(n & mask) & 1);
111  lb += z;
112  n >>= z;
113  }
114 
115  return lb;
116  }
117 
118 template<typename T>
119 size_t ceil_log2(T x)
120  {
121  if(x >> (sizeof(T)*8-1))
122  return sizeof(T)*8;
123 
124  size_t result = 0;
125  T compare = 1;
126 
127  while(compare < x)
128  {
129  compare <<= 1;
130  result++;
131  }
132 
133  return result;
134  }
135 
136 // Potentially variable time ctz used for OCB
137 inline size_t var_ctz32(uint32_t n)
138  {
139 #if defined(BOTAN_BUILD_COMPILER_IS_GCC) || defined(BOTAN_BUILD_COMPILER_IS_CLANG)
140  if(n == 0)
141  return 32;
142  return __builtin_ctz(n);
143 #else
144  return ctz<uint32_t>(n);
145 #endif
146  }
147 
148 }
149 
150 #endif
size_t ctz(T n)
Definition: bit_ops.h:99
size_t var_ctz32(uint32_t n)
Definition: bit_ops.h:137
size_t significant_bytes(T n)
Definition: bit_ops.h:77
T expand_top_bit(T a)
Definition: bit_ops.h:23
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
T ct_is_zero(T x)
Definition: bit_ops.h:32
size_t high_bit(T n)
Definition: bit_ops.h:55
Definition: alg_id.cpp:13
size_t ceil_log2(T x)
Definition: bit_ops.h:119
fe T
Definition: ge.cpp:37