1// Copyright 2014 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5// TODO(simonb): Extend for 64-bit target libraries. 6 7#include "run_length_encoder.h" 8 9#include <string.h> 10#include <string> 11#include <vector> 12 13#include "debug.h" 14 15namespace relocation_packer { 16 17namespace { 18 19// Generate a vector of deltas between the r_offset fields of adjacent 20// R_ARM_RELATIVE relocations. 21void GetDeltas(const std::vector<Elf32_Rel>& relocations, 22 std::vector<Elf32_Addr>* deltas) { 23 CHECK(relocations.size() >= 2); 24 25 for (size_t i = 0; i < relocations.size() - 1; ++i) { 26 const Elf32_Addr first = relocations[i].r_offset; 27 const Elf32_Addr second = relocations[i + 1].r_offset; 28 // Requires that offsets are 'strictly increasing'. The packing 29 // algorithm fails if this does not hold. 30 CHECK(second > first); 31 deltas->push_back(second - first); 32 } 33} 34 35// Condense a set of r_offset deltas into a run-length encoded packing. 36// Represented as count-delta pairs, where count is the run length and 37// delta the common difference between adjacent r_offsets. 38void Condense(const std::vector<Elf32_Addr>& deltas, 39 std::vector<Elf32_Word>* packed) { 40 CHECK(!deltas.empty()); 41 size_t count = 0; 42 Elf32_Addr current = deltas[0]; 43 44 // Identify spans of identically valued deltas. 45 for (size_t i = 0; i < deltas.size(); ++i) { 46 const Elf32_Addr delta = deltas[i]; 47 if (delta == current) { 48 count++; 49 } else { 50 // We reached the end of a span of identically valued deltas. 51 packed->push_back(count); 52 packed->push_back(current); 53 current = delta; 54 count = 1; 55 } 56 } 57 58 // Write the final span. 59 packed->push_back(count); 60 packed->push_back(current); 61} 62 63// Uncondense a set of r_offset deltas from a run-length encoded packing. 64// The initial address for uncondensing, the start index for the first 65// condensed slot in packed, and the count of pairs are provided. 66void Uncondense(Elf32_Addr addr, 67 const std::vector<Elf32_Word>& packed, 68 size_t start_index, 69 size_t end_index, 70 std::vector<Elf32_Rel>* relocations) { 71 // The first relocation is just one created from the initial address. 72 const Elf32_Rel initial = {addr, R_ARM_RELATIVE}; 73 relocations->push_back(initial); 74 75 // Read each count and delta pair, beginning at the start index and 76 // finishing at the end index. 77 for (size_t i = start_index; i < end_index; i += 2) { 78 size_t count = packed[i]; 79 const Elf32_Addr delta = packed[i + 1]; 80 CHECK(count > 0 && delta > 0); 81 82 // Generate relocations for this count and delta pair. 83 while (count) { 84 addr += delta; 85 const Elf32_Rel relocation = {addr, R_ARM_RELATIVE}; 86 relocations->push_back(relocation); 87 count--; 88 } 89 } 90} 91 92} // namespace 93 94// Encode R_ARM_RELATIVE relocations into a run-length encoded (packed) 95// representation. 96void RelocationRunLengthCodec::Encode(const std::vector<Elf32_Rel>& relocations, 97 std::vector<Elf32_Word>* packed) { 98 // If we have zero or one relocation only then there is no packing 99 // possible; a run-length encoding needs a run. 100 if (relocations.size() < 2) 101 return; 102 103 std::vector<Elf32_Addr> deltas; 104 GetDeltas(relocations, &deltas); 105 106 // Reserve space for the element count. 107 packed->push_back(0); 108 109 // Initialize the packed data with the first offset, then follow up with 110 // the condensed deltas vector. 111 packed->push_back(relocations[0].r_offset); 112 Condense(deltas, packed); 113 114 // Fill in the packed pair count. 115 packed->at(0) = (packed->size() - 2) >> 1; 116} 117 118// Decode R_ARM_RELATIVE reloctions from a run-length encoded (packed) 119// representation. 120void RelocationRunLengthCodec::Decode(const std::vector<Elf32_Word>& packed, 121 std::vector<Elf32_Rel>* relocations) { 122 // We need at least one packed pair after the packed pair count to be 123 // able to unpack. 124 if (packed.size() < 3) 125 return; 126 127 // Ensure that the packed data offers enough pairs. There may be zero 128 // padding on it that we ignore. 129 CHECK(packed[0] <= (packed.size() - 2) >> 1); 130 131 // The first packed vector element is the pairs count and the second the 132 // initial address. Start uncondensing pairs at the third, and finish 133 // at the end of the pairs data. 134 const size_t pairs_count = packed[0]; 135 const Elf32_Addr addr = packed[1]; 136 Uncondense(addr, packed, 2, 2 + (pairs_count << 1), relocations); 137} 138 139} // namespace relocation_packer 140