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 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 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 38 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 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 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