Difference between revisions of "Team17 compression"

From Worms Knowledge Base

Jump to: navigation, search
(added intro, history, and decompression)
 
(Some IMG files cause the algorithm to bug out, added notes about that and which files are affected.)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{ParentArticle|[[Image file]] or [[Sprite bank file]]}}
 
The majority of Team17's unique graphic file formats are stored with their image data compressed into 1 or more data streams. The exact compression algorithm used has not been made public knowledge.
 
The majority of Team17's unique graphic file formats are stored with their image data compressed into 1 or more data streams. The exact compression algorithm used has not been made public knowledge.
  
 
== History ==
 
== History ==
 +
 
It is presumed that [[Fudge Boy]] was the first one to reverse engineer Team17's compression algorithm. He used this knowledge to create two very popular and important programs, the [[WA directory editor]] and [[The Fiddler]]. However, he never released his information about Team17's compression to the public.
 
It is presumed that [[Fudge Boy]] was the first one to reverse engineer Team17's compression algorithm. He used this knowledge to create two very popular and important programs, the [[WA directory editor]] and [[The Fiddler]]. However, he never released his information about Team17's compression to the public.
  
Many years passed before it was again reverse engineered, this time by [[acme_pjz]]. On June 12, 2008 he released his findings to the public. Very shortly thereafter, [[Pisto]] revised acme_pjz's decompression code and re-released the improvements to the public.
+
Many years passed before it was again reverse engineered, this time by [[People/acme_pjz|acme_pjz]]. On June 12, 2008 he released his findings to the public. Very shortly thereafter, [[People/Pisto|Pisto]] revised acme_pjz's decompression code and re-released the improvements to the public.
  
 
== Decompression Routine ==
 
== Decompression Routine ==
  
    public static bool Decompress(BinaryReader b, ref byte[] dStream)
+
public static bool Decompress(BinaryReader b, ref byte[] dStream)
    {
+
{
        int cmd;
+
    int cmd;
        int output = 0; //offset of next write
+
    int output = 0; //offset of next write
        while ((cmd = b.ReadByte()) != -1)
+
    while ((cmd = b.ReadByte()) != -1)
        { //read a byte
+
    { //read a byte
            if ((cmd & 0x80) == 0) //command: 1 byte (color)
+
        if ((cmd & 0x80) == 0) //command: 1 byte (color)
            {
+
            dStream[output++] = (byte)cmd;
                dStream[output++] = (byte)cmd;
+
        } else {
            }
+
            int arg1 = (cmd >> 3) & 0xF; //arg1=bits 2-5
            else
+
            int arg2 = b.ReadByte();
            {
+
            if (arg2 == -1)
                int arg1 = (cmd >> 3) & 0xF; //arg1=bits 2-5
+
                return false;
                int arg2 = b.ReadByte();
+
            arg2 = ((cmd << 8) | arg2) & 0x7FF; //arg2=bits 6-16
                if (arg2 == -1) { return false; }
+
            if (arg1 == 0) {
                arg2 = ((cmd << 8) | arg2) & 0x7FF; //arg2=bits 6-16
+
                if (arg2 == 0) //command: 0x80 0x00
                if (arg1 == 0)
+
                    return false;
                {
+
                int arg3 = b.ReadByte();
                    if (arg2 == 0) { return false; } //command: 0x80 0x00
+
                if (arg3 == -1)
                    int arg3 = b.ReadByte();
+
                    return false;
                    if (arg3 == -1) { return false; }
+
                output = CopyData(output, arg2, arg3 + 18, ref dStream); //command: 3 bytes
                    output = CopyData(output, arg2, arg3 + 18, ref dStream); //command: 3 bytes
+
            } else {
                }
+
                output = CopyData(output, arg2 + 1, arg1 + 2, ref dStream); //command: 2 bytes
                else
+
            }
                {
+
        }
                    output = CopyData(output, arg2 + 1, arg1 + 2, ref dStream); //command: 2 bytes
+
    }
                }
+
    return true;
            }
+
}
        }
+
        return true;
+
public static int CopyData(int dOffset, int cOffset, int Repeat, ref byte[] dStream)
    }
+
{
 +
    for (; Repeat > 0; Repeat--)
 +
        dStream[dOffset] = dStream[dOffset++ - cOffset];
 +
    return dOffset;
 +
}
 +
 
 +
== Problematic files ==
 +
 
 +
The decompression algorithm works fine when providing it a destination buffer in the size of Width &times; Height pixels. However, the following maps are known to require up to 3 extra bytes, or the algorithm would access the destination buffer out of bounds:
 +
 
 +
* W:A: '''Training1.img''' to '''Training9.img''' (girder-only maps)
 +
* WWP: '''mission17.img''' (generated Snow terrain)
  
    public static int CopyData(int dOffset, int cOffset, int Repeat, ref byte[] dStream)
+
Alternatively, the decompression can be aborted when an out-of-bounds access is detected, as the valid data has already been written, and images should appear properly. It is unclear whether the images are damaged or the decompression routine is flawed in specific scenarioes, as the images load fine in-game without the game seemingly reserving extra memory. Noticeably, the affected maps all seem to be "screencapped" in-game terrain.
    {
+
        for (; Repeat > 0; Repeat--)
+
        {
+
            dStream[dOffset] = dStream[dOffset++ - cOffset];
+
        }
+
        return dOffset;
+
    }
+

Latest revision as of 06:17, 30 June 2020

The majority of Team17's unique graphic file formats are stored with their image data compressed into 1 or more data streams. The exact compression algorithm used has not been made public knowledge.

History

It is presumed that Fudge Boy was the first one to reverse engineer Team17's compression algorithm. He used this knowledge to create two very popular and important programs, the WA directory editor and The Fiddler. However, he never released his information about Team17's compression to the public.

Many years passed before it was again reverse engineered, this time by acme_pjz. On June 12, 2008 he released his findings to the public. Very shortly thereafter, Pisto revised acme_pjz's decompression code and re-released the improvements to the public.

Decompression Routine

public static bool Decompress(BinaryReader b, ref byte[] dStream)
{
    int cmd;
    int output = 0;  //offset of next write
    while ((cmd = b.ReadByte()) != -1)
    {  //read a byte
        if ((cmd & 0x80) == 0) {  //command: 1 byte (color)
            dStream[output++] = (byte)cmd;
        } else {
            int arg1 = (cmd >> 3) & 0xF;  //arg1=bits 2-5
            int arg2 = b.ReadByte();
            if (arg2 == -1)
                return false;
            arg2 = ((cmd << 8) | arg2) & 0x7FF;  //arg2=bits 6-16
            if (arg1 == 0) {
                if (arg2 == 0)  //command: 0x80 0x00
                    return false;
                int arg3 = b.ReadByte();
                if (arg3 == -1)
                    return false;
                output = CopyData(output, arg2, arg3 + 18, ref dStream);  //command: 3 bytes
            } else {
                output = CopyData(output, arg2 + 1, arg1 + 2, ref dStream);  //command: 2 bytes
            }
        }
    }
    return true;
}

public static int CopyData(int dOffset, int cOffset, int Repeat, ref byte[] dStream)
{
    for (; Repeat > 0; Repeat--)
        dStream[dOffset] = dStream[dOffset++ - cOffset];
    return dOffset;
}

Problematic files

The decompression algorithm works fine when providing it a destination buffer in the size of Width × Height pixels. However, the following maps are known to require up to 3 extra bytes, or the algorithm would access the destination buffer out of bounds:

  • W:A: Training1.img to Training9.img (girder-only maps)
  • WWP: mission17.img (generated Snow terrain)

Alternatively, the decompression can be aborted when an out-of-bounds access is detected, as the valid data has already been written, and images should appear properly. It is unclear whether the images are damaged or the decompression routine is flawed in specific scenarioes, as the images load fine in-game without the game seemingly reserving extra memory. Noticeably, the affected maps all seem to be "screencapped" in-game terrain.

Personal tools