run_length_encoder.cc revision 5f1c94371a64b3196d4be9466099bb892df9b88e 
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
12namespace relocation_packer {
13
14namespace {
15
16// Generate a vector of deltas between the r_offset fields of adjacent
17// relative relocations.
18void 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.
39void 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.
67void 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.
101void 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.
125void 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