Kostya's Boring Codec World

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.

In my last post I mentioned DVI family of formats and I decided to extend NihAV support a bit. Previously I implemented YULELOG.AVS demuxing and decoding and stopped at it, but apparently there are six more samples that can be found with discmaster.textfiles.com (fun fact: SAMPLE.AVP is not detected as AVSS and out of four instances three are unknown and one got the embedded JPEG file decoded).

There are certain difficulties extending support beside the original file: a good deal of the samples have AVSS format slightly different from the open specification, AVS2AVI.EXE convertor refuses to convert all but two files (saying that it does not know the algorithm used to compress them), the other available tools seem to rely on the ActionMedia card so you can’t do much without it.

So here’s the list of all known samples with some notes about them:

1. AUDM400.AVS—single audio track that uses “dvaud44” audio compression, which is some variation of DVI ADPCM. I have a suspicion that its audio packets are interleaved by channel (i.e. audio packet 0 is left channel data, packet 1 is right channel data, packet 2 is left channel data gain) but I’m not going to introduce some horrible hacks to assemble audio data in this case;
2. NWSAMP.AVS—PLV video with each component in its separate stream. Since there’s no specification available at all, I can only speculate that it employs delta compression akin to YVU9C or even something closer to Indeo 3;
3. REEL400.AVS—RTV2 video with empty audio track;
4. SAMPLE.AVP—AVSS “image” format (you don’t think WebP was the first case of such formats, do you?) with a stream containing single JPEG frame. In YUV410 format too, so I had to modify my decoder to handle it (along with fixing the case when planes are sent in separate scans);
5. SAMPLE.AVS—RTV2 video with (silent) DVI ADPCM audio. Initially video stream could not be decoded until I discovered it uses custom codes (that change between frames; and this is apparently the older version of RTV2 too). Now it works;
6. video.avs—RTV2 video with DVI ADPCM audio;
7. YULELOG.AVS—single RTV2 stream.

And since I’ve mentioned custom RTV2 codes, here’s how they work: there are codes with certain property and fixed symbol mapping (for all 143 symbols), so there’s a compact way to describe such codes. Each RTV2/Indeo2 frame has eight bytes in the header with the code description. Codes consist of two parts: unary prefix and fixed-size part, with the code descriptor providing the size of fixed part for each prefix. So e.g. code description 2,3,3 will map to 0xx, 10xxx, 1110xxx codes while description 4,1,2 will map to 0xxxx, 10x, 110xx codes. It’s not the most effective coding scheme but it takes little space and easy to implement fast decoding (you can use pre-computed look-up tables and just calculate what range of codes corresponds to which prefix). The scheme got employed again in Indeo 4 and 5.

This concludes my explorations in DVI/Indeo formats (because I don’t expect more information to resurface). There are still more formats to look at though.

Recently I’ve posted a short review of DPCM-based video codecs where Indeo 2 and 3 were mentioned, but what about Indeo 1?

Previously I believed that it’s their raw format aka IF09 (YVU 4:1:0 with 7 bits per component) but recently I’ve discovered a codec called Indeo YVU9 Compressed, which kinda fills the gap between raw video and comparatively complex Indeo 2 (which employs not merely delta coding but also vector quantisation and zero-run coding).

This format codes intra-only frames plane per plane with simple delta prediction and fixed Huffman codes for small deltas plus escape value (which means full 8-bit code value should be read). In other words, a perfect initial DPCM-based codec which can be improved in different ways.

I cannot tell if this codec really deserves to be called Indeo 1 (relegating IF09 to Indeo 0) or it’s some simplification of Indeo 2 that came later. As you know, Indeo codecs come from DVI (no, not the display interfaces) and they had different names. From what I can tell there were three video codec families there: RTV (real-time video), PLV (production-level video, not as fast) and PIC (whatever that is). RTV2 is now known as Indeo 2 but it’s hard to tell which one was Indeo 1 (if there was any) or YVU9C. What’s worse is that there’s next to no software specifications for DVI, you were supposed to use special cards with Intel chipset to encode and decode it.

In either case, it’s yet another codec reverse engineered.

First of all, here’s some information for the context: MVI codecs rely on out-of-band flags to signal what capabilities and subsampling they use (the fact that they decided to store those flags in FOURCC is a different annoyance); and despite the potential variety, only couple of flags are used for each codec. For instance, of all MVI1 files I saw only one flag has been in use (golden frame—and it’s only in one game). MVI2 has two distinct sets of flag combinations, 0x804 and 0x200. The former means bog standard MVI coding (with one chroma sample set for 4×4 block) plus one extension feature, the latter means MVI2 version 2 (if that makes any sense) where they decided to make subsampling and features selectable per frame (as well as adding more of them) and moved them to the frame header while at it.

So far I concentrated my efforts on format 0x804 to see what the feature it is. It turned out to be low-resolution deltas, just like Truemotion 2. In this mode every odd pixel is coded as previous pixel plus half of luma delta for the next pixel. I still have to make the reconstruction run properly, but that’s nothing a lot of debugging can’t fix.

This should allow me to decode even some of MovieCD samples (including the one hidden in samples.mplayerhq.hu/drivers32 for some reason) and I’ve seen quite recognizable frames already.

It’s hard to tell what features the other flavour uses but it’s reasonable to assume that it uses lowres coding as well. Hopefully I’ll get to it soon.

Update from Saturday: after dealing with the annoyance of different deltas coding scheme per each line type, I can now decode the few files I could find (including a couple of movieCDs from archive.org) just fine. The second half seems to use an alternative composing/rendering functions and reads maps differently as well. So while it’ll take more time, at least I’m closer to completion.

In last post I wrote about how I’ve managed to reconstruct a recognizable picture for MVI1 codec. After I fixed the prediction code it started to work properly. Surprisingly, Treasure Quest game proved to be a source of MVI1 files in all formats (RGB, YUV422, YUV420, YUV410 and YUV4½0—the last one has one set of chroma samples per 4×4 block and is the most common MVI format in general). Additionally it has MVI1 samples with golden frame feature (I named it after a feature in a family of competing codecs that started with rather similar coding approach): frame 0 is two intra frames with the second frame serving as the background for the other frames; there is an additional map mode which tells that certain rectangles should be copied from the golden frame (instead of previous frame or filled with one colour). MVI2 seems to have an extension of that mode but I’ll see about it when I get to it (and if I obtain samples using that mode).

So, MVI2 next. Considering the number of extensions they added (and how they interfere with frame reconstruction) it’s probably not going to be easy but now I have a base to extend instead of blind guesses to make.

As I mentioned last month, I decided to reverse engineer Motion Pixel codecs and after a lot of failed attempts to make decoder work I’ve finally got something.

First of all, here are two frames from different videos.

MVITEST.AVI:

And a frame from SHOT09.AVI (from Apollo 18 game):

As you can see, the images are not perfect but recognizable already. And just last week it would’ve been a mess of colours with some barely recognizable distorted shapes.

The reason for this is that while MVI1 (and MVI2) is indeed based on stand-alone MVI format (I call it MVI0 for clarity), there are some nuances. On the first glance MVI0 and MVI1 are the same—all steps are the same—and indeed you can use the same code to decode data from either, but the reconstruction steps differ significantly.

Essentially there are four steps there: decode rectangles defining which parts of the frame will be left intact or filled with one colour, decode deltas used to reconstruct the rest of pixels, use those deltas to generate predictors for each line (where needed), use the rest of deltas to reconstruct the rest of pixels. Additionally MVI employs chroma subsampling mode so only one pixel in 1×1 to 4×4 block (depending on mode) has delta differences applied to chroma, all other pixels update only luma component. So if you don’t do it correctly you may end up applying e.g. deltas intended for luma to chroma components and vice versa. That’s what I got for a long time and could not understand why.

It turns out that vertical prediction has its pixel sampling at different position—or maybe it’s scrambled in the same way as line prediction. There for the most common mode (one set of chroma components per 4×4 block) each group of four lines is decoded in reverse order (i.e. 3, 2, 1, 0, 7, 6, 5, 4, …). For 2×2 block only lines in pairs are reversed. You can see artefacts of wrong prediction on Apollo frame.

Anyway, having a recognisable picture means that the hardest part (for MVI1) is done, so all is left now is to fix the remaining bugs, refactor the code and move to MVI2. There are other annoying things there but now I know how to deal with them.

BTW, if you’re curious why it takes so long, the problem is the binary specification being obfuscated to the point that Ghidra refuses to decompile most of MVI1 decoder functions and can’t do much about reconstruction functions since they’re a mess of spaghetti code (probably written in assembly language directly) so it’s more of a state machine than a decoding loop. And they abuse segment registers to access different parts of the context (and this must be the reason why it cannot work under OSes from this millennium). I got some progress when I resorted to debugging this mess by running MVI2 player OllyDbg under Win95 (emulated in DosBox-X) and constantly referring to Ghidra to see where to put breakpoint to trace a certain function. That process is definitely not fun for me but it gave results.

Overall, probably it could’ve gone better but I hope the rest won’t take as long.