Trailing zero bits of a non-zero value. Zero is undefined, as for the builtins; callers must check first.
A simple fixed-size Bitset implementation similar to std::Bitset.
Constructs a bitset_fixed with all bits reset.
Resets all bits to zero.
Sets or clears the bit at position pos.
Clears the bit at position pos.
Flips (toggles) the bit at position pos.
Flips all bits.
Tests whether the bit at position pos is set.
Returns the value of the bit at position pos.
Returns the number of set bits.
Queries.
Size of the bitset_fixed (number of bits).
Finds the first bit that matches the test value. Returns the index of the first matching bit, or -1 if none found.
Finds the first run of consecutive bits that match the test value. Returns the index of the first bit in the run, or -1 if no run found.
Friend operators for convenience.
A Bitset implementation with inline storage that can grow if needed. T is the storage type (u8, u16, u32, u64) N is the initial number of bits to store inline
Constructs a Bitset with all bits reset.
Resets all bits to zero.
Sets or clears the bit at position pos.
Clears the bit at position pos.
Flips (toggles) the bit at position pos.
Flips all bits.
Tests whether the bit at position pos is set.
Returns the value of the bit at position pos.
Returns the number of set bits.
Queries.
Size of the Bitset (number of bits).
Finds the first bit that matches the test value. Returns the index of the first matching bit, or -1 if none found.
21 {
22
23template <fl::u32 N> class bitset_inlined;
24
25template <fl::u32 N> class bitset_fixed;
26
27class string;
28template <fl::u32 N = 16>
29using bitset = bitset_inlined<N>;
30
31
32
33
34
35
36
37template<typename IntType>
40 const U u = static_cast<U>(value);
41 return static_cast<fl::u8>(
42 sizeof(U) <= sizeof(unsigned) ? __builtin_popcount(static_cast<unsigned>(u))
43 : sizeof(U) <= sizeof(unsigned long) ? __builtin_popcountl(static_cast<unsigned long>(u))
44 : __builtin_popcountll(static_cast<unsigned long long>(u)));
45}
46
49template<typename IntType>
52 const U u = static_cast<U>(value);
53 return static_cast<fl::u8>(
54 sizeof(U) <= sizeof(unsigned) ? __builtin_ctz(static_cast<unsigned>(u))
55 : sizeof(U) <= sizeof(unsigned long) ? __builtin_ctzl(static_cast<unsigned long>(u))
56 : __builtin_ctzll(static_cast<unsigned long long>(u)));
57}
58
60template <fl::u32 N> class bitset_fixed {
61 private:
63 static constexpr fl::u32 bits_per_block = 8 * sizeof(fl::u16);
64 static constexpr fl::u32 block_count =
65 (N + bits_per_block - 1) / bits_per_block;
66 using block_type = fl::u16;
67
68
69 block_type _blocks[block_count];
70
71 public:
72 struct Proxy {
73 bitset_fixed &_bitset;
74 fl::u32 _pos;
75
77
79 _bitset.set(_pos, value);
80 return *this;
81 }
82
83 operator bool() const
FL_NO_EXCEPT {
return _bitset.test(_pos); }
84 };
85
87
90
92 detail::to_string(_blocks, N, dst);
93 }
94
97 for (fl::u32 i = 0; i < block_count; ++i) {
98 _blocks[i] = 0;
99 }
100 }
101
105 const fl::u32 idx =
pos / bits_per_block;
106 const fl::u32 off =
pos % bits_per_block;
107 if (value) {
108 _blocks[idx] |= (block_type(1) << off);
109 } else {
110 _blocks[idx] &= ~(block_type(1) << off);
111 }
112 }
113 return *this;
114 }
115
117 if (n > N) {
118 n = N;
119 }
120 for (fl::size i = 0; i < n; ++i) {
121 set(i, value);
122 }
123 }
124
127
131 const fl::u32 idx =
pos / bits_per_block;
132 const fl::u32 off =
pos % bits_per_block;
133 _blocks[idx] ^= (block_type(1) << off);
134 }
135 return *this;
136 }
137
140 for (fl::u32 i = 0; i < block_count; ++i) {
141 _blocks[i] = ~_blocks[i];
142 }
143
144 if (N % bits_per_block != 0) {
145 const fl::u32 extra = bits_per_block - (N % bits_per_block);
146 _blocks[block_count - 1] &= (~block_type(0) >> extra);
147 }
148 return *this;
149 }
150
154 const fl::u32 idx =
pos / bits_per_block;
155 const fl::u32 off =
pos % bits_per_block;
156 return (_blocks[idx] >> off) & 1;
157 }
158 return false;
159 }
160
163
166 fl::u32 cnt = 0;
167
168 for (fl::u32 i = 0; i + 1 < block_count; ++i) {
169 cnt += fl::popcount(_blocks[i]);
170 }
171
172
173
174 if (block_count > 0) {
175 block_type last_block = _blocks[block_count - 1];
176
177
178 if (N % bits_per_block != 0) {
179 const fl::u32 valid_bits = N % bits_per_block;
180
181 block_type mask = (valid_bits == bits_per_block)
182 ? static_cast<block_type>(~block_type(0))
183 : ((block_type(1) << valid_bits) - 1);
184 last_block &= mask;
185 }
186 cnt += fl::popcount(last_block);
187 }
188
189 return cnt;
190 }
191
196 if (N == 0)
197 return true;
198
199
200 for (fl::u32 i = 0; i < block_count - 1; ++i) {
201 if (_blocks[i] != ~block_type(0)) {
202 return false;
203 }
204 }
205
206
207 if (block_count > 0) {
208 block_type mask;
209 if (N % bits_per_block != 0) {
210
211 mask = (block_type(1) << (N % bits_per_block)) - 1;
212 } else {
213 mask = static_cast<block_type>(~block_type(0));
214 }
215
216 if ((_blocks[block_count - 1] & mask) != mask) {
217 return false;
218 }
219 }
220
221 return true;
222 }
223
225 bitset_fixed &operator&=(
const bitset_fixed &other)
FL_NO_EXCEPT {
226 for (fl::u32 i = 0; i < block_count; ++i) {
227 _blocks[i] &= other._blocks[i];
228 }
229 return *this;
230 }
233 for (fl::u32 i = 0; i < block_count; ++i) {
234 _blocks[i] |= other._blocks[i];
235 }
236 return *this;
237 }
239 bitset_fixed &operator^=(
const bitset_fixed &other)
FL_NO_EXCEPT {
240 for (fl::u32 i = 0; i < block_count; ++i) {
241 _blocks[i] ^= other._blocks[i];
242 }
243 return *this;
244 }
245
247 constexpr fl::u32 size() const
FL_NO_EXCEPT {
return N; }
248
254
256 return -1;
257 }
258
259
260 fl::u32 start_block =
offset / bits_per_block;
261 fl::u32 start_bit =
offset % bits_per_block;
262
263 for (fl::u32 block_idx = start_block; block_idx < block_count; ++block_idx) {
264 block_type current_block = _blocks[block_idx];
265
266
267 if (block_idx == block_count - 1 && N % bits_per_block != 0) {
268 const fl::u32 valid_bits = N % bits_per_block;
269 block_type mask = (valid_bits == bits_per_block)
270 ? static_cast<block_type>(~block_type(0))
271 : ((block_type(1) << valid_bits) - 1);
272 current_block &= mask;
273 }
274
275
276 if (!test_value) {
277 current_block = ~current_block;
278 }
279
280
281 if (block_idx == start_block && start_bit > 0) {
282 current_block &= ~((block_type(1) << start_bit) - 1);
283 }
284
285
286 if (current_block != 0) {
287
288 fl::u32 bit_pos = fl::countr_zero(current_block);
289 fl::u32 absolute_pos = block_idx * bits_per_block + bit_pos;
290
291
292 if (absolute_pos < N) {
293 return static_cast<fl::i32>(absolute_pos);
294 }
295 }
296 }
297
298 return -1;
299 }
300
306 fl::i32 find_run(
bool test_value, fl::u32 min_length, fl::u32
offset = 0) const
FL_NO_EXCEPT {
307 fl::u32 run_start =
offset;
308 fl::u32 run_length = 0;
309
310 for (fl::u32 i =
offset; i < N && run_length < min_length; ++i) {
311 bool current_bit = test(i);
312 if (current_bit != test_value) {
313 run_length = 0;
314 if (i + 1 < N) {
315 run_start = i + 1;
316 }
317 } else {
318 ++run_length;
319 }
320 }
321
322 if (run_length >= min_length) {
323 return static_cast<fl::i32>(run_start);
324 }
325
326 return -1;
327 }
328
331 for (fl::u32 i = 0; i < block_count; ++i) {
332 if (_blocks[i] != other._blocks[i]) {
333 return false;
334 }
335 }
336 return true;
337 }
338
340 return !(*this == other);
341 }
342
345 for (fl::i32 i = static_cast<fl::i32>(block_count) - 1; i >= 0; --i) {
346 if (_blocks[i] < other._blocks[i]) {
347 return true;
348 }
349 if (_blocks[i] > other._blocks[i]) {
350 return false;
351 }
352 }
353 return false;
354 }
355
357 return *this < other || *this == other;
358 }
359
361 return other < *this;
362 }
363
365 return other <= *this;
366 }
367
369 friend bitset_fixed
operator&(bitset_fixed lhs,
371 return lhs &= rhs;
372 }
373 friend bitset_fixed
operator|(bitset_fixed lhs,
375 return lhs |= rhs;
376 }
377 friend bitset_fixed operator^(bitset_fixed lhs,
379 return lhs ^= rhs;
380 }
381 friend bitset_fixed operator~(bitset_fixed bs)
FL_NO_EXCEPT {
return bs.flip(); }
382};
383
387template <fl::u32 N = 16>
388class bitset_inlined {
389 private:
390
391 using fixed_bitset = bitset_fixed<N>;
392 variant<fixed_bitset, bitset_dynamic> _storage;
393
394 public:
395 struct Proxy {
396 bitset_inlined &_bitset;
397 fl::u32 _pos;
398
400 : _bitset(bitset), _pos(
pos) {}
401
403 _bitset.set(_pos, value);
404 return *this;
405 }
406
407 operator bool() const
FL_NO_EXCEPT {
return _bitset.test(_pos); }
408 };
409
411
413 bitset_inlined()
FL_NO_EXCEPT : _storage(fixed_bitset()) {}
414 bitset_inlined(fl::size size)
FL_NO_EXCEPT : _storage(fixed_bitset()) {
415 if (size > N) {
416 _storage = bitset_dynamic(size);
417 }
418 }
419 bitset_inlined(
const bitset_inlined &other)
FL_NO_EXCEPT : _storage(other._storage) {}
421 : _storage(
fl::move(other._storage)) {}
422 bitset_inlined &operator=(
const bitset_inlined &other)
FL_NO_EXCEPT {
423 if (this != &other) {
424 _storage = other._storage;
425 }
426 return *this;
427 }
428 bitset_inlined &operator=(bitset_inlined &&other)
FL_NO_EXCEPT {
429 if (this != &other) {
430 _storage =
fl::move(other._storage);
431 }
432 return *this;
433 }
434
437 if (_storage.template is<fixed_bitset>()) {
438 _storage.template ptr<fixed_bitset>()->reset();
439 } else {
440 _storage.template ptr<bitset_dynamic>()->reset();
441 }
442 }
443
445 resize(n);
446 if (_storage.template is<fixed_bitset>()) {
447 _storage.template ptr<fixed_bitset>()->assign(n, value);
448 } else {
449 _storage.template ptr<bitset_dynamic>()->assign(n, value);
450 }
451 }
452
453
454
457 if (new_size <= N) {
458
459 if (_storage.template is<bitset_dynamic>()) {
460
461 fixed_bitset fixed;
462 bitset_dynamic *dynamic =
463 _storage.template ptr<bitset_dynamic>();
464
465
466 for (fl::u32 i = 0; i < N && i < dynamic->size(); ++i) {
467 if (dynamic->test(i)) {
468 fixed.set(i);
469 }
470 }
471
472 _storage = fixed;
473 }
474 } else {
475
476 if (_storage.template is<fixed_bitset>()) {
477
478 bitset_dynamic dynamic(new_size);
479 fixed_bitset *fixed = _storage.template ptr<fixed_bitset>();
480
481
482 for (fl::u32 i = 0; i < N; ++i) {
483 if (fixed->test(i)) {
484 dynamic.set(i);
485 }
486 }
487
488 _storage = dynamic;
489 } else {
490
491 _storage.template ptr<bitset_dynamic>()->resize(new_size);
492 }
493 }
494 }
495
498 if (
pos >= N && _storage.template is<fixed_bitset>()) {
500 }
501
502 if (_storage.template is<fixed_bitset>()) {
504 _storage.template ptr<fixed_bitset>()->set(
pos, value);
505 }
506 } else {
507 if (
pos >= _storage.template ptr<bitset_dynamic>()->size()) {
508 _storage.template ptr<bitset_dynamic>()->resize(
pos + 1);
509 }
510 _storage.template ptr<bitset_dynamic>()->set(
pos, value);
511 }
512 return *this;
513 }
514
517
520 if (
pos >= N && _storage.template is<fixed_bitset>()) {
522 }
523
524 if (_storage.template is<fixed_bitset>()) {
526 _storage.template ptr<fixed_bitset>()->flip(
pos);
527 }
528 } else {
529 if (
pos >= _storage.template ptr<bitset_dynamic>()->size()) {
530 _storage.template ptr<bitset_dynamic>()->resize(
pos + 1);
531 }
532 _storage.template ptr<bitset_dynamic>()->flip(
pos);
533 }
534 return *this;
535 }
536
539 if (_storage.template is<fixed_bitset>()) {
540 _storage.template ptr<fixed_bitset>()->flip();
541 } else {
542 _storage.template ptr<bitset_dynamic>()->flip();
543 }
544 return *this;
545 }
546
549 fl::u32 new_size = size() + 1;
550 resize(new_size);
551 }
552
554 template<typename... Args>
556 push_back();
557 }
558
561 if (size() > 0) {
562 resize(size() - 1);
563 }
564 }
565
568 if (_storage.template is<fixed_bitset>()) {
569 return pos < N ? _storage.template ptr<fixed_bitset>()->test(
pos)
570 : false;
571 } else {
572 return _storage.template ptr<bitset_dynamic>()->test(
pos);
573 }
574 }
575
578
581 if (_storage.template is<fixed_bitset>()) {
582 return _storage.template ptr<fixed_bitset>()->count();
583 } else {
584 return _storage.template ptr<bitset_dynamic>()->count();
585 }
586 }
587
590 if (_storage.template is<fixed_bitset>()) {
591 return _storage.template ptr<fixed_bitset>()->any();
592 } else {
593 return _storage.template ptr<bitset_dynamic>()->any();
594 }
595 }
596
598 if (_storage.template is<fixed_bitset>()) {
599 return _storage.template ptr<fixed_bitset>()->none();
600 } else {
601 return _storage.template ptr<bitset_dynamic>()->none();
602 }
603 }
604
606 if (_storage.template is<fixed_bitset>()) {
607 return _storage.template ptr<fixed_bitset>()->all();
608 } else {
609 return _storage.template ptr<bitset_dynamic>()->all();
610 }
611 }
612
615 if (_storage.template is<fixed_bitset>()) {
616 return N;
617 } else {
618 return _storage.template ptr<bitset_dynamic>()->size();
619 }
620 }
621
624 if (_storage.template is<fixed_bitset>()) {
625 _storage.template ptr<fixed_bitset>()->to_string(dst);
626 } else {
627 _storage.template ptr<bitset_dynamic>()->to_string(dst);
628 }
629 }
630
636 if (_storage.template is<fixed_bitset>()) {
637 return _storage.template ptr<fixed_bitset>()->find_first(test_value,
offset);
638 } else {
639 return _storage.template ptr<bitset_dynamic>()->find_first(test_value,
offset);
640 }
641 }
642
644 friend bitset_inlined operator~(
const bitset_inlined &bs)
FL_NO_EXCEPT {
645 bitset_inlined
result = bs;
648 }
649
650 friend bitset_inlined
operator&(
const bitset_inlined &lhs,
652 bitset_inlined
result = lhs;
653
654 if (
result._storage.template is<fixed_bitset>() &&
655 rhs._storage.template is<fixed_bitset>()) {
656
657 *
result._storage.template ptr<fixed_bitset>() &=
658 *rhs._storage.template ptr<fixed_bitset>();
659 } else {
660
661 fl::u32 min_size =
662 result.size() < rhs.size() ?
result.size() : rhs.size();
663 for (fl::u32 i = 0; i < min_size; ++i) {
665 }
666
667 for (fl::u32 i = min_size; i <
result.size(); ++i) {
669 }
670 }
671
673 }
674
675 friend bitset_inlined
operator|(
const bitset_inlined &lhs,
677 bitset_inlined
result = lhs;
678
679 if (
result._storage.template is<fixed_bitset>() &&
680 rhs._storage.template is<fixed_bitset>()) {
681
682 *
result._storage.template ptr<fixed_bitset>() |=
683 *rhs._storage.template ptr<fixed_bitset>();
684 } else {
685
686 fl::u32 max_size =
687 result.size() > rhs.size() ?
result.size() : rhs.size();
688
689
690 if (
result.size() < max_size) {
692 }
693
694
695 for (fl::u32 i = 0; i < rhs.size(); ++i) {
696 if (rhs.test(i)) {
698 }
699 }
700 }
701
703 }
704
705 friend bitset_inlined operator^(const bitset_inlined &lhs,
707 bitset_inlined
result = lhs;
708
709 if (
result._storage.template is<fixed_bitset>() &&
710 rhs._storage.template is<fixed_bitset>()) {
711
712 *
result._storage.template ptr<fixed_bitset>() ^=
713 *rhs._storage.template ptr<fixed_bitset>();
714 } else {
715
716 fl::u32 max_size =
717 result.size() > rhs.size() ?
result.size() : rhs.size();
718
719
720 if (
result.size() < max_size) {
722 }
723
724
725 for (fl::u32 i = 0; i < rhs.size(); ++i) {
727 }
728 }
729
731 }
732
735 if (size() != other.size()) {
736 return false;
737 }
738 for (fl::u32 i = 0; i < size(); ++i) {
739 if (test(i) != other.test(i)) {
740 return false;
741 }
742 }
743 return true;
744 }
745
747 return !(*this == other);
748 }
749
752 fl::u32 min_size = size() < other.size() ? size() : other.size();
753 for (fl::u32 i = min_size; i > 0; --i) {
754 bool this_bit = test(i - 1);
755 bool other_bit = other.test(i - 1);
756 if (this_bit != other_bit) {
757 return !this_bit;
758 }
759 }
760
761 return size() < other.size();
762 }
763
765 return *this < other || *this == other;
766 }
767
769 return other < *this;
770 }
771
773 return other <= *this;
774 }
775};
776
777}
ClearFlags operator&(ClearFlags a, ClearFlags b) FL_NO_EXCEPT
Enable bitwise AND for ClearFlags.
ClearFlags & operator|=(ClearFlags &a, ClearFlags b) FL_NO_EXCEPT
Enable bitwise OR assignment for ClearFlags.
ClearFlags operator|(ClearFlags a, ClearFlags b) FL_NO_EXCEPT
Enable bitwise OR for ClearFlags.
fl::UISlider offset("Offset", 0.0f, 0.0f, 1.0f, 0.01f)
constexpr remove_reference< T >::type && move(T &&t) FL_NO_EXCEPT
void to_string(const fl::u16 *bit_data, fl::u32 bit_count, string *dst) FL_NO_EXCEPT
FASTLED_FORCE_INLINE bool operator==(const CRGB &lhs, const CRGB &rhs) FL_NO_EXCEPT
Check if two CRGB objects have the same color data.
FASTLED_FORCE_INLINE bool operator>(const CRGB &lhs, const CRGB &rhs) FL_NO_EXCEPT
Check if the sum of the color channels in one CRGB object is greater than another.
FASTLED_FORCE_INLINE bool operator<=(const CRGB &lhs, const CRGB &rhs) FL_NO_EXCEPT
Check if the sum of the color channels in one CRGB object is less than or equal to another.
expected< T, E > result
Alias for expected (Rust-style naming)
FASTLED_FORCE_INLINE bool operator!=(const CRGB &lhs, const CRGB &rhs) FL_NO_EXCEPT
Check if two CRGB objects do not have the same color data.
FASTLED_FORCE_INLINE bool operator>=(const CRGB &lhs, const CRGB &rhs) FL_NO_EXCEPT
Check if the sum of the color channels in one CRGB object is greater than or equal to another.
FASTLED_FORCE_INLINE bool operator<(const CRGB &lhs, const CRGB &rhs) FL_NO_EXCEPT
Check if the sum of the color channels in one CRGB object is less than another.
#define FL_STATIC_ASSERT(...)