Tanoda
CLZF2.cs
Go to the documentation of this file.
1//
2// http://forum.unity3d.com/threads/lzf-compression-and-decompression-for-unity.152579/
3//
4
5/*
6 * Improved version to C# LibLZF Port:
7 * Copyright (c) 2010 Roman Atachiants <kelindar@gmail.com>
8 *
9 * Original CLZF Port:
10 * Copyright (c) 2005 Oren J. Maurice <oymaurice@hazorea.org.il>
11 *
12 * Original LibLZF Library Algorithm:
13 * Copyright (c) 2000-2008 Marc Alexander Lehmann <schmorp@schmorp.de>
14 *
15 * Redistribution and use in source and binary forms, with or without modifica-
16 * tion, are permitted provided that the following conditions are met:
17 *
18 * 1. Redistributions of source code must retain the above copyright notice,
19 * this list of conditions and the following disclaimer.
20 *
21 * 2. Redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution.
24 *
25 * 3. The name of the author may not be used to endorse or promote products
26 * derived from this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
29 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
30 * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
31 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
32 * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
33 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
34 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
35 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
36 * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
37 * OF THE POSSIBILITY OF SUCH DAMAGE.
38 *
39 * Alternatively, the contents of this file may be used under the terms of
40 * the GNU General Public License version 2 (the "GPL"), in which case the
41 * provisions of the GPL are applicable instead of the above. If you wish to
42 * allow the use of your version of this file only under the terms of the
43 * GPL and not to allow others to use your version of this file under the
44 * BSD license, indicate your decision by deleting the provisions above and
45 * replace them with the notice and other provisions required by the GPL. If
46 * you do not delete the provisions above, a recipient may use your version
47 * of this file under either the BSD or the GPL.
48 */
49
50/* Benchmark with Alice29 Canterbury Corpus
51 ---------------------------------------
52 (Compression) Original CLZF C#
53 Raw = 152089, Compressed = 101092
54 8292,4743 ms.
55 ---------------------------------------
56 (Compression) My LZF C#
57 Raw = 152089, Compressed = 101092
58 33,0019 ms.
59 ---------------------------------------
60 (Compression) Zlib using SharpZipLib
61 Raw = 152089, Compressed = 54388
62 8389,4799 ms.
63 ---------------------------------------
64 (Compression) QuickLZ C#
65 Raw = 152089, Compressed = 83494
66 80,0046 ms.
67 ---------------------------------------
68 (Decompression) Original CLZF C#
69 Decompressed = 152089
70 16,0009 ms.
71 ---------------------------------------
72 (Decompression) My LZF C#
73 Decompressed = 152089
74 15,0009 ms.
75 ---------------------------------------
76 (Decompression) Zlib using SharpZipLib
77 Decompressed = 152089
78 3577,2046 ms.
79 ---------------------------------------
80 (Decompression) QuickLZ C#
81 Decompressed = 152089
82 21,0012 ms.
83 */
84
85using System;
86
88{
92 public static class CLZF2
93 {
94 private static readonly uint HLOG = 14;
95 private static readonly uint HSIZE = (1 << 14);
96 private static readonly uint MAX_LIT = (1 << 5);
97 private static readonly uint MAX_OFF = (1 << 13);
98 private static readonly uint MAX_REF = ((1 << 8) + (1 << 3));
99
103 private static readonly long[] HashTable = new long[HSIZE];
104
105 // Compresses inputBytes
106 public static byte[] Compress(byte[] inputBytes)
107 {
108 // Starting guess, increase it later if needed
109 int outputByteCountGuess = inputBytes.Length * 2;
110 byte[] tempBuffer = new byte[outputByteCountGuess];
111 int byteCount = lzf_compress(inputBytes, ref tempBuffer);
112
113 // If byteCount is 0, then increase buffer and try again
114 while (byteCount == 0)
115 {
116 outputByteCountGuess *= 2;
117 tempBuffer = new byte[outputByteCountGuess];
118 byteCount = lzf_compress(inputBytes, ref tempBuffer);
119 }
120
121 byte[] outputBytes = new byte[byteCount];
122 Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
123 return outputBytes;
124 }
125
126 // Decompress outputBytes
127 public static byte[] Decompress(byte[] inputBytes)
128 {
129 // Starting guess, increase it later if needed
130 int outputByteCountGuess = inputBytes.Length * 2;
131 byte[] tempBuffer = new byte[outputByteCountGuess];
132 int byteCount = lzf_decompress(inputBytes, ref tempBuffer);
133
134 // If byteCount is 0, then increase buffer and try again
135 while (byteCount == 0)
136 {
137 outputByteCountGuess *= 2;
138 tempBuffer = new byte[outputByteCountGuess];
139 byteCount = lzf_decompress(inputBytes, ref tempBuffer);
140 }
141
142 byte[] outputBytes = new byte[byteCount];
143 Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
144 return outputBytes;
145 }
146
153 public static int lzf_compress(byte[] input, ref byte[] output)
154 {
155 int inputLength = input.Length;
156 int outputLength = output.Length;
157
158 Array.Clear(HashTable, 0, (int)HSIZE);
159
160 long hslot;
161 uint iidx = 0;
162 uint oidx = 0;
163 long reference;
164
165 uint hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]); // FRST(in_data, iidx);
166 long off;
167 int lit = 0;
168
169 for (;;)
170 {
171 if (iidx < inputLength - 2)
172 {
173 hval = (hval << 8) | input[iidx + 2];
174 hslot = ((hval ^ (hval << 5)) >> (int)(((3 * 8 - HLOG)) - hval * 5) & (HSIZE - 1));
175 reference = HashTable[hslot];
176 HashTable[hslot] = (long)iidx;
177
178
179 if ((off = iidx - reference - 1) < MAX_OFF
180 && iidx + 4 < inputLength
181 && reference > 0
182 && input[reference + 0] == input[iidx + 0]
183 && input[reference + 1] == input[iidx + 1]
184 && input[reference + 2] == input[iidx + 2]
185 )
186 {
187 /* match found at *reference++ */
188 uint len = 2;
189 uint maxlen = (uint)inputLength - iidx - len;
190 maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;
191
192 if (oidx + lit + 1 + 3 >= outputLength)
193 return 0;
194
195 do
196 len++;
197 while (len < maxlen && input[reference + len] == input[iidx + len]);
198
199 if (lit != 0)
200 {
201 output[oidx++] = (byte)(lit - 1);
202 lit = -lit;
203 do
204 output[oidx++] = input[iidx + lit];
205 while ((++lit) != 0);
206 }
207
208 len -= 2;
209 iidx++;
210
211 if (len < 7)
212 {
213 output[oidx++] = (byte)((off >> 8) + (len << 5));
214 }
215 else
216 {
217 output[oidx++] = (byte)((off >> 8) + (7 << 5));
218 output[oidx++] = (byte)(len - 7);
219 }
220
221 output[oidx++] = (byte)off;
222
223 iidx += len - 1;
224 hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]);
225
226 hval = (hval << 8) | input[iidx + 2];
227 HashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 - HLOG)) - hval * 5) & (HSIZE - 1))] = iidx;
228 iidx++;
229
230 hval = (hval << 8) | input[iidx + 2];
231 HashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 - HLOG)) - hval * 5) & (HSIZE - 1))] = iidx;
232 iidx++;
233 continue;
234 }
235 }
236 else if (iidx == inputLength)
237 break;
238
239 /* one more literal byte we must copy */
240 lit++;
241 iidx++;
242
243 if (lit == MAX_LIT)
244 {
245 if (oidx + 1 + MAX_LIT >= outputLength)
246 return 0;
247
248 output[oidx++] = (byte)(MAX_LIT - 1);
249 lit = -lit;
250 do
251 output[oidx++] = input[iidx + lit];
252 while ((++lit) != 0);
253 }
254 }
255
256 if (lit != 0)
257 {
258 if (oidx + lit + 1 >= outputLength)
259 return 0;
260
261 output[oidx++] = (byte)(lit - 1);
262 lit = -lit;
263 do
264 output[oidx++] = input[iidx + lit];
265 while ((++lit) != 0);
266 }
267
268 return (int)oidx;
269 }
270
271
278 public static int lzf_decompress(byte[] input, ref byte[] output)
279 {
280 int inputLength = input.Length;
281 int outputLength = output.Length;
282
283 uint iidx = 0;
284 uint oidx = 0;
285
286 do
287 {
288 uint ctrl = input[iidx++];
289
290 if (ctrl < (1 << 5)) /* literal run */
291 {
292 ctrl++;
293
294 if (oidx + ctrl > outputLength)
295 {
296 //SET_ERRNO (E2BIG);
297 return 0;
298 }
299
300 do
301 output[oidx++] = input[iidx++];
302 while ((--ctrl) != 0);
303 }
304 else /* back reference */
305 {
306 uint len = ctrl >> 5;
307
308 int reference = (int)(oidx - ((ctrl & 0x1f) << 8) - 1);
309
310 if (len == 7)
311 len += input[iidx++];
312
313 reference -= input[iidx++];
314
315 if (oidx + len + 2 > outputLength)
316 {
317 //SET_ERRNO (E2BIG);
318 return 0;
319 }
320
321 if (reference < 0)
322 {
323 //SET_ERRNO (EINVAL);
324 return 0;
325 }
326
327 output[oidx++] = output[reference++];
328 output[oidx++] = output[reference++];
329
330 do
331 output[oidx++] = output[reference++];
332 while ((--len) != 0);
333 }
334 }
335 while (iidx < inputLength);
336
337 return (int)oidx;
338 }
339 }
340}
Credit Erdener Gonenc - @PixelEnvision.