Westwood LCW

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

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, despite this, it is actually 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. I will give some sample code at the end.

These are all the commands I found out. Maybe there are other ones, but I haven't seen them yet.

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. Note that 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, that means that 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 Destination buffer. Both Count and Pos are words.


Code

To make things more clear, here's a piece of code that will decompress the image.

  • 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).

(C) Vladan Bato