Kostya's Boring Codec World

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?

Since the last time I’ve done some more boring stuff for NihAV, more precisely 10-bit H.264 decoder and extended MOV support.

The former is more or less straightforward but it made me regret Rust lack of text-level macro processing. The problem is generating almost identical code for various combinations of bitdepths that differ only by the clipping range and function name suffixes. Probably it can be solved with proc macros but that’s a hole I’m unwilling to jump into. Also supporting both 8- and 16-bit decoding in one module is annoying, so I ended up just putting them next to each other and selecting one for the current mode of operation. This also uncovered the fact that my scaler did not handle high-depth YUV in the most cases, so I had to fix it too. And the ironic thing is that I don’t have enough content to watch in that format (and a couple of sample files I have are Matroska with FLAC audio, which can’t be remuxed to MP4, so there’s that).

In other rather equally useless things, I’ve finally made a MOV muxer for na_eofdec. Of course it’s a simplified one, supporting only raw video and audio tracks, but even that was annoying to support properly (I’m still not sure if I do support it properly). At least when the bitterness passes I should be able to make a MOV muxer for NihAV (and who knows, maybe even implement some QT encoders to exercise it).

But that’s not all regarding MOV. In a recent post I mentioned the oldest known MOV flavours. Finally I’ve managed to extend my MOV demuxer to support beta version of it (it’s still MOV but with a few different details here and there) while alpha version was easier to support in a different demuxer written from scratch. If you’re curious, those files are short clips (about 15 seconds usually) compressed with QT RLE demonstrating some features of upcoming System 7 in rather symbolic form. Here’s a GIF of virtual memory feature presentation.

That’s about it for now, I hope to do more exciting things next. For instance, add some Amiga formats to na_eofdec. And most importantly, Paul told me about new RAD Audio codec which I still have to look at thoroughly. From a first glance while audio in Bink is a lot like MPEG Audio Layer II (i.e. simply quantise and write coefficients with a fixed amount of bits), this new codec is more akin to AAC LC as it apparently has long/short frames division and (at least two) Huffman tables for coefficients. Another change is that Bink audio was stored in simple container formats with fixed structure, new format looks more like an elementary stream with as few bits as possible spent on coding different fields. Let’s see how it turns out…

As I mentioned previously, after making 0.5.0 na_game_tool release I’d rather work on something else for a change (if at all), so here are some bits about what I’ve been doing since:

• first of all, I’ve implemented support for AV, a Polished AVI format. By that I mean the format comes apparently from a Polish company and it’s simplified remux of AVI data: first there’s BITMAPINFOHEADER (and optionally palette) followed by video stream header (starting with the familiar vids tag), then there may be WAVEFORMAT structure with auds stream header, then you have table of contents (video and audio frame sizes plus flags) followed by video and audio chunks. The format was trivial to guess and I’ve added support for it because why not;
• I’ve also finally implemented functions for reading arrays of integers. First I’ve introduced them to na_game_tool and tried them in some decoders, and then ported them to the main NihAV codebase. The idea behind it is that reading data directly into destination array (with optional byte-swapping) is faster than reading data, re-interpreting it as an integer and finally copying it into the destination buffer. I had a specific version of it implemented in MP4 demuxer already (because otherwise opening a 2-3 hour long video would cause a noticeable delay) but overall it’s nicer to have just one call instead of a loop;
• in other things, I’ve re-started na_eofdec development using the current na_game_tool codebase. That does not mean I’m starting developing it (or going to do so in the nearest feature) but at least when I eventually get to it, I can add some archive extraction modules as well. Beside that it should be a sandbox for testing MOV muxer that I want to write sooner or later (kinda like OpenDML AVI muxer in NihAV is a backport of one from na_game_tool). Of course it would need to get a couple more formats to test it on but I’m not in a hurry;
• speaking of MOV, I’ve improved support for MOV in MacBinary II. So far I’ve seen four flavours of it: essentially flat MOV with MacBin header, MOV with mdat box in data fork and moov atom in resource fork, the same but data fork containing mdat contents without size and tag, and even older format (with samples from 1990) with much flatter structure (i.e. lots of nesting chunks are not present at all). The first three are detected and handled more or less fine now, I’ll try to support it even if as a historical curiosity;
• there was one major code refactoring in NihAV, namely I’ve put demuxing handling code into a new nihav_hlblocks crate and made all my tools use it instead of dragging local copies of it. If you wonder why this was necessary, that’s because you can have normal demuxers (that return full packets for the streams) as well as raw stream demuxers (that return pieces of data belonging to a stream and you need to form full packet using a packetiser). And of course you can have simply raw streams like MP3 that needs a packetiser but no demuxer. That’s why I’ve made a DemuxerObject (yes, very original name) that encapsulates them all and represents all of them as a normal demuxer;
• and finally I’ve discovered that I can call SDL_UpdateYUVTexture instead of copying frame data into the texture manually. And then I discovered that it did not work with the time display (because it also wrote to the texture directly in presumption that it will update some pixels on the frame; there is a note in the documentation telling not to do so but it worked by chance before). So I’ve changed it to render a separate small RGBA texture and blit it over the frame instead—like it should’ve been done from the start. I somewhat wonder when I’ll have to adapt it all to SDL3 but apparently I can postpone it for now.

That’s all for now. There’s a lot to do, maybe some of it will actually be done.

Grab it from the usual place if you’re interested in it for some unfathomable reason. I’ll try to document the formats when I have time (and multimedia.cx server does not suffer from crawlers).

Update from January 30: I’ve uploaded a fixed version as I broke extracting old-style Cryo archives during refactoring (and before committing), so now it should work. The rest will (not) work in the same way as before.