RLE Compression

From ModdingWiki
Jump to: navigation, search
RLE Compression
Format typeCompression algorithm
TypeStream
I/O unit size1-byte
GamesN/A

Run-Length Encoding (RLE) is a form of lossless compression, and one of the simplest ways of compressing and storing data. It is used in various forms by games on nearly every platform. The essence of this compression method is to compress data by saving the "run-length" of the encountered values, which boils down to storing the data as a collection of length/value pairs. To take a simple case, the string 'aaaaaaaabbb' could be compressed to '8a3b' (8 bytes of a, 3 bytes of b). The trick with RLE is to make sure the data does not end up becoming larger after processing. For example, using pure length/value pairs, 'abracadabra' would become '1a1b1r1a1c1a1d1a1b1r1a'. Variations were designed to get around this problem.

Most systems also tell the program beforehand the size of the decompressed data, stored as a word or dword at the start of the data block. This is usually done so that the correct amount of memory can be allocated before the data is processed. In modern programs this is generally considered a security risk (it is trivial to write past the end of the allocated buffer), but this was not considered an issue at the time the games were written. On the other hand, a sane decompression algorithm should obviously abort the decompression process when reaching the end of its allocated buffer space anyway.

Different systems

There are three main systems of RLE, divided by how the length and values are specified.

Length/Value

In this system, all data is stored in pairs of values, with one being the value to repeat, and the other the amount of times to repeat that value. The order in which these two are stored varies in different implementations. So using the simple system above, the string '3a4b1c' would be read as 'Length 3 of a, length 4 of b, length 1 of c', and become 'aaabbbbc' when decompressed. This system is the simplest, but has the disadvantage that it greatly expands blocks of non-repeating data by prefixing each one with a repeat value of '1'.

Flag

In the second system a 'flag' is used. This is a special value that tells a program to do something whenever it is encountered. So the string '*3abcd*3e' could be decompressed to 'aaabcdeee' where '*' is the flag value, indicating that a length/value pair is coming up next. Flags may indicate a number of things (Usually a length/value pair) and can be words, bytes or bits (E.g all values over 128 are length bytes, all under value bytes). This is more complex and is less efficient space-wise than the first system, but has the advantage that the data can usually be read from multiple points and an error may not corrupt all following data (since every flag 'resets' the decompression).

Code

The most commonly used type of RLE is the Code type. A 'Code' is a value which contains two things: a Command, and a Value. The Command indicates if the following data is a single piece to be repeated or a range to be copied as it is. The Value indicates how many times to repeat the data, or how much data to copy, before reading a new Code behind the processed data. The typical implementation of this system is to use one single byte as Code, where the highest bit is 0 or 1 depending on the Command, and the Value is made from the remaining 7 bits, allowing a Value range of 0 to 127.

Sometimes, the normally-useless codes that would indicate repeating or copying 0 bytes are given special additional functions, like reading additional bytes to get a larger repeat/copy value, or are simply compensated by incrementing the 7-bit Value that is read. This increment is usually 1, but sometimes 2 for the Repeat command, since a repeat of 1 is identical to a copy of 1.

This type is not recoverable like the Flag type, but has the advantage that there are no restrictions on the type of data that can be compressed, since the decompression will never try to interpret non-code bytes as codes. Its main advantage over Length/Value is that it only needs a single code to process a whole range of uncompressed data.

Compression units

RLE compression can occur at several levels, bits, bytes or words (RLEB, RLE, RLEW). Most common is at the byte level. The used type often depends on what kind of data is being compressed. For example, most tilesets work on the byte level (1 pixel = 1 byte) and so will be compressed at the byte level, while most levels are made of two byte values for tiles and will be compressed at the word level.

RLEW compression has its own page which describes how it it commonly implemented.

Types of RLE

Source code

C#

The following code will decompress/compress raw data using the Code format, with the highest bit in the code byte indicating the command, and the remaining bits indicating the amount to copy or repeat. The class is made so the MaxRepeatValue and MaxCopyValue constants and the GetCode and WriteCode functions can be overridden in subclasses, to easily implement variations on the standard behaviour. An RleCompressionHighBitRepeat and an RleCompressionHighBitCopy class are added as basic implementations of the abstract RleImplementation<T> class.

This type of RLE compression, with the highest bit set for the Repeat code, is the one used in all Sierra/Dynamix games.

/// <summary>
/// Basic implementation of Run-Length Encoding with the highest bit set for the Repeat code.
/// The used run length is always (code & 0x7F).
/// </summary>
public class RleCompressionHighBitRepeat : RleImplementation<RleCompressionHighBitRepeat> { }
 
/// <summary>
/// Basic implementation of Run-Length Encoding with the highest bit set for the Copy code.
/// The used run length is always (code & 0x7F).
/// This calls the original GetCode/WriteCode functions but simply flips their "Repeat" boolean.
/// </summary>
public class RleCompressionHighBitCopy : RleImplementation<RleCompressionHighBitCopy>
{
    protected override Boolean GetCode(Byte[] buffer, ref UInt32 inPtr, UInt32 bufferEnd, out Boolean isRepeat, out UInt32 amount)
    {
        Boolean success = base.GetCode(buffer, ref inPtr, bufferEnd, out isRepeat, out amount);
        isRepeat = !isRepeat;
        return success;
    }
 
    protected override Boolean WriteCode(Byte[] bufferOut, ref UInt32 outPtr, UInt32 bufferEnd, Boolean forRepeat, UInt32 amount)
    {
        return base.WriteCode(bufferOut, ref outPtr, bufferEnd, !forRepeat, amount);
    }
}
 
/// <summary>
/// Basic Run-Length Encoding algorithm. Written by Maarten Meuris, aka Nyerguds.
/// This class allows easy overriding of the code to read and write codes, to
/// allow flexibility in subclassing the system for different RLE implementations.
/// </summary>
/// <typeparam name="T">
/// The implementing class. This trick allows access to the internal type and its constructor from static functions
/// in the superclass, giving the subclasses access to static functions that still use the specific subclass behaviour.
/// </typeparam>
public abstract class RleImplementation<T> where T : RleImplementation<T>, new()
{
    #region overridables to tweak in subclasses
    /// <summary>Maximum amount of repeating bytes that can be stored in one code.</summary>
    public virtual UInt32 MaxRepeatValue { get { return 0x7F; } }
    /// <summary>Maximum amount of copied bytes that can be stored in one code.</summary>
    public virtual UInt32 MaxCopyValue { get { return 0x7F; } }
 
    /// <summary>
    /// Reads a code, determines the repeat / copy command and the amount of bytes to repeat / copy,
    /// and advances the read pointer to the location behind the read code.
    /// </summary>
    /// <param name="buffer">Input buffer.</param>
    /// <param name="inPtr">Input pointer.</param>
    /// <param name="bufferEnd">Exclusive end of buffer; first position that can no longer be read from.</param>
    /// <param name="isRepeat">Returns true for repeat code, false for copy code.</param>
    /// <param name="amount">Returns the amount to copy or repeat.</param>
    /// <returns>True if the read succeeded, false if it failed.</returns>
    protected virtual Boolean GetCode(Byte[] buffer, ref UInt32 inPtr, UInt32 bufferEnd, out Boolean isRepeat, out UInt32 amount)
    {
        if (inPtr >= bufferEnd)
        {
            isRepeat = false;
            amount = 0;
            return false;
        }
        Byte code = buffer[inPtr++];
        isRepeat = (code & 0x80) != 0;
        amount = (UInt32)(code & 0x7f);
        return true;
    }
 
    /// <summary>
    /// Writes the repeat / copy code to be put before the actual byte(s) to repeat / copy,
    /// and advances the write pointer to the location behind the written code.
    /// </summary>
    /// <param name="bufferOut">Output buffer to write to.</param>
    /// <param name="outPtr">Pointer for the output buffer.</param>
    /// <param name="bufferEnd">Exclusive end of buffer; first position that can no longer be written to.</param>
    /// <param name="forRepeat">True if this is a repeat code, false if this is a copy code.</param>
    /// <param name="amount">Amount to write into the repeat or copy code.</param>
    /// <returns>True if the write succeeded, false if it failed.</returns>
    protected virtual Boolean WriteCode(Byte[] bufferOut, ref UInt32 outPtr, UInt32 bufferEnd, Boolean forRepeat, UInt32 amount)
    {
        if (outPtr >= bufferEnd)
            return false;
        if (forRepeat)
            bufferOut[outPtr++] = (Byte)(amount | 0x80);
        else
            bufferOut[outPtr++] = (Byte)(amount);
        return true;
    }
    #endregion
 
    #region static functions
    /// <summary>
    /// Decodes RLE-encoded data.
    /// </summary>
    /// <param name="buffer">Buffer to decode.</param>
    /// <param name="startOffset">Start offset in buffer.</param>
    /// <param name="endOffset">End offset in buffer.</param>
    /// <param name="decompressedSize">The expected size of the decompressed data.</param>
    /// <param name="abortOnError">If true, any found command with amount "0" in it will cause the process to abort and return null.</param>
    /// <returns>A byte array of the given output size, filled with the decompressed data.</returns>
    public static Byte[] RleDecode(Byte[] buffer, UInt32? startOffset, UInt32? endOffset, Int32 decompressedSize, Boolean abortOnError)
    {
        T rle = new T();
        return rle.RleDecodeData(buffer, startOffset, endOffset, decompressedSize, abortOnError);
    }
 
    /// <summary>
    /// Decodes RLE-encoded data.
    /// </summary>
    /// <param name="buffer">Buffer to decode.</param>
    /// <param name="startOffset">Start offset in buffer.</param>
    /// <param name="endOffset">End offset in buffer.</param>
    /// <param name="bufferOut">Output array. Determines the maximum that can be decoded.</param>
    /// <param name="abortOnError">If true, any found command with amount "0" in it will cause the process to abort and return null.</param>
    /// <returns>The amount of written bytes in bufferOut.</returns>
    public static Int32 RleDecode(Byte[] buffer, UInt32? startOffset, UInt32? endOffset, Byte[] bufferOut, Boolean abortOnError)
    {
        T rle = new T();
        return rle.RleDecodeData(buffer, startOffset, endOffset, bufferOut, abortOnError);
    }
 
    /// <summary>
    /// Applies Run-Length Encoding (RLE) to the given data.
    /// </summary>
    /// <param name="buffer">Input buffer.</param>
    /// <returns>The run-length encoded data.</returns>
    public static Byte[] RleEncode(Byte[] buffer)
    {
        T rle = new T();
        return rle.RleEncodeData(buffer);
    }
    #endregion
 
    #region public functions
    /// <summary>
    /// Decodes RLE-encoded data.
    /// </summary>
    /// <param name="buffer">Buffer to decode.</param>
    /// <param name="startOffset">Inclusive start offset in buffer. Defaults to 0.</param>
    /// <param name="endOffset">Exclusive end offset in buffer. Defaults to the buffer length.</param>
    /// <param name="decompressedSize">The expected size of the decompressed data.</param>
    /// <param name="abortOnError">If true, any found command with amount "0" in it will cause the process to abort and return null.</param>
    /// <returns>A byte array of the given output size, filled with the decompressed data, or null if abortOnError is enabled and an empty command was found.</returns>
    public Byte[] RleDecodeData(Byte[] buffer, UInt32? startOffset, UInt32? endOffset, Int32 decompressedSize, Boolean abortOnError)
    {
        Byte[] outputBuffer = new Byte[decompressedSize];
        Int32 result = this.RleDecodeData(buffer, startOffset, endOffset, outputBuffer, abortOnError);
        if (result == -1)
            return null;
        return outputBuffer;
    }
 
    /// <summary>
    /// Decodes RLE-encoded data.
    /// </summary>
    /// <param name="buffer">Buffer to decode.</param>
    /// <param name="startOffset">Inclusive start offset in buffer. Defaults to 0.</param>
    /// <param name="endOffset">Exclusive end offset in buffer. Defaults to the buffer length.</param>
    /// <param name="bufferOut">Output array. Determines the maximum that can be decoded.</param>
    /// <param name="abortOnError">If true, any found command with amount "0" in it will cause the process to abort and return -1.</param>
    /// <returns>The amount of written bytes in bufferOut.</returns>
    public Int32 RleDecodeData(Byte[] buffer, UInt32? startOffset, UInt32? endOffset, Byte[] bufferOut, Boolean abortOnError)
    {
        UInt32 inPtr = startOffset ?? 0;
        UInt32 inPtrEnd = endOffset.HasValue ? Math.Min(endOffset.Value, (UInt32)buffer.Length) : (UInt32)buffer.Length;
        Int32 outPtr = 0;
        Int32 maxOutLen = bufferOut.Length;
 
        // RLE implementation:
        // highest bit set = followed by range of repeating bytes
        // highest bit not set = followed by range of non-repeating bytes
        // In both cases, the "code" specifies the amount of bytes; either to repeat, or to copy.
 
        while (outPtr < maxOutLen && inPtr < inPtrEnd)
        {
            // get next code
            UInt32 run;
            Boolean repeat;
            if (!this.GetCode(buffer, ref inPtr, inPtrEnd, out repeat, out run))
                return -1;
            if (run == 0 && abortOnError)
                return -1;
            //End ptr after run
            UInt32 runEnd = Math.Min((UInt32)(outPtr + run), (UInt32)maxOutLen);
            // Repeat run
            if (repeat)
            {
                if (inPtr >= inPtrEnd)
                    return outPtr;
                Int32 repeatVal = buffer[inPtr++];
                for (; outPtr < runEnd; outPtr++)
                    bufferOut[outPtr] = (Byte)repeatVal;
                if (outPtr == maxOutLen)
                    return outPtr;
            }
            // Raw copy
            else
            {
                for (; outPtr < runEnd; outPtr++)
                {
                    if (inPtr >= inPtrEnd)
                        return outPtr;
                    Int32 data = buffer[inPtr++];
                    bufferOut[outPtr] = (Byte)data;
                }
                if (outPtr == maxOutLen)
                    return outPtr;
            }
        }
        return outPtr;
    }
 
    /// <summary>
    /// Applies Run-Length Encoding (RLE) to the given data. This particular function achieves especially good compression by only
    /// switching from a Copy command to a Repeat command if more than two repeating bytes are found, or if the maximum copy amount
    /// is reached. This avoids adding extra Copy command bytes after replacing two repeating bytes by a two-byte Repeat command.
    /// </summary>
    /// <param name="buffer">Input buffer.</param>
    /// <returns>The run-length encoded data.</returns>
    public Byte[] RleEncodeData(Byte[] buffer)
    {
        UInt32 inPtr = 0;
        UInt32 outPtr = 0;
        // Ensure big enough buffer. Sanity check will be done afterwards.
        UInt32 bufLen = (UInt32)((buffer.Length * 3) / 2);
        Byte[] bufferOut = new Byte[bufLen];
 
        // Retrieve these in advance to avoid extra calls to getters.
        // These are made customizable because some implementations support larger codes. Technically
        // neither run-length 0 nor 1 are useful for repeat codes (0 should not exist, 1 is identical to copy),
        // so these two values could be used as indicators for reading a larger value to repeat or copy.
        // Some implementations also decrement the repeat code value to allow storing one or two more bytes.
        UInt32 maxRepeat = this.MaxRepeatValue;
        UInt32 maxCopy = this.MaxCopyValue;
        // Standard RLE implementation:
        // highest bit set = followed by range of repeating bytes
        // highest bit not set = followed by range of non-repeating bytes
        // In both cases, the "code" specifies the amount of bytes; either to write, or to skip.
        UInt32 len = (UInt32)buffer.Length;
        UInt32 detectedRepeat = 0;
        while (inPtr < len)
        {
            // Handle 2 cases: repeat was already detected, or a new repeat detect needs to be done.
            if (detectedRepeat >= 2 || (detectedRepeat = RepeatingAhead(buffer, len, inPtr, 2)) == 2)
            {
                // Found more than 2 bytes. Worth compressing. Apply run-length encoding.
                UInt32 start = inPtr;
                UInt32 end = Math.Min(inPtr + maxRepeat, len);
                Byte cur = buffer[inPtr];
                // Already checked these in the RepeatingAhead function.
                inPtr += detectedRepeat;
                // Increase inptr to the last repeated.
                for (; inPtr < end && buffer[inPtr] == cur; inPtr++) { }
                // WriteCode is split off into a function to allow overriding it in specific implementations.
                if (!this.WriteCode(bufferOut, ref outPtr, bufLen, true, (inPtr - start)) || outPtr + 1 >= bufLen)
                    break;
                // Add value to repeat
                bufferOut[outPtr++] = cur;
                // Reset for next run
                detectedRepeat = 0;
            }
            else
            {
                Boolean abort = false;
                // if detectedRepeat is not greater than 1 after writing a code,
                // that means the maximum copy length was reached. Keep repeating
                // until the copy is aborted for a repeat.
                while (detectedRepeat == 1 && inPtr < len)
                {
                    UInt32 start = inPtr;
                    // Normal non-repeat detection logic.
                    UInt32 end = Math.Min(inPtr + maxCopy, len);
                    UInt32 maxend = inPtr + maxCopy;
                    inPtr += detectedRepeat;
                    while (inPtr < end)
                    {
                        // detected bytes to compress after this one: abort.
                        detectedRepeat = RepeatingAhead(buffer, len, inPtr, 3);
                        // Only switch to Repeat when finding three repeated bytes: if the data
                        // behind a repeat of two is non-repeating, it adds an extra Copy command.
                        if (detectedRepeat == 3)
                            break;
                        // Optimise: apply a 1-byte or 2-byte skip to ptr right away.
                        inPtr += detectedRepeat;
                        // A detected repeat of two could make it go beyond the maximum accepted number of
                        // stored bytes per code. This fixes that. These repeating bytes are always saved as
                        // Repeat code, since a new command needs to be added after ending this one anyway.
                        // If you'd use the copy max amount instead, the 2-repeat would be cut in two Copy
                        // commands, wasting one byte if another repeating range would start after it.
                        if (inPtr > maxend)
                        {
                            inPtr -= detectedRepeat;
                            break;
                        }
                    }
                    UInt32 amount = inPtr - start;
                    if (amount == 0)
                    {
                        abort = true;
                        break;
                    }
                    // Need to reset this if the copy commands aborts for full size, so a last-detected repeat
                    // value of 2 at the end of a copy range isn't propagated to a new repeat command.
                    if (amount == maxCopy)
                        detectedRepeat = 0;
                    // WriteCode is split off into a function to allow overriding it in specific implementations.
                    abort = !this.WriteCode(bufferOut, ref outPtr, bufLen, false, amount) || outPtr + amount >= bufLen;
                    if (abort)
                        break;
                    // Add values to copy
                    for (UInt32 i = start; i < inPtr; i++)
                        bufferOut[outPtr++] = buffer[i];
                }
                if (abort)
                    break;
            }
        }
        Byte[] finalOut = new Byte[outPtr];
        Array.Copy(bufferOut, 0, finalOut, 0, outPtr);
        return finalOut;
    }
    #endregion
 
    #region internal tools
    /// <summary>
    /// Checks if there are enough repeating bytes ahead.
    /// </summary>
    /// <param name="buffer">Input buffer.</param>
    /// <param name="max">The maximum offset to read inside the buffer.</param>
    /// <param name="ptr">The current read offset inside the buffer.</param>
    /// <param name="minAmount">Minimum amount of repeating bytes to search for.</param>
    /// <returns>The amount of detected repeating bytes.</returns>
    protected static UInt32 RepeatingAhead(Byte[] buffer, UInt32 max, UInt32 ptr, UInt32 minAmount)
    {
        Byte cur = buffer[ptr];
        for (UInt32 i = 1; i < minAmount; i++)
            if (ptr + i >= max || buffer[ptr + i] != cur)
                return i;
        return minAmount;
    }
    #endregion
}