1. Unity 5.6 is now released.
    Dismiss Notice
  2. We've introduced thread tags, search within a thread and similar thread search. Read more here.
    Dismiss Notice
  3. Learn how you'll soon be able to publish your games to China in four simple steps with Xiaomi. Sign up now for early access.
    Dismiss Notice
  4. Get further faster with the Unity Plus Accelerator Pack, free for new Unity Plus subscribers for a limited time. Click here for more details.
    Dismiss Notice
  5. We've released our first Timeline Experimental Preview, our new tool for creating cutscenes and more! To check it out click here.
    Dismiss Notice
  6. Check out all the fixes for 5.5 in patch releases 1 & 2.
    Dismiss Notice

LZF compression and decompression for Unity

Discussion in 'Scripting' started by Agent_007, Sep 26, 2012.

  1. Agent_007

    Agent_007

    Joined:
    Dec 18, 2011
    Posts:
    899
    I needed some general byte array compression for my project but unfortunately GZipStream and DeflateStream aren't supported with Unity. Because of that I had to cook something up, so I decided to use LZF since it has open license and existing C# code version.

    As LZF page describes "LibLZF is a very small data compression library. It consists of only two .c and two .h files and is very easy to incorporate into your own programs. The compression algorithm is very, very fast, yet still written in portable C.
    Last not least, it is freely usable, unlike most other compression libraries which are under the GPL, this library uses a BSD-type license, so you can include it in your programs without worrying."


    Original C code is written by Marc Alexander Lehmann and C# port is written by Oren J. Maurice. I removed CRC32 check functions and turned it into static class.

    Code:
    Code (csharp):
    1. /*
    2.  * Copyright (c) 2005 Oren J. Maurice <oymaurice@hazorea.org.il>
    3.  *
    4.  * Redistribution and use in source and binary forms, with or without modifica-
    5.  * tion, are permitted provided that the following conditions are met:
    6.  *
    7.  *   1.  Redistributions of source code must retain the above copyright notice,
    8.  *       this list of conditions and the following disclaimer.
    9.  *
    10.  *   2.  Redistributions in binary form must reproduce the above copyright
    11.  *       notice, this list of conditions and the following disclaimer in the
    12.  *       documentation and/or other materials provided with the distribution.
    13.  *
    14.  *   3.  The name of the author may not be used to endorse or promote products
    15.  *       derived from this software without specific prior written permission.
    16.  *
    17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
    18.  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
    19.  * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
    20.  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
    21.  * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    22.  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
    23.  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
    24.  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
    25.  * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
    26.  * OF THE POSSIBILITY OF SUCH DAMAGE.
    27.  *
    28.  * Alternatively, the contents of this file may be used under the terms of
    29.  * the GNU General Public License version 2 (the "GPL"), in which case the
    30.  * provisions of the GPL are applicable instead of the above. If you wish to
    31.  * allow the use of your version of this file only under the terms of the
    32.  * GPL and not to allow others to use your version of this file under the
    33.  * BSD license, indicate your decision by deleting the provisions above and
    34.  * replace them with the notice and other provisions required by the GPL. If
    35.  * you do not delete the provisions above, a recipient may use your version
    36.  * of this file under either the BSD or the GPL.
    37.  */
    38. using System;
    39.  
    40. /// <summary>
    41. /// Summary description for CLZF.
    42. /// </summary>
    43. public static class CLZF
    44. {
    45.     /// <summary>
    46.     /// LZF Compressor
    47.     /// </summary>
    48.  
    49.     private static readonly UInt32 HLOG = 14;
    50.     private static readonly UInt32 HSIZE = (1 << 14);
    51.  
    52.     /*
    53.         * don't play with this unless you benchmark!
    54.         * decompression is not dependent on the hash function
    55.         * the hashing function might seem strange, just believe me
    56.         * it works ;)
    57.         */
    58.     private static readonly UInt32 MAX_LIT = (1 << 5);
    59.     private static readonly UInt32 MAX_OFF = (1 << 13);
    60.     private static readonly UInt32 MAX_REF = ((1 << 8) + (1 << 3));
    61.  
    62.     private static UInt32 FRST (byte[] Array, UInt32 ptr)
    63.     {
    64.         return (UInt32)(((Array [ptr]) << 8) | Array [ptr + 1]);
    65.     }
    66.  
    67.     private static UInt32 NEXT (UInt32 v, byte[] Array, UInt32 ptr)
    68.     {
    69.         return ((v) << 8) | Array [ptr + 2];
    70.     }
    71.  
    72.     private static UInt32 IDX (UInt32 h)
    73.     {
    74.         return ((((h ^ (h << 5)) >> (int)(3 * 8 - HLOG)) - h * 5)  (HSIZE - 1));
    75.     }
    76.    
    77.     // Compresses inputBytes
    78.     public static byte[] Compress(byte[] inputBytes)
    79.     {
    80.         // Starting guess, increase it later if needed
    81.         int outputByteCountGuess = inputBytes.Length *2;
    82.         byte[] tempBuffer = new byte[outputByteCountGuess];
    83.         int byteCount = lzf_compress (inputBytes, ref tempBuffer);
    84.        
    85.         // If byteCount is 0, then increase buffer and try again
    86.         while (byteCount == 0)
    87.         {
    88.             outputByteCountGuess *=2;
    89.             tempBuffer = new byte[outputByteCountGuess];
    90.             byteCount = lzf_compress (inputBytes, ref tempBuffer);
    91.         }
    92.        
    93.         byte[] outputBytes = new byte[byteCount];
    94.         Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
    95.         return outputBytes;
    96.     }
    97.    
    98.     // Decompress outputBytes
    99.     public static byte[] Decompress(byte[] inputBytes)
    100.     {
    101.         // Starting guess, increase it later if needed
    102.         int outputByteCountGuess = inputBytes.Length *2;
    103.         byte[] tempBuffer = new byte[outputByteCountGuess];
    104.         int byteCount = lzf_decompress (inputBytes, ref tempBuffer);
    105.        
    106.         // If byteCount is 0, then increase buffer and try again
    107.         while (byteCount == 0)
    108.         {
    109.             outputByteCountGuess *=2;
    110.             tempBuffer = new byte[outputByteCountGuess];
    111.             byteCount = lzf_decompress (inputBytes, ref tempBuffer);
    112.         }
    113.        
    114.         byte[] outputBytes = new byte[byteCount];
    115.         Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
    116.         return outputBytes;
    117.     }
    118.  
    119.     /*
    120.         * compressed format
    121.         *
    122.         * 000LLLLL <L+1>    ; literal
    123.         * LLLOOOOO oooooooo ; backref L
    124.         * 111OOOOO LLLLLLLL oooooooo ; backref L+7
    125.         *
    126.         */
    127.  
    128.     private static int lzf_compress (byte[] in_data, ref byte[] out_data)
    129.     {
    130.         int in_len = in_data.Length;
    131.         int out_len = out_data.Length;
    132.        
    133.         int c;
    134.         long [] htab = new long[1 << 14];
    135.         for (c=0; c<1<<14; c++) {
    136.             htab [c] = 0;
    137.         }
    138.  
    139.         long hslot;
    140.         UInt32 iidx = 0;
    141.         UInt32 oidx = 0;
    142.         //byte *in_end  = ip + in_len;
    143.         //byte *out_end = op + out_len;
    144.         long reference;
    145.  
    146.         UInt32 hval = FRST (in_data, iidx);
    147.         long off;
    148.         int lit = 0;
    149.  
    150.         for (;;) {
    151.             if (iidx < in_len - 2) {
    152.                 hval = NEXT (hval, in_data, iidx);
    153.                 hslot = IDX (hval);
    154.                 reference = htab [hslot];
    155.                 htab [hslot] = (long)iidx;
    156.  
    157.                 if ((off = iidx - reference - 1) < MAX_OFF
    158.                          iidx + 4 < in_len
    159.                          reference > 0
    160.                          in_data [reference + 0] == in_data [iidx + 0]
    161.                          in_data [reference + 1] == in_data [iidx + 1]
    162.                          in_data [reference + 2] == in_data [iidx + 2]
    163.                         ) {
    164.                     /* match found at *reference++ */
    165.                     UInt32 len = 2;
    166.                     UInt32 maxlen = (UInt32)in_len - iidx - len;
    167.                     maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;
    168.  
    169.                     if (oidx + lit + 1 + 3 >= out_len)
    170.                         return 0;
    171.  
    172.                     do
    173.                         len++; while (len < maxlen  in_data[reference+len] == in_data[iidx+len]);
    174.  
    175.                     if (lit != 0) {
    176.                         out_data [oidx++] = (byte)(lit - 1);
    177.                         lit = -lit;
    178.                         do
    179.                             out_data [oidx++] = in_data [iidx + lit]; while ((++lit)!=0);
    180.                     }
    181.  
    182.                     len -= 2;
    183.                     iidx++;
    184.  
    185.                     if (len < 7) {
    186.                         out_data [oidx++] = (byte)((off >> 8) + (len << 5));
    187.                     } else {
    188.                         out_data [oidx++] = (byte)((off >> 8) + (7 << 5));
    189.                         out_data [oidx++] = (byte)(len - 7);
    190.                     }
    191.  
    192.                     out_data [oidx++] = (byte)off;
    193.  
    194.                     iidx += len - 1;
    195.                     hval = FRST (in_data, iidx);
    196.  
    197.                     hval = NEXT (hval, in_data, iidx);
    198.                     htab [IDX (hval)] = iidx;
    199.                     iidx++;
    200.  
    201.                     hval = NEXT (hval, in_data, iidx);
    202.                     htab [IDX (hval)] = iidx;
    203.                     iidx++;
    204.                     continue;
    205.                 }
    206.             } else if (iidx == in_len)
    207.                 break;
    208.  
    209.             /* one more literal byte we must copy */
    210.             lit++;
    211.             iidx++;
    212.  
    213.             if (lit == MAX_LIT) {
    214.                 if (oidx + 1 + MAX_LIT >= out_len)
    215.                     return 0;
    216.  
    217.                 out_data [oidx++] = (byte)(MAX_LIT - 1);
    218.                 lit = -lit;
    219.                 do
    220.                     out_data [oidx++] = in_data [iidx + lit]; while ((++lit)!=0);
    221.             }
    222.         }
    223.  
    224.         if (lit != 0) {
    225.             if (oidx + lit + 1 >= out_len)
    226.                 return 0;
    227.  
    228.             out_data [oidx++] = (byte)(lit - 1);
    229.             lit = -lit;
    230.             do
    231.                 out_data [oidx++] = in_data [iidx + lit]; while ((++lit)!=0);
    232.         }
    233.  
    234.         return (int)oidx;
    235.     }
    236.  
    237.     /// <summary>
    238.     /// LZF Decompressor
    239.     /// </summary>
    240.     private static int lzf_decompress (byte[] in_data, ref byte[] out_data)
    241.     {
    242.         int in_len = in_data.Length;
    243.         int out_len = out_data.Length;
    244.        
    245.         UInt32 iidx = 0;
    246.         UInt32 oidx = 0;
    247.  
    248.         do {
    249.             UInt32 ctrl = in_data [iidx++];
    250.  
    251.             if (ctrl < (1 << 5)) { /* literal run */
    252.                 ctrl++;
    253.  
    254.                 if (oidx + ctrl > out_len) {
    255.                     //SET_ERRNO (E2BIG);
    256.                     return 0;
    257.                 }
    258.  
    259.                 do
    260.                     out_data [oidx++] = in_data [iidx++]; while ((--ctrl)!=0);
    261.             } else { /* back reference */
    262.                 UInt32 len = ctrl >> 5;
    263.  
    264.                 int reference = (int)(oidx - ((ctrl  0x1f) << 8) - 1);
    265.  
    266.                 if (len == 7)
    267.                     len += in_data [iidx++];
    268.                      
    269.                 reference -= in_data [iidx++];
    270.  
    271.                 if (oidx + len + 2 > out_len) {
    272.                     //SET_ERRNO (E2BIG);
    273.                     return 0;
    274.                 }
    275.  
    276.                 if (reference < 0) {
    277.                     //SET_ERRNO (EINVAL);
    278.                     return 0;
    279.                 }
    280.  
    281.                 out_data [oidx++] = out_data [reference++];
    282.                 out_data [oidx++] = out_data [reference++];
    283.  
    284.                 do
    285.                     out_data [oidx++] = out_data [reference++]; while ((--len)!=0);
    286.             }
    287.         } while (iidx < in_len);
    288.  
    289.         return (int)oidx;
    290.     }
    291.  
    292. }
    Some tests I used to confirm it works
    Code (csharp):
    1. void Start () {    
    2.         // Convert 10000 character string to byte array.
    3.         byte[] text1 = Encoding.ASCII.GetBytes(new string('X', 10000));
    4.         byte[] compressed = CLZF.Compress(text1);
    5.         byte[] text2 = CLZF.Decompress(compressed);
    6.        
    7.         string longstring = "defined input is deluciously delicious.14 And here and Nora called The reversal from ground from here and executed with touch the country road, Nora made of, reliance on, can’t publish the goals of grandeur, said to his book and encouraging an envelope, and enable entry into the chryssial shimmering of hers, so God of information in her hands Spiros sits down the sign of winter? —It’s kind of Spice Christ. It is one hundred birds circle above the text: They did we said. 69 percent dead. Sissy Cogan’s shadow. —Are you x then sings.) I’m 96 percent dead humanoid figure,";
    8.         byte[] text3 = Encoding.ASCII.GetBytes(longstring);
    9.         byte[] compressed2 = CLZF.Compress(text3);
    10.         byte[] text4 = CLZF.Decompress(compressed2);
    11.        
    12.         Debug.Log("text1 size: " + text1.Length);
    13.         Debug.Log("compressed size:" + compressed.Length);
    14.         Debug.Log("text2 size: " + text2.Length);
    15.         Debug.Log("are equal: " + ByteArraysEqual(text1,text2));
    16.        
    17.         Debug.Log("text3 size: " + text3.Length);
    18.         Debug.Log("compressed2 size:" + compressed2.Length);
    19.         Debug.Log("text4 size: " + text4.Length);
    20.         Debug.Log("are equal: " + ByteArraysEqual(text3,text4));
    21.     }
    22.  
    23. public bool ByteArraysEqual(byte[] b1, byte[] b2)
    24.     {
    25.         if (b1 == b2) return true;
    26.         if (b1 == null || b2 == null) return false;
    27.         if (b1.Length != b2.Length) return false;
    28.         for (int i=0; i < b1.Length; i++)
    29.         {
    30.             if (b1[i] != b2[i]) return false;
    31.         }
    32.         return true;
    33.     }
    34.  
    Output is
    text1 size: 10000
    compressed size:120
    text2 size: 10000
    are equal: True
    text3 size: 586
    compressed2 size:520
    text4 size: 586
    are equal: True


    It seems to handle repeating stuff OK, but normal text doesn't compress very well. C# implementation isn't optimal but it is fast enough for me.
     
    nicloay and vexe like this.
  2. Agent_007

    Agent_007

    Joined:
    Dec 18, 2011
    Posts:
    899
    I found better implementation from http://csharplzfcompression.codeplex.com/ and I edited that a bit to make it Unity compatible.

    Code (csharp):
    1. /*
    2.  * Improved version to C# LibLZF Port:
    3.  * Copyright (c) 2010 Roman Atachiants <kelindar@gmail.com>
    4.  *
    5.  * Original CLZF Port:
    6.  * Copyright (c) 2005 Oren J. Maurice <oymaurice@hazorea.org.il>
    7.  *
    8.  * Original LibLZF Library  Algorithm:
    9.  * Copyright (c) 2000-2008 Marc Alexander Lehmann <schmorp@schmorp.de>
    10.  *
    11.  * Redistribution and use in source and binary forms, with or without modifica-
    12.  * tion, are permitted provided that the following conditions are met:
    13.  *
    14.  *   1.  Redistributions of source code must retain the above copyright notice,
    15.  *       this list of conditions and the following disclaimer.
    16.  *
    17.  *   2.  Redistributions in binary form must reproduce the above copyright
    18.  *       notice, this list of conditions and the following disclaimer in the
    19.  *       documentation and/or other materials provided with the distribution.
    20.  *
    21.  *   3.  The name of the author may not be used to endorse or promote products
    22.  *       derived from this software without specific prior written permission.
    23.  *
    24.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
    25.  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
    26.  * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
    27.  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
    28.  * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    29.  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
    30.  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
    31.  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
    32.  * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
    33.  * OF THE POSSIBILITY OF SUCH DAMAGE.
    34.  *
    35.  * Alternatively, the contents of this file may be used under the terms of
    36.  * the GNU General Public License version 2 (the "GPL"), in which case the
    37.  * provisions of the GPL are applicable instead of the above. If you wish to
    38.  * allow the use of your version of this file only under the terms of the
    39.  * GPL and not to allow others to use your version of this file under the
    40.  * BSD license, indicate your decision by deleting the provisions above and
    41.  * replace them with the notice and other provisions required by the GPL. If
    42.  * you do not delete the provisions above, a recipient may use your version
    43.  * of this file under either the BSD or the GPL.
    44.  */
    45. using System;
    46.  
    47. /* Benchmark with Alice29 Canterbury Corpus
    48.         ---------------------------------------
    49.         (Compression) Original CLZF C#
    50.         Raw = 152089, Compressed = 101092
    51.          8292,4743 ms.
    52.         ---------------------------------------
    53.         (Compression) My LZF C#
    54.         Raw = 152089, Compressed = 101092
    55.          33,0019 ms.
    56.         ---------------------------------------
    57.         (Compression) Zlib using SharpZipLib
    58.         Raw = 152089, Compressed = 54388
    59.          8389,4799 ms.
    60.         ---------------------------------------
    61.         (Compression) QuickLZ C#
    62.         Raw = 152089, Compressed = 83494
    63.          80,0046 ms.
    64.         ---------------------------------------
    65.         (Decompression) Original CLZF C#
    66.         Decompressed = 152089
    67.          16,0009 ms.
    68.         ---------------------------------------
    69.         (Decompression) My LZF C#
    70.         Decompressed = 152089
    71.          15,0009 ms.
    72.         ---------------------------------------
    73.         (Decompression) Zlib using SharpZipLib
    74.         Decompressed = 152089
    75.          3577,2046 ms.
    76.         ---------------------------------------
    77.         (Decompression) QuickLZ C#
    78.         Decompressed = 152089
    79.          21,0012 ms.
    80.     */
    81.  
    82.  
    83.     /// <summary>
    84.     /// Improved C# LZF Compressor, a very small data compression library. The compression algorithm is extremely fast.
    85. public static class CLZF2
    86. {
    87.     private static readonly uint HLOG = 14;
    88.     private static readonly uint HSIZE = (1 << 14);
    89.     private static readonly uint MAX_LIT = (1 << 5);
    90.     private static readonly uint MAX_OFF = (1 << 13);
    91.     private static readonly uint MAX_REF = ((1 << 8) + (1 << 3));
    92.    
    93.     /// <summary>
    94.     /// Hashtable, that can be allocated only once
    95.     /// </summary>
    96.     private static readonly long[] HashTable = new long[HSIZE];
    97.    
    98.     // Compresses inputBytes
    99.     public static byte[] Compress(byte[] inputBytes)
    100.     {
    101.         // Starting guess, increase it later if needed
    102.         int outputByteCountGuess = inputBytes.Length * 2;
    103.         byte[] tempBuffer = new byte[outputByteCountGuess];
    104.         int byteCount = lzf_compress (inputBytes, ref tempBuffer);
    105.        
    106.         // If byteCount is 0, then increase buffer and try again
    107.         while (byteCount == 0)
    108.         {
    109.             outputByteCountGuess *=2;
    110.             tempBuffer = new byte[outputByteCountGuess];
    111.             byteCount = lzf_compress (inputBytes, ref tempBuffer);
    112.         }
    113.        
    114.         byte[] outputBytes = new byte[byteCount];
    115.         Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
    116.         return outputBytes;
    117.     }
    118.    
    119.     // Decompress outputBytes
    120.     public static byte[] Decompress(byte[] inputBytes)
    121.     {
    122.         // Starting guess, increase it later if needed
    123.         int outputByteCountGuess = inputBytes.Length * 2;
    124.         byte[] tempBuffer = new byte[outputByteCountGuess];
    125.         int byteCount = lzf_decompress (inputBytes, ref tempBuffer);
    126.        
    127.         // If byteCount is 0, then increase buffer and try again
    128.         while (byteCount == 0)
    129.         {
    130.             outputByteCountGuess *=2;
    131.             tempBuffer = new byte[outputByteCountGuess];
    132.             byteCount = lzf_decompress (inputBytes, ref tempBuffer);
    133.         }
    134.        
    135.         byte[] outputBytes = new byte[byteCount];
    136.         Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
    137.         return outputBytes;
    138.     }
    139.  
    140.     /// <summary>
    141.         /// Compresses the data using LibLZF algorithm
    142.         /// </summary>
    143.         /// <param name="input">Reference to the data to compress</param>
    144.         /// <param name="output">Reference to a buffer which will contain the compressed data</param>
    145.         /// <returns>The size of the compressed archive in the output buffer</returns>
    146.         public static int lzf_compress(byte[] input, ref byte[] output)
    147.         {
    148.             int inputLength = input.Length;
    149.             int outputLength = output.Length;
    150.        
    151.             Array.Clear(HashTable, 0, (int)HSIZE);
    152.  
    153.             long hslot;
    154.             uint iidx = 0;
    155.             uint oidx = 0;
    156.             long reference;
    157.  
    158.             uint hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]); // FRST(in_data, iidx);
    159.             long off;
    160.             int lit = 0;
    161.  
    162.             for (; ; )
    163.             {
    164.                 if (iidx < inputLength - 2)
    165.                 {
    166.                     hval = (hval << 8) | input[iidx + 2];
    167.                     hslot = ((hval ^ (hval << 5)) >> (int)(((3 * 8 - HLOG)) - hval * 5)  (HSIZE - 1));
    168.                     reference = HashTable[hslot];
    169.                     HashTable[hslot] = (long)iidx;
    170.  
    171.  
    172.                     if ((off = iidx - reference - 1) < MAX_OFF
    173.                          iidx + 4 < inputLength
    174.                          reference > 0
    175.                          input[reference + 0] == input[iidx + 0]
    176.                          input[reference + 1] == input[iidx + 1]
    177.                          input[reference + 2] == input[iidx + 2]
    178.                         )
    179.                     {
    180.                         /* match found at *reference++ */
    181.                         uint len = 2;
    182.                         uint maxlen = (uint)inputLength - iidx - len;
    183.                         maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;
    184.  
    185.                         if (oidx + lit + 1 + 3 >= outputLength)
    186.                             return 0;
    187.  
    188.                         do
    189.                             len++;
    190.                         while (len < maxlen  input[reference + len] == input[iidx + len]);
    191.  
    192.                         if (lit != 0)
    193.                         {
    194.                             output[oidx++] = (byte)(lit - 1);
    195.                             lit = -lit;
    196.                             do
    197.                                 output[oidx++] = input[iidx + lit];
    198.                             while ((++lit) != 0);
    199.                         }
    200.  
    201.                         len -= 2;
    202.                         iidx++;
    203.  
    204.                         if (len < 7)
    205.                         {
    206.                             output[oidx++] = (byte)((off >> 8) + (len << 5));
    207.                         }
    208.                         else
    209.                         {
    210.                             output[oidx++] = (byte)((off >> 8) + (7 << 5));
    211.                             output[oidx++] = (byte)(len - 7);
    212.                         }
    213.  
    214.                         output[oidx++] = (byte)off;
    215.  
    216.                         iidx += len - 1;
    217.                         hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]);
    218.  
    219.                         hval = (hval << 8) | input[iidx + 2];
    220.                         HashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 - HLOG)) - hval * 5)  (HSIZE - 1))] = iidx;
    221.                         iidx++;
    222.  
    223.                         hval = (hval << 8) | input[iidx + 2];
    224.                         HashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 - HLOG)) - hval * 5)  (HSIZE - 1))] = iidx;
    225.                         iidx++;
    226.                         continue;
    227.                     }
    228.                 }
    229.                 else if (iidx == inputLength)
    230.                     break;
    231.  
    232.                 /* one more literal byte we must copy */
    233.                 lit++;
    234.                 iidx++;
    235.  
    236.                 if (lit == MAX_LIT)
    237.                 {
    238.                     if (oidx + 1 + MAX_LIT >= outputLength)
    239.                         return 0;
    240.  
    241.                     output[oidx++] = (byte)(MAX_LIT - 1);
    242.                     lit = -lit;
    243.                     do
    244.                         output[oidx++] = input[iidx + lit];
    245.                     while ((++lit) != 0);
    246.                 }
    247.             }
    248.  
    249.             if (lit != 0)
    250.             {
    251.                 if (oidx + lit + 1 >= outputLength)
    252.                     return 0;
    253.  
    254.                 output[oidx++] = (byte)(lit - 1);
    255.                 lit = -lit;
    256.                 do
    257.                     output[oidx++] = input[iidx + lit];
    258.                 while ((++lit) != 0);
    259.             }
    260.  
    261.             return (int)oidx;
    262.         }
    263.  
    264.  
    265.         /// <summary>
    266.         /// Decompresses the data using LibLZF algorithm
    267.         /// </summary>
    268.         /// <param name="input">Reference to the data to decompress</param>
    269.         /// <param name="output">Reference to a buffer which will contain the decompressed data</param>
    270.         /// <returns>Returns decompressed size</returns>
    271.         public static int lzf_decompress(byte[] input, ref byte[] output)
    272.         {
    273.             int inputLength = input.Length;
    274.             int outputLength = output.Length;
    275.        
    276.             uint iidx = 0;
    277.             uint oidx = 0;
    278.  
    279.             do
    280.             {
    281.                 uint ctrl = input[iidx++];
    282.  
    283.                 if (ctrl < (1 << 5)) /* literal run */
    284.                 {
    285.                     ctrl++;
    286.  
    287.                     if (oidx + ctrl > outputLength)
    288.                     {
    289.                         //SET_ERRNO (E2BIG);
    290.                         return 0;
    291.                     }
    292.  
    293.                     do
    294.                         output[oidx++] = input[iidx++];
    295.                     while ((--ctrl) != 0);
    296.                 }
    297.                 else /* back reference */
    298.                 {
    299.                     uint len = ctrl >> 5;
    300.  
    301.                     int reference = (int)(oidx - ((ctrl  0x1f) << 8) - 1);
    302.  
    303.                     if (len == 7)
    304.                         len += input[iidx++];
    305.  
    306.                     reference -= input[iidx++];
    307.  
    308.                     if (oidx + len + 2 > outputLength)
    309.                     {
    310.                         //SET_ERRNO (E2BIG);
    311.                         return 0;
    312.                     }
    313.  
    314.                     if (reference < 0)
    315.                     {
    316.                         //SET_ERRNO (EINVAL);
    317.                         return 0;
    318.                     }
    319.  
    320.                     output[oidx++] = output[reference++];
    321.                     output[oidx++] = output[reference++];
    322.  
    323.                     do
    324.                         output[oidx++] = output[reference++];
    325.                     while ((--len) != 0);
    326.                 }
    327.             }
    328.             while (iidx < inputLength);
    329.  
    330.             return (int)oidx;
    331.         }
    332.  
    333.     }
    334.  
    and test code
    Code (csharp):
    1. void Start () {
    2.         // Convert 10000 character string to byte array.
    3.         byte[] text1 = Encoding.ASCII.GetBytes(new string('X', 10000));
    4.         byte[] compressed = CLZF2.Compress(text1);
    5.         byte[] text2 = CLZF2.Decompress(compressed);
    6.        
    7.         string longstring = "defined input is deluciously delicious.14 And here and Nora called The reversal from ground from here and executed with touch the country road, Nora made of, reliance on, can’t publish the goals of grandeur, said to his book and encouraging an envelope, and enable entry into the chryssial shimmering of hers, so God of information in her hands Spiros sits down the sign of winter? —It’s kind of Spice Christ. It is one hundred birds circle above the text: They did we said. 69 percent dead. Sissy Cogan’s shadow. —Are you x then sings.) I’m 96 percent dead humanoid figure,";
    8.         byte[] text3 = Encoding.ASCII.GetBytes(longstring);
    9.         byte[] compressed2 = CLZF2.Compress(text3);
    10.         byte[] text4 = CLZF2.Decompress(compressed2);
    11.        
    12.         Debug.Log("text1 size: " + text1.Length);
    13.         Debug.Log("compressed size:" + compressed.Length);
    14.         Debug.Log("text2 size: " + text2.Length);
    15.         Debug.Log("are equal: " + ByteArraysEqual(text1,text2));
    16.        
    17.         Debug.Log("text3 size: " + text3.Length);
    18.         Debug.Log("compressed2 size:" + compressed2.Length);
    19.         Debug.Log("text4 size: " + text4.Length);
    20.         Debug.Log("are equal: " + ByteArraysEqual(text3,text4));
    21.     }
    22.    
    23.     public bool ByteArraysEqual(byte[] b1, byte[] b2)
    24.     {
    25.         if (b1 == b2) return true;
    26.         if (b1 == null || b2 == null) return false;
    27.         if (b1.Length != b2.Length) return false;
    28.         for (int i=0; i < b1.Length; i++)
    29.         {
    30.             if (b1[i] != b2[i]) return false;
    31.         }
    32.         return true;
    33.     }
     
  3. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    31,001
    This is cool; you should put it on the wiki. I was looking around for some method of zipping/unzipping data using managed code, and wasn't successful in finding anything that wasn't way too overblown; I hadn't heard of LZF. I have a test level file where the raw uncompressed data is about 2.4MB...I'd already implemented some simple run-length encoding, which got it down to 35KB, but there was still a fair amount of repetition in the compressed data. Using CLZF on top of the run-length encoding, it's 1.64KB. Nice. (Without run-length encoding, it's 57KB using CLZF alone, so clearly using both is advantageous in my case.)

    --Eric
     
  4. gigolo

    gigolo

    Joined:
    Sep 27, 2012
    Posts:
    61
    Sorry to bump but big thanks to you agent_007!
     
  5. landon91235

    landon91235

    Joined:
    Nov 8, 2011
    Posts:
    1,537
    I second this, this is beyond valuable.
     
  6. briosh

    briosh

    Joined:
    Aug 9, 2010
    Posts:
    17
    Just posting to say a BIG THANK YOU. One year later this is still so useful! Didn't find anything alike.
     
  7. fanjules

    fanjules

    Joined:
    Nov 9, 2011
    Posts:
    167
    Many, many, MANY thanks for this, it is now part of my project. :)

    Compression is fairly average, as is advertised for the algorithm. Compressing some GIS data I obtained a reduction from 68.6mb down to 33.0mb - better than half. Doing a simple ZIP on the same files yielded a saving of almost half again - down to 17.3mb. However, the process was considerably slower for the ZIP, even though you have to assume that's running much faster C++ code. In other words, this is an excellent algorithm for in-game operations... and could be faster still if Unity implemented it internally.

    Which leads me onto what many of us have probably wondered for a while now - why doesn't Unity ship with any compression capability? Even Flash's Actionscript had a great compress() and decompress() methods, supporting no less than 3 different types - zlib, deflate, and lzma! This has been the case since at least 2006 when AS3 came along... meanwhile in 2014 Unity has... nothing.
     
    Last edited: Jan 26, 2014
    terrypaton1 likes this.
  8. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    18,654
    This looks cool for network stuff, for instance I need to chuck a meg of data down the pipe or something. Thanks!
     
  9. benw

    benw

    Joined:
    Jul 9, 2013
    Posts:
    1
    Thanks, you saved my arse :)

    I originally tried to use .net's GZipStream stuff, but then found out Unity mono didn't support it - your post was just what I needed!
     
  10. badoet

    badoet

    Joined:
    Jun 4, 2014
    Posts:
    2
    hmm am i the only one having error from copy pasting the code?
    i got lots of stupid error from unity like Assets/Script/CLZF2.cs(173,29): error CS1525: Unexpected symbol `iidx'
    where iidx has been explicitly declared at the top.
    need help. using unity 4.5
     
  11. mrbroshkin

    mrbroshkin

    Joined:
    Aug 14, 2012
    Posts:
    27
    Here is the fixed disappeared '&' symbols version
     

    Attached Files:

    • CLZF2.cs
      File size:
      9.7 KB
      Views:
      1,433
    Fajlworks, Draco18s and Weiky like this.
  12. spartan029

    spartan029

    Joined:
    Mar 12, 2014
    Posts:
    3
    Awesome! Thanks!

    And many thanks to mrbroshkin, for the fix!
     
  13. vexe

    vexe

    Joined:
    May 18, 2013
    Posts:
    598
    Thanks! Here's a bit more cleaner version with file and string [de]compression helper methods
     

    Attached Files:

    Last edited: Nov 27, 2014
    tswalk, milox88, kayy and 1 other person like this.
  14. scrawk

    scrawk

    Joined:
    Nov 22, 2012
    Posts:
    754
    This thread is a bit old but deserves a bump as it just saved me a lot of time.
     
    jason-fisher likes this.
  15. Phastin

    Phastin

    Joined:
    Mar 22, 2013
    Posts:
    2
    I decided to use this compression scheme today, and I show my thanks by using the traditional salute of my native culture: A thread bump.
     
    Brainswitch and jason-fisher like this.
  16. andymads

    andymads

    Joined:
    Jun 16, 2011
    Posts:
    1,176
    @vexe Just wanted to say I'm occasionally getting 'array index out of range' exceptions with your CompressionHelper at line 340 (iidx is equal to input array length).
     
  17. vexe

    vexe

    Joined:
    May 18, 2013
    Posts:
    598
    That's something I didn't change from the original script. Sounds like you could maybe try while instead of do while?
     
  18. lenneth78

    lenneth78

    Joined:
    Jul 2, 2012
    Posts:
    81
    This script is wonderful ! My stress save pass from 230mo to 30mo in 1.5s ! 766% of gains. For information, other algo of compress has never finished :(.

    So thk for this script !
     
  19. wokawaka

    wokawaka

    Joined:
    Jan 11, 2014
    Posts:
    12
    This runs out of memory for me with rather small sets of data on a machine with 4gb of free ram(8gb in total)..
    This simple test throws an out of memory exception on vexe's code during compress.

    Anyone have a better version?

    EDIT: The file called "CLZF2.cs" does not have the out of memory problem that the later "cleaned upp code" does.

    The earlier version can run on string lengths of upp to 500 000 on my machine with no problems.

    Code (CSharp):
    1.         [TestMethod]
    2.         public void CompressionTest()
    3.         {
    4.             string x = string.Empty;
    5.             foreach (var z in Enumerable.Range(1, 100)) // string length 3600
    6.             {
    7.                 x += Guid.NewGuid();
    8.             }
    9.  
    10.             var compressed = CompressionHelper.CompressString(x);
    11.             var decompressed = CompressionHelper.DecompressString(compressed);
    12.  
    13.             int difflen = x.Length - compressed.Length;
    14.  
    15.             Assert.IsTrue(difflen >= 0);
    16.             Assert.AreEqual(decompressed, x);
    17.         }
     
    Last edited: May 18, 2015
  20. the_lemur

    the_lemur

    Joined:
    Apr 3, 2013
    Posts:
    90
    Finally! Someone had a C# GZipStream that was not working at all. Spent hours triyng to figure out if the data was being lost or something... This example worked right the first try.
     
  21. jjay

    jjay

    Joined:
    Mar 4, 2014
    Posts:
    3
    Heya!
    Is it possible to adapt this algorithm so it use Stream instead of byte arrays (e.g. lzf_decompress (Stream in_data, Stream out_data) ?
     
  22. killer_bigpoint

    killer_bigpoint

    Joined:
    Jul 11, 2015
    Posts:
    14
    Anybody got a javascript version of this?
     
  23. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    31,001
    Not necessary; you can use the C# version from Unityscript.

    --Eric
     
  24. bion

    bion

    Joined:
    Oct 25, 2012
    Posts:
    4
    @Eric5h5
    hi eric,what do you mean?can you say clearly?
    actually,i need a good compress and decompress library used on mobile devices.
    i have tested LZMA, which is good ,but the decompress rate is too slow on mobie devices.
    this gzip
    https://www.assetstore.unity3d.com/en/#!/content/31902. the compress is too slow,1MB cost 60s.
     
  25. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    31,001
    I don't know what you're referring to.

    --Eric
     
  26. icefallgames

    icefallgames

    Joined:
    Dec 6, 2014
    Posts:
    8
    Another thread bump - very useful, just found this today!
     
  27. SimonDarksideJ

    SimonDarksideJ

    Joined:
    Jul 3, 2012
    Posts:
    1,473
    Wow, just came across this thread and it's beyond awesome. Will dig through and put the latest version in the UI Extensions project.
    Granted this isn't UI related but it's too awesome to miss :D
     
  28. nevaran

    nevaran

    Joined:
    May 21, 2010
    Posts:
    215
    Is there some similar(fast) compression system that compresses floats instead of bytes?
    Im compressing audio data, so i need to do a conversion to bytes and then back to floats while using this one, which I cannot afford.:(
     
  29. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    31,001
    There's some C source code here which you could adapt.

    --Eric
     
  30. nevaran

    nevaran

    Joined:
    May 21, 2010
    Posts:
    215
    Thanks, ill check it out.
     
  31. nevaran

    nevaran

    Joined:
    May 21, 2010
    Posts:
    215
    I cant figure out which headers and codes are the actual program, and how to compile them into a managed library :/
     
  32. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    31,001
    src/zfp.c You read the C code and write a new version in C#.

    --Eric
     
  33. nevaran

    nevaran

    Joined:
    May 21, 2010
    Posts:
    215
    Can this be built into a managed library? Feels like it would be better.
    I have almost no knowledge in C
     
  34. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    31,001
    The point is that you read the C code and write a C# version that works in Unity. You can't use it as-is.

    --Eric
     
  35. nevaran

    nevaran

    Joined:
    May 21, 2010
    Posts:
    215
    Guess ill have some fun figuring out how the hell it works ;)
    Also ,isnt 'decompress' and 'compress' files in the template folder also needed? Its using a definition of a sort in the code
     
  36. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    31,001
    Yeah, looks like it.

    --Eric
     
  37. eunein

    eunein

    Joined:
    Jun 16, 2015
    Posts:
    3
    Hi !!

    I got a very difficult bug, When LZF compression goes, no error shows, but when decompression, the document has been damaged, please help me, thank you!
     

    Attached Files:

  38. eunein

    eunein

    Joined:
    Jun 16, 2015
    Posts:
    3
    Please ignore me... It is my fault : I choose the file mode to be Append not Create , so the old data just donot be cleared. So the file is broken for decompression. Hope this can help others ...
     
  39. tswalk

    tswalk

    Joined:
    Jul 27, 2013
    Posts:
    1,032
    just fyi, this code is very 'blocking' so if you have a large file that need decompressing... it gonna hurt.
     
  40. FlashMuller

    FlashMuller

    Joined:
    Sep 25, 2013
    Posts:
    137
    @andymads
    Did you find a solution? I am having the very same problem.
     
  41. andymads

    andymads

    Joined:
    Jun 16, 2011
    Posts:
    1,176
    No I didn't.
     
  42. EnlightenedOne

    EnlightenedOne

    Joined:
    Jun 17, 2015
    Posts:
    7
    I hit this issue, I think the latest version of Unity is threading its packet serialisation or something as one of my packet compression operations suddenly started failing periodically, so I put in a comically named line for use as a breakpoint and I waited for it to happen again:
    ...
    for (; ;) {
    if (iidx < inputLength - 2) {
    hval = (hval << 8) | input[iidx + 2];
    hslot = ((hval ^ (hval << 5)) >> (int)(((3 * 8 - HLOG)) - hval * 5) & (HSIZE - 1));
    reference = HashTable[hslot];
    HashTable[hslot] = (long)iidx;

    if ((off = iidx - reference - 1) < MAX_OFF && iidx + 4 < inputLength && reference > 0 &&
    (input.LongLength < reference + 2 || input.LongLength < iidx +2)
    ) {
    bool freakout = true;
    }


    if ((off = iidx - reference - 1) < MAX_OFF && iidx + 4 < inputLength && reference > 0 &&
    ...

    The culprit I suspect is below, threaded use of a none thread safe static:
    private static readonly long[] HashTable = new long[HSIZE];

    I was unable to get the community 2017 version of VS to acknowledge the existence of ThreadLocal so I had to use ThreadStatic annotation. I am uploading my copy of the compression algorithm please note I have different formatting and a boiler plate check for an array 1 byte long on compress and decompress you may not want. I hope this helps.
     
  43. EnlightenedOne

    EnlightenedOne

    Joined:
    Jun 17, 2015
    Posts:
    7
    I removed a redundant include and reuploaded
     

    Attached Files: