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 22 namespace panda::ecmascript::kungfu { 23 class BitSet { 24 public: 25 static constexpr uint32_t BYTE_PER_WORD = sizeof(uint64_t); 26 static constexpr uint32_t BYTE_PER_WORD_LOG2 = 3; 27 static constexpr uint32_t BIT_PER_BYTE = 8; 28 static constexpr uint32_t BIT_PER_WORD = BYTE_PER_WORD * BIT_PER_BYTE; 29 static constexpr uint32_t BIT_PER_WORD_LOG2 = 6; 30 static constexpr uint32_t BIT_PER_WORD_MASK = BIT_PER_WORD - 1; 31 BitSet(size_t bitSize)32 explicit BitSet(size_t bitSize) 33 { 34 wordCount_ = SizeOf(bitSize); 35 if (UseWords()) { 36 data_.words_ = new uint64_t[wordCount_]; 37 } 38 } 39 ~BitSet()40 ~BitSet() 41 { 42 if (UseWords()) { 43 delete[] data_.words_; 44 data_.words_ = nullptr; 45 } 46 } 47 TestBit(size_t offset)48 bool TestBit(size_t offset) const 49 { 50 if (!UseWords()) { 51 return data_.inlineWord_ & Mask(offset); 52 } else { 53 return data_.words_[Index(offset)] & Mask(IndexInWord(offset)); 54 } 55 } 56 SetBit(size_t offset)57 void SetBit(size_t offset) 58 { 59 if (!UseWords()) { 60 data_.inlineWord_ |= Mask(offset); 61 } else { 62 data_.words_[Index(offset)] |= Mask(IndexInWord(offset)); 63 } 64 } 65 ClearBit(size_t offset)66 void ClearBit(size_t offset) 67 { 68 if (!UseWords()) { 69 data_.inlineWord_ &= ~Mask(offset); 70 } else { 71 data_.words_[Index(offset)] &= ~Mask(IndexInWord(offset)); 72 } 73 } 74 Union(const BitSet & bitset)75 void Union(const BitSet &bitset) 76 { 77 if (!UseWords()) { 78 data_.inlineWord_ |= bitset.data_.inlineWord_; 79 } else { 80 for (size_t i = 0; i < wordCount_; i++) { 81 data_.words_[i] |= bitset.data_.words_[i]; 82 } 83 } 84 } 85 UnionWithChanged(const BitSet & bitset)86 bool UnionWithChanged(const BitSet &bitset) 87 { 88 if (!UseWords()) { 89 auto oldValue = data_.inlineWord_; 90 data_.inlineWord_ |= bitset.data_.inlineWord_; 91 return data_.inlineWord_ != oldValue; 92 } else { 93 bool changed = false; 94 for (size_t i = 0; i < wordCount_; i++) { 95 auto oldValue = data_.words_[i]; 96 data_.words_[i] |= bitset.data_.words_[i]; 97 if (!changed && data_.words_[i] != oldValue) { 98 changed = true; 99 } 100 } 101 return changed; 102 } 103 } 104 CopyFrom(const BitSet & other)105 void CopyFrom(const BitSet &other) 106 { 107 ASSERT(wordCount_ == other.wordCount_); 108 wordCount_ = other.wordCount_; 109 if (!UseWords()) { 110 data_.inlineWord_ = other.data_.inlineWord_; 111 return; 112 } 113 for (size_t i = 0; i < wordCount_; i++) { 114 data_.words_[i] = other.data_.words_[i]; 115 } 116 } 117 private: 118 union Data { 119 uint64_t inlineWord_; 120 uint64_t *words_ {nullptr}; 121 }; SizeOf(size_t bitSize)122 static size_t SizeOf(size_t bitSize) 123 { 124 // +1: for word 1 125 return ((bitSize - 1) >> BIT_PER_WORD_LOG2) + 1; 126 } 127 Mask(size_t index)128 uint64_t Mask(size_t index) const 129 { 130 return 1 << index; 131 } 132 IndexInWord(size_t offset)133 size_t IndexInWord(size_t offset) const 134 { 135 return offset & BIT_PER_WORD_MASK; 136 } 137 Index(size_t offset)138 size_t Index(size_t offset) const 139 { 140 return offset >> BIT_PER_WORD_LOG2; 141 } 142 WordCount(size_t size)143 size_t WordCount(size_t size) const 144 { 145 return size >> BYTE_PER_WORD_LOG2; 146 } 147 UseWords()148 bool UseWords() const { 149 return wordCount_ > 1; 150 } 151 152 uint32_t wordCount_ {0}; 153 Data data_; 154 }; 155 } // panda::ecmascript::kungfu 156 #endif // ECMASCRIPT_COMPILER_BITSET_H