1f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 2f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// found in the LICENSE file. 4f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 55f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Run-length encode and decode relative relocations. 6f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 75f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Relative relocations are the bulk of dynamic relocations (the 85f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// .rel.dyn or .rela.dyn sections) in libchrome<version>.so, and the ELF 95f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// standard representation of them is wasteful. .rel.dyn contains 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// relocations without addends, .rela.dyn relocations with addends. 11f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// A relocation with no addend is 8 bytes on 32 bit platforms and 16 bytes 135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// on 64 bit plaforms, split into offset and info fields. Offsets strictly 145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// increase, and each is commonly a few bytes different from its predecessor. 155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// There are long runs where the difference does not change. The info field 165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// is constant. Example, from 'readelf -x4 libchrome.<version>.so' 32 bit: 17f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 18f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// offset info offset info 19f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 808fef01 17000000 848fef01 17000000 ................ 20f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 888fef01 17000000 8c8fef01 17000000 ................ 21f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 908fef01 17000000 948fef01 17000000 ................ 22f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 23f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Run length encoding packs this data more efficiently, by representing it 24f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// as a delta and a count of entries each differing from its predecessor 25f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// by this delta. The above can be represented as a start address followed 26f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// by an encoded count of 6 and offset difference of 4: 27f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 28f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// start count diff 295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 01ef8f80 00000006 00000004 30f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Because relative relocation offsets strictly increase, the complete 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// set of relative relocations in libchrome.<version>.so can be 33f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// represented by a single start address followed by one or more difference 34f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// and count encoded word pairs: 35f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 36f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// start run1 count run1 diff run2 count run2 diff 375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 01ef8f80 00000006 00000004 00000010 00000008 ... 38f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Decoding regenerates relative relocations beginning at address 40f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 'start' and for each encoded run, incrementing the address by 'difference' 415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// for 'count' iterations and emitting a new relative relocation. 42f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 43f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Once encoded, data is prefixed by a single word count of packed delta and 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// count pairs. A final run-length encoded relative relocations vector 45f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// might therefore look something like: 46f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// 47f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// pairs start run 1 run 2 ... run 15 485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 0000000f 01ef8f80 00000006 00000004 00000010 00000008 ... 49f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Interpreted as: 50f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// pairs=15 start=.. count=6,delta=4 count=16,delta=8 51f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 52f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#ifndef TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_ 53f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#define TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_ 54f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 55f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include <vector> 56f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 57f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "elf.h" 585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "elf_traits.h" 59f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 60f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)namespace relocation_packer { 61f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// A RelocationRunLengthCodec packs vectors of relative relocations 63f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// into more compact forms, and unpacks them to reproduce the pre-packed data. 64f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)class RelocationRunLengthCodec { 65f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) public: 665f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Encode relative relocations into a more compact form. 675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // |relocations| is a vector of relative relocation structs. 68f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // |packed| is the vector of packed words into which relocations are packed. 695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) static void Encode(const std::vector<ELF::Rel>& relocations, 705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Xword>* packed); 71f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Decode relative relocations from their more compact form. 73f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // |packed| is the vector of packed relocations. 745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // |relocations| is a vector of unpacked relative relocation structs. 755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) static void Decode(const std::vector<ELF::Xword>& packed, 765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Rel>* relocations); 77f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)}; 78f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 79f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} // namespace relocation_packer 80f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 81f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#endif // TOOLS_RELOCATION_PACKER_SRC_RUN_LENGTH_ENCODER_H_ 82