| // 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 |