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/util.h"
15 #include "util/logging.h"
16
17 namespace re2 {
18
19 class Bitmap256 {
20 public:
Bitmap256()21 Bitmap256() {
22 Clear();
23 }
24
25 // Clears all of the bits.
Clear()26 void Clear() {
27 memset(words_, 0, sizeof words_);
28 }
29
30 // Tests the bit with index c.
Test(int c)31 bool Test(int c) const {
32 DCHECK_GE(c, 0);
33 DCHECK_LE(c, 255);
34
35 return (words_[c / 64] & (uint64_t{1} << (c % 64))) != 0;
36 }
37
38 // Sets the bit with index c.
Set(int c)39 void Set(int c) {
40 DCHECK_GE(c, 0);
41 DCHECK_LE(c, 255);
42
43 words_[c / 64] |= (uint64_t{1} << (c % 64));
44 }
45
46 // Finds the next non-zero bit with index >= c.
47 // Returns -1 if no such bit exists.
48 int FindNextSetBit(int c) const;
49
50 private:
51 // Finds the least significant non-zero bit in n.
FindLSBSet(uint64_t n)52 static int FindLSBSet(uint64_t n) {
53 DCHECK_NE(n, 0);
54 #if defined(__GNUC__)
55 return __builtin_ctzll(n);
56 #elif defined(_MSC_VER) && defined(_M_X64)
57 unsigned long c;
58 _BitScanForward64(&c, n);
59 return static_cast<int>(c);
60 #elif defined(_MSC_VER) && defined(_M_IX86)
61 unsigned long c;
62 if (static_cast<uint32_t>(n) != 0) {
63 _BitScanForward(&c, static_cast<uint32_t>(n));
64 return static_cast<int>(c);
65 } else {
66 _BitScanForward(&c, static_cast<uint32_t>(n >> 32));
67 return static_cast<int>(c) + 32;
68 }
69 #else
70 int c = 63;
71 for (int shift = 1 << 5; shift != 0; shift >>= 1) {
72 uint64_t word = n << shift;
73 if (word != 0) {
74 n = word;
75 c -= shift;
76 }
77 }
78 return c;
79 #endif
80 }
81
82 uint64_t words_[4];
83 };
84
FindNextSetBit(int c)85 int Bitmap256::FindNextSetBit(int c) const {
86 DCHECK_GE(c, 0);
87 DCHECK_LE(c, 255);
88
89 // Check the word that contains the bit. Mask out any lower bits.
90 int i = c / 64;
91 uint64_t word = words_[i] & (~uint64_t{0} << (c % 64));
92 if (word != 0)
93 return (i * 64) + FindLSBSet(word);
94
95 // Check any following words.
96 i++;
97 switch (i) {
98 case 1:
99 if (words_[1] != 0)
100 return (1 * 64) + FindLSBSet(words_[1]);
101 FALLTHROUGH_INTENDED;
102 case 2:
103 if (words_[2] != 0)
104 return (2 * 64) + FindLSBSet(words_[2]);
105 FALLTHROUGH_INTENDED;
106 case 3:
107 if (words_[3] != 0)
108 return (3 * 64) + FindLSBSet(words_[3]);
109 FALLTHROUGH_INTENDED;
110 default:
111 return -1;
112 }
113 }
114
115 } // namespace re2
116
117 #endif // RE2_BITMAP256_H_
118