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] & (1ULL << (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] |= (1ULL << (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
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
FindNextSetBit(int c)86 int Bitmap256::FindNextSetBit(int c) const {
87 DCHECK_GE(c, 0);
88 DCHECK_LE(c, 255);
89
90 // Check the word that contains the bit. Mask out any lower bits.
91 int i = c / 64;
92 uint64_t word = words_[i] & (~0ULL << (c % 64));
93 if (word != 0)
94 return (i * 64) + FindLSBSet(word);
95
96 // Check any following words.
97 i++;
98 switch (i) {
99 case 1:
100 if (words_[1] != 0)
101 return (1 * 64) + FindLSBSet(words_[1]);
102 FALLTHROUGH_INTENDED;
103 case 2:
104 if (words_[2] != 0)
105 return (2 * 64) + FindLSBSet(words_[2]);
106 FALLTHROUGH_INTENDED;
107 case 3:
108 if (words_[3] != 0)
109 return (3 * 64) + FindLSBSet(words_[3]);
110 FALLTHROUGH_INTENDED;
111 default:
112 return -1;
113 }
114 }
115
116 } // namespace re2
117
118 #endif // RE2_BITMAP256_H_
119