1 /*
2 * Copyright (C) 2018 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 "compact_offset_table.h"
18
19 #include "compact_dex_utils.h"
20 #include "base/leb128.h"
21
22 namespace art {
23
Accessor(const uint8_t * data_begin,uint32_t minimum_offset,uint32_t table_offset)24 CompactOffsetTable::Accessor::Accessor(const uint8_t* data_begin,
25 uint32_t minimum_offset,
26 uint32_t table_offset)
27 : table_(reinterpret_cast<const uint32_t*>(data_begin + table_offset)),
28 minimum_offset_(minimum_offset),
29 data_begin_(data_begin) {}
30
Accessor(const uint8_t * data_begin)31 CompactOffsetTable::Accessor::Accessor(const uint8_t* data_begin)
32 : Accessor(data_begin + 2 * sizeof(uint32_t),
33 reinterpret_cast<const uint32_t*>(data_begin)[0],
34 reinterpret_cast<const uint32_t*>(data_begin)[1]) {}
35
GetOffset(uint32_t index) const36 uint32_t CompactOffsetTable::Accessor::GetOffset(uint32_t index) const {
37 const uint32_t offset = table_[index / kElementsPerIndex];
38 const size_t bit_index = index % kElementsPerIndex;
39
40 const uint8_t* block = data_begin_ + offset;
41 uint16_t bit_mask = *block;
42 ++block;
43 bit_mask = (bit_mask << kBitsPerByte) | *block;
44 ++block;
45 if ((bit_mask & (1 << bit_index)) == 0) {
46 // Bit is not set means the offset is 0.
47 return 0u;
48 }
49 // Trim off the bits above the index we want and count how many bits are set. This is how many
50 // lebs we need to decode.
51 size_t count = POPCOUNT(static_cast<uintptr_t>(bit_mask) << (kBitsPerIntPtrT - 1 - bit_index));
52 DCHECK_GT(count, 0u);
53 uint32_t current_offset = minimum_offset_;
54 do {
55 current_offset += DecodeUnsignedLeb128(&block);
56 --count;
57 } while (count > 0);
58 return current_offset;
59 }
60
Build(const std::vector<uint32_t> & offsets,std::vector<uint8_t> * out_data)61 void CompactOffsetTable::Build(const std::vector<uint32_t>& offsets,
62 std::vector<uint8_t>* out_data) {
63 static constexpr size_t kNumOffsets = 2;
64 uint32_t out_offsets[kNumOffsets] = {};
65 CompactOffsetTable::Build(offsets, out_data, &out_offsets[0], &out_offsets[1]);
66 // Write the offsets at the start of the debug info.
67 out_data->insert(out_data->begin(),
68 reinterpret_cast<const uint8_t*>(&out_offsets[0]),
69 reinterpret_cast<const uint8_t*>(&out_offsets[kNumOffsets]));
70 }
71
Build(const std::vector<uint32_t> & offsets,std::vector<uint8_t> * out_data,uint32_t * out_min_offset,uint32_t * out_table_offset)72 void CompactOffsetTable::Build(const std::vector<uint32_t>& offsets,
73 std::vector<uint8_t>* out_data,
74 uint32_t* out_min_offset,
75 uint32_t* out_table_offset) {
76 DCHECK(out_data != nullptr);
77 DCHECK(out_data->empty());
78 // Calculate the base offset and return it.
79 *out_min_offset = std::numeric_limits<uint32_t>::max();
80 for (const uint32_t offset : offsets) {
81 if (offset != 0u) {
82 *out_min_offset = std::min(*out_min_offset, offset);
83 }
84 }
85 // Write the leb blocks and store the important offsets (each kElementsPerIndex elements).
86 size_t block_start = 0;
87
88 std::vector<uint32_t> offset_table;
89
90 // Write data first then the table.
91 while (block_start < offsets.size()) {
92 // Write the offset of the block for each block.
93 offset_table.push_back(out_data->size());
94
95 // Block size of up to kElementsPerIndex
96 const size_t block_size = std::min(offsets.size() - block_start, kElementsPerIndex);
97
98 // Calculate bit mask since need to write that first.
99 uint16_t bit_mask = 0u;
100 for (size_t i = 0; i < block_size; ++i) {
101 if (offsets[block_start + i] != 0u) {
102 bit_mask |= 1 << i;
103 }
104 }
105 // Write bit mask.
106 out_data->push_back(static_cast<uint8_t>(bit_mask >> kBitsPerByte));
107 out_data->push_back(static_cast<uint8_t>(bit_mask));
108
109 // Write offsets relative to the previous offset.
110 uint32_t prev_offset = *out_min_offset;
111 for (size_t i = 0; i < block_size; ++i) {
112 const uint32_t offset = offsets[block_start + i];
113 if (offset != 0u) {
114 uint32_t delta = offset - prev_offset;
115 EncodeUnsignedLeb128(out_data, delta);
116 prev_offset = offset;
117 }
118 }
119
120 block_start += block_size;
121 }
122
123 // Write the offset table.
124 AlignmentPadVector(out_data, alignof(uint32_t));
125 *out_table_offset = out_data->size();
126 out_data->insert(out_data->end(),
127 reinterpret_cast<const uint8_t*>(&offset_table[0]),
128 reinterpret_cast<const uint8_t*>(&offset_table[0] + offset_table.size()));
129 }
130
131 } // namespace art
132