|
|
|
T.
More...
#include <Iguana/Utilities/classlib/utils/BitOps.h>
Static Public Member Functions | |
| static T | ceil2 (T n) |
| Round n up to next power of two. | |
| static T | count (T n) |
| Count the number of bits set in n. | |
| static T | extract (const T *restrict p, unsigned int maxbit, unsigned int from, unsigned int count) |
| Extract count bits from bit vector p, starting at bit position from, but not exceeding maxbit, possibly straddling word boundaries. | |
| static T | extract (T n, unsigned int from, unsigned int count) |
| Extract count bits from word n, starting at bit position from. | |
| static T | extractSafe (const T *restrict p, unsigned int from, unsigned int count) |
| Extract count bits from bit vector p, starting at bit position from. | |
| static T | extractStraddledSafe (const T *restrict p, unsigned int from, unsigned int count) |
| Extract count bits from bit vector p, starting at bit position from, possibly straddling word boundaries. | |
| static T | extractUnstraddled (const T *restrict p, unsigned int maxbit, unsigned int from, unsigned int count) |
| Extract count bits from bit vector p, starting at bit position from, but not exceeding maxbit. | |
| static bool | islog2 (T n) |
| Return true if n is a power of two. | |
| static T | log2 (T n) |
| Compute log2 base of n, i.e. | |
| static T | mortonInterleave (T x, T y) |
| Compute interleaved Morton Number for x and y. | |
| static void | mortonSplit (T n, T &x, T &y) |
| Decode x and y from the interleaved Morton Number n. | |
| static bool | parity (T n) |
| Compute parity of n. | |
| static T | reverse (T n) |
| Reverse the order of bits in n: the least significant bit becomes the most signficant one and vice versa. | |
| static T | rzero (T n) |
| Compute the number of zero bits on the right edge of n, i.e the log2 of the least significant set bit in n. | |
| static void | swap (T &x, T &y) |
| Swap x and y in place without temporaries. | |
T.
Most of the methods use maths faster than the naive loops or table lookups. In some cases (hot inner loops) a suitably tuned table look-up could be faster than the implementation used here. The best size of such tables is somewhat application dependent and therefore no such generic service is provided here.
Definition at line 25 of file BitOps.h.
| T lat::BitOps< T >::ceil2 | ( | T | n | ) | [inline, static] |
Round n up to next power of two.
Definition at line 285 of file BitOps.h.
References bookConverter::compute().
00286 { return BitOpsCeil2<BitTraits<T>::Bits/2>::template Op<T>::compute (n-1)+1; }
| T lat::BitOps< T >::count | ( | T | n | ) | [inline, static] |
Count the number of bits set in n.
Definition at line 148 of file BitOps.h.
References bookConverter::compute().
00149 { return BitOpsCount<BitTraits<T>::Bits/2>::template Op<T>::compute (n); }
| T lat::BitOps< T >::extract | ( | const T *restrict | p, | |
| unsigned int | maxbit, | |||
| unsigned int | from, | |||
| unsigned int | count | |||
| ) | [inline, static] |
Extract count bits from bit vector p, starting at bit position from, but not exceeding maxbit, possibly straddling word boundaries.
The vector of unsigned integral words of type T starting at p is treated as one long bit vector. The words are treated in their natural bit order: the bit position zero is the least significant bit of the first word in p, bit position N-1 (where N is the number of bits in T) is the most significant bit of the first word, bit position N is the least significant bit of the second word in p, and so on.
This method performs a fetch slower than the other extract methods but deals correctly with situations where the requested bits straddle the word boundaries of p elements. If from is less or equal to maxbit, from + count is also assumed to be. If from is greater than maxbit, zero is returned.
Definition at line 506 of file BitOps.h.
References lat::BitOps< T >::extractStraddledSafe().
00508 { return from > maxbit ? 0 : extractStraddledSafe (p, from, count); }
| T lat::BitOps< T >::extract | ( | T | n, | |
| unsigned int | from, | |||
| unsigned int | count | |||
| ) | [inline, static] |
Extract count bits from word n, starting at bit position from.
The caller guarantees that [from, from + count) fits in n.
Definition at line 409 of file BitOps.h.
Referenced by lat::BitOps< T >::extractSafe().
00410 { 00411 enum { AllOnes = BitPattern<T,0xff,8,BitTraits<T>::Bytes>::Pattern }; 00412 return (n >> (BitTraits<T>::Bits - from - count)) & ~(AllOnes << count); 00413 }
| T lat::BitOps< T >::extractSafe | ( | const T *restrict | p, | |
| unsigned int | from, | |||
| unsigned int | count | |||
| ) | [inline, static] |
Extract count bits from bit vector p, starting at bit position from.
The vector of unsigned integral words of type T starting at p is treated as one long bit vector. The words are treated in their natural bit order: the bit position zero is the least significant bit of the first word in p, bit position N-1 (where N is the number of bits in T) is the most significant bit of the first word, bit position N is the least significant bit of the second word in p, and so on.
The caller guarantees that [from, from + count) does not straddle word boundaries of p elements, and that the requested bits do not exceed the end of the valid range of p.
Definition at line 430 of file BitOps.h.
References lat::BitOps< T >::extract().
Referenced by lat::BitOps< T >::extractStraddledSafe(), and lat::BitOps< T >::extractUnstraddled().
00432 { 00433 return extract (* (p + from/BitTraits<T>::Bits), 00434 from % BitTraits<T>::Bits, 00435 count); 00436 }
| T lat::BitOps< T >::extractStraddledSafe | ( | const T *restrict | p, | |
| unsigned int | from, | |||
| unsigned int | count | |||
| ) | [inline, static] |
Extract count bits from bit vector p, starting at bit position from, possibly straddling word boundaries.
The vector of unsigned integral words of type T starting at p is treated as one long bit vector. The words are treated in their natural bit order: the bit position zero is the least significant bit of the first word in p, bit position N-1 (where N is the number of bits in T) is the most significant bit of the first word, bit position N is the least significant bit of the second word in p, and so on.
This method performs a fetch slower than the other extract methods but deals correctly with situations where the requested bits straddle the word boundaries of p elements. The caller guarantees that count does not exceed the number of bits in T and that the requested bits do not exceed the end of the valid range of p.
Definition at line 476 of file BitOps.h.
References lat::BitOps< T >::extractSafe(), and min.
Referenced by lat::BitOps< T >::extract().
00478 { 00479 unsigned int count_word_1 = std::min(count, 00480 BitTraits<T>::Bits 00481 - from % BitTraits<T>::Bits); 00482 unsigned int count_word_2 = count - count_word_1; 00483 00484 return (extractSafe (p, from, count_word_1) << count_word_2 00485 | extractSafe (p, from+count_word_1, count_word_2)); 00486 }
| T lat::BitOps< T >::extractUnstraddled | ( | const T *restrict | p, | |
| unsigned int | maxbit, | |||
| unsigned int | from, | |||
| unsigned int | count | |||
| ) | [inline, static] |
Extract count bits from bit vector p, starting at bit position from, but not exceeding maxbit.
The vector of unsigned integral words of type T starting at p is treated as one long bit vector. The words are treated in their natural bit order: the bit position zero is the least significant bit of the first word in p, bit position N-1 (where N is the number of bits in T) is the most significant bit of the first word, bit position N is the least significant bit of the second word in p, and so on.
The caller guarantees that [from, from + count) does not straddle word boundaries of p elements. If from is less or equal to maxbit, from + count is also assumed to be. If from is greater than maxbit, zero is returned.
Definition at line 454 of file BitOps.h.
References lat::BitOps< T >::extractSafe().
00456 { return from > maxbit ? 0 : extractSafe (p, from, count); }
| bool lat::BitOps< T >::islog2 | ( | T | n | ) | [inline, static] |
| T lat::BitOps< T >::log2 | ( | T | n | ) | [inline, static] |
Compute log2 base of n, i.e.
the log2 of the most signficant set bit in n.
Definition at line 253 of file BitOps.h.
References bookConverter::compute().
00254 { return BitOpsLog2<BitTraits<T>::Bits/2>::template Op<T>::compute (n, 0); }
| T lat::BitOps< T >::mortonInterleave | ( | T | x, | |
| T | y | |||
| ) | [inline, static] |
Compute interleaved Morton Number for x and y.
Both x and y must use only the lower half bits of T.
Morton Numbers interleave the bits of x and y such that 2D plane squares close to (x, y) have Morton Numbers close to the Morton Number of (x, y). The interleaving has also the property that the numbers are proportional to x and y and leave no "gaps". 2D squares can thus be put in a vector indexed by the Morton Numbers of their (x, y) coordinates. The vector will have no gaps and squares close to each other will be close to each other in the linear sequence.
Definition at line 388 of file BitOps.h.
References bookConverter::compute().
00389 { return BitOpsMortonInterleave<BitTraits<T>::Bits/4>::template Op<T>::compute (x) 00390 | (BitOpsMortonInterleave<BitTraits<T>::Bits/4>::template Op<T>::compute (y) << 1); }
| void lat::BitOps< T >::mortonSplit | ( | T | n, | |
| T & | x, | |||
| T & | y | |||
| ) | [inline, static] |
Decode x and y from the interleaved Morton Number n.
Definition at line 396 of file BitOps.h.
References bookConverter::compute().
00397 { 00398 x = BitOpsMortonExtract<BitTraits<T>::Bits/4>::template Op<T>::compute (n); 00399 y = BitOpsMortonExtract<BitTraits<T>::Bits/4>::template Op<T>::compute (n >> 1); 00400 }
| bool lat::BitOps< T >::parity | ( | T | n | ) | [inline, static] |
Compute parity of n.
Returns true if n has an odd number of bits set.
Definition at line 310 of file BitOps.h.
References bookConverter::compute().
00311 { return BitOpsParity<BitTraits<T>::Bits/2>::template Op<T>::compute (n) & 1; }
| T lat::BitOps< T >::reverse | ( | T | n | ) | [inline, static] |
Reverse the order of bits in n: the least significant bit becomes the most signficant one and vice versa.
Definition at line 182 of file BitOps.h.
References bookConverter::compute().
00183 { return BitOpsReverse<BitTraits<T>::Bits/2>::template Op<T>::compute (n); }
| T lat::BitOps< T >::rzero | ( | T | n | ) | [inline, static] |
Compute the number of zero bits on the right edge of n, i.e the log2 of the least significant set bit in n.
Definition at line 220 of file BitOps.h.
References bookConverter::compute().
00221 { return BitOpsRZero<BitTraits<T>::Bits/2>::template Op<T>::compute 00222 (n, BitTraits<T>::Bits); }
| void lat::BitOps< T >::swap | ( | T & | x, | |
| T & | y | |||
| ) | [inline, static] |
1.5.4