blob: 15dd19ca9f05b7440f89fc9cf35a3c6ca73dc29d [file] [log] [blame]
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#include "vm/bitmap.h"
#include "platform/assert.h"
#include "vm/log.h"
#include "vm/object.h"
namespace dart {
void BitmapBuilder::SetLength(intptr_t new_length) {
// When this function is used to shorten the length, affected bits in the
// backing store need to be cleared because the implementation assumes it.
if (new_length < length_) {
// Byte offset containing the first bit to be cleared.
intptr_t byte_offset = new_length >> kBitsPerByteLog2;
if (byte_offset < data_size_in_bytes_) {
// First bit index (in the byte) to be cleared.
intptr_t bit_index = new_length & (kBitsPerByte - 1);
intptr_t mask = (1 << bit_index) - 1;
BackingStore()[byte_offset] &= mask;
// Clear the rest.
++byte_offset;
if (byte_offset < data_size_in_bytes_) {
memset(&BackingStore()[byte_offset], 0,
data_size_in_bytes_ - byte_offset);
}
}
}
length_ = new_length;
}
bool BitmapBuilder::Get(intptr_t bit_offset) const {
if (!InRange(bit_offset)) {
return false;
}
intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
// Bits not covered by the backing store are implicitly false.
return (byte_offset < data_size_in_bytes_) && GetBit(bit_offset);
}
void BitmapBuilder::Set(intptr_t bit_offset, bool value) {
if (!InRange(bit_offset)) {
length_ = bit_offset + 1;
}
// Bits not covered by the backing store are implicitly false.
// Grow the backing store if necessary.
if (value) {
if (!InBackingStore(bit_offset)) {
intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
uint8_t* old_data = BackingStore();
intptr_t old_size = data_size_in_bytes_;
data_size_in_bytes_ =
Utils::RoundUp(byte_offset + 1, kIncrementSizeInBytes);
ASSERT(data_size_in_bytes_ > 0);
// Note: do not update data_ yet because it might overwrite old_data
// contents.
uint8_t* new_data = AllocBackingStore(data_size_in_bytes_);
memmove(new_data, old_data, old_size);
memset(&new_data[old_size], 0, (data_size_in_bytes_ - old_size));
data_.ptr_ = new_data;
}
ASSERT(InBackingStore(bit_offset));
}
// Set bit if in backing store.
if (InBackingStore(bit_offset)) {
SetBit(bit_offset, value);
}
}
void BitmapBuilder::SetRange(intptr_t min, intptr_t max, bool value) {
for (intptr_t i = min; i <= max; i++) {
Set(i, value);
}
}
void BitmapBuilder::Print() const {
for (intptr_t i = 0; i < Length(); i++) {
if (Get(i)) {
THR_Print("1");
} else {
THR_Print("0");
}
}
}
void BitmapBuilder::AppendAsBytesTo(BaseWriteStream* stream) const {
// Early return if there are no bits in the payload to copy.
if (Length() == 0) return;
const intptr_t total_size =
Utils::RoundUp(Length(), kBitsPerByte) / kBitsPerByte;
intptr_t payload_size;
intptr_t extra_size;
if (total_size > data_size_in_bytes_) {
// A [BitmapBuilder] does not allocate storage for the trailing 0 bits in
// the backing store, so we need to add additional empty bytes here.
payload_size = data_size_in_bytes_;
extra_size = total_size - data_size_in_bytes_;
} else {
payload_size = total_size;
extra_size = 0;
}
#if defined(DEBUG)
// Make sure any bits in the payload beyond the bit length if we're not
// appending trailing zeroes are cleared to ensure deterministic snapshots.
if (extra_size == 0 && Length() % kBitsPerByte != 0) {
const int8_t mask = (1 << (Length() % kBitsPerByte)) - 1;
ASSERT_EQUAL(BackingStore()[payload_size - 1],
(BackingStore()[payload_size - 1] & mask));
}
#endif
stream->WriteBytes(BackingStore(), payload_size);
for (intptr_t i = 0; i < extra_size; i++) {
stream->WriteByte(0U);
}
}
bool BitmapBuilder::GetBit(intptr_t bit_offset) const {
if (!InRange(bit_offset)) {
return false;
}
intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
ASSERT(byte_offset < data_size_in_bytes_);
intptr_t bit_remainder = bit_offset & (kBitsPerByte - 1);
uint8_t mask = 1U << bit_remainder;
return ((BackingStore()[byte_offset] & mask) != 0);
}
void BitmapBuilder::SetBit(intptr_t bit_offset, bool value) {
if (!InRange(bit_offset)) {
FATAL(
"Fatal error in BitmapBuilder::SetBit :"
" invalid bit_offset, %" Pd "\n",
bit_offset);
}
intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
ASSERT(byte_offset < data_size_in_bytes_);
intptr_t bit_remainder = bit_offset & (kBitsPerByte - 1);
uint8_t mask = 1U << bit_remainder;
if (value) {
BackingStore()[byte_offset] |= mask;
} else {
BackingStore()[byte_offset] &= ~mask;
}
}
void BitmapBuilder::Write(BaseWriteStream* stream) const {
const intptr_t payload_size =
Utils::Minimum(Utils::RoundUp(Length(), kBitsPerByte) / kBitsPerByte,
data_size_in_bytes_);
stream->Write<intptr_t>(Length());
stream->Write<intptr_t>(payload_size);
stream->WriteBytes(BackingStore(), payload_size);
}
void BitmapBuilder::Read(ReadStream* stream) {
length_ = stream->Read<intptr_t>();
const intptr_t payload_size = stream->Read<intptr_t>();
if (payload_size > data_size_in_bytes_) {
data_size_in_bytes_ = payload_size;
data_.ptr_ = AllocBackingStore(data_size_in_bytes_);
} else {
memset(BackingStore() + payload_size, 0,
data_size_in_bytes_ - payload_size);
}
stream->ReadBytes(BackingStore(), payload_size);
}
} // namespace dart