How to simulate a seek() when binary parsing?

[landaire]

I'm developing a parser for a binary format using winnow that has a layout kind of like:

struct Chunk {
    identifier: u32,
    size: u32,
    data: &'input [u8]
}

The data chunks in some scenarios can be extremely large -- like 1.5gb. I'm developing this parser in a sans-io manner with a LocatingSlice<Partial<&[u8]>> stream so I can facilitate both wasm and desktop environments. On desktop these large chunks are mostly no biggie because I'm just going to mmap the file and call it a day.

In my parser I'd like to be able to essentially skip() over these bytes without reading them. I'm aware that I can take(N).void().parse_next(input), but I'm weakly confident that this would thrashing the Partial<&[u8]> buffer and cause the upper state machine to think it needs to fill a buffer with N bytes for reading, when in reality I just need to simulate a seek.

Is there a recommended way to handle this type of scenario?

It's worth noting:

1. I've never written a sans-io parser before
2. I've never had to do file operations In WASM before
3. I've never used winnow as much as I have for this project (I've used nom but not with a similar scenario).

[epage]

Partial parsing is very context dependent. I'm going to make some guesses but and we can see where your situation diverges.

It sounds like you are dealing with a file format made of consecutive Chunks and you want to skip over some chunks while processing others, effectively making the data a Vec<Chunk>. I'm assuming datas length is recorded in Chunk::size.

Let's then split up the data:

type File<'input> = Vec<(ChunkHeader, ChunkData<'input>)>;

type ChunkData<'input> = &'input [u8]

struct ChunkHeader {
    identifier: u32,
    size: u32,
}

I recommend this model of data processing because

• ChunkHeader is a fixed size you can request from the stream
• ChunkData is a fixed size and so you can request from the stream

You can then skip ahead to future chunks without reading in all ChunkDatas as this is now being processed outside of your parser. This then makes the data not need Partial.

Now, you mentioned ChunkData can be large, so maybe you don't want to load all of that into memory at once. Since you didn't mention a data model for ChunkData, I'm assuming its a more general buffer that you want to seek within. The situation is not too different from before as you can leave the processing of ChunkData to outside of your parser.

If there is a data model for ChunkData that you are needing to process, then more information will be needed. In general, I try to focus the conversation for partial process on what parts of a frame are fixed sized, length-prefixed, or delimited.

[landaire]

You can then skip ahead to future chunks without reading in all ChunkDatas as this is now being processed outside of your parser. This then makes the data not need Partial.

But since ChunkData is an &'input [u8], that implies that the data is resident in memory no? Am I missing something? Let's assume that this is not a streaming scenario and I can freely seek around the buffer. The file format is a container format where there's gigabytes of data at the start, followed by the file entries at the end of the file.

Here's a rough diagram:

   ┌───────────────────────┐                
   │       Header          │                
   ├───────────────────────│                
   │                       │                
   │     Additional        │                
   │      Metadata         │                
   │                       │                
   ├───────────────────────│                
   │                       │                
   │                       │                
   │                       │                
   │                       │                
   │                       │                
   │    Casual 1.8GiB      │                
┌─▶│       of data         │◀─┐             
│  │                       │  │┌───────────┐
│  │                       │  ││ File Meta │
│  │                       │  ││has offset │
│  │                       │  ││ into data │
│  │                       │  ││   chunk   │
│  │                       │  ││           │
│  ├───────────┬───────────┤  │└───────────┘
│  │ File Meta │ File Meta │──┘             
│  ├───────────┼───────────┤                
└──│ File Meta │ File Meta │                
   ├───────────┼───────────┤                
   │ File Meta │ File Meta │                
   └───────────┴───────────┘                  

I don't know why I didn't just link to the code. Don't judge, I'm in the heavy prototyping stage :p

Here's my chunk reader: https://github.com/landaire/enfusion_tools/blob/f538e386f986392563ccdf67e52044540069c16a/crates/enfusion_pak/src/parser.rs#L397-L412

And here's my main processing loop: https://github.com/landaire/enfusion_tools/blob/f538e386f986392563ccdf67e52044540069c16a/crates/enfusion_pak/src/parser.rs#L207-L226

And here's an example of where I have a huge amount of data to skip over: https://github.com/landaire/enfusion_tools/blob/f538e386f986392563ccdf67e52044540069c16a/crates/enfusion_pak/src/parser.rs#L269-L280

For now I ended up describing these chunks as having a Range<usize> describing the memory range of the large data.

Something I'm still not really understanding though -- and this is probably on me for not explaining too well -- i how to notify the upper layer of the stack to skip N bytes.

To better explain why this is the case, let me give a pretty strict example. Let's say I have two parser modes -- one where I fixed-size buffer dedicated to the parser of 20MB which backs the Partial data, and another where the stream is just a Partial backed by an mmap'd file. I'm parsing and I come across a data chunk that's 1GB. With an mmap() model this is pretty easy right:

fn parse_data_chunk(input: &mut LocatingSlice<Partial<&[u8]>>) -> WResult<Chunk> {
    let data = length_take(be_u32).parse_next(input)?;

    let chunk = Chunk::Data {
        data,
    };

    Ok(chunk)
}

When I try to handle this in my 20MB fixed buffer scenario, that length_take(be_32) is going to return an ErrMode::Incomplete error right? So the upper layer of the stack is going to get an ErrMode::Incomplete(some_byte_count) which implies the data is needed right now.

What I really need is just to say "hey, align yourself N bytes forward so you can begin processing the next chunk".

How I've done this now Is my parsers return a (usize, Chunk) where the usize is the number of bytes to skip. I really don't know if this is the best way of going about this, and this right here is the problem I'm trying to solve.

[epage]

How I've done this now Is my parsers return a (usize, Chunk) where the usize is the number of bytes to skip. I really don't know if this is the best way of going about this, and this right here is the problem I'm trying to solve.

I think this is a flavor of what I was recommending. Instead of a strictly hierarchical parser where there is a Top Level Format, Subdivisions, Sub-subdivions parsers to instead give the caller the choice of what to do at each stage by having a parser for the header before data and the footer after it. The caller can then choose to progressively read data, load all of it at once, or seek ahead.

[landaire]

I figured there wasn't a one-size-fits-all solution, but I didn't know if I was footgunning myself by doing it this way.

Thank you @epage for the insight! I appreciate you taking the time to analyze my scenario.