Westwood LCW

From ModdingWiki
Jump to: navigation, search

Westwood's LCW compression, commonly known as "Format 80", because it is indicated in file headers with value 0x80, was Westwood's response to Unisys' enforcement of their patent on the LZW algorithm. The internally used name, LCW, stands for Lempel-Castle-Welch, with "Castle" referring to Louis Castle, who wrote the adapted algorithm. However, while its compression algorithm is indeed based on LZW principles, its final written data is a lot more similar to Code-based RLE compression, just with a much-extended set of commands.

Explanation

There are several different commands, with different sizes, from 1 to 5 bytes. The positions mentioned below always refer to the destination buffer (i.e. the uncompressed image). The relative positions are relative to the current position in the destination buffer, which is one byte beyond the last written byte.

Command 1: Short copy

This command is 1 byte long.

 +---+---+---+---+---+---+---+---+
 | 1 | 0 |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+
         \_______________________/
                    |
                  Count

This one means : copy next Count bytes as is from Source to Dest.

A Count value of 0, so a byte 80h, indicates the end of the compressed data is reached.


Command 2: Existing block relative copy

This command is 2 bytes long.

 +---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+
 | 0 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 +---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+
     \___________/\__________________________________________________/
           |                             |
        Count-3                  Relative Position

This means copy Count bytes from Dest at Current Position - Relative Position to Current Position. Note that you have to add 3 to the number you find in the bits 4-6 of the first byte to obtain the Count. If the Relative Position is 1, that means repeat Count times the previous byte.

Command 3: Existing block absolute copy

This command is 3 bytes long.

 +---+---+---+---+---+---+---+---+   +---------------+---------------+
 | 1 | 1 |   |   |   |   |   |   |   |               |               |
 +---+---+---+---+---+---+---+---+   +---------------+---------------+
         \_______________________/                  Pos
                    |
                Count-3

Copy Count bytes from Pos, where Pos is absolute from the start of the destination buffer. (Pos is a word, meaning the images can't be larger than 64K)

Command 4: Repeat value

This command is 4 bytes long.

 +---+---+---+---+---+---+---+---+   +-------+-------+  +-------+
 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |   |       |       |  |       |
 +---+---+---+---+---+---+---+---+   +-------+-------+  +-------+
                                           Count          Value

Write Value Count times. (Count is a word, Value is a byte)


Command 5: Long copy

This command is 5 bytes long.

 +---+---+---+---+---+---+---+---+   +-------+-------+  +-------+-------+
 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |   |       |       |  |       |       |
 +---+---+---+---+---+---+---+---+   +-------+-------+  +-------+-------+
                                           Count               Pos

Copy Count bytes from Dest starting at Pos. Pos is absolute from the start of the Dest buffer. Both Count and Pos are words.


Code

Decompression

This is the decompression code written by Vladan Bato when he figured out the format in his research into the first Command & Conquer game:

  • DP = destination pointer
  • SP = source pointer
  • Source and Dest are the two buffers
 
  SP:=0;
  DP:=0;
  repeat
    Com:=Source[SP];
    inc(SP);
    b7:=Com shr 7;  {b7 is bit 7 of Com}
    case b7 of
      0 : begin  {copy command (2)}
            {Count is bits 4-6 + 3}
            Count:=(Com and $7F) shr 4 + 3;
            {Position is bits 0-3, with bits 0-7 of next byte}
            Posit:=(Com and $0F) shl 8+Source[SP];
            Inc(SP);
            {Starting pos=Cur pos. - calculated value}
            Posit:=DP-Posit;
            for i:=Posit to Posit+Count-1 do
            begin
              Dest[DP]:=Dest[i];
              Inc(DP);
            end;
          end;
      1 : begin
            {Check bit 6 of Com}
            b6:=(Com and $40) shr 6;
            case b6 of
              0 : begin  {Copy as is command (1)}
                    Count:=Com and $3F;  {mask 2 topmost bits}
                    if Count=0 then break; {EOF marker}
                    for i:=1 to Count do
                    begin
                      Dest[DP]:=Source[SP];
                      Inc(DP);
                      Inc(SP);
                    end;
                  end;
              1 : begin  {large copy, very large copy and fill commands}
                    {Count = (bits 0-5 of Com) +3}
                    {if Com=FEh then fill, if Com=FFh then very large copy}
                    Count:=Com and $3F;
                    if Count<$3E then {large copy (3)}
                    begin
                      Inc(Count,3);
                      {Next word = pos. from start of image}
                      Posit:=Word(Source[SP]);
                      Inc(SP,2);
                      for i:=Posit to Posit+Count-1 do
                      begin
                        Dest[DP]:=Dest[i];
                        Inc(DP);
                      end;
                    end
                    else if Count=$3F then   {very large copy (5)}
                    begin
                      {next 2 words are Count and Pos}
                      Count:=Word(Source[SP]);
                      Posit:=Word(Source[SP+2]);
                      Inc(SP,4);
                      for i:=Posit to Posit+Count-1 do
                      begin
                        Dest[DP]:=Dest[i];
                        Inc(DP);
                      end;
                    end else
                    begin   {Count=$3E, fill (4)}
                      {Next word is count, the byte after is color}
                      Count:=Word(Source[SP]);
                      Inc(SP,2);
                      b:=Source[SP];
                      Inc(SP);
                      for i:=0 to Count-1 do
                      begin
                        Dest[DP]:=b;
                        inc(DP);
                      end;
                    end;
                  end;
            end;
          end;
    end;
  until false;

Note that you won't be able to compile this code, because the typecasting won't work. (But I'm sure you'll be able to fix it).

Compression

Several tools created by the Command & Conquer modding community, like XCC Mixer, OS SHP Builder, and the older DOS tools, like RAMIX and Vladan Bato's own Mix Manager, can write LCW, but these tools often use either very simple compression, or use the 'copy' commands and perform no real compression at all.

A reconstruction of the original LCW compression algorithm 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. This code achieves exactly the same compression as the original files inside the Westwood games.

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

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

////////////////////////////////////////////////////////////////////////////////
/// <!-- LCW_Comp() -->
/// \brief
///     Compresses data to the proprietary LCW format used in many games 
///     developed by Westwood Studios.
/// \param
///     src - Pointer to the data to compress.
/// \param
///     dst - Pointer to the buffer to store the compressed data.
/// \param
///     bytes - Size of the data to compress.
/// \return
///     Length of the compressed data in bytes.
/// \warning
///     Worst case can have the compressed data larger than the original.
////////////////////////////////////////////////////////////////////////////////
int LCW_Comp(void const *src, void *dst, unsigned int bytes, bool relative)
{
    CHRONO_ASSERT(src != NULL);
    CHRONO_ASSERT(dst != NULL);
    if ( !bytes ) {
        return 0;
    }
    //Decide if we are going to do relative offsets for 3 and 5 byte commands
    relative = (relative && bytes > UINT16_MAX) ? true : false;
    const uint8 *getp = scast<const uint8 *>(src);
    uint8 *putp = scast<uint8 *>(dst);
    const uint8 *getstart = getp;
    const uint8 *getend = getp + bytes;
    uint8 *putstart = putp;
    //relative LCW starts with 0 to flag as relative for decoder
    if ( relative ) {
        *putp++ = 0;
    }
    //Write a starting cmd1 and set bool to have cmd1 in progress
    uint8 *cmd_onep = putp;
    *putp++ = 0x81;
    *putp++ = *getp++;
    bool cmd_one = true;
    //Compress data
    while ( getp < getend ) {
        //Is RLE encode (4bytes) worth evaluating?
        if ( getend - getp > 64 && *getp == *(getp + 64) ) {
            //RLE run length is encoded as a short so max is UINT16_MAX
            const uint8 *rlemax = (getend - getp) < UINT16_MAX ? getend : getp + UINT16_MAX;
            const uint8 *rlep;
            for ( rlep = getp + 1; *rlep == *getp && rlep < rlemax; ++rlep);
            uint16 run_length = rlep - getp;
            //If run length is long enough, write the command and start loop again
            if ( run_length >= 0x41 ) {
                //write 4byte command 0b11111110
                cmd_one = false;
                *putp++ = 0xFE;
                *putp++ = run_length;
                *putp++ = run_length >> 8;
                *putp++ = *getp;
                getp = rlep;
                continue;
            }
        }
        //current block size for an offset copy
        int block_size = 0;
        const uint8 *offstart;
        //Set where we start looking for matching runs.
        if ( relative ) {
            offstart = (getp - getstart) < UINT16_MAX ? getstart : getp - UINT16_MAX;
        } else {
            offstart = getstart;
        }
        //Look for matching runs
        const uint8 *offchk = offstart;
        const uint8 *offsetp = getp;
        while ( offchk < getp ) {
            //Move offchk to next matching position
            while ( offchk < getp && *offchk != *getp ) {
                ++offchk;
            }
            //If the checking pointer has reached current pos, break
            if ( offchk >= getp ) {
                break;
            }
            //find out how long the run of matches goes for
            //<= because it can consider the current pixel as part of a run
            int i;
            for ( i = 1; &getp[i] < getend; ++i ) {
                if ( offchk[i] != getp[i] ) {
                    break;
                }
            }
            if ( i >= block_size) {
                block_size = i;
                offsetp = offchk;
            }
            ++offchk;
        }
        //decide what encoding to use for current run
        if ( block_size <= 2 ) {
            //short copy 0b10??????
            //check we have an existing 1 byte command and if its value is still
            //small enough to handle additional bytes
            //start a new command if current one doesn't have space or we don't
            //have one to continue
            if ( cmd_one && *cmd_onep < 0xBF) {
                //increment command value
                ++*cmd_onep;
                *putp++ = *getp++;
            } else {
                cmd_onep = putp;
                *putp++ = 0x81;
                *putp++ = *getp++;
                cmd_one = true;
            }
        } else {
            uint16 offset;
            uint16 rel_offset = getp - offsetp;
            if ( block_size > 0xA || (rel_offset > 0xFFF) ) {
                //write 5 byte command 0b11111111
                if ( block_size > 0x40 ) {
                    *putp++ = 0xFF;
                    *putp++ = block_size;
                    *putp++ = block_size >> 8;
                    //write 3 byte command 0b11??????
                } else {
                    *putp++ = (block_size - 3) | 0xC0;
                }
                offset = relative ? rel_offset : offsetp - getstart;
                //write 2 byte command? 0b0???????
            } else {
                //uint8 cmd_two_val = 16 * (block_size - 3) + (rel_offset >> 8);
                offset = rel_offset << 8 | (16 * (block_size - 3) + (rel_offset >> 8));
            }
            *putp++ = offset;
            *putp++ = offset >> 8;
            getp += block_size;
            cmd_one = false;
        }
    }
    //write final 0x80, this is why its also known as format80 compression
    *putp++ = 0x80;
    return putp - putstart;
}