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::kRelativeRelocationCode); |
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::kRelativeRelocationCode); |
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 |