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// Delta encode and decode relative relocations with addends.
6//
7// Relative relocations are the bulk of dynamic relocations (the
8// .rel.dyn or .rela.dyn sections) in libchrome<version>.so, and the ELF
9// standard representation of them is wasteful.  .rel.dyn contains
10// relocations without addends, .rela.dyn relocations with addends.
11//
12// A relocation with an addend is 12 bytes on 32 bit platforms and 24 bytes
13// on 64 bit plaforms.  It is split into offset, info, and addend fields.
14// Offsets strictly increase, and each is commonly a few bytes different
15// from its predecessor.  Addends are less well behaved.  The info field is
16// constant.  Example, from 'readelf -x4 libchrome.<version>.so' 64 bit:
17//
18//   offset            info
19//   80949303 00000000 03040000 00000000 ................
20//   addend            offset
21//   fc015b00 00000000 88949303 00000000 ..[.............
22//   info              addend
23//   03040000 00000000 24025b00 00000000 ........$.[.....
24//   offset            info
25//   90949303 00000000 03040000 00000000 ................
26//   addend            offset
27//   3c025b00 00000000 98949303 00000000 <.[.............
28//   info              addend
29//   03040000 00000000 50025b00 00000000 ........P.[.....
30//
31// The offset strictly increases, but the addend is unpredictable, so run
32// length encoding will not work well with this data.  We can however pack
33// with delta encoding.  The upper four bytes of the eight byte offset and
34// addend are invariably zeroes.  The difference between adjacent offsets
35// is almost always small, and between adjacent addends is often small.  And
36// info is constant and can be eliminated.
37//
38// Delta encoding reduces the size of the data modestly, so that the first
39// three relocations above can be represented as:
40//
41// initial offset    initial addend    offset delta      addend delta
42// 00000000 03939480 00000000 005b01fc 00000000 00000008 00000000 00000028
43// offset delta      addend delta      ...
44// 00000000 00000008 00000000 0000009f
45//
46// The addend delta can be negative as well as positive, but overall the
47// deltas have a much smaller range than the input data.  When encoded as
48// signed LEB128 the total data reduction becomes useful.
49
50#ifndef TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_
51#define TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_
52
53#include <vector>
54
55#include "elf.h"
56#include "elf_traits.h"
57
58namespace relocation_packer {
59
60// A RelocationDeltaCodec packs vectors of relative relocations with
61// addends into more compact forms, and unpacks them to reproduce the
62// pre-packed data.
63class RelocationDeltaCodec {
64 public:
65  // Encode relative relocations with addends into a more compact form.
66  // |relocations| is a vector of relative relocation with addend structs.
67  // |packed| is the vector of packed words into which relocations are packed.
68  static void Encode(const std::vector<ELF::Rela>& relocations,
69                     std::vector<ELF::Sxword>* packed);
70
71  // Decode relative relocations with addends from their more compact form.
72  // |packed| is the vector of packed relocations.
73  // |relocations| is a vector of unpacked relative relocations.
74  static void Decode(const std::vector<ELF::Sxword>& packed,
75                     std::vector<ELF::Rela>* relocations);
76};
77
78}  // namespace relocation_packer
79
80#endif  // TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_
81