RunLengthEncoding.cs

Program.cs

using System;
using System.Text;
using System.Diagnostics;

namespace RLE
{
	class Program
	{
		public static string ByteArrayToString(byte[] ba, int len, int offset)
		{
			StringBuilder hex = new StringBuilder(ba.Length * 2);
			for (int ix = offset; ix < offset + len; ix++)
				hex.AppendFormat("{0:X2}", ba[ix]);
			return hex.ToString();
		}

		private static byte[] lhsBytes = new byte[512];
		private static byte[] rhsBytes = new byte[512];
		private static RunLengthEncoding rle = new RunLengthEncoding();


		private static void TestOn(ulong lon)
		{
			byte[] bytes = BitConverter.GetBytes(lon);
			int len = rle.Compress(bytes, 0, bytes.Length, lhsBytes, 0, lhsBytes.Length);
			int outLen = rle.Decompress(lhsBytes, 0, len, rhsBytes, 0, rhsBytes.Length);
			ulong get = BitConverter.ToUInt64(rhsBytes, 0);

			Debug.Assert(bytes.Length == outLen, string.Format("len don't match on: {0}, len: {1}, outLen{2}", lon.ToString("X"), len, outLen));
			Debug.Assert(lon == get, string.Format("value don't match, orig: {0}, get:{1}", lon.ToString("X"), get.ToString("X")));

			return;
		}

		private static void DetailOn(ulong lon)
		{
			RunLengthEncoding rle = new RunLengthEncoding();
			byte[] bytes = BitConverter.GetBytes(lon);

			Console.WriteLine(ByteArrayToString(bytes, bytes.Length, 0));
			int len = rle.Compress(bytes, 0, bytes.Length, lhsBytes, 0, lhsBytes.Length);
			Console.WriteLine("from len: {0} to {1}", bytes.Length, len);
			Console.WriteLine(ByteArrayToString(lhsBytes, len, 0));

			int outLen = rle.Decompress(lhsBytes, 0, len, rhsBytes, 0, rhsBytes.Length);
			Console.WriteLine(ByteArrayToString(rhsBytes, outLen, 0));


			ulong outLon = BitConverter.ToUInt64(rhsBytes, 0);

			Console.WriteLine(lon);
			Console.WriteLine(outLon);
		}


		static void Main(string[] args)
		{

			for (ulong val = uint.MinValue; val <= uint.MaxValue; val += 1)
			{
				if (val % 100000 == 0)
					Console.WriteLine(val);
				TestOn(val);
			}

			/*
			RunLengthEncoding rle = new RunLengthEncoding();
			ulong lon = 0x00000000FF000000;

			Console.WriteLine(ByteArrayToString(bytes, bytes.Length, 0));
			int len = rle.Compress(bytes, 0, bytes.Length, lhsBytes, 0, lhsBytes.Length);
			Console.WriteLine("from len: {0} to {1}", bytes.Length, len);
			Console.WriteLine(ByteArrayToString(lhsBytes, len, 0));

			int outLen = rle.Decompress(lhsBytes, 0, len, rhsBytes, 0, rhsBytes.Length);
			Console.WriteLine(ByteArrayToString(rhsBytes, outLen, 0));


			ulong outLon = BitConverter.ToUInt64(rhsBytes, 0);

			Console.WriteLine(lon);
			Console.WriteLine(outLon);
			*/
		}

	}
}

RunLengthEncoding.cs

using System;

/*
 *	Run Length Encoding
 *	Only run length on 0s
 *	How the fuck there's no implementation on the fucking internet.
 */

//	TODO add a limit to only apply RLE on the first XX bytes, as it just needs to cover
//		 FlatBuffer vtable area
public class RunLengthEncoding
{
	/*	Run Length Indicator, also as escape char	*/
	private const byte RUN_LENGTH_INDICATOR = 0xF5;

	/*	Compress */
	public int Compress(byte[] inputBuffer, int inputOffset, int inputLengh,
						byte[] outputBuffer, int outputOffset, int outputLength)
	{
		// TODO assert outputLenght is twice the input length

		int iix = inputOffset;
		int oix = outputOffset;
		int runLength = 0;

		while (iix < inputLengh)
		{
			if (runLength > 0)
			{
				byte cur = inputBuffer[iix];
				if (cur == 0x0 && runLength < RUN_LENGTH_INDICATOR)
				{
					runLength++;
					iix++;
				}
				else
				{
					outputBuffer[oix++] = (byte)runLength;
					runLength = 0;
				}
			}
			else
			{
				byte cur = inputBuffer[iix];
				if (cur == 0x0)
				{
					byte next = inputBuffer[iix + 1];
					if (iix + 1 < inputLengh && inputBuffer[iix+1] == 0x0)
					{
						outputBuffer[oix++] = RUN_LENGTH_INDICATOR;
						runLength = 2;
						iix += 2;
					}
					else
					{
						// write single 0 and advance
						outputBuffer[oix++] = inputBuffer[iix++];
					}
				}
				else if (cur == RUN_LENGTH_INDICATOR)
				{
					// self escape
					outputBuffer[oix++] = RUN_LENGTH_INDICATOR;
					outputBuffer[oix++] = RUN_LENGTH_INDICATOR;
					iix++;
				}
				else
				{
					outputBuffer[oix++] = inputBuffer[iix++];
				}
			}
		}

		if (runLength > 0)
		{
			outputBuffer[oix++] = (byte)runLength;
		}


		return oix - outputOffset;
	}

	/*	Decompress	*/
	public int Decompress(byte[] inputBuffer, int inputOffset, int inputLength,
						  byte[] outputBuffer, int outputOffset, int outputLength)
	{

		int iix = inputOffset;
		int oix = outputOffset;

		while (iix < inputLength)
		{
			byte cur = inputBuffer[iix];
			if (cur == RUN_LENGTH_INDICATOR)
			{
				byte next = inputBuffer[iix + 1];
				// TODO handle dry out
				if (next == RUN_LENGTH_INDICATOR)
				{
					// it's a escape
					outputBuffer[oix++] = RUN_LENGTH_INDICATOR;
					iix += 2;
				}
				else
				{
					// expand zeros
					while (next-- > 0)
					{
						outputBuffer[oix++] = 0x0;
					}
					// move on
					iix += 2;
				}
			}
			else
			{
				outputBuffer[oix++] = inputBuffer[iix++]; 
			}

		}

		return oix - outputOffset;
	}


}