1//! Bit level parsers
2//!
3
4#[cfg(test)]
5mod tests;
6
7use crate::error::{ErrMode, ErrorConvert, ErrorKind, Needed, ParseError};
8use crate::lib::std::ops::{AddAssign, Div, Shl, Shr};
9use crate::stream::{AsBytes, Stream, StreamIsPartial, ToUsize};
10use crate::trace::trace;
11use crate::{IResult, Parser};
12
13/// Converts a byte-level input to a bit-level input
14///
15/// See [`bytes`] to convert it back.
16///
17/// # Example
18/// ```
19/// use winnow::prelude::*;
20/// use winnow::Bytes;
21/// use winnow::binary::bits::{bits, take};
22/// use winnow::error::Error;
23///
24/// type Stream<'i> = &'i Bytes;
25///
26/// fn stream(b: &[u8]) -> Stream<'_> {
27/// Bytes::new(b)
28/// }
29///
30/// fn parse(input: Stream<'_>) -> IResult<Stream<'_>, (u8, u8)> {
31/// bits::<_, _, Error<(_, usize)>, _, _>((take(4usize), take(8usize))).parse_next(input)
32/// }
33///
34/// let input = stream(&[0x12, 0x34, 0xff, 0xff]);
35///
36/// let output = parse(input).expect("We take 1.5 bytes and the input is longer than 2 bytes");
37///
38/// // The first byte is consumed, the second byte is partially consumed and dropped.
39/// let remaining = output.0;
40/// assert_eq!(remaining, stream(&[0xff, 0xff]));
41///
42/// let parsed = output.1;
43/// assert_eq!(parsed.0, 0x01);
44/// assert_eq!(parsed.1, 0x23);
45/// ```
46pub fn bits<I, O, E1, E2, P>(mut parser: P) -> impl Parser<I, O, E2>
47where
48 E1: ParseError<(I, usize)> + ErrorConvert<E2>,
49 E2: ParseError<I>,
50 I: Stream,
51 P: Parser<(I, usize), O, E1>,
52{
53 trace(name:"bits", parser:move |input: I| {
54 match parser.parse_next((input, 0)) {
55 Ok(((rest: I, offset: usize), result: O)) => {
56 // If the next byte has been partially read, it will be sliced away as well.
57 // The parser functions might already slice away all fully read bytes.
58 // That's why `offset / 8` isn't necessarily needed at all times.
59 let remaining_bytes_index: usize = offset / 8 + if offset % 8 == 0 { 0 } else { 1 };
60 let (input: I, _) = rest.next_slice(offset:remaining_bytes_index);
61 Ok((input, result))
62 }
63 Err(ErrMode::Incomplete(n: Needed)) => Err(ErrMode::Incomplete(n.map(|u: NonZero| u.get() / 8 + 1))),
64 Err(e: ErrMode) => Err(e.convert()),
65 }
66 })
67}
68
69/// Convert a [`bits`] stream back into a byte stream
70///
71/// **Warning:** A partial byte remaining in the input will be ignored and the given parser will
72/// start parsing at the next full byte.
73///
74/// ```
75/// use winnow::prelude::*;
76/// use winnow::Bytes;
77/// use winnow::binary::bits::{bits, bytes, take};
78/// use winnow::combinator::rest;
79/// use winnow::error::Error;
80///
81/// type Stream<'i> = &'i Bytes;
82///
83/// fn stream(b: &[u8]) -> Stream<'_> {
84/// Bytes::new(b)
85/// }
86///
87/// fn parse(input: Stream<'_>) -> IResult<Stream<'_>, (u8, u8, &[u8])> {
88/// bits::<_, _, Error<(_, usize)>, _, _>((
89/// take(4usize),
90/// take(8usize),
91/// bytes::<_, _, Error<_>, _, _>(rest)
92/// )).parse_next(input)
93/// }
94///
95/// let input = stream(&[0x12, 0x34, 0xff, 0xff]);
96///
97/// assert_eq!(parse(input), Ok(( stream(&[]), (0x01, 0x23, &[0xff, 0xff][..]) )));
98/// ```
99pub fn bytes<I, O, E1, E2, P>(mut parser: P) -> impl Parser<(I, usize), O, E2>
100where
101 E1: ParseError<I> + ErrorConvert<E2>,
102 E2: ParseError<(I, usize)>,
103 I: Stream<Token = u8>,
104 P: Parser<I, O, E1>,
105{
106 trace(name:"bytes", parser:move |(input: I, offset: usize): (I, usize)| {
107 let (inner: I, _) = if offset % 8 != 0 {
108 input.next_slice(offset:1 + offset / 8)
109 } else {
110 input.next_slice(offset:offset / 8)
111 };
112 let i: (I, usize) = (input, offset);
113 match parser.parse_next(input:inner) {
114 Ok((rest: I, res: O)) => Ok(((rest, 0), res)),
115 Err(ErrMode::Incomplete(Needed::Unknown)) => Err(ErrMode::Incomplete(Needed::Unknown)),
116 Err(ErrMode::Incomplete(Needed::Size(sz: NonZero))) => Err(match sz.get().checked_mul(8) {
117 Some(v: usize) => ErrMode::Incomplete(Needed::new(v)),
118 None => ErrMode::Cut(E2::assert(
119 input:i,
120 _message:"overflow in turning needed bytes into needed bits",
121 )),
122 }),
123 Err(e: ErrMode) => Err(e.convert()),
124 }
125 })
126}
127
128/// Parse taking `count` bits
129///
130/// # Example
131/// ```rust
132/// # use winnow::prelude::*;
133/// # use winnow::Bytes;
134/// # use winnow::error::{Error, ErrorKind};
135/// use winnow::binary::bits::take;
136///
137/// type Stream<'i> = &'i Bytes;
138///
139/// fn stream(b: &[u8]) -> Stream<'_> {
140/// Bytes::new(b)
141/// }
142///
143/// fn parser(input: (Stream<'_>, usize), count: usize)-> IResult<(Stream<'_>, usize), u8> {
144/// take(count).parse_next(input)
145/// }
146///
147/// // Consumes 0 bits, returns 0
148/// assert_eq!(parser((stream(&[0b00010010]), 0), 0), Ok(((stream(&[0b00010010]), 0), 0)));
149///
150/// // Consumes 4 bits, returns their values and increase offset to 4
151/// assert_eq!(parser((stream(&[0b00010010]), 0), 4), Ok(((stream(&[0b00010010]), 4), 0b00000001)));
152///
153/// // Consumes 4 bits, offset is 4, returns their values and increase offset to 0 of next byte
154/// assert_eq!(parser((stream(&[0b00010010]), 4), 4), Ok(((stream(&[]), 0), 0b00000010)));
155///
156/// // Tries to consume 12 bits but only 8 are available
157/// assert_eq!(parser((stream(&[0b00010010]), 0), 12), Err(winnow::error::ErrMode::Backtrack(Error{input: (stream(&[0b00010010]), 0), kind: ErrorKind::Eof })));
158/// ```
159#[inline(always)]
160pub fn take<I, O, C, E: ParseError<(I, usize)>>(count: C) -> impl Parser<(I, usize), O, E>
161where
162 I: Stream<Token = u8> + AsBytes + StreamIsPartial,
163 C: ToUsize,
164 O: From<u8> + AddAssign + Shl<usize, Output = O> + Shr<usize, Output = O>,
165{
166 let count: usize = count.to_usize();
167 trace(name:"take", parser:move |input: (I, usize)| {
168 if <I as StreamIsPartial>::is_partial_supported() {
169 take_::<_, _, _, true>(input, count)
170 } else {
171 take_::<_, _, _, false>(input, count)
172 }
173 })
174}
175
176fn take_<I, O, E: ParseError<(I, usize)>, const PARTIAL: bool>(
177 (input: I, bit_offset: usize): (I, usize),
178 count: usize,
179) -> IResult<(I, usize), O, E>
180where
181 I: StreamIsPartial,
182 I: Stream<Token = u8> + AsBytes,
183 O: From<u8> + AddAssign + Shl<usize, Output = O> + Shr<usize, Output = O>,
184{
185 if count == 0 {
186 Ok(((input, bit_offset), 0u8.into()))
187 } else {
188 let cnt = (count + bit_offset).div(8);
189 if input.eof_offset() * 8 < count + bit_offset {
190 if PARTIAL && input.is_partial() {
191 Err(ErrMode::Incomplete(Needed::new(count)))
192 } else {
193 Err(ErrMode::from_error_kind(
194 (input, bit_offset),
195 ErrorKind::Eof,
196 ))
197 }
198 } else {
199 let mut acc: O = 0_u8.into();
200 let mut offset: usize = bit_offset;
201 let mut remaining: usize = count;
202 let mut end_offset: usize = 0;
203
204 for byte in input.as_bytes().iter().copied().take(cnt + 1) {
205 if remaining == 0 {
206 break;
207 }
208 let val: O = if offset == 0 {
209 byte.into()
210 } else {
211 (byte << offset >> offset).into()
212 };
213
214 if remaining < 8 - offset {
215 acc += val >> (8 - offset - remaining);
216 end_offset = remaining + offset;
217 break;
218 } else {
219 acc += val << (remaining - (8 - offset));
220 remaining -= 8 - offset;
221 offset = 0;
222 }
223 }
224 let (input, _) = input.next_slice(cnt);
225 Ok(((input, end_offset), acc))
226 }
227 }
228}
229
230/// Parse taking `count` bits and comparing them to `pattern`
231///
232/// # Example
233///
234/// ```rust
235/// # use winnow::prelude::*;
236/// # use winnow::Bytes;
237/// # use winnow::error::{Error, ErrorKind};
238/// use winnow::binary::bits::tag;
239///
240/// type Stream<'i> = &'i Bytes;
241///
242/// fn stream(b: &[u8]) -> Stream<'_> {
243/// Bytes::new(b)
244/// }
245///
246/// /// Compare the lowest `count` bits of `input` against the lowest `count` bits of `pattern`.
247/// /// Return Ok and the matching section of `input` if there's a match.
248/// /// Return Err if there's no match.
249/// fn parser(pattern: u8, count: u8, input: (Stream<'_>, usize)) -> IResult<(Stream<'_>, usize), u8> {
250/// tag(pattern, count).parse_next(input)
251/// }
252///
253/// // The lowest 4 bits of 0b00001111 match the lowest 4 bits of 0b11111111.
254/// assert_eq!(
255/// parser(0b0000_1111, 4, (stream(&[0b1111_1111]), 0)),
256/// Ok(((stream(&[0b1111_1111]), 4), 0b0000_1111))
257/// );
258///
259/// // The lowest bit of 0b00001111 matches the lowest bit of 0b11111111 (both are 1).
260/// assert_eq!(
261/// parser(0b00000001, 1, (stream(&[0b11111111]), 0)),
262/// Ok(((stream(&[0b11111111]), 1), 0b00000001))
263/// );
264///
265/// // The lowest 2 bits of 0b11111111 and 0b00000001 are different.
266/// assert_eq!(
267/// parser(0b000000_01, 2, (stream(&[0b111111_11]), 0)),
268/// Err(winnow::error::ErrMode::Backtrack(Error {
269/// input: (stream(&[0b11111111]), 0),
270/// kind: ErrorKind::Tag
271/// }))
272/// );
273///
274/// // The lowest 8 bits of 0b11111111 and 0b11111110 are different.
275/// assert_eq!(
276/// parser(0b11111110, 8, (stream(&[0b11111111]), 0)),
277/// Err(winnow::error::ErrMode::Backtrack(Error {
278/// input: (stream(&[0b11111111]), 0),
279/// kind: ErrorKind::Tag
280/// }))
281/// );
282/// ```
283#[inline(always)]
284#[doc(alias = "literal")]
285#[doc(alias = "just")]
286pub fn tag<I, O, C, E: ParseError<(I, usize)>>(
287 pattern: O,
288 count: C,
289) -> impl Parser<(I, usize), O, E>
290where
291 I: Stream<Token = u8> + AsBytes + StreamIsPartial,
292 C: ToUsize,
293 O: From<u8> + AddAssign + Shl<usize, Output = O> + Shr<usize, Output = O> + PartialEq,
294{
295 let count: usize = count.to_usize();
296 trace(name:"tag", parser:move |input: (I, usize)| {
297 let inp: (I, usize) = input.clone();
298
299 take(count).parse_next(input).and_then(|(i: (I, usize), o: O)| {
300 if pattern == o {
301 Ok((i, o))
302 } else {
303 Err(ErrMode::Backtrack(E::from_error_kind(input:inp, kind:ErrorKind::Tag)))
304 }
305 })
306 })
307}
308
309/// Parses one specific bit as a bool.
310///
311/// # Example
312///
313/// ```rust
314/// # use winnow::prelude::*;
315/// # use winnow::Bytes;
316/// # use winnow::error::{Error, ErrorKind};
317/// use winnow::binary::bits::bool;
318///
319/// type Stream<'i> = &'i Bytes;
320///
321/// fn stream(b: &[u8]) -> Stream<'_> {
322/// Bytes::new(b)
323/// }
324///
325/// fn parse(input: (Stream<'_>, usize)) -> IResult<(Stream<'_>, usize), bool> {
326/// bool.parse_next(input)
327/// }
328///
329/// assert_eq!(parse((stream(&[0b10000000]), 0)), Ok(((stream(&[0b10000000]), 1), true)));
330/// assert_eq!(parse((stream(&[0b10000000]), 1)), Ok(((stream(&[0b10000000]), 2), false)));
331/// ```
332#[doc(alias = "any")]
333pub fn bool<I, E: ParseError<(I, usize)>>(input: (I, usize)) -> IResult<(I, usize), bool, E>
334where
335 I: Stream<Token = u8> + AsBytes + StreamIsPartial,
336{
337 traceimpl Parser<(I, usize), bool, …>(name:"bool", |input: (I, usize)| {
338 let (res: (I, usize), bit: u32): (_, u32) = take(count:1usize).parse_next(input)?;
339 Ok((res, bit != 0))
340 })
341 .parse_next(input)
342}
343