Westwood XOR Delta

From ModdingWiki
Jump to: navigation, search
Westwood XOR Delta
Format typeCompression algorithm
TypeStream
I/O unit size1-bit
Games

The Westwood XOR Delta compression is a format used in Westwood Studios's WSA animation file format. It is commonly known as "Format 40" because it is usually indicated in file headers with byte value 0x40.

Explanation

The format is designed to be used when there are only minor differences between an image and a following one, and is often used for large animations. Animations in this format, as the name says, contain differences between frames to be xor-ed over each other.

Like Westwood LCW, the format is comparable to Code-type RLE, with byte commands containing manipulation instructions, but while RLE contains repeat and copy commands, the XOR Delta commands, which are applied to a second set of existing data, will either skip over a given number of bytes to leave them unmodified, or will apply an XOR operation on them, either using a single fixed value, or using a following range of bytes from the XOR commands buffer.

For the purpose of this explanation, the XOR data itself is in Source, and the image that the XOR needs to be applied to is already loaded in the Dest buffer. At the beginning of the operation, the pointers for both Source and Dest are set to the start of their respective buffers.

Command 1: Short skip

This command is 1 byte long.

              byte
 +---+---+---+---+---+---+---+---+
 | 1 |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
     \___________________________/
                  |
                Count

Skip Count bytes in Dest (move the pointer forward).

Command 2: Long skip

This command is 3 bytes long.

             byte                           word
 +---+---+---+---+---+---+---+---+  +---+-----+-------+
 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  | 0 | ... |       |
 +---+---+---+---+---+---+---+---+  +---+-----+-------+
                                        \_____________/
                                               |
                                             Count

Skip Count bytes.

Command 3: Long XOR

This command is 3 bytes long.

               byte                              word
 +---+---+---+---+---+---+---+---+  +---+---+-----+-------+
 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  | 1 | 0 | ... |       |
 +---+---+---+---+---+---+---+---+  +---+---+-----+-------+
                                            \_____________/
                                                  |
                                                Count

Xor next Count bytes. That means xor Count bytes from Source with bytes in Dest.

Command 4: XOR with Value

This command is 4 bytes long.

             byte                               word           byte
 +---+---+---+---+---+---+---+---+  +---+---+-----+-------+  +-------+
 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  | 1 | 1 | ... |       |  |       |
 +---+---+---+---+---+---+---+---+  +---+---+-----+-------+  +-------+
                                            \_____________/    Value
                                                  |
                                                Count

Xor next Count bytes in Dest with Value.

Command 5: Short XOR

This command is 1 byte long.

              byte
 +---+---+---+---+---+---+---+---+
 | 0 |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
     \___________________________/
                  |
                Count

Xor next Count bytes from Source with Dest.

Command 6: Long XOR with Value

This command is 3 bytes long.

             byte                     byte       byte
 +---+---+---+---+---+---+---+---+  +-------+  +-------+
 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  |       |  |       |
 +---+---+---+---+---+---+---+---+  +-------+  +-------+
                                      Count      Value

Xor next Count bytes with Value.

All images end with a 80h 00h 00h command.

I think these are all the commands, but there might be some other. If you find anything new, please add them.

Code

Decompression

DP = destination pointer
SP = source pointer
Source is buffer containing the XOR Delta data
Dest is the buffer containing the image over which the second has to be xor-ed

  SP:=0;
  DP:=0;
  repeat
    Com:=Source[SP];
    Inc(SP);
 
    if (Com and $80)<>0 then {if bit 7 set}
    begin
      if Com<>$80 then  {small skip command (1)}
      begin
        Count:=Com and $7F;
        Inc(DP,Count);
      end
      else  {Big commands}
      begin
        Count:=Word(Source[SP]);
        if Count=0 then break;
        Inc(SP,2);
 
        Tc:=(Count and $C000) shr 14;  {Tc=two topmost bits of count}
 
        case Tc of
          0,1 : begin  {Big skip (2)}
                  Inc(DP,Count);
                end;
          2 : begin {big xor (3)}
                Count:=Count and $3FFF;
                for i:=1 to Count do
                begin
                  Dest[DP]:=Dest[DP] xor Source[SP];
                  Inc(DP);
                  Inc(SP);
                end;
              end;
          3 : begin  {big repeated xor (4)}
                Count:=Count and $3FFF;
                b:=Source[SP];
                Inc(SP);
                for i:=1 to Count do
                begin
                  Dest[DP]:=Dest[DP] xor b;
                  Inc(DP);
                end;
              end;
        end;
      end;
    end else  {xor command}
    begin
      Count:=Com;
      if Count=0 then
      begin {repeated xor (6)}
        Count:=Source[SP];
        Inc(SP);
        b:=Source[SP];
        Inc(SP);
        for i:=1 to Count do
        begin
          Dest[DP]:=Dest[DP] xor b;
          Inc(DP);
        end;
      end else  {copy xor (5)}
        for i:=1 to Count do
        begin
          Dest[DP]:=Dest[DP] xor Source[SP];
          Inc(DP);
          Inc(SP);
        end;
    end;
  until false;

Compression

Very few tools in the Command & Conquer modding community actually ever implemented XOR Delta compression. Even more versatile tool suites like XCC Mixer and the older RAMIX and Mix Manager packages never contained writers for the WSA format, the main file type that uses XOR Delta. Likewise, the use of XOR Delta in the C&C1/RA1 SHP format was never implemented.

A reconstruction of the original XOR Delta and LCW compression algorithms was written by OmniBlade of the RedAlert++ team, aided by descriptions of the used principles by Louis Castle himself, and was released as C++ code on the CnCNet forums.

A C# version of the code is available in the source code of Nyerguds's Engie File Converter, which handles a multitude of Westwood Studios formats.

OmniBlade's C++ code: (released under the GNU General Public License)

////////////////////////////////////////////////////////////////////////////////
//  Some utility functions to get worst case sizes for buffer allocation
////////////////////////////////////////////////////////////////////////////////
 
inline int XOR_Worst_Case(int datasize) {
	return datasize + ((datasize / 63) * 3) + 4;
}
 
////////////////////////////////////////////////////////////////////////////////
//  Some defines used by the encoders
////////////////////////////////////////////////////////////////////////////////
#define XOR_SMALL		127
#define XOR_MED			255
#define XOR_LARGE		16383
#define XOR_MAX			32767
 
////////////////////////////////////////////////////////////////////////////////
//  NAME:
//    Generate_XOR_Delta()
//
//  DESCRIPTION:
//    Generates a binary delta between two buffers. Mainly used for image data.
//
//  PARAMETERS:
//    dest   -- Buffer to store the generated delta.
//    source -- Buffer containing data to generate the delta for.
//    base   -- Buffer containing data that is the base for the delta.
//    size   -- Size of the two source buffers (or the smallest).
//
//  RETURN:
//    Size of the generated delta in bytes.
//
//  WARNINGS:
//    Delta can be larger than the source buffers in worse case, allocate 
//    storage accordingly.
//
////////////////////////////////////////////////////////////////////////////////
int Generate_XOR_Delta(void *dest, void *source, void *base, int size)
{
	uint8 *putp = static_cast<uint8*>(dest);	//our delta
	uint8 *getsp = static_cast<uint8*>(source);	//This is the image we go to
	uint8 *getbp = static_cast<uint8*>(base);	//This is image we come from
	uint8 *getsendp = getsp + size;
 
	//Only check getsp to save a redundant check. 
	//Both source and base should be same size and both pointers should be 
	//incremented at the same time.
	while ( getsp < getsendp) {
		uint fillcount = 0;
		uint xorcount = 0;
		uint skipcount = 0;
		uint8 lastxor = *getsp ^ *getbp;
		uint8 *testsp = getsp;
		uint8 *testbp = getbp;
 
		//Only evaluate other options if we don't have a matched pair
		while ( *testsp != *testbp && testsp < getsendp ) {
			if ( (*testsp ^ *testbp) == lastxor ) {
				++fillcount;
				++xorcount;
			} else {
				if ( fillcount > 3 ) {
					break;
				} else {
					lastxor = *testsp ^ *testbp;
					fillcount = 1;
					++xorcount;
				}
			}
			++testsp;
			++testbp;
		}
 
		//fillcount should always be lower than xorcount and should be greater
		//than 3 to warrant using the fill commands.
		fillcount = fillcount > 3 ? fillcount : 0;
 
		//Okay, lets see if we have any xor bytes we need to handle
		xorcount -= fillcount;
		while ( xorcount ) {
			uint16 count = 0;
			//Its cheaper to do the small cmd twice than do the large cmd once 
			//for data that can be handled by two small cmds.
			//cmd 0???????
			if ( xorcount < XOR_MED ) {
				count = xorcount <= XOR_SMALL ? xorcount : XOR_SMALL;
				*putp++ = count;
			//cmd 10000000 10?????? ??????
			} else {
				count = xorcount <= XOR_LARGE ? xorcount : XOR_LARGE;
				*putp++ = 0x80;
				*putp++ = count;
				*putp++ = (count >> 8) | 0x80;
			}
 
			while (count) {
				*putp++ = *getsp++ ^ *getbp++;
				--count;
				--xorcount;
			}
		}
 
		//lets handle the bytes that are best done as xorfill
		while ( fillcount ) {
			uint16 count = 0;
			//cmd 00000000 ????????
			if ( fillcount <= XOR_MED ) {
				count = fillcount;
				*putp++ = 0;
				*putp++ = count;
			//cmd 10000000 11?????? ??????
			} else {
				count = fillcount <= XOR_LARGE ? fillcount : XOR_LARGE;
				*putp++ = 0x80;
				*putp++ = count;
				*putp++ = (count >> 8) | 0xC0;
			}
				*putp++ = *getsp ^ *getbp;
				fillcount -= count;
				getsp += count;
				getbp += count;
		}
 
		//Handle regions that match exactly
		while ( *testsp == *testbp && testsp < getsendp) {
			++skipcount;
			++testsp;
			++testbp;
		}
 
		while ( skipcount ) {
			uint16 count = 0;
			//Again its cheaper to do the small cmd twice than do the large cmd 
			//once for data that can be handled by two small cmds.
			//cmd 1???????
			if ( skipcount < XOR_MED ) {
				count = skipcount <= XOR_SMALL ? skipcount : XOR_SMALL;
				*putp++ = count | 0x80;
			//cmd 10000000 0??????? ????????
			} else {
				count = skipcount <= XOR_MAX ? skipcount : XOR_MAX;
				*putp++ = 0x80;
				*putp++ = count;
				*putp++ = count >> 8;
			}
			skipcount -= count;
			getsp += count;
			getbp += count;
		}	
	}
 
	//final skip command of 0 to signal end of stream.
	*putp++ = 0x80;
	*putp++ = 0;
	*putp++ = 0;
 
	return putp - static_cast<uint8*>(dest);
}