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)61 bool TestBit(size_t offset) const 62 { 63 if (!UseWords()) { 64 return data_.inlineWord_ & Mask(offset); 65 } else { 66 return data_.words_[Index(offset)] & Mask(IndexInWord(offset)); 67 } 68 } 69 SetBit(size_t offset)70 void SetBit(size_t offset) 71 { 72 if (!UseWords()) { 73 data_.inlineWord_ |= Mask(offset); 74 } else { 75 data_.words_[Index(offset)] |= Mask(IndexInWord(offset)); 76 } 77 } 78 ClearBit(size_t offset)79 void ClearBit(size_t offset) 80 { 81 if (!UseWords()) { 82 data_.inlineWord_ &= ~Mask(offset); 83 } else { 84 data_.words_[Index(offset)] &= ~Mask(IndexInWord(offset)); 85 } 86 } 87 Union(const BitSet & bitset)88 void Union(const BitSet &bitset) 89 { 90 if (!UseWords()) { 91 data_.inlineWord_ |= bitset.data_.inlineWord_; 92 } else { 93 for (size_t i = 0; i < wordCount_; i++) { 94 data_.words_[i] |= bitset.data_.words_[i]; 95 } 96 } 97 } 98 UnionWithChanged(const BitSet & bitset)99 bool UnionWithChanged(const BitSet &bitset) 100 { 101 if (!UseWords()) { 102 auto oldValue = data_.inlineWord_; 103 data_.inlineWord_ |= bitset.data_.inlineWord_; 104 return data_.inlineWord_ != oldValue; 105 } else { 106 bool changed = false; 107 for (size_t i = 0; i < wordCount_; i++) { 108 auto oldValue = data_.words_[i]; 109 data_.words_[i] |= bitset.data_.words_[i]; 110 if (!changed && data_.words_[i] != oldValue) { 111 changed = true; 112 } 113 } 114 return changed; 115 } 116 } 117 CopyFrom(const BitSet & other)118 void CopyFrom(const BitSet &other) 119 { 120 ASSERT(wordCount_ == other.wordCount_); 121 wordCount_ = other.wordCount_; 122 if (!UseWords()) { 123 data_.inlineWord_ = other.data_.inlineWord_; 124 return; 125 } 126 for (size_t i = 0; i < wordCount_; i++) { 127 data_.words_[i] = other.data_.words_[i]; 128 } 129 } 130 private: 131 union Data { 132 uint64_t inlineWord_; 133 uint64_t *words_ {nullptr}; 134 }; SizeOf(size_t bitSize)135 static size_t SizeOf(size_t bitSize) 136 { 137 // +1: for word 1 138 return ((bitSize - 1) >> BIT_PER_WORD_LOG2) + 1; 139 } 140 Mask(size_t index)141 uint64_t Mask(size_t index) const 142 { 143 return uint64_t{1} << index; 144 } 145 IndexInWord(size_t offset)146 size_t IndexInWord(size_t offset) const 147 { 148 return offset & BIT_PER_WORD_MASK; 149 } 150 Index(size_t offset)151 size_t Index(size_t offset) const 152 { 153 return offset >> BIT_PER_WORD_LOG2; 154 } 155 WordCount(size_t size)156 size_t WordCount(size_t size) const 157 { 158 return size >> BYTE_PER_WORD_LOG2; 159 } 160 UseWords()161 bool UseWords() const 162 { 163 return wordCount_ > 1; 164 } 165 166 uint32_t wordCount_ {0}; 167 Data data_; 168 }; 169 } // panda::ecmascript::kungfu 170 #endif // ECMASCRIPT_COMPILER_BITSET_H