Kostya's Boring Codec World

There’s Bink variant without any samples known but with decoder present — Bink version d (aka Bink 0.6b). While it’s version closer to Bink-b (aka 0.5b) it’s the same in operation principles with all later variants (telltale sign is integer DCT instead of floating point one in Bink-b). Here are some details on how it differs from later Bink variants.

The main difference is lack of scaled blocks, hence block types got reshuffled as well:

• type 1 — pattern run
• type 2 — intra DCT block
• type 3 — inter DCT block
• type 4 — inter DCT block (lossless)
• type 5 — single colour fill block
• type 6 — pattern (2-color) block
• type 7 — motion block (looks like it uses overlapped copy like Bink-b though)
• type 8 — raw block

In other words it’s not that special and demonstrates the evolution of Bink versions.

This codec is a collaborative effort — both me and some bogan from Melbo have been slacking on it for quite a long time.

Strewth, it’s almost the same as its successor, the real Bink known everywhere (Bink-b or 0.5 is not even mentioned in official Bink history). The main differences are lack of Huffman coding (all bundle elements are just stored in predefined number of bits), different scan-run coding (instead of storing it in a separate bundle, run values are stored in bitstream with minimum number of bits needed to code the biggest run from that point, i.e. 6 bits at the beginning but less than five bits for runs in the second half of block) and DCT uses floating-point coefficients (though the same ones for all practical purposes).

The only thing that differs significantly is motion compensation. Bink version b seems to use the same frame for all coming decoding and actually motion compensation in the first frame copies already decoded block from the same frame. After discovering that fact I was able to obtain perfect first frame in many cases and sometimes the rest of video was also decoded fine except for few glitches. The only puzzling thing is that vertical motion vector offset in the first frame seems to have slightly different value, so <-8,15> actually means “copy data from the previous left block” and <0,7> means “copy data from the top block” while such translation is not needed for all next frames.

Since all known samples are from the Heroes of Might and Magic III game and they are duplicated with Smacker samples, there’s not much interest on finishing that decoder and integrating it into current FFmpeg Bink decoder (I’ve done it as a dirty hack). So no prawn cracker for you, mate.

Update: proof-of-a-concept hack (produces minor artifacts too) can be downloaded here.

I don’t think you’ll ever encounter Bink video version ‘b’, known samples were dug out from game data of certain New World Computing games. And looks like they are not supported by official software anymore. But why that can stop us from looking at it?

This information is based on findings by certain FFmpeag deaveloper and me looking at disassembly for similarities with newer Bink version.

The main difference is that this version does not employ Huffman coding at all. All bundle data is stored in raw form, 4-11 bits per entry depending on bundle type. Number of elements in bundle is stored as 13-bit number, newer version uses different number of bits depending on plane width.

Also this Bink used floating-point version of DCT (but constants are the same as in integer version employed by latter codec version).

Coding methods (block types) are in totally different order as well. And 8×8 -> 16×16 scaling block type was not devised in that time either. Bundles contain slightly different data as well — for example, quantisers and number of residue masks are there but pattern run block uses diminishing number of bits to code runs instead of reading it from bundle (indeed, if you have to decode 48 more block elements you need to read 6 bits but when there are mere 7 block elements left 3 bits are enough).

I’ve not looked too close at DCT coefficient/residue coding methods but they seem to resemble those used in newer version of codec.

Short conclusion: while Bink video codec steadily improved, most concepts are remained the same (but there’s a bigger leap between versions ‘b’ and ‘f’ than between ‘f’ and ‘i’, the latter are almost backwards compatible). And maybe we’ll see decoder for it in FFmpeg for completeness sake.

And now for something completely the same.

Let’s talk about most interesting block type in Bink. I don’t know official name for it but I call it pattern-run block because of the way it’s coded. Idea is simple: there are runs of single colour and blocks of different colours like in your ordinary RLE; what can be interesting in that? But there is one thing — block is filled with runs/copies not in usual scan orders but following one of 16 predefined patterns – columns, spirals, Hilbert curve (Zelda pattern for some of us), whatever.

Here’s an example:

(and SVG version)

I think it’s obvious how this helps block compression. The only bad thing about it is the fact it did not appear in Smacker (mostly because Smacker uses 4×4 blocks).

This concludes my series of posts about Bink.
“Works for me” patch against FFmpeg r19754 is located here.

I’ve mentioned before that Bink differs greatly from other codecs. Now I want to walk over general structure of it and mark all peculiarities I’ve seen so far.

1. Huffman coding. I think I’ve mentioned it enough times.
2. Data coding. The fact that different values (block types, colours, run values) are coded in so-called bundles (i.e. groups) for at least one row of blocks at once. So when starting decoding new row bundles are checked whether there’s enough data and more is decoded if needed.
3. 16×16 and 8×8 block mix. Sometimes encoder inserts 16×16 block into usual array of 8×8 blocks. Looks like those blocks can happen only on even positions which eases skipping decoded part of it. 16×16 block contents are actually 8×8 block contents scaled twice.
4. Coding modes. There are 10 block types; three of them belongs to vector quantisation techniques (I’ll write another post about special run-length pattern block), two block types use DCT (more below) and another block type uses special coding for residue without any additional transform.
5. DCT coefficients coding. I’ve written a bit about it already. Have I mentioned they also use non-standard scan order (designed for pairs of coefficients)?
6. Coefficients quantising. There are 16 possible quantisers – 1, 1 1/3, 1 2/3, 2, 2 2/3, 3 1/2, 4, 5, 6, 8, 12, 17, 22, 28, 34 and 44.

I suspect that some of the things are legacy of Smacker and really clean design would go in slightly other direction – it’s not pure vector quantisation as it was but it’s not pure DCT-based codec either.

As for the progress: I have more or less working decoder in my own build of FFmpeg. When somebody kicks certain devs to push Bink demuxer and audio decoder into SVN codebase, I’ll give my decoder with that. Until then just wait.

First of all, I’d like to note that those names are taken from Bink code. In reality ‘lossy’ block is used as is and ‘lossless’ block is DCT coefficients.

And now, the differences:

• in ‘lossless’ mode coefficients are decoded until mask becomes zero, there’s no explicit number of coefficients
• coefficient bits are stored explicitly, not as several masks: coef[x] = mask | get_bits(log2(mask));
• starting list somewhat differs

For those who for some unknown reason are interested in RE progress, I can say that my implementation is still far away from perfect. It crashes on 640×480 BIKi files and for those two files it plays (BIKf and BIKi) it gives barely recognisable image — I blame DCT and dequantisation (I haven’t looked at them yet).

RTMP client seems to work fine, RTMP support in FFserver is not that close, so I work on REing some codec which seems to be rather widespread in games.

OK, now to technical details. ‘Lossless’ coefficient coding is similar but a bit more complicated.

For each 8×8 block there is 7-bit number specifying number of masks to read (mask = part of the coefficient), slightly resembling progressive JPEG coding; coefficient value may be composed from several masks, high bits are decoded first. Decoding continues until all masks are read.

Coding method is not that comprehensible though: there is list of start coefficient and modes, so decoding iterates over this list and performs some action depending on mode. Have I mentioned that aforementioned list may change during operation?

And here’s decoding algorithm (if I got it right):


mask = 1 < < get_bits(3) iterate over already decoded coefficients, if read bit = 1 then add mask to the coefficient iterate over list of modes until end is reached, if (coef,mode)==(0,0) or read bit = 0 then skip current entry:   mode = 0:    set current entry to (cur_coef+4; mode = 1)    for(i=0;i<4;i++, cur_coef++){     if(get_bit()) prepend list with (cur_coef, mode = 3)     else coeffs[cur_coef] = get_bit() ? -mask : mask;    }   mode = 1:    set current entry to (cur_coef; mode = 2)    append (cur_coef+4; mode = 2), (cur_coef+8; mode = 2), (cur_coef+12; mode = 2) to the list   mode = 2:    set current entry to (0; mode = 0)    for(i=0;i<4;i++, cur_coef++){     if(get_bit()) prepend list with (cur_coef, mode = 3)     else coeffs[cur_coef] = get_bit() ? -mask : mask;    }   mode = 3:    coeffs[cur_coef] = get_bit() ? -mask : mask;