• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2021 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 PANDA_LIBPANDABASE_UTILS_BIT_MEMORY_REGION_H_
17 #define PANDA_LIBPANDABASE_UTILS_BIT_MEMORY_REGION_H_
18 
19 #include "globals.h"
20 #include "mem/mem.h"
21 #include "utils/bit_utils.h"
22 #include "utils/span.h"
23 #include "utils/type_helpers.h"
24 
25 namespace panda {
26 
27 template <typename Base = uint8_t>
28 class BitMemoryRegion {
29 public:
30     using ValueType = std::conditional_t<std::is_const_v<Base>, const uint8_t, uint8_t>;
31 
32     BitMemoryRegion() = default;
BitMemoryRegion(Base * data,size_t size)33     BitMemoryRegion(Base *data, size_t size) : BitMemoryRegion(data, 0, size) {}
BitMemoryRegion(Base * data,size_t start,size_t size)34     BitMemoryRegion(Base *data, size_t start, size_t size)
35         : data_(reinterpret_cast<ValueType *>(reinterpret_cast<uintptr_t>(
36               AlignDown(reinterpret_cast<uintptr_t>(data) + (start >> BITS_PER_BYTE_LOG2), alignof(uint64_t))))),
37           start_(start + BITS_PER_BYTE * (reinterpret_cast<ValueType *>(data) - data_)),
38           size_(size)
39     {
40     }
41 
42     template <typename T, typename = typename T::value_type>
BitMemoryRegion(T & data)43     explicit BitMemoryRegion(T &data)
44         : BitMemoryRegion(reinterpret_cast<ValueType *>(data.data()), 0,
45                           data.size() * sizeof(typename T::value_type) * BITS_PER_BYTE)
46     {
47     }
48 
49     class Iterator : public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> {
50     public:
51         static constexpr uint32_t INVAILD_OFFSET = std::numeric_limits<uint32_t>::max();
52 
Iterator(const BitMemoryRegion & region,uint32_t offset)53         Iterator(const BitMemoryRegion &region, uint32_t offset) : region_(region), bit_(offset)
54         {
55             if (bit_ != region_.Size() && !region_.ReadBit(bit_)) {
56                 Next(1);
57             }
58         }
59 
60         Iterator &operator++()
61         {
62             Next(1);
63             return *this;
64         }
65 
66         bool operator==(const Iterator &rhs) const
67         {
68             return bit_ == rhs.bit_;
69         }
70 
71         bool operator!=(const Iterator &rhs) const
72         {
73             return !(*this == rhs);
74         }
75 
76         Iterator operator+(int32_t n) const
77         {
78             ASSERT(bit_ + n < region_.Size());
79             Iterator it(*this);
80             it.Next(n);
81             return it;
82         }
83 
84         Iterator operator-(int32_t n) const
85         {
86             ASSERT(helpers::ToUnsigned(n) <= bit_);
87             Iterator it(*this);
88             it.Next(-n);
89             return it;
90         }
91 
92         uint32_t operator*()
93         {
94             return bit_;
95         }
96 
Next(uint32_t val)97         void Next(uint32_t val)
98         {
99             ASSERT(val != 0);
100             int step = val > 0 ? 1 : -1;
101             for (; val != 0; val--) {
102                 for (bit_ += step; bit_ > 0 && bit_ != region_.Size() && !region_.ReadBit(bit_); bit_ += step) {
103                 }
104                 if (bit_ == 0 && !region_.ReadBit(bit_)) {
105                     bit_ = region_.Size();
106                 }
107             }
108         }
109 
110         ~Iterator() = default;
111 
112         DEFAULT_COPY_SEMANTIC(Iterator);
113         DEFAULT_NOEXCEPT_MOVE_SEMANTIC(Iterator);
114 
115     private:
116         const BitMemoryRegion &region_;
117         uint32_t bit_ {INVAILD_OFFSET};
118     };
119 
begin()120     Iterator begin() const
121     {
122         return Iterator(*this, 0);
123     }
124 
end()125     Iterator end() const
126     {
127         return Iterator(*this, Size());
128     }
129 
Read(size_t offset)130     bool Read(size_t offset)
131     {
132         ASSERT(offset < size_);
133         size_t index = (start_ + offset) / BITS_PER_BYTE;
134         size_t shift = (start_ + offset) % BITS_PER_BYTE;
135         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
136         return (data_[index] & (1U << shift)) != 0;
137     }
138 
Write(bool value,size_t offset)139     void Write(bool value, size_t offset)
140     {
141         ASSERT(offset < size_);
142         size_t index = (start_ + offset) / BITS_PER_BYTE;
143         size_t shift = (start_ + offset) % BITS_PER_BYTE;
144         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
145         data_[index] &= ~(1U << shift);
146         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
147         data_[index] |= ((value ? 1U : 0U) << shift);
148     }
149 
150     template <typename T = size_t>
151     NO_ADDRESS_SANITIZE  // Suppress asan since we can read extra bytes
152         T
Read(size_t offset,size_t length)153         Read(size_t offset, size_t length) const
154     {
155         static_assert(std::is_integral_v<T>, "T must be integral");
156         static_assert(std::is_unsigned_v<T>, "T must be unsigned");
157 
158         if (length == 0) {
159             return 0;
160         }
161 
162         ASSERT(offset + length <= size_);
163         ASSERT(offset < size_);
164 
165         const T *data = reinterpret_cast<const T *>(data_);
166         size_t width = std::numeric_limits<std::make_unsigned_t<T>>::digits;
167         size_t index = (start_ + offset) / width;
168         size_t shift = (start_ + offset) % width;
169         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
170         T value = data[index] >> shift;
171         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
172         T extra = data[index + (shift + (length - 1)) / width];
173         T clear = (std::numeric_limits<T>::max() << 1U) << (length - 1);
174         return (value | (extra << ((width - shift) & (width - 1)))) & ~clear;
175     }
176 
177     template <typename T = size_t>
ReadAll()178     NO_ADDRESS_SANITIZE T ReadAll() const
179     {
180         ASSERT(sizeof(T) * BITS_PER_BYTE >= Size());
181         return Read(0, Size());
182     }
183 
ReadBit(size_t offset)184     bool ReadBit(size_t offset) const
185     {
186         ASSERT(offset < size_);
187         offset += start_;
188         size_t index = offset / BITS_PER_BYTE;
189         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
190         return (data_[index] & (1U << (offset & (BITS_PER_BYTE - 1)))) != 0;
191     }
192 
193     template <typename T = size_t>
Pop(size_t length)194     T Pop(size_t length)
195     {
196         T res = Read(0, length);
197         start_ += length;
198         return res;
199     }
200 
201     NO_ADDRESS_SANITIZE
Write(uint32_t value,size_t offset,size_t length)202     void Write(uint32_t value, size_t offset, size_t length)
203     {
204         if (length == 0) {
205             return;
206         }
207 
208         ASSERT(offset + length <= size_);
209         ASSERT(offset < size_);
210 
211         uint32_t mask = std::numeric_limits<uint32_t>::max() >> (std::numeric_limits<uint32_t>::digits - length);
212         size_t index = (start_ + offset) / BITS_PER_BYTE;
213         size_t shift = (start_ + offset) % BITS_PER_BYTE;
214         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
215         data_[index] &= ~(mask << shift);
216         // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
217         data_[index] |= (value << shift);
218         size_t end_bits = BITS_PER_BYTE - shift;
219         for (int i = 1; end_bits < length; i++, end_bits += BITS_PER_BYTE) {
220             // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
221             data_[index + i] &= ~(mask >> end_bits);
222             // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
223             data_[index + i] |= (value >> end_bits);
224         }
225     }
226 
Subregion(size_t offset,size_t length)227     BitMemoryRegion Subregion(size_t offset, size_t length)
228     {
229         ASSERT(offset <= size_);
230         ASSERT(offset + length <= size_);
231         return BitMemoryRegion(data_, start_ + offset, length);
232     }
233 
Subregion(size_t offset,size_t length)234     BitMemoryRegion Subregion(size_t offset, size_t length) const
235     {
236         ASSERT(offset <= size_);
237         ASSERT(offset + length <= size_);
238         return BitMemoryRegion(data_, start_ + offset, length);
239     }
240 
Size()241     size_t Size() const
242     {
243         return size_;
244     }
245 
Popcount(size_t first,size_t length)246     size_t Popcount(size_t first, size_t length) const
247     {
248         ASSERT(first < Size());
249         ASSERT((first + length) <= Size());
250         size_t res = 0;
251         size_t i = 0;
252         for (; (i + BITS_PER_UINT32) < length; i += BITS_PER_UINT32) {
253             res += panda::Popcount(Read(first + i, BITS_PER_UINT32));
254         }
255         return res + panda::Popcount(Read(first + i, length - i));
256     }
257 
Popcount()258     size_t Popcount() const
259     {
260         return Popcount(0, Size());
261     }
262 
263     void Dump(std::ostream &os) const;
264 
265     virtual ~BitMemoryRegion() = default;
266 
267     DEFAULT_COPY_SEMANTIC(BitMemoryRegion);
268     DEFAULT_NOEXCEPT_MOVE_SEMANTIC(BitMemoryRegion);
269 
270 protected:
Advance(size_t val)271     void Advance(size_t val)
272     {
273         ASSERT(val <= size_);
274         start_ += val;
275         size_ -= val;
276     }
277 
278 private:
279     ValueType *data_ {nullptr};
280     size_t start_ {0};
281     size_t size_ {0};
282 };
283 
284 }  // namespace panda
285 
286 #endif  // PANDA_LIBPANDABASE_UTILS_BIT_MEMORY_REGION_H_
287