Westwood XOR Delta
| Format type | Compression algorithm |
|---|---|
| Type | Stream |
| I/O unit size | 1-bit |
| Games |
The Westwood XOR Delta compression is a format used in Westwood Studios's WSA animation file format, and in the C&C1/RA1 type of the Westwood SHP Format. It is commonly known as "Format 40" because it is indicated with byte value 0x40 in the frame headers of Command & Conquer 1 SHP files, the file type from which the format was originally reverse-engineered and documented.
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.
In Westwood RLE, a command with an unusable count of 0 is used as a different command that reads more bytes. This concept is expanded further in this format, to a total of six different commands. This principle is comparable to how expanding opcodes work in CPU instructions.
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.
Note: in the following explanations, a dot (.) refers to a single bit, and a double underscore (__) means a whole byte.
Command 1: Short Skip
This command is 1 byte long. It can be identified by its highest bit being 1. The Count is 7 bits long.
byte
+---+---+---+---+---+---+---+---+
| 1 | . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+
\_________________________/
|
Count
Skip Count bytes in Dest (move the pointer forward).
Command 2: Long Skip
This command is 3 bytes long. It can be identified by starting with a Short Skip command where the value is 0, with the highest bit in the following byte being 0. The Count is 15 bits long.
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+ +----+
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 0 | . | . | . | . | . | . | . | | __ |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+ +----+
\________________________________/
|
Count
Skip Count bytes.
Command 3: Long XOR
This command is 3 bytes long. It can be identified by starting with a Short skip command where the value is 0, with the highest bit in the following byte being 1, and the second-highest bit being 0. The Count is 14 bits long.
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+ +----+
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | . | . | . | . | . | . | | __ |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+ +----+
\____________________________/
|
Count
Xor the 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. This starts identically to the Long XOR, except that the second-highest bit in the second byte is 1. The Count is 14 bits long.
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+ +----+ +----+
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | . | . | . | . | . | . | | __ | | __ |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+ +----+ +----+
\____________________________/ Value
|
Count
Xor the next Count bytes in Dest with Value.
Command 5: Short XOR
This command is 1 byte long. It can be identified by its highest bit being 0. The Count is 7 bits long.
+---+---+---+---+---+---+---+---+
| 0 | . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+
\_________________________/
|
Count
Xor the next Count bytes from Source with Dest.
Command 6: Long XOR With Value
This command is 3 bytes long. It can be identified by starting with a Short XOR command where the value is 0. The Count is 8 bits long.
+---+---+---+---+---+---+---+---+ +----+ +----+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | __ | | __ |
+---+---+---+---+---+---+---+---+ +----+ +----+
Count Value
Xor the next Count bytes with Value.
All images end with a 80h 00h 00h command, which is a Long Skip with a Count of 0.
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 Chronoshift (formerly 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);
}