LZ77 Compression Algorithm<\/p>\n\n\n\n
using System;\nusing System.Collections.Generic;\nusing System.IO;\nusing System.Linq;\npublic static class Lz77\n{\n private const int RingBufferSize = 1024 * 4;\n private const int UpperMatchLength = 18;\n private const int LowerMatchLength = 3;\n private const int None = RingBufferSize;\n private static readonly int[] Parent = new int[RingBufferSize + 1];\n private static readonly int[] LeftChild = new int[RingBufferSize + 1];\n private static readonly int[] RightChild = new int[RingBufferSize + 257];\n private static readonly ushort[] Buffer = new ushort[RingBufferSize + UpperMatchLength - 1];\n private static int matchPosition, matchLength;\n \/\/\/ <summary>\n \/\/\/ Size of the compressed code during and after compression\n \/\/\/ <\/summary>\n public static int CompressedSize\n {\n get;\n set;\n }\n \/\/\/ <summary>\n \/\/\/ Size of the original code packet while decompressing\n \/\/\/ <\/summary>\n public static int DeCompressedSize\n {\n get;\n set;\n }\n public static double Ratio => (double) CompressedSize \/ DeCompressedSize * 100.0;\n public static byte[] Lz77Decompress(this byte[] ins)\n {\n if (ins == null)\n throw new Exception(\"Input buffer is null.\");\n if (ins.Length == 0)\n throw new Exception(\"Input buffer is empty.\");\n var outa = new GArray<byte>();\n var ina = new GArray<byte>(ins);\n CompressedSize = 0;\n DeCompressedSize = ina.Read(4).ToInt();\n for (var i = 0; i < RingBufferSize - UpperMatchLength; i++)\n Buffer[i] = 0;\n var r = RingBufferSize - UpperMatchLength;\n uint flags = 7;\n var z = 7;\n while (true)\n {\n flags <<= 1;\n z++;\n if (z == 8)\n {\n if (ina.ReadEnd)\n break;\n flags = ina.Read();\n z = 0;\n }\n if ((flags & 0x80) == 0)\n {\n if (ina.ReadEnd)\n break;\n var c = ina.Read();\n if (CompressedSize < DeCompressedSize)\n outa.Write(c);\n Buffer[r++] = c;\n r &= RingBufferSize - 1;\n CompressedSize++;\n }\n else\n {\n if (ina.ReadEnd)\n break;\n int i = ina.Read();\n if (ina.ReadEnd)\n break;\n int j = ina.Read();\n j = j | ((i << 8) & 0xF00);\n i = ((i >> 4) & 0xF) + LowerMatchLength;\n for (var k = 0; k <= i; k++)\n {\n var c = Buffer[(r - j - 1) & (RingBufferSize - 1)];\n if (CompressedSize < DeCompressedSize)\n outa.Write((byte) c);\n Buffer[r++] = (byte) c;\n r &= RingBufferSize - 1;\n CompressedSize++;\n }\n }\n }\n return outa.ToArray();\n }\n \/\/\/ <summary>\n \/\/\/ E:12.5, R:17.3 E:25.0, R:35.9 E:32.3, R:47.7 E:37.5, R:56.5 E:41.5, R:63.0 E:44.8, R:67.6 E:47.6, R:71.7 E:50.0,\n \/\/\/ R:75.8 E:52.1, R:79.9 E:54.0, R:83.9 E:55.7, R:87.7\n \/\/\/ E:57.3, R:91.0 E:58.8, R:93.9 E:60.1, R:96.6 E:61.3, R:98.8 E:62.5, R:100.6 E:63.6, R:102.1 E:64.6, R:103.5 E:65.6,\n \/\/\/ R:104.7 E:66.5, R:105.6 E:67.4, R:106.5\n \/\/\/ E:68.2, R:107.2 E:69.0, R:107.8 E:69.8, R:108.3 E:70.5, R:108.7\n \/\/\/ <\/summary>\n public static byte[] Lz77Compress(this byte[] ins, bool TestForCompressibility = false)\n {\n if (ins == null)\n throw new Exception(\"Input buffer is null.\");\n if (ins.Length == 0)\n throw new Exception(\"Input buffer is empty.\");\n if (TestForCompressibility)\n if ((int) Entropy(ins) > 61)\n throw new Exception(\"Input buffer Cannot be compressed.\");\n matchLength = 0;\n matchPosition = 0;\n CompressedSize = 0;\n DeCompressedSize = ins.Length;\n int length;\n var codeBuffer = new int[UpperMatchLength - 1];\n var outa = new GArray<byte>();\n var ina = new GArray<byte>(ins);\n outa.Write(DeCompressedSize.GetBytes(0, 4));\n InitTree();\n codeBuffer[0] = 0;\n var codeBufferPointer = 1;\n var mask = 0x80;\n var s = 0;\n var r = RingBufferSize - UpperMatchLength;\n for (var i = s; i < r; i++)\n Buffer[i] = 0xFFFF;\n for (length = 0; length < UpperMatchLength && !ina.ReadEnd; length++)\n Buffer[r + length] = ina.Read();\n if (length == 0)\n throw new Exception(\"No Data to Compress.\");\n for (var i = 1; i <= UpperMatchLength; i++)\n InsertNode(r - i);\n InsertNode(r);\n do\n {\n if (matchLength > length)\n matchLength = length;\n if (matchLength <= LowerMatchLength)\n {\n matchLength = 1;\n codeBuffer[codeBufferPointer++] = Buffer[r];\n }\n else\n {\n codeBuffer[0] |= mask;\n codeBuffer[codeBufferPointer++] = (byte) (((r - matchPosition - 1) >> 8) & 0xF) | ((matchLength - (LowerMatchLength + 1)) << 4);\n codeBuffer[codeBufferPointer++] = (byte) ((r - matchPosition - 1) & 0xFF);\n }\n if ((mask >>= 1) == 0)\n {\n for (var i = 0; i < codeBufferPointer; i++)\n outa.Write((byte) codeBuffer[i]);\n CompressedSize += codeBufferPointer;\n codeBuffer[0] = 0;\n codeBufferPointer = 1;\n mask = 0x80;\n }\n var lastMatchLength = matchLength;\n var ii = 0;\n for (ii = 0; ii < lastMatchLength && !ina.ReadEnd; ii++)\n {\n DeleteNode(s);\n var c = ina.Read();\n Buffer[s] = c;\n if (s < UpperMatchLength - 1)\n Buffer[s + RingBufferSize] = c;\n s = (s + 1) & (RingBufferSize - 1);\n r = (r + 1) & (RingBufferSize - 1);\n InsertNode(r);\n }\n while (ii++ < lastMatchLength)\n {\n DeleteNode(s);\n s = (s + 1) & (RingBufferSize - 1);\n r = (r + 1) & (RingBufferSize - 1);\n if (--length != 0)\n InsertNode(r);\n }\n } while (length > 0);\n if (codeBufferPointer > 1)\n {\n for (var i = 0; i < codeBufferPointer; i++)\n outa.Write((byte) codeBuffer[i]);\n CompressedSize += codeBufferPointer;\n }\n if (CompressedSize % 4 != 0)\n for (var i = 0; i < 4 - CompressedSize % 4; i++)\n outa.Write(0);\n return outa.ToArray();\n }\n private static void InitTree()\n {\n for (var i = RingBufferSize + 1; i <= RingBufferSize + 256; i++)\n RightChild[i] = None;\n for (var i = 0; i < RingBufferSize; i++)\n Parent[i] = None;\n }\n private static void InsertNode(int r)\n {\n var cmp = 1;\n var p = RingBufferSize + 1 + (Buffer[r] == 0xFFFF ? 0 : Buffer[r]);\n RightChild[r] = LeftChild[r] = None;\n matchLength = 0;\n while (true)\n {\n if (cmp >= 0)\n {\n if (RightChild[p] != None)\n {\n p = RightChild[p];\n }\n else\n {\n RightChild[p] = r;\n Parent[r] = p;\n return;\n }\n }\n else\n {\n if (LeftChild[p] != None)\n {\n p = LeftChild[p];\n }\n else\n {\n LeftChild[p] = r;\n Parent[r] = p;\n return;\n }\n }\n int i;\n for (i = 1; i < UpperMatchLength; i++)\n if ((cmp = Buffer[r + i] - Buffer[p + i]) != 0)\n break;\n if (i > matchLength)\n {\n matchPosition = p;\n if ((matchLength = i) >= UpperMatchLength)\n break;\n }\n }\n Parent[r] = Parent[p];\n LeftChild[r] = LeftChild[p];\n RightChild[r] = RightChild[p];\n Parent[LeftChild[p]] = r;\n Parent[RightChild[p]] = r;\n if (RightChild[Parent[p]] == p)\n RightChild[Parent[p]] = r;\n else LeftChild[Parent[p]] = r;\n Parent[p] = None;\n }\n private static void DeleteNode(int p)\n {\n int q;\n if (Parent[p] == None)\n return;\n if (RightChild[p] == None)\n {\n q = LeftChild[p];\n }\n else if (LeftChild[p] == None)\n {\n q = RightChild[p];\n }\n else\n {\n q = LeftChild[p];\n if (RightChild[q] != None)\n {\n do\n {\n q = RightChild[q];\n } while (RightChild[q] != None);\n RightChild[Parent[q]] = LeftChild[q];\n Parent[LeftChild[q]] = Parent[q];\n LeftChild[q] = LeftChild[p];\n Parent[LeftChild[p]] = q;\n }\n RightChild[q] = RightChild[p];\n Parent[RightChild[p]] = q;\n }\n Parent[q] = Parent[p];\n if (RightChild[Parent[p]] == p)\n RightChild[Parent[p]] = q;\n else LeftChild[Parent[p]] = q;\n Parent[p] = None;\n }\n private static double Entropy(byte[] ba)\n {\n var map = new Dictionary<byte, int>();\n foreach (var c in ba)\n if (!map.ContainsKey(c))\n map.Add(c, 1);\n else\n map[c]++;\n double Len = ba.Length;\n var re = map.Select(item => item.Value \/ Len).Aggregate(0.0, (current, frequency) => current - frequency * (Math.Log(frequency) \/ Math.Log(2)));\n return re \/ 8.00D * 100D;\n }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"LZ77 Compression Algorithm<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/44"}],"collection":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/comments?post=44"}],"version-history":[{"count":1,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/44\/revisions"}],"predecessor-version":[{"id":45,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/44\/revisions\/45"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=44"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=44"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=44"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}