Kostya's Boring Codec World

I said it before and I repeat it again: I like older formats for trying more ideas than modern ones. DMV was surprisingly full of unconventional approaches to video compression.

First of all, it uses fixed-size blocks with palette and image data occupying initial part of the block, and audio taking fixed size tail part of that block.

Then, there’s image compression itself: frame is split into 2×2 tiles that can be painted using 1-4 colours using pre-defined patterns, so only colours and pattern indices are transmitted. Those indices are further compressed with LZ77-like method that has only “emit literals” and “copy previous” (with source and destination allowed to overlap but with at least 4-byte gap for more efficient copying).

And even that is not all! I actually lied a bit because in reality it is 2x2x2 tiles since one pattern (using up to 8 colours) codes two 2×2 blocks in two consequent frames simultaneously. Now that’s an idea you don’t see every day. There are many codecs that code colours and patterns separately (like Smacker or System Shock video), some use a variation of LZ77 to compress data even further, but the only other codec I can name that coded two frames at once would be H.263+ with its PB-frames (and it was mostly interleaving data in order to avoid frame reordering, not sharing common coding data between frames).

Searching discmaster.textfiles.com for large unrecognised files returned more hits so I hope that some of the remaining formats will also feature some refreshingly crazy ideas. Now I only need time and mood for reverse engineering.

As I mentioned some time ago, Paul has shared a decoder for bytedanceVC2 codec. From the first glance it looked like H.266 rip-off. After a more thorough looking it seems to be more or less plain H.266.

There are some tell-tale signs of codecs using well-known technologies: simply listing strings in the binary gives you “VPS/SPS/PPS/APS malloc failed” (with APS being adaptation parameter set, which was not present in H.EVC but is present in H.266), “affine merge index is out of range” (again, affine motion was added in H.266), “lmcs_dec” (chroma-from-luma, another feature not picked up by H.265 but which was fine for H.266), “alf_luma_num_filters_signalled_minus1” (a variable straight from the specification). I hope that this is convincing enough to claim that the codec is based on H.266 (or VVC).

Now what would a rip-off codec change? In my experience such codecs keep general structure but replace entropy coding (either completely or at least change codebooks) and DSP routines (e.g. for H.264 rip-offs it was common to replace plane intra prediction mode with something similar but not exactly the same; motion compensation routines are the other popular candidate).

I cannot say I got too deep into it but the overall decoding is rather straightforward to understand and from what I saw at least CABAC was left untouched: it’s exactly the same as in the standard and the model weights are also exactly the same (at least the initial part). Of course that does not preclude it having differences in DSP routines but I seriously doubt it being different from the standard (or some draft of it).

And with that I conclude my looking at it. Those with more motivation and actual content to decode are welcome to try decoding it, I have neither.

As I mentioned before, apparently this format got popular enough to be licensed and used in three different container formats for three different goals (generic VfW codec, game video codec and interactive video player). Another curious thing is that the codec operates in GBR420 colourspace (yes, that means full-resolution green plane and down-scaled red and blue planes—something between Bayer and YUV420). Oh, and of course the fact that it uses true fractal compression makes it even more interesting.

Even if the codec operates on full 8-bit values internally, the reference decoder outputs either 16-bit RGB or paletted image (new palette is transmitted for some frames, usually intra ones). And it’s worth mentioning that the decoder always works on 320×200 frames (probably for simplicity), IFS image format does not have that limitation.

Internally the codec operates on 4×4 blocks grouped into 8×8 super-block so that some operations may be performed on whole 8×8 blocks instead. Planes are coded as green first and red plus blue plane next to each other second, both parts being coded independently (i.e. codec format always codes source block offsets related to the beginning of the current plane and switches them mid-decoding). Overall, decoding is straightforward: read frame header data, start decoding block opcodes for green, continue with block opcodes for red and blue, do some operations depending on header flags, output new frame.

There are several known header flags:

• 8—repeat last frame;
• 4—swap frame buffers (and output previous frame after decoding into the new current frame);
• 2—palette update is present (the first header field is an offset to it);
• 1—this is a fractal (key)frame, it should be decoded 16 times.

Yes, it’s the hallmark of the true fractal compression: it does not matter from which source you start (here it’s planes filled with 0xAB value in the very beginning), after 7-10 iterations you’ll converge to the desired image (sounds perfect for error resilience, doesn’t it?). But since it’s a computation-costly process, inter frames merely do some kind of refinement (including motion compensation).

Block opcodes are several bit fields packed into bytes LSB first. First three bits are main operation ID, seven being a signal for an extended operation with an additional 4-bit operation type. Here’s a table with them all (unlisted extended opcodes do not exist and make the reference decoder crash):

• 0-3—affine transform block
• 4—skip next 1-32 blocks;
• 5—motion compensation for the next 1-256 blocks;
• 6—raw block data follows;
• extended 0-7—affine transform for 8×8 block with an optional refinement for one of 4×4 blocks (in that case another 3-bit opcode is read and applied; the meanings are the same except that skip and motion compensation should apply only to one block and extended opcodes are not allowed);
• extended 12—skip 33 or more blocks;
• extended 15—raw 2×2 block put at absolute 16-bit offset. I doubt it’s ever been used.

Motion compensation is performed by copying block from the previous frame using one of up to 16 possible motion offsets transmitted in the frame header. This approach was not unusual back in the day (Indeo 3 immediately comes to mind).

And now for the juiciest part, namely affine transforms. Fractal coding works by finding a larger block (called domain block) which (when down-scaled, rotated/flipped and brightness/contrast adjusted) will correspond to the current one. Here domain blocks are always twice as large (with down-scaling performed as taking each even pixel at every even line) and are located at even positions (so 14-bit index is enough for them). Contrast adjustment is done as pix*¾+bias, with bias being in -64..63 range (so 7-bit index is enough for it). The transforms itself are described by their bit masks: bit 0 means source block should be mirrored (i.e. left becomes right and vice versa), bit 1 means it should be flipped (top becomes bottom and vice versa) and bit 2 means it should be transposed (i.e. pixel (1,2) becomes pixel (2,1) and such; this operation is for 8×8 blocks only).

That’s all! It was good enough to compress video with 4-10x ratio (or twice as much if you treat it as 16-bit video instead of paletted one) without the usual blocky artefacts present in other codecs. And it applied inter-frame compression in order to save both space and decoding time. While that part was not a proper fractal compression, affine transforms were still used there (it reminds me somewhat of certain French game formats that combined motion compensation with mirroring or rotating).

The sad thing is, this is probably the only true fractal video codec in existence. Writing a fractal image compressor is so simple everybody can do it as an experiment, making a proper video codec is apparently not. Even ClearVideo while being from the same company and believed to be a fractal codec is not one in reality—key-frames are coded a lot like JPEG and the only thing common with fractals is using quadtrees, copying blocks from elsewhere, and adjusting brightness when copying blocks. If not for the company name one would not think about it as having anything to do with fractals.

And as a bit of philosophy, it looks like this codec was adopted from the original fractal image encoder (as I said before, this kind of compression looks like the first straightforward scheme for fractal compression as it’s usually described in the literature) and adopted it to video by adding skip blocks and motion compensation. Then they probably started experimenting with better fractal compression—using blocks of different size and quadtree to describe that, better compression of block parameters. Then at some stage they discovered that it was much easier and faster code DCT blocks for key-frames and plain motion compensation is good enough—that’s how they ended up with ClearVideo. And then they discovered that their newer products can’t compete with other codecs and the company went out of business.

To credit where credit is due, I must say that the company got one thing right: the majority of the future video compression was searching extensively for the matching blocks, so if they started it a bit later and applied their know-how, they could’ve ended with a very competitive video encoder by now.

If it looks that I’m not doing anything, that’s about right. Nevertheless I’d like to discuss two exotic formats that I’d like to write decoders for.

The first one is unlike most of the video codecs I’ve seen so far. For starters, it uses fractal compression. Not surprising since it comes from Iterated Systems. And unlike later ClearVideo, it is really a fractal codec. From what I see, it works exactly like the textbook example of the fractal compression: split video into small fixed-size blocks, search for a domain block, apply simple affine transform on scaled-down version of it plus brightness scaling and output the result. There are additional possible operations like leaving blocks unchanged or reading raw data for a block. Since this works only for the greyscale, frame is stored in YUV420 format, planes coded sequentially. Unfortunately since the binary specification is mixed 16/32-bit VfW driver that Ghidra can’t decompile properly, the work on it goes at glacial speed.

The other codec is like the previous one but it has its own container format and DOS player. It comes from TMM—not The Multimedia Mike but rather the company known for RLE-based PH Video format. I don’t see mentions of Iterated Systems in the binary specification, but considering how similar this FRAC codec is to theirs (it uses the same bitstream format with the same opcode meanings and the same assembly instructions) I expect they’ve licensed it from Iterated Systems.

So hopefully when I actually finish it I’ll have two decoders for the price of one.

Update: while refreshing the information about fractal compression, I discovered in the Wickedpedia article on it that two companies claimed they got exclusive license for fractal compression algorithm from Iterated Systems—TMM and Dimension. The last one licensed it to Spectrum Holobyte to be used for FMV. And what do you know, that explains why FVF is named so and why its video bitstream syntax is the same as in the other two (and the code seems to be the same too). So I guess it means I’ll have almost the same decoder (but with different containers) in NihAV, na_game_tool and na_eofdec.

Update from November 4: I’ve finally implemented FVF decoder in addition to earlier FVC1 (VfW codec) and TMM-Frac decoders. So the whole trifecta is supported now.