Kostya's Boring Codec World

Recently I’ve discovered some videos on archive.org that I’d like to watch. The problem is that they are VP8/VP9 plus Vorbis/Opus in WebMKV container which NihAV did not support. So I essentially had three options: re-encode it, use a third-party player, or implement support for it. Of course I went the fourth way—implement minimum support for the larger parts and re-encode the audio.

First thing was to determine what has to be done. Since avconv can’t put VP9 into MP4, I had to implement Matroska support. It was moderately annoying but not hard. And it did not lose much respect in my eyes either (mostly because there was not much of it in the first place). Of course I ignored a lot of finer details but it seems to be good enough for my needs, I’ll eventually try it on some 10-bit H.264 plus FLAC files I have somewhere around (another codec not fit for MP4; and don’t point out at the unofficial mapping schemes—my principles say no to it).

Then, audio track. That one was easy, just re-encode it to AC3 from whatever input format. It’s fast and beats writing decoders for Xiph formats.

Finally, video. I have VP8 decoder already (mostly written for the completeness sake) but no VP9 decoder. Re-encoding video is a long process, writing decoder is not particularly fast either. The not so obvious solution was to rely on VA-API for hardware decoder. One thing that’s definitely better in Duck codecs against ITU codecs is much simpler metadata and frame management, so VP9 VA-API decoder is much smaller and simpler than H.264 one. Essentially it’s just read frame header, generate some parameter structures, send it to the decoding and update frame references afterwards—compare that to parsing data in order to find frame header, picture parameter sets it references, sequence parameter set referenced by PPS and preparing various structures for that along with complex frame management rules. VP9 is not that simple either, with its potentially present segmentation and whatnot, but it’s much more manageable for the common case. As a side note, the follow-up codecs (VP 1.0 errata 1 and VP II) are much worse in that aspect, so I don’t know if I’ll ever want to deal with them.

And there it is, my solution for watching some files without wasting too much effort on implementing full support for all involved formats. Of course it would be easier just to re-use some existing code for demuxing support and wrap decoding libraries; some may even point out the futility of it all since there are perfectly working solutions already. But as I have committed to using my own software for my multimedia needs (except for the rare cases which avconv is allowed to handle), I’ll keep improving what I have. But had the things developed better in the past, I’d have no such problem as avp from rust-av project would be usable for my needs. Alas!

What should follow a political rant that nobody would read? A release of a tool that nobody would use of course!

I’m indifferent to announce the release of na_game_tool version 0.6.0, now with AVI support. Beside being able to write output to AVI it can now also de-obfuscate some AVI files that employ some simple scheme (like XORing with a 32-bit counter). And in addition to that it can also reconstruct Smacker and audio files from AVIs (or IAVFs) used in Black Dahlia and Ripper games.

The rest of the newly-added formats are mostly those I found at discmaster.textfiles.com by searching for unknown files over several megabytes large (and filtering out corrupted samples, segments from the multi-part archives, etc). Despite discmaster not being updated anymore (you know whom to thank for the storage shortage), I’ve found enough to have another release in the future.

Meanwhile here are some short notes about some formats:

• Elige Tu Muerte is extremely short but very FMV game: it’s a dozen of .mov files with animations plus 20kB .exe engine. You just click on one of four exits and 3D-rendered figure walks there to its demise (which should be obvious from the game title). The coding format is slightly more complex than normal RLE but still nothing to write a full post about;
• Lords of the Realm VAS format is the one I halfway reverse-engineered from the files themselves and then found corresponding RLE decompression code in the binary specification to fill in the missing details. The main problem there is that it’s an overlay executable so some parts are not loaded by default and there are no references to the decompression functions;
• Tie Break Tennis 98 intro file was reverse engineered from its contents because it was less effort than to manually load LE segment of the binary specification into Ghidra. After all it has just four opcodes (fill block, raw block, skip block, and palette) so guessing the whole structure was easy;
• Gunmetal SBV gets another mention here by being the only wavelet video codec I’ve encountered in a game so far;
• this time I had three formats that should’ve been video files in theory but turned out to be an archive of video and audio tracks in stand-alone formats, optionally with some commands telling how to play them. Those formats are AVI, SMS and Knowledge Adventure movie v3.

na_game_tool is available at the usual place in the usual format.

Now I can move to work on a different tool which would tackle a format that’s very widespread and extremely exotic at the same time.

Since I got lucky during weekend with some formats, I got enough of them to release na_eofdec. This is a tool similar to na_game_tool but oriented at generic exotic and obscure formats (or Amiga ones, put them into whatever category you like). So if you’re familiar with that one (why?!) you should have no troubles with the new one either (or at least it should be the same troubles).

The motivation behind it is about the same as with the other tool: decode whatever formats I find interesting enough to implement decoders for but not interesting enough to have them supported in the main NihAV base. Also it serves as a playground for various other things (like MOV muxer in this case, which served as the base for more versatile muxer in NihAV).

Anyway, it is released in hope (but no expectations and definitely no guarantees) that it will be useful for some purpose for others. The release is available at its own sub-page at nihav.org (and there’s a link to it in the appropriate section of this blog too).

While I’ve added palettisation support for NihAV about six years ago, it was limited to per-frame palette generation back then. Since I had only two encoders supporting paletted input and both were accepting palette changes, it worked fine. It’s only when I decided to implement MOV muxer I really got a need for palettisation using global palette, so I’ve started experimenting with that.

First and foremost, design. While frame palettisation is a part of NAScale that handles video frame conversion from and to various formats, this palettisation mode is bolted to nihav-encoder. It is actually implemented in two parts: initial pass that decodes input and generates palette at the end, and actual frame palettisation (which can actually work just fine without that pass if you tell it to use some pre-defined palette). I actually started with the second part and added palette generation later (for tests using default QuickTime palette was enough). Then I went even further and extended palette generation to support segmented mode (i.e. palette may change but not for every frame, I made the limit configurable but it should be at least 10 frames—storing palette for each frame before processing is too much).

This mode is a bit fragile since palettes are calculated for the decoded frames and not for processed frames. And for palette segments it’s even worse since it tells the number of frames for which the palette is valid, so framerate conversion will make it a mess. But the alternative leads to madness libavfilter and that’s hard pass for me. I see filters more as a drug that makes multimedia projects shift attention to them, making it more and more about e.g. filter negotiation and complex graphs support and less about playing actual media; consequently, making everything a filter is a sure sign the project is on its way to becoming obsolete (yes, I don’t hold neither DirectShow nor gstreamer in high regard).

Anyway, after overall design description it’s time to talk about implementation details. Palette generation for video differs from palette generation for single image by the sheer amount of data it needs to take into account. So while I have “let’s waste memory and have a table of 64-bit counters for each possible colour” my first mode was putting colours into smaller buckets (bucket index is calculated from the top bits of components) and join similar colours (e.g. differing just by two low bits in each component) when the number of entries gets too high. It is slower and not as accurate but it consumes less memory and performing vector quantisation on hundreds of thousands of entries is much faster than on millions. So it may have its uses.

Then palette segments generation. I don’t do anything fancy and simply calculate coarse colour histogram to decide when to start a new segment. For cut-off criterion I selected the ratio between correlated histograms and auto-correlated new frame histogram. If they’re of about the same magnitude then I can add this frame to a group, update group histogram and continue, otherwise I generate palette for the just finished segment and start a new one. It’s naïve but it seems to work reasonably well.

Palettisation itself consists of finding an appropriate palette entry for the input colour (I’m aware of dithering but haven’t bothered with it yet). I use the same three methods as back then: brute force search, local search and k-d tree search. The latter is faster than the rest but gives horrible quality so I don’t know if I should improve it or throw away. Local search (especially with a small cache for last 32 results) is a nice trade-off between the rest. And brute force search is implemented by filling a small 16MB table which maps each input colour to the palette index; it is slow to generate but it works extremely fast with global palette and reasonably large video (i.e. more than those sixteen million pixels). For segmented palettes it’s better to use local search though.

That’s it. I realise that I’m the only user of such feature but it gave me something to play with and brought some joy implementing it. After all, who else can claim he converted movieCD into animated GIF without using any 16- or even 32-bit code?