sleb128.cc revision 5f1c94371a64b3196d4be9466099bb892df9b88e 
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
13namespace relocation_packer {
14
15// Empty constructor and destructor to silence chromium-style.
16Sleb128Encoder::Sleb128Encoder() { }
17Sleb128Encoder::~Sleb128Encoder() { }
18
19// Add a single value to the encoding.  Values are encoded with variable
20// length.  The least significant 7 bits of each byte hold 7 bits of data,
21// and the most significant bit is set on each byte except the last.  The
22// value is sign extended up to a multiple of 7 bits (ensuring that the
23// most significant bit is zero for a positive number and one for a
24// negative number).
25void Sleb128Encoder::Enqueue(ELF::Sxword value) {
26  static const size_t size = CHAR_BIT * sizeof(value);
27
28  bool more = true;
29  const bool negative = value < 0;
30
31  while (more) {
32    uint8_t byte = value & 127;
33    value >>= 7;
34
35    // Sign extend if encoding a -ve value.
36    if (negative)
37      value |= -(static_cast<ELF::Sxword>(1) << (size - 7));
38
39    // The sign bit of byte is second high order bit.
40    const bool sign_bit = byte & 64;
41    if ((value == 0 && !sign_bit) || (value == -1 && sign_bit))
42      more = false;
43    else
44      byte |= 128;
45    encoding_.push_back(byte);
46  }
47}
48
49// Add a vector of values to the encoding.
50void Sleb128Encoder::EnqueueAll(const std::vector<ELF::Sxword>& values) {
51  for (size_t i = 0; i < values.size(); ++i)
52    Enqueue(values[i]);
53}
54
55// Create a new decoder for the given encoded stream.
56Sleb128Decoder::Sleb128Decoder(const std::vector<uint8_t>& encoding) {
57  encoding_ = encoding;
58  cursor_ = 0;
59}
60
61// Empty destructor to silence chromium-style.
62Sleb128Decoder::~Sleb128Decoder() { }
63
64// Decode and retrieve a single value from the encoding.  Consume bytes
65// until one without its most significant bit is found, and re-form the
66// value from the 7 bit fields of the bytes consumed.
67ELF::Sxword Sleb128Decoder::Dequeue() {
68  ELF::Sxword value = 0;
69  static const size_t size = CHAR_BIT * sizeof(value);
70
71  size_t shift = 0;
72  uint8_t byte;
73
74  // Loop until we reach a byte with its high order bit clear.
75  do {
76    byte = encoding_[cursor_++];
77    value |= (static_cast<ELF::Sxword>(byte & 127) << shift);
78    shift += 7;
79  } while (byte & 128);
80
81  // The sign bit is second high order bit of the final byte decoded.
82  // Sign extend if value is -ve and we did not shift all of it.
83  if (shift < size && (byte & 64))
84    value |= -(static_cast<ELF::Sxword>(1) << shift);
85
86  return value;
87}
88
89// Decode and retrieve all remaining values from the encoding.
90void Sleb128Decoder::DequeueAll(std::vector<ELF::Sxword>* values) {
91  while (cursor_ < encoding_.size())
92    values->push_back(Dequeue());
93}
94
95}  // namespace relocation_packer
96