tools/relocation_packer/src/sleb128.cc

// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "sleb128.h"

#include <limits.h>
#include <stdint.h>
#include <vector>

#include "elf_traits.h"

namespace {

template <typename T>
class uint_traits {};

template <>
class uint_traits<uint64_t> {
 public:
  typedef int64_t int_t;
};

template <>
class uint_traits<uint32_t> {
 public:
  typedef int32_t int_t;
};

}

namespace relocation_packer {

// Empty constructor and destructor to silence chromium-style.
template <typename uint_t>
Sleb128Encoder<uint_t>::Sleb128Encoder() { }

template <typename uint_t>
Sleb128Encoder<uint_t>::~Sleb128Encoder() { }

// Add a single value to the encoding.  Values are encoded with variable
// length.  The least significant 7 bits of each byte hold 7 bits of data,
// and the most significant bit is set on each byte except the last.  The
// value is sign extended up to a multiple of 7 bits (ensuring that the
// most significant bit is zero for a positive number and one for a
// negative number).
template <typename uint_t>
void Sleb128Encoder<uint_t>::Enqueue(uint_t value) {
  typedef typename uint_traits<uint_t>::int_t int_t;
  static const size_t size = CHAR_BIT * sizeof(value);

  bool more = true;
  const bool negative = static_cast<int_t>(value) < 0;

  while (more) {
    uint8_t byte = value & 127;
    value >>= 7;

    // Sign extend if encoding a -ve value.
    if (negative)
      value |= -(static_cast<uint_t>(1) << (size - 7));

    // The sign bit of byte is second high order bit.
    const bool sign_bit = byte & 64;
    if ((value == 0 && !sign_bit) || (value == static_cast<uint_t>(-1) && sign_bit))
      more = false;
    else
      byte |= 128;
    encoding_.push_back(byte);
  }
}

// Add a vector of values to the encoding.
template <typename uint_t>
void Sleb128Encoder<uint_t>::EnqueueAll(const std::vector<uint_t>& values) {
  for (size_t i = 0; i < values.size(); ++i) {
    Enqueue(values[i]);
  }
}

// Create a new decoder for the given encoded stream.
template <typename uint_t>
Sleb128Decoder<uint_t>::Sleb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with) {
  encoding_ = encoding;
  cursor_ = start_with;
}

// Empty destructor to silence chromium-style.
template <typename uint_t>
Sleb128Decoder<uint_t>::~Sleb128Decoder() { }

// Decode and retrieve a single value from the encoding.  Consume bytes
// until one without its most significant bit is found, and re-form the
// value from the 7 bit fields of the bytes consumed.
template <typename uint_t>
uint_t Sleb128Decoder<uint_t>::Dequeue() {
  uint_t value = 0;
  static const size_t size = CHAR_BIT * sizeof(value);

  size_t shift = 0;
  uint8_t byte;

  // Loop until we reach a byte with its high order bit clear.
  do {
    byte = encoding_[cursor_++];
    value |= (static_cast<uint_t>(byte & 127) << shift);
    shift += 7;
  } while (byte & 128);

  // The sign bit is second high order bit of the final byte decoded.
  // Sign extend if value is -ve and we did not shift all of it.
  if (shift < size && (byte & 64))
    value |= -(static_cast<uint_t>(1) << shift);

  return static_cast<uint_t>(value);
}

// Decode and retrieve all remaining values from the encoding.
template <typename uint_t>
void Sleb128Decoder<uint_t>::DequeueAll(std::vector<uint_t>* values) {
  while (cursor_ < encoding_.size()) {
    values->push_back(Dequeue());
  }
}

template class Sleb128Encoder<uint32_t>;
template class Sleb128Encoder<uint64_t>;
template class Sleb128Decoder<uint32_t>;
template class Sleb128Decoder<uint64_t>;

}  // namespace relocation_packer