1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_LIBARTBASE_BASE_BIT_MEMORY_REGION_H_
18 #define ART_LIBARTBASE_BASE_BIT_MEMORY_REGION_H_
19 
20 #include "memory_region.h"
21 
22 #include "bit_utils.h"
23 #include "memory_tool.h"
24 
25 namespace art {
26 
27 // Bit memory region is a bit offset subregion of a normal memoryregion. This is useful for
28 // abstracting away the bit start offset to avoid needing passing as an argument everywhere.
29 class BitMemoryRegion final : public ValueObject {
30  public:
31   struct Less {
operatorLess32     bool operator()(const BitMemoryRegion& lhs, const BitMemoryRegion& rhs) const {
33       return Compare(lhs, rhs) < 0;
34     }
35   };
36 
37   BitMemoryRegion() = default;
BitMemoryRegion(uint8_t * data,ssize_t bit_start,size_t bit_size)38   ALWAYS_INLINE BitMemoryRegion(uint8_t* data, ssize_t bit_start, size_t bit_size) {
39     // Normalize the data pointer. Note that bit_start may be negative.
40     uint8_t* aligned_data = AlignDown(data + (bit_start >> kBitsPerByteLog2), sizeof(uintptr_t));
41     data_ = reinterpret_cast<uintptr_t*>(aligned_data);
42     bit_start_ = bit_start + kBitsPerByte * (data - aligned_data);
43     bit_size_ = bit_size;
44     DCHECK_LT(bit_start_, static_cast<size_t>(kBitsPerIntPtrT));
45   }
BitMemoryRegion(MemoryRegion region)46   ALWAYS_INLINE explicit BitMemoryRegion(MemoryRegion region)
47     : BitMemoryRegion(region.begin(), /* bit_start */ 0, region.size_in_bits()) {
48   }
BitMemoryRegion(MemoryRegion region,size_t bit_offset,size_t bit_length)49   ALWAYS_INLINE BitMemoryRegion(MemoryRegion region, size_t bit_offset, size_t bit_length)
50     : BitMemoryRegion(region) {
51     *this = Subregion(bit_offset, bit_length);
52   }
53 
IsValid()54   ALWAYS_INLINE bool IsValid() const { return data_ != nullptr; }
55 
data()56   const uint8_t* data() const {
57     DCHECK_ALIGNED(bit_start_, kBitsPerByte);
58     return reinterpret_cast<const uint8_t*>(data_) + bit_start_ / kBitsPerByte;
59   }
60 
size_in_bits()61   size_t size_in_bits() const {
62     return bit_size_;
63   }
64 
Resize(size_t bit_size)65   void Resize(size_t bit_size) {
66     bit_size_ = bit_size;
67   }
68 
Subregion(size_t bit_offset,size_t bit_length)69   ALWAYS_INLINE BitMemoryRegion Subregion(size_t bit_offset, size_t bit_length) const {
70     DCHECK_LE(bit_offset, bit_size_);
71     DCHECK_LE(bit_length, bit_size_ - bit_offset);
72     BitMemoryRegion result = *this;
73     result.bit_start_ += bit_offset;
74     result.bit_size_ = bit_length;
75     return result;
76   }
77 
Subregion(size_t bit_offset)78   ALWAYS_INLINE BitMemoryRegion Subregion(size_t bit_offset) const {
79     DCHECK_LE(bit_offset, bit_size_);
80     BitMemoryRegion result = *this;
81     result.bit_start_ += bit_offset;
82     result.bit_size_ -= bit_offset;
83     return result;
84   }
85 
86   // Load a single bit in the region. The bit at offset 0 is the least
87   // significant bit in the first byte.
LoadBit(size_t bit_offset)88   ALWAYS_INLINE bool LoadBit(size_t bit_offset) const {
89     DCHECK_LT(bit_offset, bit_size_);
90     uint8_t* data = reinterpret_cast<uint8_t*>(data_);
91     size_t index = (bit_start_ + bit_offset) / kBitsPerByte;
92     size_t shift = (bit_start_ + bit_offset) % kBitsPerByte;
93     return ((data[index] >> shift) & 1) != 0;
94   }
95 
StoreBit(size_t bit_offset,bool value)96   ALWAYS_INLINE void StoreBit(size_t bit_offset, bool value) {
97     DCHECK_LT(bit_offset, bit_size_);
98     uint8_t* data = reinterpret_cast<uint8_t*>(data_);
99     size_t index = (bit_start_ + bit_offset) / kBitsPerByte;
100     size_t shift = (bit_start_ + bit_offset) % kBitsPerByte;
101     data[index] &= ~(1 << shift);  // Clear bit.
102     data[index] |= (value ? 1 : 0) << shift;  // Set bit.
103     DCHECK_EQ(value, LoadBit(bit_offset));
104   }
105 
106   // Load `bit_length` bits from `data` starting at given `bit_offset`.
107   // The least significant bit is stored in the smallest memory offset.
108   ATTRIBUTE_NO_SANITIZE_ADDRESS  // We might touch extra bytes due to the alignment.
LoadBits(size_t bit_offset,size_t bit_length)109   ALWAYS_INLINE uint32_t LoadBits(size_t bit_offset, size_t bit_length) const {
110     DCHECK(IsAligned<sizeof(uintptr_t)>(data_));
111     DCHECK_LE(bit_offset, bit_size_);
112     DCHECK_LE(bit_length, bit_size_ - bit_offset);
113     DCHECK_LE(bit_length, BitSizeOf<uint32_t>());
114     if (bit_length == 0) {
115       return 0;
116     }
117     uintptr_t mask = std::numeric_limits<uintptr_t>::max() >> (kBitsPerIntPtrT - bit_length);
118     size_t index = (bit_start_ + bit_offset) / kBitsPerIntPtrT;
119     size_t shift = (bit_start_ + bit_offset) % kBitsPerIntPtrT;
120     uintptr_t value = data_[index] >> shift;
121     size_t finished_bits = kBitsPerIntPtrT - shift;
122     if (finished_bits < bit_length) {
123       value |= data_[index + 1] << finished_bits;
124     }
125     return value & mask;
126   }
127 
128   // Store `bit_length` bits in `data` starting at given `bit_offset`.
129   // The least significant bit is stored in the smallest memory offset.
StoreBits(size_t bit_offset,uint32_t value,size_t bit_length)130   ALWAYS_INLINE void StoreBits(size_t bit_offset, uint32_t value, size_t bit_length) {
131     DCHECK_LE(bit_offset, bit_size_);
132     DCHECK_LE(bit_length, bit_size_ - bit_offset);
133     DCHECK_LE(bit_length, BitSizeOf<uint32_t>());
134     DCHECK_LE(value, MaxInt<uint32_t>(bit_length));
135     if (bit_length == 0) {
136       return;
137     }
138     // Write data byte by byte to avoid races with other threads
139     // on bytes that do not overlap with this region.
140     uint8_t* data = reinterpret_cast<uint8_t*>(data_);
141     uint32_t mask = std::numeric_limits<uint32_t>::max() >> (BitSizeOf<uint32_t>() - bit_length);
142     size_t index = (bit_start_ + bit_offset) / kBitsPerByte;
143     size_t shift = (bit_start_ + bit_offset) % kBitsPerByte;
144     data[index] &= ~(mask << shift);  // Clear bits.
145     data[index] |= (value << shift);  // Set bits.
146     size_t finished_bits = kBitsPerByte - shift;
147     for (int i = 1; finished_bits < bit_length; i++, finished_bits += kBitsPerByte) {
148       data[index + i] &= ~(mask >> finished_bits);  // Clear bits.
149       data[index + i] |= (value >> finished_bits);  // Set bits.
150     }
151     DCHECK_EQ(value, LoadBits(bit_offset, bit_length));
152   }
153 
154   // Store bits from other bit region.
StoreBits(size_t bit_offset,const BitMemoryRegion & src,size_t bit_length)155   ALWAYS_INLINE void StoreBits(size_t bit_offset, const BitMemoryRegion& src, size_t bit_length) {
156     DCHECK_LE(bit_offset, bit_size_);
157     DCHECK_LE(bit_length, bit_size_ - bit_offset);
158     size_t bit = 0;
159     constexpr size_t kNumBits = BitSizeOf<uint32_t>();
160     for (; bit + kNumBits <= bit_length; bit += kNumBits) {
161       StoreBits(bit_offset + bit, src.LoadBits(bit, kNumBits), kNumBits);
162     }
163     size_t num_bits = bit_length - bit;
164     StoreBits(bit_offset + bit, src.LoadBits(bit, num_bits), num_bits);
165   }
166 
167   // Count the number of set bits within the given bit range.
PopCount(size_t bit_offset,size_t bit_length)168   ALWAYS_INLINE size_t PopCount(size_t bit_offset, size_t bit_length) const {
169     DCHECK_LE(bit_offset, bit_size_);
170     DCHECK_LE(bit_length, bit_size_ - bit_offset);
171     size_t count = 0;
172     size_t bit = 0;
173     constexpr size_t kNumBits = BitSizeOf<uint32_t>();
174     for (; bit + kNumBits <= bit_length; bit += kNumBits) {
175       count += POPCOUNT(LoadBits(bit_offset + bit, kNumBits));
176     }
177     count += POPCOUNT(LoadBits(bit_offset + bit, bit_length - bit));
178     return count;
179   }
180 
Compare(const BitMemoryRegion & lhs,const BitMemoryRegion & rhs)181   static int Compare(const BitMemoryRegion& lhs, const BitMemoryRegion& rhs) {
182     if (lhs.size_in_bits() != rhs.size_in_bits()) {
183       return (lhs.size_in_bits() < rhs.size_in_bits()) ? -1 : 1;
184     }
185     size_t bit = 0;
186     constexpr size_t kNumBits = BitSizeOf<uint32_t>();
187     for (; bit + kNumBits <= lhs.size_in_bits(); bit += kNumBits) {
188       uint32_t lhs_bits = lhs.LoadBits(bit, kNumBits);
189       uint32_t rhs_bits = rhs.LoadBits(bit, kNumBits);
190       if (lhs_bits != rhs_bits) {
191         return (lhs_bits < rhs_bits) ? -1 : 1;
192       }
193     }
194     size_t num_bits = lhs.size_in_bits() - bit;
195     uint32_t lhs_bits = lhs.LoadBits(bit, num_bits);
196     uint32_t rhs_bits = rhs.LoadBits(bit, num_bits);
197     if (lhs_bits != rhs_bits) {
198       return (lhs_bits < rhs_bits) ? -1 : 1;
199     }
200     return 0;
201   }
202 
203  private:
204   // The data pointer must be naturally aligned. This makes loading code faster.
205   uintptr_t* data_ = nullptr;
206   size_t bit_start_ = 0;
207   size_t bit_size_ = 0;
208 };
209 
210 constexpr uint32_t kVarintHeaderBits = 4;
211 constexpr uint32_t kVarintSmallValue = 11;  // Maximum value which is stored as-is.
212 
213 class BitMemoryReader {
214  public:
215   BitMemoryReader(BitMemoryReader&&) = default;
BitMemoryReader(BitMemoryRegion data)216   explicit BitMemoryReader(BitMemoryRegion data)
217       : finished_region_(data.Subregion(0, 0) /* set the length to zero */ ) {
218   }
219   explicit BitMemoryReader(const uint8_t* data, ssize_t bit_offset = 0)
220       : finished_region_(const_cast<uint8_t*>(data), bit_offset, /* bit_length */ 0) {
221   }
222 
data()223   const uint8_t* data() const { return finished_region_.data(); }
224 
GetReadRegion()225   BitMemoryRegion GetReadRegion() const { return finished_region_; }
226 
NumberOfReadBits()227   size_t NumberOfReadBits() const { return finished_region_.size_in_bits(); }
228 
ReadRegion(size_t bit_length)229   ALWAYS_INLINE BitMemoryRegion ReadRegion(size_t bit_length) {
230     size_t bit_offset = finished_region_.size_in_bits();
231     finished_region_.Resize(bit_offset + bit_length);
232     return finished_region_.Subregion(bit_offset, bit_length);
233   }
234 
ReadBits(size_t bit_length)235   ALWAYS_INLINE uint32_t ReadBits(size_t bit_length) {
236     return ReadRegion(bit_length).LoadBits(/* bit_offset */ 0, bit_length);
237   }
238 
ReadBit()239   ALWAYS_INLINE bool ReadBit() {
240     return ReadRegion(/* bit_length */ 1).LoadBit(/* bit_offset */ 0);
241   }
242 
243   // Read variable-length bit-packed integer.
244   // The first four bits determine the variable length of the encoded integer:
245   //   Values 0..11 represent the result as-is, with no further following bits.
246   //   Values 12..15 mean the result is in the next 8/16/24/32-bits respectively.
ReadVarint()247   ALWAYS_INLINE uint32_t ReadVarint() {
248     uint32_t x = ReadBits(kVarintHeaderBits);
249     if (x > kVarintSmallValue) {
250       x = ReadBits((x - kVarintSmallValue) * kBitsPerByte);
251     }
252     return x;
253   }
254 
255  private:
256   // Represents all of the bits which were read so far. There is no upper bound.
257   // Therefore, by definition, the "cursor" is always at the end of the region.
258   BitMemoryRegion finished_region_;
259 
260   DISALLOW_COPY_AND_ASSIGN(BitMemoryReader);
261 };
262 
263 template<typename Vector>
264 class BitMemoryWriter {
265  public:
266   explicit BitMemoryWriter(Vector* out, size_t bit_offset = 0)
out_(out)267       : out_(out), bit_start_(bit_offset), bit_offset_(bit_offset) {
268     DCHECK_EQ(NumberOfWrittenBits(), 0u);
269   }
270 
GetWrittenRegion()271   BitMemoryRegion GetWrittenRegion() const {
272     return BitMemoryRegion(out_->data(), bit_start_, bit_offset_ - bit_start_);
273   }
274 
data()275   const uint8_t* data() const { return out_->data(); }
276 
NumberOfWrittenBits()277   size_t NumberOfWrittenBits() const { return bit_offset_ - bit_start_; }
278 
Allocate(size_t bit_length)279   ALWAYS_INLINE BitMemoryRegion Allocate(size_t bit_length) {
280     out_->resize(BitsToBytesRoundUp(bit_offset_ + bit_length));
281     BitMemoryRegion region(out_->data(), bit_offset_, bit_length);
282     DCHECK_LE(bit_length, std::numeric_limits<size_t>::max() - bit_offset_) << "Overflow";
283     bit_offset_ += bit_length;
284     return region;
285   }
286 
WriteRegion(const BitMemoryRegion & region)287   ALWAYS_INLINE void WriteRegion(const BitMemoryRegion& region) {
288     Allocate(region.size_in_bits()).StoreBits(/* bit_offset */ 0, region, region.size_in_bits());
289   }
290 
WriteBits(uint32_t value,size_t bit_length)291   ALWAYS_INLINE void WriteBits(uint32_t value, size_t bit_length) {
292     Allocate(bit_length).StoreBits(/* bit_offset */ 0, value, bit_length);
293   }
294 
WriteBit(bool value)295   ALWAYS_INLINE void WriteBit(bool value) {
296     Allocate(1).StoreBit(/* bit_offset */ 0, value);
297   }
298 
299   // Write variable-length bit-packed integer.
WriteVarint(uint32_t value)300   ALWAYS_INLINE void WriteVarint(uint32_t value) {
301     if (value <= kVarintSmallValue) {
302       WriteBits(value, kVarintHeaderBits);
303     } else {
304       uint32_t num_bits = RoundUp(MinimumBitsToStore(value), kBitsPerByte);
305       uint32_t header = kVarintSmallValue + num_bits / kBitsPerByte;
306       WriteBits(header, kVarintHeaderBits);
307       WriteBits(value, num_bits);
308     }
309   }
310 
ByteAlign()311   ALWAYS_INLINE void ByteAlign() {
312     size_t end = bit_start_ + bit_offset_;
313     bit_offset_ += RoundUp(end, kBitsPerByte) - end;
314   }
315 
316  private:
317   Vector* out_;
318   size_t bit_start_;
319   size_t bit_offset_;
320 
321   DISALLOW_COPY_AND_ASSIGN(BitMemoryWriter);
322 };
323 
324 }  // namespace art
325 
326 #endif  // ART_LIBARTBASE_BASE_BIT_MEMORY_REGION_H_
327