tools/relocation_packer/src/run_length_encoder.cc

// 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