Midivid: Difference between revisions

From MultimediaWiki
Jump to navigation Jump to search
(document MidiVid)
(→‎MidiVid Lossless: initial description)
Line 90: Line 90:


== MidiVid Lossless ==
== MidiVid Lossless ==
This codec combines several compression methods and each frame can have a different one.
Known types (determined by 32-bit little-endian word at the start):
* <code>BWTZ</code> - data is compressed with method borrowed from some BTW compressor;
* <code>BWTF</code> - the same but data is split into several chunks, each preceded by 32-bit chunk size;
* <code>LZSS</code> - data is compressed with the same LZSS scheme the original MidiVid codec uses.
Also the top bit may be set to indicate that next 32-bit word is frame size (otherwise frame data follows immediately).
=== BWT* Compression ===
Data header:
* 32-bit decompressed size
* 32-bit checksum
* 16-bit compression flags
Compression flags meaning, LSB first:
* bit 0    - RLE present
* bits 1-3 -
* bits 4-6 -
* bit 7    - n-grams present
* bit 8    - first value is stored as delta?
* bit 15  - compressed data
Decoding order:
* decode small values
* decode (and add) large values
* undo MTF
* undo distance coding(?)
* if bit 8 is set undo delta
* if bit 7 is set expand n-grams
* if bits 1-3 are set undo some preprocessing
* if bits 4-6 are set undo table prediction
* if bit 0 is set undo RLE
Data is split into two partitions: small values (0, 1 and 2 only) and large values (2-255).
==== Small Values Coding ====
==== Large Values Coding ====
==== Move-To-Front Preprocessing ====
==== Distance Coding (?) ====
==== N-grams ====
==== Fixed Preprocessing ====
==== Table Prediction ====
==== RLE ====
==== Checksum Calculation ====
  crc = 0xFFFFFFFF;
  for (i = 0; i < size; i++)
    crc = (crc >> 8) ^ (((crc & 0xFF) ^ *src++) << 24);


== MidiVid 3 ==
== MidiVid 3 ==

Revision as of 04:03, 1 October 2019

Midivid is a video codec developed by Jason Dorie of BlackBox Games (later acquired by Electronic Arts). It reportedly has a lot in common with MPEG-2, while claiming better compression ratios than MPEG-2.

MidiVid

First version of MidiVid codec uses LZSS compression, vector quantisation and simple hold-and-modify approach.

Frame header (all data is little-endian):

  • 32-bit frame size (can be not set)
  • 32-bit always zero?
  • 32-bit uncompressed flag (1 means the rest of frame is compressed with LZSS)

Frame data:

  • 16-bit number of vectors
  • 16-bit intra frame flag (i.e. no update mask present)
  • (inter only) 32-bit number of blocks to update
  • (inter only) update mask - one bit per each 4x4 block
  • vector data (each vector is 2x2 YUV block without any subsampling, so 12 bytes per each vector)
  • (for frames with more than 256 vector) top index bits
  • index bits (one byte per each 2x2 block)

Decoding process:

 num_vecs = get16le(src); src += 2;
 is_intra = get16le(src); src += 2;
 if (is_intra) {
   num_blocks = (w / 2) * (h / 2);
 } else {
   num_blocks = get32le(src); src += 2;
   update_mask = src;
   src += (w >> 5) * (h >> 2);
 }
 vec_data = src;
 src += num_vecs * 12;
 if (num_vecs <= 256)
   indices = src;
 else {
   idx9data = src;
   indices = idx9data + (num_blocks + 7) / 8;
 }
 
 idx9bits = 0;
 idx9val = 0;
 for (y = 0; y < h; y += 2) {
   for (x = 0; x < w; x += 2) {
     if (!is_intra && update mask bit set for x/4,y/4 block)
       continue;
     if (num_vecs <= 256) {
       idx = *indices++;
     } else {
       if (idx9bits == 0) {
         idx9val = *idx9data++;
         idx9bits = 8;
       }
       idx9bits--;
       idx = *indices++ | (((idx9val >> (7 - idx9bits)) & 1) << 8);
     }
     output vec[idx] as 2x2 block;
   }
 }

LZSS Algorithm

It's the straightforward implementation. First you have 16-bit flags and then literals or matches:

 for (;;) {
   op = src[0] | (src[1] << 8);
   src += 2;
   for (i = 0; i < 16; i++) {
     if no data left { return; }
     if (op & 1) {
       offset = ((src[0] & 0xF0) << 4) | src[1];
       length = (src[0] & 0xF) + 3;
       src += 2;
       for (j = 0; j < length; j++)
         dst[j] = dst[j - offset];
       dst += length;
     } else {
       *dst++ = *src++;
     }
     op >>= 1;
   }
 }

MidiVid Lossless

This codec combines several compression methods and each frame can have a different one. Known types (determined by 32-bit little-endian word at the start):

  • BWTZ - data is compressed with method borrowed from some BTW compressor;
  • BWTF - the same but data is split into several chunks, each preceded by 32-bit chunk size;
  • LZSS - data is compressed with the same LZSS scheme the original MidiVid codec uses.

Also the top bit may be set to indicate that next 32-bit word is frame size (otherwise frame data follows immediately).

BWT* Compression

Data header:

  • 32-bit decompressed size
  • 32-bit checksum
  • 16-bit compression flags

Compression flags meaning, LSB first:

  • bit 0 - RLE present
  • bits 1-3 -
  • bits 4-6 -
  • bit 7 - n-grams present
  • bit 8 - first value is stored as delta?
  • bit 15 - compressed data

Decoding order:

  • decode small values
  • decode (and add) large values
  • undo MTF
  • undo distance coding(?)
  • if bit 8 is set undo delta
  • if bit 7 is set expand n-grams
  • if bits 1-3 are set undo some preprocessing
  • if bits 4-6 are set undo table prediction
  • if bit 0 is set undo RLE

Data is split into two partitions: small values (0, 1 and 2 only) and large values (2-255).

Small Values Coding

Large Values Coding

Move-To-Front Preprocessing

Distance Coding (?)

N-grams

Fixed Preprocessing

Table Prediction

RLE

Checksum Calculation

 crc = 0xFFFFFFFF;
 for (i = 0; i < size; i++)
   crc = (crc >> 8) ^ (((crc & 0xFF) ^ *src++) << 24);

MidiVid 3

Games Using Midivid