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

winnow/binary/bits/
mod.rs
