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