Bink Video
- 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