Revision control
Copy as Markdown
Other Tools
//! Read and write DWARF's "Little Endian Base 128" (LEB128) variable length
//! integer encoding.
//!
//! The implementation is a direct translation of the psuedocode in the DWARF 4
//! standard's appendix C.
//!
//! Read and write signed integers:
//!
//! ```
//! use leb128;
//!
//! let mut buf = [0; 1024];
//!
//! // Write to anything that implements `std::io::Write`.
//! {
//! let mut writable = &mut buf[..];
//! leb128::write::signed(&mut writable, -12345).expect("Should write number");
//! }
//!
//! // Read from anything that implements `std::io::Read`.
//! let mut readable = &buf[..];
//! let val = leb128::read::signed(&mut readable).expect("Should read number");
//! assert_eq!(val, -12345);
//! ```
//!
//! Or read and write unsigned integers:
//!
//! ```
//! use leb128;
//!
//! let mut buf = [0; 1024];
//!
//! {
//! let mut writable = &mut buf[..];
//! leb128::write::unsigned(&mut writable, 98765).expect("Should write number");
//! }
//!
//! let mut readable = &buf[..];
//! let val = leb128::read::unsigned(&mut readable).expect("Should read number");
//! assert_eq!(val, 98765);
//! ```
#![deny(missing_docs)]
#[doc(hidden)]
pub const CONTINUATION_BIT: u8 = 1 << 7;
#[doc(hidden)]
pub const SIGN_BIT: u8 = 1 << 6;
#[doc(hidden)]
#[inline]
pub fn low_bits_of_byte(byte: u8) -> u8 {
byte & !CONTINUATION_BIT
}
#[doc(hidden)]
#[inline]
pub fn low_bits_of_u64(val: u64) -> u8 {
let byte = val & (std::u8::MAX as u64);
low_bits_of_byte(byte as u8)
}
/// A module for reading LEB128-encoded signed and unsigned integers.
pub mod read {
use super::{low_bits_of_byte, CONTINUATION_BIT, SIGN_BIT};
use std::fmt;
use std::io;
/// An error type for reading LEB128-encoded values.
#[derive(Debug)]
pub enum Error {
/// There was an underlying IO error.
IoError(io::Error),
/// The number being read is larger than can be represented.
Overflow,
}
impl From<io::Error> for Error {
fn from(e: io::Error) -> Self {
Error::IoError(e)
}
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
match *self {
Error::IoError(ref e) => e.fmt(f),
Error::Overflow => {
write!(f, "The number being read is larger than can be represented")
}
}
}
}
impl std::error::Error for Error {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match *self {
Error::IoError(ref e) => Some(e),
Error::Overflow => None,
}
}
}
/// Read an unsigned LEB128-encoded number from the `std::io::Read` stream
/// `r`.
///
/// On success, return the number.
pub fn unsigned<R>(r: &mut R) -> Result<u64, Error>
where
R: ?Sized + io::Read,
{
let mut result = 0;
let mut shift = 0;
loop {
let mut buf = [0];
r.read_exact(&mut buf)?;
if shift == 63 && buf[0] != 0x00 && buf[0] != 0x01 {
while buf[0] & CONTINUATION_BIT != 0 {
r.read_exact(&mut buf)?;
}
return Err(Error::Overflow);
}
let low_bits = low_bits_of_byte(buf[0]) as u64;
result |= low_bits << shift;
if buf[0] & CONTINUATION_BIT == 0 {
return Ok(result);
}
shift += 7;
}
}
/// Read a signed LEB128-encoded number from the `std::io::Read` stream `r`.
///
/// On success, return the number.
pub fn signed<R>(r: &mut R) -> Result<i64, Error>
where
R: ?Sized + io::Read,
{
let mut result = 0;
let mut shift = 0;
let size = 64;
let mut byte;
loop {
let mut buf = [0];
r.read_exact(&mut buf)?;
byte = buf[0];
if shift == 63 && byte != 0x00 && byte != 0x7f {
while buf[0] & CONTINUATION_BIT != 0 {
r.read_exact(&mut buf)?;
}
return Err(Error::Overflow);
}
let low_bits = low_bits_of_byte(byte) as i64;
result |= low_bits << shift;
shift += 7;
if byte & CONTINUATION_BIT == 0 {
break;
}
}
if shift < size && (SIGN_BIT & byte) == SIGN_BIT {
// Sign extend the result.
result |= !0 << shift;
}
Ok(result)
}
}
/// A module for writing LEB128-encoded signed and unsigned integers.
pub mod write {
use super::{low_bits_of_u64, CONTINUATION_BIT};
use std::io;
/// Write `val` to the `std::io::Write` stream `w` as an unsigned LEB128 value.
///
/// On success, return the number of bytes written to `w`.
pub fn unsigned<W>(w: &mut W, mut val: u64) -> Result<usize, io::Error>
where
W: ?Sized + io::Write,
{
let mut bytes_written = 0;
loop {
let mut byte = low_bits_of_u64(val);
val >>= 7;
if val != 0 {
// More bytes to come, so set the continuation bit.
byte |= CONTINUATION_BIT;
}
let buf = [byte];
w.write_all(&buf)?;
bytes_written += 1;
if val == 0 {
return Ok(bytes_written);
}
}
}
/// Write `val` to the `std::io::Write` stream `w` as a signed LEB128 value.
///
/// On success, return the number of bytes written to `w`.
pub fn signed<W>(w: &mut W, mut val: i64) -> Result<usize, io::Error>
where
W: ?Sized + io::Write,
{
let mut bytes_written = 0;
loop {
let mut byte = val as u8;
// Keep the sign bit for testing
val >>= 6;
let done = val == 0 || val == -1;
if done {
byte &= !CONTINUATION_BIT;
} else {
// Remove the sign bit
val >>= 1;
// More bytes to come, so set the continuation bit.
byte |= CONTINUATION_BIT;
}
let buf = [byte];
w.write_all(&buf)?;
bytes_written += 1;
if done {
return Ok(bytes_written);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std;
use std::io;
#[test]
fn test_low_bits_of_byte() {
for i in 0..127 {
assert_eq!(i, low_bits_of_byte(i));
assert_eq!(i, low_bits_of_byte(i | CONTINUATION_BIT));
}
}
#[test]
fn test_low_bits_of_u64() {
for i in 0u64..127 {
assert_eq!(i as u8, low_bits_of_u64(1 << 16 | i));
assert_eq!(
i as u8,
low_bits_of_u64(i << 16 | i | (CONTINUATION_BIT as u64))
);
}
}
// Examples from the DWARF 4 standard, section 7.6, figure 22.
#[test]
fn test_read_unsigned() {
let buf = [2u8];
let mut readable = &buf[..];
assert_eq!(
2,
read::unsigned(&mut readable).expect("Should read number")
);
let buf = [127u8];
let mut readable = &buf[..];
assert_eq!(
127,
read::unsigned(&mut readable).expect("Should read number")
);
let buf = [CONTINUATION_BIT, 1];
let mut readable = &buf[..];
assert_eq!(
128,
read::unsigned(&mut readable).expect("Should read number")
);
let buf = [1u8 | CONTINUATION_BIT, 1];
let mut readable = &buf[..];
assert_eq!(
129,
read::unsigned(&mut readable).expect("Should read number")
);
let buf = [2u8 | CONTINUATION_BIT, 1];
let mut readable = &buf[..];
assert_eq!(
130,
read::unsigned(&mut readable).expect("Should read number")
);
let buf = [57u8 | CONTINUATION_BIT, 100];
let mut readable = &buf[..];
assert_eq!(
12857,
read::unsigned(&mut readable).expect("Should read number")
);
}
#[test]
fn test_read_unsigned_thru_dyn_trait() {
fn read(r: &mut dyn io::Read) -> u64 {
read::unsigned(r).expect("Should read number")
}
let buf = [0u8];
let mut readable = &buf[..];
assert_eq!(0, read(&mut readable));
let mut readable = io::Cursor::new(buf);
assert_eq!(0, read(&mut readable));
}
// Examples from the DWARF 4 standard, section 7.6, figure 23.
#[test]
fn test_read_signed() {
let buf = [2u8];
let mut readable = &buf[..];
assert_eq!(2, read::signed(&mut readable).expect("Should read number"));
let buf = [0x7eu8];
let mut readable = &buf[..];
assert_eq!(-2, read::signed(&mut readable).expect("Should read number"));
let buf = [127u8 | CONTINUATION_BIT, 0];
let mut readable = &buf[..];
assert_eq!(
127,
read::signed(&mut readable).expect("Should read number")
);
let buf = [1u8 | CONTINUATION_BIT, 0x7f];
let mut readable = &buf[..];
assert_eq!(
-127,
read::signed(&mut readable).expect("Should read number")
);
let buf = [CONTINUATION_BIT, 1];
let mut readable = &buf[..];
assert_eq!(
128,
read::signed(&mut readable).expect("Should read number")
);
let buf = [CONTINUATION_BIT, 0x7f];
let mut readable = &buf[..];
assert_eq!(
-128,
read::signed(&mut readable).expect("Should read number")
);
let buf = [1u8 | CONTINUATION_BIT, 1];
let mut readable = &buf[..];
assert_eq!(
129,
read::signed(&mut readable).expect("Should read number")
);
let buf = [0x7fu8 | CONTINUATION_BIT, 0x7e];
let mut readable = &buf[..];
assert_eq!(
-129,
read::signed(&mut readable).expect("Should read number")
);
}
#[test]
fn test_read_signed_thru_dyn_trait() {
fn read(r: &mut dyn io::Read) -> i64 {
read::signed(r).expect("Should read number")
}
let buf = [0u8];
let mut readable = &buf[..];
assert_eq!(0, read(&mut readable));
let mut readable = io::Cursor::new(buf);
assert_eq!(0, read(&mut readable));
}
#[test]
fn test_read_signed_63_bits() {
let buf = [
CONTINUATION_BIT,
CONTINUATION_BIT,
CONTINUATION_BIT,
CONTINUATION_BIT,
CONTINUATION_BIT,
CONTINUATION_BIT,
CONTINUATION_BIT,
CONTINUATION_BIT,
0x40,
];
let mut readable = &buf[..];
assert_eq!(
-0x4000000000000000,
read::signed(&mut readable).expect("Should read number")
);
}
#[test]
fn test_read_unsigned_not_enough_data() {
let buf = [CONTINUATION_BIT];
let mut readable = &buf[..];
match read::unsigned(&mut readable) {
Err(read::Error::IoError(e)) => assert_eq!(e.kind(), io::ErrorKind::UnexpectedEof),
otherwise => panic!("Unexpected: {:?}", otherwise),
}
}
#[test]
fn test_read_signed_not_enough_data() {
let buf = [CONTINUATION_BIT];
let mut readable = &buf[..];
match read::signed(&mut readable) {
Err(read::Error::IoError(e)) => assert_eq!(e.kind(), io::ErrorKind::UnexpectedEof),
otherwise => panic!("Unexpected: {:?}", otherwise),
}
}
#[test]
fn test_write_unsigned_not_enough_space() {
let mut buf = [0; 1];
let mut writable = &mut buf[..];
match write::unsigned(&mut writable, 128) {
Err(e) => assert_eq!(e.kind(), io::ErrorKind::WriteZero),
otherwise => panic!("Unexpected: {:?}", otherwise),
}
}
#[test]
fn test_write_signed_not_enough_space() {
let mut buf = [0; 1];
let mut writable = &mut buf[..];
match write::signed(&mut writable, 128) {
Err(e) => assert_eq!(e.kind(), io::ErrorKind::WriteZero),
otherwise => panic!("Unexpected: {:?}", otherwise),
}
}
#[test]
fn test_write_unsigned_thru_dyn_trait() {
fn write(w: &mut dyn io::Write, val: u64) -> usize {
write::unsigned(w, val).expect("Should write number")
}
let mut buf = [0u8; 1];
let mut writable = &mut buf[..];
assert_eq!(write(&mut writable, 0), 1);
assert_eq!(buf[0], 0);
let mut writable = Vec::from(&buf[..]);
assert_eq!(write(&mut writable, 0), 1);
assert_eq!(buf[0], 0);
}
#[test]
fn test_write_signed_thru_dyn_trait() {
fn write(w: &mut dyn io::Write, val: i64) -> usize {
write::signed(w, val).expect("Should write number")
}
let mut buf = [0u8; 1];
let mut writable = &mut buf[..];
assert_eq!(write(&mut writable, 0), 1);
assert_eq!(buf[0], 0);
let mut writable = Vec::from(&buf[..]);
assert_eq!(write(&mut writable, 0), 1);
assert_eq!(buf[0], 0);
}
#[test]
fn dogfood_signed() {
fn inner(i: i64) {
let mut buf = [0u8; 1024];
{
let mut writable = &mut buf[..];
write::signed(&mut writable, i).expect("Should write signed number");
}
let mut readable = &buf[..];
let result = read::signed(&mut readable).expect("Should be able to read it back again");
assert_eq!(i, result);
}
for i in -513..513 {
inner(i);
}
inner(std::i64::MIN);
}
#[test]
fn dogfood_unsigned() {
for i in 0..1025 {
let mut buf = [0u8; 1024];
{
let mut writable = &mut buf[..];
write::unsigned(&mut writable, i).expect("Should write signed number");
}
let mut readable = &buf[..];
let result =
read::unsigned(&mut readable).expect("Should be able to read it back again");
assert_eq!(i, result);
}
}
#[test]
fn test_read_unsigned_overflow() {
let buf = [
2u8 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
1,
];
let mut readable = &buf[..];
assert!(read::unsigned(&mut readable).is_err());
}
#[test]
fn test_read_signed_overflow() {
let buf = [
2u8 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
2 | CONTINUATION_BIT,
1,
];
let mut readable = &buf[..];
assert!(read::signed(&mut readable).is_err());
}
#[test]
fn test_read_multiple() {
let buf = [2u8 | CONTINUATION_BIT, 1u8, 1u8];
let mut readable = &buf[..];
assert_eq!(
read::unsigned(&mut readable).expect("Should read first number"),
130u64
);
assert_eq!(
read::unsigned(&mut readable).expect("Should read first number"),
1u64
);
}
#[test]
fn test_read_multiple_with_overflow() {
let buf = [
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b1111_1111,
0b0111_1111, // Overflow!
0b1110_0100,
0b1110_0000,
0b0000_0010, // 45156
];
let mut readable = &buf[..];
assert!(if let read::Error::Overflow =
read::unsigned(&mut readable).expect_err("Should fail with Error::Overflow")
{
true
} else {
false
});
assert_eq!(
read::unsigned(&mut readable).expect("Should succeed with correct value"),
45156
);
}
}