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 a 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