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 60namespace 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. 64class 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