Bink Video

From MultimediaWiki
Revision as of 04:12, 3 September 2009 by Kostya (talk | contribs)
Jump to navigation Jump to search
  • FourCC: BINK (note that some FourCC lists assert that BINK is a FourCC for general-purpose multimedia containers; however, Bink data is always known to be encapsulated in a custom container format)
  • Company: RAD Game Tools
  • Samples: http://samples.mplayerhq.hu/game-formats/bink/, countless video games

Bink is a video codec that uses Vector Quantization along with DCT and Motion Compensation). This codec is used in a large number of computer and console games. The video is packaged in custom Bink files.

Each plane is coded separately. The Y plane is always coded first in each frame.

Format

Bitstream is read LSB from 32-bit little-endian words.

Frame is coded as three planes.

Each plane starts with Huffman codebooks: two 4-bit ones, one 8-bit (which really consists of seventeen (16 plus one special) 4-bit codebooks) and four 4-bit ones.

Huffman trees

There are 16 predefined Huffman trees, Bink frame only stores tree number and sophisticated coding of leaves values.

  • 4 bits - huffman tree type.

First tree is actually raw nibbles, so no additional data for it. For other trees leaves symbols should be coded.

  • 1 bits - symbols are coded explicitly (by selection)

If that flag is one, read 3 additional bits which determine number of symbols out of order, then read those symbols (4 bits per each symbol), the rest of symbols should go in normal order.

 Example:
 read  {5} [1] (3) <9> <1> <7>
 tree type: 5
 symbols order:  9  1  7  0  2  3  4  5  6  8  A  B  C  D  E  F

In other case symbols are coded by shuffling:

  • 2 bits - shuffle depth

First divide all symbols into pairs and read 1 bit for each pair to decide whether swap this pair or not.

 Example:
 original data:  (0 1)  (2 3)  (4 5)  (6 7) ...
 read bits:         0      1      1      0  ...
 output:         (0 1)  (3 2)  (5 4)  (6 7) ...

if shuffle depth is zero, end operation; otherwise perform merging.

 void merge(uint8_t *dst, uint8_t *src1, uint8_t *src2, int size)
 {
   int size1 = size, size2 = size;
   do{
      if(getbit()){
       *dst++ = *src2++;
       size2--;
     }else{
       *dst++ = *src1++;
       size1--;
     }
   }while(size1 && size2);
   while(size1--)
     *dst++ = *src1++;
   while(size2--)
     *dst++ = *src2++;
 }

If depth is one, divide symbols into pairs and merge neighbouring pairs (i.e. [0 1] and [2 3], [4 5] and [6 7], etc.) If depth is two, divide result into quartets and merge quartet 0 with quartet 1 and quartet 2 with quartet 3. For depth = 3 additionally divide result into two halves and merge them too.

Or, more clearly:

 depth = getbits(2);
 for (i = 0; i <= depth; i++) {
   int size = 1 << i;
   int skip = size * 2;
   for (j = 0; j < 16; j += skip)
     merge(tmp + j, symbols + j, symbols + j + size, size);
   memcpy(symbols, tmp, 16);
 }

Bundle reading

Bink uses basic Huffman trees for decoding 4-bit values to create values of different types from them.

4 bit bundle

The simplest of them all:

 t = getbits(bundle->runsize);
 if(!t)
   return 0; //no data to decode
 if(getbit())
   memset(dst, getbits(4), t);
 else{
   for(i = 0; i < t; i++)
     dst[t] = gethuff(bundle->tree[0]);
 }

4 bit signed bundle

Virtually the same as 4 bit bundle but after each Huffman-coded value is decoded an additional sign bit is read; if that bit is set then decoded value is negative.

4 bit RLE bundle

Another RLE-oriented variation - if decoded value is less than 12, output it, otherwise find corresponding run length and repeat last decoded value that number of times:

 int runvalues[4] = { 4, 8, 12, 32};
 
 t = getbits(bundle->runsize);
 if(!t)
   return 0;
 for(i = 0; i < t; i++){
   v = gethuff(bundle->tree[0]);
   if(v < 0xC)
     *dst++ = v;
   else{
     memset(dst, dst[-1], runvalues[v - 12]);
     dst += runvalues[v - 12];
     i += runvalues[v - 12] - 1;
   }
 }

4 bit pair bundle

This decodes several 8-bit values composed from two nibbles:

 t = getbits(bundle->runsize);
 if(!t)
   return 0;
 for(i = 0; i < t; i++){
   n0 = gethuff(bundle->tree[0]);
   n1 = gethuff(bundle->tree[0]);
   dst[i] = n0 | (n1 << 4);
 }

8 bit bundle

There are two slightly different ways to decode this bundle depending on Bink version. This decoding method is context-dependent, i.e. high nibble is decoded with the tree selected on last decoded high nibble. The only difference between decoding methods is that value was signed in old decode.

Old version:

 t = getbits(bundle->runsize);
 if(!t)
   return 0;
 if(getbit()){
   for(i = 0; i < t; i++){
     n0 = gethuff(bundle->tree[1 + bundle->lastval]);
     n1 = gethuff(bundle->tree[0]);
     bundle->lastval = n0;
     v = (n0 << 4) | n1;
     if (v & 0x80)
       v = -(v & 0x7F);
     dst[i] = v;
   }
 }else{
   v = ??? //decoded here or from previous run
   memset(dst, v, t);
 }

New version:

 t = getbits(bundle->runsize);
 if(!t)
   return 0;
 if(getbit()){
   for(i = 0; i < t; i++){
     n0 = gethuff(bundle->tree[1 + bundle->lastval]);
     n1 = gethuff(bundle->tree[0]);
     bundle->lastval = n0;
     v = (n0 << 4) | n1;
     dst[i] = v;
   }
 }else{
   //unsure whether dst[-1] is decoded here or not
   memset(dst, dst[-1], t);
 }

16 bit delta

This one does not employ Huffman coding and uses delta coding instead.

 t = getbits(bundle->runsize);
 if(!t)
   return 0;
 start = getbits(bundle->startsize);
 if(bundle->is_signed)
  start = (start & 1) ? -(start >> 1) : (start >> 1);
 *dst++ = start;
 for(i = 0; i < t; i++){
   t2 = getbits(4);
   if(t2){
     for(j = 0; j < min(t, 8); j++){
       v = getbits(t2);
       if(v && getbit())
         v = -v;
       start += v;
       *dst++ = start;
     }
   }else{
     for(;i < t; i++)
       *dst++ = t;
   }
 }

Coefficients reading

'lossy' block (residue)

TODO

'lossless' block (DCT coeffs)

TODO

Decoding

Frame

for each block a lot of values should be decoded (value may be taken from cache if previous decode returned run of values):

  • block type - 4 bit RLE bundle
  • sub block type - 4 bit RLE bundle
  • colors data (for filling blocks) - 8 bit bundle
  • pattern - 4 bit pair bundle
  • x motion offset - 4 bit signed bundle
  • y motion offset - 4 bit signed bundle
  • DC for intrablock - 16 bit delta
  • DC for interblock - 16 bit delta
  • pattern colors run length - 4 bit bundle

Block types

0 - skip block

Copy 8x8 block from previous frame to current frame

1 - scaled 16x16 block

This is 16x16 block which has its own subtype, which corresponds to other block types (range 3-9). Blocks should be decoded in the same way and then scaled twice.

2 - motion block

Copy 8x8 block from previous frame with some offset (x and y values decoded at the beginning of the block)

3 - run fill

Fill 8x8 block with pattern 4 bits - pattern index

first 63 or 64 coefficients in block are decoded in this way:

 run = next value from Pattern Colors Run Length;
 if(getbit()){
   memset(block, Colors[0], run);
   Colors++;
 }else{
   memcpy(block, Colors, run);
   Colors += run;
 }
 block += run;

Last block element (if decoded 63 coefficients) is taken from Colors values

4 - motion+residue

motion compensation + so-called "lossy" coding (see [1]), 7 bits before coded block contain number of masks to decode.

5 - intra DCT

intrablock with DCT coefficients and 4 bits quantizer

6 - fill

Fill 8x8 block with one value from Colors

7 - inter DCT

interblock with motion vector (x and y values decoded at the beginning), DCT coefficients and 4 bit quantizer

8 - pattern fill

Fill block with two colours taken from Colors values using 8 values from Patterns

9 - raw data

Fill 8x8 block with 64 values from Colors