1 //! Bit level parsers and combinators 2 //! 3 //! Bit parsing is handled by tweaking the input in most macros. 4 //! In byte level parsing, the input is generally a `&[u8]` passed from combinator 5 //! to combinator as the slices are manipulated. 6 //! 7 //! Bit parsers take a `(&[u8], usize)` as input. The first part of the tuple is a byte slice, 8 //! the second part is a bit offset in the first byte of the slice. 9 //! 10 //! By passing a pair like this, we can leverage most of the existing combinators, and avoid 11 //! transforming the whole slice to a vector of booleans. This should make it easy 12 //! to see a byte slice as a bit stream, and parse code points of arbitrary bit length. 13 //! 14 15 /// Transforms its byte slice input into a bit stream for the underlying parser. This allows the 16 /// given bit stream parser to work on a byte slice input. 17 /// 18 /// Signature: 19 /// `bits!( parser ) => ( &[u8], (&[u8], usize) -> IResult<(&[u8], usize), T> ) -> IResult<&[u8], T>` 20 /// 21 /// ``` 22 /// # #[macro_use] extern crate nom; 23 /// # fn main() { 24 /// named!( take_4_bits<u8>, bits!( take_bits!( u8, 4 ) ) ); 25 /// 26 /// let input = vec![0xAB, 0xCD, 0xEF, 0x12]; 27 /// let sl = &input[..]; 28 /// 29 /// assert_eq!(take_4_bits( sl ), Ok( (&sl[1..], 0xA) )); 30 /// # } 31 #[macro_export(local_inner_macros)] 32 macro_rules! bits ( 33 ($i:expr, $submac:ident!( $($args:tt)* )) => ( 34 bits_impl!($i, $submac!($($args)*)); 35 ); 36 ($i:expr, $f:expr) => ( 37 bits_impl!($i, call!($f)); 38 ); 39 ); 40 41 #[cfg(feature = "verbose-errors")] 42 /// Internal parser, do not use directly 43 #[doc(hidden)] 44 #[macro_export(local_inner_macros)] 45 macro_rules! bits_impl ( 46 ($i:expr, $submac:ident!( $($args:tt)* )) => ( 47 { 48 use $crate::lib::std::result::Result::*; 49 use $crate::{Context,Err,Needed}; 50 use $crate::Slice; 51 52 let input = ($i, 0usize); 53 match $submac!(input, $($args)*) { 54 Err(Err::Error(e)) => { 55 let err = match e { 56 Context::Code((i,b), kind) => Context::Code(i.slice(b/8..), kind), 57 Context::List(mut v) => { 58 Context::List(v.drain(..).map(|((i,b), kind)| (i.slice(b/8..), kind)).collect()) 59 } 60 }; 61 Err(Err::Error(err)) 62 }, 63 Err(Err::Failure(e)) => { 64 let err = match e { 65 Context::Code((i,b), kind) => Context::Code(i.slice(b/8..), kind), 66 Context::List(mut v) => { 67 Context::List(v.drain(..).map(|((i,b), kind)| (i.slice(b/8..), kind)).collect()) 68 } 69 }; 70 Err(Err::Failure(err)) 71 }, 72 Err(Err::Incomplete(Needed::Unknown)) => Err(Err::Incomplete(Needed::Unknown)), 73 Err(Err::Incomplete(Needed::Size(i))) => { 74 //println!("bits parser returned Needed::Size({})", i); 75 Err(Err::Incomplete(Needed::Size(i / 8 + 1))) 76 }, 77 Ok(((i, bit_index), o)) => { 78 let byte_index = bit_index / 8 + if bit_index % 8 == 0 { 0 } else { 1 } ; 79 //println!("bit index=={} => byte index=={}", bit_index, byte_index); 80 Ok((i.slice(byte_index..), o)) 81 } 82 } 83 } 84 ); 85 ); 86 87 #[cfg(not(feature = "verbose-errors"))] 88 /// Internal parser, do not use directly 89 #[doc(hidden)] 90 #[macro_export(local_inner_macros)] 91 macro_rules! bits_impl ( 92 ($i:expr, $submac:ident!( $($args:tt)* )) => ( 93 { 94 use $crate::lib::std::result::Result::*; 95 use $crate::{Err,Needed,Context}; 96 use $crate::Slice; 97 98 let input = ($i, 0usize); 99 match $submac!(input, $($args)*) { 100 Err(Err::Error(e)) => { 101 let Context::Code(_,err) = e; 102 Err(Err::Error(error_position!($i, err))) 103 }, 104 Err(Err::Failure(e)) => { 105 let Context::Code(_,err) = e; 106 Err(Err::Failure(error_position!($i, err))) 107 }, 108 Err(Err::Incomplete(Needed::Unknown)) => Err(Err::Incomplete(Needed::Unknown)), 109 Err(Err::Incomplete(Needed::Size(i))) => { 110 //println!("bits parser returned Needed::Size({})", i); 111 $crate::need_more($i, $crate::Needed::Size(i / 8 + 1)) 112 }, 113 Ok(((i, bit_index), o)) => { 114 let byte_index = bit_index / 8 + if bit_index % 8 == 0 { 0 } else { 1 } ; 115 //println!("bit index=={} => byte index=={}", bit_index, byte_index); 116 Ok((i.slice(byte_index..), o)) 117 } 118 } 119 } 120 ); 121 ); 122 123 /// Counterpart to bits, bytes! transforms its bit stream input into a byte slice for the underlying 124 /// parser, allowing byte-slice parsers to work on bit streams. 125 /// 126 /// Signature: 127 /// `bytes!( parser ) => ( (&[u8], usize), &[u8] -> IResult<&[u8], T> ) -> IResult<(&[u8], usize), T>`, 128 /// 129 /// A partial byte remaining in the input will be ignored and the given parser will start parsing 130 /// at the next full byte. 131 /// 132 /// ``` 133 /// # #[macro_use] extern crate nom; 134 /// # use nom::rest; 135 /// # fn main() { 136 /// named!( parse<(u8, u8, &[u8])>, bits!( tuple!( 137 /// take_bits!(u8, 4), 138 /// take_bits!(u8, 8), 139 /// bytes!(rest) 140 /// ))); 141 /// 142 /// let input = &[0xde, 0xad, 0xbe, 0xaf]; 143 /// 144 /// assert_eq!(parse( input ), Ok(( &[][..], (0xd, 0xea, &[0xbe, 0xaf][..]) ))); 145 /// # } 146 #[macro_export(local_inner_macros)] 147 macro_rules! bytes ( 148 ($i:expr, $submac:ident!( $($args:tt)* )) => ( 149 bytes_impl!($i, $submac!($($args)*)); 150 ); 151 ($i:expr, $f:expr) => ( 152 bytes_impl!($i, call!($f)); 153 ); 154 ); 155 156 #[cfg(feature = "verbose-errors")] 157 /// Internal parser, do not use directly 158 #[doc(hidden)] 159 #[macro_export(local_inner_macros)] 160 macro_rules! bytes_impl ( 161 ($macro_i:expr, $submac:ident!( $($args:tt)* )) => ( 162 { 163 use $crate::lib::std::result::Result::*; 164 use $crate::{Err,Needed,Context,Slice,ErrorKind}; 165 166 let inp; 167 if $macro_i.1 % 8 != 0 { 168 inp = $macro_i.0.slice(1 + $macro_i.1 / 8 ..); 169 } 170 else { 171 inp = $macro_i.0.slice($macro_i.1 / 8 ..); 172 } 173 174 let sub = $submac!(inp, $($args)*); 175 let res = match sub { 176 Err(Err::Incomplete(Needed::Size(i))) => Err(match i.checked_mul(8) { 177 Some(v) => Err::Incomplete(Needed::Size(v)), 178 None => Err::Failure(error_position!((inp, 0),ErrorKind::TooLarge)), 179 }), 180 Err(Err::Incomplete(Needed::Unknown)) => Err(Err::Incomplete(Needed::Unknown)), 181 Ok((i, o)) => { 182 Ok(((i, 0), o)) 183 }, 184 Err(Err::Error(e)) => { 185 let err = match e { 186 Context::Code(i, c) => Context::Code((i,0), c), 187 Context::List(mut v) => { 188 let (i, c) = v.remove(0); 189 Context::Code((i,0), c) 190 } 191 }; 192 Err(Err::Error(err)) 193 }, 194 Err(Err::Failure(e)) => { 195 let err = match e { 196 Context::Code(i, c) => Context::Code((i,0), c), 197 Context::List(mut v) => { 198 let (i, c) = v.remove(0); 199 Context::Code((i,0), c) 200 } 201 }; 202 Err(Err::Error(err)) 203 }, 204 Err(Err::Incomplete(Needed::Unknown)) => Err(Err::Incomplete(Needed::Unknown)), 205 Err(Err::Incomplete(Needed::Size(i))) => Err(match i.checked_mul(8) { 206 Some(v) => Err::Incomplete(Needed::Size(v)), 207 None => Err::Failure(error_position!((inp, 0),ErrorKind::TooLarge)), 208 }), 209 Ok((i, o)) => { 210 Ok(((i, 0), o)) 211 } 212 }; 213 res 214 } 215 ); 216 ); 217 218 #[cfg(not(feature = "verbose-errors"))] 219 /// Internal parser, do not use directly 220 #[doc(hidden)] 221 #[macro_export(local_inner_macros)] 222 macro_rules! bytes_impl ( 223 ($macro_i:expr, $submac:ident!( $($args:tt)* )) => ( 224 { 225 use $crate::lib::std::result::Result::*; 226 use $crate::{Err,Needed,Context,Slice,ErrorKind}; 227 228 let inp; 229 if $macro_i.1 % 8 != 0 { 230 inp = $macro_i.0.slice(1 + $macro_i.1 / 8 ..); 231 } 232 else { 233 inp = $macro_i.0.slice($macro_i.1 / 8 ..); 234 } 235 236 let sub = $submac!(inp, $($args)*); 237 let res = match sub { 238 Err(Err::Incomplete(Needed::Size(i))) => Err(match i.checked_mul(8) { 239 Some(v) => Err::Incomplete(Needed::Size(v)), 240 None => Err::Failure(error_position!((inp, 0),ErrorKind::TooLarge)), 241 }), 242 Err(Err::Incomplete(Needed::Unknown)) => Err(Err::Incomplete(Needed::Unknown)), 243 Ok((i, o)) => { 244 Ok(((i, 0), o)) 245 }, 246 Err(Err::Error(e)) => { 247 let Context::Code(i, c) = e; 248 Err(Err::Error(Context::Code((i,0), c))) 249 }, 250 Err(Err::Failure(e)) => { 251 let Context::Code(i, c) = e; 252 Err(Err::Failure(Context::Code((i,0), c))) 253 }, 254 }; 255 res 256 } 257 ); 258 ); 259 260 /// Consumes the specified number of bits and returns them as the specified type. 261 /// 262 /// Signature: 263 /// `take_bits!(type, count) => ( (&[T], usize), U, usize) -> IResult<(&[T], usize), U>` 264 /// 265 /// ``` 266 /// # #[macro_use] extern crate nom; 267 /// # fn main() { 268 /// named!( take_pair<(u8, u8)>, bits!( pair!( take_bits!(u8, 4), take_bits!(u8, 4) ) ) ); 269 /// 270 /// let input = vec![0xAB, 0xCD, 0xEF]; 271 /// let sl = &input[..]; 272 /// 273 /// assert_eq!(take_pair( sl ), Ok((&sl[1..], (0xA, 0xB))) ); 274 /// assert_eq!(take_pair( &sl[1..] ), Ok((&sl[2..], (0xC, 0xD))) ); 275 /// # } 276 /// ``` 277 #[macro_export(local_inner_macros)] 278 macro_rules! take_bits ( 279 ($i:expr, $t:ty, $count:expr) => ( 280 { 281 use $crate::lib::std::result::Result::*; 282 use $crate::{Needed,IResult}; 283 284 use $crate::lib::std::ops::Div; 285 use $crate::lib::std::convert::Into; 286 use $crate::Slice; 287 //println!("taking {} bits from {:?}", $count, $i); 288 let (input, bit_offset) = $i; 289 let res : IResult<_, $t> = if $count == 0 { 290 Ok(( (input, bit_offset), (0 as u8).into())) 291 } else { 292 let cnt = ($count as usize + bit_offset).div(8); 293 if input.len() * 8 < $count as usize + bit_offset { 294 //println!("returning incomplete: {}", $count as usize + bit_offset); 295 $crate::need_more($i, Needed::Size($count as usize)) 296 } else { 297 let mut acc:$t = (0 as u8).into(); 298 let mut offset: usize = bit_offset; 299 let mut remaining: usize = $count; 300 let mut end_offset: usize = 0; 301 302 for byte in input.iter().take(cnt + 1) { 303 if remaining == 0 { 304 break; 305 } 306 let val: $t = if offset == 0 { 307 (*byte as u8).into() 308 } else { 309 (((*byte as u8) << offset) as u8 >> offset).into() 310 }; 311 312 if remaining < 8 - offset { 313 acc += val >> (8 - offset - remaining); 314 end_offset = remaining + offset; 315 break; 316 } else { 317 acc += val << (remaining - (8 - offset)); 318 remaining -= 8 - offset; 319 offset = 0; 320 } 321 } 322 Ok(( (input.slice(cnt..), end_offset) , acc)) 323 } 324 }; 325 res 326 } 327 ); 328 ); 329 330 /// Matches the given bit pattern. 331 /// 332 /// Signature: 333 /// `tag_bits!(type, count, pattern) => ( (&[T], usize), U, usize, U) -> IResult<(&[T], usize), U>` 334 /// 335 /// The caller must specify the number of bits to consume. The matched value is included in the 336 /// result on success. 337 /// 338 /// ``` 339 /// # #[macro_use] extern crate nom; 340 /// # fn main() { 341 /// named!( take_a<u8>, bits!( tag_bits!(u8, 4, 0xA) ) ); 342 /// 343 /// let input = vec![0xAB, 0xCD, 0xEF]; 344 /// let sl = &input[..]; 345 /// 346 /// assert_eq!(take_a( sl ), Ok((&sl[1..], 0xA)) ); 347 /// # } 348 /// ``` 349 #[macro_export(local_inner_macros)] 350 macro_rules! tag_bits ( 351 ($i:expr, $t:ty, $count:expr, $p: pat) => ( 352 { 353 use $crate::lib::std::result::Result::*; 354 use $crate::{Err,IResult}; 355 356 match take_bits!($i, $t, $count) { 357 Err(Err::Incomplete(i)) => Err(Err::Incomplete(i)), 358 Ok((i, o)) => { 359 if let $p = o { 360 let res: IResult<_,$t> = Ok((i, o)); 361 res 362 } else { 363 let e: $crate::ErrorKind<u32> = $crate::ErrorKind::TagBits; 364 Err(Err::Error(error_position!($i, e))) 365 } 366 }, 367 _ => { 368 let e: $crate::ErrorKind<u32> = $crate::ErrorKind::TagBits; 369 Err(Err::Error(error_position!($i, e))) 370 } 371 } 372 } 373 ) 374 ); 375 376 #[cfg(test)] 377 mod tests { 378 use lib::std::ops::{AddAssign, Shl, Shr}; 379 use internal::{Err, Needed}; 380 use util::ErrorKind; 381 use types::CompleteByteSlice; 382 383 #[test] take_bits()384 fn take_bits() { 385 let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; 386 let sl = &input[..]; 387 388 assert_eq!(take_bits!((sl, 0), u8, 0), Ok(((sl, 0), 0))); 389 assert_eq!(take_bits!((sl, 0), u8, 8), Ok(((&sl[1..], 0), 170))); 390 assert_eq!(take_bits!((sl, 0), u8, 3), Ok(((&sl[0..], 3), 5))); 391 assert_eq!(take_bits!((sl, 0), u8, 6), Ok(((&sl[0..], 6), 42))); 392 assert_eq!(take_bits!((sl, 1), u8, 1), Ok(((&sl[0..], 2), 0))); 393 assert_eq!(take_bits!((sl, 1), u8, 2), Ok(((&sl[0..], 3), 1))); 394 assert_eq!(take_bits!((sl, 1), u8, 3), Ok(((&sl[0..], 4), 2))); 395 assert_eq!(take_bits!((sl, 6), u8, 3), Ok(((&sl[1..], 1), 5))); 396 assert_eq!(take_bits!((sl, 0), u16, 10), Ok(((&sl[1..], 2), 683))); 397 assert_eq!(take_bits!((sl, 0), u16, 8), Ok(((&sl[1..], 0), 170))); 398 assert_eq!(take_bits!((sl, 6), u16, 10), Ok(((&sl[2..], 0), 752))); 399 assert_eq!(take_bits!((sl, 6), u16, 11), Ok(((&sl[2..], 1), 1504))); 400 assert_eq!(take_bits!((sl, 0), u32, 20), Ok(((&sl[2..], 4), 700_163))); 401 assert_eq!(take_bits!((sl, 4), u32, 20), Ok(((&sl[3..], 0), 716_851))); 402 assert_eq!(take_bits!((CompleteByteSlice(sl), 4), u32, 20), Ok(((sl[3..].into(), 0), 716_851))); 403 assert_eq!( 404 take_bits!((sl, 4), u32, 22), 405 Err(Err::Incomplete(Needed::Size(22))) 406 ); 407 } 408 409 #[test] tag_bits()410 fn tag_bits() { 411 let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; 412 let sl = &input[..]; 413 414 assert_eq!(tag_bits!((sl, 0), u8, 3, 0b101), Ok(((&sl[0..], 3), 5))); 415 assert_eq!(tag_bits!((sl, 0), u8, 4, 0b1010), Ok(((&sl[0..], 4), 10))); 416 assert_eq!(tag_bits!((CompleteByteSlice(sl), 0), u8, 4, 0b1010), Ok(((sl[0..].into(), 4), 10))); 417 } 418 419 named!(ch<(&[u8],usize),(u8,u8)>, 420 do_parse!( 421 tag_bits!(u8, 3, 0b101) >> 422 x: take_bits!(u8, 4) >> 423 y: take_bits!(u8, 5) >> 424 (x,y) 425 ) 426 ); 427 428 #[test] chain_bits()429 fn chain_bits() { 430 let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; 431 let sl = &input[..]; 432 assert_eq!(ch((&input[..], 0)), Ok(((&sl[1..], 4), (5, 15)))); 433 assert_eq!(ch((&input[..], 4)), Ok(((&sl[2..], 0), (7, 16)))); 434 assert_eq!(ch((&input[..1], 0)), Err(Err::Incomplete(Needed::Size(5)))); 435 } 436 437 named!(ch_bytes<(u8, u8)>, bits!(ch)); 438 #[test] bits_to_bytes()439 fn bits_to_bytes() { 440 let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; 441 assert_eq!(ch_bytes(&input[..]), Ok((&input[2..], (5, 15)))); 442 assert_eq!(ch_bytes(&input[..1]), Err(Err::Incomplete(Needed::Size(1)))); 443 assert_eq!( 444 ch_bytes(&input[1..]), 445 Err(Err::Error(error_position!(&input[1..], ErrorKind::TagBits))) 446 ); 447 } 448 449 named!(bits_bytes_bs, bits!(bytes!(::rest))); 450 named!(bits_bytes_cbs<CompleteByteSlice, CompleteByteSlice>, bits!(bytes!(::rest))); 451 #[test] bits_bytes()452 fn bits_bytes() { 453 let input = [0b10_10_10_10]; 454 assert_eq!(bits_bytes_bs(&input[..]), Ok((&[][..], &[0b10_10_10_10][..]))); 455 assert_eq!(bits_bytes_cbs(CompleteByteSlice(&input[..])), Ok(([][..].into(), [0b10_10_10_10][..].into()))); 456 } 457 458 #[derive(PartialEq, Debug)] 459 struct FakeUint(u32); 460 461 impl AddAssign for FakeUint { add_assign(&mut self, other: FakeUint)462 fn add_assign(&mut self, other: FakeUint) { 463 *self = FakeUint(self.0 + other.0); 464 } 465 } 466 467 impl Shr<usize> for FakeUint { 468 type Output = FakeUint; 469 shr(self, shift: usize) -> FakeUint470 fn shr(self, shift: usize) -> FakeUint { 471 FakeUint(self.0 >> shift) 472 } 473 } 474 475 impl Shl<usize> for FakeUint { 476 type Output = FakeUint; 477 shl(self, shift: usize) -> FakeUint478 fn shl(self, shift: usize) -> FakeUint { 479 FakeUint(self.0 << shift) 480 } 481 } 482 483 impl From<u8> for FakeUint { from(i: u8) -> FakeUint484 fn from(i: u8) -> FakeUint { 485 FakeUint(u32::from(i)) 486 } 487 } 488 489 #[test] non_privitive_type()490 fn non_privitive_type() { 491 let input = [0b10_10_10_10, 0b11_11_00_00, 0b00_11_00_11]; 492 let sl = &input[..]; 493 494 assert_eq!( 495 take_bits!((sl, 0), FakeUint, 20), 496 Ok(((&sl[2..], 4), FakeUint(700_163))) 497 ); 498 assert_eq!( 499 take_bits!((sl, 4), FakeUint, 20), 500 Ok(((&sl[3..], 0), FakeUint(716_851))) 501 ); 502 assert_eq!( 503 take_bits!((sl, 4), FakeUint, 22), 504 Err(Err::Incomplete(Needed::Size(22))) 505 ); 506 } 507 } 508