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