ROSE  0.9.9.139
integerOps.h
1 #ifndef ROSE_INTEGEROPS_H
2 #define ROSE_INTEGEROPS_H
3 
4 #include <cassert>
5 #include <limits>
6 #include <boost/static_assert.hpp>
7 #include <boost/optional.hpp>
8 
9 namespace IntegerOpsPrivate {
10 
11  template <typename T>
12  struct NumBits {
13  BOOST_STATIC_ASSERT (std::numeric_limits<T>::radix == 2);
14  BOOST_STATIC_ASSERT (std::numeric_limits<T>::is_integer);
15  static const size_t value = std::numeric_limits<T>::digits;
16  };
17 
18  template <typename T, size_t Count, bool TooBig> struct SHL1Helper;
19  template <typename T, size_t Count>
20  struct SHL1Helper<T, Count, true> {
21  static const T value = 0;
22  };
23  template <typename T, size_t Count>
24  struct SHL1Helper<T, Count, false> {
25  static const T value = T(1) << Count;
26  };
27 
28 }
29 
35 namespace IntegerOps {
36 
38 template <typename T, size_t n>
39 struct SHL1: public IntegerOpsPrivate::SHL1Helper<T, n, (n >= IntegerOpsPrivate::NumBits<T>::value)> {};
40 
42 template <typename T>
43 inline T shl1(size_t n) {
44  return (n >= IntegerOpsPrivate::NumBits<T>::value) ? T(0) : (T(1) << n);
45 }
46 
48 template <typename T, size_t n>
49 struct GenMask {
50  static const T value = SHL1<T, n>::value - T(1);
51 };
52 
54 template <typename T>
55 inline T genMask(size_t n) {
56  return shl1<T>(n) - 1;
57 }
58 
61 template <typename T>
62 inline T genMask(size_t lobit, size_t hibit)
63 {
64  assert(hibit<8*sizeof(T));
65  assert(hibit>=lobit);
66  return genMask<T>(1+hibit-lobit) << lobit;
67 }
68 
71 template <size_t NBits, typename T>
72 inline bool signBit(T value) {
73  return (value & SHL1<T, NBits - 1>::value) != T(0);
74 }
75 
76 template <typename T>
77 inline bool signBit2(T value, size_t width=8*sizeof(T)) {
78  assert(width>0 && width<=8*sizeof(T));
79  T sign_mask = shl1<T>(width-1);
80  return 0 != (value & sign_mask);
81 }
87 template <size_t FromBits, size_t ToBits, typename T>
88 inline T signExtend(T value) {
89  return value | (signBit<FromBits>(value) ? (GenMask<T, ToBits>::value ^ GenMask<T, FromBits>::value) : T(0));
90 }
91 
92 template <typename T>
93 inline T signExtend2(T value, size_t from_width, size_t to_width) {
94  assert(from_width<=8*sizeof(T));
95  assert(to_width<=8*sizeof(T));
96  return value | (signBit2(value, from_width) ? (genMask<T>(to_width) ^ genMask<T>(from_width)) : T(0));
97 }
102 template <size_t NBits, typename T>
103 inline T shiftLeft(T value, size_t count) {
104  return (value * shl1<T>(count)) & GenMask<T, NBits>::value;
105 }
106 
107 template <typename T>
108 inline T shiftLeft2(T value, size_t count, size_t width=8*sizeof(T)) {
109  assert(width>0 && width<=8*sizeof(T));
110  return (value * shl1<T>(count)) & genMask<T>(width);
111 }
116 template <size_t NBits, typename T>
117 inline T shiftRightLogical(T value, size_t count) {
118  return (count >= NBits) ? T(0) : (value >> count);
119 }
120 
121 template <typename T>
122 inline T shiftRightLogical2(T value, size_t count, size_t width=8*sizeof(T)) {
123  assert(width>0 && width<=8*sizeof(T));
124  return (count >= width) ? T(0) : (value >> count);
125 }
130 template <size_t NBits, typename T>
131 inline T shiftRightArithmetic(T value, size_t count) {
132  if (count >= NBits) {
133  return signBit<NBits>(value) ? GenMask<T, NBits>::value : T(0);
134  } else {
135  return (shiftRightLogical<NBits>(value, count) |
136  (signBit<NBits>(value) ? (GenMask<T, NBits>::value ^ genMask<T>(NBits - count)) : T(0)));
137  }
138 }
139 
140 template <typename T>
141 inline T shiftRightArithmetic2(T value, size_t count, size_t width=8*sizeof(T)) {
142  if (count >= width) {
143  return signBit2(value, width) ? genMask<T>(width) : T(0);
144  } else {
145  return (shiftRightLogical2(value, count, width) |
146  (signBit2(value, width) ? (genMask<T>(width) ^ genMask<T>(width-count)) : T(0)));
147  }
148 }
153 template <size_t NBits, typename T>
154 inline T rotateLeft(T value, size_t count) {
155  count %= NBits;
156  return ((value << count) | (value >> (NBits - count))) & GenMask<T, NBits>::value;
157 }
158 
159 template <typename T>
160 inline T rotateLeft2(T value, size_t count, size_t width=8*sizeof(T)) {
161  assert(width>0 && width<=8*sizeof(T));
162  count %= width;
163  return ((value << count) | (value >> (width-count))) & genMask<T>(width);
164 }
169 template <size_t NBits, typename T>
170 inline T rotateRight(T value, size_t count) {
171  count %= NBits;
172  return ((value >> count) | (value << (NBits - count))) & GenMask<T, NBits>::value;
173 }
174 
175 template <typename T>
176 inline T rotateRight2(T value, size_t count, size_t width=8*sizeof(T)) {
177  assert(width>0 && width<=8*sizeof(T));
178  return ((value >> count) | (value << (width - count))) & genMask<T>(width);
179 }
183 template <typename T>
184 inline bool isPowerOfTwo(T value)
185 {
186  assert(sizeof(T) <= sizeof(uint64_t));
187  if (0 != (value & SHL1<T, 8*sizeof(T)-1>::value))
188  value = ~value + 1;
189  uint64_t uval = value;
190  while (uval) {
191  if (uval & 1)
192  return 1==uval;
193  uval >>= 1u;
194  }
195  return true; // treat zero as a power of two
196 }
197 
200 template <typename T>
201 inline T log2max(T value)
202 {
203  assert(sizeof(T) <= sizeof(uint64_t));
204  uint64_t uval = value;
205  bool low_bits_set = false;
206  T retval = 0;
207  while (uval) {
208  if (1==uval)
209  return retval + (low_bits_set ? 1 : 0);
210  if (uval & 1)
211  low_bits_set = true;
212  ++retval;
213  uval >>= 1;
214  }
215  return retval;
216 }
217 
218 
219 template <typename T>
220 inline T log2(T a) {
221  T n = T(1);
222  T i = 0;
223  while (n != 0 && n < a) {
224  n <<= 1;
225  ++i;
226  }
227  return i;
228 }
229 
234 template<size_t lobit, size_t hibit, typename T>
235 inline T shift_to(T value) {
236  assert(hibit<8*sizeof(T));
237  assert(hibit>=lobit);
238  assert(0==(value & ~GenMask<T, 1+hibit-lobit>::value));
239  return shiftLeft<8*sizeof(T)>(value & GenMask<T, 1+hibit-lobit>::value, lobit);
240 }
241 template<typename T>
242 inline T shift_to2(size_t lobit, size_t hibit, T value)
243 {
244  assert(hibit<8*sizeof(T));
245  assert(hibit>=lobit);
246  assert(0==(value & ~genMask<T>(1+hibit-lobit)));
247  return shiftLeft2<T>(value & genMask<T>(1+hibit-lobit), lobit);
248 }
254 template<size_t lobit, size_t hibit, typename T>
255 inline T extract(T bits) {
256  assert(hibit<8*sizeof(T));
257  assert(hibit>=lobit);
258  return shiftRightLogical<8*sizeof(T)>(bits, lobit) & GenMask<T, 1+hibit-lobit>::value;
259 }
260 template<typename T>
261 inline T extract2(size_t lobit, size_t hibit, T bits)
262 {
263  assert(hibit<8*sizeof(T));
264  assert(hibit>=lobit);
265  return shiftRightLogical<8*sizeof(T)>(bits, lobit) & genMask<T>(1+hibit-lobit);
266 }
271 template<typename T>
272 inline bool bitmask_subset(T m1, T m2)
273 {
274  return 0 == (~m1 & m2); // m2 must not contain bits that are not in m1
275 }
276 
278 template<typename T>
279 inline size_t countSet(T val)
280 {
281  size_t retval = 0;
282  for (size_t i=0; i<8*sizeof(T); ++i) {
283  if (0 != (val & shl1<T>(i)))
284  ++retval;
285  }
286  return retval;
287 }
288 
290 template<typename T>
291 inline size_t countClear(T val)
292 {
293  size_t retval = 0;
294  for (size_t i=0; i<8*sizeof(T); ++i) {
295  if (0 == (val & shl1<T>(i)))
296  ++retval;
297  }
298  return retval;
299 }
300 
302 template<typename T>
303 inline boost::optional<size_t> msb_set(T val)
304 {
305  if (val!=0) {
306  for (size_t bitno = 8*sizeof(T); bitno>0; --bitno) {
307  if (0 != (val & shl1<T>(bitno-1)))
308  return boost::optional<size_t>(bitno-1);
309  }
310  }
311  return boost::optional<size_t>();
312 }
313 
314 } // namespace
315 #endif // ROSE_INTEGEROPS_H
T shl1(size_t n)
Bitmask with bit n set.
Definition: integerOps.h:43
T shift_to2(size_t lobit, size_t hibit, T value)
Create a shifted value.
Definition: integerOps.h:242
bool isPowerOfTwo(T value)
Returns true if the value is a power of two.
Definition: integerOps.h:184
Bit mask constant with bits 0 through n-1 set.
Definition: integerOps.h:49
bool signBit(T value)
Returns true if the sign bit is set, false if clear.
Definition: integerOps.h:72
T rotateLeft2(T value, size_t count, size_t width=8 *sizeof(T))
Rotate the bits of the value left by count bits.
Definition: integerOps.h:160
size_t countClear(T val)
Counts how many bits are clear (zero).
Definition: integerOps.h:291
Bitmask constant with bit n set.
Definition: integerOps.h:39
T shiftLeft(T value, size_t count)
Shifts bits of value left by count bits.
Definition: integerOps.h:103
Bit-wise operations on integers.
Definition: integerOps.h:35
T rotateLeft(T value, size_t count)
Rotate the bits of the value left by count bits.
Definition: integerOps.h:154
T shiftRightLogical(T value, size_t count)
Shifts bits of value right by count bits without sign extension.
Definition: integerOps.h:117
T signExtend2(T value, size_t from_width, size_t to_width)
Sign extend value.
Definition: integerOps.h:93
size_t countSet(T val)
Counts how many bits are set (one).
Definition: integerOps.h:279
T shiftRightArithmetic2(T value, size_t count, size_t width=8 *sizeof(T))
Shifts bits of value right by count bits with sign extension.
Definition: integerOps.h:141
T rotateRight2(T value, size_t count, size_t width=8 *sizeof(T))
Rotate bits of the value right by count bits.
Definition: integerOps.h:176
T extract2(size_t lobit, size_t hibit, T bits)
Extract bits from a value.
Definition: integerOps.h:261
T log2max(T value)
Returns the base-2 logorithm of value.
Definition: integerOps.h:201
T shift_to(T value)
Create a shifted value.
Definition: integerOps.h:235
T rotateRight(T value, size_t count)
Rotate bits of the value right by count bits.
Definition: integerOps.h:170
T shiftRightArithmetic(T value, size_t count)
Shifts bits of value right by count bits with sign extension.
Definition: integerOps.h:131
T genMask(size_t n)
Bitmask with bits 0 through N-1 set.
Definition: integerOps.h:55
T shiftRightLogical2(T value, size_t count, size_t width=8 *sizeof(T))
Shifts bits of value right by count bits without sign extension.
Definition: integerOps.h:122
bool bitmask_subset(T m1, T m2)
Determines if one bitmask is a subset of another.
Definition: integerOps.h:272
boost::optional< size_t > msb_set(T val)
Optionally returns the zero-origin position of the most significant set bit.
Definition: integerOps.h:303
bool signBit2(T value, size_t width=8 *sizeof(T))
Returns true if the sign bit is set, false if clear.
Definition: integerOps.h:77
T signExtend(T value)
Sign extend value.
Definition: integerOps.h:88
T extract(T bits)
Extract bits from a value.
Definition: integerOps.h:255
T shiftLeft2(T value, size_t count, size_t width=8 *sizeof(T))
Shifts bits of value left by count bits.
Definition: integerOps.h:108