MimIR 0.1
MimIR is my Intermediate Representation
Loading...
Searching...
No Matches
bitset.cpp
Go to the documentation of this file.
1#include "mim/util/bitset.h"
2
3#include <bit>
4
5#include <fe/assert.h>
6
7namespace mim {
8
9namespace {
10inline uint64_t begin_mask(uint64_t i) { return -1_u64 << (i % 64_u64); }
11inline uint64_t end_mask(uint64_t i) { return ~begin_mask(i); }
12} // namespace
13
14void BitSet::dealloc() const {
15 if (num_words_ != 1) delete[] words_;
16}
17
18size_t BitSet::count() const {
19 size_t result = 0;
20 auto w = words();
21 for (size_t i = 0, e = num_words(); i != e; ++i) result += std::popcount(w[i]);
22 return result;
23}
24
25bool BitSet::operator==(const BitSet& other) const {
26 auto n = std::min(this->num_words(), other.num_words());
27 for (size_t i = 0; i != n; ++i)
28 if (this->words()[i] != other.words()[i]) return false;
29
30 const uint64_t* w;
31 size_t m;
32 if (this->num_words() > other.num_words()) {
33 w = this->words();
34 m = this->num_words();
35 } else {
36 w = other.words();
37 m = other.num_words();
38 }
39
40 for (size_t i = n; i != m; ++i)
41 if (w[i] != 0) return false;
42
43 return true;
44}
45
46bool BitSet::any_range(const size_t begin, size_t end) const {
47 if (begin >= end) return false;
48
49 end = std::min(end, num_bits());
50 size_t i = begin / 64_s;
51 size_t e = end / 64_s;
52 auto bmask = begin_mask(begin);
53 auto emask = end_mask(end);
54
55 // if i and e are within the same word
56 if (i == e) return words()[i] & bmask & emask;
57
58 // use bmask for the first word
59 bool result = (words()[i++] & bmask);
60
61 // all other words except the last one
62 for (; !result && i != e; ++i) result |= words()[i];
63
64 // only use emask if there actually *is* an emask - otherwise we are getting out of bounds
65 return result || (emask && (words_[i] & emask));
66}
67
68BitSet& BitSet::operator>>=(uint64_t shift) {
69 uint64_t div = shift / 64_u64;
70 uint64_t rem = shift % 64_u64;
71 auto w = words();
72
73 if (div >= num_words())
74 clear();
75 else {
76 for (size_t i = 0, e = num_words() - div; i != e; ++i) w[i] = w[i + div];
77 std::fill(w + num_words() - div, w + num_words(), 0);
78
79 uint64_t carry = 0;
80 for (size_t i = num_words() - div; i-- != 0;) {
81 uint64_t new_carry = w[i] << (64_u64 - rem);
82 w[i] = (w[i] >> rem) | carry;
83 carry = new_carry;
84 }
85 }
86
87 return *this;
88}
89
90void BitSet::ensure_capacity(size_t i) const {
91 size_t num_new_words = (i + 64_s) / 64_s;
92 if (num_new_words > num_words_) {
93 num_new_words = std::bit_ceil(num_new_words);
94 assert(num_new_words >= num_words_ * 2_s
95 && "num_new_words must be a power of two at least twice of num_words_");
96 uint64_t* new_words = new uint64_t[num_new_words];
97
98 // copy over and fill rest with zero
99 std::fill(std::copy_n(words(), num_words_, new_words), new_words + num_new_words, 0);
100
101 // record new num_words and words_ pointer
102 dealloc();
103 num_words_ = num_new_words;
104 words_ = new_words;
105 }
106}
107
108} // namespace mim
BitSet & operator>>=(uint64_t shift)
Definition bitset.cpp:68
bool operator==(const BitSet &) const
Definition bitset.cpp:25
void clear()
clears all bits
Definition bitset.h:73
bool any_range(const size_t begin, const size_t end) const
Definition bitset.cpp:46
size_t count() const
number of bits set
Definition bitset.cpp:18
Definition cfg.h:11
half rem(half a, half b)
Definition types.h:95