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_ 82