Kostya's Boring Codec World

In my previous post I said I was looking at them and while some details were unknown, I got some understanding.

But it turns out The Multimedia Mike despite what he claims still hasn’t lost the knack for REing codecs—first you need to look if somebody else has done it already. And indeed, somebody else has spent two years on reverse engineering the codec. So all that was left to me was to improve its description it (which I did).

The video compression there is quite curious. Huffman-coded data chunks are not that rare (Truemotion 2 had them, for example). Huffman-coded data chunks where one chunk has tree description coded in the beginning that is used for several other chunks is more interesting. But the transforms was the juiciest part there. It turns out you have several modes of operation: fill block, raw block, smoothed DC block (that one uses DCs from neighbour blocks on all sides to create a smooth transition between them all) and the actual Adaptive Orthogonal Transform that represents block as 1-5 patterns (scaled), selected from single matrix. It reminds me a bit about SVQ1 where you had a block constructed from 2D patterns of varying size. But even more it reminds me of Matching Pursuit experimental video codec from Berkley University that also performed partial transform and selected only some bases from a large set (does anybody remember this codec at all?).

Nightlong FMV is a bit different. The format is simple but FMV2 has packed frames and there was no code for handling it in 68k version of the binary. Nevertheless I could unpack it simply by dumping frame data and extracting it with unar (PowerPacker is a strange compression format BTW, it starts reading data from the end of buffer and outputs data starting from the end as well). The unpacked data turned out to use the same format except that the frame size is now full 640×360 instead of 320×180 trying to look like twice as large. I documented it as well.

P.S. I still have some stuff to look at but more suggestions are always welcome.

In a recent post I asked for some stuff to RE and I got some (but more pointers are welcome).

Among those two there was H4M format for Gamecube (kudos to The Mike for providing me with the samples) and FMV format (yes, that’s the extension as well) for Nightlong game on Amiga. This finally gave me a chance to look at how Ghidra 10.0.1 fares with such exotic executables.

First I had to install special loaders for the executable formats (and hack their manifests to claim it’s for 10.0.1 and not 10.0) and also ISA support for special PPC extensions for Gamecube PowerPC CPU. After that it was just loading binaries and analysing them. And there’s nothing else to write about it, it just works.

Now some words about the formats. I’ve not fully REd them (and I don’t know how much time it’ll take either, it all depends on weather and mood) but there are some things I can say about them already.

FMV is a fixed 320×180 paletted video with 4×4 tiles. The compression is very simple: you can either have a raw 4×4 tile, sub-divided 4×4 tile where you can have only some pixels in 2×2 block updated, or skip command (for a single block or for rows). There is also fmv2 where each frame seems to be further (or instead?) compressed with PowerPacker (at least that’s how I interpret frame data starting with PP20).

H4M seems to be a rather advanced format. From what I see it has small frames combined in large blocks with each block having a previous block size stored as well (for seeking backwards like FLV, I suppose). Audio codec looks like a typical speech codec on console. Video codec looks interesting: it has B-frames for starters and it’s definitely not a H.264 rip-off. From what I could gather, it codes several data sources in the frame (i.e. each kind of data is stored separately and not interleaved with the rest of data), some of those data sources contain Huffman-packed data, others are used just to read plain bits and bytes (yes, I saw only functions that read single bit or eight bits, nothing else). Then the data from those sources is used to code coefficients and zero runs for the whole planes (I’m not sure yet if it has blocks at all).

I’ve looked just at I-frame decoding, no reconstruction or P/B-frame decoding yet, but what I’ve seen already makes it a very interesting codec to examine. I was asked to look at it many years ago but I declined that request since I had little experience with both PowerPC assembly and the executable format Gamecube uses (the only time when I looked at PowerPC assembly was Fruity Intermediate Codec and even then IIRC I finished REing it only after x86 binary became available). Now thanks to Ghidra with its decompiler and enthusiasts providing support for such fringe formats I can look at such formats too.

Back in the day I’ve stumbled on a post called Archaic Video Compression Algorithms of FMV Games Era (in Russian) giving a concise review of VGA era video. For a long time I wanted to discuss it but I lost the link to it and managed to locate it just recently.

For those unable to read Russian here’s a gist of it: all the variety of those formats used just three methods to compress video, those methods being lossless redundancy removal via RLE or LZ77-based method (Huffman codes not employed), vector quantisation, and block truncation coding. Inter-frame compression was rather primitive, often without any motion predictions; fade-ins/outs were not handled either. And later, when computers became powerful enough, everybody switched to DCT coding and later to in-engine animation.

It is a very good first approximation but as a person who looked into several formats myself and even documented a couple of them, I have something to add or correct.

First of all, ‘archaic’ means something not merely old but also not in common use—and that does not apply neither to LZ77 (which is still the base of most of the practical compressors and archivers; and there’s WebP using its variant in lossless mode) nor vector quantisation (even if it’s mostly employed in texture compression nowadays).

Second, I consider block truncation coding to be a specialised form of vector quantisation for a case of two colours per block. And considering that the input data could be palettised already it’s more likely the encoder searched for the most fitting two colours in the palette instead of generating two RGB triplets and handing it all to the palettisation process.

Third, I’d argue that back in the day codecs did not need sub-pixel motion compensation and motion vectors were often not needed since you could simply code an offset in LZ77 compression. And some of the codecs allowed copying data from either already decoded parts of the current frame or some not yet touched part (or any part in some cases) of the previous frame. This archaic method of copying from already decoded part of the frame is present in AV1 for example (under IntraBC name).

Fourth, I think that recursive block division deserves to be mentioned there.

A minor nit would be that even if very few codecs supported explicit fading, a lot of them had support for palette change event (partial or full). Yet it mostly depended on people developing the format and the encoder for it how well it was handled.

So in my opinion the final list of the techniques most FMV games of the VGA period used should look like this:

• lossless data compression with RLE or LZ77-based method
• vector quantisation—both whole tiles and inside single tile;
• recursive block splitting (either horizontal/vertical or as a quadtree);
• and fullpel motion compensation usually done by skipping pixels, blocks, or reusing some already decoded region.

And typical video codec of that era should look like one of those two:

1. line-based codec employing RLE, probably with skips for inter-frames and optional LZ77 compressing of whole frame data afterwards (or extending LZ77 approach to work with the forward data in the buffer as well);
2. tile-based codec usually working with 4×4 tiles, employing vector quantisation to paint the tile with 1-8 colours, sometimes sub-dividing tile for better detail preservation, sometimes having a dictionary of tile configurations, sometimes even employing block-based motion compensation; those codecs usually employ 1-4 byte opcodes to code the tile type of whole sequences of tiles of the same type.

Of course there are deviations from those two schemes but the majority of game codecs of that era should follow either of those two designs.

Later, as the original article said, those codecs were supplanted by DCT-based ones (I’ve seen the ones based on MJPEG and MPEG-1/2; and there’s hybrid Bink). On the other hand, DCT-based Bink2 is still in use.

Overall, if you look at game formats section in the wiki you’ll see a lot of various formats and many of them are built on a handful of the idea described above while still being quite different from each other. Originality lies not only in the methods employed but also in how you combine them together. And the modern codecs are the example of how different organisations build essentially the same codec using slightly different methods. MPEG-5 LCEVC was a nice change though.