winnow/binary/bits/
mod.rs

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