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 #include "sleb128.h"
6 
7 #include <limits.h>
8 #include <stdint.h>
9 #include <vector>
10 
11 #include "elf_traits.h"
12 
13 namespace {
14 
15 template <typename T>
16 class uint_traits {};
17 
18 template <>
19 class uint_traits<uint64_t> {
20  public:
21   typedef int64_t int_t;
22 };
23 
24 template <>
25 class uint_traits<uint32_t> {
26  public:
27   typedef int32_t int_t;
28 };
29 
30 }
31 
32 namespace relocation_packer {
33 
34 // Empty constructor and destructor to silence chromium-style.
35 template <typename uint_t>
Sleb128Encoder()36 Sleb128Encoder<uint_t>::Sleb128Encoder() { }
37 
38 template <typename uint_t>
~Sleb128Encoder()39 Sleb128Encoder<uint_t>::~Sleb128Encoder() { }
40 
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).
47 template <typename uint_t>
Enqueue(uint_t value)48 void Sleb128Encoder<uint_t>::Enqueue(uint_t value) {
49   typedef typename uint_traits<uint_t>::int_t int_t;
50   static const size_t size = CHAR_BIT * sizeof(value);
51 
52   bool more = true;
53   const bool negative = static_cast<int_t>(value) < 0;
54 
55   while (more) {
56     uint8_t byte = value & 127;
57     value >>= 7;
58 
59     // Sign extend if encoding a -ve value.
60     if (negative)
61       value |= -(static_cast<uint_t>(1) << (size - 7));
62 
63     // The sign bit of byte is second high order bit.
64     const bool sign_bit = byte & 64;
65     if ((value == 0 && !sign_bit) || (value == static_cast<uint_t>(-1) && sign_bit))
66       more = false;
67     else
68       byte |= 128;
69     encoding_.push_back(byte);
70   }
71 }
72 
73 // Add a vector of values to the encoding.
74 template <typename uint_t>
EnqueueAll(const std::vector<uint_t> & values)75 void Sleb128Encoder<uint_t>::EnqueueAll(const std::vector<uint_t>& values) {
76   for (size_t i = 0; i < values.size(); ++i) {
77     Enqueue(values[i]);
78   }
79 }
80 
81 // Create a new decoder for the given encoded stream.
82 template <typename uint_t>
Sleb128Decoder(const std::vector<uint8_t> & encoding,size_t start_with)83 Sleb128Decoder<uint_t>::Sleb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with) {
84   encoding_ = encoding;
85   cursor_ = start_with;
86 }
87 
88 // Empty destructor to silence chromium-style.
89 template <typename uint_t>
~Sleb128Decoder()90 Sleb128Decoder<uint_t>::~Sleb128Decoder() { }
91 
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.
95 template <typename uint_t>
Dequeue()96 uint_t Sleb128Decoder<uint_t>::Dequeue() {
97   uint_t value = 0;
98   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_++];
106     value |= (static_cast<uint_t>(byte & 127) << shift);
107     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))
113     value |= -(static_cast<uint_t>(1) << shift);
114 
115   return static_cast<uint_t>(value);
116 }
117 
118 // Decode and retrieve all remaining values from the encoding.
119 template <typename uint_t>
DequeueAll(std::vector<uint_t> * values)120 void Sleb128Decoder<uint_t>::DequeueAll(std::vector<uint_t>* values) {
121   while (cursor_ < encoding_.size()) {
122     values->push_back(Dequeue());
123   }
124 }
125 
126 template class Sleb128Encoder<uint32_t>;
127 template class Sleb128Encoder<uint64_t>;
128 template class Sleb128Decoder<uint32_t>;
129 template class Sleb128Decoder<uint64_t>;
130 
131 }  // namespace relocation_packer
132