What is needed for binary parsing?

[epage]

I don't do enough binary parsing to have a good feel for needs, so I would love to hear some!

Examples

• Missing combinators, like varint
• Challenges with bit parsing within bytes

[epage]

See also

• Bit field parsers rust-bakery/nom#66
• investigate mem transmute combinator rust-bakery/nom#354
• Add More Documentation On Bit Parsers rust-bakery/nom#1193

[epage]

#153 added impl Stream for (I, usize). I wonder about adding a dedicated stream type, Bits, so we have more control over this than () allows.

[epage]

See #234 for discussion on the role of macros for writing binary parsers

[hmeine]

As I just mentioned in #504, I am dealing with a format that would require a dec_uint() that allows for leading zeros. Not sure how related that is to binary parsing in general, but that's my context.

[epage]

So if I understand, you need take_while(1, b'0'..b'9').parse_to::<u64>()?

I wonder if the basic case is basic enough that it needs something built-in. Or if there is something built-in, if it'd be better to make it character classes (e.g. const DIGITS = (b'0'..b'9') that users can compose with other character classes and use with any of the parsers that accept them.

[hmeine]

Indeed, I wrote my own parse_uint<T>() and it was not too large, but considerably larger than yours, because I did not use parse_to()… that's great! (And I was already making use of digit1.) dec_uint() seemed to be more optimized w.r.t. the unchecked from_utf8 conversion, which seemed to be something nice to have, but parse_to() is short and sweet and at least hides the str conversion from my own code.

[hmeine]

What could also be great (*) is a variant of parse() or parse_next() that accepts a Read or BufRead and efficiently deals with the buffers and partial reads.

On a related note, I found myself trying to use parse(), but having to resort to parse_next() because I am dealing with large image files from which I am only parsing the header. Which parts of the image data that come after it are actually necessary and when they're read depends on the application, so I need to be able to read the variable-sized metadata header (which itself can already be large) efficiently and without expecting EOF directly after it.

(*) /me is half expected to be convinced otherwise, but this is with today's world view of mine.

[epage]

What could also be great (*) is a variant of parse() or parse_next() that accepts a Read or BufRead and efficiently deals with the buffers and partial reads.

This is being tracked as #299. However, the proposed need for seek (which was inspired by other parsers) might be a limitation and it would be good to know if that is a problem.

Similarly, it'd be good to know what your partial parsing state is, for example

• Frames or not? If not, what does it look like
• What determines the length of a frame, a fixed value, a delimiter, an embedded length, or a length in a header?

I suspect partial parsing should focus on frames, rather than generic buffers. For example, a partial parser for ndjson should do a "take until newline" (inclusive) partially and then do json parsing inside of that completely. This has the downside of being two passes in this case (though the first pass can use SIMD) but it reduces the overhead in filling the buffer with the right amount of data.

The question is what patterns need to be developed to help assist with these. On a related note, I have been tempted to fork circular to clean it up for these use cases (since development on it seems stalled)

On a related note, I found myself trying to use parse(), but having to resort to parse_next() because I am dealing with large image files from which I am only parsing the header. Which parts of the image data that come after it are actually necessary and when they're read depends on the application, so I need to be able to read the variable-sized metadata header (which itself can already be large) efficiently and without expecting EOF directly after it.

Would (header, rest).parse() work?

[hmeine]

The (custom, scientific) image file format I am dealing with basically consists of

1. a metadata header (incl. a variable-sized key/value table),
2. an index table for data chunks (the table size depends on entries in the above metadata table) with several per-chunk properties, and
3. the actual data, referenced by the index table. (Data chunks have variable size due to configurable per-chunk compression.)

I consider even delaying the parsing of the index table until the respective index entry is used, and the actual data should certainly not be read until it is actually accessed, so the (header, rest).parse() is not what I want (unless I am missing something).

[epage]

To clarify, with rest I meant winnow::combinator::rest which will just capture a slice for everything after the header. You can then parse the rest at a later stage.

[hmeine]

Ah, cool. That should come in handy for cases where I have already read in additional data from disk. (Not sure that this is the only way to do it until #299 is tackled, but I have now resorted to explicitly reading parts of the file from disk into bytes.BytesMut buffers and using winnow to parse it from there.)

[ckoehler]

In order of most to least encountered:

• previous fields, usually for some kind of length
• bitfields for sure, we use separate crates for that now
• varint to fixedint is useful (tho I struggle with what type to parse it to, but that's not a parsing issue)
• This thankfully doesn't happen often, but some protocols have fields and structs of both endianness. I haven't had to deal with it, but my team has. :/

We use(d) nom-derive extensively, but I've been enjoying writing parsers by hand with nom, it's more flexible. Even if it was to just implement nom-derive's Parse trait manually.

[epage]

previous fields, usually for some kind of length

I assume this is more in the context on if #234 is implemented? I believe seq! allows access to prior fields but only if they are not ignored. Depending on the data order, length_ combinators can be used when ignored.

bitfields for sure, we use separate crates for that now

We have nom's bits API though I worry about how useful that is.

Could you provide insight into what you are needing for bitfields?

This thankfully doesn't happen often, but some protocols have fields and structs of both endianness. I haven't had to deal with it, but my team has. :/

I assume this is again in context of #234?

[ckoehler]

I assume this is more in the context on if #234 is implemented? I believe seq! allows access to prior fields but only if they are not ignored. Depending on the data order, length_ combinators can be used when ignored.

Not always for TLV parsing, but also (maybe more so for us) to pass into nom's count combinator (i.e. nom-derive's Count attribute) at some later stage, sometimes even inside another struct. With nom-derive, we use ExtraArgs to pass those down into the hierarchy.

We have nom's bits API though I worry about how useful that is.

Could you provide insight into what you are needing for bitfields?

Think IPv4 header, where you get some fields that aren't defined on byte boundaries: 2 bits for this, 3 for that, 14 for another. Would be great to have an easy way to just grab some bits instead of always bytes and then masking out what you want.

bilge lets us define structs with bit boundaries, though we still need to use nom-derive's Map attribute with a Parse along byte boundaries. But this works because most protocols eventually do end at some byte boundary.
E.g. for IPv4, we'd parse a u8 with nom and map that into a bilge struct with two u4 fields, one for version and one for IHL.

With just nom-derive, we'd parse the byte and save it in a field. Then have another field that we actually care about and do something like Value = "bytefield & 0x4 >> 3" and repeat to pull out all the info from that one byte we had nom parse. It works, just isn't very pretty or easily reasoned over.

I assume this is again in context of #234?

Yep. As long as we can say to parse one field as BE and the next as LE, we're good.

[mhedgpeth]

After looking at your toml_edit implementation, I was left wondering when it's appropriate to do the byte-level parsing. I noticed you do an unsafe Vec<u8> into a String conversion in release mode, and I'm sure that speeds it up, but it got me curious what led you there. What are the benefits?

As of now I'm doing char-level parsing from a String and that is quite similar to the byte level, when we're parsing off of ascii utf-8 friendly tokens.

One final curiosity I had while reading your toml_edit implementation was that I saw a lot of constants that surprised me weren't in winnow, for example asking: is this byte an equals?

[epage]

I noticed you do an unsafe Vec into a String conversion in release mode, and I'm sure that speeds it up, but it got me curious what led you there. What are the benefits?

It was for performance. See toml-rs/toml#219

One final curiosity I had while reading your toml_edit implementation was that I saw a lot of constants that surprised me weren't in winnow, for example asking: is this byte an equals?

When you can just do b'=', I'm unsure if there is much of a point. For toml_edit, I was mapping the parser to the abnf grammar. Even if there is an EQUAL constant, I wouldn't have used it. Similarly, I rarely used things out of winnow::ascii.