1 /*
2  * Copyright (c) 2022 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef ECMASCRIPT_COMPILER_BITSET_H
17 #define ECMASCRIPT_COMPILER_BITSET_H
18 
19 #include <cstddef>
20 #include <cstdint>
21 #include "ecmascript/mem/chunk.h"
22 
23 namespace panda::ecmascript::kungfu {
24 class BitSet {
25 public:
26     static constexpr uint32_t BYTE_PER_WORD = sizeof(uint64_t);
27     static constexpr uint32_t BYTE_PER_WORD_LOG2 = 3;
28     static constexpr uint32_t BIT_PER_BYTE = 8;
29     static constexpr uint32_t BIT_PER_WORD = BYTE_PER_WORD * BIT_PER_BYTE;
30     static constexpr uint32_t BIT_PER_WORD_LOG2 = 6;
31     static constexpr uint32_t BIT_PER_WORD_MASK = BIT_PER_WORD - 1;
32 
BitSet(Chunk* chunk, size_t bitSize)33     explicit BitSet(Chunk* chunk, size_t bitSize)
34     {
35         wordCount_ = SizeOf(bitSize);
36         if (UseWords()) {
37             data_.words_ = chunk->NewArray<uint64_t>(wordCount_);
38             Reset();
39         }
40     }
41 
~BitSet()42     ~BitSet()
43     {
44         if (UseWords()) {
45             // no need delete chunk memory
46             data_.words_ = nullptr;
47         }
48     }
49 
Reset()50     void Reset()
51     {
52         if (!UseWords()) {
53             data_.inlineWord_ = 0;
54         } else {
55             for (size_t i = 0; i < wordCount_; i++) {
56                 data_.words_[i] = 0;
57             }
58         }
59     }
60 
TestBit(size_t offset) const61     bool TestBit(size_t offset) const
62     {
63         if (!UseWords()) {
64             return data_.inlineWord_ & Mask(offset);
65         }  else {
66             ASSERT(wordCount_ > Index(offset));
67             return data_.words_[Index(offset)] & Mask(IndexInWord(offset));
68         }
69     }
70 
SetBit(size_t offset)71     void SetBit(size_t offset)
72     {
73         if (!UseWords()) {
74             data_.inlineWord_ |= Mask(offset);
75         } else {
76             ASSERT(wordCount_ > Index(offset));
77             data_.words_[Index(offset)] |= Mask(IndexInWord(offset));
78         }
79     }
80 
ClearBit(size_t offset)81     void ClearBit(size_t offset)
82     {
83         if (!UseWords()) {
84             data_.inlineWord_ &= ~Mask(offset);
85         } else {
86             ASSERT(wordCount_ > Index(offset));
87             data_.words_[Index(offset)] &= ~Mask(IndexInWord(offset));
88         }
89     }
90 
Union(const BitSet &bitset)91     void Union(const BitSet &bitset)
92     {
93         if (!UseWords()) {
94             data_.inlineWord_ |= bitset.data_.inlineWord_;
95         } else {
96             for (size_t i = 0; i < wordCount_; i++) {
97                 data_.words_[i] |= bitset.data_.words_[i];
98             }
99         }
100     }
101 
UnionWithChanged(const BitSet &bitset)102     bool UnionWithChanged(const BitSet &bitset)
103     {
104         if (!UseWords()) {
105             auto oldValue = data_.inlineWord_;
106             data_.inlineWord_ |= bitset.data_.inlineWord_;
107             return data_.inlineWord_ != oldValue;
108         } else {
109             bool changed = false;
110             for (size_t i = 0; i < wordCount_; i++) {
111                 auto oldValue = data_.words_[i];
112                 data_.words_[i] |= bitset.data_.words_[i];
113                 if (!changed && data_.words_[i] != oldValue) {
114                     changed = true;
115                 }
116             }
117             return changed;
118         }
119     }
120 
Intersect(const BitSet &bitset)121     void Intersect(const BitSet &bitset)
122     {
123         if (!UseWords()) {
124             data_.inlineWord_ &= bitset.data_.inlineWord_;
125         } else {
126             for (size_t i = 0; i < wordCount_; i++) {
127                 data_.words_[i] &= bitset.data_.words_[i];
128             }
129         }
130     }
131 
CopyFrom(const BitSet &other)132     void CopyFrom(const BitSet &other)
133     {
134         ASSERT(wordCount_ == other.wordCount_);
135         wordCount_ = other.wordCount_;
136         if (!UseWords()) {
137             data_.inlineWord_ = other.data_.inlineWord_;
138             return;
139         }
140         for (size_t i = 0; i < wordCount_; i++) {
141             data_.words_[i] = other.data_.words_[i];
142         }
143     }
144 
CopyDataFrom(const BitSet &other)145     void CopyDataFrom(const BitSet &other)
146     {
147         ASSERT(wordCount_ >= other.wordCount_);
148         if (!other.UseWords()) {
149             if (UseWords()) {
150                 data_.words_[0] = other.data_.inlineWord_;
151             } else {
152                 data_.inlineWord_ = other.data_.inlineWord_;
153             }
154             return;
155         }
156         for (size_t i = 0; i < other.wordCount_; i++) {
157             data_.words_[i] = other.data_.words_[i];
158         }
159     }
160 
ShouldExpand(size_t size)161     bool ShouldExpand(size_t size)
162     {
163         if (SizeOf(size) == this->wordCount_) {
164             return false;
165         }
166         return true;
167     }
168 private:
169     union Data {
170         uint64_t inlineWord_;
171         uint64_t *words_ {nullptr};
172     };
SizeOf(size_t bitSize)173     static size_t SizeOf(size_t bitSize)
174     {
175         ASSERT(bitSize > 0);
176         // +1: for word 1
177         return ((bitSize - 1) >> BIT_PER_WORD_LOG2) + 1;
178     }
179 
Mask(size_t index) const180     uint64_t Mask(size_t index) const
181     {
182         return uint64_t{1} << index;
183     }
184 
IndexInWord(size_t offset) const185     size_t IndexInWord(size_t offset) const
186     {
187         return offset & BIT_PER_WORD_MASK;
188     }
189 
Index(size_t offset) const190     size_t Index(size_t offset) const
191     {
192         return offset >> BIT_PER_WORD_LOG2;
193     }
194 
WordCount(size_t size) const195     size_t WordCount(size_t size) const
196     {
197         return size >> BYTE_PER_WORD_LOG2;
198     }
199 
UseWords() const200     bool UseWords() const
201     {
202         return wordCount_ > 1;
203     }
204 
205     uint32_t wordCount_ {0};
206     Data data_;
207 };
208 }  // panda::ecmascript::kungfu
209 #endif  // ECMASCRIPT_COMPILER_BITSET_H
210