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