1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/bitmap.h"
6
7#include "platform/assert.h"
8#include "vm/object.h"
9
10namespace dart {
11
12void BitmapBuilder::SetLength(intptr_t new_length) {
13 // When this function is used to shorten the length, affected bits in the
14 // backing store need to be cleared because the implementation assumes it.
15 if (new_length < length_) {
16 // Byte offset containing the first bit to be cleared.
17 intptr_t byte_offset = new_length >> kBitsPerByteLog2;
18 if (byte_offset < data_size_in_bytes_) {
19 // First bit index (in the byte) to be cleared.
20 intptr_t bit_index = new_length & (kBitsPerByte - 1);
21 intptr_t mask = (1 << bit_index) - 1;
22 data_[byte_offset] &= mask;
23 // Clear the rest.
24 ++byte_offset;
25 if (byte_offset < data_size_in_bytes_) {
26 memset(&data_[byte_offset], 0, data_size_in_bytes_ - byte_offset);
27 }
28 }
29 }
30 length_ = new_length;
31}
32
33bool BitmapBuilder::Get(intptr_t bit_offset) const {
34 if (!InRange(bit_offset)) {
35 return false;
36 }
37 intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
38 // Bits not covered by the backing store are implicitly false.
39 return (byte_offset < data_size_in_bytes_) && GetBit(bit_offset);
40}
41
42void BitmapBuilder::Set(intptr_t bit_offset, bool value) {
43 if (!InRange(bit_offset)) {
44 length_ = bit_offset + 1;
45 // Bits not covered by the backing store are implicitly false.
46 if (!value) return;
47 // Grow the backing store if necessary.
48 intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
49 if (byte_offset >= data_size_in_bytes_) {
50 uint8_t* old_data = data_;
51 intptr_t old_size = data_size_in_bytes_;
52 data_size_in_bytes_ =
53 Utils::RoundUp(byte_offset + 1, kIncrementSizeInBytes);
54 ASSERT(data_size_in_bytes_ > 0);
55 data_ = Thread::Current()->zone()->Alloc<uint8_t>(data_size_in_bytes_);
56 ASSERT(data_ != NULL);
57 memmove(data_, old_data, old_size);
58 memset(&data_[old_size], 0, (data_size_in_bytes_ - old_size));
59 }
60 }
61 SetBit(bit_offset, value);
62}
63
64void BitmapBuilder::SetRange(intptr_t min, intptr_t max, bool value) {
65 for (intptr_t i = min; i <= max; i++) {
66 Set(i, value);
67 }
68}
69
70void BitmapBuilder::Print() const {
71 for (intptr_t i = 0; i < Length(); i++) {
72 if (Get(i)) {
73 OS::PrintErr("1");
74 } else {
75 OS::PrintErr("0");
76 }
77 }
78}
79
80void BitmapBuilder::AppendAsBytesTo(GrowableArray<uint8_t>* bytes) const {
81 // Early return if there are no bits in the payload to copy.
82 if (Length() == 0) return;
83
84 const intptr_t total_size =
85 Utils::RoundUp(Length(), kBitsPerByte) / kBitsPerByte;
86 intptr_t payload_size;
87 intptr_t extra_size;
88 if (total_size > data_size_in_bytes_) {
89 // A [BitmapBuilder] does not allocate storage for the trailing 0 bits in
90 // the backing store, so we need to add additional empty bytes here.
91 payload_size = data_size_in_bytes_;
92 extra_size = total_size - data_size_in_bytes_;
93 } else {
94 payload_size = total_size;
95 extra_size = 0;
96 }
97 for (intptr_t i = 0; i < payload_size; i++) {
98 bytes->Add(data_[i]);
99 }
100 for (intptr_t i = 0; i < extra_size; i++) {
101 bytes->Add(0U);
102 }
103 // Make sure any bits in the payload beyond the bit length are cleared to
104 // ensure deterministic snapshots.
105#if defined(DEBUG)
106 if (Length() % kBitsPerByte == 0) return;
107 const int8_t mask = (1 << (Length() % kBitsPerByte)) - 1;
108 ASSERT(bytes->Last() == (bytes->Last() & mask));
109#endif
110}
111
112bool BitmapBuilder::GetBit(intptr_t bit_offset) const {
113 if (!InRange(bit_offset)) {
114 return false;
115 }
116 intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
117 ASSERT(byte_offset < data_size_in_bytes_);
118 intptr_t bit_remainder = bit_offset & (kBitsPerByte - 1);
119 uint8_t mask = 1U << bit_remainder;
120 ASSERT(data_ != NULL);
121 return ((data_[byte_offset] & mask) != 0);
122}
123
124void BitmapBuilder::SetBit(intptr_t bit_offset, bool value) {
125 if (!InRange(bit_offset)) {
126 FATAL1(
127 "Fatal error in BitmapBuilder::SetBit :"
128 " invalid bit_offset, %" Pd "\n",
129 bit_offset);
130 }
131 intptr_t byte_offset = bit_offset >> kBitsPerByteLog2;
132 ASSERT(byte_offset < data_size_in_bytes_);
133 intptr_t bit_remainder = bit_offset & (kBitsPerByte - 1);
134 uint8_t mask = 1U << bit_remainder;
135 ASSERT(data_ != NULL);
136 if (value) {
137 data_[byte_offset] |= mask;
138 } else {
139 data_[byte_offset] &= ~mask;
140 }
141}
142
143} // namespace dart
144