Blender V5.3
BLI_bit_span.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#pragma once
10
11#include <optional>
12
13#include "BLI_bit_ref.hh"
14#include "BLI_index_range.hh"
15#include "BLI_math_bits.hh"
16#include "BLI_memory_utils.hh"
17
18namespace blender {
19
20namespace bits {
21
24 protected:
25 const BitInt *data_;
27
28 public:
29 BitIteratorBase(const BitInt *data, const int64_t bit_index) : data_(data), bit_index_(bit_index)
30 {
31 }
32
34 {
35 bit_index_++;
36 return *this;
37 }
38
39 friend bool operator!=(const BitIteratorBase &a, const BitIteratorBase &b)
40 {
41 BLI_assert(a.data_ == b.data_);
42 return a.bit_index_ != b.bit_index_;
43 }
44};
45
48 public:
49 BitIterator(const BitInt *data, const int64_t bit_index) : BitIteratorBase(data, bit_index) {}
50
52 {
53 return BitRef(data_, bit_index_);
54 }
55};
56
59 public:
60 MutableBitIterator(BitInt *data, const int64_t bit_index) : BitIteratorBase(data, bit_index) {}
61
63 {
64 return MutableBitRef(const_cast<BitInt *>(data_), bit_index_);
65 }
66};
67
69 private:
70 BitInt data_;
71 int current_bit_;
72
73 public:
74 explicit OneBitIterator(BitInt data) : data_(data)
75 {
76 this->operator++();
77 }
78
79 int operator*() const
80 {
81 return current_bit_;
82 }
83
85 {
86 if (data_ > 0) {
87 current_bit_ = bitscan_forward_clear_uint64(&data_);
88 }
89 else {
90 current_bit_ = -1;
91 }
92 return *this;
93 }
94
95 friend bool operator!=(const OneBitIterator &a, const OneBitIterator &b)
96 {
97 return a.current_bit_ != b.current_bit_;
98 }
99};
100
102 private:
103 const BitInt data_;
104
105 public:
107
109 {
110 return OneBitIterator(data_);
111 }
113 {
114 return OneBitIterator(0);
115 }
116};
117
119{
120 return OneBitIteratorRange(value);
121}
122
130class BitSpan {
131 protected:
136 const BitInt *data_ = nullptr;
139
140 public:
142 BitSpan() = default;
143
144 BitSpan(const BitInt *data, const int64_t size_in_bits) : data_(data), bit_range_(size_in_bits)
145 {
146 }
147
149
151 int64_t size() const
152 {
153 return bit_range_.size();
154 }
155
156 bool is_empty() const
157 {
158 return bit_range_.is_empty();
159 }
160
162 {
163 return IndexRange(bit_range_.size());
164 }
165
166 [[nodiscard]] BitRef operator[](const int64_t index) const
167 {
168 BLI_assert(index >= 0);
170 return {data_, bit_range_.start() + index};
171 }
172
173 [[nodiscard]] BitSpan slice(const IndexRange range) const
174 {
175 return {data_, bit_range_.slice(range)};
176 }
177
179 {
180 return {data_, bit_range_.take_front(n)};
181 }
182
183 BitSpan take_back(const int64_t n) const
184 {
185 return {data_, bit_range_.take_back(n)};
186 }
187
189 {
190 return {data_, bit_range_.drop_front(n)};
191 }
192
193 BitSpan drop_back(const int64_t n) const
194 {
195 return {data_, bit_range_.drop_back(n)};
196 }
197
198 const BitInt *data() const
199 {
200 return data_;
201 }
202
203 const IndexRange &bit_range() const
204 {
205 return bit_range_;
206 }
207
209 {
210 return {data_, bit_range_.start()};
211 }
212
214 {
215 return {data_, bit_range_.one_after_last()};
216 }
217};
218
226inline bool is_bounded_span(const BitSpan span)
227{
228 const int64_t offset = span.bit_range().start();
229 const int64_t size = span.size();
230 if (offset >= BitsPerInt) {
231 /* The data pointer must point at the first int already. If the offset is a multiple of
232 * #BitsPerInt, the bit span could theoretically become bounded as well if the data pointer is
233 * adjusted. But that is not handled here. */
234 return false;
235 }
236 if (size < BitsPerInt) {
238 return offset + size <= 64;
239 }
240 if (offset != 0) {
241 /* Start of larger spans must be aligned to `BitInt` boundaries. */
242 return false;
243 }
244 return true;
245}
246
250class BoundedBitSpan : public BitSpan {
251 public:
252 BoundedBitSpan() = default;
253
254 BoundedBitSpan(const BitInt *data, const int64_t size_in_bits) : BitSpan(data, size_in_bits)
255 {
257 }
258
263
264 explicit BoundedBitSpan(const BitSpan other) : BitSpan(other)
265 {
267 }
268
270 {
271 return bit_range_.start();
272 }
273
275 {
276 return bit_range_.size() >> BitToIntIndexShift;
277 }
278
280 {
281 return bit_range_.size() & BitIndexMask;
282 }
283
285 {
286 return {data_, bit_range_.take_front(n)};
287 }
288};
289
292 protected:
293 BitInt *data_ = nullptr;
295
296 public:
297 MutableBitSpan() = default;
298
300
302
303 int64_t size() const
304 {
305 return bit_range_.size();
306 }
307
308 bool is_empty() const
309 {
310 return bit_range_.is_empty();
311 }
312
314 {
315 return IndexRange(bit_range_.size());
316 }
317
319 {
320 BLI_assert(index >= 0);
322 return {data_, bit_range_.start() + index};
323 }
324
325 MutableBitSpan slice(const IndexRange range) const
326 {
327 return {data_, bit_range_.slice(range)};
328 }
329
331 {
332 return {data_, bit_range_.take_front(n)};
333 }
334
336 {
337 return {data_, bit_range_.take_back(n)};
338 }
339
340 BitInt *data() const
341 {
342 return data_;
343 }
344
345 const IndexRange &bit_range() const
346 {
347 return bit_range_;
348 }
349
351 {
352 return {data_, bit_range_.start()};
353 }
354
356 {
357 return {data_, bit_range_.one_after_last()};
358 }
359
360 operator BitSpan() const
361 {
362 return {data_, bit_range_};
363 }
364
366 void set_all();
367
369 void reset_all();
370
371 void copy_from(const BitSpan other);
372 void copy_from(const BoundedBitSpan other);
373
375 void set_all(const bool value)
376 {
377 if (value) {
378 this->set_all();
379 }
380 else {
381 this->reset_all();
382 }
383 }
384
386 void fill(const bool value)
387 {
388 this->set_all(value);
389 }
390};
391
396 public:
398
403
408
410 {
412 }
413
414 operator BoundedBitSpan() const
415 {
416 return BoundedBitSpan{BitSpan(*this)};
417 }
418
420 {
421 return bit_range_.start();
422 }
423
425 {
426 return bit_range_.size() >> BitToIntIndexShift;
427 }
428
430 {
431 return bit_range_.size() & BitIndexMask;
432 }
433
435 {
436 return {data_, bit_range_.take_front(n)};
437 }
438
440 {
442 }
443
444 void copy_from(const BitSpan other);
445 void copy_from(const BoundedBitSpan other);
446};
447
448inline std::optional<BoundedBitSpan> try_get_bounded_span(const BitSpan span)
449{
450 if (is_bounded_span(span)) {
451 return BoundedBitSpan(span);
452 }
453 if (span.bit_range().start() % BitsPerInt == 0) {
454 return BoundedBitSpan(span.data() + (span.bit_range().start() >> BitToIntIndexShift),
455 span.size());
456 }
457 return std::nullopt;
458}
459
464template<typename T> inline T to_best_bit_span(const T &data)
465{
466 static_assert(is_same_any_v<std::decay_t<T>,
467 BitSpan,
471 return data;
472}
473
474template<typename... Args>
475constexpr bool all_bounded_spans =
477
478std::ostream &operator<<(std::ostream &stream, const BitSpan &span);
479std::ostream &operator<<(std::ostream &stream, const MutableBitSpan &span);
480
481} // namespace bits
482
483using bits::BitSpan;
487
488} // namespace blender
BitSpan()=default
constexpr int64_t one_after_last() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t size() const
constexpr bool is_empty() const
constexpr IndexRange()=default
constexpr int64_t start() const
constexpr IndexRange take_back(int64_t n) const
constexpr IndexRange slice(int64_t start, int64_t size) const
constexpr IndexRange take_front(int64_t n) const
constexpr IndexRange drop_front(int64_t n) const
BitIteratorBase & operator++()
friend bool operator!=(const BitIteratorBase &a, const BitIteratorBase &b)
BitIteratorBase(const BitInt *data, const int64_t bit_index)
BitIterator(const BitInt *data, const int64_t bit_index)
BitSpan drop_back(const int64_t n) const
BitIterator end() const
IndexRange index_range() const
const BitInt * data() const
BitRef operator[](const int64_t index) const
BitSpan take_front(const int64_t n) const
BitSpan(const BitInt *data, const IndexRange bit_range)
BitSpan take_back(const int64_t n) const
BitSpan slice(const IndexRange range) const
BitSpan(const BitInt *data, const int64_t size_in_bits)
const IndexRange & bit_range() const
BitSpan drop_front(const int64_t n) const
BitIterator begin() const
BoundedBitSpan(const BitInt *data, const IndexRange bit_range)
BoundedBitSpan(const BitSpan other)
BoundedBitSpan take_front(const int64_t n) const
BoundedBitSpan(const BitInt *data, const int64_t size_in_bits)
MutableBitIterator(BitInt *data, const int64_t bit_index)
MutableBitRef operator*() const
MutableBitSpan(BitInt *data, const int64_t size)
MutableBitSpan slice(const IndexRange range) const
MutableBitIterator end() const
const IndexRange & bit_range() const
MutableBitSpan take_front(const int64_t n) const
void set_all(const bool value)
IndexRange index_range() const
void copy_from(const BitSpan other)
Definition bit_span.cc:66
MutableBitRef operator[](const int64_t index) const
MutableBitSpan(BitInt *data, const IndexRange bit_range)
void fill(const bool value)
MutableBitIterator begin() const
MutableBitSpan take_back(const int64_t n) const
MutableBoundedBitSpan(BitInt *data, const IndexRange bit_range)
MutableBoundedBitSpan take_front(const int64_t n) const
MutableBoundedBitSpan(const MutableBitSpan other)
MutableBoundedBitSpan(BitInt *data, const int64_t size)
void copy_from(const BitSpan other)
Definition bit_span.cc:78
friend bool operator!=(const OneBitIterator &a, const OneBitIterator &b)
OneBitIterator & operator++()
#define T
uint64_t BitInt
std::optional< BoundedBitSpan > try_get_bounded_span(const BitSpan span)
constexpr bool all_bounded_spans
T to_best_bit_span(const T &data)
OneBitIteratorRange iter_1_indices(BitInt value)
std::ostream & operator<<(std::ostream &stream, const BitRef &bit)
Definition bit_ref.cc:15
bool is_bounded_span(const BitSpan span)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
constexpr bool is_same_any_v
MINLINE unsigned int bitscan_forward_clear_uint64(uint64_t *a)
BMesh const char void * data