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}