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
17namespace re2 {
18
19class 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
86int 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