Kostya's Boring Codec World

As you (imaginary person who actually read this blog) I’ve stopped blogging last year. Mostly I did it because I ran out of material to write about. Well, now I have some new thoughts that I’d rather dump on the blog and forget so the blog restarted.

While the previous blog was mostly centred on codec reverse engineering and design and rants about random topics, this version should be more about NihAV development and codecs design. And obviously useless rants on random topics—except on opensource multimedia projects (I’ve said enough about CEmpeg, Libav and such; corporate ones I might still have something about).

Let’s see how well it goes this time…

In case you don’t know telegony is a belief that all offspring of a female will look like her first partner (there’s nothing wrong with it unless you know biology). In the metaphorical sense it means that the original circumstances of the company or project founding (i.e. who, with what goal and such) will affect its development to the end. Like there was a small company producing so-called “ever sharp” pencils that’s still afloat after a century—but who cares about pencils from that Sharp Corporation nowadays? Anyway, let’s talk about various opensource multimedia projects and see how it applies to them.

FFmpeg. The project was created by FFabrice Bellard who’s known for his brilliant software with horrible source code (he’s won IOCCC twice after all). FFmpeg obviously follows the suit and still has a lot of horrible code that people can’t clean up to this day. And yet it’s as ubiquitous as LZEXE packer back in DOS days or even more.

MPlayer. The project was originally created because its author could not find a video player that would support MPEG-2 video and AVI codecs at the same time—so he hacked something from libmpeg2 and avifile. And what do you know, after all these years it strives to play everything by means of ugly hacks. Those include but not limited to: catching SIGSEGV during MPEG-2 video decoding and restarting decoder, patching loaded VfW/DShow/DMO decoders based on .dll name, calling private internals of bundled FFmpeg.

MPlayer forks. mplayer2 was created by Uoti Urpala who had his disagreements with the original MPlayer team and made his own version with streamlined build system and throwing out many hacks of the original code. mpv seems to follow the suit and I guess if the next fork appears it’ll be also done by a disgruntled developer who wants to throw more hacks out and make it more average-user-friendly.

libvpx. Originally (VP3 times) it was a codec using rather well known coding methods, definitely not state of the art, with a confusing source code that was opensourced without any format description beside source code because the company didn’t care about it but wanted it to become multimedia standard anyway. The company name was On2 then, mind you! But if you look at VP8 or VP9 nothing has changed much (I still have the impression that VP9 format specification was written by engineers from that company implementing hardware decoder and benevolently edited and released by Baidu when they don’t care about VP9 any more because there’s VP X coming).

Derek B. A brilliant reverse engineer who did his first codec (VBLE) by struggling with disassembly and then asking the codec author for the sources. I’ve mentioned before that his best decoders were REd in a very original way: by declaring the intent to do that and waiting for somebody else to do it. Obviously not a project but his story fits so I thought it’s appropriate to mention him here.

VLC. As you might remember the project started to justify a high-speed LAN in some French École Abnormale (because it was not the only high school in France named École Normale in case you wonder). And what do you know—the project went fine as a business project and does so till this day. Though if they ever switch from Discworld-themed naming to Ubuntu-like they should go with Glorified Gstreamer. Why? Because while venerable old projects like XAnim, Xine or MPlayer demonstrated high-class by having their own codec reverse engineering work, VideoLAN went the way similar to the previous story—waiting until somebody does it elsewhere and then announcing support for that format.

Moral of the story: think before you start a project, people may make fun of it afterwards.

Sometimes I hear that voting in FFmpeg is worse than in North Korea. Obviously people don’t know much about voting in North Korea or they wouldn’t make such statements. Here I shall try to have a short overview on voting in two similar yet different Asian countries and compare it to FFmpeg. My knowledge about North Korea comes from posts of Russian researchers, at least one of them lives in Korea and their information looks legit to me (because it lacks political agenda and has even small details mentioned that correlate well with other information from people visiting DPRK). For the other country it’s various sources not from state media (because such information is often omitted there or you hear simply outright lies). For FFmpeg I obviously have my own experience and observations from their mailing list.

North Korea

Maybe the main reason why it makes people think about FFmpeg is the fact they claim sovereignty over the whole Korean peninsula and even appoints special people to do merges govern over regions still under occupation and even promotes them time from time. South Korea actually does the same except for useless staff but they recognize people with North Korean passports as their own citizens.

Anyway, voting. The system is rather simple: you have one candidate per region and all people vote for him. The ruling member of Kim family should get 100% support in his region (around Paektu Mountain if you forgot that)—and 100% means that all voters should come and vote (I guess it’s obvious how). In other regions some voters may skip it in case they are very ill. I don’t remember whether they can vote against but it’s rather unthinkable too. There’s a story about North Koreans fleeing to China and seeing a demonstration in South Korea on the TV—their reaction was “Why do they allow it?! How can the President run such a country?!”. So people there are quite well conditioned and voting goes smooth.

Russia

This is a country with a variety of approaches to voting—some elections nobody cares about and they can be even fair (until an inappropriate candidate is elected and then they have to correct it), some elections try to keep an image of honesty in order to show outsiders that the system works fine and elected candidates are legitimate (in that case they simply try not to rig it as blatantly), some elections are rigged in the most blatant way and even more and in the ideal case there are no more elections (under some stupid pretext they’ve got rid of governor elections and now in some towns and cities mayors are not elected either because that saves money). And referendums there while still theoretically possible can’t be on any question related to government or status of some region or the questions that are decided by government.

So depending on luck in some elections a vote can matter, in other cases it doesn’t matter and in some cases it matters that much that the votes are cast and counted without voter’s participation (some regions constantly report that over 100% of voters were present and there’s a Russian meme 146% that appeared because when they reported result for parliament elections in Rostov region IIRC the percents from different parties added up to that number and there were some other regions with total sum over 100%).

There are many tricks to get desired results—inventing new demands to filter out unwanted candidates (their neighbour Belarus has a joke “In order to be eligible as presidential candidate the person must have at least five years of presidential experience”), the same voters voting again and again (because there’s a special document allowing a voter to vote in other region—and groups of people can have a dozen of such permits per member and thus vote repeatedly in several places), putting a sheaf of “properly” filled ballots into ballot box or simply counting them as you see fit no matter what was the actual vote there.

Similar story with petitions—they are often masked with similar petitions or later an expert group finds that petition to be infeasible or contradicting the law.

FFmpeg

In the old days voting was usually called mostly on naming issues and it worked. But then disagreement with the practices of the FFmpeg leader (like committing code without any review and despite objections) escalated to the point of The Split but before that there were ugly votings that included old MPlayer members that nobody cared about in FFmpeg (because the leader said everybody with commit rights on svn.mplayerhq.hu should have a vote). So after The Split and another ugly voting there were two projects. I don’t remember any voting in Libav but in FFmpeg this tradition still holds. Like recently there was a voting committee formed and there were at least two serious votes (not just a new season logo in trac)—for code of conduct (because every project should have one but not necessarily follow it) and for banning Carl Eugen Hoyos for some time. The first one obviously passed, the second one rather expectedly failed. But then A Person Known For Resigning As Leader took an action that should be allowed only to leaders and banned some people for 24 hours from the mailing list.

Well, I think it’s clear now that FFmpeg voting is not on North Korea level because there’s animosity there that can be expected only from current MPlayer team but not FFmpeg. But is FFmpeg on par with Russia? Maybe not yet but it tries hard IMO.

Continuing the theme set by the previous post, let’s talk more about confusing names introduced by H.264. I mean CAVLC and CABAC.

CAVLC stands for Context-based Adaptive Variable Length Coding. While technically true because it employs variable-length codes and the code set is selected based on context it’s nothing special (and I’ve not spotted anything there that would make it “adaptive”). Again, it’s a trivial thing less exercised before because they had less ROM for codebooks. The idea of “let’s select codebook depending on top and/or left decoded values” it too trivial to get an own name IMO.

CABAC stands for Context-based Adaptive Binary Arithmetic Coding and the name is partly stupid and partly misleading. But before I explain why I want to present some history and terminology.

Arithmetic coding was developed in late sixties to early seventies but mostly known by work of Rissanen and Langdon that resulted in many IBM patents. The idea is that you can assign probabilities to various symbols, send them to the coder and the coding result is a long fraction belonging to the range obtained by multiplying the ranges in sequence. I.e. if we have probabilities for A, B and C as ranges [0; 1/3), [1/3; 2/3) and [2/3; 1) then AB is coded in [1/9; 2/9) range and BA is coded in [1/3; 4/9) range. It’s the ideal coding method since it codes probabilities in the minimum possible amount of bits (unless you remember it’s real world and we don’t have infinite-precision arithmetic; still, the losses are very small and there’s no better coding method).

And in 1979 G.*.*. Martin (no, not the writer known for Tuf Voyaging) introduced range coding. Which is absolutely the same thing except that (de)coder maintains low and range values instead of low and high values in a conventional arithmetic coder (hence the name). Since it was kinda not covered by patents it got more popularity over the years.

And because dealing with arbitrary probabilities usually involves division by an arbitrary integer (and maybe increased coder precision) the further improvements were for sacrificing efficiency for speed until it boiled down to coding just two symbols and creating more elaborate models to code input that takes more than one bit. Arithmetic mode in JPEG seems to be simply feeding bits from Huffman codes and such to Q-coder (patented by IBM and thus extremely popular in the wild) that squeezes a bit more entropy out of them. Then you create an advanced version (MQ-coder) and push it into JPEG-2000 until binary coding is popular in image and video coding.

So, CABAC is:

1. Context-based — yes, static coding would be a tad more effective than Huffman coding applied to bits (hint: it gives no savings). The problem that it’s the first step of the classical scheme: modelling and providing probability to the entropy coder;
2. Adaptive — see above;
3. Binary — true (just remember it codes not bits but most and least probable symbols);
4. Arithmetic — actually it uses range coding;
5. Coding — nothing to argue with here.

In general, the naming is a lot like USSR which was hardly a union, probably not soviet (whatever that word means—literal meaning is “belonging to the councils”), republics were just provinces (or local despoties) but it was more or less socialistic (to the point its ideology can be called international socialism and it was founded by SDAPR(B) too).

And I’d like to point out that CABAC should refer to the whole process of binarisation+context selection plus coding the result, not just the exact implementation used in ITU H.264 and ITU H.EVC (even if it’s called CBAC in AVS and “we have completely different coding” in VPx). And if you want an example of context-based adaptive binary non-arithmetic coding look at ELS used in G2M2 (and if you drop binary coding then you have examples in every other advanced lossless audio codec).