Wing Commander III MVE Video Codec

This document is based on the document 'Description Of The Origin Xan Video Codec' by Mike Melanson and Mario Brito found at http://multimedia.cx/xan-format.txt.

• Company: Origin Systems
• Samples: http://samples.mplayerhq.hu/game-formats/wc3-mve/

In 1994, Origin published the third installment of their popular Wing Commander space flight combat simulation games, Wing Commander III: Heart of the Tiger. The game is distributed as 4 CD-ROMs and the underlying story was driven by a lot of full motion video (FMV). The FMV is transported in a custom file format with the extension mve (see the references for more information on this format). The video data in these files is compressed with a custom, unidentified video codec (referred to here as the WC3 codec).

The WC3 codec is a computationally simple video codec that is designed to compress frames of RGB video data at a nominal resolution of 320x165 pixels. The coding method embodies both intraframes (keyframes) and interframes. The algorithm relies on variations of run-length coding and textbook Huffman coding. For interframe compression, the algorithm uses run-based motion compensation. This varies from usual MC methods which are block-based.

Wing Commander IV switched to a different video codec, the Origin Xan Codec.

Unpacking Algorithm

The WC3 video codec relies on the following bytewise unpacking algorithm taking an output buffer and an input buffer:

wc3_unpack(unsigned char *dest, unsigned char *src):
  x = next byte
  if bit 7 of x is 0:
    offset = next byte
    /* x: 0aabbbcc */
    size = bottom 2 bits of x (0..3) (this represents bits 'cc')
    bytecopy size bytes from src to dest
    size = (x & 0x1C) >> 2 + 3 (this represents bits 'bbb')
    bytecopy size bytes from current pos - ((x & 0x60) << 3) + offset + 1
  else if bit 6 of x is 0:
    fetch next byte from stream as byte1
    fetch next byte from stream as byte2
    size = top 2 bits of byte1 (0..3)
    bytecopy size bytes from src to dest
    size = bottom 6 bits of x + 4 (range: 4..67)
    bytecopy size bytes from dest - ((byte1 & 0x3F) << 8) + byte2 + 1
  else if bit 5 of x is 0:
    fetch next byte from stream as byte1
    fetch next byte from stream as byte2
    fetch next byte from stream as byte3
    size = bottom 2 bits of x (0..3)
    bytecopy size bytes from src to dest
    size = byte3 + 5 + ((x & 0xC) << 6);
    bytecopy (dest,
      dest - ((((x & 0x10) >> 4) << 0x10) + 1 + (byte1 << 8) + byte2),
      size);
  else (this means one of the top 3 bits was 1)
    size = (x & 0x1F) * 4 + 4
    if size > 0x70
    break
    copy size bytes from src to dest

This process is repeated in a loop until the break in the else case. On the way out, copy (x & 3) bytes from src to dest.

An important note about the preceding pseudocode description: When the code says that a 'bytecopy' operation is to be performed from buffer a to buffer b, neither a memcpy nor a memmove call will do. The reason is that the bytecopy function is often used to copy between overlapping memory regions. It is not uncommon for dest to equal (src + 1). This has the net effect of turning 'A' into 'AAAAAA...". This function was originally implemented on x86 microprocessors as a 'repz stosb' instruction, which means to store a string by byte repeatedly.

WC3 Codec Format

The Wing Commander III MVE file format packages sequences of video and audio frames together marked by SHOT chunks. Each SHOT chunk has a 768-byte RGB palette specified in the file header. The file demuxer must make the appropriate palette available to the video decoder when a new SHOT begins.

A chunk of WC3 Xan data is formatted as follows:

header  |  segment 1  | segment 2  |  segment 3  | segment 4

The header contains offsets to each of the segments within the chunk:

• Segment 1 contains Huffman-coded image compression codes.
• Segment 2 contains auxiliary size information.
• Segment 3 contains interframe motion vectors.
• Segment 4 contains raw or compressed palettized video data.

The chunk header is always 8 bytes long. The on-disk data format for a chunk header is:

bytes 0-1   absolute offset of segment 1 within chunk (always offset 8)
bytes 2-3   absolute offset of segment 2 within chunk
bytes 4-5   absolute offset of segment 3 within chunk
bytes 6-7   absolute offset of segment 4 within chunk

All of the 16-bit segment offsets are stored in little endian byte order. Note that the offset of segment 3 within an intracoded chunk (keyframe) ought to be 0x0000 as there are no motion vectors for an intraframe.

The first step in decoding a frame involves decoding the Huffman codes in segment 1 in order to decode the compression codes. The segment is laid out as follows:

byte 0       number of values in the Huffman tree (should be 22)
bytes 1..44  Huffman tree table
bytes 45..   Huffman-coded data.

There are 22 values in the Huffman tree since there are 22 possible compression codes (0..21) used to assemble the final output frame. Actually, there is one more value found in the table (22) that signals the end of the Huffman stream. The root of the Huffman tree is at the last byte of the table. Bits in the bytes of the Huffman-coded bits are coded right-to-left.

Assumng the Huffman tree table is stored in huff[44] where the bytes are indexed 0..43, and the root node is at index 43. The decoding algorithm is:

while (value @ current node index != 22)
  if the next bit in the coded stream is 0
    move current node index to (current node index - 22)
  else
    move current node index to (current node index - 1)
  if (value < 22)
    decompression code found, place in output buffer and reset the
    current index to the root node

After decoding the compression codes, check the first byte of segment 2 to see if the raw pixel data needs to be decoded. If the first byte equals 0x02, pass the remainder of the buffer through the wc3_unpack function. Otherwise, use the data from the second byte forward as the pixel data.

The final step builds the frame and uses data from all 4 segments. The algorithm operates as follows (assuming a palettized output buffer that is width * height bytes in size):

flag = 0
index = 0
while index < frame size (width * height):
  x = next compression code in segment 1
  size = 0
  if x is 0, toggle flag and goto next iteration
  if x is 1..8, size = x
  if x is 12..18, size += (x - 10) (net effect: add 2..8)
  if x if 9 or 19, size = next byte in segment 2
  if x is 10 or 20, size = the next BE_16 number in segment 2
  if x is 11 or 21, size = the next BE_24 number in segment 2
  if x < 12:
    toggle flag
    if flag is 1, run is unchanged from previous frame:
      for each count in size, copy pixel from same index in previous
      frame
    else /* flag is 0 */:
      for each count in size, copy the next pixel in segment 4 to the
      output
  else:
    motion byte = next byte in segment 3
    x = top nibble of motion byte
    y = bottom nibble of motion byte
    sign-extend the nibbles in x and y
    copy size bytes from the position referenced by (x, y) in the
    previous frame to the current frame
    reset flag

Note that BE_16 means a 16-bit number in big endian format, and BE_24 means a 24-bit number in big endian format.

Codec Trivia

Origin originally advertised a 486/33 and 2X (300KB/s) CDROM drive as the minimum requirements for playing the video. However, video playback functions perfectly on a 386/40 (about 20% slower than a 486/33) and, with few exceptions, plays just fine on a 1X (150KB/s) CDROM drive. This suggests that Origin was either being conservative with requirements in an effort to ward off anticipated tech support calls caused by flaky clones (a common occurance, unfortunately), or possibly had originally targeted 1X CDROM drives but had to go over the 150KB/s datarate in a few scenes due to low picture quality.

(For the curious, the scenes that don't quite make the 1X datarate cut are scenes where more than 30% of the scene is changing in every frame, such as the spaceflight sequences in the introduction, or scenes that take place in the hanger.)