2

I want to parse a binary file and track the values and positions of certain properties within it. Reading them is not that much of a problem, since I know the rules they follow in terms of where they are in relation to each other. Most of them have their offsets written in the file, anyway.

To allow editing or extending some of these values, I would need to adapt and update the positions of other values, that might follow or point to these as well, which made me think of arranging the different properties in a tree, where a parent node is a value which can influence the value or position of it's children.

For example:

Imagine a list of offsets into the file, describing a couple of data blocks. When I want to add a data block in the middle of the original ones, I need to update the list, but also change the offsets of the original data blocks, that follow my inserted one, in the first list.

I feel like that is a solved problem and I just don't know the terms to look for, so I hope I made my problem clear.

Adding some more information:

I'd like to avoid parsing the whole file, since I'm not familiar with all rules (it's an NES rom, so there is also code and graphic data in between other things).

What I do know, though is, for instance:

  • there is a list with offsets, which point to the data of different world maps
  • the world map data has a list of row positions and column positions which mark the position of levels on the map
  • those positions give an index into a list of level offsets, which in turn point to the layout of the specific level

So let's say I want to move the position of one level on the map, then I would need to update its row position, for example, and in turn maybe its position in the level offset list.

Or if I want to make one level bigger and change the offsets of all the following levels, I need to adapt the offset lists of the worlds these levels are in.

I wonder how to best model these interdependencies so that they can work in both directions.

4
  • I took the freedom and made the question title match the question text. Asking for general (braindead) patterns here often encourages the community to close such questions as "too broad/needs more focus". Please check if I got your intentions right.
    – Doc Brown
    Dec 23, 2019 at 10:12
  • @DocBrown I just wanted to avoid a "what's the best way"-question. Works, very well. Thanks :)
    – Minix
    Dec 23, 2019 at 10:13
  • There are several "randomizers" out there for various NES games (Zelda, FF1, among others). You might try seeing if any of them have github pages or otherwise make the code public, as this sounds very similar to what you want to do
    – mmathis
    Dec 23, 2019 at 13:57
  • @mmathis While those don't necessarily include adding values and changing the memory layout, that is nonetheless a great idea. Thanks :)
    – Minix
    Dec 23, 2019 at 14:32

2 Answers 2

3

I don't think there is a named "pattern" for your specific problem. Instead, let's focus on solving your problem.

The first approach which comes into my mind here is to

  • read the binary file fully into a suitable data structure where no offsets are required (for a example, a linked list of data blocks, where each data block is an array of characters or bytes or a specific data structure itself)

  • apply the manipulations to this data structure like inserting a new data block into the middle of the list

  • write the data structure back to its binary representation (recalculating any offsets required)

So as a general strategy:

  • use data structures which avoid redundancies and allow the manipulations your situation requires in a suffciently efficient manner

  • if redundancy cannot be avoided, use data structures where redundancies are encapsulated into a few central places and updated automatically.

    For example, a "data block" could be an encapsulated data structure which always knows its total byte size in its binary representation (like most modern string classes), which will make the offset calculation more efficient.

7
  • I can't parse the whole binary file, since I don't (yet) know all of its internal rules (I updated the question accordingly) and I think this "suitable data structure" is exactly what I'm looking for. I could imagine that a tree would lend itself to the many lookup-table like lists in the rom, which need updating based on the positions of the data blocks. But modeling this inter-dependency got me stumped a bit.
    – Minix
    Dec 23, 2019 at 10:20
  • @Minix: What I wrote may still work when you do not parse any data block, just read it into a binary array without changing it. But beware, if there are hidden dependencies inside a data block which are required to be updated as well, there is no way around analysing the file format to the point where you understand those dependencies.
    – Doc Brown
    Dec 23, 2019 at 10:23
  • I updated the question again, giving a specific thing I want to do and where I'm struggling to come up with something. I hoped keeping it general, would yield a general solution, but I guess I wasn't specific enough to explain myself properly.
    – Minix
    Dec 23, 2019 at 10:31
  • @Minix: my answer does not change - pick a suitable data structure which avoids and encapsulates the redundancies and convert the data to it before manipulating it. Which data structure that is in your case is what you have to work out for yourself, this is the hard work which requires diving into the details. As an idea: maybe you can convert some absolute offsets to relative ones, so moving blocks won't require to change most of the relative offsets.
    – Doc Brown
    Dec 23, 2019 at 11:47
  • This answer seems to assume that the file fits into main memmory.
    – lijat
    Dec 24, 2019 at 11:04
0

I feel like that is a solved problem

Yes, it is. The file contains a linked list, and the offsets are the pointers from one list element to the next. The only difference to your vanilla memory based linked list implementation is that you need to explicitly dereference your pointers, aka file offsets.

As such, inserting something into this file based linked list works the same as for the vanilla linked list:

  1. You identify the position where you want to insert the object using a double pointer, aka the file offset of the file offset pointing to the list element before which you want to insert your own element.

  2. You allocate and initialize your new list element, initializing its next pointer (aka file offset) to the value behind the double pointer (single dereference) you got.

  3. You change the value behind the double pointer (single dereference) to point to the new list element. I.e. You write the file offset of the new list element at the position indicated by the position identifying file offset.

Pseudocode using C syntax:

//`position` is the result of step 1
void insert(Node** position, Stuff content) {
    //step 2
    Node* newElement = allocateFileSpace(sizeof(Node));
    initializeNode(newElement, content);
    newElement->next = *position;

    //step 3
    *position = newElement;
}

You only need to replace each dereferencing operation (* or ->) by the respective file offset based access.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.