ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GBitVec.h
(Generate patch)
# Line 3 | Line 3
3   #include "GBase.h"
4   //this code is lifted from LLVM (llvm.org, BitVector.h)
5  
6 + /// bitCount_32 - this function counts the number of set bits in a value.
7 + /// Ex. CountPopulation(0xF000F000) = 8
8 + /// Returns 0 if the word is zero.
9 + inline uint bitCount_32(uint32_t Value) {
10 + #if __GNUC__ >= 4
11 +    return __builtin_popcount(Value);
12 + #else
13 +    uint32_t v = Value - ((Value >> 1) & 0x55555555);
14 +    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
15 +    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
16 + #endif
17 +  }
18 +
19 + /// bitCount_64 - this function counts the number of set bits in a value,
20 + /// (64 bit edition.)
21 + inline uint bitCount_64(uint64_t Value) {
22 + #if __GNUC__ >= 4
23 +    return __builtin_popcountll(Value);
24 + #else
25 +    uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
26 +    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
27 +    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
28 +    return uint((uint64_t)(v * 0x0101010101010101ULL) >> 56);
29 + #endif
30 +  }
31 +
32 + /// CountTrailingZeros_32 - this function performs the platform optimal form of
33 + /// counting the number of zeros from the least significant bit to the first one
34 + /// bit.  Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
35 + /// Returns 32 if the word is zero.
36 + inline unsigned bitCountTrailingZeros_32(uint32_t Value) {
37 + #if __GNUC__ >= 4
38 +  return Value ? __builtin_ctz(Value) : 32;
39 + #else
40 +  static const unsigned Mod37BitPosition[] = {
41 +    32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
42 +    4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
43 +    5, 20, 8, 19, 18
44 +  };
45 +  return Mod37BitPosition[(-Value & Value) % 37];
46 + #endif
47 + }
48 +
49 + // CountTrailingZeros_64 - This function performs the platform optimal form
50 + /// of counting the number of zeros from the least significant bit to the first
51 + /// one bit (64 bit edition.)
52 + /// Returns 64 if the word is zero.
53 + inline unsigned bitCountTrailingZeros_64(uint64_t Value) {
54 + #if __GNUC__ >= 4
55 +  return Value ? __builtin_ctzll(Value) : 64;
56 + #else
57 +  static const unsigned Mod67Position[] = {
58 +    64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
59 +    4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
60 +    47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
61 +    29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
62 +    7, 48, 35, 6, 34, 33, 0
63 +  };
64 +  return Mod67Position[(-Value & Value) % 67];
65 + #endif
66 + }
67  
68   class GBitVec {
69    typedef unsigned long BitWord;
# Line 174 | Line 235
235      return -1;
236    }
237  
238 <  /// clear - Clear all bits.
238 >  /// clear - Clear all bits; does NOT release memory
239    void clear() {
240      Size = 0;
241    }
# Line 271 | Line 332
332    bool operator==(const GBitVec &RHS) const {
333      uint ThisWords = NumBitWords(size());
334      uint RHSWords  = NumBitWords(RHS.size());
335 <    uint i;
336 <    for (i = 0; i != GMIN(ThisWords, RHSWords); ++i)
335 >    register uint i;
336 >    uint imax=GMIN(ThisWords, RHSWords);
337 >    for (i = 0; i != imax; ++i)
338        if (fBits[i] != RHS.fBits[i])
339          return false;
340  
# Line 297 | Line 359
359    GBitVec &operator&=(const GBitVec &RHS) {
360      uint ThisWords = NumBitWords(size());
361      uint RHSWords  = NumBitWords(RHS.size());
362 <    uint i;
363 <    for (i = 0; i != GMIN(ThisWords, RHSWords); ++i)
362 >    register uint i;
363 >    uint imax=GMIN(ThisWords, RHSWords);
364 >    for (i = 0; i != imax; ++i)
365        fBits[i] &= RHS.fBits[i];
366  
367      // Any bits that are just in this GBitVec become zero, because they aren't

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines