• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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