15f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 25f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// found in the LICENSE file. 45f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 55f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Delta encode and decode relative relocations with addends. 65f1c94371a64b3196d4be9466099bb892df9b88eTorne (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. 115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// A relocation with an addend is 12 bytes on 32 bit platforms and 24 bytes 135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// on 64 bit plaforms. It is split into offset, info, and addend fields. 145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Offsets strictly increase, and each is commonly a few bytes different 155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// from its predecessor. Addends are less well behaved. The info field is 165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// constant. Example, from 'readelf -x4 libchrome.<version>.so' 64 bit: 175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// offset info 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 80949303 00000000 03040000 00000000 ................ 205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// addend offset 215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// fc015b00 00000000 88949303 00000000 ..[............. 225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// info addend 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 03040000 00000000 24025b00 00000000 ........$.[..... 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// offset info 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 90949303 00000000 03040000 00000000 ................ 265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// addend offset 275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 3c025b00 00000000 98949303 00000000 <.[............. 285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// info addend 295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 03040000 00000000 50025b00 00000000 ........P.[..... 305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// The offset strictly increases, but the addend is unpredictable, so run 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// length encoding will not work well with this data. We can however pack 335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// with delta encoding. The upper four bytes of the eight byte offset and 345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// addend are invariably zeroes. The difference between adjacent offsets 355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// is almost always small, and between adjacent addends is often small. And 365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// info is constant and can be eliminated. 375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Delta encoding reduces the size of the data modestly, so that the first 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// three relocations above can be represented as: 405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// initial offset initial addend offset delta addend delta 425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 00000000 03939480 00000000 005b01fc 00000000 00000008 00000000 00000028 435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// offset delta addend delta ... 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 00000000 00000008 00000000 0000009f 455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// The addend delta can be negative as well as positive, but overall the 475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// deltas have a much smaller range than the input data. When encoded as 485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// signed LEB128 the total data reduction becomes useful. 495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#ifndef TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_ 515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#define TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_ 525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <vector> 545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "elf.h" 565f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "elf_traits.h" 575f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)namespace relocation_packer { 595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// A RelocationDeltaCodec packs vectors of relative relocations with 615f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// addends into more compact forms, and unpacks them to reproduce the 625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// pre-packed data. 635f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)class RelocationDeltaCodec { 645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) public: 655f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Encode relative relocations with addends into a more compact form. 665f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // |relocations| is a vector of relative relocation with addend structs. 675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // |packed| is the vector of packed words into which relocations are packed. 685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) static void Encode(const std::vector<ELF::Rela>& relocations, 695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Sxword>* packed); 705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Decode relative relocations with addends from their more compact form. 725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // |packed| is the vector of packed relocations. 735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // |relocations| is a vector of unpacked relative relocations. 745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) static void Decode(const std::vector<ELF::Sxword>& packed, 755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) std::vector<ELF::Rela>* relocations); 765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)}; 775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} // namespace relocation_packer 795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#endif // TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_ 81