David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2018 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_TABLE_H_ |
| 18 | #define ART_LIBARTBASE_BASE_BIT_TABLE_H_ |
| 19 | |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 20 | #include <array> |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 21 | #include <initializer_list> |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 22 | #include <numeric> |
| 23 | #include <string.h> |
| 24 | #include <type_traits> |
| 25 | #include <unordered_map> |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 26 | |
| 27 | #include "base/bit_memory_region.h" |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 28 | #include "base/casts.h" |
David Srbecky | 93bd361 | 2018-07-02 19:30:18 +0100 | [diff] [blame^] | 29 | #include "base/iteration_range.h" |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 30 | #include "base/memory_region.h" |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 31 | #include "base/scoped_arena_containers.h" |
| 32 | #include "base/stl_util.h" |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 33 | |
| 34 | namespace art { |
| 35 | |
| 36 | constexpr uint32_t kVarintHeaderBits = 4; |
| 37 | constexpr uint32_t kVarintSmallValue = 11; // Maximum value which is stored as-is. |
| 38 | |
| 39 | // Load variable-length bit-packed integer from `data` starting at `bit_offset`. |
| 40 | // The first four bits determine the variable length of the encoded integer: |
| 41 | // Values 0..11 represent the result as-is, with no further following bits. |
| 42 | // Values 12..15 mean the result is in the next 8/16/24/32-bits respectively. |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 43 | ALWAYS_INLINE static inline uint32_t DecodeVarintBits(BitMemoryReader& reader) { |
| 44 | uint32_t x = reader.ReadBits(kVarintHeaderBits); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 45 | if (x > kVarintSmallValue) { |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 46 | x = reader.ReadBits((x - kVarintSmallValue) * kBitsPerByte); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 47 | } |
| 48 | return x; |
| 49 | } |
| 50 | |
| 51 | // Store variable-length bit-packed integer from `data` starting at `bit_offset`. |
| 52 | template<typename Vector> |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 53 | ALWAYS_INLINE static inline void EncodeVarintBits(BitMemoryWriter<Vector>& out, uint32_t value) { |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 54 | if (value <= kVarintSmallValue) { |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 55 | out.WriteBits(value, kVarintHeaderBits); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 56 | } else { |
| 57 | uint32_t num_bits = RoundUp(MinimumBitsToStore(value), kBitsPerByte); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 58 | uint32_t header = kVarintSmallValue + num_bits / kBitsPerByte; |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 59 | out.WriteBits(header, kVarintHeaderBits); |
| 60 | out.WriteBits(value, num_bits); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 61 | } |
| 62 | } |
| 63 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 64 | // Generic purpose table of uint32_t values, which are tightly packed at bit level. |
| 65 | // It has its own header with the number of rows and the bit-widths of all columns. |
| 66 | // The values are accessible by (row, column). The value -1 is stored efficiently. |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 67 | template<uint32_t kNumColumns> |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 68 | class BitTableBase { |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 69 | public: |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 70 | static constexpr uint32_t kNoValue = std::numeric_limits<uint32_t>::max(); // == -1. |
| 71 | static constexpr uint32_t kValueBias = kNoValue; // Bias so that -1 is encoded as 0. |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 72 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 73 | BitTableBase() {} |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 74 | explicit BitTableBase(BitMemoryReader& reader) { |
| 75 | Decode(reader); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 76 | } |
| 77 | |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 78 | ALWAYS_INLINE void Decode(BitMemoryReader& reader) { |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 79 | // Decode row count and column sizes from the table header. |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 80 | size_t initial_bit_offset = reader.GetBitOffset(); |
| 81 | num_rows_ = DecodeVarintBits(reader); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 82 | if (num_rows_ != 0) { |
| 83 | column_offset_[0] = 0; |
| 84 | for (uint32_t i = 0; i < kNumColumns; i++) { |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 85 | size_t column_end = column_offset_[i] + DecodeVarintBits(reader); |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 86 | column_offset_[i + 1] = dchecked_integral_cast<uint16_t>(column_end); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 87 | } |
| 88 | } |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 89 | header_bit_size_ = reader.GetBitOffset() - initial_bit_offset; |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 90 | |
| 91 | // Record the region which contains the table data and skip past it. |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 92 | table_data_ = reader.Skip(num_rows_ * NumRowBits()); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 93 | } |
| 94 | |
| 95 | ALWAYS_INLINE uint32_t Get(uint32_t row, uint32_t column = 0) const { |
| 96 | DCHECK_LT(row, num_rows_); |
| 97 | DCHECK_LT(column, kNumColumns); |
| 98 | size_t offset = row * NumRowBits() + column_offset_[column]; |
| 99 | return table_data_.LoadBits(offset, NumColumnBits(column)) + kValueBias; |
| 100 | } |
| 101 | |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 102 | ALWAYS_INLINE BitMemoryRegion GetBitMemoryRegion(uint32_t row, uint32_t column = 0) const { |
| 103 | DCHECK_LT(row, num_rows_); |
| 104 | DCHECK_LT(column, kNumColumns); |
| 105 | size_t offset = row * NumRowBits() + column_offset_[column]; |
| 106 | return table_data_.Subregion(offset, NumColumnBits(column)); |
| 107 | } |
| 108 | |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 109 | size_t NumRows() const { return num_rows_; } |
| 110 | |
| 111 | uint32_t NumRowBits() const { return column_offset_[kNumColumns]; } |
| 112 | |
| 113 | constexpr size_t NumColumns() const { return kNumColumns; } |
| 114 | |
| 115 | uint32_t NumColumnBits(uint32_t column) const { |
| 116 | return column_offset_[column + 1] - column_offset_[column]; |
| 117 | } |
| 118 | |
David Srbecky | 86decb6 | 2018-06-05 06:41:10 +0100 | [diff] [blame] | 119 | size_t HeaderBitSize() const { return header_bit_size_; } |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 120 | |
David Srbecky | 86decb6 | 2018-06-05 06:41:10 +0100 | [diff] [blame] | 121 | size_t BitSize() const { return header_bit_size_ + table_data_.size_in_bits(); } |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 122 | |
| 123 | protected: |
| 124 | BitMemoryRegion table_data_; |
| 125 | size_t num_rows_ = 0; |
| 126 | |
| 127 | uint16_t column_offset_[kNumColumns + 1] = {}; |
David Srbecky | 86decb6 | 2018-06-05 06:41:10 +0100 | [diff] [blame] | 128 | uint16_t header_bit_size_ = 0; |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 129 | }; |
| 130 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 131 | // Helper class which can be used to create BitTable accessors with named getters. |
| 132 | template<uint32_t NumColumns> |
| 133 | class BitTableAccessor { |
| 134 | public: |
| 135 | static constexpr uint32_t kNumColumns = NumColumns; |
| 136 | static constexpr uint32_t kNoValue = BitTableBase<kNumColumns>::kNoValue; |
| 137 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 138 | BitTableAccessor(const BitTableBase<kNumColumns>* table, uint32_t row) |
| 139 | : table_(table), row_(row) { |
David Srbecky | a45a85c | 2018-06-21 16:03:12 +0100 | [diff] [blame] | 140 | DCHECK(table_ != nullptr); |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 141 | } |
| 142 | |
| 143 | ALWAYS_INLINE uint32_t Row() const { return row_; } |
| 144 | |
David Srbecky | a45a85c | 2018-06-21 16:03:12 +0100 | [diff] [blame] | 145 | ALWAYS_INLINE bool IsValid() const { return row_ < table_->NumRows(); } |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 146 | |
| 147 | ALWAYS_INLINE bool Equals(const BitTableAccessor& other) { |
| 148 | return this->table_ == other.table_ && this->row_ == other.row_; |
| 149 | } |
| 150 | |
| 151 | // Helper macro to create constructors and per-table utilities in derived class. |
| 152 | #define BIT_TABLE_HEADER() \ |
| 153 | using BitTableAccessor<kNumColumns>::BitTableAccessor; /* inherit constructors */ \ |
| 154 | template<int COLUMN, int UNUSED /*needed to compile*/> struct ColumnName; \ |
| 155 | |
| 156 | // Helper macro to create named column accessors in derived class. |
| 157 | #define BIT_TABLE_COLUMN(COLUMN, NAME) \ |
| 158 | static constexpr uint32_t k##NAME = COLUMN; \ |
| 159 | ALWAYS_INLINE uint32_t Get##NAME() const { return table_->Get(row_, COLUMN); } \ |
| 160 | ALWAYS_INLINE bool Has##NAME() const { return Get##NAME() != kNoValue; } \ |
| 161 | template<int UNUSED> struct ColumnName<COLUMN, UNUSED> { \ |
| 162 | static constexpr const char* Value = #NAME; \ |
| 163 | }; \ |
| 164 | |
| 165 | protected: |
| 166 | const BitTableBase<kNumColumns>* table_ = nullptr; |
| 167 | uint32_t row_ = -1; |
| 168 | }; |
| 169 | |
David Srbecky | d97e082 | 2018-06-03 12:00:24 +0100 | [diff] [blame] | 170 | // Template meta-programming helper. |
| 171 | template<typename Accessor, size_t... Columns> |
David Srbecky | 86decb6 | 2018-06-05 06:41:10 +0100 | [diff] [blame] | 172 | static const char* const* GetBitTableColumnNamesImpl(std::index_sequence<Columns...>) { |
David Srbecky | d97e082 | 2018-06-03 12:00:24 +0100 | [diff] [blame] | 173 | static const char* names[] = { Accessor::template ColumnName<Columns, 0>::Value... }; |
| 174 | return names; |
| 175 | } |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 176 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 177 | // Returns the names of all columns in the given accessor. |
David Srbecky | d97e082 | 2018-06-03 12:00:24 +0100 | [diff] [blame] | 178 | template<typename Accessor> |
David Srbecky | 86decb6 | 2018-06-05 06:41:10 +0100 | [diff] [blame] | 179 | static const char* const* GetBitTableColumnNames() { |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 180 | return GetBitTableColumnNamesImpl<Accessor>(std::make_index_sequence<Accessor::kNumColumns>()); |
David Srbecky | d97e082 | 2018-06-03 12:00:24 +0100 | [diff] [blame] | 181 | } |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 182 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 183 | // Wrapper which makes it easier to use named accessors for the individual rows. |
| 184 | template<typename Accessor> |
| 185 | class BitTable : public BitTableBase<Accessor::kNumColumns> { |
| 186 | public: |
David Srbecky | 0b4e5a3 | 2018-06-11 16:25:29 +0100 | [diff] [blame] | 187 | class const_iterator : public std::iterator<std::random_access_iterator_tag, |
| 188 | /* value_type */ Accessor, |
| 189 | /* difference_type */ int32_t, |
| 190 | /* pointer */ void, |
| 191 | /* reference */ void> { |
| 192 | public: |
| 193 | using difference_type = int32_t; |
| 194 | const_iterator() {} |
| 195 | const_iterator(const BitTable* table, uint32_t row) : table_(table), row_(row) {} |
| 196 | const_iterator operator+(difference_type n) { return const_iterator(table_, row_ + n); } |
| 197 | const_iterator operator-(difference_type n) { return const_iterator(table_, row_ - n); } |
| 198 | difference_type operator-(const const_iterator& other) { return row_ - other.row_; } |
| 199 | void operator+=(difference_type rows) { row_ += rows; } |
| 200 | void operator-=(difference_type rows) { row_ -= rows; } |
| 201 | const_iterator operator++() { return const_iterator(table_, ++row_); } |
| 202 | const_iterator operator--() { return const_iterator(table_, --row_); } |
| 203 | const_iterator operator++(int) { return const_iterator(table_, row_++); } |
| 204 | const_iterator operator--(int) { return const_iterator(table_, row_--); } |
| 205 | bool operator==(const_iterator i) const { DCHECK(table_ == i.table_); return row_ == i.row_; } |
| 206 | bool operator!=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ != i.row_; } |
| 207 | bool operator<=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ <= i.row_; } |
| 208 | bool operator>=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ >= i.row_; } |
| 209 | bool operator<(const_iterator i) const { DCHECK(table_ == i.table_); return row_ < i.row_; } |
| 210 | bool operator>(const_iterator i) const { DCHECK(table_ == i.table_); return row_ > i.row_; } |
David Srbecky | 93bd361 | 2018-07-02 19:30:18 +0100 | [diff] [blame^] | 211 | Accessor operator*() { |
| 212 | DCHECK_LT(row_, table_->NumRows()); |
| 213 | return Accessor(table_, row_); |
| 214 | } |
| 215 | Accessor operator->() { |
| 216 | DCHECK_LT(row_, table_->NumRows()); |
| 217 | return Accessor(table_, row_); |
| 218 | } |
| 219 | Accessor operator[](size_t index) { |
| 220 | DCHECK_LT(row_ + index, table_->NumRows()); |
| 221 | return Accessor(table_, row_ + index); |
| 222 | } |
David Srbecky | 0b4e5a3 | 2018-06-11 16:25:29 +0100 | [diff] [blame] | 223 | private: |
| 224 | const BitTable* table_ = nullptr; |
| 225 | uint32_t row_ = 0; |
| 226 | }; |
| 227 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 228 | using BitTableBase<Accessor::kNumColumns>::BitTableBase; // Constructors. |
| 229 | |
David Srbecky | 0b4e5a3 | 2018-06-11 16:25:29 +0100 | [diff] [blame] | 230 | ALWAYS_INLINE const_iterator begin() const { return const_iterator(this, 0); } |
| 231 | ALWAYS_INLINE const_iterator end() const { return const_iterator(this, this->NumRows()); } |
| 232 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 233 | ALWAYS_INLINE Accessor GetRow(uint32_t row) const { |
| 234 | return Accessor(this, row); |
| 235 | } |
David Srbecky | a45a85c | 2018-06-21 16:03:12 +0100 | [diff] [blame] | 236 | |
| 237 | ALWAYS_INLINE Accessor GetInvalidRow() const { |
| 238 | return Accessor(this, static_cast<uint32_t>(-1)); |
| 239 | } |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 240 | }; |
| 241 | |
David Srbecky | 0b4e5a3 | 2018-06-11 16:25:29 +0100 | [diff] [blame] | 242 | template<typename Accessor> |
| 243 | typename BitTable<Accessor>::const_iterator operator+( |
| 244 | typename BitTable<Accessor>::const_iterator::difference_type n, |
| 245 | typename BitTable<Accessor>::const_iterator a) { |
| 246 | return a + n; |
| 247 | } |
| 248 | |
David Srbecky | 93bd361 | 2018-07-02 19:30:18 +0100 | [diff] [blame^] | 249 | template<typename Accessor> |
| 250 | class BitTableRange : public IterationRange<typename BitTable<Accessor>::const_iterator> { |
| 251 | public: |
| 252 | typedef typename BitTable<Accessor>::const_iterator const_iterator; |
| 253 | |
| 254 | using IterationRange<const_iterator>::IterationRange; |
| 255 | BitTableRange() : IterationRange<const_iterator>(const_iterator(), const_iterator()) { } |
| 256 | |
| 257 | bool empty() const { return this->begin() == this->end(); } |
| 258 | size_t size() const { return this->end() - this->begin(); } |
| 259 | |
| 260 | Accessor operator[](size_t index) const { |
| 261 | const_iterator it = this->begin() + index; |
| 262 | DCHECK(it < this->end()); |
| 263 | return *it; |
| 264 | } |
| 265 | |
| 266 | Accessor back() const { |
| 267 | DCHECK(!empty()); |
| 268 | return *(this->end() - 1); |
| 269 | } |
| 270 | |
| 271 | void pop_back() { |
| 272 | DCHECK(!empty()); |
| 273 | --this->last_; |
| 274 | } |
| 275 | }; |
| 276 | |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 277 | // Helper class for encoding BitTable. It can optionally de-duplicate the inputs. |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 278 | template<uint32_t kNumColumns> |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 279 | class BitTableBuilderBase { |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 280 | public: |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 281 | static constexpr uint32_t kNoValue = BitTableBase<kNumColumns>::kNoValue; |
| 282 | static constexpr uint32_t kValueBias = BitTableBase<kNumColumns>::kValueBias; |
| 283 | |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 284 | class Entry { |
| 285 | public: |
| 286 | Entry() { |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 287 | std::fill_n(data_, kNumColumns, kNoValue); |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 288 | } |
| 289 | |
| 290 | Entry(std::initializer_list<uint32_t> values) { |
| 291 | DCHECK_EQ(values.size(), kNumColumns); |
| 292 | std::copy(values.begin(), values.end(), data_); |
| 293 | } |
| 294 | |
| 295 | uint32_t& operator[](size_t column) { |
| 296 | DCHECK_LT(column, kNumColumns); |
| 297 | return data_[column]; |
| 298 | } |
| 299 | |
| 300 | uint32_t operator[](size_t column) const { |
| 301 | DCHECK_LT(column, kNumColumns); |
| 302 | return data_[column]; |
| 303 | } |
| 304 | |
| 305 | private: |
| 306 | uint32_t data_[kNumColumns]; |
| 307 | }; |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 308 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 309 | explicit BitTableBuilderBase(ScopedArenaAllocator* allocator) |
David Srbecky | 159c9dd | 2018-05-24 14:56:51 +0100 | [diff] [blame] | 310 | : rows_(allocator->Adapter(kArenaAllocBitTableBuilder)), |
| 311 | dedup_(8, allocator->Adapter(kArenaAllocBitTableBuilder)) { |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 312 | } |
| 313 | |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 314 | Entry& operator[](size_t row) { return rows_[row]; } |
| 315 | const Entry& operator[](size_t row) const { return rows_[row]; } |
David Srbecky | 0b4e5a3 | 2018-06-11 16:25:29 +0100 | [diff] [blame] | 316 | const Entry& back() const { return rows_.back(); } |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 317 | size_t size() const { return rows_.size(); } |
| 318 | |
David Srbecky | 159c9dd | 2018-05-24 14:56:51 +0100 | [diff] [blame] | 319 | // Append given value to the vector without de-duplication. |
| 320 | // This will not add the element to the dedup map to avoid its associated costs. |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 321 | void Add(Entry value) { |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 322 | rows_.push_back(value); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 323 | } |
| 324 | |
David Srbecky | 159c9dd | 2018-05-24 14:56:51 +0100 | [diff] [blame] | 325 | // Append given list of values and return the index of the first value. |
| 326 | // If the exact same set of values was already added, return the old index. |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 327 | uint32_t Dedup(Entry* values, size_t count = 1) { |
David Srbecky | 159c9dd | 2018-05-24 14:56:51 +0100 | [diff] [blame] | 328 | FNVHash<MemoryRegion> hasher; |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 329 | uint32_t hash = hasher(MemoryRegion(values, sizeof(Entry) * count)); |
David Srbecky | 159c9dd | 2018-05-24 14:56:51 +0100 | [diff] [blame] | 330 | |
| 331 | // Check if we have already added identical set of values. |
| 332 | auto range = dedup_.equal_range(hash); |
| 333 | for (auto it = range.first; it != range.second; ++it) { |
| 334 | uint32_t index = it->second; |
| 335 | if (count <= size() - index && |
| 336 | std::equal(values, |
| 337 | values + count, |
David Srbecky | 5f93710 | 2018-06-02 10:24:25 +0100 | [diff] [blame] | 338 | rows_.begin() + index, |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 339 | [](const Entry& lhs, const Entry& rhs) { |
| 340 | return memcmp(&lhs, &rhs, sizeof(Entry)) == 0; |
David Srbecky | 159c9dd | 2018-05-24 14:56:51 +0100 | [diff] [blame] | 341 | })) { |
| 342 | return index; |
| 343 | } |
| 344 | } |
| 345 | |
| 346 | // Add the set of values and add the index to the dedup map. |
| 347 | uint32_t index = size(); |
| 348 | rows_.insert(rows_.end(), values, values + count); |
| 349 | dedup_.emplace(hash, index); |
| 350 | return index; |
| 351 | } |
| 352 | |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 353 | uint32_t Dedup(Entry value) { |
| 354 | return Dedup(&value, /* count */ 1); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 355 | } |
| 356 | |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 357 | // Calculate the column bit widths based on the current data. |
| 358 | void Measure(/*out*/ std::array<uint32_t, kNumColumns>* column_bits) const { |
| 359 | uint32_t max_column_value[kNumColumns]; |
| 360 | std::fill_n(max_column_value, kNumColumns, 0); |
| 361 | for (uint32_t r = 0; r < size(); r++) { |
| 362 | for (uint32_t c = 0; c < kNumColumns; c++) { |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 363 | max_column_value[c] |= rows_[r][c] - kValueBias; |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 364 | } |
| 365 | } |
| 366 | for (uint32_t c = 0; c < kNumColumns; c++) { |
| 367 | (*column_bits)[c] = MinimumBitsToStore(max_column_value[c]); |
| 368 | } |
| 369 | } |
| 370 | |
| 371 | // Encode the stored data into a BitTable. |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 372 | template<typename Vector> |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 373 | void Encode(BitMemoryWriter<Vector>& out) const { |
| 374 | size_t initial_bit_offset = out.GetBitOffset(); |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 375 | |
| 376 | std::array<uint32_t, kNumColumns> column_bits; |
| 377 | Measure(&column_bits); |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 378 | EncodeVarintBits(out, size()); |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 379 | if (size() != 0) { |
| 380 | // Write table header. |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 381 | for (uint32_t c = 0; c < kNumColumns; c++) { |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 382 | EncodeVarintBits(out, column_bits[c]); |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 383 | } |
| 384 | |
| 385 | // Write table data. |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 386 | for (uint32_t r = 0; r < size(); r++) { |
| 387 | for (uint32_t c = 0; c < kNumColumns; c++) { |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 388 | out.WriteBits(rows_[r][c] - kValueBias, column_bits[c]); |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 389 | } |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 390 | } |
| 391 | } |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 392 | |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 393 | // Verify the written data. |
| 394 | if (kIsDebugBuild) { |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 395 | BitTableBase<kNumColumns> table; |
David Srbecky | a38e6cf | 2018-06-26 18:13:49 +0100 | [diff] [blame] | 396 | BitMemoryReader reader(out.data(), initial_bit_offset); |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 397 | table.Decode(reader); |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 398 | DCHECK_EQ(size(), table.NumRows()); |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 399 | for (uint32_t c = 0; c < kNumColumns; c++) { |
| 400 | DCHECK_EQ(column_bits[c], table.NumColumnBits(c)); |
| 401 | } |
David Srbecky | dd966bc | 2018-05-24 13:55:52 +0100 | [diff] [blame] | 402 | for (uint32_t r = 0; r < size(); r++) { |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 403 | for (uint32_t c = 0; c < kNumColumns; c++) { |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 404 | DCHECK_EQ(rows_[r][c], table.Get(r, c)) << " (" << r << ", " << c << ")"; |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 405 | } |
| 406 | } |
| 407 | } |
| 408 | } |
| 409 | |
| 410 | protected: |
David Srbecky | f325e28 | 2018-06-13 15:02:32 +0100 | [diff] [blame] | 411 | ScopedArenaDeque<Entry> rows_; |
David Srbecky | 159c9dd | 2018-05-24 14:56:51 +0100 | [diff] [blame] | 412 | ScopedArenaUnorderedMultimap<uint32_t, uint32_t> dedup_; // Hash -> row index. |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 413 | }; |
| 414 | |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 415 | template<typename Accessor> |
| 416 | class BitTableBuilder : public BitTableBuilderBase<Accessor::kNumColumns> { |
| 417 | public: |
| 418 | using BitTableBuilderBase<Accessor::kNumColumns>::BitTableBuilderBase; // Constructors. |
| 419 | }; |
| 420 | |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 421 | // Helper class for encoding single-column BitTable of bitmaps (allows more than 32 bits). |
| 422 | class BitmapTableBuilder { |
| 423 | public: |
| 424 | explicit BitmapTableBuilder(ScopedArenaAllocator* const allocator) |
| 425 | : allocator_(allocator), |
| 426 | rows_(allocator->Adapter(kArenaAllocBitTableBuilder)), |
| 427 | dedup_(8, allocator_->Adapter(kArenaAllocBitTableBuilder)) { |
| 428 | } |
| 429 | |
| 430 | MemoryRegion operator[](size_t row) { return rows_[row]; } |
| 431 | const MemoryRegion operator[](size_t row) const { return rows_[row]; } |
| 432 | size_t size() const { return rows_.size(); } |
| 433 | |
| 434 | // Add the given bitmap to the table and return its index. |
| 435 | // If the bitmap was already added it will be deduplicated. |
| 436 | // The last bit must be set and any padding bits in the last byte must be zero. |
| 437 | uint32_t Dedup(const void* bitmap, size_t num_bits) { |
| 438 | MemoryRegion region(const_cast<void*>(bitmap), BitsToBytesRoundUp(num_bits)); |
| 439 | DCHECK(num_bits == 0 || BitMemoryRegion(region).LoadBit(num_bits - 1) == 1); |
| 440 | DCHECK_EQ(BitMemoryRegion(region).LoadBits(num_bits, region.size_in_bits() - num_bits), 0u); |
| 441 | FNVHash<MemoryRegion> hasher; |
| 442 | uint32_t hash = hasher(region); |
| 443 | |
| 444 | // Check if we have already added identical bitmap. |
| 445 | auto range = dedup_.equal_range(hash); |
| 446 | for (auto it = range.first; it != range.second; ++it) { |
| 447 | if (MemoryRegion::ContentEquals()(region, rows_[it->second])) { |
| 448 | return it->second; |
| 449 | } |
| 450 | } |
| 451 | |
| 452 | // Add the bitmap and add the index to the dedup map. |
| 453 | uint32_t index = size(); |
| 454 | void* copy = allocator_->Alloc(region.size(), kArenaAllocBitTableBuilder); |
| 455 | memcpy(copy, region.pointer(), region.size()); |
| 456 | rows_.push_back(MemoryRegion(copy, region.size())); |
| 457 | dedup_.emplace(hash, index); |
| 458 | max_num_bits_ = std::max(max_num_bits_, num_bits); |
| 459 | return index; |
| 460 | } |
| 461 | |
| 462 | // Encode the stored data into a BitTable. |
| 463 | template<typename Vector> |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 464 | void Encode(BitMemoryWriter<Vector>& out) const { |
| 465 | size_t initial_bit_offset = out.GetBitOffset(); |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 466 | |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 467 | EncodeVarintBits(out, size()); |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 468 | if (size() != 0) { |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 469 | EncodeVarintBits(out, max_num_bits_); |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 470 | |
| 471 | // Write table data. |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 472 | for (MemoryRegion row : rows_) { |
| 473 | BitMemoryRegion src(row); |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 474 | BitMemoryRegion dst = out.Allocate(max_num_bits_); |
| 475 | dst.StoreBits(/* bit_offset */ 0, src, std::min(max_num_bits_, src.size_in_bits())); |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 476 | } |
| 477 | } |
| 478 | |
| 479 | // Verify the written data. |
| 480 | if (kIsDebugBuild) { |
David Srbecky | cf7833e | 2018-06-14 16:45:22 +0100 | [diff] [blame] | 481 | BitTableBase<1> table; |
David Srbecky | a38e6cf | 2018-06-26 18:13:49 +0100 | [diff] [blame] | 482 | BitMemoryReader reader(out.data(), initial_bit_offset); |
David Srbecky | 078d7ba | 2018-06-21 15:36:48 +0100 | [diff] [blame] | 483 | table.Decode(reader); |
David Srbecky | 5513c2b | 2018-05-24 15:03:20 +0100 | [diff] [blame] | 484 | DCHECK_EQ(size(), table.NumRows()); |
| 485 | DCHECK_EQ(max_num_bits_, table.NumColumnBits(0)); |
| 486 | for (uint32_t r = 0; r < size(); r++) { |
| 487 | BitMemoryRegion expected(rows_[r]); |
| 488 | BitMemoryRegion seen = table.GetBitMemoryRegion(r); |
| 489 | size_t num_bits = std::max(expected.size_in_bits(), seen.size_in_bits()); |
| 490 | for (size_t b = 0; b < num_bits; b++) { |
| 491 | bool e = b < expected.size_in_bits() && expected.LoadBit(b); |
| 492 | bool s = b < seen.size_in_bits() && seen.LoadBit(b); |
| 493 | DCHECK_EQ(e, s) << " (" << r << ")[" << b << "]"; |
| 494 | } |
| 495 | } |
| 496 | } |
| 497 | } |
| 498 | |
| 499 | private: |
| 500 | ScopedArenaAllocator* const allocator_; |
| 501 | ScopedArenaDeque<MemoryRegion> rows_; |
| 502 | ScopedArenaUnorderedMultimap<uint32_t, uint32_t> dedup_; // Hash -> row index. |
| 503 | size_t max_num_bits_ = 0u; |
| 504 | }; |
| 505 | |
David Srbecky | 052f8ca | 2018-04-26 15:42:54 +0100 | [diff] [blame] | 506 | } // namespace art |
| 507 | |
| 508 | #endif // ART_LIBARTBASE_BASE_BIT_TABLE_H_ |