Guest User

Tetris DX RLE encode/decode example

a guest
May 6th, 2020
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // RLE.cs - Tetris DX RLE encode/decode (example) - Ed Kearney
  2.  
  3. using System;
  4.  
  5. namespace TetrisDx_RLE_encode_decode
  6. {
  7.     public class RLE
  8.     {
  9.         private enum OperationMode { Compression, RawData, Inspect } // When encoding data, there are 3 modes of operation when analysing the raw data...
  10.        
  11.         // Encoding Operation modes:
  12.         // -------------------------
  13.         // Inspect mode -     Read the data to see if it can be Compressed or not, either enters RawData or Compression modes depending on
  14.         //                    if it reads two different bytes (enters RawData mode), or 3 matching bytes (enters Compression mode)
  15.         // Compression mode - it keeps reading until it finds the end of a block, then end of the input data, or a different input byte,
  16.         //                    then it writes the compressed data and changes to the correct mode
  17.         // 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,
  18.         //                    then it writes the compressed data and changes to the correct mode
  19.  
  20.         public byte[] RLEDecodeGraphics(byte[] data, int numBlocks = 0, int numTiles = 0, int startTileIndex = 0)
  21.         {
  22.             // Decode a byte array according to the following table.
  23.             // Note: Valid data must be found at array index 0.
  24.  
  25.             // Value    Meaning
  26.             // -----    ----------------------------------------------------------
  27.             // 00       End of data.
  28.             // 01 - 7F  Read another byte, and write it to the output n times.
  29.             // 80       Invalid.
  30.             // 81 - FF  Copy n -128 bytes from input to output.
  31.  
  32.             // Parameters:
  33.             // -----------
  34.             // data - the input encoded data
  35.             // numBlocks - the number of blocks to decode (default is 0, which means unlimited)
  36.             // numTiles - the number of tiles to decode (default is 0, which means unlimited) [not implemented]
  37.             // startTileIndex - the tile to start outputting from  (default is 0, which means the first) [not implemented]
  38.  
  39.             int blockCount = 0; // count the number of blocks, so that data can be limited in parameters
  40.             // int tileCount = 0;  // count the number of tiles, so that data can be limited in parameters [not implemented]
  41.  
  42.             int startingSize = 10000000; // maximum size of encoded data (truncated later) [there are probably better ways to do this]
  43.             byte[] decodedData = new byte[startingSize]; // create a dummy byte array, that will be written to, based on the input encoded data
  44.  
  45.             byte mask = 0x80; // + 128 bytes - this indicates that the encoded data is a sequence of raw data
  46.  
  47.             int dataLength = 0; // length of data to process
  48.             byte packedCharacter = 0x00; // currect character to output n times.
  49.             int byteCompressedCount = 0; // how far through the encoded data are we?
  50.             int byteUncompressedCount = 0; // how large has the decoded data become?
  51.  
  52.  
  53.             while (byteCompressedCount < data.Length) // go through all the input data
  54.             {
  55.                 dataLength = data[byteCompressedCount]; // get current byte (the length of the following data)
  56.  
  57.                 if (dataLength == 0x00) // end of data block
  58.                 {
  59.                     byteCompressedCount += 1; // skip to next block if available, otherwise ends while loop (for valid data).
  60.  
  61.                     blockCount++; // increase the count of the number of blocks of data
  62.  
  63.                     if (numBlocks != 0 && blockCount == numBlocks) // if the intended number of blocks is reached
  64.                     {
  65.                         byteCompressedCount = data.Length; // exit the while loop
  66.                     }
  67.                 }
  68.                 else if (dataLength > 0x80) // a block of raw (decoded) data follows
  69.                 {
  70.                     byteCompressedCount += 1; // move to data
  71.  
  72.                     dataLength = dataLength & ~mask; // (length n - 128)
  73.  
  74.                     for (int j = 0; j < dataLength; j++) // populate the decoded data array
  75.                     {
  76.                         if (byteCompressedCount < data.Length) // if the end of the data has not been reached
  77.                         {
  78.                             decodedData[byteUncompressedCount] = data[byteCompressedCount]; // decode a byte of data
  79.                             byteUncompressedCount++; // increase the index number of the output data by the length of the data just written
  80.                             byteCompressedCount++; // increase the index number of the source data by the length of the data just read
  81.                         }
  82.                     }
  83.                 }
  84.                 else if (dataLength < 0x80) // copy the following byte dataLength times
  85.                 {
  86.                     packedCharacter = data[byteCompressedCount + 1]; // get target byte to write
  87.  
  88.                     for (int j = 0; j < dataLength; j++) // populate the decoded data array dataLength times
  89.                     {
  90.                         decodedData[byteUncompressedCount] = packedCharacter; // write the target byte
  91.                         byteUncompressedCount++; // increase the index number of the output data by the length of the data just written
  92.                     }
  93.  
  94.                     byteCompressedCount += 2; // increase the index number of the source data by the length of the data just read
  95.                 }
  96.                 else
  97.                 {
  98.                     //dataLength == 0x80 - do nothing...
  99.                 }
  100.  
  101.             }
  102.             Array.Resize(ref decodedData, byteUncompressedCount); // truncate decoded data to the correct length
  103.  
  104.             return decodedData; // return the decoded data
  105.         }
  106.  
  107.         public byte[] RLEEncodeGraphics(byte[] data, int blockSize = 0, int targetSize = 0, int blockCount = 0, bool squeezeMode = false)
  108.         {
  109.             // Encode a byte array according to the following table.
  110.             // Note: Valid data must be found at array index 0.
  111.  
  112.             // Value    Meaning
  113.             // -----    ----------------------------------------------------------
  114.             // 00       End of data.
  115.             // 01 - 7F  Read another byte, and write it to the output n times.
  116.             // 80       Invalid.
  117.             // 81 - FF  Copy n -128 bytes from input to output.
  118.  
  119.             // Parameters:
  120.             // -----------
  121.             // data - the input decoded/raw data
  122.             // 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)
  123.             // 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)
  124.             // blockCount - the number of blocks to encode (default is 0, which means unlimited/all)
  125.             // 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)
  126.             // NOTE: squeezeMode requires blockSize, targetSize, and blockCount to be set
  127.  
  128.  
  129.             int startingSize = 10000000; // maximum size of encoded data (truncated later) [there are probably better ways to do this]
  130.  
  131.             byte[] encodedData = new byte[startingSize]; // create a dummy byte array, that will be written to, based on the input decoded data
  132.  
  133.             byte mask = 0x80; // + 128 bytes - this indicates that the encoded data is a sequence of raw data
  134.  
  135.             byte currentByte = 0x00, previousByte = 0x00, nextPreviousByte = 0x00;
  136.  
  137.             int byteCount = 0; // count the number of blocks, so that data can be limited in parameters
  138.  
  139.             int byteCompressedCount = 0; // how large has the encoded data gotten?
  140.             int byteUncompressedCount = 0; // how far through the decoded data are we?
  141.  
  142.             bool blockEnd = false; // flags if we need to handle the end of a block
  143.             bool squeezeData = false; // flags if we need to squuze the rest of the data
  144.  
  145.             OperationMode mode = OperationMode.Inspect; // start out in Inspect Mode
  146.  
  147.             // Limit the input data size to be the number of blocks specified (otherwise unlimited/startingSize)
  148.             int maxDataSize = data.Length;
  149.             if (blockCount != 0)
  150.                 maxDataSize = blockCount * blockSize;
  151.  
  152.             while ((byteUncompressedCount + byteCount) <= maxDataSize)
  153.             {
  154.                 // process all of the raw input data, until the end of it, or until the requested amount of blocks has been reached
  155.                 // this is *less than OR equals to* so that the end of a block can be correctly processed.
  156.  
  157.                 if (blockSize > 0 && (byteUncompressedCount + byteCount) > 0 && (byteUncompressedCount + byteCount) % blockSize == 0)
  158.                 {
  159.                     blockEnd = true; // If a block size has been specified, and we are at the end of a block, flag it
  160.                 }
  161.                 else if (squeezeMode) // If the data has to fit within the target size (no matter what)
  162.                 {
  163.                     // get the size of the encoded output data
  164.                     int currentSize = byteCompressedCount;
  165.                     if (mode == OperationMode.Compression)
  166.                         currentSize += 2;
  167.                     else
  168.                         currentSize += byteCount;
  169.  
  170.                     // Check the remaining space (allotted by the targetSize)
  171.                     if (SqueezeDataCheck(targetSize, currentSize, blockSize, byteUncompressedCount + byteCount - 1))
  172.                     {
  173.                         // 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
  174.                         byteCount -= 1; // we can't actually write the current byte, so move back a step
  175.                         squeezeData = true;
  176.                     }
  177.                 }
  178.  
  179.                 //default mode is "Inspect mode" - look for potential blocks of data, starting from the last position of unknown input data
  180.  
  181.                 if (squeezeData || blockEnd || byteCount == 0x7F) // 1st check - do we need to write the current section of data due to a limit?
  182.                 {
  183.                     // Limits:
  184.                     // -------
  185.                     // 1: Data needs to be squuezed (developer function)
  186.                     // 2: The end of a block has been reached
  187.                     // 3: The current section has reached a length of 0x7F (the maximum length of a section)
  188.  
  189.                     if (mode == OperationMode.Inspect) mode = OperationMode.RawData; // shouldn't be needed, but just in case
  190.  
  191.                     if (byteCount > 0) // If there is data to write, write it
  192.                     {
  193.                         if (mode == OperationMode.Compression)
  194.                             RLEWriteEncodedGraphics(ref encodedData, ref byteCompressedCount, ref byteUncompressedCount, previousByte, byteCount);
  195.                         else
  196.                             RLEWriteRawGraphics(ref encodedData, ref byteCompressedCount, data, ref byteUncompressedCount, mask, byteCount);
  197.                     }
  198.                     byteCount = 0; // reset the the index of the current section
  199.  
  200.                     if (squeezeData) // Squeeze the data if needed
  201.                     {
  202.                         SqueezeData(ref encodedData, ref byteCompressedCount, blockSize - byteUncompressedCount, ref byteUncompressedCount);
  203.                         squeezeData = false; // turn the flag off
  204.                         blockEnd = true; // make sure the end of the block indicator is added
  205.                         byteUncompressedCount++; //hack!!!!!
  206.                     }
  207.  
  208.                     if (blockEnd) // add the end of a block indicator (if needed)
  209.                     {
  210.                         RLEWriteEndOfBlock(ref encodedData, ref byteCompressedCount);
  211.                         blockCount++; // increase the count of blocks by 1
  212.                         blockEnd = false; // turn the flag off
  213.                     }
  214.    
  215.                     mode = OperationMode.Inspect; // revert to Inspect mode, in case there is more data to process after this
  216.                 }
  217.                 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
  218.                 {
  219.                     if (currentByte != previousByte) // if the current byte is different to the previous one, then treat this section as raw data (and enter RawData mode)
  220.                         mode = OperationMode.RawData;
  221.                     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)
  222.                         mode = OperationMode.Compression;
  223.                     // else stay in Inspect mode
  224.                 }
  225.                 else if (mode == OperationMode.Compression && currentByte != previousByte) //  Compression mode: the compressible data has ended (a non-matching byte has been found)
  226.                 {
  227.                     RLEWriteEncodedGraphics(ref encodedData, ref byteCompressedCount, ref byteUncompressedCount, previousByte, byteCount - 1); // write the section of compressed data
  228.                     mode = OperationMode.Inspect; // change to Inspect mode
  229.                     byteCount = 1; // start the current section at 1 (includes the current byte)
  230.                 }
  231.                 else if (mode == OperationMode.RawData && previousByte == nextPreviousByte && previousByte == currentByte) // RawData mode: the uncompressible data has ended (compressible data has been found)
  232.                 {
  233.                     RLEWriteRawGraphics(ref encodedData, ref byteCompressedCount, data, ref byteUncompressedCount, mask, byteCount - 3); // write the section of raw data
  234.                     mode = OperationMode.Compression; // change to Compression mode
  235.                     byteCount = 3; // start the current section at 3 (includes the current byte, and the previous 2 [i.e. the 3 matching ones])
  236.                 }
  237.                 // else just read more input data, in whatever mode we are in
  238.  
  239.                 byteCount++; // go to the next byte in the input data
  240.  
  241.                 // Set up the values of the previous few bytes for later comparison
  242.                 nextPreviousByte = previousByte;
  243.                 previousByte = currentByte;
  244.  
  245.                 if (byteUncompressedCount < maxDataSize)
  246.                     currentByte = data[byteUncompressedCount + byteCount - 1]; // read in the next byte (unless we are at the end of the data)      
  247.             }
  248.  
  249.             Array.Resize(ref encodedData, byteCompressedCount); // truncate encoded data to the correct size
  250.  
  251.             if (targetSize > 0)
  252.                 if (encodedData.Length > targetSize) // check the size of the output data (if requested)
  253.                     Console.WriteLine("Data too large for target size."); // if too big, say so
  254.                 else
  255.                     Array.Resize(ref encodedData, targetSize); // if too small, expand encoded data byte array (fill up to the required length with 0x00)
  256.  
  257.             return encodedData; // return the encoded data
  258.         }
  259.  
  260.         private void RLEWriteEncodedGraphics(ref byte[] destinationData, ref int destIndex, ref int sourceIndex, byte targetByte, int byteCount)
  261.         {
  262.             // Write a section of encoded graphics data to the byte array
  263.  
  264.             // Parameters:
  265.             // -----------
  266.             // destinationData - the encoded graphical output
  267.             // destIndex - the current byte to write to (output data)
  268.             // sourceIndex - the current byte of the source decoded data
  269.             // targetByte - the byte of data that will be run-length encoded
  270.             // byteCount - the length of the run-length encoded data (maximum length is 0x7F)
  271.  
  272.             destinationData[destIndex] = (byte)(byteCount); // write the length of the RLE data (n)
  273.             destinationData[destIndex + 1] = targetByte; // write the byte to duplicate n times (when decoded)
  274.             sourceIndex += byteCount; // increase the index number of the source data by the length of the data just read
  275.             destIndex += 2; // increase the index number of the output data by the length of the data just written
  276.         }
  277.  
  278.         private void RLEWriteRawGraphics(ref byte[] destinationData, ref int destIndex, byte[] sourceData, ref int sourceIndex, byte mask, int byteCount)
  279.         {
  280.             // 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)
  281.  
  282.             // Parameters:
  283.             // -----------
  284.             // destinationData - the encoded graphical output
  285.             // destIndex - the current byte to write to (output data)
  286.             // sourceData - the raw graphical input
  287.             // sourceIndex - the current byte of the source decoded data
  288.             // mask - the mask to add to the length (byteCount) of the data (this will indicate this is raw data, rather than encoded)
  289.             // byteCount - the length of the run-length encoded data (maximum length is 0x7F)
  290.  
  291.             destinationData[destIndex] = (byte)(byteCount); // write the length of the raw data
  292.             destinationData[destIndex] += mask; // add mask of 0x80 to the byte just written (the length of the raw data);
  293.  
  294.             destIndex++; // increase the index number of the output data by the length of the data just written
  295.  
  296.             for (int j = 0; j < byteCount; j++) // populate the output data with all of the raw bytes
  297.             {
  298.                 destinationData[destIndex] = sourceData[sourceIndex]; // write a raw byte from the source data to the output data
  299.                 sourceIndex++; // increase the index number of the source data by the length of the data just read
  300.                 destIndex++; // increase the index number of the output data by the length of the data just written
  301.             }
  302.         }
  303.  
  304.         private void RLEWriteEndOfBlock(ref byte[] destinationData, ref int destIndex)
  305.         {
  306.             // A block of data (1 bank of GBC VRAM) is terminated by 0x00, so implement this
  307.  
  308.             // Parameters:
  309.             // -----------
  310.             // destinationData - the encoded graphical output
  311.             // destIndex - the current byte to write to (output data)
  312.  
  313.             destinationData[destIndex] = 0x00; // write terminating byte (0x00) to output data
  314.             destIndex++; // increase the index number of the output data by the length of the data just written
  315.         }
  316.  
  317.         private bool SqueezeDataCheck(int targetSize, int currentSize, int blockSize, int currentByte)
  318.         {
  319.             // Check to see if the rest of the raw input data could be encoded in to the remaining target size of output data
  320.  
  321.             // Parameters:
  322.             // -----------
  323.             // targetSize - the target size of encoded data (i.e. the size of the existing data in the unmodified ROM)
  324.             // currentSize - the current size of the encoded data
  325.             // blockSize - the length of a block of graphics data (1 bank of VRAM)
  326.             // currentByte - the current byte of the source decoded data
  327.  
  328.             int squeezeUncompressedLength = 0x7F; // the maximum length of a sequence of data
  329.             int squeezeCompressedLength = 2; // the length of an encoded sequence of data (1 byte from length, 1 byte for the byte to encode)
  330.  
  331.             int spaceLeft = targetSize - 1 - currentSize - 1; // calculate the amount of space left before the output data would be too big
  332.             int bytesLeft = blockSize - currentByte; // calculate the amount of data remaining in the current block
  333.             float spaceRequired = Math.Max(1, bytesLeft / squeezeUncompressedLength) * squeezeCompressedLength; // calculate how much space is required
  334.             if (spaceRequired > spaceLeft)
  335.             {
  336.                 return true; // if the output data is going to be too long, flag this to the calling procedure
  337.             }
  338.             return false;
  339.         }
  340.  
  341.         private void SqueezeData(ref byte[] data, ref int currentSize, int bytesLeft, ref int currentByte)
  342.         {
  343.             // trash the tiles at the end of the data to squeeze it in to the same space
  344.             // 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
  345.             // 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.
  346.  
  347.             // SqueezeDataCheck needs to be run before this to make sure the correct amount of data to trash is identified,
  348.             // and the data that can be saved must have already been written to the output byte array.
  349.  
  350.             // Parameters:
  351.             // -----------
  352.             // data - the output encoded data
  353.             // currentSize - the current byte to write to (output data) -> passed to/from RLEWriteEncodedGraphics as destIndex
  354.             // bytesLeft - the amount of data that needs to be trashed
  355.             // currentByte - the current byte of the source decoded data -> passed to/from RLEWriteEncodedGraphics as sourceIndex
  356.  
  357.             int squeezeUncompressedLength = 0x7F; // the maximum length of a sequence of data
  358.             byte blankByte = 0xFF; // the byte to write to replace the trashed graphics data
  359.  
  360.             int byteCount = 0; // used to count how much more data is left to create
  361.  
  362.             while (bytesLeft > 0) // write encoded data that fills up the rwquired pixels to complete the current block of data
  363.             {
  364.                 if (bytesLeft - squeezeUncompressedLength > 0)
  365.                 {
  366.                     // if there is more data than length 0x7F, then write one full sequence of encoded data
  367.                     byteCount = squeezeUncompressedLength;
  368.                     bytesLeft = bytesLeft - squeezeUncompressedLength; // reduce the data left to encode by 0x7F
  369.                 }
  370.  
  371.                 else
  372.                 {
  373.                     // if there is less data than length 0x7F, then write the remaining sequence of data
  374.                     byteCount = bytesLeft;
  375.                     bytesLeft = 0;
  376.                 }
  377.                 RLEWriteEncodedGraphics(ref data, ref currentSize, ref currentByte, blankByte, byteCount); // write the requested length of encoded data to the output byte array
  378.  
  379.             }
  380.         }
  381.  
  382.     }
  383. }
RAW Paste Data Copied