third_party/android_platform/bionic/tools/relocation_packer/src/sleb128.cc

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