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 #include <stdint.h> 9 #include <string.h> 10 11 #include "absl/log/absl_check.h" 12 #include "absl/log/absl_log.h" 13 14 #ifdef _MSC_VER 15 #include <intrin.h> 16 #endif 17 18 namespace re2 { 19 20 class Bitmap256 { 21 public: Bitmap256()22 Bitmap256() { 23 Clear(); 24 } 25 26 // Clears all of the bits. Clear()27 void Clear() { 28 memset(words_, 0, sizeof words_); 29 } 30 31 // Tests the bit with index c. Test(int c)32 bool Test(int c) const { 33 ABSL_DCHECK_GE(c, 0); 34 ABSL_DCHECK_LE(c, 255); 35 36 return (words_[c / 64] & (uint64_t{1} << (c % 64))) != 0; 37 } 38 39 // Sets the bit with index c. Set(int c)40 void Set(int c) { 41 ABSL_DCHECK_GE(c, 0); 42 ABSL_DCHECK_LE(c, 255); 43 44 words_[c / 64] |= (uint64_t{1} << (c % 64)); 45 } 46 47 // Finds the next non-zero bit with index >= c. 48 // Returns -1 if no such bit exists. 49 int FindNextSetBit(int c) const; 50 51 private: 52 // Finds the least significant non-zero bit in n. FindLSBSet(uint64_t n)53 static int FindLSBSet(uint64_t n) { 54 ABSL_DCHECK_NE(n, uint64_t{0}); 55 #if defined(__GNUC__) 56 return __builtin_ctzll(n); 57 #elif defined(_MSC_VER) && defined(_M_X64) 58 unsigned long c; 59 _BitScanForward64(&c, n); 60 return static_cast<int>(c); 61 #elif defined(_MSC_VER) && defined(_M_IX86) 62 unsigned long c; 63 if (static_cast<uint32_t>(n) != 0) { 64 _BitScanForward(&c, static_cast<uint32_t>(n)); 65 return static_cast<int>(c); 66 } else { 67 _BitScanForward(&c, static_cast<uint32_t>(n >> 32)); 68 return static_cast<int>(c) + 32; 69 } 70 #else 71 int c = 63; 72 for (int shift = 1 << 5; shift != 0; shift >>= 1) { 73 uint64_t word = n << shift; 74 if (word != 0) { 75 n = word; 76 c -= shift; 77 } 78 } 79 return c; 80 #endif 81 } 82 83 uint64_t words_[4]; 84 }; 85 86 } // namespace re2 87 88 #endif // RE2_BITMAP256_H_ 89