Westwood LZW-12

Westwood LZW-12

Format type	Compression algorithm
Type	Stream
I/O unit size	1-bit
Games	BattleTech: The Crescent Hawk's Revenge Eye of the Beholder

Westwood LZW-12 is a textbook implementation of LZW compression with a code length of 12 bits, following the basic LZW algorithm as described Mark Nelson. It is often referred to as "Format 1" or "Westwood Compression Method 1", because it is generally indicated in file headers' compression type as value "1".

This compression method was used by Westwood in PC games such as BattleTech: The Crescent Hawk's Revenge and the first game in the Eye of the Beholder series. It was abandoned around 1993-1994 due to copyright enforcement on LZW by Unisys, and replaced by Westwood LCW.

Compressed structure

The compressed data stream is made up of groups which are 12 bits long each. The last group is set to 0xfff and should only be treated as an end marker. Finally the stream ends with 8 bits set to zero for files with even length or 12 bits for files with uneven length. The contents of the groups have two functions.

Byte group

0000 cccc cccc - When the first four bits are set to zero the following eight bits represents a byte to store in the decompressed data stream.

Index group

xxxx yyyy yyyy - When the first four bits are not set to zero the whole group represents an index value which points to a previous group in the compressed data stream. To get the correct index value you first need to decrease the first four bits by one.

Decompression explained

When processing a byte group its byte value is simply stored as is into the decompressed data stream. Index groups on the other hand will always store at least two bytes. First the byte value retrieved from where the index pointed to. Secondly the byte value from the group next to where we got the first byte value. Since index groups may point to other index groups we have to travel through the index tree until we end up at a byte group to know which byte we can store. Thus for each extra jump in the index tree we will store one byte value next to each traveled index group.

Decompression illustrated

To better explain how this works, here is the first part of one of the files from the PC version of the first game in the Eye of the Beholder series.

BLUE.EGA

                              »
7a 36 01 00 00 fa 00 00 00 00 00 01 00 10 00 08
00 60 08 10 51 01 10 7. .. .. .. .. .. .. .. ..

And here is the compressed data formed in 12 bit groups.

Index	Group	Description	Decompressed data
0	000	Byte group Store byte value 0	0
1	100	Index group Jump to group index 0 Store byte value 0	0
		Advance to next group Jump to group index 0 Store byte value 0	0
2	100	Index group Jump to group index 0 Store byte value 0	0
		Advance to next group Jump to group index 0 Store byte value 0	0
3	008	Byte group Store byte value 8	8
4	006	Byte group Store byte value 6	6
5	008	Byte group Store byte value 8	8
6	105	Index group Jump to group index 5 Store byte value 8	8
		Advance to next group Jump to group index 5 Store byte value 8	8
7	101	Index group Jump to group index 1 Jump to group index 0 Store byte value 0	0
		Advance to next group Jump to group index 0 Store byte value 0	0
		Return to group index 1 Advance to next group Jump to group index 0 Store byte value 0	0
8	107	Index group Jump to group index 7 Jump to group index 1 Jump to group index 0 Store byte value 0	0
		Advance to next group Jump to group index 0 Store byte value 0	0
		Return to group index 1 Advance to next group Jump to group index 0 Store byte value 0	0
		Return to group index 7 Advance to next group Jump to group index 7 Jump to group index 1 Jump to group index 0 Store byte value 0	0

Decompression sample code

Here is working sample code which was the result of the compressed data pattern analysis.

private byte[] Decompress1(Content c)
{
    Header h = GetHeader(c.data);
    byte[] data = new byte[h.originalSize];
    int a = 10 + h.paletteSize, b = 0;
    bool low = false;
    byte[] tribbles = new byte[(c.data.Length - (a + 1)) * 2 / 3 * 2];
    if (c.data[c.data.Length - 1] != 0x00) return null;
    while (true)
    {
        if (a >= c.data.Length - 1) return null;
        byte[] nibbles = new byte[3];
        for (int n = 0; n != 3; n++)
        {
            if (low == false)
            {
                nibbles[n] = (byte)(c.data[a] >> 4);
                low = true;
            }
            else
            {
                nibbles[n] = (byte)(c.data[a] & 0x0f);
                low = false;
                a++;
            }
        }
        if (b + 1 >= tribbles.Length) return null;
        tribbles[b] = nibbles[0];
        tribbles[b + 1] = (byte)((nibbles[1] << 4) | nibbles[2]);
        if (tribbles[b] == 0x0f && tribbles[b + 1] == 0xff) break;
        b += 2;
    }
    if (a + 1 != c.data.Length && a + 2 != c.data.Length && b + 2 != tribbles.Length) return null;
    for (a = 0, b = 0; a != tribbles.Length - 2; a += 2)
    {
        int offset = a;
        int count = 0;
        while (tribbles[offset] != 0x00)
        {
            offset = (((tribbles[offset] - 1) << 8) | tribbles[offset + 1]) * 2;
            if (offset >= a) return null;
            count++;
        }
        if (b == data.Length) return null;
        data[b] = tribbles[offset + 1];
        b++;
        if (count == 0) continue;
        while (count != 0)
        {
            offset += 2;
            int o = offset;
            while (tribbles[offset] != 0x00)
            {
                offset = (((tribbles[offset] - 1) << 8) | tribbles[offset + 1]) * 2;
                if (offset >= o) return null;
            }
            if (b == data.Length) return null;
            data[b] = tribbles[offset + 1];
            b++;
            count--;
            offset = a;
            int counter = 0;
            while (counter != count)
            {
                offset = (((tribbles[offset] - 1) << 8) | tribbles[offset + 1]) * 2;
                if (offset >= a) return null;
                counter++;
            }
        }
    }
    return data;
}

/ Linus Kalliope