OLD | NEW |
(Empty) | |
| 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 |
| 15 namespace relocation_packer { |
| 16 |
| 17 namespace { |
| 18 |
| 19 // Generate a vector of deltas between the r_offset fields of adjacent |
| 20 // R_ARM_RELATIVE relocations. |
| 21 void 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. |
| 38 void 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. |
| 66 void 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. |
| 96 void 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. |
| 120 void 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 |
OLD | NEW |