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