blob: 227f5eb082b31b71cedfc4d1df9bde538f822899 [file] [log] [blame]
/*
* Copyright (C) 2018 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_LIBARTBASE_BASE_BIT_TABLE_H_
#define ART_LIBARTBASE_BASE_BIT_TABLE_H_
#include <array>
#include <initializer_list>
#include <numeric>
#include <string.h>
#include <type_traits>
#include <unordered_map>
#include "base/bit_memory_region.h"
#include "base/casts.h"
#include "base/iteration_range.h"
#include "base/memory_region.h"
#include "base/scoped_arena_containers.h"
#include "base/stl_util.h"
namespace art {
// Generic purpose table of uint32_t values, which are tightly packed at bit level.
// It has its own header with the number of rows and the bit-widths of all columns.
// The values are accessible by (row, column). The value -1 is stored efficiently.
template<uint32_t kNumColumns>
class BitTableBase {
public:
static constexpr uint32_t kNoValue = std::numeric_limits<uint32_t>::max(); // == -1.
static constexpr uint32_t kValueBias = kNoValue; // Bias so that -1 is encoded as 0.
BitTableBase() {}
explicit BitTableBase(BitMemoryReader& reader) {
Decode(reader);
}
ALWAYS_INLINE void Decode(BitMemoryReader& reader) {
// Decode row count and column sizes from the table header.
std::array<uint32_t, 1+kNumColumns> header = reader.ReadInterleavedVarints<1+kNumColumns>();
num_rows_ = header[0];
column_offset_[0] = 0;
for (uint32_t i = 0; i < kNumColumns; i++) {
size_t column_end = column_offset_[i] + header[i + 1];
column_offset_[i + 1] = dchecked_integral_cast<uint16_t>(column_end);
}
// Record the region which contains the table data and skip past it.
table_data_ = reader.ReadRegion(num_rows_ * NumRowBits());
}
ALWAYS_INLINE uint32_t Get(uint32_t row, uint32_t column = 0) const {
DCHECK(table_data_.IsValid()) << "Table has not been loaded";
DCHECK_LT(row, num_rows_);
DCHECK_LT(column, kNumColumns);
size_t offset = row * NumRowBits() + column_offset_[column];
return table_data_.LoadBits(offset, NumColumnBits(column)) + kValueBias;
}
ALWAYS_INLINE BitMemoryRegion GetBitMemoryRegion(uint32_t row, uint32_t column = 0) const {
DCHECK(table_data_.IsValid()) << "Table has not been loaded";
DCHECK_LT(row, num_rows_);
DCHECK_LT(column, kNumColumns);
size_t offset = row * NumRowBits() + column_offset_[column];
return table_data_.Subregion(offset, NumColumnBits(column));
}
uint32_t NumRows() const { return num_rows_; }
uint32_t NumRowBits() const { return column_offset_[kNumColumns]; }
constexpr uint32_t NumColumns() const { return kNumColumns; }
uint32_t NumColumnBits(uint32_t column) const {
return column_offset_[column + 1] - column_offset_[column];
}
size_t DataBitSize() const { return table_data_.size_in_bits(); }
bool Equals(const BitTableBase& other) const {
return num_rows_ == other.num_rows_ &&
std::equal(column_offset_, column_offset_ + kNumColumns, other.column_offset_) &&
BitMemoryRegion::Equals(table_data_, other.table_data_);
}
protected:
BitMemoryRegion table_data_;
uint32_t num_rows_ = 0;
uint16_t column_offset_[kNumColumns + 1] = {};
};
// Helper class which can be used to create BitTable accessors with named getters.
template<uint32_t NumColumns>
class BitTableAccessor {
public:
static constexpr uint32_t kNumColumns = NumColumns;
static constexpr uint32_t kNoValue = BitTableBase<kNumColumns>::kNoValue;
BitTableAccessor() = default;
BitTableAccessor(const BitTableBase<kNumColumns>* table, uint32_t row)
: table_(table), row_(row) {
DCHECK(table_ != nullptr);
}
ALWAYS_INLINE uint32_t Row() const { return row_; }
ALWAYS_INLINE bool IsValid() const { return row_ < table_->NumRows(); }
ALWAYS_INLINE bool Equals(const BitTableAccessor& other) {
return this->table_ == other.table_ && this->row_ == other.row_;
}
// Helper macro to create constructors and per-table utilities in derived class.
#define BIT_TABLE_HEADER(NAME) \
using BitTableAccessor<kNumColumns>::BitTableAccessor; /* inherit constructors */ \
template<int COLUMN, int UNUSED /*needed to compile*/> struct ColumnName; \
static constexpr const char* kTableName = #NAME; \
// Helper macro to create named column accessors in derived class.
#define BIT_TABLE_COLUMN(COLUMN, NAME) \
static constexpr uint32_t k##NAME = COLUMN; \
ALWAYS_INLINE uint32_t Get##NAME() const { return table_->Get(row_, COLUMN); } \
ALWAYS_INLINE bool Has##NAME() const { return Get##NAME() != kNoValue; } \
template<int UNUSED> struct ColumnName<COLUMN, UNUSED> { \
static constexpr const char* Value = #NAME; \
}; \
protected:
const BitTableBase<kNumColumns>* table_ = nullptr;
uint32_t row_ = -1;
};
// Template meta-programming helper.
template<typename Accessor, size_t... Columns>
static const char* const* GetBitTableColumnNamesImpl(std::index_sequence<Columns...>) {
static const char* names[] = { Accessor::template ColumnName<Columns, 0>::Value... };
return names;
}
// Wrapper which makes it easier to use named accessors for the individual rows.
template<typename Accessor>
class BitTable : public BitTableBase<Accessor::kNumColumns> {
public:
class const_iterator : public std::iterator<std::random_access_iterator_tag,
/* value_type */ Accessor,
/* difference_type */ int32_t,
/* pointer */ void,
/* reference */ void> {
public:
using difference_type = int32_t;
const_iterator() {}
const_iterator(const BitTable* table, uint32_t row) : table_(table), row_(row) {}
const_iterator operator+(difference_type n) { return const_iterator(table_, row_ + n); }
const_iterator operator-(difference_type n) { return const_iterator(table_, row_ - n); }
difference_type operator-(const const_iterator& other) { return row_ - other.row_; }
void operator+=(difference_type rows) { row_ += rows; }
void operator-=(difference_type rows) { row_ -= rows; }
const_iterator operator++() { return const_iterator(table_, ++row_); }
const_iterator operator--() { return const_iterator(table_, --row_); }
const_iterator operator++(int) { return const_iterator(table_, row_++); }
const_iterator operator--(int) { return const_iterator(table_, row_--); }
bool operator==(const_iterator i) const { DCHECK(table_ == i.table_); return row_ == i.row_; }
bool operator!=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ != i.row_; }
bool operator<=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ <= i.row_; }
bool operator>=(const_iterator i) const { DCHECK(table_ == i.table_); return row_ >= i.row_; }
bool operator<(const_iterator i) const { DCHECK(table_ == i.table_); return row_ < i.row_; }
bool operator>(const_iterator i) const { DCHECK(table_ == i.table_); return row_ > i.row_; }
Accessor operator*() {
DCHECK_LT(row_, table_->NumRows());
return Accessor(table_, row_);
}
Accessor operator->() {
DCHECK_LT(row_, table_->NumRows());
return Accessor(table_, row_);
}
Accessor operator[](size_t index) {
DCHECK_LT(row_ + index, table_->NumRows());
return Accessor(table_, row_ + index);
}
private:
const BitTable* table_ = nullptr;
uint32_t row_ = 0;
};
using BitTableBase<Accessor::kNumColumns>::BitTableBase; // Constructors.
ALWAYS_INLINE const_iterator begin() const { return const_iterator(this, 0); }
ALWAYS_INLINE const_iterator end() const { return const_iterator(this, this->NumRows()); }
ALWAYS_INLINE Accessor GetRow(uint32_t row) const {
return Accessor(this, row);
}
ALWAYS_INLINE Accessor GetInvalidRow() const {
return Accessor(this, static_cast<uint32_t>(-1));
}
const char* GetName() const {
return Accessor::kTableName;
}
const char* const* GetColumnNames() const {
return GetBitTableColumnNamesImpl<Accessor>(std::make_index_sequence<Accessor::kNumColumns>());
}
};
template<typename Accessor>
typename BitTable<Accessor>::const_iterator operator+(
typename BitTable<Accessor>::const_iterator::difference_type n,
typename BitTable<Accessor>::const_iterator a) {
return a + n;
}
template<typename Accessor>
class BitTableRange : public IterationRange<typename BitTable<Accessor>::const_iterator> {
public:
using const_iterator = typename BitTable<Accessor>::const_iterator;
using IterationRange<const_iterator>::IterationRange;
BitTableRange() : IterationRange<const_iterator>(const_iterator(), const_iterator()) { }
bool empty() const { return this->begin() == this->end(); }
size_t size() const { return this->end() - this->begin(); }
Accessor operator[](size_t index) const {
const_iterator it = this->begin() + index;
DCHECK(it < this->end());
return *it;
}
Accessor back() const {
DCHECK(!empty());
return *(this->end() - 1);
}
void pop_back() {
DCHECK(!empty());
--this->last_;
}
};
// Helper class for encoding BitTable. It can optionally de-duplicate the inputs.
template<uint32_t kNumColumns>
class BitTableBuilderBase {
public:
static constexpr uint32_t kNoValue = BitTableBase<kNumColumns>::kNoValue;
static constexpr uint32_t kValueBias = BitTableBase<kNumColumns>::kValueBias;
class Entry {
public:
Entry() {
// The definition of kNoValue here is for host and target debug builds which complain about
// missing a symbol definition for BitTableBase<N>::kNovValue when optimization is off.
static constexpr uint32_t kNoValue = BitTableBase<kNumColumns>::kNoValue;
std::fill_n(data_, kNumColumns, kNoValue);
}
Entry(std::initializer_list<uint32_t> values) {
DCHECK_EQ(values.size(), kNumColumns);
std::copy(values.begin(), values.end(), data_);
}
uint32_t& operator[](size_t column) {
DCHECK_LT(column, kNumColumns);
return data_[column];
}
uint32_t operator[](size_t column) const {
DCHECK_LT(column, kNumColumns);
return data_[column];
}
private:
uint32_t data_[kNumColumns];
};
explicit BitTableBuilderBase(ScopedArenaAllocator* allocator)
: rows_(allocator->Adapter(kArenaAllocBitTableBuilder)),
dedup_(8, allocator->Adapter(kArenaAllocBitTableBuilder)) {
}
Entry& operator[](size_t row) { return rows_[row]; }
const Entry& operator[](size_t row) const { return rows_[row]; }
const Entry& back() const { return rows_.back(); }
size_t size() const { return rows_.size(); }
// Append given value to the vector without de-duplication.
// This will not add the element to the dedup map to avoid its associated costs.
void Add(Entry value) {
rows_.push_back(value);
}
// Append given list of values and return the index of the first value.
// If the exact same set of values was already added, return the old index.
uint32_t Dedup(Entry* values, size_t count = 1) {
FNVHash<MemoryRegion> hasher;
uint32_t hash = hasher(MemoryRegion(values, sizeof(Entry) * count));
// Check if we have already added identical set of values.
auto range = dedup_.equal_range(hash);
for (auto it = range.first; it != range.second; ++it) {
uint32_t index = it->second;
if (count <= size() - index &&
std::equal(values,
values + count,
rows_.begin() + index,
[](const Entry& lhs, const Entry& rhs) {
return memcmp(&lhs, &rhs, sizeof(Entry)) == 0;
})) {
return index;
}
}
// Add the set of values and add the index to the dedup map.
uint32_t index = size();
rows_.insert(rows_.end(), values, values + count);
dedup_.emplace(hash, index);
return index;
}
uint32_t Dedup(Entry value) {
return Dedup(&value, /* count */ 1);
}
// Calculate the column bit widths based on the current data.
void Measure(/*out*/ uint32_t* column_bits) const {
uint32_t max_column_value[kNumColumns];
std::fill_n(max_column_value, kNumColumns, 0);
for (uint32_t r = 0; r < size(); r++) {
for (uint32_t c = 0; c < kNumColumns; c++) {
max_column_value[c] |= rows_[r][c] - kValueBias;
}
}
for (uint32_t c = 0; c < kNumColumns; c++) {
column_bits[c] = MinimumBitsToStore(max_column_value[c]);
}
}
// Encode the stored data into a BitTable.
template<typename Vector>
void Encode(BitMemoryWriter<Vector>& out) const {
size_t initial_bit_offset = out.NumberOfWrittenBits();
// Write table header.
std::array<uint32_t, 1 + kNumColumns> header;
header[0] = size();
uint32_t* column_bits = header.data() + 1;
Measure(column_bits);
out.WriteInterleavedVarints(header);
// Write table data.
for (uint32_t r = 0; r < size(); r++) {
for (uint32_t c = 0; c < kNumColumns; c++) {
out.WriteBits(rows_[r][c] - kValueBias, column_bits[c]);
}
}
// Verify the written data.
if (kIsDebugBuild) {
BitTableBase<kNumColumns> table;
BitMemoryReader reader(out.GetWrittenRegion().Subregion(initial_bit_offset));
table.Decode(reader);
DCHECK_EQ(size(), table.NumRows());
for (uint32_t c = 0; c < kNumColumns; c++) {
DCHECK_EQ(column_bits[c], table.NumColumnBits(c));
}
for (uint32_t r = 0; r < size(); r++) {
for (uint32_t c = 0; c < kNumColumns; c++) {
DCHECK_EQ(rows_[r][c], table.Get(r, c)) << " (" << r << ", " << c << ")";
}
}
}
}
protected:
ScopedArenaDeque<Entry> rows_;
ScopedArenaUnorderedMultimap<uint32_t, uint32_t> dedup_; // Hash -> row index.
};
template<typename Accessor>
class BitTableBuilder : public BitTableBuilderBase<Accessor::kNumColumns> {
public:
using BitTableBuilderBase<Accessor::kNumColumns>::BitTableBuilderBase; // Constructors.
};
// Helper class for encoding single-column BitTable of bitmaps (allows more than 32 bits).
class BitmapTableBuilder {
public:
explicit BitmapTableBuilder(ScopedArenaAllocator* const allocator)
: allocator_(allocator),
rows_(allocator->Adapter(kArenaAllocBitTableBuilder)),
dedup_(8, allocator_->Adapter(kArenaAllocBitTableBuilder)) {
}
MemoryRegion operator[](size_t row) { return rows_[row]; }
const MemoryRegion operator[](size_t row) const { return rows_[row]; }
size_t size() const { return rows_.size(); }
// Add the given bitmap to the table and return its index.
// If the bitmap was already added it will be deduplicated.
// The last bit must be set and any padding bits in the last byte must be zero.
uint32_t Dedup(const void* bitmap, size_t num_bits) {
MemoryRegion region(const_cast<void*>(bitmap), BitsToBytesRoundUp(num_bits));
DCHECK(num_bits == 0 || BitMemoryRegion(region).LoadBit(num_bits - 1) == 1);
DCHECK_EQ(BitMemoryRegion(region).LoadBits(num_bits, region.size_in_bits() - num_bits), 0u);
FNVHash<MemoryRegion> hasher;
uint32_t hash = hasher(region);
// Check if we have already added identical bitmap.
auto range = dedup_.equal_range(hash);
for (auto it = range.first; it != range.second; ++it) {
if (MemoryRegion::ContentEquals()(region, rows_[it->second])) {
return it->second;
}
}
// Add the bitmap and add the index to the dedup map.
uint32_t index = size();
void* copy = allocator_->Alloc(region.size(), kArenaAllocBitTableBuilder);
memcpy(copy, region.pointer(), region.size());
rows_.push_back(MemoryRegion(copy, region.size()));
dedup_.emplace(hash, index);
max_num_bits_ = std::max(max_num_bits_, num_bits);
return index;
}
// Encode the stored data into a BitTable.
template<typename Vector>
void Encode(BitMemoryWriter<Vector>& out) const {
size_t initial_bit_offset = out.NumberOfWrittenBits();
// Write table header.
out.WriteInterleavedVarints(std::array<uint32_t, 2>{
dchecked_integral_cast<uint32_t>(size()),
dchecked_integral_cast<uint32_t>(max_num_bits_),
});
// Write table data.
for (MemoryRegion row : rows_) {
size_t bits_to_copy = std::min(max_num_bits_, row.size_in_bits());
BitMemoryRegion src(row, /*bit_offset=*/ 0u, bits_to_copy);
BitMemoryRegion dst = out.Allocate(max_num_bits_);
dst.Subregion(/*bit_offset=*/ 0, bits_to_copy).CopyBits(src);
}
// Verify the written data.
if (kIsDebugBuild) {
BitTableBase<1> table;
BitMemoryReader reader(out.GetWrittenRegion().Subregion(initial_bit_offset));
table.Decode(reader);
DCHECK_EQ(size(), table.NumRows());
DCHECK_EQ(max_num_bits_, table.NumColumnBits(0));
for (uint32_t r = 0; r < size(); r++) {
BitMemoryRegion expected(rows_[r]);
BitMemoryRegion seen = table.GetBitMemoryRegion(r);
size_t num_bits = std::max(expected.size_in_bits(), seen.size_in_bits());
for (size_t b = 0; b < num_bits; b++) {
bool e = b < expected.size_in_bits() && expected.LoadBit(b);
bool s = b < seen.size_in_bits() && seen.LoadBit(b);
DCHECK_EQ(e, s) << " (" << r << ")[" << b << "]";
}
}
}
}
private:
ScopedArenaAllocator* const allocator_;
ScopedArenaDeque<MemoryRegion> rows_;
ScopedArenaUnorderedMultimap<uint32_t, uint32_t> dedup_; // Hash -> row index.
size_t max_num_bits_ = 0u;
};
} // namespace art
#endif // ART_LIBARTBASE_BASE_BIT_TABLE_H_