Kostya's Boring Codec World

In my last post I said something about video compression but now I have much clearer picture in my head so I’d better document it a bit.

So it turns out bitmaps and videos share the same compression methods (just 1 and 3, 0 and 5 are video-only) and they’re even more interesting than at the first glance.

• Compression 0 is simple stream with 8- or 16-bit opcodes with follow-up pixel data. Top two bits mean operation – skip, error, copy, repeat; next bit signals whether actual operation length is 5 or 13 bits; next bits are obviously operation size.
• Compression 1 is tiling compression. Frame data is split into three chunks with first two starting with chunk size. First chunk is bit flags telling which 40×40 tiles in the frame are updated (this chunk can be ignored). Second chunk contains its own tile dimensions and tile metadata (one bit signals that tile is coded, 3 additional bits tell tile type). The last chunk contains tile contents in form of pixels and pattern data. Tile can be skipped, filled with single colour, filled with raw pixels, or it can be filled with 2-16 colours (with all intermediate values allowed) using 1-4 bits as index.
• Compression 3 is LZ77-like and works on two lines at once. It reads a code using static codebook (one for intra-frames, another one for inter-frames), for code 0 is for literal (reads and output two pixel values, one for each line), all other code values are treated as copy length which is followed by offset (and in case of inter frame also direction bit telling if data should be copied from start to end or from end to start).
• Compression 5 is virtually the same as compression 1 but tile type takes 4 bits now to fit operation 8 (copy tile from the same place in some previous frame).

Indeed, this game turned out to have very original formats.

In my recent post about video in Russian quests I said that the Russian adventure games I looked at used standard video formats (except for one game employing custom-modified FLIC). Well, now I can say there’s one game with an original format.

Escape from the Haunted House as its English version is known (unlike the original Russian title which translates to Spectre of the Old Park—because the goal of the game is to escape haunted house naturally) is a Myst or 7th Guest clone which means it should use animations for scene transitions and it has lots of them.

Almost all game resources are stored in a single 600 MB file in a peculiar format: unlike the usual fixed-size record pointing at actual resources, here you have 16-bit tag followed by the tag-speficic data (may be none, may be 1-128 bytes, may be some arbitrary size declared in fixed-size header). And 90% of the data are animations.

Animations by themselves are rather peculiar. First you have a header starting with " AN 0.90" (or some other floating point number), then you have a palette, chunk table and actual chunks. Audio is 5-bit DPCM (one bit for difference sign and four bits to update step index) which actually codes sample as x[i] = x[i - 1] * 2 - x[i - 2] + delta, I don’t remember seeing audio coding like this even if it’s rather simple.

Video coding employs RLE and static codebooks (depending on coding method) and some second pass to output image data in specific form. Nothing really complicated but quite original.

The problem with binary specification was the way it’s written (it’s fun to force Ghidra to decompile a function which it turns back into data because the code is self-modifying), particularly first I managed to locate a function to create those IMV data archives and only then its counterpart for loading data from archive. And after extracting data I found which type corresponds to animations and which functions handle it.

At least this all turned out to be even more original than I was asking for.

Since I had been looking at video files in various games I’ve decided to look at AVX format in Jack Orlando, a Polish adventure game.

The format is not very complicated but somewhat WTFy. It combines audio track compressed with IMA ADPCM and RLE-compressed video. The format is organised into chunks (audio, video, palette update). Sound easy enough?

Well, here are WTFy bits:

• audio violates chunking structure: file starts with 32-bit word to signal this is video file, then you always have ~110kB of audio data (that starts with its own header) and only then you have video header and chunks;
• speaking of which, video frames are packed together with audio chunks so after reading/decoding one you have audio data without the usual chunk header (you can have standalone audio chunk of course);
• oh, and another thing—the video file header seems to list number of audio frames (which is usually several times larger than the number of video frames);
• another fun fact about video header: it may occur several times throughout the file;
• and another fun fact: while the format is paletted, palette can be either 24-bit (I’ve seen that only in intro) or 16-bit (all other files, which are predominantly short game over animations). And by 16-bit palette I mean 256-colour palette with actual colours represented in RGB565, I’ve never seen that before;
• as a cherry on top of that sometimes chunks start earlier or later than you’d expect from declared size.

And if you thought video compression would be sane, think again:

• actual data is compressed in two passes: first it groups data into coded segments in the form (1 byte - number of skipped pixels, 1 byte - number of coded pixels, 0-254 bytes - actual pixels) and then all that data is RLE coded (0xFF – escape flag after which run value and run count bytes follow, otherwise byte value should be copied as is);
• since this is too easy it also uses pixel value 0 as skip value;
• plus there’s a global offset in the beginning of the chunk telling from which pixel to start decoding;
• plus there are two video chunk types that seem to differ only in one header field being missing in one of them;
• and the actual video is 640×480 but it is coded as 1024×480 with right part of the frame being blank.

Some game formats are interesting but this one borders with being unbearably interesting.

Since I need some distraction from VGM-XVD formats, I decided to look at some simple game format and somehow my eyes turned to Fable. This is a point-and-click adventure from 1996 from a studio that made only this game. Overall it could’ve been better with a better beginning, no whiplash-inducing ending and no aliens in the premise so it does not resemble a bad imitation of Might and Magic series.

Anyway, the game contains three videos: 50-second logos+opening, 3-minute intro and 50-second ending (it may be different for North American release but I’ve not seen that version). And the compression employed there turned out to be interesting.

It looks like they took PCX RLE for the inspiration but they made it more complex: depending on top bits you can have run, skip or raw copy. And raw copy is where it gets interesting. During decoding of the whole video file the raw pixel sequences are added to the special buffer which can be used later to copy pixels from. This reminds me somewhat of VPx golden frame which could be updated in some versions with fresh decoded blocks and referenced even many frames later.

And here is why I like to look at those old formats—they sometimes offer an interesting coding approach while modern codecs seem to be made from the standard blocks.