summaryrefslogtreecommitdiffstats
path: root/third_party/rust/leb128/src/lib.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/leb128/src/lib.rs')
-rw-r--r--third_party/rust/leb128/src/lib.rs652
1 files changed, 652 insertions, 0 deletions
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
+ );
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-23 14:00:55 +0000