Add BitmapTableBuilder.

This will allow the use of BitTable for masks.

Test: test-art-host-gtest-bit_table_test
Change-Id: I81bb79a5bd82d63de4449d7f1e28ef6722491cbc

3 files changed, 170 insertions, 10 deletions

diff --git a/libartbase/base/bit_memory_region.h b/libartbase/base/bit_memory_region.h
index 3f4d0ba55b..a3d3ee41d6 100644
--- a/libartbase/base/bit_memory_region.h
+++ b/libartbase/base/bit_memory_region.h
@@ -67,7 +67,7 @@ class BitMemoryRegion FINAL : public ValueObject {
     return ((data_[index] >> shift) & 1) != 0;
   }
 
-  ALWAYS_INLINE void StoreBit(uintptr_t bit_offset, bool value) const {
+  ALWAYS_INLINE void StoreBit(uintptr_t bit_offset, bool value) {
     DCHECK_LT(bit_offset, bit_size_);
     uint8_t* data = reinterpret_cast<uint8_t*>(data_);
     size_t index = (bit_start_ + bit_offset) / kBitsPerByte;
@@ -138,6 +138,19 @@ class BitMemoryRegion FINAL : public ValueObject {
     *bit_offset += bit_length;
   }
 
+  // Store bits from other bit region.
+  ALWAYS_INLINE void StoreBits(size_t bit_offset, const BitMemoryRegion& src, size_t bit_length) {
+    DCHECK_LE(bit_offset, bit_size_);
+    DCHECK_LE(bit_length, bit_size_ - bit_offset);
+    size_t bit = 0;
+    constexpr size_t kNumBits = BitSizeOf<uint32_t>();
+    for (; bit + kNumBits <= bit_length; bit += kNumBits) {
+      StoreBits(bit_offset + bit, src.LoadBits(bit, kNumBits), kNumBits);
+    }
+    size_t num_bits = bit_length - bit;
+    StoreBits(bit_offset + bit, src.LoadBits(bit, num_bits), num_bits);
+  }
+
   ALWAYS_INLINE bool Equals(const BitMemoryRegion& other) const {
     return data_ == other.data_ &&
            bit_start_ == other.bit_start_ &&
diff --git a/libartbase/base/bit_table.h b/libartbase/base/bit_table.h
index fbded2785c..8cfd044703 100644
--- a/libartbase/base/bit_table.h
+++ b/libartbase/base/bit_table.h
@@ -126,6 +126,13 @@ class BitTable {
     return table_data_.LoadBits(offset, NumColumnBits(column)) + kValueBias;
   }
 
+  ALWAYS_INLINE BitMemoryRegion GetBitMemoryRegion(uint32_t row, uint32_t column = 0) const {
+    DCHECK_LT(row, num_rows_);
+    DCHECK_LT(column, kNumColumns);
+    size_t offset = row * NumRowBits() + column_offset_[column];
+    return table_data_.Subregion(offset, NumColumnBits(column));
+  }
+
   size_t NumRows() const { return num_rows_; }
 
   uint32_t NumRowBits() const { return column_offset_[kNumColumns]; }
@@ -286,6 +293,93 @@ class BitTableBuilder {
 template<typename T>
 constexpr size_t BitTableBuilder<T>::kNumColumns;
 
+// 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(Vector* out, size_t* bit_offset) const {
+    size_t initial_bit_offset = *bit_offset;
+
+    EncodeVarintBits(out, bit_offset, size());
+    if (size() != 0) {
+      EncodeVarintBits(out, bit_offset, max_num_bits_);
+
+      // Write table data.
+      out->resize(BitsToBytesRoundUp(*bit_offset + max_num_bits_ * size()));
+      BitMemoryRegion region(MemoryRegion(out->data(), out->size()));
+      for (MemoryRegion row : rows_) {
+        BitMemoryRegion src(row);
+        region.StoreBits(*bit_offset, src, std::min(max_num_bits_, src.size_in_bits()));
+        *bit_offset += max_num_bits_;
+      }
+    }
+
+    // Verify the written data.
+    if (kIsDebugBuild) {
+      BitTable<1> table;
+      BitMemoryRegion region(MemoryRegion(out->data(), out->size()));
+      table.Decode(region, &initial_bit_offset);
+      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_
diff --git a/libartbase/base/bit_table_test.cc b/libartbase/base/bit_table_test.cc
index f579440199..8abf0da9d9 100644
--- a/libartbase/base/bit_table_test.cc
+++ b/libartbase/base/bit_table_test.cc
@@ -154,20 +154,73 @@ TEST(BitTableTest, TestDedup) {
   BitTableBuilder<RowData> builder(&allocator);
   RowData value0{1, 2};
   RowData value1{3, 4};
-  RowData value2{56948505, 0};
-  RowData value3{67108869, 0};
+  EXPECT_EQ(0u, builder.Dedup(&value0));
+  EXPECT_EQ(1u, builder.Dedup(&value1));
+  EXPECT_EQ(0u, builder.Dedup(&value0));
+  EXPECT_EQ(1u, builder.Dedup(&value1));
+  EXPECT_EQ(2u, builder.size());
+}
+
+TEST(BitTableTest, TestBitmapTable) {
+  MallocArenaPool pool;
+  ArenaStack arena_stack(&pool);
+  ScopedArenaAllocator allocator(&arena_stack);
+
+  std::vector<uint8_t> buffer;
+  size_t encode_bit_offset = 0;
+  const uint64_t value = 0xDEADBEEF0BADF00Dull;
+  BitmapTableBuilder builder(&allocator);
+  std::multimap<uint64_t, size_t> indicies;  // bitmap -> row.
+  for (size_t bit_length = 0; bit_length <= BitSizeOf<uint64_t>(); ++bit_length) {
+    uint64_t bitmap = value & MaxInt<uint64_t>(bit_length);
+    indicies.emplace(bitmap, builder.Dedup(&bitmap, MinimumBitsToStore(bitmap)));
+  }
+  builder.Encode(&buffer, &encode_bit_offset);
+  EXPECT_EQ(1 + static_cast<uint32_t>(POPCOUNT(value)), builder.size());
+
+  size_t decode_bit_offset = 0;
+  BitTable<1> table(buffer.data(), buffer.size(), &decode_bit_offset);
+  EXPECT_EQ(encode_bit_offset, decode_bit_offset);
+  for (auto it : indicies) {
+    uint64_t expected = it.first;
+    BitMemoryRegion actual = table.GetBitMemoryRegion(it.second);
+    EXPECT_GE(actual.size_in_bits(), MinimumBitsToStore(expected));
+    for (size_t b = 0; b < actual.size_in_bits(); b++, expected >>= 1) {
+      EXPECT_EQ(expected & 1, actual.LoadBit(b)) << "b=" << b;
+    }
+  }
+}
+
+TEST(BitTableTest, TestCollisions) {
+  MallocArenaPool pool;
+  ArenaStack arena_stack(&pool);
+  ScopedArenaAllocator allocator(&arena_stack);
   FNVHash<MemoryRegion> hasher;
-  EXPECT_EQ(hasher(MemoryRegion(&value2, sizeof(RowData))),
-            hasher(MemoryRegion(&value3, sizeof(RowData))));  // Test hash collision.
+
+  struct RowData {
+    uint32_t a;
+    uint32_t b;
+  };
+  RowData value0{56948505, 0};
+  RowData value1{67108869, 0};
+
+  BitTableBuilder<RowData> builder(&allocator);
+  EXPECT_EQ(hasher(MemoryRegion(&value0, sizeof(RowData))),
+            hasher(MemoryRegion(&value1, sizeof(RowData))));
   EXPECT_EQ(0u, builder.Dedup(&value0));
   EXPECT_EQ(1u, builder.Dedup(&value1));
-  EXPECT_EQ(2u, builder.Dedup(&value2));
-  EXPECT_EQ(3u, builder.Dedup(&value3));
   EXPECT_EQ(0u, builder.Dedup(&value0));
   EXPECT_EQ(1u, builder.Dedup(&value1));
-  EXPECT_EQ(2u, builder.Dedup(&value2));
-  EXPECT_EQ(3u, builder.Dedup(&value3));
-  EXPECT_EQ(4u, builder.size());
+  EXPECT_EQ(2u, builder.size());
+
+  BitmapTableBuilder builder2(&allocator);
+  EXPECT_EQ(hasher(MemoryRegion(&value0, BitsToBytesRoundUp(MinimumBitsToStore(value0.a)))),
+            hasher(MemoryRegion(&value1, BitsToBytesRoundUp(MinimumBitsToStore(value1.a)))));
+  EXPECT_EQ(0u, builder2.Dedup(&value0.a, MinimumBitsToStore(value0.a)));
+  EXPECT_EQ(1u, builder2.Dedup(&value1.a, MinimumBitsToStore(value1.a)));
+  EXPECT_EQ(0u, builder2.Dedup(&value0.a, MinimumBitsToStore(value0.a)));
+  EXPECT_EQ(1u, builder2.Dedup(&value1.a, MinimumBitsToStore(value1.a)));
+  EXPECT_EQ(2u, builder2.size());
 }
 
 }  // namespace art