15f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 25f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// found in the LICENSE file. 45f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 55f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "sleb128.h" 65f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 75f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <limits.h> 85f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <stdint.h> 95f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <vector> 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include "elf_traits.h" 125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)namespace relocation_packer { 145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Empty constructor and destructor to silence chromium-style. 165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)Sleb128Encoder::Sleb128Encoder() { } 175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)Sleb128Encoder::~Sleb128Encoder() { } 185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Add a single value to the encoding. Values are encoded with variable 205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// length. The least significant 7 bits of each byte hold 7 bits of data, 215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// and the most significant bit is set on each byte except the last. The 225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// value is sign extended up to a multiple of 7 bits (ensuring that the 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// most significant bit is zero for a positive number and one for a 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// negative number). 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Sleb128Encoder::Enqueue(ELF::Sxword value) { 265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) static const size_t size = CHAR_BIT * sizeof(value); 275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) bool more = true; 295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const bool negative = value < 0; 305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while (more) { 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) uint8_t byte = value & 127; 335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) value >>= 7; 345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Sign extend if encoding a -ve value. 365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (negative) 375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) value |= -(static_cast<ELF::Sxword>(1) << (size - 7)); 385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // The sign bit of byte is second high order bit. 405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const bool sign_bit = byte & 64; 415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if ((value == 0 && !sign_bit) || (value == -1 && sign_bit)) 425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) more = false; 435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) else 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) byte |= 128; 455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) encoding_.push_back(byte); 465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Add a vector of values to the encoding. 505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Sleb128Encoder::EnqueueAll(const std::vector<ELF::Sxword>& values) { 515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for (size_t i = 0; i < values.size(); ++i) 525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) Enqueue(values[i]); 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Create a new decoder for the given encoded stream. 565f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)Sleb128Decoder::Sleb128Decoder(const std::vector<uint8_t>& encoding) { 575f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) encoding_ = encoding; 585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) cursor_ = 0; 595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 615f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Empty destructor to silence chromium-style. 625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)Sleb128Decoder::~Sleb128Decoder() { } 635f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Decode and retrieve a single value from the encoding. Consume bytes 655f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// until one without its most significant bit is found, and re-form the 665f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// value from the 7 bit fields of the bytes consumed. 675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)ELF::Sxword Sleb128Decoder::Dequeue() { 685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ELF::Sxword value = 0; 695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) static const size_t size = CHAR_BIT * sizeof(value); 705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) size_t shift = 0; 725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) uint8_t byte; 735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Loop until we reach a byte with its high order bit clear. 755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) do { 765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) byte = encoding_[cursor_++]; 775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) value |= (static_cast<ELF::Sxword>(byte & 127) << shift); 785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) shift += 7; 795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } while (byte & 128); 805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 815f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // The sign bit is second high order bit of the final byte decoded. 825f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // Sign extend if value is -ve and we did not shift all of it. 835f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if (shift < size && (byte & 64)) 845f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) value |= -(static_cast<ELF::Sxword>(1) << shift); 855f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 865f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return value; 875f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 885f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 895f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Decode and retrieve all remaining values from the encoding. 905f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)void Sleb128Decoder::DequeueAll(std::vector<ELF::Sxword>* values) { 915f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while (cursor_ < encoding_.size()) 925f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) values->push_back(Dequeue()); 935f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 945f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 955f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} // namespace relocation_packer 96