tools/relocation_packer/src/delta_encoder.h

   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_