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
23namespace panda::ecmascript::kungfu {
24class BitSet {
25public:
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
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
42    ~BitSet()
43    {
44        if (UseWords()) {
45            // no need delete chunk memory
46            data_.words_ = nullptr;
47        }
48    }
49
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
61    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
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
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
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
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
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
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
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
161    bool ShouldExpand(size_t size)
162    {
163        if (SizeOf(size) == this->wordCount_) {
164            return false;
165        }
166        return true;
167    }
168private:
169    union Data {
170        uint64_t inlineWord_;
171        uint64_t *words_ {nullptr};
172    };
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
180    uint64_t Mask(size_t index) const
181    {
182        return uint64_t{1} << index;
183    }
184
185    size_t IndexInWord(size_t offset) const
186    {
187        return offset & BIT_PER_WORD_MASK;
188    }
189
190    size_t Index(size_t offset) const
191    {
192        return offset >> BIT_PER_WORD_LOG2;
193    }
194
195    size_t WordCount(size_t size) const
196    {
197        return size >> BYTE_PER_WORD_LOG2;
198    }
199
200    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