1f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 2f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// found in the LICENSE file. 4f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 5f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "leb128.h" 6f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 7f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include <stdint.h> 8f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include <vector> 9f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "elf_traits.h" 115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 12f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)namespace relocation_packer { 13f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 14116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Empty constructor and destructor to silence chromium-style. 15116680a4aac90f2aa7413d9095a592090648e557Ben MurdochLeb128Encoder::Leb128Encoder() { } 16116680a4aac90f2aa7413d9095a592090648e557Ben MurdochLeb128Encoder::~Leb128Encoder() { } 17116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 18f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Add a single value to the encoding. Values are encoded with variable 19f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// length. The least significant 7 bits of each byte hold 7 bits of data, 20f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// and the most significant bit is set on each byte except the last. 215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Leb128Encoder::Enqueue(ELF::Xword value) { 225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) do { 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const uint8_t byte = value & 127; 24f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) value >>= 7; 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) encoding_.push_back((value ? 128 : 0) | byte); 265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } while (value); 27f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 28f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 29f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Add a vector of values to the encoding. 305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Leb128Encoder::EnqueueAll(const std::vector<ELF::Xword>& values) { 31f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) for (size_t i = 0; i < values.size(); ++i) 32f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) Enqueue(values[i]); 33f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 34f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 35116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Create a new decoder for the given encoded stream. 36116680a4aac90f2aa7413d9095a592090648e557Ben MurdochLeb128Decoder::Leb128Decoder(const std::vector<uint8_t>& encoding) { 37116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch encoding_ = encoding; 38116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch cursor_ = 0; 39116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 40116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 41116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Empty destructor to silence chromium-style. 42116680a4aac90f2aa7413d9095a592090648e557Ben MurdochLeb128Decoder::~Leb128Decoder() { } 43116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 44f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Decode and retrieve a single value from the encoding. Read forwards until 45f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// a byte without its most significant bit is found, then read the 7 bit 46f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// fields of the bytes spanned to re-form the value. 475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)ELF::Xword Leb128Decoder::Dequeue() { 485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ELF::Xword value = 0; 495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) size_t shift = 0; 515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) uint8_t byte; 52f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Loop until we reach a byte with its high order bit clear. 545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) do { 555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) byte = encoding_[cursor_++]; 565f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) value |= static_cast<ELF::Xword>(byte & 127) << shift; 575f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) shift += 7; 585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } while (byte & 128); 59f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 60f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) return value; 61f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 62f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 63f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)// Decode and retrieve all remaining values from the encoding. 645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Leb128Decoder::DequeueAll(std::vector<ELF::Xword>* values) { 65f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) while (cursor_ < encoding_.size()) 66f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) values->push_back(Dequeue()); 67f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} 68f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 69f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)} // namespace relocation_packer 70