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 relocation_packer { 14 15 // Empty constructor and destructor to silence chromium-style. Sleb128Encoder()16Sleb128Encoder::Sleb128Encoder() { } ~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). Enqueue(ELF::Sxword value)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. EnqueueAll(const std::vector<ELF::Sxword> & values)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. Sleb128Decoder(const std::vector<uint8_t> & encoding)56Sleb128Decoder::Sleb128Decoder(const std::vector<uint8_t>& encoding) { 57 encoding_ = encoding; 58 cursor_ = 0; 59 } 60 61 // Empty destructor to silence chromium-style. ~Sleb128Decoder()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. Dequeue()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. DequeueAll(std::vector<ELF::Sxword> * values)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