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