tools/relocation_packer/src/run_length_encoder.cc

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