| /* |
| * Copyright (C) 2011 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. |
| */ |
| |
| #include "bit_vector.h" |
| |
| #include <limits> |
| #include <sstream> |
| |
| #include "allocator.h" |
| #include "bit_vector-inl.h" |
| |
| namespace art { |
| |
| // The number of words necessary to encode bits. |
| static constexpr uint32_t BitsToWords(uint32_t bits) { |
| return RoundUp(bits, 32) / 32; |
| } |
| |
| // TODO: replace excessive argument defaulting when we are at gcc 4.7 |
| // or later on host with delegating constructor support. Specifically, |
| // starts_bits and storage_size/storage are mutually exclusive. |
| BitVector::BitVector(uint32_t start_bits, |
| bool expandable, |
| Allocator* allocator, |
| uint32_t storage_size, |
| uint32_t* storage) |
| : storage_(storage), |
| storage_size_(storage_size), |
| allocator_(allocator), |
| expandable_(expandable) { |
| static_assert(sizeof(*storage_) == kWordBytes, "word bytes"); |
| static_assert(sizeof(*storage_) * 8u == kWordBits, "word bits"); |
| if (storage_ == nullptr) { |
| storage_size_ = BitsToWords(start_bits); |
| storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * kWordBytes)); |
| } |
| } |
| |
| BitVector::~BitVector() { |
| allocator_->Free(storage_); |
| } |
| |
| bool BitVector::SameBitsSet(const BitVector *src) const { |
| int our_highest = GetHighestBitSet(); |
| int src_highest = src->GetHighestBitSet(); |
| |
| // If the highest bit set is different, we are different. |
| if (our_highest != src_highest) { |
| return false; |
| } |
| |
| // If the highest bit set is -1, both are cleared, we are the same. |
| // If the highest bit set is 0, both have a unique bit set, we are the same. |
| if (our_highest <= 0) { |
| return true; |
| } |
| |
| // Get the highest bit set's cell's index |
| // No need of highest + 1 here because it can't be 0 so BitsToWords will work here. |
| int our_highest_index = BitsToWords(our_highest); |
| |
| // This memcmp is enough: we know that the highest bit set is the same for both: |
| // - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less. |
| // ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index, |
| // they are automatically at 0. |
| return (memcmp(storage_, src->GetRawStorage(), our_highest_index * kWordBytes) == 0); |
| } |
| |
| void BitVector::Intersect(const BitVector* src) { |
| uint32_t src_storage_size = src->storage_size_; |
| |
| // Get the minimum size between us and source. |
| uint32_t min_size = (storage_size_ < src_storage_size) ? storage_size_ : src_storage_size; |
| |
| uint32_t idx; |
| for (idx = 0; idx < min_size; idx++) { |
| storage_[idx] &= src->GetRawStorageWord(idx); |
| } |
| |
| // Now, due to this being an intersection, there are two possibilities: |
| // - Either src was larger than us: we don't care, all upper bits would thus be 0. |
| // - Either we are larger than src: we don't care, all upper bits would have been 0 too. |
| // So all we need to do is set all remaining bits to 0. |
| for (; idx < storage_size_; idx++) { |
| storage_[idx] = 0; |
| } |
| } |
| |
| bool BitVector::Union(const BitVector* src) { |
| // Get the highest bit to determine how much we need to expand. |
| int highest_bit = src->GetHighestBitSet(); |
| bool changed = false; |
| |
| // If src has no bit set, we are done: there is no need for a union with src. |
| if (highest_bit == -1) { |
| return changed; |
| } |
| |
| // Update src_size to how many cells we actually care about: where the bit is + 1. |
| uint32_t src_size = BitsToWords(highest_bit + 1); |
| |
| // Is the storage size smaller than src's? |
| if (storage_size_ < src_size) { |
| changed = true; |
| |
| EnsureSize(highest_bit); |
| |
| // Paranoid: storage size should be big enough to hold this bit now. |
| DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits); |
| } |
| |
| for (uint32_t idx = 0; idx < src_size; idx++) { |
| uint32_t existing = storage_[idx]; |
| uint32_t update = existing | src->GetRawStorageWord(idx); |
| if (existing != update) { |
| changed = true; |
| storage_[idx] = update; |
| } |
| } |
| return changed; |
| } |
| |
| bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) { |
| // Get the highest bit to determine how much we need to expand. |
| int highest_bit = union_with->GetHighestBitSet(); |
| bool changed = false; |
| |
| // If src has no bit set, we are done: there is no need for a union with src. |
| if (highest_bit == -1) { |
| return changed; |
| } |
| |
| // Update union_with_size to how many cells we actually care about: where the bit is + 1. |
| uint32_t union_with_size = BitsToWords(highest_bit + 1); |
| |
| // Is the storage size smaller than src's? |
| if (storage_size_ < union_with_size) { |
| EnsureSize(highest_bit); |
| |
| // Paranoid: storage size should be big enough to hold this bit now. |
| DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits); |
| } |
| |
| uint32_t not_in_size = not_in->GetStorageSize(); |
| |
| uint32_t idx = 0; |
| for (; idx < std::min(not_in_size, union_with_size); idx++) { |
| uint32_t existing = storage_[idx]; |
| uint32_t update = existing | |
| (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx)); |
| if (existing != update) { |
| changed = true; |
| storage_[idx] = update; |
| } |
| } |
| |
| for (; idx < union_with_size; idx++) { |
| uint32_t existing = storage_[idx]; |
| uint32_t update = existing | union_with->GetRawStorageWord(idx); |
| if (existing != update) { |
| changed = true; |
| storage_[idx] = update; |
| } |
| } |
| return changed; |
| } |
| |
| void BitVector::Subtract(const BitVector *src) { |
| uint32_t src_size = src->storage_size_; |
| |
| // We only need to operate on bytes up to the smaller of the sizes of the two operands. |
| unsigned int min_size = (storage_size_ > src_size) ? src_size : storage_size_; |
| |
| // Difference until max, we know both accept it: |
| // There is no need to do more: |
| // If we are bigger than src, the upper bits are unchanged. |
| // If we are smaller than src, the non-existant upper bits are 0 and thus can't get subtracted. |
| for (uint32_t idx = 0; idx < min_size; idx++) { |
| storage_[idx] &= (~(src->GetRawStorageWord(idx))); |
| } |
| } |
| |
| uint32_t BitVector::NumSetBits() const { |
| uint32_t count = 0; |
| for (uint32_t word = 0; word < storage_size_; word++) { |
| count += POPCOUNT(storage_[word]); |
| } |
| return count; |
| } |
| |
| uint32_t BitVector::NumSetBits(uint32_t end) const { |
| DCHECK_LE(end, storage_size_ * kWordBits); |
| return NumSetBits(storage_, end); |
| } |
| |
| void BitVector::SetInitialBits(uint32_t num_bits) { |
| // If num_bits is 0, clear everything. |
| if (num_bits == 0) { |
| ClearAllBits(); |
| return; |
| } |
| |
| // Set the highest bit we want to set to get the BitVector allocated if need be. |
| SetBit(num_bits - 1); |
| |
| uint32_t idx; |
| // We can set every storage element with -1. |
| for (idx = 0; idx < WordIndex(num_bits); idx++) { |
| storage_[idx] = std::numeric_limits<uint32_t>::max(); |
| } |
| |
| // Handle the potentially last few bits. |
| uint32_t rem_num_bits = num_bits & 0x1f; |
| if (rem_num_bits != 0) { |
| storage_[idx] = (1U << rem_num_bits) - 1; |
| ++idx; |
| } |
| |
| // Now set the upper ones to 0. |
| for (; idx < storage_size_; idx++) { |
| storage_[idx] = 0; |
| } |
| } |
| |
| int BitVector::GetHighestBitSet() const { |
| unsigned int max = storage_size_; |
| for (int idx = max - 1; idx >= 0; idx--) { |
| // If not 0, we have more work: check the bits. |
| uint32_t value = storage_[idx]; |
| |
| if (value != 0) { |
| // Return highest bit set in value plus bits from previous storage indexes. |
| return 31 - CLZ(value) + (idx * kWordBits); |
| } |
| } |
| |
| // All zero, therefore return -1. |
| return -1; |
| } |
| |
| void BitVector::Copy(const BitVector *src) { |
| // Get highest bit set, we only need to copy till then. |
| int highest_bit = src->GetHighestBitSet(); |
| |
| // If nothing is set, clear everything. |
| if (highest_bit == -1) { |
| ClearAllBits(); |
| return; |
| } |
| |
| // Set upper bit to ensure right size before copy. |
| SetBit(highest_bit); |
| |
| // Now set until highest bit's storage. |
| uint32_t size = 1 + (highest_bit / kWordBits); |
| memcpy(storage_, src->GetRawStorage(), kWordBytes * size); |
| |
| // Set upper bits to 0. |
| uint32_t left = storage_size_ - size; |
| |
| if (left > 0) { |
| memset(storage_ + size, 0, kWordBytes * left); |
| } |
| } |
| |
| #if defined(__clang__) && defined(__ARM_64BIT_STATE) |
| // b/19180814 When POPCOUNT is inlined, boot up failed on arm64 devices. |
| __attribute__((optnone)) |
| #endif |
| uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) { |
| uint32_t word_end = WordIndex(end); |
| uint32_t partial_word_bits = end & 0x1f; |
| |
| uint32_t count = 0u; |
| for (uint32_t word = 0u; word < word_end; word++) { |
| count += POPCOUNT(storage[word]); |
| } |
| if (partial_word_bits != 0u) { |
| count += POPCOUNT(storage[word_end] & ~(0xffffffffu << partial_word_bits)); |
| } |
| return count; |
| } |
| |
| void BitVector::Dump(std::ostream& os, const char *prefix) const { |
| std::ostringstream buffer; |
| DumpHelper(prefix, buffer); |
| os << buffer.str() << std::endl; |
| } |
| |
| void BitVector::DumpHelper(const char* prefix, std::ostringstream& buffer) const { |
| // Initialize it. |
| if (prefix != nullptr) { |
| buffer << prefix; |
| } |
| |
| buffer << '('; |
| for (size_t i = 0; i < storage_size_ * kWordBits; i++) { |
| buffer << IsBitSet(i); |
| } |
| buffer << ')'; |
| } |
| |
| void BitVector::EnsureSize(uint32_t idx) { |
| if (idx >= storage_size_ * kWordBits) { |
| DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << idx; |
| |
| /* Round up to word boundaries for "idx+1" bits */ |
| uint32_t new_size = BitsToWords(idx + 1); |
| DCHECK_GT(new_size, storage_size_); |
| uint32_t *new_storage = |
| static_cast<uint32_t*>(allocator_->Alloc(new_size * kWordBytes)); |
| memcpy(new_storage, storage_, storage_size_ * kWordBytes); |
| // Zero out the new storage words. |
| memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * kWordBytes); |
| // TODO: collect stats on space wasted because of resize. |
| |
| // Free old storage. |
| allocator_->Free(storage_); |
| |
| // Set fields. |
| storage_ = new_storage; |
| storage_size_ = new_size; |
| } |
| } |
| |
| } // namespace art |