1f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 2f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// found in the LICENSE file. 4f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 5f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "run_length_encoder.h" 6f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 7f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include <vector> 8f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 9f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "debug.h" 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "elf_traits.h" 11f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 12f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)namespace relocation_packer { 13f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 14f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)namespace { 15f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 16f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Generate a vector of deltas between the r_offset fields of adjacent 175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// relative relocations. 185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void GetDeltas(const std::vector<ELF::Rel>& relocations, 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Addr>* deltas) { 20f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) CHECK(relocations.size() >= 2); 21f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 22f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) for (size_t i = 0; i < relocations.size() - 1; ++i) { 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const ELF::Rel* first = &relocations[i]; 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) CHECK(ELF_R_TYPE(first->r_info) == ELF::kRelativeRelocationCode); 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const ELF::Rel* second = &relocations[i + 1]; 275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) CHECK(ELF_R_TYPE(second->r_info) == ELF::kRelativeRelocationCode); 285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 29f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Requires that offsets are 'strictly increasing'. The packing 30f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // algorithm fails if this does not hold. 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) CHECK(second->r_offset > first->r_offset); 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) deltas->push_back(second->r_offset - first->r_offset); 33f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 34f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 35f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 36f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Condense a set of r_offset deltas into a run-length encoded packing. 37f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Represented as count-delta pairs, where count is the run length and 38f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// delta the common difference between adjacent r_offsets. 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Condense(const std::vector<ELF::Addr>& deltas, 405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Xword>* packed) { 41f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) CHECK(!deltas.empty()); 42f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) size_t count = 0; 435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ELF::Addr current = deltas[0]; 44f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 45f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Identify spans of identically valued deltas. 46f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) for (size_t i = 0; i < deltas.size(); ++i) { 475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const ELF::Addr delta = deltas[i]; 48f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (delta == current) { 49f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) count++; 50f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } else { 51f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // We reached the end of a span of identically valued deltas. 52f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) packed->push_back(count); 53f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) packed->push_back(current); 54f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) current = delta; 55f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) count = 1; 56f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 57f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 58f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 59f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Write the final span. 60f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) packed->push_back(count); 61f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) packed->push_back(current); 62f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 63f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 64f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Uncondense a set of r_offset deltas from a run-length encoded packing. 65f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// The initial address for uncondensing, the start index for the first 66f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// condensed slot in packed, and the count of pairs are provided. 675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Uncondense(ELF::Addr addr, 685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const std::vector<ELF::Xword>& packed, 69f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) size_t start_index, 70f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) size_t end_index, 715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Rel>* relocations) { 72f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // The first relocation is just one created from the initial address. 735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ELF::Rel initial; 745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) initial.r_offset = addr; 755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) initial.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); 76f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) relocations->push_back(initial); 77f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 78f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Read each count and delta pair, beginning at the start index and 79f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // finishing at the end index. 80f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) for (size_t i = start_index; i < end_index; i += 2) { 81f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) size_t count = packed[i]; 825f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const ELF::Addr delta = packed[i + 1]; 83f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) CHECK(count > 0 && delta > 0); 84f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 85f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Generate relocations for this count and delta pair. 86f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) while (count) { 87f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) addr += delta; 885f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ELF::Rel relocation; 895f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) relocation.r_offset = addr; 905f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); 91f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) relocations->push_back(relocation); 92f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) count--; 93f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 94f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 95f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 96f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 97f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} // namespace 98f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 995f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Encode relative relocations into a run-length encoded (packed) 100f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// representation. 1015f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void RelocationRunLengthCodec::Encode(const std::vector<ELF::Rel>& relocations, 1025f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Xword>* packed) { 103f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // If we have zero or one relocation only then there is no packing 104f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // possible; a run-length encoding needs a run. 105f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (relocations.size() < 2) 106f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return; 107f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 1085f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Addr> deltas; 109f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) GetDeltas(relocations, &deltas); 110f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 111f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Reserve space for the element count. 112f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) packed->push_back(0); 113f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 114f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Initialize the packed data with the first offset, then follow up with 115f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // the condensed deltas vector. 116f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) packed->push_back(relocations[0].r_offset); 117f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) Condense(deltas, packed); 118f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 119f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Fill in the packed pair count. 120f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) packed->at(0) = (packed->size() - 2) >> 1; 121f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 122f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 1235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Decode relative relocations from a run-length encoded (packed) 124f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// representation. 1255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void RelocationRunLengthCodec::Decode(const std::vector<ELF::Xword>& packed, 1265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Rel>* relocations) { 1275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // We need at least one packed pair after the packed pair count and start 1285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // address to be able to unpack. 1295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (packed.size() < 4) 130f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return; 131f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 132f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Ensure that the packed data offers enough pairs. There may be zero 133f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // padding on it that we ignore. 134f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) CHECK(packed[0] <= (packed.size() - 2) >> 1); 135f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 136f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // The first packed vector element is the pairs count and the second the 137f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // initial address. Start uncondensing pairs at the third, and finish 138f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // at the end of the pairs data. 139f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) const size_t pairs_count = packed[0]; 1405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const ELF::Addr addr = packed[1]; 141f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) Uncondense(addr, packed, 2, 2 + (pairs_count << 1), relocations); 142f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 143f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 144f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} // namespace relocation_packer 145