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
120static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length,
121					   void *output);
122static 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
137static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length,
138					   void *output);
139static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void *input, int length,
140					     void *output, int maxout);
141#include "fastlz.c"
142
143int 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
153int 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
167int 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
181static 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
273match:
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
394literal:
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
429static 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