blob: 12c21e3645627732e13b070268d227d062684c52 [file] [log] [blame]
Dmitriy Ivanov87a06172015-02-06 10:56:28 -08001// 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#include "sleb128.h"
6
7#include <limits.h>
8#include <stdint.h>
9#include <vector>
10
11#include "elf_traits.h"
12
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080013namespace {
14
15template <typename T>
16class uint_traits {};
17
18template <>
19class uint_traits<uint64_t> {
20 public:
21 typedef int64_t int_t;
22};
23
24template <>
25class uint_traits<uint32_t> {
26 public:
27 typedef int32_t int_t;
28};
29
30}
31
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080032namespace relocation_packer {
33
34// Empty constructor and destructor to silence chromium-style.
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080035template <typename uint_t>
36Sleb128Encoder<uint_t>::Sleb128Encoder() { }
37
38template <typename uint_t>
39Sleb128Encoder<uint_t>::~Sleb128Encoder() { }
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080040
41// Add a single value to the encoding. Values are encoded with variable
42// length. The least significant 7 bits of each byte hold 7 bits of data,
43// and the most significant bit is set on each byte except the last. The
44// value is sign extended up to a multiple of 7 bits (ensuring that the
45// most significant bit is zero for a positive number and one for a
46// negative number).
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080047template <typename uint_t>
48void Sleb128Encoder<uint_t>::Enqueue(uint_t value) {
49 typedef typename uint_traits<uint_t>::int_t int_t;
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080050 static const size_t size = CHAR_BIT * sizeof(value);
51
52 bool more = true;
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080053 const bool negative = static_cast<int_t>(value) < 0;
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080054
55 while (more) {
56 uint8_t byte = value & 127;
57 value >>= 7;
58
59 // Sign extend if encoding a -ve value.
60 if (negative)
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080061 value |= -(static_cast<uint_t>(1) << (size - 7));
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080062
63 // The sign bit of byte is second high order bit.
64 const bool sign_bit = byte & 64;
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080065 if ((value == 0 && !sign_bit) || (value == static_cast<uint_t>(-1) && sign_bit))
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080066 more = false;
67 else
68 byte |= 128;
69 encoding_.push_back(byte);
70 }
71}
72
73// Add a vector of values to the encoding.
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080074template <typename uint_t>
75void Sleb128Encoder<uint_t>::EnqueueAll(const std::vector<uint_t>& values) {
76 for (size_t i = 0; i < values.size(); ++i) {
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080077 Enqueue(values[i]);
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080078 }
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080079}
80
81// Create a new decoder for the given encoded stream.
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080082template <typename uint_t>
83Sleb128Decoder<uint_t>::Sleb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with) {
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080084 encoding_ = encoding;
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080085 cursor_ = start_with;
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080086}
87
88// Empty destructor to silence chromium-style.
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080089template <typename uint_t>
90Sleb128Decoder<uint_t>::~Sleb128Decoder() { }
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080091
92// Decode and retrieve a single value from the encoding. Consume bytes
93// until one without its most significant bit is found, and re-form the
94// value from the 7 bit fields of the bytes consumed.
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -080095template <typename uint_t>
96uint_t Sleb128Decoder<uint_t>::Dequeue() {
97 uint_t value = 0;
Dmitriy Ivanov87a06172015-02-06 10:56:28 -080098 static const size_t size = CHAR_BIT * sizeof(value);
99
100 size_t shift = 0;
101 uint8_t byte;
102
103 // Loop until we reach a byte with its high order bit clear.
104 do {
105 byte = encoding_[cursor_++];
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -0800106 value |= (static_cast<uint_t>(byte & 127) << shift);
Dmitriy Ivanov87a06172015-02-06 10:56:28 -0800107 shift += 7;
108 } while (byte & 128);
109
110 // The sign bit is second high order bit of the final byte decoded.
111 // Sign extend if value is -ve and we did not shift all of it.
112 if (shift < size && (byte & 64))
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -0800113 value |= -(static_cast<uint_t>(1) << shift);
Dmitriy Ivanov87a06172015-02-06 10:56:28 -0800114
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -0800115 return static_cast<uint_t>(value);
Dmitriy Ivanov87a06172015-02-06 10:56:28 -0800116}
117
118// Decode and retrieve all remaining values from the encoding.
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -0800119template <typename uint_t>
120void Sleb128Decoder<uint_t>::DequeueAll(std::vector<uint_t>* values) {
121 while (cursor_ < encoding_.size()) {
Dmitriy Ivanov87a06172015-02-06 10:56:28 -0800122 values->push_back(Dequeue());
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -0800123 }
Dmitriy Ivanov87a06172015-02-06 10:56:28 -0800124}
125
Dmitriy Ivanovf8ff6b12015-01-27 19:32:56 -0800126template class Sleb128Encoder<uint32_t>;
127template class Sleb128Encoder<uint64_t>;
128template class Sleb128Decoder<uint32_t>;
129template class Sleb128Decoder<uint64_t>;
130
Dmitriy Ivanov87a06172015-02-06 10:56:28 -0800131} // namespace relocation_packer