Tetris DX RLE encode/decode example

// RLE.cs - Tetris DX RLE encode/decode (example) - Ed Kearney

using System;

namespace TetrisDx_RLE_encode_decode
{
    public class RLE
    {
        private enum OperationMode { Compression, RawData, Inspect } // When encoding data, there are 3 modes of operation when analysing the raw data...

        // Encoding Operation modes:
        // -------------------------
        // Inspect mode -     Read the data to see if it can be Compressed or not, either enters RawData or Compression modes depending on
        //                    if it reads two different bytes (enters RawData mode), or 3 matching bytes (enters Compression mode)
        // Compression mode - it keeps reading until it finds the end of a block, then end of the input data, or a different input byte,
        //                    then it writes the compressed data and changes to the correct mode
        // RawData mode -     it keeps reading until  the end of a block, then end of the input data, or a matching set of 3 input bytes,
        //                    then it writes the compressed data and changes to the correct mode

        public byte[] RLEDecodeGraphics(byte[] data, int numBlocks = 0, int numTiles = 0, int startTileIndex = 0)
        {
            // Decode a byte array according to the following table.
            // Note: Valid data must be found at array index 0.

            // Value    Meaning
            // -----    ----------------------------------------------------------
            // 00       End of data.
            // 01 - 7F  Read another byte, and write it to the output n times.
            // 80       Invalid.
            // 81 - FF  Copy n -128 bytes from input to output.

            // Parameters:
            // -----------
            // data - the input encoded data
            // numBlocks - the number of blocks to decode (default is 0, which means unlimited)
            // numTiles - the number of tiles to decode (default is 0, which means unlimited) [not implemented]
            // startTileIndex - the tile to start outputting from  (default is 0, which means the first) [not implemented]

            int blockCount = 0; // count the number of blocks, so that data can be limited in parameters
            // int tileCount = 0;  // count the number of tiles, so that data can be limited in parameters [not implemented]

            int startingSize = 10000000; // maximum size of encoded data (truncated later) [there are probably better ways to do this]
            byte[] decodedData = new byte[startingSize]; // create a dummy byte array, that will be written to, based on the input encoded data

            byte mask = 0x80; // + 128 bytes - this indicates that the encoded data is a sequence of raw data

            int dataLength = 0; // length of data to process
            byte packedCharacter = 0x00; // currect character to output n times.
            int byteCompressedCount = 0; // how far through the encoded data are we?
            int byteUncompressedCount = 0; // how large has the decoded data become?


            while (byteCompressedCount < data.Length) // go through all the input data
            {
                dataLength = data[byteCompressedCount]; // get current byte (the length of the following data)

                if (dataLength == 0x00) // end of data block
                {
                    byteCompressedCount += 1; // skip to next block if available, otherwise ends while loop (for valid data).

                    blockCount++; // increase the count of the number of blocks of data

                    if (numBlocks != 0 && blockCount == numBlocks) // if the intended number of blocks is reached
                    {
                        byteCompressedCount = data.Length; // exit the while loop
                    }
                }
                else if (dataLength > 0x80) // a block of raw (decoded) data follows
                {
                    byteCompressedCount += 1; // move to data

                    dataLength = dataLength & ~mask; // (length n - 128)

                    for (int j = 0; j < dataLength; j++) // populate the decoded data array
                    {
                        if (byteCompressedCount < data.Length) // if the end of the data has not been reached
                        {
                            decodedData[byteUncompressedCount] = data[byteCompressedCount]; // decode a byte of data
                            byteUncompressedCount++; // increase the index number of the output data by the length of the data just written
                            byteCompressedCount++; // increase the index number of the source data by the length of the data just read
                        }
                    }
                }
                else if (dataLength < 0x80) // copy the following byte dataLength times
                {
                    packedCharacter = data[byteCompressedCount + 1]; // get target byte to write

                    for (int j = 0; j < dataLength; j++) // populate the decoded data array dataLength times
                    {
                        decodedData[byteUncompressedCount] = packedCharacter; // write the target byte
                        byteUncompressedCount++; // increase the index number of the output data by the length of the data just written
                    }

                    byteCompressedCount += 2; // increase the index number of the source data by the length of the data just read
                }
                else
                {
                    //dataLength == 0x80 - do nothing...
                }

            }
            Array.Resize(ref decodedData, byteUncompressedCount); // truncate decoded data to the correct length

            return decodedData; // return the decoded data
        }

        public byte[] RLEEncodeGraphics(byte[] data, int blockSize = 0, int targetSize = 0, int blockCount = 0, bool squeezeMode = false)
        {
            // Encode a byte array according to the following table.
            // Note: Valid data must be found at array index 0.

            // Value    Meaning
            // -----    ----------------------------------------------------------
            // 00       End of data.
            // 01 - 7F  Read another byte, and write it to the output n times.
            // 80       Invalid.
            // 81 - FF  Copy n -128 bytes from input to output.

            // Parameters:
            // -----------
            // data - the input decoded/raw data
            // blockSize - the size of a block of graphics data - this is equivalent to 1 bank of VRAM in Tetris DX (default is 0, which means unlimited)
            // targetSize - the length of the data that we want to replace (allows us to check if the new data is shorter, longer or the same size as the existing data) (default is 0, which means don't care)
            // blockCount - the number of blocks to encode (default is 0, which means unlimited/all)
            // squeezeMode - if enabled, this will trash data at the end of a block so that it will have the same length as the input data (target length)
            // NOTE: squeezeMode requires blockSize, targetSize, and blockCount to be set


            int startingSize = 10000000; // maximum size of encoded data (truncated later) [there are probably better ways to do this]

            byte[] encodedData = new byte[startingSize]; // create a dummy byte array, that will be written to, based on the input decoded data

            byte mask = 0x80; // + 128 bytes - this indicates that the encoded data is a sequence of raw data

            byte currentByte = 0x00, previousByte = 0x00, nextPreviousByte = 0x00;

            int byteCount = 0; // count the number of blocks, so that data can be limited in parameters

            int byteCompressedCount = 0; // how large has the encoded data gotten?
            int byteUncompressedCount = 0; // how far through the decoded data are we?

            bool blockEnd = false; // flags if we need to handle the end of a block
            bool squeezeData = false; // flags if we need to squuze the rest of the data

            OperationMode mode = OperationMode.Inspect; // start out in Inspect Mode

            // Limit the input data size to be the number of blocks specified (otherwise unlimited/startingSize)
            int maxDataSize = data.Length;
            if (blockCount != 0)
                maxDataSize = blockCount * blockSize;

            while ((byteUncompressedCount + byteCount) <= maxDataSize)
            {
                // process all of the raw input data, until the end of it, or until the requested amount of blocks has been reached
                // this is *less than OR equals to* so that the end of a block can be correctly processed.

                if (blockSize > 0 && (byteUncompressedCount + byteCount) > 0 && (byteUncompressedCount + byteCount) % blockSize == 0)
                {
                    blockEnd = true; // If a block size has been specified, and we are at the end of a block, flag it
                }
                else if (squeezeMode) // If the data has to fit within the target size (no matter what)
                {
                    // get the size of the encoded output data
                    int currentSize = byteCompressedCount;
                    if (mode == OperationMode.Compression)
                        currentSize += 2;
                    else
                        currentSize += byteCount;

                    // Check the remaining space (allotted by the targetSize)
                    if (SqueezeDataCheck(targetSize, currentSize, blockSize, byteUncompressedCount + byteCount - 1))
                    {
                        // If we have run out of space, we need to flag that we should save the current section and squeeze the rest of the bytes in the block
                        byteCount -= 1; // we can't actually write the current byte, so move back a step
                        squeezeData = true;
                    }
                }

                //default mode is "Inspect mode" - look for potential blocks of data, starting from the last position of unknown input data

                if (squeezeData || blockEnd || byteCount == 0x7F) // 1st check - do we need to write the current section of data due to a limit?
                {
                    // Limits:
                    // -------
                    // 1: Data needs to be squuezed (developer function)
                    // 2: The end of a block has been reached
                    // 3: The current section has reached a length of 0x7F (the maximum length of a section)

                    if (mode == OperationMode.Inspect) mode = OperationMode.RawData; // shouldn't be needed, but just in case

                    if (byteCount > 0) // If there is data to write, write it
                    {
                        if (mode == OperationMode.Compression)
                            RLEWriteEncodedGraphics(ref encodedData, ref byteCompressedCount, ref byteUncompressedCount, previousByte, byteCount);
                        else
                            RLEWriteRawGraphics(ref encodedData, ref byteCompressedCount, data, ref byteUncompressedCount, mask, byteCount);
                    }
                    byteCount = 0; // reset the the index of the current section

                    if (squeezeData) // Squeeze the data if needed
                    {
                        SqueezeData(ref encodedData, ref byteCompressedCount, blockSize - byteUncompressedCount, ref byteUncompressedCount);
                        squeezeData = false; // turn the flag off
                        blockEnd = true; // make sure the end of the block indicator is added
                        byteUncompressedCount++; //hack!!!!!
                    }

                    if (blockEnd) // add the end of a block indicator (if needed)
                    {
                        RLEWriteEndOfBlock(ref encodedData, ref byteCompressedCount);
                        blockCount++; // increase the count of blocks by 1
                        blockEnd = false; // turn the flag off
                    }

                    mode = OperationMode.Inspect; // revert to Inspect mode, in case there is more data to process after this
                }
                else if (mode == OperationMode.Inspect && byteCount > 1) // Inspect mode: work out whether the current section of data is compressible or not, and then set the correct mode
                {
                    if (currentByte != previousByte) // if the current byte is different to the previous one, then treat this section as raw data (and enter RawData mode)
                        mode = OperationMode.RawData;
                    else if (previousByte == nextPreviousByte && previousByte == currentByte) // if the current byte is the same as the previous two, then  treat this section as compressed data (and enter Compression mode)
                        mode = OperationMode.Compression;
                    // else stay in Inspect mode
                }
                else if (mode == OperationMode.Compression && currentByte != previousByte) //  Compression mode: the compressible data has ended (a non-matching byte has been found)
                {
                    RLEWriteEncodedGraphics(ref encodedData, ref byteCompressedCount, ref byteUncompressedCount, previousByte, byteCount - 1); // write the section of compressed data
                    mode = OperationMode.Inspect; // change to Inspect mode
                    byteCount = 1; // start the current section at 1 (includes the current byte)
                }
                else if (mode == OperationMode.RawData && previousByte == nextPreviousByte && previousByte == currentByte) // RawData mode: the uncompressible data has ended (compressible data has been found)
                {
                    RLEWriteRawGraphics(ref encodedData, ref byteCompressedCount, data, ref byteUncompressedCount, mask, byteCount - 3); // write the section of raw data
                    mode = OperationMode.Compression; // change to Compression mode
                    byteCount = 3; // start the current section at 3 (includes the current byte, and the previous 2 [i.e. the 3 matching ones])
                }
                // else just read more input data, in whatever mode we are in

                byteCount++; // go to the next byte in the input data

                // Set up the values of the previous few bytes for later comparison
                nextPreviousByte = previousByte;
                previousByte = currentByte;

                if (byteUncompressedCount < maxDataSize)
                    currentByte = data[byteUncompressedCount + byteCount - 1]; // read in the next byte (unless we are at the end of the data)
            }

            Array.Resize(ref encodedData, byteCompressedCount); // truncate encoded data to the correct size

            if (targetSize > 0)
                if (encodedData.Length > targetSize) // check the size of the output data (if requested)
                    Console.WriteLine("Data too large for target size."); // if too big, say so
                else
                    Array.Resize(ref encodedData, targetSize); // if too small, expand encoded data byte array (fill up to the required length with 0x00)

            return encodedData; // return the encoded data
        }

        private void RLEWriteEncodedGraphics(ref byte[] destinationData, ref int destIndex, ref int sourceIndex, byte targetByte, int byteCount)
        {
            // Write a section of encoded graphics data to the byte array

            // Parameters:
            // -----------
            // destinationData - the encoded graphical output
            // destIndex - the current byte to write to (output data)
            // sourceIndex - the current byte of the source decoded data
            // targetByte - the byte of data that will be run-length encoded
            // byteCount - the length of the run-length encoded data (maximum length is 0x7F)

            destinationData[destIndex] = (byte)(byteCount); // write the length of the RLE data (n)
            destinationData[destIndex + 1] = targetByte; // write the byte to duplicate n times (when decoded)
            sourceIndex += byteCount; // increase the index number of the source data by the length of the data just read
            destIndex += 2; // increase the index number of the output data by the length of the data just written
        }

        private void RLEWriteRawGraphics(ref byte[] destinationData, ref int destIndex, byte[] sourceData, ref int sourceIndex, byte mask, int byteCount)
        {
            // Write a section of raw graphics data to the byte array (only sequences of the same byte 3 times [or more] in a row are worth encoding)

            // Parameters:
            // -----------
            // destinationData - the encoded graphical output
            // destIndex - the current byte to write to (output data)
            // sourceData - the raw graphical input
            // sourceIndex - the current byte of the source decoded data
            // mask - the mask to add to the length (byteCount) of the data (this will indicate this is raw data, rather than encoded)
            // byteCount - the length of the run-length encoded data (maximum length is 0x7F)

            destinationData[destIndex] = (byte)(byteCount); // write the length of the raw data
            destinationData[destIndex] += mask; // add mask of 0x80 to the byte just written (the length of the raw data);

            destIndex++; // increase the index number of the output data by the length of the data just written

            for (int j = 0; j < byteCount; j++) // populate the output data with all of the raw bytes
            {
                destinationData[destIndex] = sourceData[sourceIndex]; // write a raw byte from the source data to the output data
                sourceIndex++; // increase the index number of the source data by the length of the data just read
                destIndex++; // increase the index number of the output data by the length of the data just written
            }
        }

        private void RLEWriteEndOfBlock(ref byte[] destinationData, ref int destIndex)
        {
            // A block of data (1 bank of GBC VRAM) is terminated by 0x00, so implement this

            // Parameters:
            // -----------
            // destinationData - the encoded graphical output
            // destIndex - the current byte to write to (output data)

            destinationData[destIndex] = 0x00; // write terminating byte (0x00) to output data
            destIndex++; // increase the index number of the output data by the length of the data just written
        }

        private bool SqueezeDataCheck(int targetSize, int currentSize, int blockSize, int currentByte)
        {
            // Check to see if the rest of the raw input data could be encoded in to the remaining target size of output data

            // Parameters:
            // -----------
            // targetSize - the target size of encoded data (i.e. the size of the existing data in the unmodified ROM)
            // currentSize - the current size of the encoded data
            // blockSize - the length of a block of graphics data (1 bank of VRAM)
            // currentByte - the current byte of the source decoded data

            int squeezeUncompressedLength = 0x7F; // the maximum length of a sequence of data
            int squeezeCompressedLength = 2; // the length of an encoded sequence of data (1 byte from length, 1 byte for the byte to encode)

            int spaceLeft = targetSize - 1 - currentSize - 1; // calculate the amount of space left before the output data would be too big
            int bytesLeft = blockSize - currentByte; // calculate the amount of data remaining in the current block
            float spaceRequired = Math.Max(1, bytesLeft / squeezeUncompressedLength) * squeezeCompressedLength; // calculate how much space is required
            if (spaceRequired > spaceLeft)
            {
                return true; // if the output data is going to be too long, flag this to the calling procedure
            }
            return false;
        }

        private void SqueezeData(ref byte[] data, ref int currentSize, int bytesLeft, ref int currentByte)
        {
            // trash the tiles at the end of the data to squeeze it in to the same space
            // trashing tiles is replacing data at the end of the block with 0xFF (i.e. 2 pixels of color #4) so that it can be encoded to save space
            // information is of course lost, so this is just a quick fix until the data can be remapped in the ROM, or the graphics are edited to compress better.

            // SqueezeDataCheck needs to be run before this to make sure the correct amount of data to trash is identified,
            // and the data that can be saved must have already been written to the output byte array.

            // Parameters:
            // -----------
            // data - the output encoded data
            // currentSize - the current byte to write to (output data) -> passed to/from RLEWriteEncodedGraphics as destIndex
            // bytesLeft - the amount of data that needs to be trashed
            // currentByte - the current byte of the source decoded data -> passed to/from RLEWriteEncodedGraphics as sourceIndex

            int squeezeUncompressedLength = 0x7F; // the maximum length of a sequence of data
            byte blankByte = 0xFF; // the byte to write to replace the trashed graphics data

            int byteCount = 0; // used to count how much more data is left to create

            while (bytesLeft > 0) // write encoded data that fills up the rwquired pixels to complete the current block of data
            {
                if (bytesLeft - squeezeUncompressedLength > 0)
                {
                    // if there is more data than length 0x7F, then write one full sequence of encoded data
                    byteCount = squeezeUncompressedLength;
                    bytesLeft = bytesLeft - squeezeUncompressedLength; // reduce the data left to encode by 0x7F
                }

                else
                {
                    // if there is less data than length 0x7F, then write the remaining sequence of data
                    byteCount = bytesLeft;
                    bytesLeft = 0;
                }
                RLEWriteEncodedGraphics(ref data, ref currentSize, ref currentByte, blankByte, byteCount); // write the requested length of encoded data to the output byte array

            }
        }

    }
}