Westwood RLE-Zero

Westwood RLE-Zero

Format type	Compression algorithm
Type	Stream
I/O unit size	1-byte
Games	Dune II Lands of Lore: The Throne of Chaos The Legend of Kyrandia 2: The Hand of Fate The Legend of Kyrandia 3: Malcolm's Revenge Command & Conquer Monopoly Command & Conquer: Sole Survivor Command & Conquer: Red Alert Command & Conquer: Tiberian Sun Command & Conquer: Red Alert 2

Westwood's RLE-Zero compression is a flag-based RLE algorithm that only compacts 00 bytes in the data, which indicate transparency on the sprites. There are two file types used by Westwood Studios that use zero-compacting RLE compression: the Dune II SHP format, and the Tiberian Sun SHP format. The second version of the compression format is slightly different than the first.

Principle

Since a sprite placed on a transparent background, when seen per row, will generally have a chunk of transparent pixels, then a chunk of the actual image data, and then another chunk of transparent pixels, a very quick technique to compact sprites is to compress the obviously-repeating transparency colour but leave the rest.

This is not only used for compression purposes, but can often be fed straight into a blitter mechanism as actual instructions for writing the data into the screen buffer, optimising the drawing process.

Dune II

The RLE-Zero compression used in Dune II SHP files is a classic flag-based RLE triggered by the value 00. Whenever a 00 byte is encountered, the byte behind it will indicate how many times this 00 needs to be repeated. This RLE compression never crosses over to a next line, and should be treated line per line, a detail that is important when writing a compression algorithm, since the games will most likely not support auto-wrapping content. If overflows occur they should be ignored.

Tiberian Sun

The RLE-Zero compression used in the Tiberian Sun SHP format uses the same flag-based RLE compression as the earlier Dune II type, but differs from its predecessor in that it starts every data line with a UINT16LE value which indicates the amount of bytes in the current compressed line. This means that, using the frame height as amount of lines to process, the end of the data is defined in the data itself.

Note that the value stored as length includes the two bytes used up by the length value itself, so to get the end offset of the current data line, the length value should be added to the read offset you had at the start of the data line, before reading the length value. Alternatively, you can also just subtract 2 from the value.

Example compression / decompression code

This code was written by Nyerguds for the Engie File Converter.

Dune II

Decompression

public static Byte[] DecompressRleZeroD2(Byte[] fileData, ref Int32 offset, Int32 frameWidth, Int32 frameHeight)
{
    Int32 fullLength = frameWidth * frameHeight;
    Byte[] finalImage = new Byte[fullLength];
    Int32 datalen = fileData.Length;
    Int32 outLineOffset = 0;
    for (Int32 y = 0; y < frameHeight; y++)
    {
        Int32 outOffset = outLineOffset;
        Int32 nextLineOffset = outLineOffset + frameWidth;
        Boolean readZero = false;
        for (; offset < datalen; offset++)
        {
            if (outOffset >= nextLineOffset)
                break;
            if (readZero)
            {
                readZero = false;
                Int32 zeroes = fileData[offset];
                for (; zeroes > 0 && outOffset < nextLineOffset; zeroes--)
                    finalImage[outOffset++] = 0;
            }
            else if (fileData[offset] == 0)
            {
                readZero = true;
            }
            else
            {
                finalImage[outOffset++] = fileData[offset];
            }
        }
        outLineOffset = nextLineOffset;
    }
    return finalImage;
}

Compression

public static Byte[] CompressRleZeroD2(Byte[] imageData, Int32 frameWidth, Int32 frameHeight)
{
    using (MemoryStream ms = new MemoryStream())
    {
        Int32 inputLineOffset = 0;
        for (Int32 y = 0; y < frameHeight; y++)
        {
            Int32 inputOffset = inputLineOffset;
            Int32 nextLineOffset = inputOffset + frameWidth;
            while (inputOffset < nextLineOffset)
            {
                Byte b = imageData[inputOffset];
                if (b == 0)
                {
                    Int32 startOffs = inputOffset;
                    Int32 max = Math.Min(startOffs + 256, nextLineOffset);
                    for (; inputOffset < max && imageData[inputOffset] == 0; inputOffset++) { }
                    ms.WriteByte(0);
                    Int32 skip = inputOffset - startOffs;
                    ms.WriteByte((Byte)(skip));
                }
                else
                {
                    ms.WriteByte(b);
                    inputOffset++;
                }
            }
            inputLineOffset = nextLineOffset;
        }
        return ms.ToArray();
    }
}

Tiberian Sun

Decompression

public static Byte[] DecompressRleZeroTs(Byte[] fileData, ref Int32 offset, Int32 frameWidth, Int32 frameHeight)
{
    Byte[] finalImage = new Byte[frameWidth * frameHeight];
    Int32 datalen = fileData.Length;
    Int32 outLineOffset = 0;
    for (Int32 y = 0; y < frameHeight; y++)
    {
        Int32 outOffset = outLineOffset;
        Int32 nextLineOffset = outLineOffset + frameWidth;
        if (offset + 2 >= datalen)
            throw new ArgumentException("Not enough lines in RLE-Zero data!", "fileData");
        // Compose little-endian UInt16 from 2 bytes
        Int32 lineLen = fileData[offset] | (fileData[offset + 1] << 8);
        Int32 end = offset + lineLen;
        if (lineLen < 2 || end > datalen)
            throw new ArgumentException("Bad value in RLE-Zero line header!", "fileData");
        // Skip header
        offset += 2;
        Boolean readZero = false;
        for (; offset < end; offset++)
        {
            if (outOffset >= nextLineOffset)
                throw new ArgumentException("Bad line alignment in RLE-Zero data!", "fileData");
            if (readZero)
            {
                readZero = false;
                Int32 zeroes = fileData[offset];
                for (; zeroes > 0 && outOffset < nextLineOffset; zeroes--)
                    finalImage[outOffset++] = 0;
            }
            else if (fileData[offset] == 0)
            {
                readZero = true;
            }
            else
            {
                finalImage[outOffset++] = fileData[offset];
            }
        }
        outLineOffset = nextLineOffset;
    }
    return finalImage;
}

Compression

public static Byte[] CompressRleZeroTs(Byte[] imageData, Int32 frameWidth, Int32 frameHeight)
{
    using (MemoryStream ms = new MemoryStream())
    {
        Int32 inputLineOffset = 0;
        for (Int32 y = 0; y < frameHeight; y++)
        {
            Int64 lineStartOffs = ms.Position;
            ms.Position = lineStartOffs + 2;
            Int32 inputOffset = inputLineOffset;
            Int32 nextLineOffset = inputOffset + frameWidth;
            while (inputOffset < nextLineOffset)
            {
                Byte b = imageData[inputOffset];
                if (b == 0)
                {
                    Int32 startOffs = inputOffset;
                    Int32 max = Math.Min(startOffs + 256, nextLineOffset);
                    for (; inputOffset < max && imageData[inputOffset] == 0; inputOffset++) { }
                    ms.WriteByte(0);
                    Int32 skip = inputOffset - startOffs;
                    ms.WriteByte((Byte)(skip));
                }
                else
                {
                    ms.WriteByte(b);
                    inputOffset++;
                }
            }
            // Go back to start of the line data and fill in the length.
            Int64 lineEndOffs = ms.Position;
            Int64 len = lineEndOffs - lineStartOffs;
            if (len > UInt16.MaxValue)
                throw new ArgumentException("Compressed line width is too large to store!", "imageData");
            ms.Position = lineStartOffs;
            ms.WriteByte((Byte)(len & 0xFF));
            ms.WriteByte((Byte) ((len >> 8) & 0xFF));
            ms.Position = lineEndOffs;
            inputLineOffset = nextLineOffset;
        }
        return ms.ToArray();
    }
}