• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
58 namespace 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.
63 class 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