1 // Copyright 2016 The RE2 Authors. All Rights Reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 #ifndef RE2_BITMAP256_H_ 6 #define RE2_BITMAP256_H_ 7 8 #ifdef _MSC_VER 9 #include <intrin.h> 10 #endif 11 #include <stdint.h> 12 #include <string.h> 13 14 #include "util/logging.h" 15 16 namespace re2 { 17 18 class Bitmap256 { 19 public: Bitmap256()20 Bitmap256() { 21 Clear(); 22 } 23 24 // Clears all of the bits. Clear()25 void Clear() { 26 memset(words_, 0, sizeof words_); 27 } 28 29 // Tests the bit with index c. Test(int c)30 bool Test(int c) const { 31 DCHECK_GE(c, 0); 32 DCHECK_LE(c, 255); 33 34 return (words_[c / 64] & (uint64_t{1} << (c % 64))) != 0; 35 } 36 37 // Sets the bit with index c. Set(int c)38 void Set(int c) { 39 DCHECK_GE(c, 0); 40 DCHECK_LE(c, 255); 41 42 words_[c / 64] |= (uint64_t{1} << (c % 64)); 43 } 44 45 // Finds the next non-zero bit with index >= c. 46 // Returns -1 if no such bit exists. 47 int FindNextSetBit(int c) const; 48 49 private: 50 // Finds the least significant non-zero bit in n. FindLSBSet(uint64_t n)51 static int FindLSBSet(uint64_t n) { 52 DCHECK_NE(n, 0); 53 #if defined(__GNUC__) 54 return __builtin_ctzll(n); 55 #elif defined(_MSC_VER) && defined(_M_X64) 56 unsigned long c; 57 _BitScanForward64(&c, n); 58 return static_cast<int>(c); 59 #elif defined(_MSC_VER) && defined(_M_IX86) 60 unsigned long c; 61 if (static_cast<uint32_t>(n) != 0) { 62 _BitScanForward(&c, static_cast<uint32_t>(n)); 63 return static_cast<int>(c); 64 } else { 65 _BitScanForward(&c, static_cast<uint32_t>(n >> 32)); 66 return static_cast<int>(c) + 32; 67 } 68 #else 69 int c = 63; 70 for (int shift = 1 << 5; shift != 0; shift >>= 1) { 71 uint64_t word = n << shift; 72 if (word != 0) { 73 n = word; 74 c -= shift; 75 } 76 } 77 return c; 78 #endif 79 } 80 81 uint64_t words_[4]; 82 }; 83 84 } // namespace re2 85 86 #endif // RE2_BITMAP256_H_ 87