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 #include "fastlz/fastlz.h"
28
29 #if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
30
31 /*
32 * Always check for bound when decompressing.
33 * Generally it is best to leave it defined.
34 */
35 #define FASTLZ_SAFE
36
37 /*
38 * Give hints to the compiler for branch prediction optimization.
39 */
40 #if defined(__GNUC__) && (__GNUC__ > 2)
41 #define FASTLZ_EXPECT_CONDITIONAL(c) (__builtin_expect((c), 1))
42 #define FASTLZ_UNEXPECT_CONDITIONAL(c) (__builtin_expect((c), 0))
43 #else
44 #define FASTLZ_EXPECT_CONDITIONAL(c) (c)
45 #define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
46 #endif
47
48 /*
49 * Use inlined functions for supported systems.
50 */
51 #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
52 #define FASTLZ_INLINE inline
53 #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
54 #define FASTLZ_INLINE __inline
55 #else
56 #define FASTLZ_INLINE
57 #endif
58
59 /*
60 * Prevent accessing more than 8-bit at once, except on x86 architectures.
61 */
62 #if !defined(FASTLZ_STRICT_ALIGN)
63 #define FASTLZ_STRICT_ALIGN
64 #if defined(__i386__) || defined(__386) /* GNU C, Sun Studio */
65 #undef FASTLZ_STRICT_ALIGN
66 #elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
67 #undef FASTLZ_STRICT_ALIGN
68 #elif defined(_M_IX86) /* Intel, MSVC */
69 #undef FASTLZ_STRICT_ALIGN
70 #elif defined(__386)
71 #undef FASTLZ_STRICT_ALIGN
72 #elif defined(_X86_) /* MinGW */
73 #undef FASTLZ_STRICT_ALIGN
74 #elif defined(__I86__) /* Digital Mars */
75 #undef FASTLZ_STRICT_ALIGN
76 #endif
77 #endif
78
79 /*
80 * FIXME: use preprocessor magic to set this on different platforms!
81 */
82 typedef unsigned char flzuint8;
83 typedef unsigned short flzuint16;
84 typedef unsigned int flzuint32;
85
86 /* prototypes */
87 int fastlz_compress(const void* input, int length, void* output);
88 int fastlz_compress_level(int level, const void* input, int length, void* output);
89 int fastlz_decompress(const void* input, int length, void* output, int maxout);
90
91 #define MAX_COPY 32
92 #define MAX_LEN 264 /* 256 + 8 */
93 #define MAX_DISTANCE 8192
94
95 #if !defined(FASTLZ_STRICT_ALIGN)
96 #define FASTLZ_READU16(p) *((const flzuint16*)(p))
97 #else
98 #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
99 #endif
100
101 #define HASH_LOG 13
102 #define HASH_SIZE (1<< HASH_LOG)
103 #define HASH_MASK (HASH_SIZE-1)
104 #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
105
106 #undef FASTLZ_LEVEL
107 #define FASTLZ_LEVEL 1
108
109 #undef FASTLZ_COMPRESSOR
110 #undef FASTLZ_DECOMPRESSOR
111 #define FASTLZ_COMPRESSOR fastlz1_compress
112 #define FASTLZ_DECOMPRESSOR fastlz1_decompress
113 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
114 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
115 #include "fastlz.c"
116
117 #undef FASTLZ_LEVEL
118 #define FASTLZ_LEVEL 2
119
120 #undef MAX_DISTANCE
121 #define MAX_DISTANCE 8191
122 #define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
123
124 #undef FASTLZ_COMPRESSOR
125 #undef FASTLZ_DECOMPRESSOR
126 #define FASTLZ_COMPRESSOR fastlz2_compress
127 #define FASTLZ_DECOMPRESSOR fastlz2_decompress
128 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
129 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
130 #include "fastlz.c"
131
fastlz_compress(const void * input,int length,void * output)132 int fastlz_compress(const void* input, int length, void* output)
133 {
134 /* for short block, choose fastlz1 */
135 if(length < 65536)
136 return fastlz1_compress(input, length, output);
137
138 /* else... */
139 return fastlz2_compress(input, length, output);
140 }
141
fastlz_decompress(const void * input,int length,void * output,int maxout)142 int fastlz_decompress(const void* input, int length, void* output, int maxout)
143 {
144 /* magic identifier for compression level */
145 int level = ((*(const flzuint8*)input) >> 5) + 1;
146
147 if(level == 1)
148 return fastlz1_decompress(input, length, output, maxout);
149 if(level == 2)
150 return fastlz2_decompress(input, length, output, maxout);
151
152 /* unknown level, trigger error */
153 return 0;
154 }
155
fastlz_compress_level(int level,const void * input,int length,void * output)156 int fastlz_compress_level(int level, const void* input, int length, void* output)
157 {
158 if(level == 1)
159 return fastlz1_compress(input, length, output);
160 if(level == 2)
161 return fastlz2_compress(input, length, output);
162
163 return 0;
164 }
165
166 #else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
167
FASTLZ_COMPRESSOR(const void * input,int length,void * output)168 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
169 {
170 const flzuint8* ip = (const flzuint8*) input;
171 const flzuint8* ip_bound = ip + length - 2;
172 const flzuint8* ip_limit = ip + length - 12 - 1;
173 flzuint8* op = (flzuint8*) output;
174
175 const flzuint8* htab[HASH_SIZE];
176 const flzuint8** hslot;
177 flzuint32 hval;
178
179 flzuint32 copy;
180
181 /* sanity check */
182 if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
183 {
184 if(length)
185 {
186 /* create literal copy only */
187 *op++ = length-1;
188 ip_bound++;
189 while(ip <= ip_bound)
190 *op++ = *ip++;
191 return length+1;
192 }
193 else
194 return 0;
195 }
196
197 /* initializes hash table */
198 for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
199 *hslot = ip;
200
201 /* we start with literal copy */
202 copy = 2;
203 *op++ = MAX_COPY-1;
204 *op++ = *ip++;
205 *op++ = *ip++;
206
207 /* main loop */
208 while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
209 {
210 const flzuint8* ref;
211 flzuint32 distance;
212
213 /* minimum match length */
214 flzuint32 len = 3;
215
216 /* comparison starting-point */
217 const flzuint8* anchor = ip;
218
219 /* check for a run */
220 #if FASTLZ_LEVEL==2
221 if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
222 {
223 distance = 1;
224 ip += 3;
225 ref = anchor - 1 + 3;
226 goto match;
227 }
228 #endif
229
230 /* find potential match */
231 HASH_FUNCTION(hval,ip);
232 hslot = htab + hval;
233 ref = htab[hval];
234
235 /* calculate distance to the match */
236 distance = anchor - ref;
237
238 /* update hash table */
239 *hslot = anchor;
240
241 /* is this a match? check the first 3 bytes */
242 if(distance==0 ||
243 #if FASTLZ_LEVEL==1
244 (distance >= MAX_DISTANCE) ||
245 #else
246 (distance >= MAX_FARDISTANCE) ||
247 #endif
248 *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
249 goto literal;
250
251 #if FASTLZ_LEVEL==2
252 /* far, needs at least 5-byte match */
253 if(distance >= MAX_DISTANCE)
254 {
255 if(*ip++ != *ref++ || *ip++!= *ref++)
256 goto literal;
257 len += 2;
258 }
259
260 match:
261 #endif
262
263 /* last matched byte */
264 ip = anchor + len;
265
266 /* distance is biased */
267 distance--;
268
269 if(!distance)
270 {
271 /* zero distance means a run */
272 flzuint8 x = ip[-1];
273 while(ip < ip_bound)
274 if(*ref++ != x) break; else ip++;
275 }
276 else
277 for(;;)
278 {
279 /* safe because the outer check against ip limit */
280 if(*ref++ != *ip++) break;
281 if(*ref++ != *ip++) break;
282 if(*ref++ != *ip++) break;
283 if(*ref++ != *ip++) break;
284 if(*ref++ != *ip++) break;
285 if(*ref++ != *ip++) break;
286 if(*ref++ != *ip++) break;
287 if(*ref++ != *ip++) break;
288 while(ip < ip_bound)
289 if(*ref++ != *ip++) break;
290 break;
291 }
292
293 /* if we have copied something, adjust the copy count */
294 if(copy)
295 /* copy is biased, '0' means 1 byte copy */
296 *(op-copy-1) = copy-1;
297 else
298 /* back, to overwrite the copy count */
299 op--;
300
301 /* reset literal counter */
302 copy = 0;
303
304 /* length is biased, '1' means a match of 3 bytes */
305 ip -= 3;
306 len = ip - anchor;
307
308 /* encode the match */
309 #if FASTLZ_LEVEL==2
310 if(distance < MAX_DISTANCE)
311 {
312 if(len < 7)
313 {
314 *op++ = (len << 5) + (distance >> 8);
315 *op++ = (distance & 255);
316 }
317 else
318 {
319 *op++ = (7 << 5) + (distance >> 8);
320 for(len-=7; len >= 255; len-= 255)
321 *op++ = 255;
322 *op++ = len;
323 *op++ = (distance & 255);
324 }
325 }
326 else
327 {
328 /* far away, but not yet in the another galaxy... */
329 if(len < 7)
330 {
331 distance -= MAX_DISTANCE;
332 *op++ = (len << 5) + 31;
333 *op++ = 255;
334 *op++ = distance >> 8;
335 *op++ = distance & 255;
336 }
337 else
338 {
339 distance -= MAX_DISTANCE;
340 *op++ = (7 << 5) + 31;
341 for(len-=7; len >= 255; len-= 255)
342 *op++ = 255;
343 *op++ = len;
344 *op++ = 255;
345 *op++ = distance >> 8;
346 *op++ = distance & 255;
347 }
348 }
349 #else
350
351 if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
352 while(len > MAX_LEN-2)
353 {
354 *op++ = (7 << 5) + (distance >> 8);
355 *op++ = MAX_LEN - 2 - 7 -2;
356 *op++ = (distance & 255);
357 len -= MAX_LEN-2;
358 }
359
360 if(len < 7)
361 {
362 *op++ = (len << 5) + (distance >> 8);
363 *op++ = (distance & 255);
364 }
365 else
366 {
367 *op++ = (7 << 5) + (distance >> 8);
368 *op++ = len - 7;
369 *op++ = (distance & 255);
370 }
371 #endif
372
373 /* update the hash at match boundary */
374 HASH_FUNCTION(hval,ip);
375 htab[hval] = ip++;
376 HASH_FUNCTION(hval,ip);
377 htab[hval] = ip++;
378
379 /* assuming literal copy */
380 *op++ = MAX_COPY-1;
381
382 continue;
383
384 literal:
385 *op++ = *anchor++;
386 ip = anchor;
387 copy++;
388 if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
389 {
390 copy = 0;
391 *op++ = MAX_COPY-1;
392 }
393 }
394
395 /* left-over as literal copy */
396 ip_bound++;
397 while(ip <= ip_bound)
398 {
399 *op++ = *ip++;
400 copy++;
401 if(copy == MAX_COPY)
402 {
403 copy = 0;
404 *op++ = MAX_COPY-1;
405 }
406 }
407
408 /* if we have copied something, adjust the copy length */
409 if(copy)
410 *(op-copy-1) = copy-1;
411 else
412 op--;
413
414 #if FASTLZ_LEVEL==2
415 /* marker for fastlz2 */
416 *(flzuint8*)output |= (1 << 5);
417 #endif
418
419 return op - (flzuint8*)output;
420 }
421
FASTLZ_DECOMPRESSOR(const void * input,int length,void * output,int maxout)422 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
423 {
424 const flzuint8* ip = (const flzuint8*) input;
425 const flzuint8* ip_limit = ip + length;
426 flzuint8* op = (flzuint8*) output;
427 flzuint8* op_limit = op + maxout;
428 flzuint32 ctrl = (*ip++) & 31;
429 int loop = 1;
430
431 do
432 {
433 const flzuint8* ref = op;
434 flzuint32 len = ctrl >> 5;
435 flzuint32 ofs = (ctrl & 31) << 8;
436
437 if(ctrl >= 32)
438 {
439 #if FASTLZ_LEVEL==2
440 flzuint8 code;
441 #endif
442 len--;
443 ref -= ofs;
444 if (len == 7-1)
445 #if FASTLZ_LEVEL==1
446 len += *ip++;
447 ref -= *ip++;
448 #else
449 do
450 {
451 code = *ip++;
452 len += code;
453 } while (code==255);
454 code = *ip++;
455 ref -= code;
456
457 /* match from 16-bit distance */
458 if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
459 if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
460 {
461 ofs = (*ip++) << 8;
462 ofs += *ip++;
463 ref = op - ofs - MAX_DISTANCE;
464 }
465 #endif
466
467 #ifdef FASTLZ_SAFE
468 if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
469 return 0;
470
471 if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
472 return 0;
473 #endif
474
475 if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
476 ctrl = *ip++;
477 else
478 loop = 0;
479
480 if(ref == op)
481 {
482 /* optimize copy for a run */
483 flzuint8 b = ref[-1];
484 *op++ = b;
485 *op++ = b;
486 *op++ = b;
487 for(; len; --len)
488 *op++ = b;
489 }
490 else
491 {
492 #if !defined(FASTLZ_STRICT_ALIGN)
493 const flzuint16* p;
494 flzuint16* q;
495 #endif
496 /* copy from reference */
497 ref--;
498 *op++ = *ref++;
499 *op++ = *ref++;
500 *op++ = *ref++;
501
502 #if !defined(FASTLZ_STRICT_ALIGN)
503 /* copy a byte, so that now it's word aligned */
504 if(len & 1)
505 {
506 *op++ = *ref++;
507 len--;
508 }
509
510 /* copy 16-bit at once */
511 q = (flzuint16*) op;
512 op += len;
513 p = (const flzuint16*) ref;
514 for(len>>=1; len > 4; len-=4)
515 {
516 *q++ = *p++;
517 *q++ = *p++;
518 *q++ = *p++;
519 *q++ = *p++;
520 }
521 for(; len; --len)
522 *q++ = *p++;
523 #else
524 for(; len; --len)
525 *op++ = *ref++;
526 #endif
527 }
528 }
529 else
530 {
531 ctrl++;
532 #ifdef FASTLZ_SAFE
533 if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
534 return 0;
535 if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
536 return 0;
537 #endif
538
539 *op++ = *ip++;
540 for(--ctrl; ctrl; ctrl--)
541 *op++ = *ip++;
542
543 loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
544 if(loop)
545 ctrl = *ip++;
546 }
547 }
548 while(FASTLZ_EXPECT_CONDITIONAL(loop));
549
550 return op - (flzuint8*)output;
551 }
552
553 #endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
554