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(name:"bits", parser:move |input: &mut Input| {
60 let mut bit_input: (&mut Input, usize) = (input.clone(), 0);
61 match parser.parse_next(&mut bit_input) {
62 Ok(result: Output) => {
63 let (mut rest: &mut Input, offset: usize) = 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: usize = offset / BYTE + if offset % BYTE == 0 { 0 } else { 1 };
68 let _ = rest.next_slice(offset:remaining_bytes_index);
69 *input = rest;
70 Ok(result)
71 }
72 Err(e: BitError) => match e.needed() {
73 Some(n: Needed) => Err(ParserError::incomplete(
74 input,
75 _needed:n.map(|u: NonZero| u.get() / BYTE + 1),
76 )),
77 None => Err(ErrorConvert::convert(self: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: usize = count.to_usize();
204 trace(name:"take", parser: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: usize = count.to_usize();
337 trace(name:"pattern", parser:move |input: &mut (Input, usize)| {
338 let start: Checkpoint<(::Checkpoint, …), …> = input.checkpoint();
339
340 take(count).parse_next(input).and_then(|o: Output| {
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 traceimpl Parser<(Input, usize), …, …>(name:"bool", |input: &mut (Input, usize)| {
394 let bit: u32 = take(count:1usize).parse_next(input)?;
395 Ok(bit != 0)
396 })
397 .parse_next(input)
398}
399