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