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