Westwood Compression Method One

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

Westwood compression method one

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.

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