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