2

I am working on an automatic decode tool for a database like file structure. The file consists of a header and a body. Information that is known before trying to decode the file: Number of rows and size of the body. The files are generally pretty small. 1 to 35 columns and 1 to to 4000 rows.

The fields can be the following:

  • String : one byte for size, followed by the actual string, not zero terminated
  • StringAcii : one byte for size, followed by the actual string, not zero terminated
  • OptionalString : one byte which can be 0 or 1, if 1, its followed by a string
  • OptionalStringAcii : one byte which can be 0 or 1, if 1, its followed by a string
  • Number : 32 bits
  • Bool : Byte with value 0 or 1

There is also a meta data file for each file which contains the number of columns.

My current approach is this: Compute all possible column types, but exit early if I find a combination that never can be possible while looking at the first row. Eg column 1 = bool, where value is 4.

For each possible column combination that is at least valid for the first row, try to parse the whole table. If no errors and all byte are consumed at the end we have a possible candidate.

This works pretty well, but it is way too slow if a table has 25+ columns.I also often get multiple possible schamas. What would be a better way to address this problem? Anything I can do to reduce the number of possible combinations?

2
  • 1
    If the data/metadata files do not contain any information about the schema except the number of columns, then the only way of narrowing down the possible schemas to probable schemas is to apply some form of heuristics. Assuming you know what the files are for/from you should be able to come up with some suitable rules. (e.g. likely range of numeric columns, language used in string columns etc)
    – Ian Cook
    Aug 5, 2020 at 13:48
  • Have a look at the binary templates feature of 010 editor (a commercial but affordable hex editor): sweetscape.com/010editor/templates.html. A trial version is available and might be enough for you.
    – Remko
    Apr 21, 2023 at 7:38

3 Answers 3

2

You're going to have to get heuristic on this I think. My approach would be to generate a parse tree for the first record, where you tokenize the data and create nodes for valid interpretations. Then you apply the tree to the second record, eliminating any invalid paths. Rinse and repeat until you have either a single valid path, or you reach the end of the file. In the case where you have multiple valid interpretations when you reach the end of the file, then you'll either have to output each interpretation, or go back and improve your validity tests. It's not going to be lightning quick though.

Is there definitely nothing else in the header? Do you have access to any code that actually parses these files successfully? It's definitely worth posting one of these files so we can take a look.

1
  • 1
    This is a good answer, especially this point: "Is there definitely nothing else in the header? Do you have access to any code that actually parses these files successfully?" The key point being that, for the programs that were legitimately intended to parse these files, they must know how to decode the structure. How do they do it? The most likely answers are A) they make assumptions about the structure of the file, or B) there is metadata in a header describing the layout. The latter will be easy, the former might require speculative analysis like the first paragraph of this reply. Apr 23, 2023 at 19:01
1

I would start by computing all valid column types for the first byte of every message. First start with the smallest message though. That will restrict your possible sequence of fields the most.

Take the intersection across those types. The correct column type for the first column is in there.

For each column type in the intersection, take the data, remove that column from the start and recurse.

I'd think carefully about what is a "valid" field. Can there be 0 valued bytes in a string or an ascii string?

Post a couple of these files. That'll help us look at ways to infer the format.

Another smart thing you could do... for each row, calculate the number of times you can successfully find a location in that row which is a valid field of type t.

Then for each type t, across all rows, find the minimum number of successful application types. For instance if row 1 has 3 strings and 2 bools, and row two has 2 strings and 3 bools, you would search with the assumption that you can only use up to 2 strings and 2 bool fields.

1
  • the problem is you can't guess the type of the first column without scanning the entire row.
    – Jasen
    Apr 27, 2022 at 21:45
1

You know the number of columns from the metadata file (is that really all it contains? A single integer?). Generate the set of all possible schemas with that number of columns. For each line, parse and validate it according to each schema in the set. If any field fails validation, for example a string containing non-printable characters, you discard the entire schema from the set and start over on the first line with the next candidate from the set.

By testing the optional string and string candidates first for each line you will exit early for the vast majority of candidate schemas, and you will only test the most likely candidates for more than a handful of lines.

A key to this being performant is not doing any validation when actually parsing the data, only when checking it against the schema definition. Otherwise you will end up testing each and every byte in the file several times over rather than just against likely candidates.

Hopefully I explain this in a way that makes sense. If not, please provide an example file-set and I'll give you some example code.

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.