Kostya's Boring Codec World

First of all I’d like to blame Peter Ross for ignoring this peculiar format from his favourite company. Apparently he prefers to dig Lead instead.

Anyway, as I was scraping bottom of the barrel for FMV game formats to support in na_game_tool (and I still haven’t found good candidates for some letters, a rant about it will come later), I encountered a game called Psychic Detective.

It stores video in large .str files with some external means to signal where a segment starts and what format it has (as it may switch between 160×120 and 320×240 video and 11kHz stereo and 22kHz mono audio).

Audio is bog standard IMA ADPCM, video is while being intra-frame only is much more curious.

First of all, it employs vector quantisation with the same approach as Cinepak: there is a codebook of 2×2 blocks that get scaled to 4×4 output block, there is a codebook of 2×2 sub-blocks used to compose 4×4 output blocks, there are block mode bits telling whether it’s one- or four-vector block, and finally there are vector indices. And for larger (320×240) videos there is even a second codebook that replaces four-vector codebook after a provided line, a lot like Cinepak slices. The main difference is the structure: while Cinepak has more flexible frame structure with chunks for codebook updates, indices and such, here all data is stored in the fixed order with its sizes transmitted in the frame header.

Oh, and there’s another minor detail: frames simultaneously code 8-bit paletted and YUV video (rendered as 15- or 16-bit RGB). This is achieved by transmitting actual palette and duplicating codebook information first as palette indices and then as YUV blocks (so the decoder can decide which one to use). Also YUV to RGB conversion is simplified to look a lot like Cinepak formula as well.

I keep repeating the same thing again and again because it still holds true: those old codecs are much more interesting to look at because sometimes you find out crazy methods like this one.

I keep looking for old games with interesting animation formats and I’ve found another two, from Israeli companies this time.

First is the format used in Armed & Delirious. Since all of the files are in the custom archive (except for a single file with “please change CD” animation) I’m not going to support it, though I still documented it for posterity. Apparently it has two operating modes: updating some lines where each line can have its own coding mode (all are RLE variations) and updating tiles, now with each tile having its own coding mode. The only interesting thing is that tile coding operates on a sub-set of colours so it can use 3-6 bits for index. I remember some formats resorting to 16 colours and 4-bit indices but there are more variations here.

And then there’s VID format used in Soul Hunt and, apparently, some other games by the same company. It features DPCM-compressed audio and depending on version RLE- or JPEG-compressed images (and both versions are present in the game). That’s right, they use code (probably borrowed from libjpeg but I’m not sure about that) to decode data in JPEG-like format (8×8 blocks, IDCT and such) and then use some large lookup table to convert it from YUV to paletted RGB. Of course there are video codecs with such built-in functionality like Cinepak or Indeo 3 but it’s still surprising to see such thing in a random codec.

Update from December 21st: I’ve looked at JPEG-inspired coding again and I have a better understanding what it does (so maybe I’ll even be able to support it eventually):

• there’s intra- and inter-coding, the former operates on 256×16 megablocks (consisting of 32×2 Y blocks and 16 U and V blocks each), the latter has a macroblock update mask and codes only updated macroblocks;
• there are two quantisation matrices sets used in intra and inter mode, the binary specifications calls them “good” and “bad” factors;
• the colour conversion code and IDCT seem to come from libjpeg while coefficient coding is their own invention;
• coefficient coding seems to employ a rather simple set of codes: xxx0 is used for -4..4 values (codes are LSB first), xxxxxx01 is used for larger values, xxxxxx11 is used to code zero runs and xxxxxxxx 11111111 is used to code large values;
• DC prediction is present and works the following way: decode block, dequantise it, add last DC value (and update it afterwards), scale block DC value by 32.

Initially I was discouraged by the coefficient decoding routines being implemented as state machines with computed label, so Ghidra cannot decompile it properly. I.e. it starts with “refill bit buffer” state, then moves to “decode new coefficient having 32 bits”, then it handles one of four cases listed above and moves to “decode new coefficient having 28 bits”, or “decode new coefficient having 24 bits”, or “decode new coefficient having 16 bits” state—unless it decoded the full block and saves that state to keep working from it the next time the function is called. Oh well, at least it turned out to be not that much complicated in the end.

Update from December 27th: I dug a bit more and while decoding macroblock data looks feasible, reconstructing it properly is bonkers, as the game reads quantisation matrices and scale factor for good/bad case from quants.ini text file. So I’m not so sure it’s worth the effort…

In my recent post about na_game_tool 0.2.5 release I complained that I still miss formats starting with letters B, O, W, Y and Z. Well, after an extensive search I’ve managed to find two formats to cover some missing letters.

First is the animation format used in some DOS version of the game Baldies (it’s an RTS game released on consoles as well as on Windows and DOS—and there was even an early Amiga demo apparently). CD with DOS/Windows version employs ordinary FLIC, (floppy?) DOS version and demos used its own animation format instead. It’s rather ordinary RLE anyway in a BAL(d) file as the rest of game resources.

The second game, Los Justicieros (or Zorton Brothers, which is a much better title for my purposes) is much more interesting game. It has a format with various compression methods as well as audio chunks and palette manipulation commands (like fade to black or fade to a new palette). And the compression methods are a mix of RLE and tile-based VQ (in both senses). One method decodes picture as RLE, another one uses RLE on updates to the previous frame, third method either codes whole frame in 4×2 two-colour tiles or codes an update mask first and draws only updated tiles. The fourth method uses RLE on updates as one of the previously described methods, but instead of pixels it codes two-colour 4×4 tiles. Another fun thing is that there are (at least in the version I was able to locate) five files in this format: four of those code one still image and the fifth one codes over half an hour of all video scenes.

In either case it was a very curious format—exactly the reason why I like to examine those old games.

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.