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