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