LZ77 Compression Algorithm
using System; using System.Collections.Generic; using System.IO; using System.Linq; public static class Lz77 { private const int RingBufferSize = 1024 * 4; private const int UpperMatchLength = 18; private const int LowerMatchLength = 3; private const int None = RingBufferSize; private static readonly int[] Parent = new int[RingBufferSize + 1]; private static readonly int[] LeftChild = new int[RingBufferSize + 1]; private static readonly int[] RightChild = new int[RingBufferSize + 257]; private static readonly ushort[] Buffer = new ushort[RingBufferSize + UpperMatchLength - 1]; private static int matchPosition, matchLength; /// <summary> /// Size of the compressed code during and after compression /// </summary> public static int CompressedSize { get; set; } /// <summary> /// Size of the original code packet while decompressing /// </summary> public static int DeCompressedSize { get; set; } public static double Ratio => (double) CompressedSize / DeCompressedSize * 100.0; public static byte[] Lz77Decompress(this byte[] ins) { if (ins == null) throw new Exception("Input buffer is null."); if (ins.Length == 0) throw new Exception("Input buffer is empty."); var outa = new GArray<byte>(); var ina = new GArray<byte>(ins); CompressedSize = 0; DeCompressedSize = ina.Read(4).ToInt(); for (var i = 0; i < RingBufferSize - UpperMatchLength; i++) Buffer[i] = 0; var r = RingBufferSize - UpperMatchLength; uint flags = 7; var z = 7; while (true) { flags <<= 1; z++; if (z == 8) { if (ina.ReadEnd) break; flags = ina.Read(); z = 0; } if ((flags & 0x80) == 0) { if (ina.ReadEnd) break; var c = ina.Read(); if (CompressedSize < DeCompressedSize) outa.Write(c); Buffer[r++] = c; r &= RingBufferSize - 1; CompressedSize++; } else { if (ina.ReadEnd) break; int i = ina.Read(); if (ina.ReadEnd) break; int j = ina.Read(); j = j | ((i << 8) & 0xF00); i = ((i >> 4) & 0xF) + LowerMatchLength; for (var k = 0; k <= i; k++) { var c = Buffer[(r - j - 1) & (RingBufferSize - 1)]; if (CompressedSize < DeCompressedSize) outa.Write((byte) c); Buffer[r++] = (byte) c; r &= RingBufferSize - 1; CompressedSize++; } } } return outa.ToArray(); } /// <summary> /// 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, /// R:75.8 E:52.1, R:79.9 E:54.0, R:83.9 E:55.7, R:87.7 /// 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, /// R:104.7 E:66.5, R:105.6 E:67.4, R:106.5 /// E:68.2, R:107.2 E:69.0, R:107.8 E:69.8, R:108.3 E:70.5, R:108.7 /// </summary> public static byte[] Lz77Compress(this byte[] ins, bool TestForCompressibility = false) { if (ins == null) throw new Exception("Input buffer is null."); if (ins.Length == 0) throw new Exception("Input buffer is empty."); if (TestForCompressibility) if ((int) Entropy(ins) > 61) throw new Exception("Input buffer Cannot be compressed."); matchLength = 0; matchPosition = 0; CompressedSize = 0; DeCompressedSize = ins.Length; int length; var codeBuffer = new int[UpperMatchLength - 1]; var outa = new GArray<byte>(); var ina = new GArray<byte>(ins); outa.Write(DeCompressedSize.GetBytes(0, 4)); InitTree(); codeBuffer[0] = 0; var codeBufferPointer = 1; var mask = 0x80; var s = 0; var r = RingBufferSize - UpperMatchLength; for (var i = s; i < r; i++) Buffer[i] = 0xFFFF; for (length = 0; length < UpperMatchLength && !ina.ReadEnd; length++) Buffer[r + length] = ina.Read(); if (length == 0) throw new Exception("No Data to Compress."); for (var i = 1; i <= UpperMatchLength; i++) InsertNode(r - i); InsertNode(r); do { if (matchLength > length) matchLength = length; if (matchLength <= LowerMatchLength) { matchLength = 1; codeBuffer[codeBufferPointer++] = Buffer[r]; } else { codeBuffer[0] |= mask; codeBuffer[codeBufferPointer++] = (byte) (((r - matchPosition - 1) >> 8) & 0xF) | ((matchLength - (LowerMatchLength + 1)) << 4); codeBuffer[codeBufferPointer++] = (byte) ((r - matchPosition - 1) & 0xFF); } if ((mask >>= 1) == 0) { for (var i = 0; i < codeBufferPointer; i++) outa.Write((byte) codeBuffer[i]); CompressedSize += codeBufferPointer; codeBuffer[0] = 0; codeBufferPointer = 1; mask = 0x80; } var lastMatchLength = matchLength; var ii = 0; for (ii = 0; ii < lastMatchLength && !ina.ReadEnd; ii++) { DeleteNode(s); var c = ina.Read(); Buffer[s] = c; if (s < UpperMatchLength - 1) Buffer[s + RingBufferSize] = c; s = (s + 1) & (RingBufferSize - 1); r = (r + 1) & (RingBufferSize - 1); InsertNode(r); } while (ii++ < lastMatchLength) { DeleteNode(s); s = (s + 1) & (RingBufferSize - 1); r = (r + 1) & (RingBufferSize - 1); if (--length != 0) InsertNode(r); } } while (length > 0); if (codeBufferPointer > 1) { for (var i = 0; i < codeBufferPointer; i++) outa.Write((byte) codeBuffer[i]); CompressedSize += codeBufferPointer; } if (CompressedSize % 4 != 0) for (var i = 0; i < 4 - CompressedSize % 4; i++) outa.Write(0); return outa.ToArray(); } private static void InitTree() { for (var i = RingBufferSize + 1; i <= RingBufferSize + 256; i++) RightChild[i] = None; for (var i = 0; i < RingBufferSize; i++) Parent[i] = None; } private static void InsertNode(int r) { var cmp = 1; var p = RingBufferSize + 1 + (Buffer[r] == 0xFFFF ? 0 : Buffer[r]); RightChild[r] = LeftChild[r] = None; matchLength = 0; while (true) { if (cmp >= 0) { if (RightChild[p] != None) { p = RightChild[p]; } else { RightChild[p] = r; Parent[r] = p; return; } } else { if (LeftChild[p] != None) { p = LeftChild[p]; } else { LeftChild[p] = r; Parent[r] = p; return; } } int i; for (i = 1; i < UpperMatchLength; i++) if ((cmp = Buffer[r + i] - Buffer[p + i]) != 0) break; if (i > matchLength) { matchPosition = p; if ((matchLength = i) >= UpperMatchLength) break; } } Parent[r] = Parent[p]; LeftChild[r] = LeftChild[p]; RightChild[r] = RightChild[p]; Parent[LeftChild[p]] = r; Parent[RightChild[p]] = r; if (RightChild[Parent[p]] == p) RightChild[Parent[p]] = r; else LeftChild[Parent[p]] = r; Parent[p] = None; } private static void DeleteNode(int p) { int q; if (Parent[p] == None) return; if (RightChild[p] == None) { q = LeftChild[p]; } else if (LeftChild[p] == None) { q = RightChild[p]; } else { q = LeftChild[p]; if (RightChild[q] != None) { do { q = RightChild[q]; } while (RightChild[q] != None); RightChild[Parent[q]] = LeftChild[q]; Parent[LeftChild[q]] = Parent[q]; LeftChild[q] = LeftChild[p]; Parent[LeftChild[p]] = q; } RightChild[q] = RightChild[p]; Parent[RightChild[p]] = q; } Parent[q] = Parent[p]; if (RightChild[Parent[p]] == p) RightChild[Parent[p]] = q; else LeftChild[Parent[p]] = q; Parent[p] = None; } private static double Entropy(byte[] ba) { var map = new Dictionary<byte, int>(); foreach (var c in ba) if (!map.ContainsKey(c)) map.Add(c, 1); else map[c]++; double Len = ba.Length; var re = map.Select(item => item.Value / Len).Aggregate(0.0, (current, frequency) => current - frequency * (Math.Log(frequency) / Math.Log(2))); return re / 8.00D * 100D; } }