Line data Source code
1 : /*
2 : FastLZ - lightning-fast lossless compression library
3 :
4 : Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
5 : Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
6 : Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
7 :
8 : Permission is hereby granted, free of charge, to any person obtaining a copy
9 : of this software and associated documentation files (the "Software"), to deal
10 : in the Software without restriction, including without limitation the rights
11 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : copies of the Software, and to permit persons to whom the Software is
13 : furnished to do so, subject to the following conditions:
14 :
15 : The above copyright notice and this permission notice shall be included in
16 : all copies or substantial portions of the Software.
17 :
18 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 : THE SOFTWARE.
25 : */
26 :
27 : #if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
28 :
29 : /*
30 : * Always check for bound when decompressing.
31 : * Generally it is best to leave it defined.
32 : */
33 : #define FASTLZ_SAFE
34 :
35 : /*
36 : * Give hints to the compiler for branch prediction optimization.
37 : */
38 : #if defined(__GNUC__) && (__GNUC__ > 2)
39 : #define FASTLZ_EXPECT_CONDITIONAL(c) (__builtin_expect((c), 1))
40 : #define FASTLZ_UNEXPECT_CONDITIONAL(c) (__builtin_expect((c), 0))
41 : #else
42 : #define FASTLZ_EXPECT_CONDITIONAL(c) (c)
43 : #define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
44 : #endif
45 :
46 : /*
47 : * Use inlined functions for supported systems.
48 : */
49 : #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
50 : #define FASTLZ_INLINE inline
51 : #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
52 : #define FASTLZ_INLINE __inline
53 : #else
54 : #define FASTLZ_INLINE
55 : #endif
56 :
57 : /*
58 : * Prevent accessing more than 8-bit at once, except on x86 architectures.
59 : */
60 : #if !defined(FASTLZ_STRICT_ALIGN)
61 : #define FASTLZ_STRICT_ALIGN
62 : #if defined(__i386__) || defined(__386) /* GNU C, Sun Studio */
63 : #undef FASTLZ_STRICT_ALIGN
64 : #elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
65 : #undef FASTLZ_STRICT_ALIGN
66 : #elif defined(_M_IX86) /* Intel, MSVC */
67 : #undef FASTLZ_STRICT_ALIGN
68 : #elif defined(__386)
69 : #undef FASTLZ_STRICT_ALIGN
70 : #elif defined(_X86_) /* MinGW */
71 : #undef FASTLZ_STRICT_ALIGN
72 : #elif defined(__I86__) /* Digital Mars */
73 : #undef FASTLZ_STRICT_ALIGN
74 : #endif
75 : #endif
76 :
77 : /*
78 : * FIXME: use preprocessor magic to set this on different platforms!
79 : */
80 : typedef unsigned char flzuint8;
81 : typedef unsigned short flzuint16;
82 : typedef unsigned int flzuint32;
83 :
84 : /* prototypes */
85 : int fastlz_compress(const void* input, int length, void* output);
86 : int fastlz_compress_level(int level, const void* input, int length, void* output);
87 : int fastlz_decompress(const void* input, int length, void* output, int maxout);
88 :
89 : #define MAX_COPY 32
90 : #define MAX_LEN 264 /* 256 + 8 */
91 : #define MAX_DISTANCE 8192
92 :
93 : #if !defined(FASTLZ_STRICT_ALIGN)
94 : #define FASTLZ_READU16(p) *((const flzuint16*)(p))
95 : #else
96 : #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
97 : #endif
98 :
99 : #define HASH_LOG 13
100 : #define HASH_SIZE (1<< HASH_LOG)
101 : #define HASH_MASK (HASH_SIZE-1)
102 : #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
103 :
104 : #undef FASTLZ_LEVEL
105 : #define FASTLZ_LEVEL 1
106 :
107 : #undef FASTLZ_COMPRESSOR
108 : #undef FASTLZ_DECOMPRESSOR
109 : #define FASTLZ_COMPRESSOR fastlz1_compress
110 : #define FASTLZ_DECOMPRESSOR fastlz1_decompress
111 : static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
112 : static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
113 : #include "fastlz.c"
114 :
115 : #undef FASTLZ_LEVEL
116 : #define FASTLZ_LEVEL 2
117 :
118 : #undef MAX_DISTANCE
119 : #define MAX_DISTANCE 8191
120 : #define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
121 :
122 : #undef FASTLZ_COMPRESSOR
123 : #undef FASTLZ_DECOMPRESSOR
124 : #define FASTLZ_COMPRESSOR fastlz2_compress
125 : #define FASTLZ_DECOMPRESSOR fastlz2_decompress
126 : static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
127 : static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
128 : #include "fastlz.c"
129 :
130 76 : int fastlz_compress(const void* input, int length, void* output)
131 : {
132 : /* for short block, choose fastlz1 */
133 76 : if(length < 65536)
134 2 : return fastlz1_compress(input, length, output);
135 :
136 : /* else... */
137 74 : return fastlz2_compress(input, length, output);
138 : }
139 :
140 76 : int fastlz_decompress(const void* input, int length, void* output, int maxout)
141 : {
142 : /* magic identifier for compression level */
143 76 : int level = ((*(const flzuint8*)input) >> 5) + 1;
144 :
145 76 : if(level == 1)
146 2 : return fastlz1_decompress(input, length, output, maxout);
147 74 : if(level == 2)
148 74 : return fastlz2_decompress(input, length, output, maxout);
149 :
150 : /* unknown level, trigger error */
151 0 : return 0;
152 : }
153 :
154 0 : int fastlz_compress_level(int level, const void* input, int length, void* output)
155 : {
156 0 : if(level == 1)
157 0 : return fastlz1_compress(input, length, output);
158 0 : if(level == 2)
159 0 : return fastlz2_compress(input, length, output);
160 :
161 0 : return 0;
162 : }
163 :
164 : #else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
165 :
166 76 : static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
167 : {
168 76 : const flzuint8* ip = (const flzuint8*) input;
169 76 : const flzuint8* ip_bound = ip + length - 2;
170 76 : const flzuint8* ip_limit = ip + length - 12;
171 76 : flzuint8* op = (flzuint8*) output;
172 :
173 : const flzuint8* htab[HASH_SIZE];
174 : const flzuint8** hslot;
175 : flzuint32 hval;
176 :
177 : flzuint32 copy;
178 :
179 : /* sanity check */
180 76 : if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
181 : {
182 0 : if(length)
183 : {
184 : /* create literal copy only */
185 0 : *op++ = length-1;
186 0 : ip_bound++;
187 0 : while(ip <= ip_bound)
188 0 : *op++ = *ip++;
189 0 : return length+1;
190 : }
191 : else
192 0 : return 0;
193 : }
194 :
195 : /* initializes hash table */
196 622668 : for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
197 622592 : *hslot = ip;
198 :
199 : /* we start with literal copy */
200 76 : copy = 2;
201 76 : *op++ = MAX_COPY-1;
202 76 : *op++ = *ip++;
203 76 : *op++ = *ip++;
204 :
205 : /* main loop */
206 417712710 : while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
207 : {
208 : const flzuint8* ref;
209 : flzuint32 distance;
210 :
211 : /* minimum match length */
212 417712558 : flzuint32 len = 3;
213 :
214 : /* comparison starting-point */
215 417712558 : const flzuint8* anchor = ip;
216 :
217 : /* check for a run */
218 : #if FASTLZ_LEVEL==2
219 417691084 : if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
220 : {
221 119030 : distance = 1;
222 119030 : ip += 3;
223 119030 : ref = anchor - 1 + 3;
224 119030 : goto match;
225 : }
226 : #endif
227 :
228 : /* find potential match */
229 417593528 : HASH_FUNCTION(hval,ip);
230 417593528 : hslot = htab + hval;
231 417593528 : ref = htab[hval];
232 :
233 : /* calculate distance to the match */
234 417593528 : distance = anchor - ref;
235 :
236 : /* update hash table */
237 417593528 : *hslot = anchor;
238 :
239 : /* is this a match? check the first 3 bytes */
240 417593528 : if(distance==0 ||
241 : #if FASTLZ_LEVEL==1
242 14184 : (distance >= MAX_DISTANCE) ||
243 : #else
244 413637730 : (distance >= MAX_FARDISTANCE) ||
245 : #endif
246 546380422 : *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
247 : goto literal;
248 :
249 : #if FASTLZ_LEVEL==2
250 : /* far, needs at least 5-byte match */
251 124171778 : if(distance >= MAX_DISTANCE)
252 : {
253 8305690 : if(*ip++ != *ref++ || *ip++!= *ref++)
254 : goto literal;
255 1647174 : len += 2;
256 : }
257 :
258 : match:
259 : #endif
260 :
261 : /* last matched byte */
262 117640706 : ip = anchor + len;
263 :
264 : /* distance is biased */
265 117640706 : distance--;
266 :
267 117640706 : if(!distance)
268 : {
269 : /* zero distance means a run */
270 119432 : flzuint8 x = ip[-1];
271 1068990 : while(ip < ip_bound)
272 949558 : if(*ref++ != x) break; else ip++;
273 : }
274 : else
275 : for(;;)
276 : {
277 : /* safe because the outer check against ip limit */
278 117521274 : if(*ref++ != *ip++) break;
279 71870972 : if(*ref++ != *ip++) break;
280 41072298 : if(*ref++ != *ip++) break;
281 25379470 : if(*ref++ != *ip++) break;
282 18977954 : if(*ref++ != *ip++) break;
283 13217458 : if(*ref++ != *ip++) break;
284 9109480 : if(*ref++ != *ip++) break;
285 6900566 : if(*ref++ != *ip++) break;
286 31439700 : while(ip < ip_bound)
287 26483824 : if(*ref++ != *ip++) break;
288 4955856 : break;
289 : }
290 :
291 : /* if we have copied something, adjust the copy count */
292 117640706 : if(copy)
293 : /* copy is biased, '0' means 1 byte copy */
294 29529692 : *(op-copy-1) = copy-1;
295 : else
296 : /* back, to overwrite the copy count */
297 88111014 : op--;
298 :
299 : /* reset literal counter */
300 117640706 : copy = 0;
301 :
302 : /* length is biased, '1' means a match of 3 bytes */
303 117640706 : ip -= 3;
304 117640706 : len = ip - anchor;
305 :
306 : /* encode the match */
307 : #if FASTLZ_LEVEL==2
308 117632292 : if(distance < MAX_DISTANCE)
309 : {
310 115985212 : if(len < 7)
311 : {
312 107018052 : *op++ = (len << 5) + (distance >> 8);
313 107018052 : *op++ = (distance & 255);
314 : }
315 : else
316 : {
317 8967160 : *op++ = (7 << 5) + (distance >> 8);
318 8971022 : for(len-=7; len >= 255; len-= 255)
319 3862 : *op++ = 255;
320 8967160 : *op++ = len;
321 8967160 : *op++ = (distance & 255);
322 : }
323 : }
324 : else
325 : {
326 : /* far away, but not yet in the another galaxy... */
327 1647080 : if(len < 7)
328 : {
329 1418632 : distance -= MAX_DISTANCE;
330 1418632 : *op++ = (len << 5) + 31;
331 1418632 : *op++ = 255;
332 1418632 : *op++ = distance >> 8;
333 1418632 : *op++ = distance & 255;
334 : }
335 : else
336 : {
337 228448 : distance -= MAX_DISTANCE;
338 228448 : *op++ = (7 << 5) + 31;
339 231418 : for(len-=7; len >= 255; len-= 255)
340 2970 : *op++ = 255;
341 228448 : *op++ = len;
342 228448 : *op++ = 255;
343 228448 : *op++ = distance >> 8;
344 228448 : *op++ = distance & 255;
345 : }
346 : }
347 : #else
348 :
349 8414 : if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
350 28 : while(len > MAX_LEN-2)
351 : {
352 24 : *op++ = (7 << 5) + (distance >> 8);
353 24 : *op++ = MAX_LEN - 2 - 7 -2;
354 24 : *op++ = (distance & 255);
355 24 : len -= MAX_LEN-2;
356 : }
357 :
358 8414 : if(len < 7)
359 : {
360 7428 : *op++ = (len << 5) + (distance >> 8);
361 7428 : *op++ = (distance & 255);
362 : }
363 : else
364 : {
365 986 : *op++ = (7 << 5) + (distance >> 8);
366 986 : *op++ = len - 7;
367 986 : *op++ = (distance & 255);
368 : }
369 : #endif
370 :
371 : /* update the hash at match boundary */
372 117640706 : HASH_FUNCTION(hval,ip);
373 117640706 : htab[hval] = ip++;
374 117640706 : HASH_FUNCTION(hval,ip);
375 117640706 : htab[hval] = ip++;
376 :
377 : /* assuming literal copy */
378 117640706 : *op++ = MAX_COPY-1;
379 :
380 117640706 : continue;
381 :
382 : literal:
383 300071852 : *op++ = *anchor++;
384 300071852 : ip = anchor;
385 300071852 : copy++;
386 300071852 : if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
387 : {
388 6489432 : copy = 0;
389 6489432 : *op++ = MAX_COPY-1;
390 : }
391 : }
392 :
393 : /* left-over as literal copy */
394 76 : ip_bound++;
395 744 : while(ip <= ip_bound)
396 : {
397 592 : *op++ = *ip++;
398 592 : copy++;
399 592 : if(copy == MAX_COPY)
400 : {
401 12 : copy = 0;
402 12 : *op++ = MAX_COPY-1;
403 : }
404 : }
405 :
406 : /* if we have copied something, adjust the copy length */
407 76 : if(copy)
408 74 : *(op-copy-1) = copy-1;
409 : else
410 2 : op--;
411 :
412 : #if FASTLZ_LEVEL==2
413 : /* marker for fastlz2 */
414 74 : *(flzuint8*)output |= (1 << 5);
415 : #endif
416 :
417 76 : return op - (flzuint8*)output;
418 : }
419 :
420 76 : static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
421 : {
422 76 : const flzuint8* ip = (const flzuint8*) input;
423 76 : const flzuint8* ip_limit = ip + length;
424 76 : flzuint8* op = (flzuint8*) output;
425 76 : flzuint8* op_limit = op + maxout;
426 76 : flzuint32 ctrl = (*ip++) & 31;
427 76 : int loop = 1;
428 :
429 : do
430 : {
431 153659940 : const flzuint8* ref = op;
432 153659940 : flzuint32 len = ctrl >> 5;
433 153659940 : flzuint32 ofs = (ctrl & 31) << 8;
434 :
435 153659940 : if(ctrl >= 32)
436 : {
437 : #if FASTLZ_LEVEL==2
438 : flzuint8 code;
439 : #endif
440 117640730 : len--;
441 117640730 : ref -= ofs;
442 117640730 : if (len == 7-1)
443 : #if FASTLZ_LEVEL==1
444 1010 : len += *ip++;
445 8438 : ref -= *ip++;
446 : #else
447 : do
448 : {
449 9202440 : code = *ip++;
450 9202440 : len += code;
451 9202440 : } while (code==255);
452 117632292 : code = *ip++;
453 117632292 : ref -= code;
454 :
455 : /* match from 16-bit distance */
456 117632292 : if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
457 2076326 : if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
458 : {
459 1647080 : ofs = (*ip++) << 8;
460 1647080 : ofs += *ip++;
461 1647080 : ref = op - ofs - MAX_DISTANCE;
462 : }
463 : #endif
464 :
465 : #ifdef FASTLZ_SAFE
466 117640730 : if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
467 0 : return 0;
468 :
469 117640730 : if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
470 0 : return 0;
471 : #endif
472 :
473 117640730 : if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
474 117640730 : ctrl = *ip++;
475 : else
476 0 : loop = 0;
477 :
478 117640730 : if(ref == op)
479 : {
480 : /* optimize copy for a run */
481 119456 : flzuint8 b = ref[-1];
482 119456 : *op++ = b;
483 119456 : *op++ = b;
484 119456 : *op++ = b;
485 830078 : for(; len; --len)
486 710622 : *op++ = b;
487 : }
488 : else
489 : {
490 : #if !defined(FASTLZ_STRICT_ALIGN)
491 : const flzuint16* p;
492 : flzuint16* q;
493 : #endif
494 : /* copy from reference */
495 117521274 : ref--;
496 117521274 : *op++ = *ref++;
497 117521274 : *op++ = *ref++;
498 117521274 : *op++ = *ref++;
499 :
500 : #if !defined(FASTLZ_STRICT_ALIGN)
501 : /* copy a byte, so that now it's word aligned */
502 : if(len & 1)
503 : {
504 : *op++ = *ref++;
505 : len--;
506 : }
507 :
508 : /* copy 16-bit at once */
509 : q = (flzuint16*) op;
510 : op += len;
511 : p = (const flzuint16*) ref;
512 : for(len>>=1; len > 4; len-=4)
513 : {
514 : *q++ = *p++;
515 : *q++ = *p++;
516 : *q++ = *p++;
517 : *q++ = *p++;
518 : }
519 : for(; len; --len)
520 : *q++ = *p++;
521 : #else
522 333827644 : for(; len; --len)
523 216306370 : *op++ = *ref++;
524 : #endif
525 : }
526 : }
527 : else
528 : {
529 36019210 : ctrl++;
530 : #ifdef FASTLZ_SAFE
531 36019210 : if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
532 0 : return 0;
533 36019210 : if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
534 0 : return 0;
535 : #endif
536 :
537 36019210 : *op++ = *ip++;
538 300072596 : for(--ctrl; ctrl; ctrl--)
539 264053386 : *op++ = *ip++;
540 :
541 36019210 : loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
542 36019210 : if(loop)
543 36019134 : ctrl = *ip++;
544 : }
545 : }
546 153659940 : while(FASTLZ_EXPECT_CONDITIONAL(loop));
547 :
548 76 : return op - (flzuint8*)output;
549 : }
550 :
551 : #endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
|
