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// Run-length encode and decode R_ARM_RELATIVE relocations.
6//
7// R_ARM_RELATIVE relocations are the bulk of dynamic relocations (the
8// .rel.dyn section) in libchrome<version>.so, and the ELF standard
9// representation of them is wasteful.
10//
11// A relocation is 8 bytes (16 bytes on 64 bit plaforms), split into offset
12// and info fields.  Offsets strictly increase, and each is commonly a
13// few bytes different from its predecessor.  There are long runs where
14// the difference does not change.  The info field is always 0x17.  Example,
15// from 'readelf -x4 libchrome.<version>.so':
16//
17//   offset   info     offset   info
18//   808fef01 17000000 848fef01 17000000 ................
19//   888fef01 17000000 8c8fef01 17000000 ................
20//   908fef01 17000000 948fef01 17000000 ................
21//
22// Run length encoding packs this data more efficiently, by representing it
23// as a delta and a count of entries each differing from its predecessor
24// by this delta.  The above can be represented as a start address followed
25// by an encoded count of 6 and offset difference of 4:
26//
27//   start    count    diff
28//   808fef01 00000006 00000004
29//
30// Because R_ARM_RELATIVE relocation offsets strictly increase, the complete
31// set of R_ARM_RELATIVE relocations in libchrome.<version>.so can be
32// represented by a single start address followed by one or more difference
33// and count encoded word pairs:
34//
35//   start    run1 count run1 diff  run2 count run2 diff
36//   808fef01 00000006   00000004   00000010   00000008 ...
37//
38// Decoding regenerates R_ARM_RELATIVE relocations beginning at address
39// 'start' and for each encoded run, incrementing the address by 'difference'
40// for 'count' iterations and emitting a new R_ARM_RELATIVE relocation.
41//
42// Once encoded, data is prefixed by a single word count of packed delta and
43// count pairs.  A final run-length encoded R_ARM_RELATIVE relocations vector
44// might therefore look something like:
45//
46//   pairs    start    run 1             run 2             ... run 15
47//   0000000f 808fef01 00000006 00000004 00000010 00000008 ...
48// Interpreted as:
49//   pairs=15 start=.. count=6,delta=4   count=16,delta=8
50
51#ifndef TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_
52#define TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_
53
54#include <stdint.h>
55#include <string.h>
56#include <vector>
57
58#include "elf.h"
59
60namespace relocation_packer {
61
62// A RelocationRunLengthCodec packs vectors of R_ARM_RELATIVE relocations
63// into more compact forms, and unpacks them to reproduce the pre-packed data.
64class RelocationRunLengthCodec {
65 public:
66  // Encode R_ARM_RELATIVE relocations into a more compact form.
67  // |relocations| is a vector of R_ARM_RELATIVE relocation structs.
68  // |packed| is the vector of packed words into which relocations are packed.
69  static void Encode(const std::vector<Elf32_Rel>& relocations,
70                     std::vector<Elf32_Word>* packed);
71
72  // Decode R_ARM_RELATIVE relocations from their more compact form.
73  // |packed| is the vector of packed relocations.
74  // |relocations| is a vector of unpacked R_ARM_RELATIVE relocation structs.
75  static void Decode(const std::vector<Elf32_Word>& packed,
76                     std::vector<Elf32_Rel>* relocations);
77};
78
79}  // namespace relocation_packer
80
81#endif  // TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_
82