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 #include "bit_table.h"
18 
19 #include <map>
20 
21 #include "gtest/gtest.h"
22 
23 #include "base/arena_allocator.h"
24 #include "base/bit_utils.h"
25 #include "base/malloc_arena_pool.h"
26 
27 namespace art {
28 
TEST(BitTableTest,TestEmptyTable)29 TEST(BitTableTest, TestEmptyTable) {
30   MallocArenaPool pool;
31   ArenaStack arena_stack(&pool);
32   ScopedArenaAllocator allocator(&arena_stack);
33 
34   std::vector<uint8_t> buffer;
35   BitMemoryWriter<std::vector<uint8_t>> writer(&buffer);
36   BitTableBuilderBase<1> builder(&allocator);
37   builder.Encode(writer);
38 
39   BitMemoryReader reader(buffer.data());
40   BitTableBase<1> table(reader);
41   EXPECT_EQ(writer.NumberOfWrittenBits(), reader.NumberOfReadBits());
42   EXPECT_EQ(0u, table.NumRows());
43 }
44 
TEST(BitTableTest,TestSingleColumnTable)45 TEST(BitTableTest, TestSingleColumnTable) {
46   MallocArenaPool pool;
47   ArenaStack arena_stack(&pool);
48   ScopedArenaAllocator allocator(&arena_stack);
49 
50   constexpr uint32_t kNoValue = -1;
51   std::vector<uint8_t> buffer;
52   BitMemoryWriter<std::vector<uint8_t>> writer(&buffer);
53   BitTableBuilderBase<1> builder(&allocator);
54   builder.Add({42u});
55   builder.Add({kNoValue});
56   builder.Add({1000u});
57   builder.Add({kNoValue});
58   builder.Encode(writer);
59 
60   BitMemoryReader reader(buffer.data());
61   BitTableBase<1> table(reader);
62   EXPECT_EQ(writer.NumberOfWrittenBits(), reader.NumberOfReadBits());
63   EXPECT_EQ(4u, table.NumRows());
64   EXPECT_EQ(42u, table.Get(0));
65   EXPECT_EQ(kNoValue, table.Get(1));
66   EXPECT_EQ(1000u, table.Get(2));
67   EXPECT_EQ(kNoValue, table.Get(3));
68   EXPECT_EQ(10u, table.NumColumnBits(0));
69 }
70 
TEST(BitTableTest,TestUnalignedTable)71 TEST(BitTableTest, TestUnalignedTable) {
72   MallocArenaPool pool;
73   ArenaStack arena_stack(&pool);
74   ScopedArenaAllocator allocator(&arena_stack);
75 
76   for (size_t start_bit_offset = 0; start_bit_offset <= 32; start_bit_offset++) {
77     std::vector<uint8_t> buffer;
78     BitMemoryWriter<std::vector<uint8_t>> writer(&buffer, start_bit_offset);
79     BitTableBuilderBase<1> builder(&allocator);
80     builder.Add({42u});
81     builder.Encode(writer);
82 
83     BitMemoryReader reader(buffer.data(), start_bit_offset);
84     BitTableBase<1> table(reader);
85     EXPECT_EQ(writer.NumberOfWrittenBits(), reader.NumberOfReadBits());
86     EXPECT_EQ(1u, table.NumRows());
87     EXPECT_EQ(42u, table.Get(0));
88   }
89 }
90 
TEST(BitTableTest,TestBigTable)91 TEST(BitTableTest, TestBigTable) {
92   MallocArenaPool pool;
93   ArenaStack arena_stack(&pool);
94   ScopedArenaAllocator allocator(&arena_stack);
95 
96   constexpr uint32_t kNoValue = -1;
97   std::vector<uint8_t> buffer;
98   BitMemoryWriter<std::vector<uint8_t>> writer(&buffer);
99   BitTableBuilderBase<4> builder(&allocator);
100   builder.Add({42u, kNoValue, 0u, static_cast<uint32_t>(-2)});
101   builder.Add({62u, kNoValue, 63u, static_cast<uint32_t>(-3)});
102   builder.Encode(writer);
103 
104   BitMemoryReader reader(buffer.data());
105   BitTableBase<4> table(reader);
106   EXPECT_EQ(writer.NumberOfWrittenBits(), reader.NumberOfReadBits());
107   EXPECT_EQ(2u, table.NumRows());
108   EXPECT_EQ(42u, table.Get(0, 0));
109   EXPECT_EQ(kNoValue, table.Get(0, 1));
110   EXPECT_EQ(0u, table.Get(0, 2));
111   EXPECT_EQ(static_cast<uint32_t>(-2), table.Get(0, 3));
112   EXPECT_EQ(62u, table.Get(1, 0));
113   EXPECT_EQ(kNoValue, table.Get(1, 1));
114   EXPECT_EQ(63u, table.Get(1, 2));
115   EXPECT_EQ(static_cast<uint32_t>(-3), table.Get(1, 3));
116   EXPECT_EQ(6u, table.NumColumnBits(0));
117   EXPECT_EQ(0u, table.NumColumnBits(1));
118   EXPECT_EQ(7u, table.NumColumnBits(2));
119   EXPECT_EQ(32u, table.NumColumnBits(3));
120 }
121 
TEST(BitTableTest,TestDedup)122 TEST(BitTableTest, TestDedup) {
123   MallocArenaPool pool;
124   ArenaStack arena_stack(&pool);
125   ScopedArenaAllocator allocator(&arena_stack);
126 
127   BitTableBuilderBase<2> builder(&allocator);
128   BitTableBuilderBase<2>::Entry value0{1, 2};
129   BitTableBuilderBase<2>::Entry value1{3, 4};
130   EXPECT_EQ(0u, builder.Dedup(&value0));
131   EXPECT_EQ(1u, builder.Dedup(&value1));
132   EXPECT_EQ(0u, builder.Dedup(&value0));
133   EXPECT_EQ(1u, builder.Dedup(&value1));
134   EXPECT_EQ(2u, builder.size());
135 }
136 
TEST(BitTableTest,TestBitmapTable)137 TEST(BitTableTest, TestBitmapTable) {
138   MallocArenaPool pool;
139   ArenaStack arena_stack(&pool);
140   ScopedArenaAllocator allocator(&arena_stack);
141 
142   std::vector<uint8_t> buffer;
143   BitMemoryWriter<std::vector<uint8_t>> writer(&buffer);
144   const uint64_t value = 0xDEADBEEF0BADF00Dull;
145   BitmapTableBuilder builder(&allocator);
146   std::multimap<uint64_t, size_t> indices;  // bitmap -> row.
147   for (size_t bit_length = 0; bit_length <= BitSizeOf<uint64_t>(); ++bit_length) {
148     uint64_t bitmap = value & MaxInt<uint64_t>(bit_length);
149     indices.emplace(bitmap, builder.Dedup(&bitmap, MinimumBitsToStore(bitmap)));
150   }
151   builder.Encode(writer);
152   EXPECT_EQ(1 + static_cast<uint32_t>(POPCOUNT(value)), builder.size());
153 
154   BitMemoryReader reader(buffer.data());
155   BitTableBase<1> table(reader);
156   EXPECT_EQ(writer.NumberOfWrittenBits(), reader.NumberOfReadBits());
157   for (auto it : indices) {
158     uint64_t expected = it.first;
159     BitMemoryRegion actual = table.GetBitMemoryRegion(it.second);
160     EXPECT_GE(actual.size_in_bits(), MinimumBitsToStore(expected));
161     for (size_t b = 0; b < actual.size_in_bits(); b++, expected >>= 1) {
162       EXPECT_EQ(expected & 1, actual.LoadBit(b)) << "b=" << b;
163     }
164   }
165 }
166 
TEST(BitTableTest,TestCollisions)167 TEST(BitTableTest, TestCollisions) {
168   MallocArenaPool pool;
169   ArenaStack arena_stack(&pool);
170   ScopedArenaAllocator allocator(&arena_stack);
171   FNVHash<MemoryRegion> hasher;
172 
173   BitTableBuilderBase<2>::Entry value0{56948505, 0};
174   BitTableBuilderBase<2>::Entry value1{67108869, 0};
175 
176   BitTableBuilderBase<2> builder(&allocator);
177   EXPECT_EQ(hasher(MemoryRegion(&value0, sizeof(value0))),
178             hasher(MemoryRegion(&value1, sizeof(value1))));
179   EXPECT_EQ(0u, builder.Dedup(&value0));
180   EXPECT_EQ(1u, builder.Dedup(&value1));
181   EXPECT_EQ(0u, builder.Dedup(&value0));
182   EXPECT_EQ(1u, builder.Dedup(&value1));
183   EXPECT_EQ(2u, builder.size());
184 
185   BitmapTableBuilder builder2(&allocator);
186   EXPECT_EQ(hasher(MemoryRegion(&value0, BitsToBytesRoundUp(MinimumBitsToStore(value0[0])))),
187             hasher(MemoryRegion(&value1, BitsToBytesRoundUp(MinimumBitsToStore(value1[0])))));
188   EXPECT_EQ(0u, builder2.Dedup(&value0[0], MinimumBitsToStore(value0[0])));
189   EXPECT_EQ(1u, builder2.Dedup(&value1[0], MinimumBitsToStore(value1[0])));
190   EXPECT_EQ(0u, builder2.Dedup(&value0[0], MinimumBitsToStore(value0[0])));
191   EXPECT_EQ(1u, builder2.Dedup(&value1[0], MinimumBitsToStore(value1[0])));
192   EXPECT_EQ(2u, builder2.size());
193 }
194 
195 }  // namespace art
196