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 relocation_packer {
  14
  15 // Empty constructor and destructor to silence chromium-style.
  16 Sleb128Encoder::Sleb128Encoder() { }
  17 Sleb128Encoder::~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).
  25 void 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.
  50 void 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.
  56 Sleb128Decoder::Sleb128Decoder(const std::vector<uint8_t>& encoding) {
  57   encoding_ = encoding;
  58   cursor_ = 0;
  59 }
  60
  61 // Empty destructor to silence chromium-style.
  62 Sleb128Decoder::~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.
  67 ELF::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.
  90 void Sleb128Decoder::DequeueAll(std::vector<ELF::Sxword>* values) {
  91   while (cursor_ < encoding_.size())
  92     values->push_back(Dequeue());
  93 }
  94
  95 }  // namespace relocation_packer