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