1
2//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
3//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
4#pragma once
5
6#include "Prerequisites/BsPrerequisitesUtil.h"
7#include "Math/BsMath.h"
8#include "Utility/BsBitwise.h"
9
10namespace bs
11{
12 /** @addtogroup Implementation
13 * @{
14 */
15
16 class Bitfield;
17
18 /** References a single bit in a Bitfield. */
19 class BitReferenceConst
20 {
21 public:
22 BitReferenceConst(const uint32_t& data, uint32_t bitMask)
23 :mData(data), mBitMask(bitMask)
24 { }
25
26 operator bool() const
27 {
28 return (mData & mBitMask) != 0;
29 }
30
31 protected:
32 const uint32_t& mData;
33 uint32_t mBitMask;
34 };
35
36 /** References a single bit in a Bitfield and allows it to be modified. */
37 class BitReference
38 {
39 public:
40 BitReference(uint32_t& data, uint32_t bitMask)
41 :mData(data), mBitMask(bitMask)
42 { }
43
44 operator bool() const
45 {
46 return (mData & mBitMask) != 0;
47 }
48
49 BitReference& operator=(bool value)
50 {
51 if(value)
52 mData |= mBitMask;
53 else
54 mData &= ~mBitMask;
55
56 return *this;
57 }
58
59 BitReference& operator=(const BitReference& rhs)
60 {
61 *this = (bool)rhs;
62 return *this;
63 }
64
65 protected:
66 uint32_t& mData;
67 uint32_t mBitMask;
68 };
69
70 /** Helper template used for specifying types for const and non-const iterator variants for Bitfield. */
71 template<bool CONST>
72 struct TBitfieldIteratorTypes
73 { };
74
75 template<>
76 struct TBitfieldIteratorTypes<true>
77 {
78 typedef const Bitfield& ArrayType;
79 typedef BitReferenceConst ReferenceType;
80 };
81
82 template<>
83 struct TBitfieldIteratorTypes<false>
84 {
85 typedef Bitfield& ArrayType;
86 typedef BitReference ReferenceType;
87 };
88
89 /** Iterator for iterating over individual bits in a Bitfield. */
90 template<bool CONST>
91 class TBitfieldIterator
92 {
93 public:
94 typedef typename TBitfieldIteratorTypes<CONST>::ArrayType ArrayType;
95 typedef typename TBitfieldIteratorTypes<CONST>::ReferenceType ReferenceType;
96
97 TBitfieldIterator(ArrayType owner, uint32_t bitIndex, uint32_t dwordIndex, uint32_t mask)
98 : mOwner(owner), mBitIndex(bitIndex), mDwordIndex(dwordIndex), mMask(mask)
99 { }
100
101 TBitfieldIterator& operator++()
102 {
103 mBitIndex++;
104 mMask <<= 1;
105
106 if (!mMask)
107 {
108 mDwordIndex++;
109 mMask = 1;
110 }
111
112 return *this;
113 }
114
115 operator bool() const
116 {
117 return mBitIndex < mOwner.size();
118 }
119
120 bool operator!() const
121 {
122 return !(bool)*this;
123 }
124
125 bool operator!=(const TBitfieldIterator& rhs)
126 {
127 return mBitIndex != rhs.mBitIndex;
128 }
129
130 ReferenceType operator*() const
131 {
132 assert((bool)*this);
133
134 return ReferenceType(mOwner.mData[mDwordIndex], mMask);
135 }
136
137 private:
138 ArrayType mOwner;
139 uint32_t mBitIndex;
140 uint32_t mDwordIndex;
141 uint32_t mMask;
142 };
143
144 /** @} */
145
146 /** @addtogroup General
147 * @{
148 */
149
150 /**
151 * Dynamically sized field that contains a sequential list of bits. The bits are compactly stored and allow for
152 * quick sequential searches (compared to single or multi-byte type sequential searches).
153 */
154 class Bitfield
155 {
156 static constexpr uint32_t BITS_PER_DWORD = sizeof(uint32_t) * 8;
157 static constexpr uint32_t BITS_PER_DWORD_LOG2 = 5;
158
159 public:
160 using Iterator = TBitfieldIterator<false>;
161 using ConstIterator = TBitfieldIterator<true>;
162
163 /**
164 * Initializes the bitfield with enough storage for @p count bits and sets them to the initial value of @p value.
165 */
166 Bitfield(bool value = false, uint32_t count = 0)
167 :mNumBits(count)
168 {
169 if(count > 0)
170 {
171 realloc(count);
172 reset(value);
173 }
174 }
175
176 ~Bitfield()
177 {
178 if(mData)
179 bs_free(mData);
180 }
181
182 Bitfield(const Bitfield& other)
183 :mNumBits(other.mNumBits)
184 {
185 if (other.mMaxBits)
186 {
187 realloc(other.mMaxBits);
188
189 const uint32_t numBytes = Math::divideAndRoundUp(other.mNumBits, BITS_PER_DWORD) * sizeof(uint32_t);
190 memcpy(mData, other.mData, numBytes);
191 }
192 }
193
194 Bitfield(Bitfield&& other)
195 : mData(std::exchange(other.mData, nullptr))
196 , mMaxBits(std::exchange(other.mMaxBits, 0))
197 , mNumBits(std::exchange(other.mNumBits, 0))
198 { }
199
200 Bitfield& operator=(const Bitfield& rhs)
201 {
202 if(this != &rhs)
203 {
204 clear(true);
205 mNumBits = rhs.mNumBits;
206
207 if (rhs.mMaxBits)
208 {
209 realloc(rhs.mMaxBits);
210
211 const uint32_t numBytes = Math::divideAndRoundUp(rhs.mNumBits, BITS_PER_DWORD) * sizeof(uint32_t);
212 memcpy(mData, rhs.mData, numBytes);
213 }
214 }
215
216 return *this;
217 }
218
219 Bitfield& operator=(Bitfield&& rhs)
220 {
221 if(this != &rhs)
222 {
223 if (mData)
224 bs_free(mData);
225
226 mData = std::exchange(rhs.mData, nullptr);
227 mNumBits = std::exchange(rhs.mNumBits, 0);
228 mMaxBits = std::exchange(rhs.mMaxBits, 0);
229 }
230
231 return *this;
232 }
233
234 BitReference operator[](uint32_t idx)
235 {
236 assert(idx < mNumBits);
237
238 const uint32_t bitMask = 1 << (idx & (BITS_PER_DWORD - 1));
239 uint32_t& data = mData[idx >> BITS_PER_DWORD_LOG2];
240
241 return BitReference(data, bitMask);
242 }
243
244 BitReferenceConst operator[](uint32_t idx) const
245 {
246 assert(idx < mNumBits);
247
248 const uint32_t bitMask = 1 << (idx & (BITS_PER_DWORD - 1));
249 uint32_t& data = mData[idx >> BITS_PER_DWORD_LOG2];
250
251 return BitReferenceConst(data, bitMask);
252 }
253
254 /** Adds a new bit value to the end of the bitfield and returns the index of the added bit. */
255 uint32_t add(bool value)
256 {
257 if(mNumBits >= mMaxBits)
258 {
259 // Grow
260 const uint32_t newMaxBits = mMaxBits + 4 * BITS_PER_DWORD + mMaxBits / 2;
261 realloc(newMaxBits);
262 }
263
264 const uint32_t index = mNumBits;
265 mNumBits++;
266
267 (*this)[index] = value;
268 return index;
269 }
270
271 /** Removes a bit at the specified index. */
272 void remove(uint32_t index)
273 {
274 assert(index < mNumBits);
275
276 const uint32_t dwordIndex = index >> BITS_PER_DWORD_LOG2;
277 const uint32_t mask = 1 << (index & (BITS_PER_DWORD - 1));
278
279 const uint32_t curDwordBits = mData[dwordIndex];
280
281 // Mask the dword we want to remove the bit from
282 const uint32_t firstHalfMask = mask - 1; // These stay the same
283 const uint32_t secondHalfMask = ~firstHalfMask; // These get shifted so the removed bit gets moved outside the mask
284
285 mData[dwordIndex] = (curDwordBits & firstHalfMask) | (((curDwordBits >> 1) & secondHalfMask));
286
287 // Grab the last bit from the next dword and put it as the last bit in the current dword. Then shift the
288 // next dword and repeat until all following dwords are processed.
289 const uint32_t lastDwordIndex = (mNumBits - 1) >> BITS_PER_DWORD_LOG2;
290 for(uint32_t i = dwordIndex; i < lastDwordIndex; i++)
291 {
292 // First bit from next dword goes at the end of the current dword
293 mData[i] |= (mData[i + 1] & 0x1) << 31;
294
295 // Following dword gets shifted, removing the bit we just mvoed
296 mData[i + 1] >>= 1;
297 }
298
299 mNumBits--;
300 }
301
302 /** Attempts to find the first non-zero bit in the field. Returns -1 if all bits are zero or the field is empty. */
303 uint32_t find(bool value) const
304 {
305 const uint32_t mask = value ? 0 : (uint32_t)-1;
306 const uint32_t numDWords = Math::divideAndRoundUp(mNumBits, BITS_PER_DWORD);
307
308 for(uint32_t i = 0; i < numDWords; i++)
309 {
310 if(mData[i] == mask)
311 continue;
312
313 const uint32_t bits = value ? mData[i] : ~mData[i];
314 const uint32_t bitIndex = i * BITS_PER_DWORD + Bitwise::leastSignificantBit(bits);
315
316 if(bitIndex < mNumBits)
317 return bitIndex;
318 }
319
320 return (uint32_t)-1;
321 }
322
323 /** Counts the number of values in the bit field. */
324 uint32_t count(bool value) const
325 {
326 // Note: Implement this faster via popcnt and similar instructions
327
328 uint32_t counter = 0;
329 for(const auto& entry : *this)
330 {
331 if(entry == value)
332 counter++;
333 }
334
335 return counter;
336 }
337
338 /** Resets all the bits in the field to the specified value. */
339 void reset(bool value = false)
340 {
341 if(mNumBits == 0)
342 return;
343
344 const int32_t mask = value ? 0xFF : 0;
345 const uint32_t numBytes = Math::divideAndRoundUp(mNumBits, BITS_PER_DWORD) * sizeof(uint32_t);
346 memset(mData, mask, numBytes);
347 }
348
349 /**
350 * Removes all the bits from the field. If @p free is true then the underlying memory buffers will be freed as
351 * well.
352 */
353 void clear(bool free = false)
354 {
355 mNumBits = 0;
356
357 if(free)
358 {
359 if (mData)
360 {
361 bs_free(mData);
362 mData = nullptr;
363 }
364
365 mMaxBits = 0;
366 }
367 }
368
369 /** Returns the number of bits in the bitfield */
370 uint32_t size() const
371 {
372 return mNumBits;
373 }
374
375 /** Returns a non-const iterator pointing to the first bit in the bitfield. */
376 Iterator begin()
377 {
378 return Iterator(*this, 0, 0, 1);
379 }
380
381 /** Returns a non-const interator pointing past the last bit in the bitfield. */
382 Iterator end()
383 {
384 uint32_t bitIndex = mNumBits;
385 uint32_t dwordIndex = bitIndex >> BITS_PER_DWORD_LOG2;
386 uint32_t mask = 1 << (bitIndex & (BITS_PER_DWORD - 1));
387
388 return Iterator(*this, bitIndex, dwordIndex, mask);
389 }
390
391 /** Returns a const iterator pointing to the first bit in the bitfield. */
392 ConstIterator begin() const
393 {
394 return ConstIterator(*this, 0, 0, 1);
395 }
396
397 /** Returns a const interator pointing past the last bit in the bitfield. */
398 ConstIterator end() const
399 {
400 uint32_t bitIndex = mNumBits;
401 uint32_t dwordIndex = bitIndex >> BITS_PER_DWORD_LOG2;
402 uint32_t mask = 1 << (bitIndex & (BITS_PER_DWORD - 1));
403
404 return ConstIterator(*this, bitIndex, dwordIndex, mask);
405 }
406
407 private:
408 template<bool CONST>
409 friend class TBitfieldIterator;
410
411 /** Reallocates the internal buffer making enough room for @p numBits (rounded to a multiple of DWORD). */
412 void realloc(uint32_t numBits)
413 {
414 numBits = Math::divideAndRoundUp(numBits, BITS_PER_DWORD) * BITS_PER_DWORD;
415
416 if(numBits != mMaxBits)
417 {
418 assert(numBits > mMaxBits);
419
420 const uint32_t numDwords = Math::divideAndRoundUp(numBits, BITS_PER_DWORD);
421
422 // Note: Eventually add support for custom allocators
423 auto buffer = bs_allocN<uint32_t>(numDwords);
424 if(mData)
425 {
426 const uint32_t numBytes = Math::divideAndRoundUp(mMaxBits, BITS_PER_DWORD) * sizeof(uint32_t);
427 memcpy(buffer, mData, numBytes);
428 bs_free(mData);
429 }
430
431 mData = buffer;
432 mMaxBits = numBits;
433 }
434 }
435
436 uint32_t* mData = nullptr;
437 uint32_t mMaxBits = 0;
438 uint32_t mNumBits;
439 };
440
441
442}
443
444/** @cond SPECIALIZATIONS */
445/** @addtogroup Implementation
446 * @{
447 */
448
449namespace std
450{
451 template <> inline void swap(bs::BitReference& lhs, bs::BitReference& rhs)
452 {
453 const bool temp = lhs;
454 lhs = rhs;
455 rhs = temp;
456 }
457
458 inline void swap(bs::BitReference&& lhs, bs::BitReference&& rhs)
459 {
460 const bool temp = lhs;
461 lhs = rhs;
462 rhs = temp;
463 }
464};
465
466/** @endgroup */
467/** @endcond */