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