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