Kostya's Boring Codec World

Since I had nothing better to do and remembered about one mostly finished format, I decided to add its support to na_game_tool. The game in question is called either Cydonia: Mars – The First Manned Mission or Lightbringer (with two variations of sub-title).

The main problem is that there may be different audio and video formats inside but you cannot easily detect them. The header contains only the dimensions (which can be any as long at it’s 640×320 as the game uses hard-coded dimensions in the decoder), number of video frames (also rather pointless as it does not really affect anything) and audio present flag (the only useful information there).

First annoyance is audio format detection. The simplest solution I could devise is looking at the first audio block size and depending on its size setting the format (22050 bytes means 11kHz mono, 44100 bytes are for 22kHz mono and 88200 bytes are for 22kHz stereo). As long as you don’t encounter those extra-short files with a single audio block of different size you should be fine.

Then, video. Game demo (and maybe some versions of the full game) uses paletted video while the full game (at least the version I could find) uses 16-bit video instead. So if you discover palette chunk before video it must be a paletted format. At least the compression schemes remain the same.

And what do you know, video compression is also annoying. Both compression methods employ LZ77-based algorithm with some variations. Method 3 always decodes 640*320 bytes (or twice as much for 16-bit video) and employs an additional code for leaving data unchanged from the previous frame. Method 2 uses the same coding method (minus the “keep previous data” code) to code inter frame data of variable length (without an end code apparently). Essentially if the next 24-bit code is a valid offset (which is coded as x+y*632) then copy a block from the previous frame at the given position, otherwise decode block data (64 or 128 bytes depending on bit-depth). As I mentioned before, you don’t know compressed data size beforehand and you don’t have end-of-stream marker so you have to decode the needed amount of data as you paint the frame.

Overall, this is rather interesting video compression scheme but Paco also serves as an example of how not to design a container format. This reminds me of RoQ hack where the game engine used slightly different decoding mode if the filename was in a special list. And Nova Logic KDV but there it were different flavours in different games at least.

I’ve written a decoder for Ratvideo (and documented it as well). So why it’s not done? Because apparently it’s VIDPAK (from the creator of DIGPAK John W. Ratcliff—hmm, I wonder if his name has anything to do with the format name) so it’s a different thing that had been done. And since the format was created by an EA programmer for use in EA games it’s definitely Peter Ross’s fault for not REing it.

So the runtime-generated table turned out to be code for masked update and inter-coding mode proved out to be a fixed-size mask telling which pixels to update plus the values to update it with. Mentioned in the previous post mode with duplicating lines turned out to be an alternative coding mode where each next line uses a previous one as the reference, so that previous line is copied and updated depending on the mask. That’s another case where you need to look at the disassembly instead of what decompiler provides (if it manages to produce something in the first place) but the code is almost trivial.

I’m not going to look at any more game formats in the near future (unless some come to my attention), so it’s just boring stuff for me for now.

While I saw this format mentioned in dexvert unsupported formats, I ignored it for confusing with RatDVD. And apparently it’s not me who should’ve paid attention—since it’s a format used in some of EA games (like SSN-21 Seawolf or Kasparov’s Gambit) it is Peter Ross who should’ve looked and REd it by now.

While the format is rather simple, it is still rather curious. Audio data seems to be coded using a mix of RLE and ADPCM (i.e. it allows coding a run of the same sample value or deltas that are scaled depending on the previous delta code value). Video can be coded as simple frame (raw or RLE) or split into two parts (each may be raw or RLE as well) and assembled back somehow. From what I see it uses one buffer as a source of pixels and another one as opcodes stream and invokes a runtime-generated code for those opcodes. So I’ll need to find out what gets generated first and then translate it to more conventional operations. Though I expect it to be something rather simple like telling how many pixels to skip. There’s another mode which seems to use flags to tell which lines of the previous frame to duplicate but could misunderstand it (after all, the standalone player code supports additional features like scaling during playback).

Of course I intend to document it and add this format support to na_game_tool eventually.

I tried to look at it before but since the game uses that special 32-bit DOS extender (PMODE/W if anybody’s curious), I gave up. As I mentioned in one of previous posts, I need either to find a way to dump unpacked and properly loaded executable reliably or write such decompressor from the binary specification—and I’m not eager to do either of those things.

Luckily somebody bothered to decompile the engine in order to make game work on modern OSes without DOS emulation. I use the term “decompile” because a lot of the parts are slightly prettified direct translations of the assembly. Anyway, this can be improved and it probably work good enough already to make game fans rejoice.

Here’s the decompiled cutscene player and what follows is my understanding of the code given there.

So, HAF files start with 16-bit number of the frames followed by two tables, one byte per entry each. First table contains sound effects that should be played starting at that frame (or zero), second table gives frame duration at 70fps. Then actual frame data follows: 16-bit frame size, 768-byte palette and then LZW-compressed image. And looks like they lifted LZW compression from GIF as it’s not only the basic parameters of LZW compression being the same (dictionary size limited to 4096, having restart code and arbitrary initial number of bits) but also LZW data is packed into chunks prefixed with its size. I can’t outright remember any other format doing that—or having a need to do that when total data size is known beforehand.

Maybe I’ll add support for this format to na_game_tool eventually but I’ll find something else to do for now.

This British company had developed quite an amount of good games itself and published even more. As I mentioned in one of my previous posts, I’d like to take a look at some of those (after both seeing their games mentioned in dexvert unsupported formats and realizing that I’ve unknowingly added support for some other games to na_game_tool already). Though I’ve REd the most important format of them all, BMV, long time ago from ScummVM code (their code is still slightly prettied direct conversion of assembly into C++).

Alien Breed

Since this game comes from a wormy developer, its ANM files for the PC version in reality are mere AVIs using KMVC. They don’t play with my old decoder so I’ll have to look what’s different in that version.

Chronicles of the Sword

Fun thing is that most of the game resource files have .PC extension regardless of the type and content. But here I’ll talk about SEQ/*.PC of course.

Those files expose rudimentary chunk structure i.e. they have three short chunks with some basic metadata and frame sizes in the beginning but that’s all. The rest seems to be frame data starting with frame dimensions and image data size (if VGA palette follows it seems to be unaccounted for).

I’d like to take a closer look at it but it’s too annoying: the executable uses CauseWay DOS Extender with packed 32-bit part so I either need to learn how to dump it or RE the extender code to see how it unpacks the code (the trick I used for the next game didn’t work). In either case I’ll postpone it until I’m sufficiently bored and really out of ideas what to do.

Microcosm

This games uses the simplest yet still rather weird codec: scalable RLE.

What do I mean by that? It employs several methods of compression, all are rather simple variations on RLE, except that some have “masked update” opcode beside the usual run/copy/skip. That opcode is a bit mask telling which ones of the following 7 or 15 pixels should be updated with new values or left intact.

But you probably wondered more about the “scalable” part of the description. Well, that format actually codes four 80×200 images per frame (each one may use its own method) and then interleaves the columns. And if you’re not satisfied with the spatial scalability only, it has temporal scalability as well: every even frame is coded independently (i.e. frame 2 updates frame 0, frame 4 updates frame 2 while frame 3 updates frame 1 and so on).

Also it stores palette in BRG order for some reason, which I don’t remember seeing in any other codec—unlike 2-pixel RLE (IIRC I was surprised to see such approach in some ARMovie codecs but it turned out to be not that rare after all).

This format was surprisingly hard to reverse engineer not merely because of its five different coding methods but also because its binary specification is somewhat inaccessible. The executable uses Phar Lap DOS Extender with compressed extended part. I did not know how to approach it until eventually I managed to use dosbox-x debugging facilities and dump what turned out to be the unpacked 32-bit part, which I could later load in Ghidra as raw 32-bit binary and find proper decompression routines. No such luck with the previous game because it seems to load the code into XMS and I don’t know if it’s possible to dump that part of memory at all…

In either case this codec will be supported in na_game_tool 0.2.0 and I can finally start forgetting about it (but not before documenting it in The Wiki).

Novastorm

This game uses a rather curious approach to the video coding—it treats all blocks as being coded with 16 colours plus mask and during video decoding it updates current colours (often by reusing them from some previous block) and mask. And then the draw routine uses those per-block colours and mask to reconstruct it.

Of course you can have fewer colours but it’s an interesting approach. “You want fill block? Just replicate this colour sixteen times. You want two-colour block? Just copy/read two colour values and (optionally) update mask using just 1 bit per cell. And yes, some opcodes tell you to read the full mask for the block while others tell you to read first a mask that tells you for which block rows the mask is actually transmitted.

What about inter coding? The skip mode is simple: you have a fixed-size array of flags telling you which block is coded and for which operations should be skipped.

So it’s a bit hairy to implement and I left that for later.

WipEout

This one is somewhat funny—it uses IF chunked format (i.e. just two bytes per chunk name and 16-bit chunk size) and seems to pack frame data with an LZ77 algorithm before actual video decompression kicks in. The scheme seems to operate on nibbles as some of the opcodes are “fill 32-bit word of output with 0x44444444”, “XOR 32-bit word of output with 0x00F00000”, “replace top/bottom three nibbles of 32-bit word with 0x777” and so on. Also there’s a post-decoding image permutation step (and in case of one mode, it seems to use raw image that gets pre-permuted just to permute it back to the original state in the end; I haven’t looked too closely but it looks suspicious).

Another curious thing is that it has a table of 32-bit values transmitted at the beginning of each frame with several opcodes to copy that value to the output.

Overall, it’s an interesting codec and I’d like to have decoder for it implemented for the upcoming na_game_tool 0.2.0 release but it’s too hairy for that. So it also goes to my “what to do when I’m bored and can’t think of anything better to do” list.

As you can see, I have not done much but even a cursory glance at those formats show the variety of approaches to video coding that you cannot see in the modern codecs. And that’s why I like looking at old formats.

P.S. With the intended amount of decoders implemented I hope to finally release na_game_tool this weekend. There should be a follow-up post about it soon (and then probably just occasional rants for long time).

…as I’ve seen so far, of course, but the chances for it to keep this title are good.

I’m talking about XCF format (found in ACF files of Time Commando game developed by Adeline Software). For starters, the format allows various commands that are related to the engine (so XCF is used not merely for videos but also for the stage demo records containing e.g. commands to the camera and various other things.

But there’s nothing compared to the video codec design. The frame is split into three parts: fixed-size part with per-block 6-bit opcodes and two variable-length parts. I’d like to say that one contains colour values and another one stores masks and motion vectors, but in reality either kind of data may be read from either source and it’s not consistent even between modes (e.g. for four-colour pattern block both masks and colours are read from part 1 while for two-colour pattern block colours are read from part 2; it’s like they designed it on whatever registers were available in the decoding function at the moment). And for some reason they did not went further and left those frame parts uncompressed.

The real monstrosity though is the opcodes. As I’ve mentioned, they take six bits which means 64 different opcodes. And unlike many other codecs where you’d have half a dozen operations (copy from previous, fill with 1/2/16 colours and such) plus run count, here you have way more. Also it uses 8×8 block size which helps adding new modes. Here’s an abridged list:

• raw block;
• skip block;
• motion block with one-byte motion vector (using nibbles for vector components), two-byte absolute offset, two-byte relative offset or two-byte motion vector;
• motion block with each quarter using the same four modes;
• single value fill block—and another mode for filling block quarters;
• 2/4/8/16-colour pattern block;
• 2/4/8-colour pattern block quarters;
• special 4-colour pattern subblock coding mode where you can pick only one alternative option and only for half of the pixels;
• block filled with mostly single colour except where mask tells to read a new value;
• block with values coded as nibble-size differences to the base colour;
• block coded as two base colours (high nibble only) plus low nibble of the current value;
• block using RLE plus one of four scan modes (line scan, top-down scan, zigzag and inverted zigzag);
• block using the same scan modes but sending only nibbles for the colour values (first nibble is for base colour high nibble, others are used to replace its low nibble).

And that’s not all, some modes (e.g. motion or fill) have refinement mode. E.g. opcodes 1-4 all mean skip block, but while opcode 1 means copy block from the same place in the previous frame and do nothing, opcode 2 means doing that and then replacing four pixels at arbitrary positions with new values, opcode 3 means the same but with eight pixels, and opcode 4 means using a mask telling which pixels should be replaced. It works the same way for other opcodes supporting it—first do the operation, then optionally update some of the pixels.

If you thought that peculiarities end there, you’d be wrong. Motion vectors are a displacement from the centre of the block instead of its top left corner as in any other video codec. And looks like while the format stored video dimensions, the decoder will work with any width as long as it’s 320 pixels.

I don’t envy future me who has to document it for The Wiki.

P.S. And what’s ironic is that the game was released between Little Big Adventure and its sequel, and while the former used custom format with FLI compression methods (and commands to play external audio), the latter switched to Smacker—a much simpler codec but apparently more effective.

P.P.S. After I reverse engineer a codec or two from games published by Psygnosis I should publish a new version of na_game_tool and switch to actually documenting all the formats it supports; and then do something completely different. At least the end is near.

Since I’m still in a search of video formats for my na_game_tool, I happened to look at Jagged Alliance: Deadly Games and found an SMS file there (and then more for a demo version of Nemesis: The Wizardry Adventure).

The file starts with BLAH magic followed by two sizes, some table and audio data. And after audio data there’s a suspiciously familiar SMK2 signature. And indeed, the file from that point plays fine as Smacker video.

Of course this reminded me of a game Ripper, released in the same 1996 apparently (but by a different developer and publisher), which had AVI format that encapsulated Smacker of FLIC along with an audio track external to the format.

Why such combination needed to exist? I feel that the main actor in Ripper expressed the answer to that the best. After all, Smacker supports up to seven audio tracks and other games of that period played Smacker video and audio just fine; it should allow seeking even if nothing seems to have ever used that feature. Maybe it really needed more cowbell.

I’m still picking unfinished and half-finished format for na_game_tool and there were some from Access games. While supporting animations from Amazon: Guardians of Eden is rather pointless (since they simply update pixels on some scene and do not have own palette), supporting H2O and PTF formats is more interesting.

I wrote about them back in the day and about H2O specifically. And since it was a quick look and my eyes are not that good, I missed some details. But as I finally implemented a decoder for it, now I can correct that story.

As it turned out, H2O stores video data as Huffman-coded 16-bit values instead of usual bytes. And those values are used for both opcodes and colours. If top four bits of opcode are 0-3 then the top byte codes number of 4×4 blocks to process and low byte is fill value (0 means skip block instead). If top four bits of opcode are 4, then low 12 bits are number of blocks to process minus one and each block data consists of 16-bit pattern and two colours (packed as another 16-bit value). Top four bits of opcode being 5 mean partial update for the specified number of blocks, each block having 16-bit update mask and 0-16 colours to update (packed in 16-bit words).

So while the format is no ground-breaker, it still turned out to be more interesting than I expected it to be.

P.S. I guess I’ll do a bunch of FLI-based formats next. There are some curious variations of it like FLI with audio or RNC ProPack compression.