Index: tools/relocation_packer/src/relocation_packer_rle.cc |
diff --git a/tools/relocation_packer/src/relocation_packer_rle.cc b/tools/relocation_packer/src/relocation_packer_rle.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..49a246bead87900021b12d04d74c8254c71ff853 |
--- /dev/null |
+++ b/tools/relocation_packer/src/relocation_packer_rle.cc |
@@ -0,0 +1,136 @@ |
+// Copyright 2014 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+// TODO(simonb): Extend for 64-bit target libraries. |
+ |
+#include "relocation_packer_rle.h" |
+ |
+#include <string.h> |
+#include <string> |
+#include <vector> |
+ |
+#include "relocation_packer_debug.h" |
+ |
+namespace relocation_packer { |
+ |
+namespace { |
+ |
+// Generate a vector of deltas between the r_offset fields of adjacent |
+// R_ARM_RELATIVE relocations. |
+void GetDeltas(const std::vector<Elf32_Rel>& relocations, |
+ std::vector<Elf32_Addr>* deltas) { |
+ CHECK(relocations.size() >= 2); |
+ |
+ for (size_t i = 0; i < relocations.size() - 1; ++i) { |
+ const Elf32_Addr first = relocations[i].r_offset; |
+ const Elf32_Addr second = relocations[i + 1].r_offset; |
+ // Requires that offsets are 'strictly increasing'. The packing |
+ // algorithm fails if this does not hold. |
+ CHECK(second > first); |
+ deltas->push_back(second - first); |
+ } |
+} |
+ |
+// Condense a set of r_offset deltas into a run-length encoded packing. |
+// Represented as count-delta pairs, where count is the run length and |
+// delta the common difference between adjacent r_offsets. |
+void Condense(const std::vector<Elf32_Addr>& deltas, |
+ std::vector<Elf32_Word>* packed) { |
+ CHECK(!deltas.empty()); |
+ size_t count = 0; |
+ Elf32_Addr current = deltas[0]; |
+ |
+ // Identify spans of identically valued deltas. |
+ for (size_t i = 0; i < deltas.size(); ++i) { |
+ const Elf32_Addr delta = deltas[i]; |
+ if (delta == current) { |
+ count++; |
+ } else { |
+ // We reached the end of a span of identically valued deltas. |
+ packed->push_back(count); |
+ packed->push_back(current); |
+ current = delta; |
+ count = 1; |
+ } |
+ } |
+ |
+ // Write the final span. |
+ packed->push_back(count); |
+ packed->push_back(current); |
+} |
+ |
+// Uncondense a set of r_offset deltas from a run-length encoded packing. |
+// The initial address for uncondensing, the start index for the first |
+// condensed slot in packed, and the count of pairs are provided. |
+void Uncondense(Elf32_Addr addr, |
+ const std::vector<Elf32_Word>& packed, |
+ size_t start, |
rmcilroy
2014/06/02 15:16:35
nit - start_idx (I got confused between the "initi
simonb (inactive)
2014/06/04 16:40:35
Switched to receiving start_index and end_index, d
|
+ size_t pairs_count, |
+ std::vector<Elf32_Rel>* relocations) { |
+ // The first relocation is just one created from the initial address. |
+ const Elf32_Rel initial = {addr, R_ARM_RELATIVE}; |
+ relocations->push_back(initial); |
+ |
+ // Read each count and delta pair, beginning at the start index. |
+ for (size_t i = start; i < start + (pairs_count << 1); i += 2) { |
rmcilroy
2014/06/02 15:16:35
nit - might be clearer if you pass (pairs_count <<
simonb (inactive)
2014/06/04 16:40:35
See above.
|
+ size_t count = packed[i]; |
+ const Elf32_Addr delta = packed[i + 1]; |
+ CHECK(count > 0 && delta > 0); |
+ |
+ while (count) { |
+ addr += delta; |
+ const Elf32_Rel relocation = {addr, R_ARM_RELATIVE}; |
+ relocations->push_back(relocation); |
+ count--; |
+ } |
+ } |
+} |
+ |
+} // namespace |
+ |
+// Encode R_ARM_RELATIVE relocations into a run-length encoded (packed) |
+// representation. |
+void RelocationRunLengthCodec::Encode(const std::vector<Elf32_Rel>& relocations, |
+ std::vector<Elf32_Word>* packed) { |
+ // If we have zero or one relocation only then there is no packing |
+ // possible; a run-length encoding needs a run. |
+ if (relocations.size() < 2) |
+ return; |
+ |
+ std::vector<Elf32_Addr> deltas; |
+ GetDeltas(relocations, &deltas); |
+ |
+ // Reserve space for the element count. |
+ packed->push_back(0); |
+ |
+ // Initialize the packed data with the first offset, then follow up with |
+ // the condensed deltas vector. |
+ packed->push_back(relocations[0].r_offset); |
+ Condense(deltas, packed); |
+ |
+ // Fill in the packed pair count. |
+ packed->at(0) = (packed->size() - 1) >> 1; |
+} |
+ |
+// Decode R_ARM_RELATIVE reloctions from a run-length encoded (packed) |
+// representation. |
+void RelocationRunLengthCodec::Decode(const std::vector<Elf32_Word>& packed, |
+ std::vector<Elf32_Rel>* relocations) { |
+ // We need at least one packed pair after the packed pair count to be |
+ // able to unpack. |
+ if (packed.size() < 3) |
+ return; |
+ |
+ // Ensure that the packed data offers enough pairs. There may be zero |
+ // padding on it that we ignore. |
+ CHECK(packed[0] <= (packed.size() - 1) >> 1); |
+ |
+ // The first packed vector element is the initial address, and we start |
+ // uncondensing at the second. |
+ const size_t pairs_count = packed[0]; |
+ const Elf32_Addr addr = packed[1]; |
+ Uncondense(addr, packed, 2, pairs_count, relocations); |
+} |
+ |
+} // namespace relocation_packer |