LZF - Echtzeit Kompressions Algorithmus (verbesserte Version)

    • C#
    • .NET (FX) 4.5–4.8

    Es gibt 2 Antworten in diesem Thema. Der letzte Beitrag () ist von VincentTB.

      LZF - Echtzeit Kompressions Algorithmus (verbesserte Version)

      Hi,
      einige haben vielleicht mitbekommen, dass mir die Signaturen der Methoden von wohl einem der besten freien Kompressionsalgorithmen ganz schön zu schaffen machten. Weil dieser QuickLZ ersetzen soll, war nun meine Aufgabe, LZF so anzupassen, dass alles genauso funktioniert wie vorher. U. a. habe ich die Möglichkeit hinzugefügt, dass man die Startposition des zu dekomprimierenden Arrays auswählen kann und es wird nun direkt ein Byte-Array zurückgegeben. Außerdem sind nun die ersten 4 Bytes die original Größe der Datei, was beim Dekomprimieren ein Vorteil ist, weil man nun exakt so viele Bytes reservieren kann, wie nötig sind (und man nicht schätzen muss).

      Hier sind mal ein paar Messwerte:

      		1 KiB1 MiB
      Komprimieren40710 Ticks52 ms (6919662 ticks)
      Dekomprimieren3373 Ticks8 ms (1089177 ticks)


      Mit dem Code:
      Spoiler anzeigen

      C#-Quellcode

      1. var data = new byte[1024];
      2. var random = new Random();
      3. random.NextBytes(data);
      5. byte[] result = null;
      6. var sw = Stopwatch.StartNew();
      7. for (int i = 0; i < 50; i++)
      8. {
      9. result = LZF.Compress(data, 0);
      10. }
      12. Console.WriteLine($"Compressing speed: {sw.ElapsedMilliseconds / 50} ms ({sw.ElapsedTicks} ticks) / KiB, final size: {result.Length / 1024} KiB (50 rounds)");
      14. byte[] decompressed = null;
      15. sw.Restart();
      16. for (int i = 0; i < 50; i++)
      17. {
      18. decompressed = LZF.Decompress(result, 0);
      19. }
      20. sw.Stop();
      22. bool hashesAreEqual;
      23. using (var sha256 = new SHA256CryptoServiceProvider())
      24. {
      25. var originalHash = sha256.ComputeHash(data);
      26. var decompressedHash = sha256.ComputeHash(decompressed);
      27. hashesAreEqual = originalHash.SequenceEqual(decompressedHash);
      28. }
      29. Console.WriteLine($"Decompressing speed: {sw.ElapsedMilliseconds / 50} ms ({sw.ElapsedTicks} ticks) / KiB, hashes are {(hashesAreEqual ? "equal" : "not equal")} (50 rounds)");
      31. data = new byte[1024 * 1024];
      32. random.NextBytes(data);
      34. sw.Restart();
      35. for (int i = 0; i < 50; i++)
      36. {
      37. result = LZF.Compress(data, 0);
      38. }
      40. Console.WriteLine($"Compressing speed: {sw.ElapsedMilliseconds / 50} ms ({sw.ElapsedTicks} ticks) / MiB, final size: {result.Length / 1024} KiB (50 rounds)");
      42. sw.Restart();
      43. for (int i = 0; i < 50; i++)
      44. {
      45. decompressed = LZF.Decompress(result, 0);
      46. }
      47. sw.Stop();
      49. using (var sha256 = new SHA256CryptoServiceProvider())
      50. {
      51. var originalHash = sha256.ComputeHash(data);
      52. var decompressedHash = sha256.ComputeHash(decompressed);
      53. hashesAreEqual = originalHash.SequenceEqual(decompressedHash);
      54. }
      55. Console.WriteLine($"Decompressing speed: {sw.ElapsedMilliseconds / 50} ms ({sw.ElapsedTicks} ticks) / MiB, hashes are {(hashesAreEqual ? "equal" : "not equal")} (50 rounds)");


      Ich denke, dass die Werte ganz Ok sind :D

      Hier ist nun der Code:

      C#-Quellcode

      1. /*
      2. * Remove the C++ things, make it static and add offset parameter:
      3. * Copyright (c) 2016 Anapher <https://github.com/Anapher>
      4. *
      5. * Improved version to C# LibLZF Port:
      6. * Copyright (c) 2010 Roman Atachiants <kelindar@gmail.com>
      7. *
      8. * Original CLZF Port:
      9. * Copyright (c) 2005 Oren J. Maurice <oymaurice@hazorea.org.il>
      10. *
      11. * Original LibLZF Library & Algorithm:
      12. * Copyright (c) 2000-2008 Marc Alexander Lehmann <schmorp@schmorp.de>
      13. *
      14. * Redistribution and use in source and binary forms, with or without modifica-
      15. * tion, are permitted provided that the following conditions are met:
      16. *
      17. * 1. Redistributions of source code must retain the above copyright notice,
      18. * this list of conditions and the following disclaimer.
      19. *
      20. * 2. Redistributions in binary form must reproduce the above copyright
      21. * notice, this list of conditions and the following disclaimer in the
      22. * documentation and/or other materials provided with the distribution.
      23. *
      24. * 3. The name of the author may not be used to endorse or promote products
      25. * derived from this software without specific prior written permission.
      26. *
      27. * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
      28. * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
      29. * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
      30. * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
      31. * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
      32. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
      33. * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
      34. * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
      35. * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
      36. * OF THE POSSIBILITY OF SUCH DAMAGE.
      37. *
      38. * Alternatively, the contents of this file may be used under the terms of
      39. * the GNU General Public License version 2 (the "GPL"), in which case the
      40. * provisions of the GPL are applicable instead of the above. If you wish to
      41. * allow the use of your version of this file only under the terms of the
      42. * GPL and not to allow others to use your version of this file under the
      43. * BSD license, indicate your decision by deleting the provisions above and
      44. * replace them with the notice and other provisions required by the GPL. If
      45. * you do not delete the provisions above, a recipient may use your version
      46. * of this file under either the BSD or the GPL.
      47. */
      49. using System;
      51. namespace LzfTest
      52. {
      53. /// <summary>
      54. /// Improved C# LZF Compressor, a very small data compression library. The compression algorithm is extremely fast.
      55. /// </summary>
      56. public static class LZF
      57. {
      58. private const uint HLOG = 14;
      59. private const uint HSIZE = 1 << 14;
      60. private const uint MAX_LIT = 1 << 5;
      61. private const uint MAX_OFF = 1 << 13;
      62. private const uint MAX_REF = (1 << 8) + (1 << 3);
      64. /// <summary>
      65. /// Compresses the data using LibLZF algorithm
      66. /// </summary>
      67. /// <param name="input">Reference to the data to compress</param>
      68. /// <param name="output">Reference to a buffer which will contain the compressed data</param>
      69. /// <param name="start"></param>
      70. /// <returns>The size of the compressed archive in the output buffer</returns>
      71. private static int InternalCompress(byte[] input, byte[] output, int start)
      72. {
      73. var hashTable = new long[HSIZE];
      74. Array.Copy(BitConverter.GetBytes(input.Length - start), output, 4);
      76. uint iidx = (uint)start;
      77. uint oidx = 4;
      79. uint hval = (uint)((input[iidx] << 8) | input[iidx + 1]); // FRST(in_data, iidx);
      80. int lit = 0;
      82. for (;;)
      83. {
      84. if (iidx < input.Length - 2)
      85. {
      86. hval = (hval << 8) | input[iidx + 2];
      87. long hslot = (hval ^ (hval << 5)) >> (int)(3 * 8 - HLOG - hval * 5) & (HSIZE - 1);
      88. var reference = hashTable[hslot];
      89. hashTable[hslot] = iidx;
      91. long off;
      92. if ((off = iidx - reference - 1) < MAX_OFF
      93. && iidx + 4 < input.Length
      94. && reference > 0
      95. && input[reference + 0] == input[iidx + 0]
      96. && input[reference + 1] == input[iidx + 1]
      97. && input[reference + 2] == input[iidx + 2]
      98. )
      99. {
      100. /* match found at *reference++ */
      101. uint len = 2;
      102. uint maxlen = (uint)input.Length - iidx - len;
      103. maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;
      105. if (oidx + lit + 1 + 3 >= output.Length)
      106. return 0;
      108. do
      109. len++; while (len < maxlen && input[reference + len] == input[iidx + len]);
      111. if (lit != 0)
      112. {
      113. output[oidx++] = (byte)(lit - 1);
      114. lit = -lit;
      115. do
      116. output[oidx++] = input[iidx + lit]; while (++lit != 0);
      117. }
      119. len -= 2;
      120. iidx++;
      122. if (len < 7)
      123. {
      124. output[oidx++] = (byte)((off >> 8) + (len << 5));
      125. }
      126. else
      127. {
      128. output[oidx++] = (byte)((off >> 8) + (7 << 5));
      129. output[oidx++] = (byte)(len - 7);
      130. }
      132. output[oidx++] = (byte)off;
      134. iidx += len - 1;
      135. hval = (uint)((input[iidx] << 8) | input[iidx + 1]);
      137. hval = (hval << 8) | input[iidx + 2];
      138. hashTable[(hval ^ (hval << 5)) >> (int)(3 * 8 - HLOG - hval * 5) & (HSIZE - 1)] = iidx;
      139. iidx++;
      141. hval = (hval << 8) | input[iidx + 2];
      142. hashTable[(hval ^ (hval << 5)) >> (int)(3 * 8 - HLOG - hval * 5) & (HSIZE - 1)] = iidx;
      143. iidx++;
      144. continue;
      145. }
      146. }
      147. else if (iidx == input.Length)
      148. break;
      150. /* one more literal byte we must copy */
      151. lit++;
      152. iidx++;
      154. if (lit == MAX_LIT)
      155. {
      156. if (oidx + 1 + MAX_LIT >= output.Length)
      157. return 0;
      159. output[oidx++] = (byte)(MAX_LIT - 1);
      160. lit = -lit;
      161. do
      162. output[oidx++] = input[iidx + lit]; while (++lit != 0);
      163. }
      164. }
      166. if (lit != 0)
      167. {
      168. if (oidx + lit + 1 >= output.Length)
      169. return 0;
      171. output[oidx++] = (byte)(lit - 1);
      172. lit = -lit;
      173. do
      174. output[oidx++] = input[iidx + lit]; while (++lit != 0);
      175. }
      177. return (int)oidx;
      178. }
      180. /// <summary>
      181. /// Compresses the data using LibLZF algorithm
      182. /// </summary>
      183. /// <param name="source">Reference to the data to compress</param>
      184. /// <param name="start">The point where it should start to decompress from the <see cref="source" /></param>
      185. /// <returns>The compressed bytes</returns>
      186. public static byte[] Compress(byte[] source, int start)
      187. {
      188. var destination = new byte[source.Length + source.Length / 2 + 36000];
      189. var used = InternalCompress(source, destination, start);
      190. if (used == 0)
      191. return null;
      193. var compressed = new byte[used];
      194. for (uint i = 0; i < used; ++i)
      195. compressed[i] = destination[i];
      196. return compressed;
      197. }
      199. /// <summary>
      200. /// Decompresses the data using LibLZF algorithm
      201. /// </summary>
      202. /// <param name="source">Reference to the data to decompress</param>
      203. /// <param name="start">
      204. /// The point where it should start to decompress from the <see cref="source"/</param>
      205. /// <returns>The decompressed bytes</returns>
      206. public static byte[] Decompress(byte[] source, int start)
      207. {
      208. var decompressed = new byte[GetSize(source, start)];
      209. var used = InternalDecompress(source, decompressed, start);
      210. if (used == 0)
      211. throw new InvalidOperationException("Impossible");
      213. return decompressed;
      214. }
      216. /// <summary>
      217. /// Decompresses the data using LibLZF algorithm
      218. /// </summary>
      219. /// <param name="input">Reference to the data to decompress</param>
      220. /// <param name="output">Reference to a buffer which will contain the decompressed data</param>
      221. /// <param name="start"></param>
      222. /// <returns>Returns decompressed size</returns>
      223. private static int InternalDecompress(byte[] input, byte[] output, int start)
      224. {
      225. uint iidx = 4 + (uint)start;
      226. uint oidx = 0;
      228. do
      229. {
      230. uint ctrl = input[iidx++];
      232. if (ctrl < 1 << 5) /* literal run */
      233. {
      234. ctrl++;
      236. if (oidx + ctrl > output.Length)
      237. {
      238. //SET_ERRNO (E2BIG);
      239. return 0;
      240. }
      242. do
      243. output[oidx++] = input[iidx++]; while (--ctrl != 0);
      244. }
      245. else /* back reference */
      246. {
      247. uint len = ctrl >> 5;
      249. int reference = (int)(oidx - ((ctrl & 0x1f) << 8) - 1);
      251. if (len == 7)
      252. len += input[iidx++];
      254. reference -= input[iidx++];
      256. if (oidx + len + 2 > output.Length)
      257. {
      258. //SET_ERRNO (E2BIG);
      259. return 0;
      260. }
      262. if (reference < 0)
      263. {
      264. //SET_ERRNO (EINVAL);
      265. return 0;
      266. }
      268. output[oidx++] = output[reference++];
      269. output[oidx++] = output[reference++];
      271. do
      272. output[oidx++] = output[reference++]; while (--len != 0);
      273. }
      274. } while (iidx < input.Length);
      276. return (int)oidx;
      277. }
      279. private static int GetSize(byte[] source, int start)
      280. {
      281. return BitConverter.ToInt32(source, start);
      282. }
      283. }
      284. }


      Der Code stammt nicht von mir, wurde aber von mir verbessert. Die Lizenz hat sich nicht verändert, findet ihr hier: csharplzfcompression.codeplex.com/license
      Den originalen Code könnt ihr hier finden: csharplzfcompression.codeplex.com/SourceControl/latest
      Im Anhang findet ihr noch ein Test Projekt, welches ich für die Messwerte oben verwendet habe.
      Dateien

      • LzfTest.zip

        (34,76 kB, 201 mal heruntergeladen, zuletzt: )
      Mfg
      Vincent

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „VincentTB“ ()

      Hi @VincentTB!

      Erst mal: Sehr gute Arbeit ;D

      Hab den Code mal ausprobiert und mir ist da aber folgendes aufgfallen:
      In deinem Bsp erstellst du ein byte-Array, das du zufällig mit Werten füllst. Dass der Code schnell komprimiert stell ich jetz mal außer frage, aber was die Kompressionsstärke in dem Fall angeht, versagt der doch auf ganzer Länge. Oder mach ich da was falsch?

      Wenn ich folgenden Code verwende:

      C#-Quellcode

      1. var data = new byte[1024];
      2. byte[] result = null;
      3. var random = new Random();
      5. random.NextBytes(data);
      6. result = LZF.Compress(data, 0);
      8. File.WriteAllBytes("data.txt", data);
      9. File.WriteAllBytes("result.txt", result);


      dann erstelle ich mir ja 2 Dateien: eine data.txt und eine result.txt
      Wenn ich jetz mit dem Explorer mir die Dateien anschaue, dann ist die erste(data.txt) ganze 1024 bytes groß, die komprimierte datei aber 1060 kb groß.


      Lg Radinator

      PS: Bei 20Mb random bytes ist der Unterschied fast ein ganzes MB
      In general (across programming languages), a pointer is a number that represents a physical location in memory. A nullpointer is (almost always) one that points to 0, and is widely recognized as "not pointing to anything". Since systems have different amounts of supported memory, it doesn't always take the same number of bytes to hold that number, so we call a "native size integer" one that can hold a pointer on any particular system. - Sam Harwell

      @Radinator
      Das ist völlig logisch, zufällige Bytes können nicht komprimiert werden. Es wird größer, weil dann noch Metadaten dazu kommen. Teste das doch mal z. B. mit einer Bild-Datei, diese wird wesentlich kleiner. Zufällige Bytes sind vielleicht nicht optimal, um zu zeigen, was der Algorithmus kann :D Bei dem offiziellen Benchmark wurden auch andere Methoden genutzt, um die Daten zu generieren, für mich war das mehr so eine Kontrolle, dass der Algorithmus trotz meinen Änderungen gut funktioniert.

      Ich habe übrigens bei meiner Implementierung noch einen Check gemacht, ob sich die Kompression überhaupt gelohnt hat, wenn nicht, schicke ich die unkomprimierten Bytes. Das spart dann auch Zeit auf der Clientseite, weil diese dann nicht extra dekomprimiert werden müssen (Man sollte vielleicht dazu sagen, dass es sich um einen Server-Client Datenaustausch handelt).
      Mfg
      Vincent

    Facebook
    Telefonspende