Home | History | Annotate | Download | only in src 
      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
    145