diff options
Diffstat (limited to 'third_party/rust/nom/src/bits')
| -rw-r--r-- | third_party/rust/nom/src/bits/complete.rs | 75 | ||||
| -rw-r--r-- | third_party/rust/nom/src/bits/macros.rs | 263 | ||||
| -rw-r--r-- | third_party/rust/nom/src/bits/mod.rs | 119 | ||||
| -rw-r--r-- | third_party/rust/nom/src/bits/streaming.rs | 75 |
4 files changed, 532 insertions, 0 deletions
diff --git a/third_party/rust/nom/src/bits/complete.rs b/third_party/rust/nom/src/bits/complete.rs new file mode 100644 index 0000000000..f868ec2643 --- /dev/null +++ b/third_party/rust/nom/src/bits/complete.rs @@ -0,0 +1,75 @@ +//! bit level parsers +//! + +use crate::error::{ErrorKind, ParseError}; +use crate::internal::{Err, IResult}; +use crate::lib::std::ops::{AddAssign, RangeFrom, Shl, Shr, Div}; +use crate::traits::{InputIter, InputLength, Slice, ToUsize}; + +/// generates a parser taking `count` bits +pub fn take<I, O, C, E: ParseError<(I, usize)>>(count: C) -> impl Fn((I, usize)) -> IResult<(I, usize), O, E> +where + I: Slice<RangeFrom<usize>> + InputIter<Item = u8> + InputLength, + C: ToUsize, + O: From<u8> + AddAssign + Shl<usize, Output = O> + Shr<usize, Output = O>, +{ + let count = count.to_usize(); + move |(input, bit_offset): (I, usize)| { + if count == 0 { + Ok(((input, bit_offset), 0u8.into())) + } else { + let cnt = (count + bit_offset).div(8); + if input.input_len() * 8 < count + bit_offset { + Err(Err::Error(E::from_error_kind((input, bit_offset), ErrorKind::Eof))) + } else { + let mut acc:O = (0 as u8).into(); + let mut offset: usize = bit_offset; + let mut remaining: usize = count; + let mut end_offset: usize = 0; + + for byte in input.iter_elements().take(cnt + 1) { + if remaining == 0 { + break; + } + let val: O = if offset == 0 { + byte.into() + } else { + ((byte << offset) as u8 >> offset).into() + }; + + if remaining < 8 - offset { + acc += val >> (8 - offset - remaining); + end_offset = remaining + offset; + break; + } else { + acc += val << (remaining - (8 - offset)); + remaining -= 8 - offset; + offset = 0; + } + } + Ok(( (input.slice(cnt..), end_offset) , acc)) + } + } + } +} + +/// generates a parser taking `count` bits and comparing them to `pattern` +pub fn tag<I, O, C, E: ParseError<(I, usize)>>(pattern: O, count: C) -> impl Fn((I, usize)) -> IResult<(I, usize), O, E> +where + I: Slice<RangeFrom<usize>> + InputIter<Item = u8> + InputLength + Clone, + C: ToUsize, + O: From<u8> + AddAssign + Shl<usize, Output = O> + Shr<usize, Output = O> + PartialEq, +{ + let count = count.to_usize(); + move |input: (I, usize)| { + let inp = input.clone(); + + take(count)(input).and_then(|(i, o)| { + if pattern == o { + Ok((i, o)) + } else { + Err(Err::Error(error_position!(inp, ErrorKind::TagBits))) + } + }) + } +} diff --git a/third_party/rust/nom/src/bits/macros.rs b/third_party/rust/nom/src/bits/macros.rs new file mode 100644 index 0000000000..b056503fc6 --- /dev/null +++ b/third_party/rust/nom/src/bits/macros.rs @@ -0,0 +1,263 @@ +//! Bit level parsers and combinators +//! +//! Bit parsing is handled by tweaking the input in most macros. +//! In byte level parsing, the input is generally a `&[u8]` passed from combinator +//! to combinator as the slices are manipulated. +//! +//! Bit parsers take a `(&[u8], usize)` as input. The first part of the tuple is a byte slice, +//! the second part is a bit offset in the first byte of the slice. +//! +//! By passing a pair like this, we can leverage most of the existing combinators, and avoid +//! transforming the whole slice to a vector of booleans. This should make it easy +//! to see a byte slice as a bit stream, and parse code points of arbitrary bit length. +//! + +/// Transforms its byte slice input into a bit stream for the underlying parser. This allows the +/// given bit stream parser to work on a byte slice input. +/// +/// Signature: +/// `bits!( parser ) => ( &[u8], (&[u8], usize) -> IResult<(&[u8], usize), T> ) -> IResult<&[u8], T>` +/// +/// ``` +/// # #[macro_use] extern crate nom; +/// # use nom::{Err, Needed}; +/// # fn main() { +/// named!( take_4_bits<u8>, bits!( take_bits!( 4u8 ) ) ); +/// +/// let input = vec![0xAB, 0xCD, 0xEF, 0x12]; +/// let sl = &input[..]; +/// +/// assert_eq!(take_4_bits( sl ), Ok( (&sl[1..], 0xA) )); +/// assert_eq!(take_4_bits( &b""[..] ), Err(Err::Incomplete(Needed::Size(1)))); +/// # } +#[macro_export(local_inner_macros)] +macro_rules! bits ( + ($i:expr, $submac:ident!( $($args:tt)* )) => ({ + $crate::bits::bitsc($i, move |i| { $submac!(i, $($args)*) }) + }); + ($i:expr, $f:expr) => ( + bits!($i, call!($f)) + ); +); + +/// Counterpart to bits, bytes! transforms its bit stream input into a byte slice for the underlying +/// parser, allowing byte-slice parsers to work on bit streams. +/// +/// Signature: +/// `bytes!( parser ) => ( (&[u8], usize), &[u8] -> IResult<&[u8], T> ) -> IResult<(&[u8], usize), T>`, +/// +/// A partial byte remaining in the input will be ignored and the given parser will start parsing +/// at the next full byte. +/// +/// ``` +/// # #[macro_use] extern crate nom; +/// # use nom::combinator::rest; +/// # use nom::error::ErrorKind; +/// # fn main() { +/// +/// named!( parse<(u8, u8, &[u8])>, bits!( tuple!( +/// take_bits!(4u8), +/// take_bits!(8u8), +/// bytes!(rest::<_, (_, ErrorKind)>) +/// ))); +/// +/// let input = &[0xde, 0xad, 0xbe, 0xaf]; +/// +/// assert_eq!(parse( input ), Ok(( &[][..], (0xd, 0xea, &[0xbe, 0xaf][..]) ))); +/// # } +#[macro_export(local_inner_macros)] +macro_rules! bytes ( + ($i:expr, $submac:ident!( $($args:tt)* )) => ({ + $crate::bits::bytesc($i, move |i| { $submac!(i, $($args)*) }) + }); + ($i:expr, $f:expr) => ( + bytes!($i, call!($f)) + ); +); + +/// Consumes the specified number of bits and returns them as the specified type. +/// +/// Signature: +/// `take_bits!(type, count) => ( (&[T], usize), U, usize) -> IResult<(&[T], usize), U>` +/// +/// ``` +/// # #[macro_use] extern crate nom; +/// # fn main() { +/// named!(bits_pair<(&[u8], usize), (u8, u8)>, pair!( take_bits!(4u8), take_bits!(4u8) ) ); +/// named!( take_pair<(u8, u8)>, bits!( bits_pair ) ); +/// +/// let input = vec![0xAB, 0xCD, 0xEF]; +/// let sl = &input[..]; +/// +/// assert_eq!(take_pair( sl ), Ok((&sl[1..], (0xA, 0xB))) ); +/// assert_eq!(take_pair( &sl[1..] ), Ok((&sl[2..], (0xC, 0xD))) ); +/// # } +/// ``` +#[macro_export(local_inner_macros)] +macro_rules! take_bits ( + ($i:expr, $count:expr) => ( + { + let res: $crate::IResult<_, _> = $crate::bits::streaming::take($count)($i); + res + } + ); +); + +/// Matches the given bit pattern. +/// +/// Signature: +/// `tag_bits!(type, count, pattern) => ( (&[T], usize), U, usize, U) -> IResult<(&[T], usize), U>` +/// +/// The caller must specify the number of bits to consume. The matched value is included in the +/// result on success. +/// +/// ``` +/// # #[macro_use] extern crate nom; +/// # fn main() { +/// named!( take_a<u8>, bits!( tag_bits!(4usize, 0xA) ) ); +/// +/// let input = vec![0xAB, 0xCD, 0xEF]; +/// let sl = &input[..]; +/// +/// assert_eq!(take_a( sl ), Ok((&sl[1..], 0xA)) ); +/// # } +/// ``` +#[macro_export(local_inner_macros)] +macro_rules! tag_bits ( + ($i:expr, $count:expr, $p: expr) => ( + { + let res: $crate::IResult<_, _> = $crate::bits::streaming::tag($p, $count)($i); + res + } + ) +); + +#[cfg(test)] +mod tests { + use crate::lib::std::ops::{AddAssign, Shl, Shr}; + use crate::internal::{Err, Needed, IResult}; + use crate::error::ErrorKind; + + #[test] + fn take_bits() { + let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; + let sl = &input[..]; + + assert_eq!(take_bits!((sl, 0), 0u8), Ok(((sl, 0), 0))); + assert_eq!(take_bits!((sl, 0), 8u8), Ok(((&sl[1..], 0), 170))); + assert_eq!(take_bits!((sl, 0), 3u8), Ok(((&sl[0..], 3), 5))); + assert_eq!(take_bits!((sl, 0), 6u8), Ok(((&sl[0..], 6), 42))); + assert_eq!(take_bits!((sl, 1), 1u8), Ok(((&sl[0..], 2), 0))); + assert_eq!(take_bits!((sl, 1), 2u8), Ok(((&sl[0..], 3), 1))); + assert_eq!(take_bits!((sl, 1), 3u8), Ok(((&sl[0..], 4), 2))); + assert_eq!(take_bits!((sl, 6), 3u8), Ok(((&sl[1..], 1), 5))); + assert_eq!(take_bits!((sl, 0), 10u8), Ok(((&sl[1..], 2), 683))); + assert_eq!(take_bits!((sl, 0), 8u8), Ok(((&sl[1..], 0), 170))); + assert_eq!(take_bits!((sl, 6), 10u8), Ok(((&sl[2..], 0), 752))); + assert_eq!(take_bits!((sl, 6), 11u8), Ok(((&sl[2..], 1), 1504))); + assert_eq!(take_bits!((sl, 0), 20u8), Ok(((&sl[2..], 4), 700_163))); + assert_eq!(take_bits!((sl, 4), 20u8), Ok(((&sl[3..], 0), 716_851))); + let r: IResult<_,u32> = take_bits!((sl, 4), 22u8); + assert_eq!( + r, + Err(Err::Incomplete(Needed::Size(22))) + ); + } + + #[test] + fn tag_bits() { + let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; + let sl = &input[..]; + + assert_eq!(tag_bits!((sl, 0), 3u8, 0b101), Ok(((&sl[0..], 3), 5))); + assert_eq!(tag_bits!((sl, 0), 4u8, 0b1010), Ok(((&sl[0..], 4), 10))); + } + + named!(ch<(&[u8],usize),(u8,u8)>, + do_parse!( + tag_bits!(3u8, 0b101) >> + x: take_bits!(4u8) >> + y: take_bits!(5u8) >> + (x,y) + ) + ); + + #[test] + fn chain_bits() { + let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; + let sl = &input[..]; + assert_eq!(ch((&input[..], 0)), Ok(((&sl[1..], 4), (5, 15)))); + assert_eq!(ch((&input[..], 4)), Ok(((&sl[2..], 0), (7, 16)))); + assert_eq!(ch((&input[..1], 0)), Err(Err::Incomplete(Needed::Size(5)))); + } + + named!(ch_bytes<(u8, u8)>, bits!(ch)); + #[test] + fn bits_to_bytes() { + let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; + assert_eq!(ch_bytes(&input[..]), Ok((&input[2..], (5, 15)))); + assert_eq!(ch_bytes(&input[..1]), Err(Err::Incomplete(Needed::Size(1)))); + assert_eq!( + ch_bytes(&input[1..]), + Err(Err::Error(error_position!(&input[1..], ErrorKind::TagBits))) + ); + } + + named!(bits_bytes_bs, bits!(bytes!(crate::combinator::rest::<_, (&[u8], ErrorKind)>))); + #[test] + fn bits_bytes() { + let input = [0b10_10_10_10]; + assert_eq!(bits_bytes_bs(&input[..]), Ok((&[][..], &[0b10_10_10_10][..]))); + } + + #[derive(PartialEq, Debug)] + struct FakeUint(u32); + + impl AddAssign for FakeUint { + fn add_assign(&mut self, other: FakeUint) { + *self = FakeUint(self.0 + other.0); + } + } + + impl Shr<usize> for FakeUint { + type Output = FakeUint; + + fn shr(self, shift: usize) -> FakeUint { + FakeUint(self.0 >> shift) + } + } + + impl Shl<usize> for FakeUint { + type Output = FakeUint; + + fn shl(self, shift: usize) -> FakeUint { + FakeUint(self.0 << shift) + } + } + + impl From<u8> for FakeUint { + fn from(i: u8) -> FakeUint { + FakeUint(u32::from(i)) + } + } + + #[test] + fn non_privitive_type() { + let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; + let sl = &input[..]; + + assert_eq!( + take_bits!((sl, 0), 20u8), + Ok(((&sl[2..], 4), FakeUint(700_163))) + ); + assert_eq!( + take_bits!((sl, 4), 20u8), + Ok(((&sl[3..], 0), FakeUint(716_851))) + ); + let r3: IResult<_, FakeUint> = take_bits!((sl, 4), 22u8); + assert_eq!( + r3, + Err(Err::Incomplete(Needed::Size(22))) + ); + } +} diff --git a/third_party/rust/nom/src/bits/mod.rs b/third_party/rust/nom/src/bits/mod.rs new file mode 100644 index 0000000000..a6b12f1a74 --- /dev/null +++ b/third_party/rust/nom/src/bits/mod.rs @@ -0,0 +1,119 @@ +//! bit level parsers +//! + +#[macro_use] +mod macros; + +pub mod streaming; +pub mod complete; + +use crate::error::{ParseError, ErrorKind}; +use crate::internal::{Err, IResult, Needed}; +use crate::lib::std::ops::RangeFrom; +use crate::traits::{Slice, ErrorConvert}; + + +/// Converts a byte-level input to a bit-level input, for consumption by a parser that uses bits. +/// +/// Afterwards, the input is converted back to a byte-level parser, with any remaining bits thrown +/// away. +/// +/// # Example +/// ```ignore +/// # #[macro_use] extern crate nom; +/// # use nom::IResult; +/// use nom::bits::bits; +/// use nom::bits::complete::take; +/// +/// fn take_4_bits(input: &[u8]) -> IResult<&[u8], u64> { +/// bits(take::<_, _, _, (_, _)>(4usize))(input) +/// } +/// +/// let input = vec![0xAB, 0xCD, 0xEF, 0x12]; +/// let sl = &input[..]; +/// +/// assert_eq!(take_4_bits( sl ), Ok( (&sl[1..], 0xA) )); +/// ``` +pub fn bits<I, O, E1: ParseError<(I, usize)>+ErrorConvert<E2>, E2: ParseError<I>, P>(parser: P) -> impl Fn(I) -> IResult<I, O, E2> +where + I: Slice<RangeFrom<usize>>, + P: Fn((I, usize)) -> IResult<(I, usize), O, E1>, +{ + move |input: I| match parser((input, 0)) { + Ok(((rest, offset), res)) => { + let byte_index = offset / 8 + if offset % 8 == 0 { 0 } else { 1 }; + Ok((rest.slice(byte_index..), res)) + } + Err(Err::Incomplete(n)) => Err(Err::Incomplete(n.map(|u| u / 8 + 1))), + Err(Err::Error(e)) => Err(Err::Error(e.convert())), + Err(Err::Failure(e)) => Err(Err::Failure(e.convert())), + } +} + +#[doc(hidden)] +pub fn bitsc<I, O, E1: ParseError<(I, usize)>+ErrorConvert<E2>, E2: ParseError<I>, P>(input: I, parser: P) -> IResult<I, O, E2> +where + I: Slice<RangeFrom<usize>>, + P: Fn((I, usize)) -> IResult<(I, usize), O, E1>, +{ + bits(parser)(input) +} + +/// Counterpart to bits, bytes transforms its bit stream input into a byte slice for the underlying +/// parser, allowing byte-slice parsers to work on bit streams. +/// +/// A partial byte remaining in the input will be ignored and the given parser will start parsing +/// at the next full byte. +/// +/// ```ignore +/// # #[macro_use] extern crate nom; +/// # use nom::IResult; +/// # use nom::combinator::rest; +/// # use nom::sequence::tuple; +/// use nom::bits::{bits, bytes, streaming::take_bits}; +/// +/// fn parse(input: &[u8]) -> IResult<&[u8], (u8, u8, &[u8])> { +/// bits(tuple(( +/// take_bits(4usize), +/// take_bits(8usize), +/// bytes(rest) +/// )))(input) +/// } +/// +/// let input = &[0xde, 0xad, 0xbe, 0xaf]; +/// +/// assert_eq!(parse( input ), Ok(( &[][..], (0xd, 0xea, &[0xbe, 0xaf][..]) ))); +/// ``` +pub fn bytes<I, O, E1: ParseError<I>+ErrorConvert<E2>, E2: ParseError<(I, usize)>, P>(parser: P) -> impl Fn((I, usize)) -> IResult<(I, usize), O, E2> +where + I: Slice<RangeFrom<usize>> + Clone, + P: Fn(I) -> IResult<I, O, E1>, +{ + move |(input, offset): (I, usize)| { + let inner = if offset % 8 != 0 { + input.slice((1 + offset / 8)..) + } else { + input.slice((offset / 8)..) + }; + let i = (input.clone(), offset); + match parser(inner) { + Ok((rest, res)) => Ok(((rest, 0), res)), + Err(Err::Incomplete(Needed::Unknown)) => Err(Err::Incomplete(Needed::Unknown)), + Err(Err::Incomplete(Needed::Size(sz))) => Err(match sz.checked_mul(8) { + Some(v) => Err::Incomplete(Needed::Size(v)), + None => Err::Failure(E2::from_error_kind(i, ErrorKind::TooLarge)), + }), + Err(Err::Error(e)) => Err(Err::Error(e.convert())), + Err(Err::Failure(e)) => Err(Err::Failure(e.convert())), + } + } +} + +#[doc(hidden)] +pub fn bytesc<I, O, E1: ParseError<I>+ErrorConvert<E2>, E2: ParseError<(I, usize)>, P>(input: (I, usize), parser: P) -> IResult<(I, usize), O, E2> +where + I: Slice<RangeFrom<usize>> + Clone, + P: Fn(I) -> IResult<I, O, E1>, +{ + bytes(parser)(input) +} diff --git a/third_party/rust/nom/src/bits/streaming.rs b/third_party/rust/nom/src/bits/streaming.rs new file mode 100644 index 0000000000..5ab75961bb --- /dev/null +++ b/third_party/rust/nom/src/bits/streaming.rs @@ -0,0 +1,75 @@ +//! bit level parsers +//! + +use crate::error::{ErrorKind, ParseError}; +use crate::internal::{Err, IResult, Needed}; +use crate::lib::std::ops::{AddAssign, RangeFrom, Shl, Shr, Div}; +use crate::traits::{InputIter, InputLength, Slice, ToUsize}; + +/// generates a parser taking `count` bits +pub fn take<I, O, C, E: ParseError<(I, usize)>>(count: C) -> impl Fn((I, usize)) -> IResult<(I, usize), O, E> +where + I: Slice<RangeFrom<usize>> + InputIter<Item = u8> + InputLength, + C: ToUsize, + O: From<u8> + AddAssign + Shl<usize, Output = O> + Shr<usize, Output = O>, +{ + let count = count.to_usize(); + move |(input, bit_offset): (I, usize)| { + if count == 0 { + Ok(((input, bit_offset), 0u8.into())) + } else { + let cnt = (count + bit_offset).div(8); + if input.input_len() * 8 < count + bit_offset { + Err(Err::Incomplete(Needed::Size(count as usize))) + } else { + let mut acc:O = (0 as u8).into(); + let mut offset: usize = bit_offset; + let mut remaining: usize = count; + let mut end_offset: usize = 0; + + for byte in input.iter_elements().take(cnt + 1) { + if remaining == 0 { + break; + } + let val: O = if offset == 0 { + byte.into() + } else { + ((byte << offset) as u8 >> offset).into() + }; + + if remaining < 8 - offset { + acc += val >> (8 - offset - remaining); + end_offset = remaining + offset; + break; + } else { + acc += val << (remaining - (8 - offset)); + remaining -= 8 - offset; + offset = 0; + } + } + Ok(( (input.slice(cnt..), end_offset) , acc)) + } + } + } +} + +/// generates a parser taking `count` bits and comparing them to `pattern` +pub fn tag<I, O, C, E: ParseError<(I, usize)>>(pattern: O, count: C) -> impl Fn((I, usize)) -> IResult<(I, usize), O, E> +where + I: Slice<RangeFrom<usize>> + InputIter<Item = u8> + InputLength + Clone, + C: ToUsize, + O: From<u8> + AddAssign + Shl<usize, Output = O> + Shr<usize, Output = O> + PartialEq, +{ + let count = count.to_usize(); + move |input: (I, usize)| { + let inp = input.clone(); + + take(count)(input).and_then(|(i, o)| { + if pattern == o { + Ok((i, o)) + } else { + Err(Err::Error(error_position!(inp, ErrorKind::TagBits))) + } + }) + } +} |