ROSE  0.11.2.0
BitOps.h
1 #ifndef ROSE_BitOps_H
2 #define ROSE_BitOps_H
3 
4 #include <Sawyer/Assert.h>
5 #include <Sawyer/Optional.h>
6 
7 namespace Rose {
8 
13 namespace BitOps {
14 
16 template<typename Unsigned>
17 inline size_t nBits(Unsigned x = Unsigned(0)) {
18  return 8*sizeof(Unsigned);
19 }
20 
22 template<typename Unsigned>
23 inline Unsigned all(bool b = true) {
24  return Unsigned(0) - Unsigned(b ? 1 : 0);
25 }
26 
27 template<typename Unsigned> inline Unsigned lowMask(size_t n);
28 
32 template<typename Unsigned>
33 inline Unsigned allLsb(Unsigned src, size_t w, bool b = true) {
34  ASSERT_require(w <= nBits(src));
35  if (b) {
36  return src | lowMask<Unsigned>(w);
37  } else {
38  return src & ~lowMask<Unsigned>(w);
39  }
40 }
41 
47 template<typename Unsigned>
48 inline Unsigned lowMask(size_t n) {
49  return n >= nBits<Unsigned>() ? all<Unsigned>(true) : (Unsigned(1) << n) - Unsigned(1);
50 }
51 
56 template<typename Unsigned>
57 inline Unsigned highMask(size_t n) {
58  return n >= nBits<Unsigned>() ? all<Unsigned>(true) : lowMask<Unsigned>(n) << (nBits<Unsigned>() - n);
59 }
60 
65 template<typename Unsigned>
66 inline Unsigned select(Unsigned cond, Unsigned a, Unsigned b) {
67  return (a & cond) | (b & ~cond);
68 }
69 
75 template<typename Unsigned>
76 inline Unsigned shiftLeft(Unsigned src, size_t n, bool b = false) {
77  if (n >= nBits(src)) {
78  return all<Unsigned>(b);
79  } else {
80  return Unsigned(src << n) | (all<Unsigned>(b) & lowMask<Unsigned>(n));
81  }
82 }
83 
90 template<typename Unsigned>
91 inline Unsigned shiftLeftLsb(Unsigned src, size_t w, size_t n, bool b = false) {
92  ASSERT_require(w <= nBits(src));
93  if (n >= w) {
94  return allLsb(src, w, b);
95  } else {
96  return select(lowMask<Unsigned>(w), shiftLeft(src, n, b), src);
97  }
98 }
99 
105 template<typename Unsigned>
106 inline Unsigned shiftRight(Unsigned src, size_t n, bool b = false) {
107  if (n >= nBits(src)) {
108  return all<Unsigned>(b);
109  } else {
110  return Unsigned(src >> n) | (all<Unsigned>(b) & highMask<Unsigned>(n));
111  }
112 }
113 
119 template<typename Unsigned>
120 inline Unsigned shiftRightLsb(Unsigned src, size_t w, size_t n, bool b = false) {
121  ASSERT_require(w <= nBits(src));
122  if (n >= w) {
123  return allLsb(src, w, b);
124  } else {
125  return select(lowMask<Unsigned>(w), shiftRight(src & lowMask<Unsigned>(w), n, b), src);
126  }
127 }
128 
133 template<typename Unsigned>
134 inline Unsigned position(size_t i) {
135  return i < nBits<Unsigned>() ? shiftLeft(Unsigned(1), i) : Unsigned(0);
136 }
137 
141 template<typename Unsigned>
142 inline Unsigned positionLsb(Unsigned src, size_t w, size_t i) {
143  ASSERT_require(w <= nBits(src));
144  return select(lowMask<Unsigned>(w), position<Unsigned>(i), src);
145 }
146 
152 template<typename Unsigned>
153 inline Unsigned mask(size_t least, size_t greatest) {
154  ASSERT_require(greatest < nBits<Unsigned>());
155  ASSERT_require(greatest >= least);
156  return shiftLeft(lowMask<Unsigned>(greatest - least + 1), least);
157 }
158 
162 template<typename Unsigned>
163 inline Unsigned maskLsb(Unsigned src, size_t w, size_t least, size_t greatest) {
164  ASSERT_require(w <= nBits(src));
165  return select(lowMask<Unsigned>(w), mask<Unsigned>(least, greatest), src);
166 }
167 
171 template<typename Unsigned>
172 inline bool bit(Unsigned src, size_t i) {
173  return i < nBits(src) ? (src & position<Unsigned>(i)) != 0 : false;
174 }
175 
180 template<typename Unsigned>
181 inline bool bitLsb(Unsigned src, size_t w, size_t i) {
182  return i < w ? (src & position<Unsigned>(i)) != 0 : false;
183 }
184 
188 template<typename Unsigned>
189 inline bool msb(Unsigned src) {
190  return bit(src, nBits(src) - 1);
191 }
192 
196 template<typename Unsigned>
197 inline bool msbLsb(Unsigned src, size_t w) {
198  ASSERT_require(w <= nBits(src));
199  return w > 0 ? bit(src, w-1) : false;
200 }
201 
208 template<typename Unsigned>
209 inline Unsigned shiftRightSigned(Unsigned src, size_t n) {
210  return shiftRight(src, n, msb(src));
211 }
212 
213 
220 template<typename Unsigned>
221 inline Unsigned shiftRightSigned(Unsigned src, size_t w, size_t n) {
222  return shiftRightLsb(src, n, w, msbLsb(src, w));
223 }
224 
229 template<typename Unsigned>
230 inline Unsigned bits(Unsigned src, size_t least, size_t greatest) {
231  return shiftRight(src & mask<Unsigned>(least, greatest), least);
232 }
233 
238 template<typename Unsigned>
239 inline Unsigned bitsLsb(Unsigned src, size_t w, size_t least, size_t greatest) {
240  return shiftRight(src & mask<Unsigned>(least, greatest) & lowMask<Unsigned>(w), least);
241 }
242 
243 
248 template<typename UnsignedTarget, typename UnsignedSource>
249 inline UnsignedTarget convert(UnsignedSource x, bool b = false) {
250  if (nBits(x) < nBits<UnsignedTarget>()) {
251  // extending
252  return UnsignedTarget(x) | (all<UnsignedTarget>(b) & ~lowMask<UnsignedTarget>(nBits(x)));
253  } else {
254  // truncating
255  return UnsignedTarget(x & lowMask<UnsignedSource>(nBits<UnsignedTarget>()));
256  }
257 }
258 
263 template<typename UnsignedTarget, typename UnsignedSource>
264 inline UnsignedTarget convertSigned(UnsignedSource x) {
265  return convert<UnsignedTarget>(x, msb(x));
266 }
267 
271 template<typename Unsigned>
272 inline Unsigned signExtend(Unsigned src, size_t n) {
273  if (n < nBits(src)) {
274  if (msbLsb(src, n)) {
275  src |= mask<Unsigned>(n, nBits(src)-1);
276  } else {
277  src &= ~mask<Unsigned>(n, nBits(src)-1);
278  }
279  }
280  return src;
281 }
282 
287 template<typename Unsigned>
288 inline Unsigned signExtendLsb(Unsigned src, size_t n, size_t m) {
289  ASSERT_require(n > 0);
290  ASSERT_require(m >= n);
291  ASSERT_require(m <= nBits(src));
292  if (m == n) {
293  return src;
294  } else {
295  Unsigned newBitsMask = mask<Unsigned>(n, m-1);
296  if (bit(src, n-1)) {
297  return src | newBitsMask;
298  } else {
299  return src & ~newBitsMask;
300  }
301  }
302 }
303 
309 template<typename Unsigned>
310 inline Unsigned rotateLeft(Unsigned src, size_t n) {
311  n %= nBits(src);
312  return shiftLeft(src, n) | shiftRight(src, nBits(src)-n);
313 }
314 
319 template<typename Unsigned>
320 inline Unsigned rotateLeftLsb(Unsigned src, size_t w, size_t n) {
321  ASSERT_require(w <= nBits(src));
322  n = w ? n % w : 0;
323  return select(lowMask<Unsigned>(w),
324  shiftLeftLsb(src, w, n) | shiftRightLsb(src, w-n),
325  src);
326 }
327 
333 template<typename Unsigned>
334 inline Unsigned rotateRight(Unsigned src, size_t n) {
335  n %= nBits(src);
336  return shiftRight(src, n) | shiftLeft(src, nBits(src)-n);
337 }
338 
343 template<typename Unsigned>
344 inline Unsigned rotateRightLsb(Unsigned src, size_t w, size_t n) {
345  ASSERT_require(w <= nBits(src));
346  n = w ? n % w : 0;
347  return select(lowMask<Unsigned>(w),
348  shiftRightLsb(src, w, n) | shiftLeftLsb(src, w, w-n),
349  src);
350 }
351 
358 template<typename Unsigned>
359 inline Unsigned replicate(Unsigned src, size_t n) {
360  ASSERT_require(n != 0);
361  if (n >= nBits(src)) {
362  return src;
363  } else {
364  size_t ngroups = (nBits(src) + 1) / n;
365  Unsigned retval = 0;
366  for (size_t i = 0; i < ngroups; ++i)
367  retval |= shiftLeft(src & lowMask<Unsigned>(n), i*n);
368  return retval;
369  }
370 }
371 
377 template<typename Unsigned>
378 inline Unsigned replicateLsb(Unsigned src, size_t w, size_t n) {
379  ASSERT_require(w <= nBits(src));
380  return select(lowMask<Unsigned>(w), replicate(src, n), src);
381 }
382 
386 template<typename Unsigned>
388  if (src) {
389  for (size_t i = nBits(src); i > 0; --i) {
390  if (bit(src, i-1))
391  return i-1;
392  }
393  }
394  return Sawyer::Nothing();
395 }
396 
397 } // namespace
398 } // namespace
399 #endif
400 
Unsigned shiftRight(Unsigned src, size_t n, bool b=false)
Right shift a value.
Definition: BitOps.h:106
Unsigned positionLsb(Unsigned src, size_t w, size_t i)
Generate a single-bit mask without affecting the high-order bits.
Definition: BitOps.h:142
Unsigned rotateLeft(Unsigned src, size_t n)
Rotate bits left.
Definition: BitOps.h:310
Unsigned signExtendLsb(Unsigned src, size_t n, size_t m)
Sign extend part of value without affecting other bits.
Definition: BitOps.h:288
Unsigned replicate(Unsigned src, size_t n)
Replicate low-order bits to fill return value.
Definition: BitOps.h:359
Unsigned signExtend(Unsigned src, size_t n)
Sign extend part of a value to the full width of the src type.
Definition: BitOps.h:272
UnsignedTarget convert(UnsignedSource x, bool b=false)
Extend or truncate a value.
Definition: BitOps.h:249
Unsigned position(size_t i)
Generate a single-bit mask.
Definition: BitOps.h:134
bool bitLsb(Unsigned src, size_t w, size_t i)
Extract a single bit.
Definition: BitOps.h:181
Unsigned shiftLeft(Unsigned src, size_t n, bool b=false)
Left shift a value.
Definition: BitOps.h:76
Sawyer::Optional< size_t > highestSetBit(Unsigned src)
Index of the highest set bit.
Definition: BitOps.h:387
size_t nBits(Unsigned x=Unsigned(0))
Number of bits in a type or value.
Definition: BitOps.h:17
UnsignedTarget convertSigned(UnsignedSource x)
Sign extend or truncate a value.
Definition: BitOps.h:264
Unsigned shiftLeftLsb(Unsigned src, size_t w, size_t n, bool b=false)
Left shift part of a value without affecting the rest.
Definition: BitOps.h:91
Unsigned shiftRightLsb(Unsigned src, size_t w, size_t n, bool b=false)
Right shift part of a value without affecting the rest.
Definition: BitOps.h:120
Unsigned all(bool b=true)
Generate a value with all bits set or cleared.
Definition: BitOps.h:23
Unsigned lowMask(size_t n)
Generate a value with low order bits set.
Definition: BitOps.h:48
Main namespace for the ROSE library.
bool msb(Unsigned src)
Most significant bit.
Definition: BitOps.h:189
Unsigned rotateRight(Unsigned src, size_t n)
Rotate bits right.
Definition: BitOps.h:334
Unsigned select(Unsigned cond, Unsigned a, Unsigned b)
Combine two values based on a bit mask.
Definition: BitOps.h:66
Unsigned bits(Unsigned src, size_t least, size_t greatest)
Extract part of a value.
Definition: BitOps.h:230
Unsigned mask(size_t least, size_t greatest)
Generate a mask.
Definition: BitOps.h:153
Unsigned rotateLeftLsb(Unsigned src, size_t w, size_t n)
Rotate low-order bits left without affecting others.
Definition: BitOps.h:320
Unsigned rotateRightLsb(Unsigned src, size_t w, size_t n)
Rotate low-order bits right without affecting others.
Definition: BitOps.h:344
Unsigned allLsb(Unsigned src, size_t w, bool b=true)
Set or clear the low-order bits.
Definition: BitOps.h:33
Unsigned bitsLsb(Unsigned src, size_t w, size_t least, size_t greatest)
Extract part of a value limited by width.
Definition: BitOps.h:239
Unsigned highMask(size_t n)
Generate a value with high order bits set.
Definition: BitOps.h:57
bool bit(Unsigned src, size_t i)
Extract a single bit.
Definition: BitOps.h:172
Represents no value.
Definition: Optional.h:32
Unsigned replicateLsb(Unsigned src, size_t w, size_t n)
Replicate low-order bits to fill region without affecting other bits.
Definition: BitOps.h:378
bool msbLsb(Unsigned src, size_t w)
Most significant bit within lsb region.
Definition: BitOps.h:197
Unsigned maskLsb(Unsigned src, size_t w, size_t least, size_t greatest)
Generate a mask without affecting other bits.
Definition: BitOps.h:163
Unsigned shiftRightSigned(Unsigned src, size_t n)
Right shift replicating MSB.
Definition: BitOps.h:209