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 "absl/base/macros.h" |
15 | #include "util/logging.h" |
16 | |
17 | namespace re2 { |
18 | |
19 | class Bitmap256 { |
20 | public: |
21 | Bitmap256() { |
22 | Clear(); |
23 | } |
24 | |
25 | // Clears all of the bits. |
26 | void Clear() { |
27 | memset(words_, 0, sizeof words_); |
28 | } |
29 | |
30 | // Tests the bit with index 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. |
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. |
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 | |
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 | ABSL_FALLTHROUGH_INTENDED; |
102 | case 2: |
103 | if (words_[2] != 0) |
104 | return (2 * 64) + FindLSBSet(words_[2]); |
105 | ABSL_FALLTHROUGH_INTENDED; |
106 | case 3: |
107 | if (words_[3] != 0) |
108 | return (3 * 64) + FindLSBSet(words_[3]); |
109 | ABSL_FALLTHROUGH_INTENDED; |
110 | default: |
111 | return -1; |
112 | } |
113 | } |
114 | |
115 | } // namespace re2 |
116 | |
117 | #endif // RE2_BITMAP256_H_ |
118 | |