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: |
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] & (1ULL << (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] |= (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. |
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 | |
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 | |