winnow/binary/bits/
mod.rs

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

winnow/binary/bits/
mod.rs
