Kostya's Boring Codec World

Since I have nothing better to do (or the pending stuff makes me thinks I have nothing better to do), I search for a game to look at (preferably with a custom video format with an extension starting with ‘o’, ‘w’ or ‘y’ but any undocumented custom video format would do).

One of those games was Blood & Lace (despite the name it’s not about somebody cutting fingers while trying to put shoes on; whatever—I mostly study games, not play them). It had some videos using Indeo 4 or 5 plus some animations apparently on the game engine. Those were compressed as well as all TGA files. So out of curiosity I looked at the binary specification and apparently most of the files are compressed with LZH (the old compression method with dynamic Huffman coding used in LHA) using custom header starting with JFX1. And TGA files use JGF5 header which is almost the same but has image width and height in it before LZH-compressed data.

That’s another one in my collection of common LZ77-based methods used in multimedia compression, I wonder what will be next.

You can blame Paul for interesting me enough to spend some time on research. He discussed how he implemented deflate support for librempeg and I got curious myself how other fast LZ77-based encoders do the matching.

The traditional approach is to have a hash chain (i.e. associate each dictionary position with a hash, usually calculated from three symbols, pointing to the next position with the same hash). It’s simple and works surprisingly well. Almost all compressors I looked at used either this approach or a hash map.

The only exception I saw was GLZA which described itself as counting symbol frequencies first and then building partial suffix tree just for the most common symbols.

And finally I encountered the paper by Sadakane and Imai from 2000 where the authors proposed two improvements: introducing the secondary hash for the collisions in the hash chain or, alternatively, using suffix sorting (in a suffix array). They report that using two-level hash improves performance significantly, especially for large dictionary sizes but it’s negligible for 64kB or less, while suffix sorting time seems to grow logarithmic from the dictionary size but it beats one-level hash at dictionary sizes of 256kB and two-level hash at dictionary sizes above 1MB.

So, apparently, this is yet another case when keeping it simple is advantageous. Compressors with larger dictionaries will benefit from a different approach, while deflate has maximum dictionary size at 32kB and anything but brute force search will be about equally good.

In either case, I don’t regret spending time on this quick research.

In the previous post I’ve mentioned that one of the levels contain an unfinished witch puzzle probably based on Match Two that also contains various photos of the (presumably team and their families (about a dozen of them actually). I also wanted to tell a bit more about it and since I’m working on boring parts of NihAV and it will take a while, why not tell the story now?
(more…)

I guess everybody else has reacted on his post about MPEG crisis so I can do that as well. So, $postname—most people just don’t understand his outlook. If you interpret his words from his point of view it’s clear he’s right for most of the things.
(more…)

Sweden has a lot of local bus routes and every region (or län) has its own most popular bus route:

• for Stockholm and Örebro län it’s “Ej i trafik” (something like “not participating in public transit service”, “trafik” in Swedish often means both [car] traffic and public transport service);
• for Södermanland it’s “Är ej i trafik” (“Is not in service”);
• in Östergötland it’s “Tyvärr, ej i tjänst” (“Sorry, not in service”).

The joke is that while there are many numbered bus routes (hundreds in Stockholm län), the regulations make bus drivers rest after completing a route so quite often a bus arrives to the end station, unloads all passengers, changes its route number to the one above and goes away; then, obviously, another bus (or the same one after the driver has rested) comes to pick passengers. Since I almost never travel by bus in Germany (we have trams here after all), most of my bus trips happened in Ukraine and Sweden—and those countries differ in approach to drivers indeed.

Another interesting thing is the variety of buses: in Stockholm län you have buses going on trunk lines—quite often those are articulated buses and they’re always painted blue—and ordinary buses (always red); some buses are double-deckers, like on bus route 676 (Stockholm-Norrtälje) and some coaches are double-deckers too (I still fondly remember travelling on top floor of one from Luleå to Sundsvall—no fond memories about Ukrainian bus trips though). And in Norrland they still have skvaders (aka buses with additional cargo departments). Also buses in Stockholm län quite often have USB chargers for every seat and even WiFi—everything for passenger comfort.

It’s quite interesting that some bus routes are operated by two buses: for example, if I want to get from Bromma to Portugal (a place on Adelsö island near Stockholm) I’d take bus 312 which goes to Sjöangen, there I’d step out, get into new bus 312 waiting there while the previous bus goes to the rest. Also it’d travel on a ferry which I also like for some reason.

So there’s something interesting about Swedish buses after all. But railways are still much better (more comfort, higher speeds, less problems from car traffic etc etc) and definitely more awesome (I’ve witnessed rail bus pushing a fallen fir from the tracks less than a week ago—try finding an ordinary bus doing that). But it’s still nice to know that Sweden has good things beside people, trains, food, drinks and nature.

P.S. This seems to have gone a bit further than just describing how popular bus routes differ in various Swedish regions. Hopefully my upcoming NowABitClearerVideo post would go the same way.

So, it has come to this. How does bitstream reading might work. Here I’ll try to present several ways to read bits and variable-length codes.
(more…)

Unfortunately I was not able to visit Sweden this Easter season — it was merely 6 days in Stockholm. Yet I’ve managed to try one of the reasons I come to Sweden — påskmust. For those who don’t know what it is — shame on you! For the rest here’s my incomplete and biased guide.

Some old julmust photo. Left to right: Nygårda, Eldorado (Hemköp), ICA, Coop, Wasa, Apotekarnes. Lying is the Lidl julmust.

Some old påskmust photo (probably from 2011). Left to right: Mora, Nygårda, Apotekarnes, ICA, probably Lidl, Eldorado (Hemköp), Coop. Lying are ordinary and special Wasa påskmust. Front bottle is from Guttsta Källa.

This year catch. Back row: Wasa special, ICA, Apotekarnes. Front row: Nyckelbryggeri, Zeunerts, Grebbestads bryggeri, Mora, Nygarda, Danish abomination.

So one can divide julmust/påskmust into four categories:

1. Widespread must from large producers or supermarket chains. That includes Apotekarnes, Nygårda and must made for Coop, Hemköp, ICA and Lidl. But not for Netto, see category four for that.
2. Must from Norrland breweries. Nyckelbryggeri, Wasa and Zeunerts are most known. And maybe Mora.
3. Must from non-Norrland breweries. Guttsta Källa, Grebbestads, Hammars (I have to try that one yet).
4. Abominations from people who don’t know how to make proper must. That includes Bjäre must from C*ca-cola, Harboe must from Netto (made in Denmark) and whatever Danish stuff I tried this year. Concentrate for making must at home probably belongs here too.

The taste is hard to describe but it’s really nice and makes me think of liquid bread for some reason. The main difference is Norrland/non-Norrland must. Julmust and påskmust in Norrland style is less sweet and usually has a hint of coffee. Must from large producers is usually sweeter than the rest. Wasa bryggeri produces two kinds of must — special, available only in Norrland and made after Norrland traditions, and ordinary, available in Svealand and with taste closer to the more widespread varieties.

Danish must is either bland or plainly wrong. The one I tried this year is not actually bad, it’s just completely wrong — it contains e.g. raspberry juice and cola extract. If I drink påskmust I want to be påskmust, not a weird mix of Pommac and Trocadero that probably has only water and sugar in common with the other påskmust recipes.

And now is the actual guide. If you want to try it then start with widespread påskmust you can find in any Swedish supermarket, it should be fine. If you like it that way then be happy, if you want something less sweet then try smaller breweries and especially Norrland ones (it’s hard to find it outside Norrland though). And if you are not in season then you can still try something similar — bordsdricka from Wasa or sommarmust from Nyckelbryggeri should be available (in Norrland).

P.S. You can extrapolate it to Trocadero as well except there’s less variation in taste and there’s no supermarket or Danish version.

As you might remember, alternative history genre is modelling events based on real history but with something gone differently. Here’s what could’ve happened with H.265 but didn’t.

So, finally there’s a new standard released — ITU H.265. It promises twice as low bitrate for the same picture quality in H.264. Yet people do not care much about it since industry leaders offer their solutions:

China introduces their new standard for video coding — Hybrid Enhanced Video Standard or HEVS for short. It features quadtree representation of coding blocks, more than thirty spatial prediction modes, block transforms from 4×4 to 32×32 and has one unique feature — motion vectors that implicitly take mirror references from reference picture lists. This standard is nominated for main video coding standard on CUVRD (China ultraviolet ray disc) but gains little popularity outside China.

On2 makes a new codec named VP9 that has no open specifications. After tedious reverse engineering it turns out to employ coding scheme from VP5 times, spatial and motion prediction from H.265 with slightly altered coefficients and overall coding scheme from H.265 drafts.

Re… buffering… alNetworks releases NGV at last (fourcc RV50). Again, after long studies of binary specification, it turns out to be based on H.265 drafts with some in-house improvements: using context-specific codebooks for elements coding, ?-pel motion compensation (which is implemented as motion vectors pretended to be ?-pel but in reality several different positions are handled by the same function). The codec goes very popular in China for some reason.

Sorenson releases SVQ7. It is based on old H.265 draft and employs ?- and ?-pel motion compensation. It has some additional features like watermarking and quickly becomes the codec of choice for QuickTime.

P.S. Good thing nothing like this has really happened.

An excerpt from a book that I have to refer sometimes (here’s the source, it really tells a lot about proper relationship. Ask a nearby German for a translation if you need it.

P.S. Next post will be about a codec technical description, I promise.

Italy is a good country (piecewise) — nice scenery, decent food (and pasta), nice architecture…
There’s but one thing that annoys me, I think you’ll be able to spot it on those two pictures.

Milan, a corner of via Vitruvio and via Benedetto Marcello.

Turin, largo Cassini.

I cannot say it for sure but I remember Ukrainian markets (right after closing time) being cleaner than that.