Kostya's Boring Codec World

When I have enough inspiration, I improve NihAV. When I don’t (which is more common state to me), I RE codecs or write blog posts—so here’s one.

First of all, I’ve started adding non-raw encoders for some common QT formats. It’s not that there are no open-source encoders for them, but I do them mostly to find out how it is done and maybe learn something new in the process. For instance, RLE encoding combines skips, runs and pixel copies; this rises the question of optimal encoding as sometimes it may be cheaper to encode a whole area as new pixels instead of a mix of copy+skip+copy. So I’ve implemented a greedy approach (i.e. code longest skip or run and fall back to encoding raw if those two fail) as well as slow but optimal one. It’s a variation of trellis coding: just calculate encoding cost with each mode (skip/run/raw) to all next possible positions and if it’s lower than the existing one, use that mode; at the end simply trace back the decisions that gave least cost at the end and encode them in right order.

Then I also added RPZA encoder. This is essentially the first texture codec before GPUs with the need for texture compression, its main compression mode is encoding 4×4 block with four colours where two colours are linearly interpolated from two explicitly transmitted colours. There is no apparent way on how to do it fast, so I ended up with an extremely simplified scheme: first I calculate the maximum difference between components and pick the one with the largest difference (or code block as single-colour if it’s small enough) to decide what values to pick, then I calculate explicit colours from an average of input pixels close to minimum and maximum ends of that range. I also have a refinement step by running vector quantisation loop to adjust the ends but it’s rarely needed in practice.

There are still more encoders to implement (SMC, SVQ1, IMA ADPCM and MACE) but none of them is interesting beside SVQ1, so probably I’ll write about it when/if I ever get to implementing an encoder for it (it does not matter if The Multimedia Mike has done that over fifteen years ago—NIH is there in the project name for a reason).

Now, surprisingly enough I’ve improved decoding support as well. The original QuickTime had SIVQ codec which is a straightforward 256-entry codebook for 2×2 RGB24 tiles followed by codebook indices. I had read its binary specification some time ago and recently I was able to locate (probably the only existing) sample for it, which is a good reason to write a decoder for it. It was well-spent five minutes of my time. Maybe in the future I’ll also do something about Pixar codecs (Ghidra works better with raw m68k version of the decoder than with 16-bit Windows 3.x version of the same).

And finally I’ve improved the support for multi-descriptor MOV files. I mentioned it some time ago and I got bitten by it again recently. For example, alice_lo_m.mov from samples.mplayerhq.hu got just first frame decoded for me and many QuickTime 1.5 sample videos (with its developers) gave an error on the last frame. For the former it’s because first frame is JPEG and the rest of them are SVQ1, while the latter samples are coded with Cinepak but the last frame may be a special one encoded with RPZA. And there was another file fully encoded with RPZA—but with the majority of it being 160×120 while last dozen of frames or so were 320×240. So I finally got annoyed enough to implement multiple streams per track so at least the frames get marshalled to the correct decoder, even if it leads to the partial streams being rather unusable. Maybe one day I’ll write a tool which will walk through MOV and render all tracks in correct sequence (taking edit lists into account), scaling and adjusting playback rate as needed, producing a raw MOV file that can be played without special hacks; or maybe I don’t hate myself that much.

That’s it for now, don’t expect anything soon (MVS description may appear but who’s waiting for that?).

In theory I should be documenting the codes Paul has shared with me or MVS (did you know that it employs a rather interesting chroma subsampling method—coding three 8×8 blocks in a macroblock but chroma samples have less than a half of coefficients in zigzag order coded) but instead I’ll write about something nobody really cares about.

As some of you may know, RedHat had (at least) two multimedia formats developed: RLE-based PhotoMotion for RedHat PC (later licensed to American Laser Games that seems to extend it somewhat) and gradient-based UltiMotion codec for AVI (the format of choice for VfOS/2).

Since the codec is somewhat unique, I decided to write an encoder for it. This way I can re-encode e.g. some movieCD (a format hardly anybody remembers) to another obscure format nobody remembers exactly just because I can. But the main reason is to learn how it’s organised.

There are three distinctive features it has: shared chroma (i.e. 8×8 super-block can have just one pair of chroma samples instead of coding each 4×4 block with its own pair), quantised values (6-bit luma and 4-bit chroma) and of course gradients. Actually there are seven block coding modes and only half of them are gradient-based—the rest are more conventional skip block, scaled-down block (4 luma samples only), BTC (2 samples plus fill pattern) and raw block.

Gradients here are essentially filling the block in one of the direction a lot like intra prediction works in H.264 and later, the main differences being fewer angles and fill values being transmitted explicitly. Fun thing is that unlike other codecs there’s no easy way to transmit a flat block, you need to code it in some extended way as the simplest (“shallow”) mode codes a coarse gradient with two values, the second value being implicit N+1. More complicated (“LTC”) mode codes a fine gradient but allows only a four-colour combination present in 4096-entry codebook. There’s also an extended mode where you can code any values for a gradient.

This of course poses a challenge of finding a good gradient in reasonable time (because trying all 4096 combinations with all 16 directions may get a bit slow). For shallow coding it’s easier, you essentially have block split into two parts, so checking averages for those parts and seeing if they fit is enough. For LTC and extended mode I applied a similar trick by finding the averages of four samples used in each gradient angle and saw if they fit well enough (for LTC it was also checking that the samples are monotone increasing and checking only the more or less close codebook entries; probably there’s more of optimisation potential but I’m fine with it as is).

Actually I started it gradually: first by implementing simple “raw or skip blocks only” mode, then “any block type that does not introduce additional loss (beside YUV quantisation)” mode, then lossy mode, and finally fast-and-shitty mode. The idea behind the last one is to calculate blocks variance and to use that information to force block selection process (i.e. not try more complex block types on blocks with low variance). As you can guess from the name it did not work out that nice (but it was about twice as fast). But overall lossy mode works rather good and by introducing distortion thresholds I can vary output file size significantly (3-5 times smaller and still not being a block soup). I’m not going to bother with any rate control and overall I consider this experiment done.

In conclusion I’d like to write something but nothing comes to my mind. Stay tuned for more stuff nobody cares about (like obscure codecs or my experiments with palettisation).

Here’s another portion of news about what I’ve been doing in last couple of weeks. Hopefully I’ll be able to write about fruity MVS soon.

While most of what I did is not worth mentioning, there are some bits I find funny or curious enough to share.

First of all, I’ve added VAXL and (Clari)SSA decoding support to na_eofdec (just some more and there will be enough formats for 0.1.0 release). And I actually added them mostly to test an IFF parser (derived from my AVI parser and enhanced). The idea is simple: just point it to the data needed to be parsed and provide chunk handlers and it should do the trick. The main enhancement is also providing a condition when to stop—at the end, on any unknown chunk, before some pre-defined chunk, or right after such chunk has been parsed. This way I can control parsing process without relying too much on some special callbacks or states. For example, in VAXL that means I parse header by expecting VXHD chunk and nothing else. The rest of VAXL consists of time code, palette, image data, and audio samples chunks; there I simply stop after BMAP chunk and output reconstructed frame (and audio if present). In SSA (IFF variant, I added FEE one too for completeness sake) each frame is wrapped into FORM DLTA list so there I just parse sub-chunks ignoring unknown ones.

Then I’ve finally had another look at TCA and improved my decoder, going from less than half of samples I had being supported to virtually all of them. While I presumed that video is always compressed with LZW, in reality it also has RLE and raw modes. RLE mode is rather curious at that as it codes run+mode as 00 00 xx yy zz, 00 xx yy or xx number (i.e. if first one or two bytes are zero, read one or two bytes of the number too) with low bit signalling run or skip and the rest being its length (e.g. 55 means skip 42 bytes while 00 01 00 01 means repeating 01 128 times). But since the format is next to impossible to detect statically (no magic constants in the header, so you’d better check packet structure instead), it’ll remain a useless curiosity—just like I love it.

And most of the time I spent on writing MOV muxer. Since I’ve written one for na_eofdec already (raw output only) I had some base to start off at least. Of course it’s wonky and even copying data may or may not work depending on your luck, at least now I have a format to output variable framerate content losslessly (previously the only alternative for VFR content in NihAV was to encode data with RealVideo 4 and Cook). At least now, after all possible enhancements, I can either re-mux old-style MOV into a new one (and the output may actually be playable) or use nihav-encoder -i input.mov -o output.mov --profile raw to decode some more exotic format not supported by anything else (like MoviePak in MacBinary MOV) to a raw format that (hopefully) more tools can understand. I can also use my Cinepak or Indeo 3 encoders there (and Truemotion 1 too in the future just for lulz) and I should probably write encoders for other common QT codecs (even if there are other implementations, up to SVQ1 by The Multimedia Mike). This should keep me entertained for a while. And who knows, maybe it will serve as a base for MP4 muxer if the need for one arises.

That’s it for now, hopefully I’ll have more to write about later.

As I mentioned previously, I don’t want to work on game codecs for a while, so I picked other stuff instead. For instance, I’ve fixed a bug in my Indeo 3 encoder (which nobody uses, myself included), refactored some NihAV code and added a couple of decoders.

First, there is PDQ2 decoder. It actually turned out to be slightly more interesting than I expected as there’s a version of the codec for Saturn version of the game (it’s not that different yet somewhat different nevertheless).

Then I’ve finally managed to figure out MoviePak. After locating a decompressor binary and trying to disassemble it as raw M68k code I could locate enough code and data to figure out that since it uses JPEG codebooks it’s likely to be based on JPEG. And after learning a bit more about how it works and NOPing out A-line _StripAddress calls (that was the most interesting part actually—you can’t find it without knowing terminology and even then just barely; I was lucky to try searching for information about 68881, learning terminology and finally finding a reference of Macintosh Toolbox calls) I managed to make Ghidra happy enough to produce a usable decompilation. After that it was just a question of re-using JPEG decoder with a slightly different header format, which finally made me do a refactoring of JPEG decoding.

And since I’ve factored out common JPEG decoding support for MoviePak, Radius Studio and actual motion JPEG decoder, I decided to add a video codec for effects used in proDAD Adorage video editor (its FOURCC is pDAD, quite surprisingly). This one could be reverse engineered just by looking at the frame data. Each frame consists of 20-byte header, JPEG image plus alpha channel coded as PNG or JPEG. Since I have not bothered to write a motion PNG decoder (it’s very uncommon after all and I’m not NIHing image library—at least not yet), I decode just the first part. Maybe I’ll add a PNG decoder support and re-visit this decoder for proper alpha support, but for now this seems unlikely.

I’ll keep working on some boring stuff nobody cares about but maybe I’ll have a codec or two to write about as well.