summaryrefslogtreecommitdiff
path: root/src/common/bit_set.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/bit_set.h')
-rw-r--r--src/common/bit_set.h244
1 files changed, 0 insertions, 244 deletions
diff --git a/src/common/bit_set.h b/src/common/bit_set.h
deleted file mode 100644
index 5cd1352b2..000000000
--- a/src/common/bit_set.h
+++ /dev/null
@@ -1,244 +0,0 @@
1// This file is under the public domain.
2
3#pragma once
4
5#include <cstddef>
6#ifdef _WIN32
7#include <intrin.h>
8#endif
9#include <initializer_list>
10#include <new>
11#include <type_traits>
12#include "common/common_types.h"
13
14// namespace avoids conflict with OS X Carbon; don't use BitSet<T> directly
15namespace Common {
16
17// Helper functions:
18
19#ifdef _MSC_VER
20template <typename T>
21static inline int CountSetBits(T v) {
22 // from https://graphics.stanford.edu/~seander/bithacks.html
23 // GCC has this built in, but MSVC's intrinsic will only emit the actual
24 // POPCNT instruction, which we're not depending on
25 v = v - ((v >> 1) & (T) ~(T)0 / 3);
26 v = (v & (T) ~(T)0 / 15 * 3) + ((v >> 2) & (T) ~(T)0 / 15 * 3);
27 v = (v + (v >> 4)) & (T) ~(T)0 / 255 * 15;
28 return (T)(v * ((T) ~(T)0 / 255)) >> (sizeof(T) - 1) * 8;
29}
30static inline int LeastSignificantSetBit(u8 val) {
31 unsigned long index;
32 _BitScanForward(&index, val);
33 return (int)index;
34}
35static inline int LeastSignificantSetBit(u16 val) {
36 unsigned long index;
37 _BitScanForward(&index, val);
38 return (int)index;
39}
40static inline int LeastSignificantSetBit(u32 val) {
41 unsigned long index;
42 _BitScanForward(&index, val);
43 return (int)index;
44}
45static inline int LeastSignificantSetBit(u64 val) {
46 unsigned long index;
47 _BitScanForward64(&index, val);
48 return (int)index;
49}
50#else
51static inline int CountSetBits(u8 val) {
52 return __builtin_popcount(val);
53}
54static inline int CountSetBits(u16 val) {
55 return __builtin_popcount(val);
56}
57static inline int CountSetBits(u32 val) {
58 return __builtin_popcount(val);
59}
60static inline int CountSetBits(u64 val) {
61 return __builtin_popcountll(val);
62}
63static inline int LeastSignificantSetBit(u8 val) {
64 return __builtin_ctz(val);
65}
66static inline int LeastSignificantSetBit(u16 val) {
67 return __builtin_ctz(val);
68}
69static inline int LeastSignificantSetBit(u32 val) {
70 return __builtin_ctz(val);
71}
72static inline int LeastSignificantSetBit(u64 val) {
73 return __builtin_ctzll(val);
74}
75#endif
76
77// Similar to std::bitset, this is a class which encapsulates a bitset, i.e.
78// using the set bits of an integer to represent a set of integers. Like that
79// class, it acts like an array of bools:
80// BitSet32 bs;
81// bs[1] = true;
82// but also like the underlying integer ([0] = least significant bit):
83// BitSet32 bs2 = ...;
84// bs = (bs ^ bs2) & BitSet32(0xffff);
85// The following additional functionality is provided:
86// - Construction using an initializer list.
87// BitSet bs { 1, 2, 4, 8 };
88// - Efficiently iterating through the set bits:
89// for (int i : bs)
90// [i is the *index* of a set bit]
91// (This uses the appropriate CPU instruction to find the next set bit in one
92// operation.)
93// - Counting set bits using .Count() - see comment on that method.
94
95// TODO: use constexpr when MSVC gets out of the Dark Ages
96
97template <typename IntTy>
98class BitSet {
99 static_assert(!std::is_signed_v<IntTy>, "BitSet should not be used with signed types");
100
101public:
102 // A reference to a particular bit, returned from operator[].
103 class Ref {
104 public:
105 Ref(Ref&& other) : m_bs(other.m_bs), m_mask(other.m_mask) {}
106 Ref(BitSet* bs, IntTy mask) : m_bs(bs), m_mask(mask) {}
107 operator bool() const {
108 return (m_bs->m_val & m_mask) != 0;
109 }
110 bool operator=(bool set) {
111 m_bs->m_val = (m_bs->m_val & ~m_mask) | (set ? m_mask : 0);
112 return set;
113 }
114
115 private:
116 BitSet* m_bs;
117 IntTy m_mask;
118 };
119
120 // A STL-like iterator is required to be able to use range-based for loops.
121 class Iterator {
122 public:
123 Iterator(const Iterator& other) : m_val(other.m_val), m_bit(other.m_bit) {}
124 Iterator(IntTy val) : m_val(val), m_bit(0) {}
125 Iterator& operator=(Iterator other) {
126 new (this) Iterator(other);
127 return *this;
128 }
129 int operator*() {
130 return m_bit + ComputeLsb();
131 }
132 Iterator& operator++() {
133 int lsb = ComputeLsb();
134 m_val >>= lsb + 1;
135 m_bit += lsb + 1;
136 m_has_lsb = false;
137 return *this;
138 }
139 Iterator operator++(int _) {
140 Iterator other(*this);
141 ++*this;
142 return other;
143 }
144 bool operator==(Iterator other) const {
145 return m_val == other.m_val;
146 }
147 bool operator!=(Iterator other) const {
148 return m_val != other.m_val;
149 }
150
151 private:
152 int ComputeLsb() {
153 if (!m_has_lsb) {
154 m_lsb = LeastSignificantSetBit(m_val);
155 m_has_lsb = true;
156 }
157 return m_lsb;
158 }
159 IntTy m_val;
160 int m_bit;
161 int m_lsb = -1;
162 bool m_has_lsb = false;
163 };
164
165 BitSet() : m_val(0) {}
166 explicit BitSet(IntTy val) : m_val(val) {}
167 BitSet(std::initializer_list<int> init) {
168 m_val = 0;
169 for (int bit : init)
170 m_val |= (IntTy)1 << bit;
171 }
172
173 static BitSet AllTrue(std::size_t count) {
174 return BitSet(count == sizeof(IntTy) * 8 ? ~(IntTy)0 : (((IntTy)1 << count) - 1));
175 }
176
177 Ref operator[](std::size_t bit) {
178 return Ref(this, (IntTy)1 << bit);
179 }
180 const Ref operator[](std::size_t bit) const {
181 return (*const_cast<BitSet*>(this))[bit];
182 }
183 bool operator==(BitSet other) const {
184 return m_val == other.m_val;
185 }
186 bool operator!=(BitSet other) const {
187 return m_val != other.m_val;
188 }
189 bool operator<(BitSet other) const {
190 return m_val < other.m_val;
191 }
192 bool operator>(BitSet other) const {
193 return m_val > other.m_val;
194 }
195 BitSet operator|(BitSet other) const {
196 return BitSet(m_val | other.m_val);
197 }
198 BitSet operator&(BitSet other) const {
199 return BitSet(m_val & other.m_val);
200 }
201 BitSet operator^(BitSet other) const {
202 return BitSet(m_val ^ other.m_val);
203 }
204 BitSet operator~() const {
205 return BitSet(~m_val);
206 }
207 BitSet& operator|=(BitSet other) {
208 return *this = *this | other;
209 }
210 BitSet& operator&=(BitSet other) {
211 return *this = *this & other;
212 }
213 BitSet& operator^=(BitSet other) {
214 return *this = *this ^ other;
215 }
216 operator u32() = delete;
217 operator bool() {
218 return m_val != 0;
219 }
220
221 // Warning: Even though on modern CPUs this is a single fast instruction,
222 // Dolphin's official builds do not currently assume POPCNT support on x86,
223 // so slower explicit bit twiddling is generated. Still should generally
224 // be faster than a loop.
225 unsigned int Count() const {
226 return CountSetBits(m_val);
227 }
228
229 Iterator begin() const {
230 return Iterator(m_val);
231 }
232 Iterator end() const {
233 return Iterator(0);
234 }
235
236 IntTy m_val;
237};
238
239} // namespace Common
240
241typedef Common::BitSet<u8> BitSet8;
242typedef Common::BitSet<u16> BitSet16;
243typedef Common::BitSet<u32> BitSet32;
244typedef Common::BitSet<u64> BitSet64;
HIC SVNT DRACONES