1 /**
2 * Copyright 2024 Huawei Technologies Co., Ltd
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #ifndef MINDSPORE_PI_JIT_UTILS_BITMAP_H
17 #define MINDSPORE_PI_JIT_UTILS_BITMAP_H
18
19 #include <vector>
20 #include <numeric>
21 #include <limits>
22 #include <algorithm>
23 #include "utils/convert_utils_base.h"
24
25 namespace mindspore {
26 namespace pijit {
27
PopCount(unsigned x)28 constexpr int PopCount(unsigned x) {
29 #ifdef __GNUC__
30 return __builtin_popcount(x);
31 #else
32 int c = 0;
33 while (x) {
34 c += (x & 1);
35 x >>= 1;
36 }
37 return c;
38 #endif
39 }
40
CountTrailingZeros(size_t x)41 constexpr size_t CountTrailingZeros(size_t x) {
42 constexpr auto bits = std::numeric_limits<size_t>::digits;
43 constexpr auto limit = std::numeric_limits<unsigned>::digits;
44 if (x == 0) {
45 return bits;
46 }
47 size_t c = 0;
48 if ((x & std::numeric_limits<unsigned>::max()) == 0) {
49 c += limit;
50 x >>= limit;
51 }
52 #ifdef __GNUC__
53 return bits == limit ? __builtin_ctz(x) : c + __builtin_ctzll(x);
54 #else
55 while ((x & 1) == 0) {
56 c++;
57 x >>= 1;
58 }
59 return c;
60 #endif
61 }
62
63 class BitMap {
64 public:
65 // traverse the index of bit that is set
66 class Iter {
67 public:
68 Iter(const BitMap *map, bool begin);
69 bool operator!=(const Iter &o) const { return this->data_ != o.data_; }
70 size_t operator*() { return offset_; }
71 Iter &operator++();
72
73 private:
74 // advance to next one bit
75 void NextOne();
76
77 const size_t *end_;
78 const size_t *data_;
79 size_t offset_;
80 };
81
BitMap()82 BitMap() : size_(0), bits_() {}
BitMap(size_t size)83 explicit BitMap(size_t size) : size_(size), bits_(count(), 0) {}
size()84 size_t size() const { return size_; }
Get(size_t i)85 bool Get(size_t i) const { return data()[i >> shf] & (size_t(1) << (i & mod)); }
Set(size_t i)86 void Set(size_t i) { data()[i >> shf] |= (size_t(1) << (i & mod)); }
Clear(size_t i)87 void Clear(size_t i) { data()[i >> shf] &= ~(size_t(1) << (i & mod)); }
88
89 // logic and, a &= b
90 void And(const BitMap &o);
91
92 // logic or, a |= b
93 void Or(const BitMap &o);
94
95 // logic or, return true if any bit changed
96 bool OrWithChange(const BitMap &o);
97
98 // logic and not, a &= ~b
99 void Diff(const BitMap &o);
100
101 // count one bits
102 size_t CountBits() const;
103
104 private:
105 static constexpr const int shf = CountTrailingZeros(std::numeric_limits<size_t>::digits);
106 static constexpr const int mod = (1 << shf) - 1;
107
count()108 size_t count() const { return (size_ >> shf) + static_cast<bool>(size_ & IntToSize(mod)); }
bytes()109 size_t bytes() const { return count() * sizeof(size_t); }
data()110 size_t *data() { return bits_.data(); }
data()111 const size_t *data() const { return bits_.data(); }
112
113 size_t size_;
114 std::vector<size_t> bits_;
115 };
116
117 } // namespace pijit
118 } // namespace mindspore
119
120 #endif
121