1 /*
2 * Copyright (C) 2011 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_vector.h"
18
19 #include <limits>
20 #include <sstream>
21
22 #include "allocator.h"
23 #include "bit_vector-inl.h"
24
25 namespace art {
26
BitVector(bool expandable,Allocator * allocator,uint32_t storage_size,uint32_t * storage)27 BitVector::BitVector(bool expandable,
28 Allocator* allocator,
29 uint32_t storage_size,
30 uint32_t* storage)
31 : storage_(storage),
32 storage_size_(storage_size),
33 allocator_(allocator),
34 expandable_(expandable) {
35 DCHECK(storage_ != nullptr);
36
37 static_assert(sizeof(*storage_) == kWordBytes, "word bytes");
38 static_assert(sizeof(*storage_) * 8u == kWordBits, "word bits");
39 }
40
BitVector(uint32_t start_bits,bool expandable,Allocator * allocator)41 BitVector::BitVector(uint32_t start_bits,
42 bool expandable,
43 Allocator* allocator)
44 : BitVector(expandable,
45 allocator,
46 BitsToWords(start_bits),
47 static_cast<uint32_t*>(allocator->Alloc(BitsToWords(start_bits) * kWordBytes))) {
48 // We don't know if the allocator cleared things.
49 ClearAllBits();
50 }
51
BitVector(const BitVector & src,bool expandable,Allocator * allocator)52 BitVector::BitVector(const BitVector& src,
53 bool expandable,
54 Allocator* allocator)
55 : BitVector(expandable,
56 allocator,
57 src.storage_size_,
58 static_cast<uint32_t*>(allocator->Alloc(src.storage_size_ * kWordBytes))) {
59 // Direct memcpy would be faster, but this should be fine too and is cleaner.
60 Copy(&src);
61 }
62
~BitVector()63 BitVector::~BitVector() {
64 if (storage_ != nullptr) {
65 // Only free if we haven't been moved out of.
66 allocator_->Free(storage_);
67 }
68 }
69
SameBitsSet(const BitVector * src) const70 bool BitVector::SameBitsSet(const BitVector *src) const {
71 int our_highest = GetHighestBitSet();
72 int src_highest = src->GetHighestBitSet();
73
74 // If the highest bit set is different, we are different.
75 if (our_highest != src_highest) {
76 return false;
77 }
78
79 // If the highest bit set is -1, both are cleared, we are the same.
80 // If the highest bit set is 0, both have a unique bit set, we are the same.
81 if (our_highest <= 0) {
82 return true;
83 }
84
85 // Get the highest bit set's cell's index
86 // No need of highest + 1 here because it can't be 0 so BitsToWords will work here.
87 int our_highest_index = BitsToWords(our_highest);
88
89 // This memcmp is enough: we know that the highest bit set is the same for both:
90 // - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less.
91 // ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index,
92 // they are automatically at 0.
93 return (memcmp(storage_, src->GetRawStorage(), our_highest_index * kWordBytes) == 0);
94 }
95
IsSubsetOf(const BitVector * other) const96 bool BitVector::IsSubsetOf(const BitVector *other) const {
97 int this_highest = GetHighestBitSet();
98 int other_highest = other->GetHighestBitSet();
99
100 // If the highest bit set is -1, this is empty and a trivial subset.
101 if (this_highest < 0) {
102 return true;
103 }
104
105 // If the highest bit set is higher, this cannot be a subset.
106 if (this_highest > other_highest) {
107 return false;
108 }
109
110 // Compare each 32-bit word.
111 size_t this_highest_index = BitsToWords(this_highest + 1);
112 for (size_t i = 0; i < this_highest_index; ++i) {
113 uint32_t this_storage = storage_[i];
114 uint32_t other_storage = other->storage_[i];
115 if ((this_storage | other_storage) != other_storage) {
116 return false;
117 }
118 }
119 return true;
120 }
121
Intersect(const BitVector * src)122 void BitVector::Intersect(const BitVector* src) {
123 uint32_t src_storage_size = src->storage_size_;
124
125 // Get the minimum size between us and source.
126 uint32_t min_size = (storage_size_ < src_storage_size) ? storage_size_ : src_storage_size;
127
128 uint32_t idx;
129 for (idx = 0; idx < min_size; idx++) {
130 storage_[idx] &= src->GetRawStorageWord(idx);
131 }
132
133 // Now, due to this being an intersection, there are two possibilities:
134 // - Either src was larger than us: we don't care, all upper bits would thus be 0.
135 // - Either we are larger than src: we don't care, all upper bits would have been 0 too.
136 // So all we need to do is set all remaining bits to 0.
137 for (; idx < storage_size_; idx++) {
138 storage_[idx] = 0;
139 }
140 }
141
Union(const BitVector * src)142 bool BitVector::Union(const BitVector* src) {
143 // Get the highest bit to determine how much we need to expand.
144 int highest_bit = src->GetHighestBitSet();
145 bool changed = false;
146
147 // If src has no bit set, we are done: there is no need for a union with src.
148 if (highest_bit == -1) {
149 return changed;
150 }
151
152 // Update src_size to how many cells we actually care about: where the bit is + 1.
153 uint32_t src_size = BitsToWords(highest_bit + 1);
154
155 // Is the storage size smaller than src's?
156 if (storage_size_ < src_size) {
157 changed = true;
158
159 EnsureSize(highest_bit);
160
161 // Check: storage size should be big enough to hold this bit now.
162 DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
163 }
164
165 for (uint32_t idx = 0; idx < src_size; idx++) {
166 uint32_t existing = storage_[idx];
167 uint32_t update = existing | src->GetRawStorageWord(idx);
168 if (existing != update) {
169 changed = true;
170 storage_[idx] = update;
171 }
172 }
173 return changed;
174 }
175
UnionIfNotIn(const BitVector * union_with,const BitVector * not_in)176 bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) {
177 // Get the highest bit to determine how much we need to expand.
178 int highest_bit = union_with->GetHighestBitSet();
179 bool changed = false;
180
181 // If src has no bit set, we are done: there is no need for a union with src.
182 if (highest_bit == -1) {
183 return changed;
184 }
185
186 // Update union_with_size to how many cells we actually care about: where the bit is + 1.
187 uint32_t union_with_size = BitsToWords(highest_bit + 1);
188
189 // Is the storage size smaller than src's?
190 if (storage_size_ < union_with_size) {
191 EnsureSize(highest_bit);
192
193 // Check: storage size should be big enough to hold this bit now.
194 DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
195 }
196
197 uint32_t not_in_size = not_in->GetStorageSize();
198
199 uint32_t idx = 0;
200 for (; idx < std::min(not_in_size, union_with_size); idx++) {
201 uint32_t existing = storage_[idx];
202 uint32_t update = existing |
203 (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx));
204 if (existing != update) {
205 changed = true;
206 storage_[idx] = update;
207 }
208 }
209
210 for (; idx < union_with_size; idx++) {
211 uint32_t existing = storage_[idx];
212 uint32_t update = existing | union_with->GetRawStorageWord(idx);
213 if (existing != update) {
214 changed = true;
215 storage_[idx] = update;
216 }
217 }
218 return changed;
219 }
220
Subtract(const BitVector * src)221 void BitVector::Subtract(const BitVector *src) {
222 uint32_t src_size = src->storage_size_;
223
224 // We only need to operate on bytes up to the smaller of the sizes of the two operands.
225 unsigned int min_size = (storage_size_ > src_size) ? src_size : storage_size_;
226
227 // Difference until max, we know both accept it:
228 // There is no need to do more:
229 // If we are bigger than src, the upper bits are unchanged.
230 // If we are smaller than src, the nonexistent upper bits are 0 and thus can't get subtracted.
231 for (uint32_t idx = 0; idx < min_size; idx++) {
232 storage_[idx] &= (~(src->GetRawStorageWord(idx)));
233 }
234 }
235
NumSetBits() const236 uint32_t BitVector::NumSetBits() const {
237 uint32_t count = 0;
238 for (uint32_t word = 0; word < storage_size_; word++) {
239 count += POPCOUNT(storage_[word]);
240 }
241 return count;
242 }
243
NumSetBits(uint32_t end) const244 uint32_t BitVector::NumSetBits(uint32_t end) const {
245 DCHECK_LE(end, storage_size_ * kWordBits);
246 return NumSetBits(storage_, end);
247 }
248
SetInitialBits(uint32_t num_bits)249 void BitVector::SetInitialBits(uint32_t num_bits) {
250 // If num_bits is 0, clear everything.
251 if (num_bits == 0) {
252 ClearAllBits();
253 return;
254 }
255
256 // Set the highest bit we want to set to get the BitVector allocated if need be.
257 SetBit(num_bits - 1);
258
259 uint32_t idx;
260 // We can set every storage element with -1.
261 for (idx = 0; idx < WordIndex(num_bits); idx++) {
262 storage_[idx] = std::numeric_limits<uint32_t>::max();
263 }
264
265 // Handle the potentially last few bits.
266 uint32_t rem_num_bits = num_bits & 0x1f;
267 if (rem_num_bits != 0) {
268 storage_[idx] = (1U << rem_num_bits) - 1;
269 ++idx;
270 }
271
272 // Now set the upper ones to 0.
273 for (; idx < storage_size_; idx++) {
274 storage_[idx] = 0;
275 }
276 }
277
GetHighestBitSet() const278 int BitVector::GetHighestBitSet() const {
279 unsigned int max = storage_size_;
280 for (int idx = max - 1; idx >= 0; idx--) {
281 // If not 0, we have more work: check the bits.
282 uint32_t value = storage_[idx];
283
284 if (value != 0) {
285 // Return highest bit set in value plus bits from previous storage indexes.
286 return 31 - CLZ(value) + (idx * kWordBits);
287 }
288 }
289
290 // All zero, therefore return -1.
291 return -1;
292 }
293
Copy(const BitVector * src)294 void BitVector::Copy(const BitVector *src) {
295 // Get highest bit set, we only need to copy till then.
296 int highest_bit = src->GetHighestBitSet();
297
298 // If nothing is set, clear everything.
299 if (highest_bit == -1) {
300 ClearAllBits();
301 return;
302 }
303
304 // Set upper bit to ensure right size before copy.
305 SetBit(highest_bit);
306
307 // Now set until highest bit's storage.
308 uint32_t size = 1 + (highest_bit / kWordBits);
309 memcpy(storage_, src->GetRawStorage(), kWordBytes * size);
310
311 // Set upper bits to 0.
312 uint32_t left = storage_size_ - size;
313
314 if (left > 0) {
315 memset(storage_ + size, 0, kWordBytes * left);
316 }
317 }
318
NumSetBits(const uint32_t * storage,uint32_t end)319 uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) {
320 uint32_t word_end = WordIndex(end);
321 uint32_t partial_word_bits = end & 0x1f;
322
323 uint32_t count = 0u;
324 for (uint32_t word = 0u; word < word_end; word++) {
325 count += POPCOUNT(storage[word]);
326 }
327 if (partial_word_bits != 0u) {
328 count += POPCOUNT(storage[word_end] & ~(0xffffffffu << partial_word_bits));
329 }
330 return count;
331 }
332
Dump(std::ostream & os,const char * prefix) const333 void BitVector::Dump(std::ostream& os, const char *prefix) const {
334 std::ostringstream buffer;
335 DumpHelper(prefix, buffer);
336 os << buffer.str() << std::endl;
337 }
338
DumpHelper(const char * prefix,std::ostringstream & buffer) const339 void BitVector::DumpHelper(const char* prefix, std::ostringstream& buffer) const {
340 // Initialize it.
341 if (prefix != nullptr) {
342 buffer << prefix;
343 }
344
345 buffer << '(';
346 for (size_t i = 0; i < storage_size_ * kWordBits; i++) {
347 buffer << IsBitSet(i);
348 }
349 buffer << ')';
350 }
351
EnsureSize(uint32_t idx)352 void BitVector::EnsureSize(uint32_t idx) {
353 if (idx >= storage_size_ * kWordBits) {
354 DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << idx;
355
356 /* Round up to word boundaries for "idx+1" bits */
357 uint32_t new_size = BitsToWords(idx + 1);
358 DCHECK_GT(new_size, storage_size_);
359 uint32_t *new_storage =
360 static_cast<uint32_t*>(allocator_->Alloc(new_size * kWordBytes));
361 memcpy(new_storage, storage_, storage_size_ * kWordBytes);
362 // Zero out the new storage words.
363 memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * kWordBytes);
364 // TODO: collect stats on space wasted because of resize.
365
366 // Free old storage.
367 allocator_->Free(storage_);
368
369 // Set fields.
370 storage_ = new_storage;
371 storage_size_ = new_size;
372 }
373 }
374
GetAllocator() const375 Allocator* BitVector::GetAllocator() const {
376 return allocator_;
377 }
378
Resize(size_t rows,size_t cols,bool clear)379 void BaseBitVectorArray::Resize(size_t rows, size_t cols, bool clear) {
380 DCHECK(IsExpandable());
381 if (clear) {
382 Clear();
383 }
384 cols = RoundUp(cols, BitVector::kWordBits);
385 num_columns_ = cols;
386 num_rows_ = rows;
387 // Ensure size
388 GetRawData().SetBit(num_rows_ * num_columns_ - 1);
389 GetRawData().ClearBit(num_rows_ * num_columns_ - 1);
390 }
391
392 // In order to improve performance we do this in 4-byte blocks. Clang should be
393 // able to optimize this to larger blocks if possible.
UnionRows(size_t dest_row,size_t other)394 void BaseBitVectorArray::UnionRows(size_t dest_row, size_t other) {
395 DCHECK_LT(dest_row, num_rows_);
396 DCHECK_LT(other, num_rows_);
397 size_t block_words = num_columns_ / BitVector::kWordBits;
398 uint32_t* dest =
399 GetRawData().GetRawStorage() + ((dest_row * num_columns_) / BitVector::kWordBits);
400 uint32_t* source = GetRawData().GetRawStorage() + ((other * num_columns_) / BitVector::kWordBits);
401 for (uint32_t i = 0; i < block_words; ++i, ++dest, ++source) {
402 *dest = (*dest) | (*source);
403 }
404 }
405
406 } // namespace art
407