1 /* lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
6 All Rights Reserved.
7
8 The LZO library is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of
11 the License, or (at your option) any later version.
12
13 The LZO library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with the LZO library; see the file COPYING.
20 If not, write to the Free Software Foundation, Inc.,
21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22
23 Markus F.X.J. Oberhumer
24 <markus@oberhumer.com>
25 http://www.oberhumer.com/opensource/lzo/
26 */
27
28
29 #if !defined(LZO1X) && !defined(LZO1Y) && !defined(LZO1Z)
30 # define LZO1X 1
31 #endif
32
33 #if defined(LZO1X)
34 # include "config1x.h"
35 #elif defined(LZO1Y)
36 # include "config1y.h"
37 #elif defined(LZO1Z)
38 # include "config1z.h"
39 #else
40 # error
41 #endif
42
43
44 /***********************************************************************
45 //
46 ************************************************************************/
47
48 #define SWD_N M4_MAX_OFFSET /* size of ring buffer */
49 #define SWD_THRESHOLD 1 /* lower limit for match length */
50 #define SWD_F 2048 /* upper limit for match length */
51
52 #define SWD_BEST_OFF (LZO_MAX3( M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN ) + 1)
53
54 #if defined(LZO1X)
55 # define LZO_COMPRESS_T lzo1x_999_t
56 # define lzo_swd_t lzo1x_999_swd_t
57 #elif defined(LZO1Y)
58 # define LZO_COMPRESS_T lzo1y_999_t
59 # define lzo_swd_t lzo1y_999_swd_t
60 # define lzo1x_999_compress_internal lzo1y_999_compress_internal
61 # define lzo1x_999_compress_dict lzo1y_999_compress_dict
62 # define lzo1x_999_compress_level lzo1y_999_compress_level
63 # define lzo1x_999_compress lzo1y_999_compress
64 #elif defined(LZO1Z)
65 # define LZO_COMPRESS_T lzo1z_999_t
66 # define lzo_swd_t lzo1z_999_swd_t
67 # define lzo1x_999_compress_internal lzo1z_999_compress_internal
68 # define lzo1x_999_compress_dict lzo1z_999_compress_dict
69 # define lzo1x_999_compress_level lzo1z_999_compress_level
70 # define lzo1x_999_compress lzo1z_999_compress
71 #else
72 # error
73 #endif
74
75 #if 0
76 # define HEAD3(b,p) \
77 ((((((lzo_xint)b[p]<<3)^b[p+1])<<3)^b[p+2]) & (SWD_HSIZE-1))
78 #endif
79 #if 0 && (LZO_OPT_UNALIGNED32) && (LZO_ABI_LITTLE_ENDIAN)
80 # define HEAD3(b,p) \
81 (((* (lzo_uint32_tp) &b[p]) ^ ((* (lzo_uint32_tp) &b[p])>>10)) & (SWD_HSIZE-1))
82 #endif
83
84 #include "lzo_mchw.ch"
85
86
87 /* this is a public functions, but there is no prototype in a header file */
88 LZO_EXTERN(int)
89 lzo1x_999_compress_internal ( const lzo_bytep in , lzo_uint in_len,
90 lzo_bytep out, lzo_uintp out_len,
91 lzo_voidp wrkmem,
92 const lzo_bytep dict, lzo_uint dict_len,
93 lzo_callback_p cb,
94 int try_lazy_parm,
95 lzo_uint good_length,
96 lzo_uint max_lazy,
97 lzo_uint nice_length,
98 lzo_uint max_chain,
99 lzo_uint32_t flags );
100
101
102 /***********************************************************************
103 //
104 ************************************************************************/
105
106 static lzo_bytep
code_match(LZO_COMPRESS_T * c,lzo_bytep op,lzo_uint m_len,lzo_uint m_off)107 code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
108 {
109 lzo_uint x_len = m_len;
110 lzo_uint x_off = m_off;
111
112 c->match_bytes += (unsigned long) m_len;
113
114 #if 0
115 /*
116 static lzo_uint last_m_len = 0, last_m_off = 0;
117 static lzo_uint prev_m_off[4];
118 static unsigned prev_m_off_ptr = 0;
119 unsigned i;
120
121 //if (m_len >= 3 && m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
122 if (m_len >= 3 && m_len <= M2_MAX_LEN)
123 {
124 //if (m_len == last_m_len && m_off == last_m_off)
125 //printf("last_m_len + last_m_off\n");
126 //else
127 if (m_off == last_m_off)
128 printf("last_m_off\n");
129 else
130 {
131 for (i = 0; i < 4; i++)
132 if (m_off == prev_m_off[i])
133 printf("prev_m_off %u: %5ld\n",i,(long)m_off);
134 }
135 }
136 last_m_len = m_len;
137 last_m_off = prev_m_off[prev_m_off_ptr] = m_off;
138 prev_m_off_ptr = (prev_m_off_ptr + 1) & 3;
139 */
140 #endif
141
142 assert(op > c->out);
143 if (m_len == 2)
144 {
145 assert(m_off <= M1_MAX_OFFSET);
146 assert(c->r1_lit > 0); assert(c->r1_lit < 4);
147 m_off -= 1;
148 #if defined(LZO1Z)
149 *op++ = LZO_BYTE(M1_MARKER | (m_off >> 6));
150 *op++ = LZO_BYTE(m_off << 2);
151 #else
152 *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
153 *op++ = LZO_BYTE(m_off >> 2);
154 #endif
155 c->m1a_m++;
156 }
157 #if defined(LZO1Z)
158 else if (m_len <= M2_MAX_LEN && (m_off <= M2_MAX_OFFSET || m_off == c->last_m_off))
159 #else
160 else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
161 #endif
162 {
163 assert(m_len >= 3);
164 #if defined(LZO1X)
165 m_off -= 1;
166 *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
167 *op++ = LZO_BYTE(m_off >> 3);
168 assert(op[-2] >= M2_MARKER);
169 #elif defined(LZO1Y)
170 m_off -= 1;
171 *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
172 *op++ = LZO_BYTE(m_off >> 2);
173 assert(op[-2] >= M2_MARKER);
174 #elif defined(LZO1Z)
175 if (m_off == c->last_m_off)
176 *op++ = LZO_BYTE(((m_len - 1) << 5) | (0x700 >> 6));
177 else
178 {
179 m_off -= 1;
180 *op++ = LZO_BYTE(((m_len - 1) << 5) | (m_off >> 6));
181 *op++ = LZO_BYTE(m_off << 2);
182 }
183 #endif
184 c->m2_m++;
185 }
186 else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4)
187 {
188 assert(m_len == 3);
189 assert(m_off > M2_MAX_OFFSET);
190 m_off -= 1 + M2_MAX_OFFSET;
191 #if defined(LZO1Z)
192 *op++ = LZO_BYTE(M1_MARKER | (m_off >> 6));
193 *op++ = LZO_BYTE(m_off << 2);
194 #else
195 *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
196 *op++ = LZO_BYTE(m_off >> 2);
197 #endif
198 c->m1b_m++;
199 }
200 else if (m_off <= M3_MAX_OFFSET)
201 {
202 assert(m_len >= 3);
203 m_off -= 1;
204 if (m_len <= M3_MAX_LEN)
205 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
206 else
207 {
208 m_len -= M3_MAX_LEN;
209 *op++ = M3_MARKER | 0;
210 while (m_len > 255)
211 {
212 m_len -= 255;
213 *op++ = 0;
214 }
215 assert(m_len > 0);
216 *op++ = LZO_BYTE(m_len);
217 }
218 #if defined(LZO1Z)
219 *op++ = LZO_BYTE(m_off >> 6);
220 *op++ = LZO_BYTE(m_off << 2);
221 #else
222 *op++ = LZO_BYTE(m_off << 2);
223 *op++ = LZO_BYTE(m_off >> 6);
224 #endif
225 c->m3_m++;
226 }
227 else
228 {
229 lzo_uint k;
230
231 assert(m_len >= 3);
232 assert(m_off > 0x4000); assert(m_off <= 0xbfff);
233 m_off -= 0x4000;
234 k = (m_off & 0x4000) >> 11;
235 if (m_len <= M4_MAX_LEN)
236 *op++ = LZO_BYTE(M4_MARKER | k | (m_len - 2));
237 else
238 {
239 m_len -= M4_MAX_LEN;
240 *op++ = LZO_BYTE(M4_MARKER | k | 0);
241 while (m_len > 255)
242 {
243 m_len -= 255;
244 *op++ = 0;
245 }
246 assert(m_len > 0);
247 *op++ = LZO_BYTE(m_len);
248 }
249 #if defined(LZO1Z)
250 *op++ = LZO_BYTE(m_off >> 6);
251 *op++ = LZO_BYTE(m_off << 2);
252 #else
253 *op++ = LZO_BYTE(m_off << 2);
254 *op++ = LZO_BYTE(m_off >> 6);
255 #endif
256 c->m4_m++;
257 }
258
259 c->last_m_len = x_len;
260 c->last_m_off = x_off;
261 return op;
262 }
263
264
265 static lzo_bytep
STORE_RUN(LZO_COMPRESS_T * c,lzo_bytep op,const lzo_bytep ii,lzo_uint t)266 STORE_RUN ( LZO_COMPRESS_T *c, lzo_bytep op, const lzo_bytep ii, lzo_uint t )
267 {
268 c->lit_bytes += (unsigned long) t;
269
270 if (op == c->out && t <= 238)
271 {
272 *op++ = LZO_BYTE(17 + t);
273 }
274 else if (t <= 3)
275 {
276 #if defined(LZO1Z)
277 op[-1] = LZO_BYTE(op[-1] | t);
278 #else
279 op[-2] = LZO_BYTE(op[-2] | t);
280 #endif
281 c->lit1_r++;
282 }
283 else if (t <= 18)
284 {
285 *op++ = LZO_BYTE(t - 3);
286 c->lit2_r++;
287 }
288 else
289 {
290 lzo_uint tt = t - 18;
291
292 *op++ = 0;
293 while (tt > 255)
294 {
295 tt -= 255;
296 *op++ = 0;
297 }
298 assert(tt > 0);
299 *op++ = LZO_BYTE(tt);
300 c->lit3_r++;
301 }
302 do *op++ = *ii++; while (--t > 0);
303
304 return op;
305 }
306
307
308 static lzo_bytep
code_run(LZO_COMPRESS_T * c,lzo_bytep op,const lzo_bytep ii,lzo_uint lit,lzo_uint m_len)309 code_run ( LZO_COMPRESS_T *c, lzo_bytep op, const lzo_bytep ii,
310 lzo_uint lit, lzo_uint m_len )
311 {
312 if (lit > 0)
313 {
314 assert(m_len >= 2);
315 op = STORE_RUN(c,op,ii,lit);
316 c->r1_m_len = m_len;
317 c->r1_lit = lit;
318 }
319 else
320 {
321 assert(m_len >= 3);
322 c->r1_m_len = 0;
323 c->r1_lit = 0;
324 }
325
326 return op;
327 }
328
329
330 /***********************************************************************
331 //
332 ************************************************************************/
333
334 static lzo_uint
len_of_coded_match(lzo_uint m_len,lzo_uint m_off,lzo_uint lit)335 len_of_coded_match ( lzo_uint m_len, lzo_uint m_off, lzo_uint lit )
336 {
337 lzo_uint n = 4;
338
339 if (m_len < 2)
340 return 0;
341 if (m_len == 2)
342 return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : 0;
343 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
344 return 2;
345 if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
346 return 2;
347 if (m_off <= M3_MAX_OFFSET)
348 {
349 if (m_len <= M3_MAX_LEN)
350 return 3;
351 m_len -= M3_MAX_LEN;
352 while (m_len > 255)
353 {
354 m_len -= 255;
355 n++;
356 }
357 return n;
358 }
359 if (m_off <= M4_MAX_OFFSET)
360 {
361 if (m_len <= M4_MAX_LEN)
362 return 3;
363 m_len -= M4_MAX_LEN;
364 while (m_len > 255)
365 {
366 m_len -= 255;
367 n++;
368 }
369 return n;
370 }
371 return 0;
372 }
373
374
375 static lzo_uint
min_gain(lzo_uint ahead,lzo_uint lit1,lzo_uint lit2,lzo_uint l1,lzo_uint l2,lzo_uint l3)376 min_gain(lzo_uint ahead, lzo_uint lit1, lzo_uint lit2, lzo_uint l1, lzo_uint l2, lzo_uint l3)
377 {
378 lzo_uint lazy_match_min_gain;
379
380 assert (ahead >= 1);
381 lazy_match_min_gain = ahead;
382
383 #if 0
384 if (l3)
385 lit2 -= ahead;
386 #endif
387
388 if (lit1 <= 3)
389 lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
390 else if (lit1 <= 18)
391 lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
392
393 lazy_match_min_gain += (l2 - l1) * 2;
394 if (l3)
395 lazy_match_min_gain -= (ahead - l3) * 2;
396
397 if ((lzo_int) lazy_match_min_gain < 0)
398 lazy_match_min_gain = 0;
399
400 #if 0
401 if (l1 == 2)
402 if (lazy_match_min_gain == 0)
403 lazy_match_min_gain = 1;
404 #endif
405
406 return lazy_match_min_gain;
407 }
408
409
410 /***********************************************************************
411 //
412 ************************************************************************/
413
414 #if !defined(NDEBUG)
415 static
assert_match(const lzo_swd_p swd,lzo_uint m_len,lzo_uint m_off)416 void assert_match( const lzo_swd_p swd, lzo_uint m_len, lzo_uint m_off )
417 {
418 const LZO_COMPRESS_T *c = swd->c;
419 lzo_uint d_off;
420
421 assert(m_len >= 2);
422 if (m_off <= (lzo_uint) (c->bp - c->in))
423 {
424 assert(c->bp - m_off + m_len < c->ip);
425 assert(lzo_memcmp(c->bp, c->bp - m_off, m_len) == 0);
426 }
427 else
428 {
429 assert(swd->dict != NULL);
430 d_off = m_off - (lzo_uint) (c->bp - c->in);
431 assert(d_off <= swd->dict_len);
432 if (m_len > d_off)
433 {
434 assert(lzo_memcmp(c->bp, swd->dict_end - d_off, d_off) == 0);
435 assert(c->in + m_len - d_off < c->ip);
436 assert(lzo_memcmp(c->bp + d_off, c->in, m_len - d_off) == 0);
437 }
438 else
439 {
440 assert(lzo_memcmp(c->bp, swd->dict_end - d_off, m_len) == 0);
441 }
442 }
443 }
444 #else
445 # define assert_match(a,b,c) ((void)0)
446 #endif
447
448
449 #if defined(SWD_BEST_OFF)
450
451 static void
better_match(const lzo_swd_p swd,lzo_uint * m_len,lzo_uint * m_off)452 better_match ( const lzo_swd_p swd, lzo_uint *m_len, lzo_uint *m_off )
453 {
454 #if defined(LZO1Z)
455 const LZO_COMPRESS_T *c = swd->c;
456 #endif
457
458 if (*m_len <= M2_MIN_LEN)
459 return;
460 #if defined(LZO1Z)
461 if (*m_off == c->last_m_off && *m_len <= M2_MAX_LEN)
462 return;
463 #if 1
464 if (*m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 &&
465 c->last_m_off && swd->best_off[*m_len-1] == c->last_m_off)
466 {
467 *m_len = *m_len - 1;
468 *m_off = swd->best_off[*m_len];
469 return;
470 }
471 #endif
472 #endif
473
474 if (*m_off <= M2_MAX_OFFSET)
475 return;
476
477 #if 1
478 /* M3/M4 -> M2 */
479 if (*m_off > M2_MAX_OFFSET &&
480 *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 &&
481 swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET)
482 {
483 *m_len = *m_len - 1;
484 *m_off = swd->best_off[*m_len];
485 return;
486 }
487 #endif
488
489 #if 1
490 /* M4 -> M2 */
491 if (*m_off > M3_MAX_OFFSET &&
492 *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2 &&
493 swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET)
494 {
495 *m_len = *m_len - 2;
496 *m_off = swd->best_off[*m_len];
497 return;
498 }
499 #endif
500
501 #if 1
502 /* M4 -> M3 */
503 if (*m_off > M3_MAX_OFFSET &&
504 *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1 &&
505 swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET)
506 {
507 *m_len = *m_len - 1;
508 *m_off = swd->best_off[*m_len];
509 }
510 #endif
511 }
512
513 #endif
514
515
516 /***********************************************************************
517 //
518 ************************************************************************/
519
520 LZO_PUBLIC(int)
lzo1x_999_compress_internal(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem,const lzo_bytep dict,lzo_uint dict_len,lzo_callback_p cb,int try_lazy_parm,lzo_uint good_length,lzo_uint max_lazy,lzo_uint nice_length,lzo_uint max_chain,lzo_uint32_t flags)521 lzo1x_999_compress_internal ( const lzo_bytep in , lzo_uint in_len,
522 lzo_bytep out, lzo_uintp out_len,
523 lzo_voidp wrkmem,
524 const lzo_bytep dict, lzo_uint dict_len,
525 lzo_callback_p cb,
526 int try_lazy_parm,
527 lzo_uint good_length,
528 lzo_uint max_lazy,
529 lzo_uint nice_length,
530 lzo_uint max_chain,
531 lzo_uint32_t flags )
532 {
533 lzo_bytep op;
534 const lzo_bytep ii;
535 lzo_uint lit;
536 lzo_uint m_len, m_off;
537 LZO_COMPRESS_T cc;
538 LZO_COMPRESS_T * const c = &cc;
539 lzo_swd_p const swd = (lzo_swd_p) wrkmem;
540 lzo_uint try_lazy;
541 int r;
542
543 /* sanity check */
544 #if defined(LZO1X)
545 LZO_COMPILE_TIME_ASSERT(LZO1X_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
546 #elif defined(LZO1Y)
547 LZO_COMPILE_TIME_ASSERT(LZO1Y_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
548 #elif defined(LZO1Z)
549 LZO_COMPILE_TIME_ASSERT(LZO1Z_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
550 #else
551 # error
552 #endif
553
554 /* setup parameter defaults */
555 /* number of lazy match tries */
556 try_lazy = (lzo_uint) try_lazy_parm;
557 if (try_lazy_parm < 0)
558 try_lazy = 1;
559 /* reduce lazy match search if we already have a match with this length */
560 if (good_length == 0)
561 good_length = 32;
562 /* do not try a lazy match if we already have a match with this length */
563 if (max_lazy == 0)
564 max_lazy = 32;
565 /* stop searching for longer matches than this one */
566 if (nice_length == 0)
567 nice_length = 0;
568 /* don't search more positions than this */
569 if (max_chain == 0)
570 max_chain = SWD_MAX_CHAIN;
571
572 c->init = 0;
573 c->ip = c->in = in;
574 c->in_end = in + in_len;
575 c->out = out;
576 c->cb = cb;
577 c->m1a_m = c->m1b_m = c->m2_m = c->m3_m = c->m4_m = 0;
578 c->lit1_r = c->lit2_r = c->lit3_r = 0;
579
580 op = out;
581 ii = c->ip; /* point to start of literal run */
582 lit = 0;
583 c->r1_lit = c->r1_m_len = 0;
584
585 r = init_match(c,swd,dict,dict_len,flags);
586 if (r != 0)
587 return r;
588 if (max_chain > 0)
589 swd->max_chain = max_chain;
590 if (nice_length > 0)
591 swd->nice_length = nice_length;
592
593 r = find_match(c,swd,0,0);
594 if (r != 0)
595 return r;
596 while (c->look > 0)
597 {
598 lzo_uint ahead;
599 lzo_uint max_ahead;
600 lzo_uint l1, l2, l3;
601
602 c->codesize = pd(op, out);
603
604 m_len = c->m_len;
605 m_off = c->m_off;
606
607 assert(c->bp == c->ip - c->look);
608 assert(c->bp >= in);
609 if (lit == 0)
610 ii = c->bp;
611 assert(ii + lit == c->bp);
612 assert(swd->b_char == *(c->bp));
613
614 if ( m_len < 2 ||
615 (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4)) ||
616 #if 1
617 /* Do not accept this match for compressed-data compatibility
618 * with LZO v1.01 and before
619 * [ might be a problem for decompress() and optimize() ]
620 */
621 (m_len == 2 && op == out) ||
622 #endif
623 (op == out && lit == 0))
624 {
625 /* a literal */
626 m_len = 0;
627 }
628 else if (m_len == M2_MIN_LEN)
629 {
630 /* compression ratio improves if we code a literal in some cases */
631 if (m_off > MX_MAX_OFFSET && lit >= 4)
632 m_len = 0;
633 }
634
635 if (m_len == 0)
636 {
637 /* a literal */
638 lit++;
639 swd->max_chain = max_chain;
640 r = find_match(c,swd,1,0);
641 assert(r == 0); LZO_UNUSED(r);
642 continue;
643 }
644
645 /* a match */
646 #if defined(SWD_BEST_OFF)
647 if (swd->use_best_off)
648 better_match(swd,&m_len,&m_off);
649 #endif
650 assert_match(swd,m_len,m_off);
651
652
653 /* shall we try a lazy match ? */
654 ahead = 0;
655 if (try_lazy == 0 || m_len >= max_lazy)
656 {
657 /* no */
658 l1 = 0;
659 max_ahead = 0;
660 }
661 else
662 {
663 /* yes, try a lazy match */
664 l1 = len_of_coded_match(m_len,m_off,lit);
665 assert(l1 > 0);
666 #if 1
667 max_ahead = LZO_MIN(try_lazy, l1 - 1);
668 #else
669 max_ahead = LZO_MIN3(try_lazy, l1, m_len - 1);
670 #endif
671 }
672
673
674 while (ahead < max_ahead && c->look > m_len)
675 {
676 lzo_uint lazy_match_min_gain;
677
678 if (m_len >= good_length)
679 swd->max_chain = max_chain >> 2;
680 else
681 swd->max_chain = max_chain;
682 r = find_match(c,swd,1,0);
683 ahead++;
684
685 assert(r == 0); LZO_UNUSED(r);
686 assert(c->look > 0);
687 assert(ii + lit + ahead == c->bp);
688
689 #if defined(LZO1Z)
690 if (m_off == c->last_m_off && c->m_off != c->last_m_off)
691 if (m_len >= M2_MIN_LEN && m_len <= M2_MAX_LEN)
692 c->m_len = 0;
693 #endif
694 if (c->m_len < m_len)
695 continue;
696 #if 1
697 if (c->m_len == m_len && c->m_off >= m_off)
698 continue;
699 #endif
700 #if defined(SWD_BEST_OFF)
701 if (swd->use_best_off)
702 better_match(swd,&c->m_len,&c->m_off);
703 #endif
704 l2 = len_of_coded_match(c->m_len,c->m_off,lit+ahead);
705 if (l2 == 0)
706 continue;
707 #if 0
708 if (c->m_len == m_len && l2 >= l1)
709 continue;
710 #endif
711
712
713 #if 1
714 /* compressed-data compatibility [see above] */
715 l3 = (op == out) ? 0 : len_of_coded_match(ahead,m_off,lit);
716 #else
717 l3 = len_of_coded_match(ahead,m_off,lit);
718 #endif
719
720 lazy_match_min_gain = min_gain(ahead,lit,lit+ahead,l1,l2,l3);
721 if (c->m_len >= m_len + lazy_match_min_gain)
722 {
723 c->lazy++;
724 assert_match(swd,c->m_len,c->m_off);
725
726 if (l3)
727 {
728 /* code previous run */
729 op = code_run(c,op,ii,lit,ahead);
730 lit = 0;
731 /* code shortened match */
732 op = code_match(c,op,ahead,m_off);
733 }
734 else
735 {
736 lit += ahead;
737 assert(ii + lit == c->bp);
738 }
739 goto lazy_match_done;
740 }
741 }
742
743
744 assert(ii + lit + ahead == c->bp);
745
746 /* 1 - code run */
747 op = code_run(c,op,ii,lit,m_len);
748 lit = 0;
749
750 /* 2 - code match */
751 op = code_match(c,op,m_len,m_off);
752 swd->max_chain = max_chain;
753 r = find_match(c,swd,m_len,1+ahead);
754 assert(r == 0); LZO_UNUSED(r);
755
756 lazy_match_done: ;
757 }
758
759
760 /* store final run */
761 if (lit > 0)
762 op = STORE_RUN(c,op,ii,lit);
763
764 #if defined(LZO_EOF_CODE)
765 *op++ = M4_MARKER | 1;
766 *op++ = 0;
767 *op++ = 0;
768 #endif
769
770 c->codesize = pd(op, out);
771 assert(c->textsize == in_len);
772
773 *out_len = pd(op, out);
774
775 if (c->cb && c->cb->nprogress)
776 (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
777
778 #if 0
779 printf("%ld %ld -> %ld %ld: %ld %ld %ld %ld %ld %ld: %ld %ld %ld %ld\n",
780 (long) c->textsize, (long) in_len, (long) c->codesize,
781 c->match_bytes, c->m1a_m, c->m1b_m, c->m2_m, c->m3_m, c->m4_m,
782 c->lit_bytes, c->lit1_r, c->lit2_r, c->lit3_r, c->lazy);
783 #endif
784 assert(c->lit_bytes + c->match_bytes == in_len);
785
786 return LZO_E_OK;
787 }
788
789
790 /***********************************************************************
791 //
792 ************************************************************************/
793
794 LZO_PUBLIC(int)
lzo1x_999_compress_level(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem,const lzo_bytep dict,lzo_uint dict_len,lzo_callback_p cb,int compression_level)795 lzo1x_999_compress_level ( const lzo_bytep in , lzo_uint in_len,
796 lzo_bytep out, lzo_uintp out_len,
797 lzo_voidp wrkmem,
798 const lzo_bytep dict, lzo_uint dict_len,
799 lzo_callback_p cb,
800 int compression_level )
801 {
802 static const struct
803 {
804 int try_lazy_parm;
805 lzo_uint good_length;
806 lzo_uint max_lazy;
807 lzo_uint nice_length;
808 lzo_uint max_chain;
809 lzo_uint32_t flags;
810 } c[9] = {
811 /* faster compression */
812 { 0, 0, 0, 8, 4, 0 },
813 { 0, 0, 0, 16, 8, 0 },
814 { 0, 0, 0, 32, 16, 0 },
815 { 1, 4, 4, 16, 16, 0 },
816 { 1, 8, 16, 32, 32, 0 },
817 { 1, 8, 16, 128, 128, 0 },
818 { 2, 8, 32, 128, 256, 0 },
819 { 2, 32, 128, SWD_F, 2048, 1 },
820 { 2, SWD_F, SWD_F, SWD_F, 4096, 1 }
821 /* max. compression */
822 };
823
824 if (compression_level < 1 || compression_level > 9)
825 return LZO_E_ERROR;
826
827 compression_level -= 1;
828 return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
829 dict, dict_len, cb,
830 c[compression_level].try_lazy_parm,
831 c[compression_level].good_length,
832 c[compression_level].max_lazy,
833 #if 0
834 c[compression_level].nice_length,
835 #else
836 0,
837 #endif
838 c[compression_level].max_chain,
839 c[compression_level].flags);
840 }
841
842
843 /***********************************************************************
844 //
845 ************************************************************************/
846
847 LZO_PUBLIC(int)
lzo1x_999_compress_dict(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem,const lzo_bytep dict,lzo_uint dict_len)848 lzo1x_999_compress_dict ( const lzo_bytep in , lzo_uint in_len,
849 lzo_bytep out, lzo_uintp out_len,
850 lzo_voidp wrkmem,
851 const lzo_bytep dict, lzo_uint dict_len )
852 {
853 return lzo1x_999_compress_level(in, in_len, out, out_len, wrkmem,
854 dict, dict_len, 0, 8);
855 }
856
857 LZO_PUBLIC(int)
lzo1x_999_compress(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem)858 lzo1x_999_compress ( const lzo_bytep in , lzo_uint in_len,
859 lzo_bytep out, lzo_uintp out_len,
860 lzo_voidp wrkmem )
861 {
862 return lzo1x_999_compress_level(in, in_len, out, out_len, wrkmem,
863 NULL, 0, (lzo_callback_p) 0, 8);
864 }
865
866
867 /*
868 vi:ts=4:et
869 */
870
871