Westwood RLE-Zero

From ModdingWiki
Jump to: navigation, search

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 value 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 differs from the earlier Dune II type in that it prefixes every line with a UINT16LE value which indicates the amount of bytes in the following 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.

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!");
        Int32 lineLen = (Int32) ArrayUtils.ReadIntFromByteArray(fileData, offset, 2, true);
        Int32 end = offset + lineLen;
        if (lineLen < 2 || end > datalen)
            throw new ArgumentException("Bad value in RLE-Zero line header!");
        // Skip header
        offset += 2;
        Boolean readZero = false;
        for (; offset < end; offset++)
        {
            if (outOffset >= nextLineOffset)
                throw new ArgumentException("Bad line alignment in RLE-Zero data!");
            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 NotSupportedException("Compressed line width is too large to store!");
            ms.Position = lineStartOffs;
            ms.WriteByte((Byte)(len & 0xFF));
            ms.WriteByte((Byte) ((len >> 8) & 0xFF));
            ms.Position = lineEndOffs;
            inputLineOffset = nextLineOffset;
        }
        return ms.ToArray();
    }
}