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 #ifndef ART_LIBDEXFILE_DEX_COMPACT_OFFSET_TABLE_H_ 18 #define ART_LIBDEXFILE_DEX_COMPACT_OFFSET_TABLE_H_ 19 20 #include <cstdint> 21 #include <vector> 22 23 namespace art { 24 25 // Compact offset table that aims to minimize size while still providing reasonable speed (10-20ns 26 // average time per lookup on host). 27 class CompactOffsetTable { 28 public: 29 // This value is coupled with the leb chunk bitmask. That logic must also be adjusted when the 30 // integer is modified. 31 static constexpr size_t kElementsPerIndex = 16; 32 33 // Leb block format: 34 // [uint16_t] 16 bit mask for what indexes actually have a non zero offset for the chunk. 35 // [lebs] Up to 16 lebs encoded using leb128, one leb bit. The leb specifies how the offset 36 // changes compared to the previous index. 37 38 class Accessor { 39 public: 40 // Read the minimum and table offsets from the data pointer. 41 explicit Accessor(const uint8_t* data_begin); 42 43 Accessor(const uint8_t* data_begin, uint32_t minimum_offset, uint32_t table_offset); 44 45 // Return the offset for the index. 46 uint32_t GetOffset(uint32_t index) const; 47 48 private: 49 const uint32_t* const table_; 50 const uint32_t minimum_offset_; 51 const uint8_t* const data_begin_; 52 }; 53 54 // Version that also serializes the min offset and table offset. 55 static void Build(const std::vector<uint32_t>& offsets, std::vector<uint8_t>* out_data); 56 57 // Returned offsets are all relative to out_min_offset. 58 static void Build(const std::vector<uint32_t>& offsets, 59 std::vector<uint8_t>* out_data, 60 uint32_t* out_min_offset, 61 uint32_t* out_table_offset); 62 63 // 32 bit aligned for the offset table. 64 static constexpr size_t kAlignment = sizeof(uint32_t); 65 }; 66 67 } // namespace art 68 69 #endif // ART_LIBDEXFILE_DEX_COMPACT_OFFSET_TABLE_H_ 70