Archive for the ‘Game Video’ Category

Bink2: Inter Block Residue

Saturday, January 18th, 2014

Inter block residue decoding is not different from intra block decoding except that DCs are expected to be in -1023…1023 range instead of 0…2047 and quantisation matrix for luma is different.

Posts about reconstruction process might follow.

Bink2: Intra Block — Chroma

Saturday, January 18th, 2014

Chroma block coding is similar to luma but with some changes since there are only 4 blocks coded here.

Thus, CBP is coded as two nibbles (real CBP and VLC switch) and it does not try to reuse nibbles from last CBP in code.

There are only 4 DCs here but they are decoded the same way.

AC block decoding is completely the same.

Bink2: Intra Block — Luma

Saturday, January 18th, 2014

Intra luma block in Bink2 contains the following elements: CBP, quantiser, DCs and ACs.

CBP is coded as 32-bit bitmask depending on the previous CBP value. Internally top half is coded depending on bottom one and the whole bitmask is coded in nibbles starting from LSB.
Lower half decoding depends on the control bits:

  • 11 — simply return last CBP
  • 10 — use low 16 bit from last CBP
  • 0 — decode 4 low nibbles of CBP. Initial nibble value is set to (last_cbp >> 4) & 0xF, if the next bit is 1 then don’t change it, otherwise read new value from the bitstream (4 bits of course).

Now we can use these low 16 bits of CBP to restore high 16 bits. This is also done by nibbles and decoding depends on them (why nibbles? Because blocks are coded in groups of four).

pat4 = (last_cbp >> 20) & 0xF;
ref = cbp;
for (i = 0; i < 4; i++) {   if (!ones_count[ref & 0xF]) {    pat4 = 0;   } else if (ones_count[ref & 0xF] || getbit()) {    pat4 = 0;    for (bit = 1; bit < 0x10; bit <<= 1)     if ((ref & bit) && getbit())      pat4 |= bit;   } else {    pat4 &= ref & 0xF;   }   cbp |= pat4 << 16 + i * 4;   ref >>= 4

Essentially it decides what set bits to copy from the first part. And top 16 bits are not really a coded block pattern, it just tells decoder to use an alternative set of VLC codes in AC decoding.

Quantiser is coded with static VLC (plus sign bit for nonzero value) as a difference to the previous quantiser.

Quantisation table for DC: 4 4 4 4 4 6 7 8 10 12 16 24 32 48 64 128

16 DCs (coded with the same scheme as motion vector described in the previous post)

16 blocks of AC coefficients coded in groups of four. Each AC block is coded as (value, skip) pair where value is coded with static VLC that gives small levels (0-3) or number of bits for raw value to read. Skips have one peculiarity too: value coded with static VLC defines either skip (for values 0-10), escape value (when you got you need to read 6 bits with real skip value), end of block value and that the following 8 AC coefficients won’t have skip values coded after them.

Scan order is strange, here are first 8 indices from it: 0, 2, 1, 8, 9, 17, 10, 16, 24, 3, 18, 25, 32, 11, 33

Bink2: Frame structure

Thursday, January 16th, 2014

Frames consist of ordinary macroblocks in 420 format with optional alpha. Bitstream is packed into 32-bit little-endian words.

Every macroblock is prefixed by 2-bit code determining its type.

Type 0 (intra block). Decode intra block.

Type 1 (skip block). Simply skip block.

Type 2 (motion block). Decode motion vectors and copy block with ½-pel precision for luma and alpha and ¼-pel precision for chroma. There is no residue coding.

Type 3 (inter block). Decode motion vectors and copy block with ½-pel precision for luma and alpha and ¼-pel precision for chroma. Now decode and add residue.

Motion vector differences are coded this way: motion vector element size in bits (3 bits, if read value is 7 then read additional 2 bits, so total is up to 7+3=10 bits per MV element); four motion vector elements; sign bits for non-zero motion vector elements.

Side note: looks like this codec employs this scheme (bit size in 3+2 scheme, fixed-size values, signs for nonzero values) for other elements too, e.g. DCs.

Luma hpel filter looks something like (A - 4*B + 19*C - 4*D + E + 1) >> 5
Chroma qpel: ¼ — (6*A + 2*B + 1) >> 3, ½ — (A + B + 1) >> 1

Next: intra macroblock decoding — luma.

Bink2: RE Notes

Thursday, January 16th, 2014

Since I obviously have nothing better to do with my time I looked at Bink2 again. In the (hopefully) following blog posts I’ll try to document bitstream format; general codec design was presented much earlier.

At least container format remains the same (except that it uses e.g. KB2f or KB2g instead of BIKi).

In ten years every codec becomes Op^H^HJPEG

Saturday, May 11th, 2013

So, RAD has announced Bink 2. While there are no known samples or encoder, decoder is present in RAD game tools already. For some random reason (what I have to do with Bink anyway?) I decided to look at it.

Format is probably the same except that preferred extension is .bk2 and it starts with 'KB2f' instead of 'BIKf' or 'BIKi'.

The main features they advertise are speed and dual-core decoding support. Most parts of the code are SIMDified indeed and as for dual-core decoding support it seems to be fulfilled with breaking frame into top and bottom half (not that I’ve looked at it closely but strings in the player suggest that).

Now about the format itself. Bink2 operates in YUV 4:2:0 format with optional alpha and employs 8×8 DCT with 16×16 macroblocks. There are not many interesting details in the coding itself: DCs are coded separately before ACs, three quantisation matrices — two for luma/alpha (for intra and inter blocks) and one for chroma, static codes are used for coding them (compare that to the way it was done in Bink Classic), motion compensation is halfpel for luma and quarterpel for chroma now with bicubic interpolation. There are four modes for coding block: intra block, skip block, motion-only block and motion compensation with residue coded.

There seems to be some postprocessing they rightfully call “Blur” but I’m not that sure about it.

What can I say about the codec overall? It’s boring. While Bink 1 is not that fast it was much more fun to RE: coding values in bundles ­— I’ve rarely seen that (Duck TrueMotion 2 comes to mind and that’s all), various coding techniques — vector quantisation and DCT (as I’ve mentioned above, coding DCT coefficients was rather unique too) and some other tricks (unusual scans, specially coded block difference, double-scaling blocks, etc. etc.).

Overall, Bink2 will probably be what it’s promised to be (fast, portable codec for games) but it won’t have the real spirit of Smacker and Bink design. Or maybe it’s just me getting older.

P.S. I wonder if they start providing logo in Bink2 file embedded in player like they do with Smacker and Bink players.

P.P.S. This post title is inspired by a certain German saying about cars in case it wasn’t obvious.

Some notes on video in LucasArts games

Saturday, April 2nd, 2011

Recently I’ve been trying to add video support from LucasArts games to Libav and I must admit it’s not that easy. While there are only two container formats (one for paletted videos and one for 16-bit ones) there are too many compression methods used for palettised videos.

Here are some known codec numbers:

  • 1­–3 (the same codec actually)
  • 5
  • 21
  • 37
  • 47
  • 48

Codecs 1-3, 37 and 47 are common in adventure games, so I have more interest in supporting them (and ScummVM has decoders for them). But starting with at least codec 37 they added subcodecs, so there are several compression methods may be employed with each of them (ranging from raw data to RLE to vector quantisation). That means a lot of reverse-engineering work to support it so don’t expect full-featured decoder soon. And there’s also audio.

Nonexistent beast: Bink-d

Saturday, March 12th, 2011

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.

Almost full Bink support

Sunday, February 13th, 2011

Thank to the efforts of Peter Ross we finally got Bink version b video support. Now I can stop nagging him about it and he may work on something else. I think it’s almost a year since we had game decoders added to FFmpeg, we should do that more often.

P.S. Why I say almost full? There is still some issue with audio in Bink-b, after Peter resolves it FFmpeg will have complete Bink decoding support.

Update: thanks to Peter’s effort we have full Bink-b support now, including both video and audio.

Maybe the last word about Bink version b

Saturday, November 20th, 2010

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.