diff options
Diffstat (limited to 'tools/relocation_packer/src/delta_encoder.cc')
| -rw-r--r-- | tools/relocation_packer/src/delta_encoder.cc | 307 |
1 files changed, 0 insertions, 307 deletions
diff --git a/tools/relocation_packer/src/delta_encoder.cc b/tools/relocation_packer/src/delta_encoder.cc deleted file mode 100644 index 8349d7c64..000000000 --- a/tools/relocation_packer/src/delta_encoder.cc +++ /dev/null @@ -1,307 +0,0 @@ -// Copyright 2014 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#include "delta_encoder.h" - -#include <vector> - -#include "debug.h" - -static constexpr uint32_t RELOCATION_GROUPED_BY_INFO_FLAG = 1; -static constexpr uint32_t RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2; -static constexpr uint32_t RELOCATION_GROUPED_BY_ADDEND_FLAG = 4; -static constexpr uint32_t RELOCATION_GROUP_HAS_ADDEND_FLAG = 8; - -static bool is_relocation_grouped_by_info(uint64_t flags) { - return (flags & RELOCATION_GROUPED_BY_INFO_FLAG) != 0; -} - -static bool is_relocation_grouped_by_offset_delta(uint64_t flags) { - return (flags & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) != 0; -} - -static bool is_relocation_grouped_by_addend(uint64_t flags) { - return (flags & RELOCATION_GROUPED_BY_ADDEND_FLAG) != 0; -} - -static bool is_relocation_group_has_addend(uint64_t flags) { - return (flags & RELOCATION_GROUP_HAS_ADDEND_FLAG) != 0; -} - -namespace relocation_packer { - -// Encode relocations into a delta encoded (packed) representation. -template <typename ELF> -void RelocationDeltaCodec<ELF>::Encode(const std::vector<ElfRela>& relocations, - std::vector<ElfAddr>* packed) { - if (relocations.size() == 0) - return; - - // Start with the relocation count, then append groups - // TODO(dimitry): we might want to move it to DT_ANDROID_RELCOUNT section - packed->push_back(static_cast<ElfAddr>(relocations.size())); - - // lets write starting offset (offset of the first reloc - first delta) - ElfAddr start_offset = relocations.size() > 1 ? - relocations[0].r_offset - (relocations[1].r_offset - relocations[0].r_offset) : - relocations[0].r_offset; - - packed->push_back(start_offset); - - // this one is used to calculate delta - ElfAddr previous_addend = 0; - ElfAddr previous_offset = start_offset; - - for (size_t group_start = 0; group_start < relocations.size(); ) { - ElfAddr group_flags = 0; - ElfAddr group_offset_delta = 0; - ElfAddr group_addend = 0; - ElfAddr group_info = 0; - - ElfAddr group_size = 0; - - DetectGroup(relocations, group_start, previous_offset, &group_size, &group_flags, - &group_offset_delta, &group_info, &group_addend); - - // write the group header - packed->push_back(group_size); - packed->push_back(group_flags); - - if (is_relocation_grouped_by_offset_delta(group_flags)) { - packed->push_back(group_offset_delta); - } - - if (is_relocation_grouped_by_info(group_flags)) { - packed->push_back(group_info); - } - - if (is_relocation_group_has_addend(group_flags) && - is_relocation_grouped_by_addend(group_flags)) { - packed->push_back(group_addend - previous_addend); - previous_addend = group_addend; - } - - for (size_t i = 0; i < static_cast<size_t>(group_size); ++i) { - CHECK((group_start + i) < relocations.size()); - const ElfRela* relocation = &relocations[group_start + i]; - - if (!is_relocation_grouped_by_offset_delta(group_flags)) { - packed->push_back(relocation->r_offset - previous_offset); - } - previous_offset = relocation->r_offset; - - if (!is_relocation_grouped_by_info(group_flags)) { - packed->push_back(relocation->r_info); - } - - if (is_relocation_group_has_addend(group_flags) && - !is_relocation_grouped_by_addend(group_flags)) { - packed->push_back(relocation->r_addend - previous_addend); - previous_addend = relocation->r_addend; - } - } - - // If the relocation group does not have an addend - reset it to 0 - // to simplify addend computation for the group following this one. - if (!is_relocation_group_has_addend(group_flags)) { - previous_addend = 0; - } - - group_start += group_size; - } -} - -// Decode relocations from a delta encoded (packed) representation. -template <typename ELF> -void RelocationDeltaCodec<ELF>::Decode(const std::vector<ElfAddr>& packed, - std::vector<ElfRela>* relocations) { - if (packed.size() < 5) { - return; - } - - size_t ndx = 0; - ElfAddr current_count = 0; - ElfAddr total_count = packed[ndx++]; - - ElfAddr offset = packed[ndx++]; - ElfAddr info = 0; - ElfAddr addend = 0; - - while(current_count < total_count) { - // read group - ElfAddr group_size = packed[ndx++]; - ElfAddr group_flags = packed[ndx++]; - ElfAddr group_offset_delta = 0; - - if (is_relocation_grouped_by_offset_delta(group_flags)) { - group_offset_delta = packed[ndx++]; - } - - if (is_relocation_grouped_by_info(group_flags)) { - info = packed[ndx++]; - } - - if (is_relocation_group_has_addend(group_flags) && - is_relocation_grouped_by_addend(group_flags)) { - addend += packed[ndx++]; - } - - // now read not grouped info - for (ElfAddr i = 0; i<group_size; ++i) { - if (is_relocation_grouped_by_offset_delta(group_flags)) { - offset += group_offset_delta; - } else { - offset += packed[ndx++]; - } - - if (!is_relocation_grouped_by_info(group_flags)) { - info = packed[ndx++]; - } - - if (is_relocation_group_has_addend(group_flags) && - !is_relocation_grouped_by_addend(group_flags)) { - addend += packed[ndx++]; - } - - ElfRela reloc; - reloc.r_offset = offset; - reloc.r_info = info; - reloc.r_addend = is_relocation_group_has_addend(group_flags) ? addend : 0; - relocations->push_back(reloc); - } - - if (!is_relocation_group_has_addend(group_flags)) { - addend = 0; - } - - current_count += group_size; - } -} - -// This function detects a way to group reloc_one and reloc_two, sets up group_flags -// and initializes values for corresponding group_ fields. For example if relocations -// can be grouped by r_info the function will set group_info variable. -template <typename ELF> -void RelocationDeltaCodec<ELF>::DetectGroupFields(const ElfRela& reloc_one, - const ElfRela& reloc_two, - ElfAddr current_offset_delta, - ElfAddr* group_flags, - ElfAddr* group_offset_delta, - ElfAddr* group_info, - ElfAddr* group_addend) { - *group_flags = 0; - - const ElfAddr offset_delta = static_cast<ElfAddr>(reloc_two.r_offset) - - static_cast<ElfAddr>(reloc_one.r_offset); - - if (offset_delta == current_offset_delta) { - *group_flags |= RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG; - if (group_offset_delta != nullptr) { - *group_offset_delta = current_offset_delta; - } - } - - if (reloc_one.r_info == reloc_two.r_info) { - *group_flags |= RELOCATION_GROUPED_BY_INFO_FLAG; - if (group_info != nullptr) { - *group_info = reloc_one.r_info; - } - } - - if (reloc_one.r_addend != 0 || reloc_two.r_addend != 0) { - *group_flags |= RELOCATION_GROUP_HAS_ADDEND_FLAG; - if (reloc_one.r_addend == reloc_two.r_addend) { - *group_flags |= RELOCATION_GROUPED_BY_ADDEND_FLAG; - if (group_addend != nullptr) { - *group_addend = reloc_one.r_addend; - } - } - } -} - -// This function is used to detect if there is better group available -// during RelocationDeltaCodec<ELF>::DetectGroup processing. -// Current implementation prefers having groups without addend (== zero addend) -// to any other groups field with the ratio 3:1. This is because addend tends -// to be more unevenly distributed than other fields. -static uint32_t group_weight(uint64_t flags) { - uint32_t weight = 0; - if (!is_relocation_group_has_addend(flags)) { - weight += 3; - } else if (is_relocation_grouped_by_addend(flags)) { - weight += 1; - } - - if (is_relocation_grouped_by_offset_delta(flags)) { - weight += 1; - } - - if (is_relocation_grouped_by_info(flags)) { - weight += 1; - } - - return weight; -} - -template <typename ELF> -void RelocationDeltaCodec<ELF>::DetectGroup(const std::vector<ElfRela>& relocations, - size_t group_starts_with, ElfAddr previous_offset, - ElfAddr* group_size, ElfAddr* group_flags, - ElfAddr* group_offset_delta, ElfAddr* group_info, - ElfAddr* group_addend) { - CHECK(group_starts_with < relocations.size()); - CHECK(group_flags != nullptr); - - const ElfRela& reloc_one = relocations[group_starts_with++]; - if (group_starts_with == relocations.size()) { - *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG; - *group_size = 1; - return; - } - - const ElfAddr offset_delta = reloc_one.r_offset - previous_offset; - - // detect group_flags - DetectGroupFields(reloc_one, relocations[group_starts_with], offset_delta, group_flags, - group_offset_delta, group_info, group_addend); - - if (group_starts_with + 1 == relocations.size()) { - *group_size = 2; - return; - } - - ElfAddr cnt = 1; - for (size_t i = group_starts_with; i < relocations.size() - 1; ++i) { - ElfAddr candidate_flags; - // check if next group (reloc_current; reloc_next) has better grouped_by flags - DetectGroupFields(relocations[i], relocations[i+1], offset_delta, &candidate_flags, - nullptr, nullptr, nullptr); - - if (group_weight(*group_flags) < group_weight(candidate_flags)) { - break; - } - cnt++; - - if (candidate_flags != *group_flags) { - break; - } - - if (i + 1 == relocations.size() - 1) { // last one - cnt++; - } - } - - // if as a result of checking candidates we ended up with cnt == 1 - // reset flags to the default state - if (cnt == 1) { - *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG; - } - - *group_size = cnt; -} - -template class RelocationDeltaCodec<ELF32_traits>; -template class RelocationDeltaCodec<ELF64_traits>; - -} // namespace relocation_packer |