Line | Count | Source |
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: |
22 | 12.2M | Bitmap256() { |
23 | 12.2M | Clear(); |
24 | 12.2M | } |
25 | | |
26 | | // Clears all of the bits. |
27 | 17.8M | void Clear() { |
28 | 17.8M | memset(words_, 0, sizeof words_); |
29 | 17.8M | } |
30 | | |
31 | | // Tests the bit with index c. |
32 | 121M | bool Test(int c) const { |
33 | 121M | ABSL_DCHECK_GE(c, 0); |
34 | 121M | ABSL_DCHECK_LE(c, 255); |
35 | | |
36 | 121M | return (words_[c / 64] & (uint64_t{1} << (c % 64))) != 0; |
37 | 121M | } |
38 | | |
39 | | // Sets the bit with index c. |
40 | 337M | void Set(int c) { |
41 | 337M | ABSL_DCHECK_GE(c, 0); |
42 | 337M | ABSL_DCHECK_LE(c, 255); |
43 | | |
44 | 337M | words_[c / 64] |= (uint64_t{1} << (c % 64)); |
45 | 337M | } |
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. |
53 | 310M | static int FindLSBSet(uint64_t n) { |
54 | 310M | ABSL_DCHECK_NE(n, uint64_t{0}); |
55 | 310M | #if defined(__GNUC__) |
56 | 310M | 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 | 310M | } |
82 | | |
83 | | uint64_t words_[4]; |
84 | | }; |
85 | | |
86 | | } // namespace re2 |
87 | | |
88 | | #endif // RE2_BITMAP256_H_ |