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