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::{AsBytes, 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 name:"bits",
61 parser:unpeek(peek:move |input: Input| {
62 match parser.parse_peek((input, 0)) {
63 Ok(((rest: Input, offset: usize), result: Output)) => {
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: usize =
68 offset / BYTE + if offset % BYTE == 0 { 0 } else { 1 };
69 let (input: Input, _) = rest.peek_slice(offset:remaining_bytes_index);
70 Ok((input, result))
71 }
72 Err(ErrMode::Incomplete(n: Needed)) => {
73 Err(ErrMode::Incomplete(n.map(|u: NonZero| u.get() / BYTE + 1)))
74 }
75 Err(e: ErrMode) => 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> + AsBytes + 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: usize = count.to_usize();
201 trace(
202 name:"take",
203 parser:unpeek(peek: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: I, bit_offset: usize): (I, usize),
215 count: usize,
216) -> IResult<(I, usize), O, E>
217where
218 I: StreamIsPartial,
219 I: Stream<Token = u8> + AsBytes + 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.as_bytes().iter().copied().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> + AsBytes + 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: usize = count.to_usize();
350 trace(name:"pattern", parser:move |input: &mut (Input, usize)| {
351 let start: Checkpoint<(::Checkpoint, …), …> = input.checkpoint();
352
353 take(count).parse_next(input).and_then(|o: Output| {
354 if pattern == o {
355 Ok(o)
356 } else {
357 input.reset(&start);
358 Err(ErrMode::Backtrack(Error::from_error_kind(
359 input,
360 kind: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> + AsBytes + StreamIsPartial + Clone,
408{
409 traceimpl Parser<(Input, usize), …>(name:"bool", |input: &mut (Input, usize)| {
410 let bit: u32 = take(count:1usize).parse_next(input)?;
411 Ok(bit != 0)
412 })
413 .parse_next(input)
414}
415