Kostya's Boring Codec World

There’s an Argentinian game called La Mágica Aventura del Cine or (The Magical Movie Adventure in English language release) which has animations in ordinary and custom FLI format. The files are hidden inside large resource files along with .voc and other types with no obvious index (probably it is stored in accompanying .lod file which was not useful even after I uncompressed it). Anyway, custom FLIs have marker 0xAF66 with chunk types 110 (contiguous VGA palette) and 100 (LZ77-compressed frame). I’ve added support for it to na_game_tool but, like with Cross Racing Championship RoQ files, I won’t count it towards the total number of formats supported.

What’s curious is the compression scheme employed here. It is slightly more complex than classic LZSS since it has more modes of coding offset and length (8/13-bit offsets, 2/3/8/16-bit lengths). Nothing special but it looks almost the same as the compression employed in HNM except for one bit meaning inverted, LSB bitstream reading and large lengths handling. And like HNM there are two slightly different variants of the compression method used here as well: ordinary compressed files seem to use the version with 16-bit flags while frames (and some other, probably also image, formats) employ the version with 32-bit flags. I somewhat wonder if there was a widespread version of this particular compression format that got adapted by two different companies in the same way as LZSS.c from Haruhiko Okumura (which is so common that I often recognise the format even without looking at the binary specification).

In either case it’s time to move on, there are still two or three formats left to RE and implement for the na_game_tool release.

I’ve finally finished adding Knowledge Adventure movie v2/v3 support to na_game_tool—just a couple of formats more and I can make a release.

Meanwhile I want to talk about what I discovered.

First of all, the original format still looks too hard to implement, mostly because of its incomprehensible binary specification. With all known samples employing arithmetic coding if you get one thing wrong you won’t get any thing right.

Let’s jump to version 3. As it turned out, it is not a movie file per se but rather an archive containing interleaved chunks of version 2 movie format and optionally an audio track. It even stores the original file names in the header. What’s curious is that version 2 supports embedded audio track just fine.

So now the most interesting part left. Version 2 movies as I described in the previous post use static Huffman coding for multiple streams (like mode bytes, motion vector indices, colours and such). The main thing I didn’t understand back then was its pattern mode: apparently the decoder keeps track of two significant colours used by all blocks in the line (e.g. last column of the raw block, or last pixel of each motion-compensated sub-block, or two colours used in a pattern block) and may re-use them from a neighbouring block for a pattern fill.

There are also some other fun things, like older games using transposed images (i.e. it’s coded as columns in left-to-right mode) while newer games use bottom-to-top coding. And single images are often coded as a sequence of strips (e.g. first you have strip 132 pixels wide, next to it a strip 128 pixels wide and so on until the whole image is decoded).

Actually there are many feature flags in the play there, I’ve ended up implementing just the most common modes and giving up on more complex ones. At least it works on the majority of the files I tried (including the ones extracted from older and newer Knowledge Adventure archive formats—of course na_game_tool supports extracting from them now). The format will be documented shortly after the release (because it’s a thing I usually do when I have nothing better to do) so those willing to do it better will have both the code and the description to work from.

Meanwhile I’ll just chase another pair of some game codecs for completeness sake, make the release, and move to implementing a different multimedia tool…

While I’m still preparing next na_game_tool release (still a couple of codecs to RE and implement!), I’ve finally encountered a very rare beast—wavelet game video codec!

Gunmetal features SBV format with the minimum header (frame table contains just timestamps and start offsets) but each of those frames is coded using fast wavelet coding algorithm. First level is transmitted as byte values, the other levels are coded in 4×4 or 8×8 blocks, one level after another, using fixed-bits non-zero coefficient coding (the number of bits depends on the block coding mode) plus some bit flags to code zero runs. (De)quantisation is done by simple shift operation. Wavelet looks like the traditional LGT 5/3.

One might think the scheme is truly scalable but unfortunately you have to decode data for one plane before you move to another. Speaking of planes it’s a simplified YUV-like scheme with
Y = ( R + G + B) / 3
Cr = (2R - G - B) / 3,
Cb = (2B - R - G) / 3
with the traditional 4:2:0 sub-sampling.

This could’ve been a simple intermediate video codec for the cases where you’re really strapped for CPU power but still want some compression. And yet it’s a game format instead… I’m still delighted to encounter such format in a game (and in general).

Mostly because of the weather I have not been in mood to work on anything serious for weeks, but here is something rather interesting.

Apparently there are some CD-ROMs represented on discmaster titled “Moving Puzzle: …” that have some .mv files (inside media.pak archive) that supposedly give motion to those puzzles. And of course somebody had to look at the format.

Obviously the format was inspired by QuickTime as it has the header with all those chunks defining per-track data including e.g. sample-to-chunk mapping. There are two main differences though: the format is flat as first you have header size and header chunks following each other without any nesting (so when you encounter the second track header chunk the following chunks will belong to this new track); and the data is little-endian there, both numbers and tags (e.g. “ssiz” which is sample sizes chunk is written as “ziss” instead, same for e.g. codec IDs). Luckily I could ignore most of it as the data seems to be stored without gaps, so reading palette, then seeking to the first video chunk and reading individual samples(frames) from there works fine.

And it has its own two codecs, RLE and LZSS. RLE has two modes, both coded the same but inter mode storing the difference from the previous frame (not even XOR, simple subtraction by modulo). LZSS is not the usual flavour either. Unlike the most widespread scheme of “read 8/16/32-bit flags, treat the following bytes until next flags as either literals or packed 16-bit LZ offset+copy length combination” here it is a continuous bitstream with offset and length bits being signalled in the bitstream header and offset zero being used to skip decoded data (since you decode to the frame buffer, it leaves some bytes of it unchanged). Nothing groundbreaking but you most implementations hardly make any changes from the original LZSS.C and right now I can only think of JAM format which implemented LZSS with copying from the reference picture.

IMO this is an over-engineered system but that’s what makes it interesting to look at.

Yes, calculating that results in VID5 but in reality it’s MPEG-4 part 2 (minus some parts). Paul has asked me to look at it some time ago, so I did (which is much better than implementing a decoder for it).

As I said already, this is essentially MPEG-4 part 2 with some insane parts being cut off (but not enough to turn it back into ITU H.263): there’s no support for special texture shapes, interlacing or even quarterpel motion compensation. There are still B- and S-frames to complicate things though. Bitstream format is cut down as well to remove most of the nonsense (or omgFFeatures if you have that view), so there are just frames containing basic header (or slightly less basic with GMC and S-frames) plus macroblock data. Macroblock data is almost identical to the expected format—they even still have sync pattern handling in MCBPC despite there being no need for that.

So on the one hard writing decoder for it is not that hard, as you can simply hack an existing decoder for that, and hard enough at the same time (because you either need to hack an existing decoder or implement it yourself and that ISO standard is not easy to comprehend and personally I decided not to touch S-frames at all and if the need arises I’m actually considering making a wrapper for xvidcore instead).

Meanwhile I still have MVS to document and lots of encoders to write to make use of my new palettiser (because so far I have just three codecs that can encode paletted formats—two of them are for AVI, one is GIF, and none are for MOV). So hopefully I’ll have something more interesting to write about next time.

So I found another pair of rather peculiar game video formats. What’s curious is that while MVI1 and MVI2 are rather different internally, they both are used in Battle Race demo, and that’s not saying anything about their design (yet).

Both MVI1 and MVI2 are codecs used in some old DOS games developed by Ikarion Software. The only common thing in their structure is that is starts with magic containing “MVI” followed by 16-bit version and a table of frame sizes. And that’s where the differences begin. In MVI1 frame sizes are coded as radix-7 (or MIDI encoding, also known as LEB128 nowadays); in MVI2 they didn’t bother with it and left them as 32-bit numbers. In MVI1 frame consists of several optional parts, in MVI2 frame structure is fixed. And there’s another small difference: MVI1 has LZ77-compressed paletted images while MVI2 has vector-quantised 5-bit YUV420.

Of course formats employing LZ77 are dime a dozen but MVI1 still manages to stand out: first, it employs radix-7 encoded offsets, and it also de-interleaves palette by components before compressing (i.e. first all red components are sent, then all green components and finally all blue components). Optionally it can employ motion compensation on 10×10 tiles (which is uncommon already) with motion vectors for each tile being compressed with RLE and also in de-interleaved form (i.e. 768 16-bit offsets are split into high and low bytes and those are compressed one after another). I can’t think of many formats back then that thought about de-interleaving data in order to increase compression.

MVI2 splits frames into 64×64 tiles that are composed of 4×4 blocks selected from a circular buffer of 4096 entries. So frame decoding consists of reading new 4×4 blocks for the codebook and then decoding 12-bit block indices for 64×64 luma plane and two 32×32 chroma planes (all they use the same codebook, which is rather unusual for such codecs). Of course such approach is not particularly new (and reminds me more of 16-bit consoles) but I still can’t remember another VQ-based codec with exactly the same design.

P.S. And there’s also MVI used in Archimedean Dynasty—yet another MVI format from yet another German company. I’ve not looked at it yet (beside a cursory glance in the hex viewer) but it looks different from those two. Let’s see what surprises it has…