Description Of The Origin Xan Video Codec by Mike Melanson (mike at multimedia.cx) and Mario Brito (mbrito at dei.uc.pt) v1.0: December 10, 2003 ======================================================================= NOTE: The information in this document is now maintained in Wiki format at: http://wiki.multimedia.cx/index.php?title=Wing_Commander_III_MVE_Video_Codec ======================================================================= Copyright (c) 2003 Mike Melanson and Mario Brito Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License". Contents -------- * Introduction * Xan Core * Wing Commander III Video Format * Wing Commander IV/Xxan Video Format * References * Acknowledgements * Changelog * GNU Free Documentation License Introduction ------------ 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. In 1995, Origin published the followup, "Wing Commander IV: The Price of Freedom". Following the same formula as the previous game, WC4 makes liberal use of FMV. This time, the FMV is transported in Microsoft AVI files. The video codec, similar to the one used in WC3, was identified by the four-character code (fourcc) 'Xxan'. Several other Origin games are known to use this format as well. This document takes the liberty of grouping both the WC3 and WC4 video codecs together as the Xan codec. This document describes the common properties of the Xan codec as well as the on-disk data formats used for storing Xan-encoded data. Xan Core -------- The Xan 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 usually block-based. Both Xan variants rely on a particular unpacking function that operates like this: xan_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. Wing Commander III Video Format ------------------------------- Wing Commander III Xan video data is transported in WC3 MVE files. See the references for more information on the file format. The 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. And 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 xan_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. Wing Commander IV/Xxan Video Format ----------------------------------- The WC4 variant of the Xan format is similar to the WC3 variant. It uses the same xan_unpack logic, and also contains Huffman-coded compression codes. The codec contains a certain amount of postprocessing so that multiple output formats can be natively supported. All of the technical details of the WC4 Xan format have not been fully reverse engineered yet. References ---------- Wing Commander III: Heart of the Tiger, by Origin xanlib.dll audio/video decoder module, used for decoding WC4 Xan data Description of the Wing Commander III MVE Movie File Format http://www.multimedia.cx/wc3movie.txt Acknowledgements ---------------- Thanks to Michael Niedermayer (michaelni at gmx dot at) for peer review, corrections, and recommendations for improvement. Changelog --------- v1.0: December 10, 2003 - initial release GNU Free Documentation License ------------------------------ see http://www.gnu.org/licenses/fdl.html