diff options
Diffstat (limited to 'third_party/rust/leb128/src')
| -rw-r--r-- | third_party/rust/leb128/src/bin/leb128-repl.rs | 94 | ||||
| -rw-r--r-- | third_party/rust/leb128/src/lib.rs | 652 |
2 files changed, 746 insertions, 0 deletions
diff --git a/third_party/rust/leb128/src/bin/leb128-repl.rs b/third_party/rust/leb128/src/bin/leb128-repl.rs new file mode 100644 index 0000000000..4f6c43e367 --- /dev/null +++ b/third_party/rust/leb128/src/bin/leb128-repl.rs @@ -0,0 +1,94 @@ +use leb128; + +use std::io::{self, BufRead, Write}; +use std::str; + +fn display(bytes: &[u8]) -> String { + let mut s = vec![]; + + // Base 10. + write!(&mut s, "{:?}\n", bytes).unwrap(); + + // Hex. + write!(&mut s, "[").unwrap(); + for (i, b) in bytes.iter().enumerate() { + if i != 0 { + write!(&mut s, ", ").unwrap(); + } + write!(&mut s, "{:0x}", b).unwrap(); + } + writeln!(&mut s, "]").unwrap(); + + // Binary. + write!(&mut s, "[").unwrap(); + for (i, b) in bytes.iter().enumerate() { + if i != 0 { + write!(&mut s, ", ").unwrap(); + } + write!(&mut s, "{:08b}", b).unwrap(); + } + writeln!(&mut s, "]").unwrap(); + + String::from_utf8(s).unwrap() +} + +fn main() { + println!( + " +LEB128 Read-Eval-Print-Loop! + +Converts numbers to signed and unsigned LEB128 and displays the results in +base-10, hex, and binary. +" + ); + + let mut stdin = io::BufReader::new(io::stdin()); + let mut stdout = io::stdout(); + + let mut buf = vec![]; + + loop { + stdout.write_all(b"> ").expect("failed to write to stdout"); + stdout.flush().expect("failed to flush stdout"); + + buf.clear(); + let n = stdin + .read_until(b'\n', &mut buf) + .expect("failed to read line from stdin"); + if n == 0 { + break; + } + + let uleb = str::from_utf8(&buf) + .ok() + .and_then(|s| s.trim().parse().ok()) + .and_then(|n: u64| { + let mut s = vec![]; + leb128::write::unsigned(&mut s, n).ok()?; + Some(display(&s)) + }) + .unwrap_or_else(|| "error\n".into()); + stdout + .write_all(b"# unsigned LEB128\n") + .and_then(|_| stdout.write_all(uleb.as_bytes())) + .and_then(|_| stdout.write_all(b"\n")) + .expect("failed to write to stdout"); + + let leb = str::from_utf8(&buf) + .ok() + .and_then(|s| s.trim().parse().ok()) + .and_then(|n: i64| { + let mut s = vec![]; + leb128::write::signed(&mut s, n).ok()?; + Some(display(&s)) + }) + .unwrap_or_else(|| "error\n".into()); + stdout + .write_all(b"# signed LEB128\n") + .and_then(|_| stdout.write_all(leb.as_bytes())) + .and_then(|_| stdout.write_all(b"\n")) + .expect("failed to write to stdout"); + + stdout.flush().expect("failed to flush stdout"); + } +} diff --git a/third_party/rust/leb128/src/lib.rs b/third_party/rust/leb128/src/lib.rs new file mode 100644 index 0000000000..f979b18386 --- /dev/null +++ b/third_party/rust/leb128/src/lib.rs @@ -0,0 +1,652 @@ +//! 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 + ); + } +} |