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()36Sleb128Encoder<uint_t>::Sleb128Encoder() { } 37 38 template <typename uint_t> ~Sleb128Encoder()39Sleb128Encoder<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)48void 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)75void 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)83Sleb128Decoder<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()90Sleb128Decoder<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()96uint_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)120void 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