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)
5f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "packer.h"
6f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
7f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include <vector>
8f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
9f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "debug.h"
105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "delta_encoder.h"
115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "elf_traits.h"
12f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "leb128.h"
13f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "run_length_encoder.h"
145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "sleb128.h"
15f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
16f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)namespace relocation_packer {
17f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Pack relative relocations into a run-length encoded packed
19f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// representation.
20f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)void RelocationPacker::PackRelativeRelocations(
215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    const std::vector<ELF::Rel>& relocations,
22f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)    std::vector<uint8_t>* packed) {
23f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // Run-length encode.
245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  std::vector<ELF::Xword> packed_words;
25f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  RelocationRunLengthCodec codec;
26f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  codec.Encode(relocations, &packed_words);
27f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
28f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // If insufficient data to run-length encode, do nothing.
29f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  if (packed_words.empty())
30f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)    return;
31f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
32f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // LEB128 encode, with "APR1" prefix.
33f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  Leb128Encoder encoder;
34f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  encoder.Enqueue('A');
35f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  encoder.Enqueue('P');
36f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  encoder.Enqueue('R');
37f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  encoder.Enqueue('1');
38f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  encoder.EnqueueAll(packed_words);
39f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
40f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  encoder.GetEncoding(packed);
41f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
42f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // Pad packed to a whole number of words.  This padding will decode as
43f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // LEB128 zeroes.  Run-length decoding ignores it because encoding
44f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // embeds the pairs count in the stream itself.
455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  while (packed->size() % sizeof(ELF::Word))
46f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)    packed->push_back(0);
47f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)}
48f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Unpack relative relocations from a run-length encoded packed
50f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// representation.
51f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)void RelocationPacker::UnpackRelativeRelocations(
52f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)    const std::vector<uint8_t>& packed,
535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    std::vector<ELF::Rel>* relocations) {
54f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // LEB128 decode, after checking and stripping "APR1" prefix.
555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  std::vector<ELF::Xword> packed_words;
56f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  Leb128Decoder decoder(packed);
575f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  CHECK(decoder.Dequeue() == 'A' &&
585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)        decoder.Dequeue() == 'P' &&
595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)        decoder.Dequeue() == 'R' &&
605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)        decoder.Dequeue() == '1');
61f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  decoder.DequeueAll(&packed_words);
62f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
63f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  // Run-length decode.
64f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  RelocationRunLengthCodec codec;
65f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)  codec.Decode(packed_words, relocations);
66f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)}
67f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)
685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Pack relative relocations with addends into a delta encoded packed
695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// representation.
705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void RelocationPacker::PackRelativeRelocations(
715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    const std::vector<ELF::Rela>& relocations,
725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    std::vector<uint8_t>* packed) {
735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // Delta encode.
745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  std::vector<ELF::Sxword> packed_words;
755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  RelocationDeltaCodec codec;
765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  codec.Encode(relocations, &packed_words);
775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // If insufficient data to delta encode, do nothing.
795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  if (packed_words.empty())
805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    return;
815f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
825f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // Signed LEB128 encode, with "APA1" prefix.  ASCII does not encode as
835f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // itself under signed LEB128, so we have to treat it specially.
845f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  Sleb128Encoder encoder;
855f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  encoder.EnqueueAll(packed_words);
865f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  std::vector<uint8_t> encoded;
875f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  encoder.GetEncoding(&encoded);
885f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
895f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  packed->push_back('A');
905f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  packed->push_back('P');
915f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  packed->push_back('A');
925f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  packed->push_back('1');
935f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  packed->insert(packed->end(), encoded.begin(), encoded.end());
945f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
955f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // Pad packed to a whole number of words.  This padding will decode as
965f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // signed LEB128 zeroes.  Delta decoding ignores it because encoding
975f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // embeds the pairs count in the stream itself.
985f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  while (packed->size() % sizeof(ELF::Word))
995f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    packed->push_back(0);
1005f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)}
1015f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
1025f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Unpack relative relocations with addends from a delta encoded
1035f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// packed representation.
1045f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void RelocationPacker::UnpackRelativeRelocations(
1055f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    const std::vector<uint8_t>& packed,
1065f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)    std::vector<ELF::Rela>* relocations) {
1075f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // Check "APA1" prefix.
1085f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  CHECK(packed.at(0) == 'A' &&
1095f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)        packed.at(1) == 'P' &&
1105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)        packed.at(2) == 'A' &&
1115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)        packed.at(3) == '1');
1125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
1135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // Signed LEB128 decode, after stripping "APA1" prefix.
1145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  std::vector<ELF::Sxword> packed_words;
1155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  std::vector<uint8_t> stripped(packed.begin() + 4, packed.end());
1165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  Sleb128Decoder decoder(stripped);
1175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  decoder.DequeueAll(&packed_words);
1185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
1195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  // Delta decode.
1205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  RelocationDeltaCodec codec;
1215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)  codec.Decode(packed_words, relocations);
1225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)}
1235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)
124f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)}  // namespace relocation_packer
125