Hardware acceleration for NihAV video player

October 18th, 2023

Since I was not fully satisfied with the CPU load from my H.264 decoder (and optimising it further is too tedious), I decided to take a look at VA-API hardware accelerated decoding once again (no Vulkan for me).

It turned out that documentation is not as lacking as I expected it to be, it’s just most of it was eaten by bindgen so e.g. you can get VAImage from the decoded surface but you have to look into source code for its definition because it’s just an alias for semi-hidden _VAImage. And even if you look at the original header files from libva, that documentation is rather scarce anyway.
Read the rest of this entry »

Encoding Bink Audio

October 11th, 2023

As I mentioned in the introduction post, Bink Audio is rather simple: you have audio frames overlapped by 1/16th of its size with the previous and the following frame, data is transformed either with RDFT (stereo mode) or DCT-II (per-channel mode), quantised and written out.

From what I can tell, there are about three revisions of the codec: version 'b' (and maybe 'd') was RDFT-only and first two coefficients were written as 32-bit floats. Later versions shaved three bits off exponents as the range for those coefficients is rather limited. Also while the initial version grouped output values by sixteen, later versions use grouping by eight values with possibility to code a run for the groups with the same bit width.

The coding is rather simple, just quantise bands (that more or less correspond to the critical bands for human ear), select bitwidth of the coefficients groups (that are fixed-width are not related to the band widths) and code them without any special tricks. The only trick is how to quantise the bands.

Since my previous attempts to write a proper psychoacoustic model for an encoder failed, I decided to keep it simple: the encoder simply tries all possible quantisers and selects the one with the lowest value of A log2 dist+λ bits. This may be slow but it works fast enough for my (un)practical purposes and the quality is not that bad either (as much as I can be trusted on judging it). And of course it allows to control bitrate in rather natural way.

There’s one other caveat though: Bink Audio frames are tied to Bink Video frames (unless it’s newer Bink Audio only container) and thus the codec should know the video framerate in order to match it. I worked around it by introducing yet another nihav-encoder hack to set audio timebase from the video so I don’t have to provide it by hand.

So that’s it. It was a nice experiment and I hope (but not expect) to think of something equally fun to do next.

Bink encoder: coefficients coding

October 10th, 2023

Somewhat unrelated update: I’ve managed to verify that the output of my decoder works in the Heroes of Might and Magic III properly even with sound after I fiddled with the container flags. The only annoyance is that because of DCT discrepancies sometimes there are artefacts in the form of white or black dots but who would care about that?

At last let’s talk about the one of the most original things in the Bink Video format (and considering the rest of the things it has, that’s saying something).
Read the rest of this entry »

Bink encoder: doing DCT

October 9th, 2023

Again, this should be laughably trivial for anybody familiar with that area but I since I lack mathematical skills to do it properly, here’s how I wrote forward DCT for inverse one.
Read the rest of this entry »

Bink video encoder tricks

October 8th, 2023

As I mentioned in the introductory post, there are nine block coding modes and my encoder tries them all to see which is good (or good enough) to be used. What I have not mentioned is that some of those blocks have sixteen variations (quantisers for DCT-based blocks and scan patterns for RLE blocks), which makes search even longer.

First of all, I use the rather obvious approach to trying blocks: order them in a sequence, motion blocks types first, then simple ones (fill, two-colour pattern, RLE) with intra DCT and raw being the last. And if the block metric is low enough then the block is good enough and the rest of the modes should not be tried.

Second, there are two encoding modes: quality-based and bitrate-based. For bitrate-based mode I simply manipulate lambda ratio between block distortion and bits and that’s it. For quality mode I actually collected statistics on different files at different quality settings to see what block types are used more or less. I.e. on the highest quality setting intra blocks are not used at all while on low quality settings you don’t see lossless residue or raw blocks.

So I simply used the option to disable different block coding modes (introduced to make debugging other coding modes easier) and modified the list depending on quality setting.

Then I went even further and observed the statistics of the DCT block quantisers used depending on quality settings. As one could reasonably expect, low quality setting resulting in quantisers 12-15 (and rarely 11) while high quality setting used quantisers 0-10 the most. So limiting the quantisers depending on quality was the next logical step.

And here are some other tricks:

  • on lower quality levels I use non-zero threshold for RLE block so that e.g. a sequence 4, 3, 5, 4 will be treated as a run of fours;
  • in the previous version of the encoder I used Block Truncation Coding (probably the only possible application of it even if a bit unwise), now I’m simply calculating averages of the values above/below block mean value;
  • in rate-distortion metric I scale the bits value, doing otherwise often leads to the essentially free skip block being selected almost every time and blocky moving pictures are better than slightly less blocky still one.

Of course it is easy to come with more but it’s been enough for me.

Bink bitstream bundling

October 7th, 2023

Bink Video organises frame data somewhat on per-row basis and separated into individual streams. That means that data is sent in portions in interleaved fashion: first it is block types, then it’s colour values for e.g. fill or pattern blocks, then it’s motion values and so on. Before each row decoding can start, decoder should check if it still has some data from that stream or read more. For example, in the beginning you may get just enough block types transmitted for one row, zero motion vectors and one DC value for a block somewhere in the middle of the stream; so for the second row you refill only block types, and DC values stream will be queried only after that single value in it has been used.

And to complicate the things further, there may be yet another kind of data stored in-between: RLE block information (scan index, copy/run bit and run lengths), DCT coefficients and lossless residue data.

It’s also worth noting that while version 'b' simply stored stream data in fixed-length bit-fields, the latter versions employed static codebooks to improve compression.

Anyway, how to write such streams correctly? My original encoder supported only several block types and was able to bundle all stream data together to transmit it once for the whole plane. But since I wanted to support all possible block types, I had to devise more flexible system. So I ended up with a structure that holds all data in per-row entries so when the plane data is gathered I can easily decide how many rows of data to send and when more data needs to be sent. Additional bitstream data is also stored there (in form of (code, length) pairs) and can be written for each row that has it.

Beside that I’ve introduced a structure to all stream data for one block. This makes it easy to calculate how many bits will be used to code it, output the data (just append its contents to the corresponding entries in the plane data) and even reconstruct the block from it (except for DCT-based ones). Actually I use three instances of it (one for the best block coding candidate, one for the current block coding and one for trying block coding variants if the mode permits it) but that’s a minor detail.

In either case, even if this approach to coding is not unique (TrueMotion codecs employed it as well, to give one example), it’s distinct enough from the other variants I’ve seen and was still quite fun to implement.

Bink encoding: format and encoder designs

October 6th, 2023

Here I’m going to give a brief review of how Bink formats (container, video and audio codecs) are designed and how it affected the overall encoder design in NihAV.
Read the rest of this entry »

Documenting failure(s) of a Bink encoder

October 5th, 2023

Since I really had nothing better to do, I decided to try writing Bink-b encoder. Again. The previous version was a simple program to compress image sequence into a somewhat working video file, the new version supports all possible features: motion compensation, all block types including DCT-based ones, quality- and bitrate-oriented compression modes and even audio.

I worked on the encoders not because I have any real need but rather in order to both understand better how Bink codecs work and what tricks can be employed in the decoder. Bink video supports different block coding modes, from rather ordinary DCT to RLE using a custom scan order and special mode for coding motion residues. Bink audio is a simple perceptual codec that should still give me some possibilities for experimentation (of course I remember how I failed to write AAC encoder, but maybe with such simple format the outcome will be not too horrible?).

In the following posts I’ll try to describe how some things in Bink format work, what difficulties I had to overcome and what the results are.

Eventually I want to test my implementation against the original decoder (by creating a custom heroes3.vid or video.vid for HoMM3). Also it is rather easy to enhance my work to produce latter-version Bink videos but I’m not sure if it’s worth doing that as there’s a good free encoder for it already (probably a much better one than I can ever create) and Bink format is not a good candidate for normal videos as it was created for game cutscenes with the only options to keep or end playing, no option for rewinding back at random place to repeat scene you missed (or skip some boring part).

In either case, it’s still a nice experience. After all, NihAV is about experimenting and learning how stuff works and Bink offered a lot of new things to try.

On emerging dictatorships

September 16th, 2023

In some cases authoritarian governments come suddenly, usually as the result of a coup or a legal loophole (Article 48 of Weimar Constitution is an example codified in ages), in other cases the power grab goes gradually like in the famous frog-in-the-boiling-water metaphor. It’s easy to act surprised, as the things are almost the same as they were yesterday or last year, but usually there are tell-tale signs of a country going into authoritarianism. Here I’d like to remind about them.

Probably the most important of them is the judicial branch reform that de facto cancels its independency as the government controls who gets appointed as a judge. After you get loyal judges who’s going to stop your unlawful reforms? We had such situation in Ukraine during 2010-2014 (even without any factual reform; but more about Ukraine later), Poland tries to get it (and that’s disturbing), Hungary has done it (of course), Israel is doing it right now (which may end too bad for the country) and so on. But usually at this stage the things are so bad that the actual dictatorship (or demokratur) is merely the next step, are there any earlier signs?

Again, one of the important but rather late signs is unwillingness to part with power. It may happen in any circumstances but usually it’s parliamentary republic with a dominating party and the same prime minister for decades. There may be a president but he or she is a nominal figure while the prime minister remains at power (see Georgia, Germany, Hungary or Israel). Of course it may still not work out like with Merkel, who had to retire after sixteen years, without leaving a good successor candidate in her own party; IMO she should’ve got a prison sentence for serving russian interests but she got awarded a Grand Cross for that instead. I feel the maximum term for any such post should be about twelve years and anybody, who like the current (since 2010) Hungarian prime minister say they want to remain for another twenty years, should be put to prison immediately. South Korea has a good idea with its presidents, a good deal of them were either shot or imprisoned after their term was over. In Fourecks they imprison politicians right after they’re elected (so save time)—but alas it’s a fictional continent.

But usually it’s not one single person but somebody with a support of major party. And, surprisingly enough, those parties usually have something in common: they rely on populism, promoting “traditional values” to the extent of being against anything new, and very often seeing USA and “the West” as their enemies. In other words, promising to return the country to the times of past glory (or at least when the situation was not so bleak) and blaming foreigners and their agents on everything bad that has happened since those times (I’m sorry if that does not reduce the list of possible candidates by much, that’s the state of modern politics). I should probably add another thing to cheap populism: creating show by solving issues nobody had like renaming a country. I can understand why Congo does not want its capital named after the Belgian king who is responsible for mass genocide in the country (and for the same reason Ukraine renames its towns and streets), I can understand why a country renames itself from Rhodesia, I can understand when a country introduces a preferred name while still recognizing the old one (like Czechia or Sakartvelo). But demanding that your country called abroad differently without any apparent reason for renaming sounds like a cheap gesture to show your own people that your country is proud and how others have to comply with it (while drawing attention from more important issues). In case it’s not obvious I’m talking about The Country Formerly Known As Turkey and The Country Most Likely To Be Known As Modi Raj.

The very minor signs would be the corruption potential: if a party serves interests of an oligarch or an oligarch group it is naïve to expect from it to have no attempts to seize power and hold it as long as possible to exercise it for profit and to avoid prosecution. And a thing related to it—friendship with russia (usually paid from the russian side).

In the end I’d like to talk about Ukraine to serve as an example. There were two and a half attempts to grab power in its recent history. First attempt was made by the second president, Leonid Kuchma: back in the day he even traded some presidential privileges for some additional executive functions he could perform. Over the years he increased his power, often with a help of shady people like Pavlo Lazarenko (famous for being a Ukrainian prime minister, a citizen of Panama and building so wide corruption network that he served a prison sentence in the USA for it) or Yuriy Kravchenko (who turned police into his personal mob). Kuchma often solved problems by firing the current prime minister and selecting a new candidate. Still that has not saved him from the consequences of murdering Gongadze and the Cassette Scandal. Another fun fact is that Ukrainian oligarch Pinchuk had a nickname “Kuchma’s-son-in-law” (because he really was one). It is also said that he tried to game the system by trying to organise 2004 elections in such a way that both candidates would lose and he would remain by default. Those elections and rigged counting though caused so much public outrage (called the first Maidan) that they had to repeat the vote.

The second attempt was when viktor yanukovich assumed the post of the president and the Party of Regions (from which he came) got the majority in the parliament. Those were dark times when he used kangaroo courts to deal with his opponents (because no judge could be appointed at that time without approval from the President’s Office) and cancel previous constitutional reform limiting presidential power; people affiliated with him (“the Family”) could raid and steal other businesses and it is said they managed to steal a sixth of the country budget every year in addition to that. As you know, it ended by him selling Ukraine to russia, fleeing the country and starting the war that goes to this day. It is less remembered that during his last days of presidency his party tried to pass the same laws as in russia to limit the freedoms and allow to prosecute the protesters easily. It did not work out.

The half-attempt is when Volodymyr Zelensky became a president and his party got majority in the parliament (mostly thanks to his image). He had not so great decisions in the beginning (and the parliament supported them) so it could end badly. But then a führer decided to take Kyiv in three days and the Ukrainian nation united against the enemy once again. Since then Zelensky (and somewhat his party) act decently because it’s the matter of survival. Who knows how it will go after the victory but for now I have nothing else to say about him.

I hope this brief review of Ukrainian political history served an example of how important it is to stop authoritarianism when you can still do it without human casualties. Revolutions often take a much higher price…

NihAV: now with GIF support

September 11th, 2023

One would wonder why. The answer is simple: I merely wanted to play with LZW encoding and created a GIF encoder. Then I needed to debug it and thus ended up with a decoder as well. And while I was at it I added animated GIF support for both decoding and encoding.

I’m not going to repeat on how it works, it’s been written in all possible textbooks and tutorials on data compression (and then some), I’m more interested in implementing an efficient encoder for it. I should remind you that LZW compression was patented (at least by Sperry and IBM) and that patent introduced a lot of chaos in multimedia before MP3 or H.264 were a thing.

The algorithm simply tells you to find a match for the input string in the dictionary and add a new string to the dictionary. You can keep the actual strings in the dictionary (simple but not very effective), you can keep the reference to it in the input (simple and saves a lot on dictionary space but not very effective and you can’t feed it input by chunks), you can keep the same dictionary structure as the decoder and try to match input to the code sequence (the most compact way to store the dictionary but not so straightforward to use; more on a practical extension of this approach at the end of this post). Since I do not care about wasting whopping two megabytes of RAM on the dictionary, I implemented a simple trie: each node contains a code ending at that node and 256 pointers to the next next trie nodes (each code/pointer fits into 16-bit integer with zero as “invalid value” pointer). Of course it can be made more compact but I prefer simplicity and clarity.

Now, the question is whether the compression efficiency can be improved somehow. Since the decoder expects encoder to work in a certain manner we can’t change format. The tricks that work good for LZ77 like lazy matching do not work that great for LZ78: you have dictionary state changed at each step and you don’t know which entry will be more useful in the future. Also emitting shorter matches means we also litter the dictionary with duplicates, which does not help compression in the long run either.

Thus the only thing we can use is creative dictionary clearing. E.g. we can emit reset code after every N symbols encoded to keep the code length constant (that’s the trick various libraries used to produce the compliant stream without doing any compression and thus not infringing the patent), or you can keep the dictionary filled with what it was until the very end (and if data properties change your compression ratio hurts), or (as most encoders do) you simply reset the dictionary after it gets full. But can you do better?

I tried two heuristics. First, I tried segmenting data by having a sliding window and comparing the character occurrence in each half, if those differed by a lot then it was a good place to restart. From what I heard, this simple approach allows better compression for LZ77- and BWT-based compression schemes. In this case it helped only when compressing the data that could not be compressed at all (e.g. greyscale continuous-tone images), in other cases the results were worse than with the default strategy. The second approach was simple: keep the rolling average of last, say, sixteen match lengths and if it drops significantly when the dictionary is full then it’s time to clear it. Surprisingly enough it seemed to improve compression for several fractions of a percent in general cases (and sometimes worsened the ratio on hard-to-compress files by about the same amount) so I kept it.


And while talking about GIF and LZW, here are some words about FFmpeg support of GIF: it’s rather laughable. While encoding to GIF has been supported from the early days (from 2002, to be less vague), actual LZW compression support was introduced only in 2009 (using a work of some Summer of Code student from 2007; the notorious patent on LZW compression had expired by that time). A bit later in the same year the encoder was improved to work with paletted input instead of RGB24 (which was maimed to use fixed palette anyway). In the same time the original animated GIF encoder+muxer (not to be confused with now improved single-image GIF encoder) kept existing with all the original deficiencies (RGB24 input, fixed palette, no compression) so by encoding to .gif without specifying image2 muxer you’d get significantly worse results. I heard it’d been improved at last back in 2018 but I have not been caring before so why start now?

The interesting thing there is that LZW compression employed for both GIF and TIFF seems to be based on compress approach with a hash table. Essentially the dictionary is stored in the same form as in the decoder (a reference to the previous code plus suffix character) but indices are hash codes instead of sequential entries and the encoder in a decoder mirror mode: it traverses the table to find the code that corresponds to the current code plus a new character (and if it’s not found, the prefix code is output and new code pair is added to the dictionary). Also it seems to compress data slightly worse than the straightforward implementation in some cases (e.g. in my tests one 320×240 PGM file got expanded to 83159 bytes instead of 83132 bytes and another 112×288 PPM file got compressed to 10371 bytes instead of 10366 bytes; the difference is negligible but it’s there). I suspect this is caused by hash collisions i.e. in some rare cases a shorter code and a longer one have the same hash and the former gets selected even when the latter should be better.


In either case, this might have been not a very useful exercise but it was fun and somewhat educational too. Now only to find a thing to do next…