Kostya's Boring Codec World

So it has come to this, some events and discussions made me write this post.

How I imagine the perfect process for new codecs? It’s rather simple model: you have some places where ideas and enthusiasts swarm and from their work and selecting best ideas new candidate codec is born.

There are such places for all codec types: audio enthusiasts can find testers at Hydrogenaudio, video enthusiasts can talk at Doom9, general and image compression people seem to be present at encode.ru. In first approximation it works as expected—people propose ideas, test new compression programs and report benchmarks, suggest improvements. What can be wrong there? Just one thing: people making software incompatible with anything else (custom containers/archive formats) and trying to push it on everybody. After you invent some format make sure it works in some standard environment (for compressors it’s usually single file compression mode, .tar.xz seems to be more popular than .7z even if they use the same LZMA algorithm; for codecs it should be the standard container—even Matroska would do). And document the format too—properly instead of usual “bug off” level.

There are standardised codecs that undergo similar process: various companies or researchers submit their work, a base for a new standard is chosen, new proposals try to improve it. And then companies start to push their patented shit there and that’s where the system goes wrong (QMF in MPEG Audio Layer III anyone?). It’s not better when some company tries to push its product as a standard without any evaluation (and thus we get wonderful line of SMPTE VC-x codecs for instance).

And there’s OggXiph. This is again a community that designs codecs mostly because they can and pushes them mostly because they’re Free™ and OpenSource™ and they mostly suck otherwise: Ogg format is for streaming not good for anything, most people still don’t know that it’s Ogg/FLAC because it was developed outside (and has horrible raw stream format), Speex has no readable specification and easier understood with disassembling the library rather than reading source code, Theora is an outdated enterprise grade code, Opus has its issues (but it’s rather good, one cannot deny that), Daala will probably never happen.

And what do I see in recent news? Alliance for Open Media plans to release first draft of their codec soon and it is:

• hosted on baidusource.com;
• for now just libvpx with some names changes;
• everything else about it screams Baidu too.

It if looks like Duck, produces codecs like Duck and has the same source code as Duck, then it probably is DuckOn2Baidu.

At least in the old times there was some competition of ideas in codecs so one could choose between different codecs giving good results—and in some cases they were available for various ecosystems too (e.g. Indeo was present in AVI and MOV, ClearVideo managed to get into AVI, MOV and RM). Now it’s just foam of lossless codecs that even their authors forget about next year and one or two companies pushing their stuff on everybody. And that makes me sad.

It’s time to say myself: you are no longer relevant. All remotely useful codecs have been reverse engineered already and most of them are obsolete. Everybody uses either H.26[45]+AAC or VP{3,8,9}+Opus and nothing else is required (even by VLC). And I grew tired too if it wasn’t obvious from my previous posts (I don’t even blame lu_zero anymore).

And thus my plans are to document Duck TrueMotion 2X and VP4, ClearVideo and hopefully VX.

In NihAV (yeah, like it’ll ever happen) I decided to implement just fringe codecs like those and no new modern codecs maybe except Bink2 and WMV3 (I know what should be done to support beta P-frames there but the libavcodec decoder is so unwieldy that my brain switches off trying to analyse how to do that change there; before you say anything it’s a part of the code written before I took over it and failed to make it into full-featured decoder during GSoC 2006).

So, this FOSDEM certain Vittorio gave a talk about reverse engineering codecs, all materials are here. Here are my thoughts about it.

First of all, I gave a talk about similar topic once at VDD 12, it was my first and last public talk. Of course it was a fail and there was no single question asked (and mind you, VDD attendants are usually know multimedia much deeper than ordinary FOSDEM visitor). So I think it takes a lot of courage to give such talk so Vittorio did a good job here.

Now to the remarks about the presentation itself.

He calls himself a pupil of Kostya (slide 2) — the name is not rare so I don’t know which Kostya he meant. Definitely not me as he’s yet to show any signs he has learned something from me.

Slide 6 mentions examples of rip-off codecs and gets it wrong too. Real had some licensed codecs, RealVideo 2 is a licensed Intel rip-off of H.263 (and surprisingly Real had even one original codec, lossless audio one). Oh, and the VP family starts with VP3, before that it was Duck TrueMotion 1/2.

Categories mentioned on the next slide are rather random subsets of all video codecs out there. I’ve REd several codecs that do not belong to either category (one of them was used in Hedgewars clones called Worms BTW).

TDSC part of the talk is remarkable for two things: 5-line tool (slide 16) is something I write from heart when I’m too lazy to find the previous version of it and it actually took less time to RE it than to talk about how it was done (the main issue there was to call JPEG decoder inside TDSC decoder).

As for Canopus HQX — I’ve written about it years ago. Beside the profile-specific tables there’s actual decoding to be done (you know, VLCs, DCT, that kind of stuff). But large tables in binary specification fend off reverse engineers quite often.

So, it was a good introductory talk but I haven’t missed anything by not attending it.

Everybody knowing even a bit about me knows that I live in Germany and I’d rather live in Sweden. One of the reasons is that Sweden feels like future (i.e. improved) version of Germany, and here I finally explain why.

Railways. While railway system in Germany is mostly fine it still can have some improvements: train carriages should have an electric outlet per seat. Now it’s fulfilled only in ICE 1st class seats without neighbouring seats. Also hassle-free (or simply free) WiFi onboard. Also it would be nice to have tilting trains like X2000 because it’s all fine and good when you have dedicated high-speed line but quite often you don’t and it would benefit more to have higher speed there (quick example: route Mannheim–Saarbrücken takes 1:32 by Regional Express with its 6 stops or 1:19 by ICE/TGV with only one intermediate stop). And Sweden is more liberal in a sense that now you have line Stockholm–Göteborg serviced by both SJ and MTR expresses (compared to that France where they mark every railway station as belonging to SNCF feels like Ukraine).

Service. Sweden has supermarkets open every day (shorter opening hours on holidays of course) and they also contain local post office too (here post offices are usually selling stationery and some goods from local supermarket instead and share the space with Postbank instead). In Germany almost everything is closed on Sundays. Also it’s funny how in Sweden Lidl can be considered low-tier supermarket (Hemköp/Willy:s, ICA and Coop are much better), in Germany Lidl is considered middle-tier supermarket and in Czech Republic it’s considered one of the best. And there’s much better recycling: all plastic bottles are accepted by the same machine (here you bottles that should be recycled elsewhere and bottles that are not recycled at all), there’s printing on packaging where it should sort to (i.e. hard/soft plastic, paper, metal etc) and water quality is way higher too.

Religion. Sweden definitely doesn’t bother with Christianity that much (and that’s why I enjoy visiting Swedish churches). And as a nice touch even in the centre of Stockholm you have squares named after Odin and Thor and a street called “way to Valhalla”. In Germany they still cannot admit that Wednesday is Wotan’s (or Odin’s) day.

Government offices. Sweden has got it right—census matters are handled by the tax office. Germany is yet to realize that idea. One can point out that in the USA citizenship and taxpaying are the same thing (since you have to file a declaration in any case and pay taxes even if you live and work abroad) but the execution in this case is botched.

P.S. I blame lu_zero for not giving reasons to blame him in this post in the usual way.

So it has come to this. Looks like I should not eat the best Sweden can offer—namely, meat (especially game) and seafood (especially herring). Well, what can I eat in Sweden then?

Not surprisingly there are still many good and tasty things for me. Let’s see…

Chicken. At least in Stockholm any decent supermarket offers warm grilled chicken—full, half or just legs. And each supermarket offers its own brand of chicken sausages to grill.

Dairy products. Beside my favourite cheese and filmjölk varieties there are still many nice and crazy things, like youghurt-quark or drinkable quark (or ordinary cottage cheese that goes well with blueberry-raspberry jam).

Bread and pastry. Sweden has much better bread variety than Germany—that means more different kinds of bread, especially hard bread (if you’re German feel free to stay offended anyway or go discuss beer with Czechs). I also like västerbottenostpaj—a pie with Västerbotten cheese. And semlor. And various Swedish cakes. I should note that Swedes like to use cinnamon and whipped cream in various dishes and rare Swedish cake has no whipped cream. When I was staying at an hotel in Örnsköldsvik (or simply Ö-vik for locals) it has a large bowl of whipped cream among other things for breakfast. And I guess if I simply sprinkle some cinnamon onto a lump of whipped cream it will make Swedish Minimal Cake (I’d like it for sure). And of course marzipan pigs in season.

Crisps(chips). You have it under both names and they are extremely tasty. And when Swedes get bored with potatoes they can make any root into chips, including the ones I’ve never eaten in other form. Here in Germany I bought a packet of chips only once and it was Svenska LantChips of course.

Snacks in general. They usually occupy half of my bag when I return from Sweden (the rest is mostly drinks and other stuff). Wonderful nut mixes, dried fruit and berries, various confectionery things. And of course all supermarkets (beside lidl-iest of them) have naturgodis section where one can mix various sorts of these (think of loose candy stand but with dried strawberries, roasted almonds, peanuts in chocolate and such). And loose candy stands with at least dozen varieties are really everywhere.

Fruits and berries. Paradoxically I can buy vendetta oranges in Sweden but I’ve not seen them here in Germany—Sweden must be closer to Italy then (BTW I still blame lu_zero for not recognizing short name for Sicilian blood oranges despite pretending to know a lot about citruses). There’s wider selection of fruit than in Germany. And there’s much much better selection of berries. You have traditional raspberries, blueberries, black and red currants, RIMs, strawberries and also Nordic berries—Swedish blueberries (they are smaller and have more intense taste), lingon, cranberries and cloudberries. In Norrland in season you can get even more. On my arrival in December I bought some cherries in supermarket—they were available both fresh and frozen (and it’s hard to buy even frozen cherries in Germany outside season). And I like cherries, especially sour ones (BTW I blame lu_zero for being a competition).

Drinks. Sweden has the best water in the world and one can enjoy drinking tap water there (unlike tolerating tap water in Germany and doing it at your own risk in Ukraine). And that’s why a lot of drinks are sold as concentrates that you have to dilute yourself in proportion 1:3 or 1:6. And because it’s Sweden you have good selection of drinks based on berry juice. I especially like blueberry-cranberry and blueberry-raspberry drinks and of course lingon. Carbonated soft drinks are the best in the world too (and if word Trocadero doesn’t tell you anything you’re reading a wrong blog) but I wrote about it many times.

And of course julskinka. I’m Ukrainian after all.

Last year I’ve said some harsh words about some Danish påskmust. Just in case I was wrong I decided to recheck it and bought another bottle. Here are the pictures:

In case you don’t see the list of ingredients it contains:

• carbonated water;
• elderberry juice;
• blackcurrant juice;
• sugar;
• grape juice;
• malt extract;
• spices;
• caramel colour;
• hops;
• citric acid.

And it tastes like POSIX julmust from AIX brewery would taste—it has right ingredients but also lots of things normally not found in julmust and the taste is weird in result. Only people with perverted taste like Danes (remember, one of them invented C++ and is not ashamed of it) or lu_zero(whom I blame for his tastes quite often) would like it.

Last week I’ve been attending a fifth Libav coding sprint in Pelh?imov. Here’s a report from the host of the current sprint (she was amazing, many thanks). It was fun indeed (some fun provided by Lufthansa canceling my flight because of strike).

It’s the third sprint I attended and there’s a pattern in them. Even if they are called coding sprints there’s not so much coding going there, it’s more discussing various stuff and food than actual coding (though Anton spends a lot of time fixing some decoder usually). As I’m no longer a Libav developer, I simply hang around and try to provide enough trolling and proper drinks, sometimes even sharing a bit of knowledge if anybody wants to listen.

Another recurring theme is AVScale, a saner replacement for libswscale. It gets discussed during the sprints (since Summer 2014) but nothing substantial gets done. The only things we got so far are my proof of concept implementation (I’ll present it later in my post about NAScale, it’s the same thing) and something hacked by 1-2 Italians under influence of alcohol in a couple of hours (with great comments like //luzero doesn't remember this) that has Libav integration but no functionality (my code is complete opposite of that — standalone and doing some useful functions). Well, just wait for new posts about this, they’ll appear eventually.

In general I attend sprints just to see people and new places and have some fun. Among the places where sprints took place — Pelh?imov, Stockholm and Turin — I’d say Stockholm was the best so far as it is the easiest to reach and has the best food to my taste (plus thanks to SouthPole AB hosting more people than at any other sprint). I should attend a sprint again some time.

P.S. I still blame lu_zero for not writing anything about it yet.

I like a good read with analysis of random stuff. The problem is that the planned series of posts on parallels between social organisations and software development are not written yet.

The first post would be dedicated to the idea supplanted by bureaucracy. This happens when somebody has a good idea like “let’s create X foundation to promote good thing Y” and with time it turns into monopoly that dictates the rules to everybody else in that area. A special attention would be paid to the ways such organisations maintain “democratic” façade while making all decisions in private — like with introducing many almost useless contributors into voters and convincing them to vote in the way organisers want. An addendum about how such non-profit organisations get their incredible amount of money would be good too. And if you’re still in need of an example — think about any sports organisation like IOC or FIFA.

The second post would be about cultists — not people adhering to some religion but rather people blindly following something and not even thinking that other people might have other views and needs. For example, iUsers or those who program in Oberon dialects (that seems to include Go despite it being not a direct descendant). The main problem with them is that those cultists usually force their fetish as the only proper solution and the main answer to “but I want to do that” is “it’s not needed and I’ve never did it myself”.

The third post would be about a common tactic switching from peculiar details when advertising stuff to blanket statements when defending from criticism (or vice versa). Among other things it’s very common for Oberon and systemd advocates in a fashion like “Feature X? We have it right in Y. Y sucks? Well, it’s just a single dialect/module, the whole system is wonderful, stop attacking it.” It would be painful but giving parallels between this and terrorists/peaceful Islam would be proper too.

And of course I blame lu_zero for not writing this.

Even if I’m no longer Libav or FFmpeg developer I still look at both projects’ development mailing lists (on FFmpeg’s one mostly in faint hope that Peter Ross submits anything awesome again).

So one day I see this message. The “former” leader calls a large share of commits they get “enemy merges” (and it cannot be humorous, it’s not mean enough to be Austrian humor). Well, nice attitude you have there. And you know what? This might be a semi-official position there.

I was present at FFmpeg-Libav discussion at VDD (since I was not noticed by Jean-Baptiste I remained while other outsiders were kicked out — here’s the recording of public part). There I even managed to ask a single question — what’s really changed since Michael’s resignation. FFmpeg people failed to answer that. Beside not making merges anymore Michael still announces and makes releases and does whatever changes he likes without reviews; he’s still a de facto leader in my opinion. I’m yet to see FFmpeg having defined rules stating something different (even Libav has something). Another fun fact from that meeting was some FFmpeg people openly stating they hate Libav merely because it exists.

Again, I don’t have to care about FFmpeg community but working at Libav in such conditions is no fun either (and it’s no fun for many other reasons many of which sadly have something to do with FFmpeg).

So I’d rather follow the advice from the great philosopher Eric Theodor Cartman — “screw you guys, I’m going home”. Developing NihAV at slow pace (i.e. when I feel like doing it) in a neutral one-developer atmosphere is much better.

… When I was a young piglet I liked to read the rather famous paper by Bell, Cleary and Witten discussing general data compression and PPM. The best phrase there was that the progress in data compression is mostly defined by larger amounts of RAM available. I still believe those words to be true and below I present my thoughts on current state of data compression. Probably it’s trivial, well-known, obvious or wrong to anybody knowing a bit about data compression but well, it’s my blog and my discarded thoughts dumpster.

General data compression

Let’s start from the very end — entropy coding. There are two approaches: coding into integer amount of bits or coding as close to Shannon’s entropy limit as possible. For both we have been having optimal coding methods for about half a century (Huffman coding — 1952, arithmetic coding — mid-1970s). You cannot improve compression ratio here, so the following schemes are mostly tradeoffs sacrificing a bit of compression for speed gains (especially in form of (pseudo-)arithmetic coders operating only on binary). The only outstanding thing is so-called Asymmetric Numeral Systems but I suspect they are isomorphic to traditional entropy coders.

Now about let’s look at what feeds data to entropy coders. There are two main approaches (often combined): context modeling (probably the real foundation for current highest compression methods — PPM — was proposed in mid-1980s) and LZ77 (guess the year yourselves). Are there improvements in this area? Yes! The principle is simple — the better you can predict input the better you can code it. So if you combine different methods to better handle your data you can get some gains.

And yet the main compression gain here lies in proper preprocessing. From table or executable code preprocessing (table data usually differs only a bit between entries and for executables you can get some gains if you replace jump/call addresses with absolute values) to Burrows–Wheeler transform plus move-to-front plus RLE if needed etc.

Audio compression

You have four main targets here: general lossy compression, speech compression, lossless fast compression and lossless crazy compression.

General lossy compression follows the scheme established in 1990s or earlier: transform to frequency domain, grouping frequencies and coding frequency bands. Most of the methods are quite old and progress is defined mostly by how much RAM and CPU users are willing to sacrifice on it. For example, Celt (main part of Opus; the other part, SILK, is an ordinary speech codec) is not that much different in design from G.722.1 from late 1990s.

Speech coding follows canons from 1980s too — performing LPC, coding filter coefficients and other information enhancing signal reconstruction (pulse position, pitch tilt etc.).

Lossless fast compression (aka for normal usage) follows the suit too — you have LPC or some adaptive filters used for prediction plus residue coding (usually with Golomb/Rice codes from 1960s-1970s, BTW the original Golomb paper is AWESOME, they don’t write papers like that nowadays).

Lossless crazy compression (aka spend hours compressing it and as much for decompressing) employ the same suit but they have longer filters and usually even several filters of different size applied each after another plus better residue coding schemes.

Image compression

Here you have more variety of coding methods but most of them are very old (just look when Haar wavelet was proposed). Especially funny is that JPEG is still holding strong despite being more than twenty years old. I still remember so-called fourth generation image compression (separating image into region borders and textures to fill them and coding those), it didn’t lift off yet despite being introduced in late 1980s or so.

The only interesting development happens in lossless image compression but neither 2-D LZ77 (WebP) nor context modeling (FLIF) are particularly new ideas.

Video compression

Modern codecs are all so similar and they are usually ripoffs of H.26x (there are two exceptions — Thor, which is not a ripoff just because it was designed with openly acknowledging that some parts are taken from H.265, and Daala, which is more original and it’s discussed below).

So nowadays you have a very limited subset of ideas that were present in video codecs from 1990s — it’s boring macroblocks (now with quadtree partitioning instead of fixed size), motion compensation (now you have more reference frames to choose from though) and binary entropy coder (except for Thor, it went the way of RealVideo 3/4 with context-adaptive VLCs). Even the trend of adding special coding tools for special content doesn’t look that original (if you remember countless screen codecs and MPEG-4 Audio, *barf*).

The only exception for now is Daala that uses more original ideas but I fear it will end the same boring codec because it is not crazy enough to make a breakthrough. I believe it should do more crazy preprocessing at least and maybe better modeling, e.g. taking more than nearest neighbours into account (maybe even use something PPM-like for element coding and not just probabilities mixing). Look at JBIG for inspiration maybe 😉

Conclusions

Don’t expect miracles in data compression to happen anytime soon but couple of percent improvements for specialised fields at least in a decade is possible and even expected.