Guidelines for the design of file formats

Fundamentally, text means that some serialization format or character set exists to encode text. The famous ASCII (American Standard Code for Information Interchange) standard covers 128 characters and other sets are not considered ASCII these days. The other famous text encoding is Unicode which has taken up the tremendous effort to cover all used writing systems of the world in one encoding. To serialize Unicode scalars into actual bytes, different character sets can be chosen. UCS-2 and UTF-16 are deprecated, but UTF-32 can be still found. Unlike UTF-32, UTF-8 has the advantage of backwards-compatibility to ASCII and even ISO 8859-1. Furthermore it uses less space to serialize text in common languages like English. Since each character uses one up to 4 four bytes, the same text encoded in UTF-32 usually longer, but cannot be indexed by codepoint in constant time. To summarize: there is a long history of character sets including EBCDIC, Mac OS Roman, Windows-1252, Shift-JIS, Cork, and WTF-8. But with a current adoption above 98% within the World Wide Web, UTF-8 is the de-facto standard (backed by manifestos like UTF-8 Everywhere) and commonly picked as character set for new text file formats. And someone how thinks Unicode is unnecessary for English text, must be considered a bit naïve.

Going back to the question of binary versus text, the result is that some file formats declare that only byte sequences according to the declared character set are considered admissible files; namely text files. This is put into contrast to binary files where any sequence of bytes is admissible per default. Recognize that file formats like HTML require you to declare the character set, formats like PDF allow you to switch character encoding in the file as often as desired, and formats like HTTP headers are so complex that custom RFCs were written. One counterexample is the TOML file format which declares that “a TOML file must be a valid UTF-8 encoded Unicode document” and therefore is a genuine text file format.

One notorious problem with file format definitions is that people think that terms like “whitespace”, “hyphen”, or “line break” are universal, unambiguous names for characters. No, no, and no. Instead the notion of whitespace (more specifically Unicode scalars with Whitespace property), hyphen (more specifically U+002D - HYPHEN-MINUS), and line break (more specifically Mandatory break according to UAX#14) specifically come from text encodings like Unicode.

If you don’t specify the text encoding, I don’t know what those words mean. For Unicode encodings like UTF-8 or UTF-16, I clarified the meaning. If you use ASCII instead of Unicode, everyone understands that “whitespace” means 0x20, the space character as only representative of this group. If you mention hyphen, it is even more unambiguous than the Unicode case, because the less common U+00AD SOFT HYPHEN exists (among others). In the case of ASCII, “hyphen” means 0x2D unambiguously. But in ASCII there is no line break definition at all. Is 0x0A (“line feed”) a line break? Is 0x0D (“carriage return”) a line break? Both? Conventionally, 0x0A is a line break on Linux machines and the sequence 0x0A & 0x0D is a line break on Windows machines. But why is 0x0C (“page break”) not a line break? If you define a page break, you necessarily contribute a line break?! We are never going to know this, because ASCII does not define what a line break is.

If you actually decide to use a well-thought through standard like Unicode, you can answer difficult questions quickly in a standardized way as well: Is Unicode normalization semantically meaningful?

If you don’t specify the text encoding, I literally know nothing about the content. I don’t know what a whitespace character is. I don’t even know what a character is, because I don’t know how many bytes constitute a character.

Some binary file formats and most text file formats have some requirement like “arbitrary user content follows”. In this setting, you really don’t know when the user content is finished. As a result, you are going to need some byte sequence which tells “user content finishes here” which is not interpreted as user content itself. You need to escape the “user content syntax”.

I wrote an article about syntax escaping some time ago, but the gist is this: syntax escaping can be avoided by a length specifier which is only practical for binary files (never let a user count bytes or Unicode codepoints). Otherwise, you can decide to declare one byte sequence to be “escaping”. If you repeat this byte sequence, it regains its original meaning, but otherwise some escaping sequence is started which might signify something like “user content stops here”.

The worst thing, you can do is to ignore the problem. If you allow arbitrary user content, but don’t declare an escaping mechanism, you either open up yourself to ambiguities or violate the requirement “arbitrary user content”. My personal opinion is that XML’s escaping mechanism is simple and extensible compared to other approaches.

File extensions give the operating system a clue which application might be capable of interpreting a file. For historic reasons, they tend to be short (2 to 4) sequences of Latin characters. They are an incomplete concept leading to unintended collisions. For example all kinds of markup syntaxes are declared as .md file these days. Historically .txt used to be full of collisions. But it still makes sense to align all users upon one file extension.

What I would like to stress here as well is the MIME type. It is equally helpful to align all users upon one MIME type. The x- prefix opens up MIME types to custom standards. So text/x-foobar would be a valid choice.

One might think that magic numbers are unnecessary boilerplate. If the specified structure is unique for your file format anyhow, why should a magic number be necessary? The answer is simple: Not all tools want to look at the entire document structure to determine whether a file follows a certain file format. If it only has to read some leading bytes (namely the so-called magic number), they are much quicker to determine whether the file is interesting ^[1]

The simple argument pro version numbers is “implementors can easily dispatch interpretation”. If your document follows the specification 1.0, the source code for 1.0 interprets your file. If your document follows the specification 2.0, the source code for 2.0 interprets your file. This way you can easily introduce backwards-incompatible version changes.

File format design is design. Every design needs iteration for perfection and consistency. Please finish the draft version in a straight-forwards, usecase-centered manner. But be open to improve upon your design in subsequent versions. Iterate and iterate and iterate. And re-iterate again. And ask your target audience about their opinion. Then you mastered the art.

One thing, I would like to point out which comes from programming language design is that design should go from specific cases to generality. What is meant that one can specify very extensible elements in your syntax. But you should define those elements for their specific cases and disallow others. In subsequent versions, you might understand which other cases exist and which cases make sense. Under these circumstances, you might open up that element for more (or more general) cases.

Let me illustrate this with a trivial example: You might have 10 specific cases to distinguish, but you have to use one byte as discriminant. Therefore 256 cases can be distinguished, but you only need 10 cases. Now the general approach to design can be done in the following wrong way:

Instead the following correct way can be taken:

The point of the latter approach is not that “implementor-defined is always stupid”. If you are certain please specify (for example) 10 cases for the desired cases, 20 cases for “implementor-defined” usecases, but be aware that disallowing some values opens up extensibility in future versions. You should restrict your design tightly. Once you gained experience and feedback, you should open up to other cases. Being restricted in the beginning enables the necessary extensibility for later.

There is a simple design which can model any binary data model unambiguously. It is called TLV (Type-Length-Value).

The file format has to follow the general recommendations first. Introduce a magic number. Introduce a version number. Put your metadata in a header. And then let us write down the data in the body of the file.

The body is a sequence of entries. Every entry consists of a type, a length, and a value.

You have to encode a boolean value? Designate a type, length one should always be required, and specify which two values are admissible. Done.
You have to encode Unicode text? Designate a type, the length can be adjusted to the actual byte length, and specify which encoding you require in the value. Done.

This design is very simple and very generic. Does it solve all problems and do all binary files become instances of the TLV design? No. TLV is generic and a very good guideline. However, it applies only to binary files (no human wants to think through a three-step process all the time and particularly count bytes) and binary files mainly exist because they optimize some requirements over text files. Binary files might optimize parsing performance or space usage. As a result, designers start to skip fields. For example, if an entry of type 0x42 is always preceeded by an entry of type 0x41, space-optimizing designers might claim that the type byte 0x42 must be left out. Indeed, position-defined entries do not need a type if it can be derived from the position index. But in this very moment, the TLV design principle is violated and TLV remains only as “general rule of thumb”.

Everyone should be familiar with TLV and follow it for binary files, if ambiguity-freedom cannot be guaranteed for the entire design. A similar design where values usually represent chunks is the Interchange File Format.

When it comes to binary files, endianness is necessary to be specified. Usually deciding upon this value directly leads to the question of target hardware platforms. Endianness can be defined arbitrarily. Big endian or little endian? It is trivial. Just pick one. But the only meaningful way to pick the best value is thinking about the target platform. Does it target Intel machines? Then little endian makes more sense. Are humans going to look at the values from time to time? Big endian might be more convenient, but less optimized for desktop computer hardware.

You should know your target domain, your target audience, and common hardware platforms. But don’t optimize prematurely.

If you start cramming all data into bitvectors to save a few bytes to optimize space, you neglect that machines are optimized to operate on bytes and cache lines. Extracting individual bits is a time-consuming operation. You might be better off adding a few unused bits exchanging space for time.

In the end, benchmarking your prototype parsing implementation reveals the actually interesting parts to optimize. This becomes especially important, if you plan to apply compression on parts of your data.

My final point would be that syntax and semantics are two different concepts. You need to be aware of it. You may be able to use the syntax of an existing standard and define custom semantics on top of it. One example would be XML (syntax) and InkML (semantics). You may also define a new syntax like Simple Outline XML for existing semantics like XML.

I gave examples for text files here, but this also applies to binary files. The only problem is that binary files usually have a very specific data model which differs to other formats. But generic binary file standards include ASN.1 and postcard (introductory talk on youtube).

If you are able to split syntax and semantics, you end up in one of two scenarios:

Not too bad, right?