1 /* lzo1c_9x.c -- implementation of the LZO1C-999 compression algorithm
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
6 Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
7 Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
8 Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
9 Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
10 Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
11 Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
12 Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
13 Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
14 Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
15 Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
16 Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
17 Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
18 All Rights Reserved.
19
20 The LZO library is free software; you can redistribute it and/or
21 modify it under the terms of the GNU General Public License as
22 published by the Free Software Foundation; either version 2 of
23 the License, or (at your option) any later version.
24
25 The LZO library is distributed in the hope that it will be useful,
26 but WITHOUT ANY WARRANTY; without even the implied warranty of
27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 GNU General Public License for more details.
29
30 You should have received a copy of the GNU General Public License
31 along with the LZO library; see the file COPYING.
32 If not, write to the Free Software Foundation, Inc.,
33 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
34
35 Markus F.X.J. Oberhumer
36 <markus@oberhumer.com>
37 http://www.oberhumer.com/opensource/lzo/
38 */
39
40
41 #include "config1c.h"
42
43
44 /***********************************************************************
45 //
46 ************************************************************************/
47
48 #define N 16383 /* size of ring buffer */
49 #define THRESHOLD 2 /* lower limit for match length */
50 #define F 2048 /* upper limit for match length */
51
52
53 #define LZO1C
54 #define LZO_COMPRESS_T lzo1c_999_t
55 #define lzo_swd_t lzo1c_999_swd_t
56 #include "lzo_mchw.ch"
57
58
59
60 /***********************************************************************
61 //
62 ************************************************************************/
63
64 static lzo_bytep
code_match(LZO_COMPRESS_T * c,lzo_bytep op,lzo_uint m_len,lzo_uint m_off)65 code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
66 {
67 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
68 {
69 assert(m_len >= M2_MIN_LEN);
70 assert(m_off >= M2_MIN_OFFSET);
71
72 m_off -= M2_MIN_OFFSET;
73 /* code match len + low offset bits */
74 *op++ = LZO_BYTE(((m_len - (M2_MIN_LEN - 2)) << M2O_BITS) |
75 (m_off & M2O_MASK));
76 /* code high offset bits */
77 *op++ = LZO_BYTE(m_off >> M2O_BITS);
78 c->m2_m++;
79 }
80 else
81 {
82 assert(m_len >= M3_MIN_LEN);
83 assert(m_off <= M3_MAX_OFFSET);
84
85 m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
86 /* code match len */
87 if (m_len <= M3_MAX_LEN)
88 *op++ = LZO_BYTE(M3_MARKER | (m_len - (M3_MIN_LEN - 1)));
89 else
90 {
91 assert(m_len >= M4_MIN_LEN);
92 /* code M4 match len flag */
93 *op++ = M4_MARKER;
94 /* code match len */
95 m_len -= M4_MIN_LEN - 1;
96 while (m_len > 255)
97 {
98 m_len -= 255;
99 *op++ = 0;
100 }
101 assert(m_len > 0);
102 *op++ = LZO_BYTE(m_len);
103 }
104 /* code low offset bits */
105 *op++ = LZO_BYTE(m_off & M3O_MASK);
106 /* code high offset bits */
107 *op++ = LZO_BYTE(m_off >> M3O_BITS);
108
109 c->r1_m_len = 0;
110 c->m3 = op;
111 c->m3_m++;
112 }
113 return op;
114 }
115
116
117 /***********************************************************************
118 // this is a public function, but there is no prototype in a header file
119 ************************************************************************/
120
121 LZO_EXTERN(int)
122 lzo1c_999_compress_callback ( const lzo_bytep in , lzo_uint in_len,
123 lzo_bytep out, lzo_uintp out_len,
124 lzo_voidp wrkmem,
125 lzo_callback_p cb,
126 lzo_uint max_chain );
127
128 LZO_PUBLIC(int)
lzo1c_999_compress_callback(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem,lzo_callback_p cb,lzo_uint max_chain)129 lzo1c_999_compress_callback ( const lzo_bytep in , lzo_uint in_len,
130 lzo_bytep out, lzo_uintp out_len,
131 lzo_voidp wrkmem,
132 lzo_callback_p cb,
133 lzo_uint max_chain )
134 {
135 lzo_bytep op;
136 const lzo_bytep ii;
137 lzo_uint lit;
138 lzo_uint m_len, m_off;
139 LZO_COMPRESS_T cc;
140 LZO_COMPRESS_T * const c = &cc;
141 lzo_swd_p const swd = (lzo_swd_p) wrkmem;
142 int r;
143
144 /* sanity check */
145 LZO_COMPILE_TIME_ASSERT(LZO1C_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
146
147 c->init = 0;
148 c->ip = c->in = in;
149 c->in_end = in + in_len;
150 c->cb = cb;
151 c->r1_r = c->m3_r = c->m2_m = c->m3_m = 0;
152
153 op = out;
154 ii = c->ip; /* point to start of literal run */
155 lit = 0;
156 c->r1_m_len = 0;
157 c->m3 = out + 1; /* pointer after last m3/m4 match */
158
159 r = init_match(c,swd,NULL,0,0);
160 if (r != 0)
161 return r;
162 if (max_chain > 0)
163 swd->max_chain = max_chain;
164
165 r = find_match(c,swd,0,0);
166 if (r != 0)
167 return r;
168 while (c->look > 0)
169 {
170 int lazy_match_min_gain = -1;
171 lzo_uint ahead = 0;
172
173 m_len = c->m_len;
174 m_off = c->m_off;
175
176 #if 0
177 printf("%5ld: %5d len:%3d off:%5d\n", (c->ip-c->look)-in, c->look,
178 m_len, m_off);
179 #endif
180
181 assert(c->ip - c->look >= in);
182 if (lit == 0)
183 ii = c->ip - c->look;
184 assert(ii + lit == c->ip - c->look);
185 assert(swd->b_char == *(c->ip - c->look));
186
187 if ((m_len < M2_MIN_LEN) ||
188 (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
189 {
190 m_len = 0;
191 }
192 else
193 {
194 assert(c->ip - c->look - m_off >= in);
195 assert(c->ip - c->look - m_off + m_len < c->ip);
196 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
197 m_len) == 0);
198
199 if (lit > 0)
200 {
201 /* we have a current literal run: do not try a lazy match,
202 if the literal could be coded into a r1 or m3 match */
203 if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
204 lazy_match_min_gain = -1;
205 else if (lit == 3 && op == c->m3)
206 lazy_match_min_gain = -1;
207 else if (lit < 3 && op == c->m3)
208 lazy_match_min_gain = 0;
209 else
210 lazy_match_min_gain = 1;
211
212 #if (M2_MIN_LEN == 2)
213 if (m_len == 2)
214 {
215 /* don't code a match of len 2 if we have to
216 code a literal run. Code a literal instead. */
217 m_len = 0;
218 }
219 #endif
220 #if (M2_MIN_LEN == M3_MIN_LEN)
221 if (m_len == M2_MIN_LEN && m_off > M2_MAX_OFFSET)
222 {
223 /* don't code a M3 match of len 3 if we have to
224 code a literal run. Code a literal instead. */
225 m_len = 0;
226 }
227 #endif
228 }
229 else
230 {
231 /* no current literal run: only try a lazy match,
232 if the literal could be coded into a r1 or m3 match */
233 if (c->r1_m_len == M2_MIN_LEN || op == c->m3)
234 lazy_match_min_gain = 0;
235 else
236 lazy_match_min_gain = -1;
237 }
238 }
239
240
241 /* try a lazy match */
242 if (m_len == 0)
243 lazy_match_min_gain = -1;
244 if (lazy_match_min_gain >= 0 && c->look > m_len)
245 {
246 assert(m_len > 0);
247
248 r = find_match(c,swd,1,0);
249 assert(r == 0);
250 assert(c->look > 0);
251
252 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
253 c->m_off > M2_MAX_OFFSET)
254 lazy_match_min_gain += 1;
255
256 if (c->m_len >= m_len + lazy_match_min_gain)
257 {
258 c->lazy++;
259 #if !defined(NDEBUG)
260 m_len = c->m_len;
261 m_off = c->m_off;
262 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
263 m_len) == 0);
264 #endif
265 lit++;
266 assert(ii + lit == c->ip - c->look);
267 continue;
268 }
269 else
270 {
271 ahead = 1;
272 assert(ii + lit + 1 == c->ip - c->look);
273 }
274 assert(m_len > 0);
275 }
276 assert(ii + lit + ahead == c->ip - c->look);
277
278
279 if (m_len == 0)
280 {
281 /* a literal */
282 lit++;
283 r = find_match(c,swd,1,0);
284 assert(r == 0);
285 }
286 else
287 {
288 /* 1 - store run */
289 if (lit > 0)
290 {
291 /* code current literal run */
292 if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
293 {
294 /* Code a context sensitive R1 match. */
295 assert((op[-2] >> M2O_BITS) == (M2_MARKER >> M2O_BITS));
296 op[-2] &= M2O_MASK;
297 assert((op[-2] >> M2O_BITS) == 0);
298 /* copy 1 literal */
299 *op++ = *ii++;
300 assert(ii + ahead == c->ip - c->look);
301 c->r1_r++;
302 }
303 else if (lit < 4 && op == c->m3)
304 {
305 assert((c->m3[-2] >> M3O_BITS) == 0);
306 c->m3[-2] |= LZO_BYTE(lit << M3O_BITS);
307 MEMCPY_DS(op, ii, lit);
308 assert(ii + ahead == c->ip - c->look);
309 c->m3_r++;
310 }
311 else
312 {
313 op = STORE_RUN(op,ii,lit);
314 }
315 if (lit < R0FAST)
316 c->r1_m_len = m_len;
317 else
318 c->r1_m_len = 0;
319 lit = 0;
320 }
321 else
322 c->r1_m_len = 0;
323
324 /* 2 - code match */
325 op = code_match(c,op,m_len,m_off);
326 r = find_match(c,swd,m_len,1+ahead);
327 assert(r == 0);
328 }
329
330 c->codesize = pd(op, out);
331 }
332
333
334 /* store final run */
335 if (lit > 0)
336 op = STORE_RUN(op,ii,lit);
337
338 #if defined(LZO_EOF_CODE)
339 *op++ = M3_MARKER | 1;
340 *op++ = 0;
341 *op++ = 0;
342 #endif
343
344 c->codesize = pd(op, out);
345 assert(c->textsize == in_len);
346
347 *out_len = pd(op, out);
348
349 if (c->cb && c->cb->nprogress)
350 (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
351
352 #if 0
353 printf("%ld %ld -> %ld: %ld %ld %ld %ld %ld\n",
354 (long) c->textsize, (long)in_len, (long) c->codesize,
355 c->r1_r, c->m3_r, c->m2_m, c->m3_m, c->lazy);
356 #endif
357 return LZO_E_OK;
358 }
359
360
361
362 /***********************************************************************
363 //
364 ************************************************************************/
365
366 LZO_PUBLIC(int)
lzo1c_999_compress(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem)367 lzo1c_999_compress ( const lzo_bytep in , lzo_uint in_len,
368 lzo_bytep out, lzo_uintp out_len,
369 lzo_voidp wrkmem )
370 {
371 return lzo1c_999_compress_callback(in,in_len,out,out_len,wrkmem,
372 (lzo_callback_p) 0, 0);
373 }
374
375
376 /*
377 vi:ts=4:et
378 */
379
380