Rev | Line | |
---|
[176] | 1 | /* -*- C++ -*- */ |
---|
| 2 | |
---|
| 3 | /** |
---|
| 4 | * @file bitindex.h |
---|
| 5 | * |
---|
| 6 | * Bit-access operations, including msb and lsb. |
---|
| 7 | * @author Emery Berger (emery@cs.umass.edu) |
---|
| 8 | */ |
---|
| 9 | |
---|
| 10 | // lsb is due to Leiserson, Prokop, Randall (MIT). |
---|
| 11 | // msb is also a fast implementation of floor(lg_2). |
---|
| 12 | |
---|
| 13 | #ifndef _BITINDEX_H_ |
---|
| 14 | #define _BITINDEX_H_ |
---|
| 15 | |
---|
| 16 | #include <assert.h> |
---|
| 17 | |
---|
| 18 | namespace HL { |
---|
| 19 | |
---|
| 20 | class BitIndex { |
---|
| 21 | private: |
---|
| 22 | |
---|
| 23 | enum { debruijn32 = 0x077CB531UL }; |
---|
| 24 | static int index32[32]; |
---|
| 25 | static unsigned long lgtable[16]; |
---|
| 26 | static unsigned long on[32]; |
---|
| 27 | static unsigned long off[32]; |
---|
| 28 | |
---|
| 29 | void setup (void); |
---|
| 30 | |
---|
| 31 | public: |
---|
| 32 | |
---|
| 33 | BitIndex (void); |
---|
| 34 | ~BitIndex (void) {} |
---|
| 35 | |
---|
| 36 | // Set bit_index in b (to 1). |
---|
| 37 | static void set (unsigned long &b, int index) |
---|
| 38 | { |
---|
| 39 | assert (index >= 0); |
---|
| 40 | assert (index < 32); |
---|
| 41 | b |= on[index]; |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | // Reset bit_index in b (set it to 0). |
---|
| 45 | static void reset (unsigned long &b, int index) |
---|
| 46 | { |
---|
| 47 | assert (index >= 0); |
---|
| 48 | assert (index < 32); |
---|
| 49 | b &= off[index]; |
---|
| 50 | } |
---|
| 51 | |
---|
| 52 | // Find the least-significant bit. |
---|
| 53 | static int lsb (unsigned long b) |
---|
| 54 | { |
---|
| 55 | //#if 0 |
---|
| 56 | #if 0 // i386 |
---|
| 57 | // Intel x86 code. |
---|
| 58 | register unsigned long index = 0; |
---|
| 59 | if (b > 0) { |
---|
| 60 | asm ("bsfl %1, %0" : "=r" (index) : "r" (b)); |
---|
| 61 | } |
---|
| 62 | return index; |
---|
| 63 | #else |
---|
| 64 | b &= (unsigned long) -((signed long) b); |
---|
| 65 | b *= debruijn32; |
---|
| 66 | b >>= 27; |
---|
| 67 | return index32[b]; |
---|
| 68 | #endif |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | // Find the most-significant bit. |
---|
| 72 | static int msb (unsigned long b) |
---|
| 73 | { |
---|
| 74 | #if 0 // i386 |
---|
| 75 | // Intel x86 code. |
---|
| 76 | register unsigned long index = 0; |
---|
| 77 | if (b > 0) { |
---|
| 78 | asm ("bsrl %1, %0" : "=r" (index) : "r" (b)); |
---|
| 79 | } |
---|
| 80 | return index; |
---|
| 81 | #else |
---|
| 82 | int l = 0; |
---|
| 83 | // b < 2^32 |
---|
| 84 | if (b >= 65536) { |
---|
| 85 | l += 16; |
---|
| 86 | b >>= 16; |
---|
| 87 | } |
---|
| 88 | // b < 2^16 |
---|
| 89 | if (b >= 256) { |
---|
| 90 | l += 8; |
---|
| 91 | b >>= 8; |
---|
| 92 | } |
---|
| 93 | // b < 2^8 |
---|
| 94 | if (b >= 16) { |
---|
| 95 | l += 4; |
---|
| 96 | b >>= 4; |
---|
| 97 | } |
---|
| 98 | return l + lgtable[b]; |
---|
| 99 | #endif |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | |
---|
| 103 | }; |
---|
| 104 | |
---|
| 105 | }; |
---|
| 106 | |
---|
| 107 | #endif |
---|
Note: See
TracBrowser
for help on using the repository browser.