Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(76)

Unified Diff: tools/relocation_packer/src/run_length_encoder.cc

Issue 670183003: Update from chromium 62675d9fb31fb8cedc40f68e78e8445a74f362e7 (Closed) Base URL: git@github.com:domokit/mojo.git@master
Patch Set: Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: tools/relocation_packer/src/run_length_encoder.cc
diff --git a/tools/relocation_packer/src/run_length_encoder.cc b/tools/relocation_packer/src/run_length_encoder.cc
new file mode 100644
index 0000000000000000000000000000000000000000..2f2e1c315f30d684e659b475a6a98b3e2ae7187c
--- /dev/null
+++ b/tools/relocation_packer/src/run_length_encoder.cc
@@ -0,0 +1,144 @@
+// 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.
+
+#include "run_length_encoder.h"
+
+#include <vector>
+
+#include "debug.h"
+#include "elf_traits.h"
+
+namespace relocation_packer {
+
+namespace {
+
+// Generate a vector of deltas between the r_offset fields of adjacent
+// relative relocations.
+void GetDeltas(const std::vector<ELF::Rel>& relocations,
+ std::vector<ELF::Addr>* deltas) {
+ CHECK(relocations.size() >= 2);
+
+ for (size_t i = 0; i < relocations.size() - 1; ++i) {
+ const ELF::Rel* first = &relocations[i];
+ CHECK(ELF_R_TYPE(first->r_info) == ELF::kRelativeRelocationCode);
+
+ const ELF::Rel* second = &relocations[i + 1];
+ CHECK(ELF_R_TYPE(second->r_info) == ELF::kRelativeRelocationCode);
+
+ // Requires that offsets are 'strictly increasing'. The packing
+ // algorithm fails if this does not hold.
+ CHECK(second->r_offset > first->r_offset);
+ deltas->push_back(second->r_offset - first->r_offset);
+ }
+}
+
+// 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<ELF::Addr>& deltas,
+ std::vector<ELF::Xword>* packed) {
+ CHECK(!deltas.empty());
+ size_t count = 0;
+ ELF::Addr current = deltas[0];
+
+ // Identify spans of identically valued deltas.
+ for (size_t i = 0; i < deltas.size(); ++i) {
+ const ELF::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(ELF::Addr addr,
+ const std::vector<ELF::Xword>& packed,
+ size_t start_index,
+ size_t end_index,
+ std::vector<ELF::Rel>* relocations) {
+ // The first relocation is just one created from the initial address.
+ ELF::Rel initial;
+ initial.r_offset = addr;
+ initial.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode);
+ relocations->push_back(initial);
+
+ // Read each count and delta pair, beginning at the start index and
+ // finishing at the end index.
+ for (size_t i = start_index; i < end_index; i += 2) {
+ size_t count = packed[i];
+ const ELF::Addr delta = packed[i + 1];
+ CHECK(count > 0 && delta > 0);
+
+ // Generate relocations for this count and delta pair.
+ while (count) {
+ addr += delta;
+ ELF::Rel relocation;
+ relocation.r_offset = addr;
+ relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode);
+ relocations->push_back(relocation);
+ count--;
+ }
+ }
+}
+
+} // namespace
+
+// Encode relative relocations into a run-length encoded (packed)
+// representation.
+void RelocationRunLengthCodec::Encode(const std::vector<ELF::Rel>& relocations,
+ std::vector<ELF::Xword>* 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<ELF::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() - 2) >> 1;
+}
+
+// Decode relative relocations from a run-length encoded (packed)
+// representation.
+void RelocationRunLengthCodec::Decode(const std::vector<ELF::Xword>& packed,
+ std::vector<ELF::Rel>* relocations) {
+ // We need at least one packed pair after the packed pair count and start
+ // address to be able to unpack.
+ if (packed.size() < 4)
+ return;
+
+ // Ensure that the packed data offers enough pairs. There may be zero
+ // padding on it that we ignore.
+ CHECK(packed[0] <= (packed.size() - 2) >> 1);
+
+ // The first packed vector element is the pairs count and the second the
+ // initial address. Start uncondensing pairs at the third, and finish
+ // at the end of the pairs data.
+ const size_t pairs_count = packed[0];
+ const ELF::Addr addr = packed[1];
+ Uncondense(addr, packed, 2, 2 + (pairs_count << 1), relocations);
+}
+
+} // namespace relocation_packer
« no previous file with comments | « tools/relocation_packer/src/run_length_encoder.h ('k') | tools/relocation_packer/src/run_length_encoder_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698