Magellan Linux

Annotation of /trunk/mkinitrd-magellan/busybox/archival/lzo1x_9x.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 984 - (hide annotations) (download)
Sun May 30 11:32:42 2010 UTC (14 years, 5 months ago) by niro
File MIME type: text/plain
File size: 21043 byte(s)
-updated to busybox-1.16.1 and enabled blkid/uuid support in default config
1 niro 984 /* 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) 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     #include "libbb.h"
40    
41     /* The following is probably only safe on Intel-compatible processors ... */
42     #define LZO_UNALIGNED_OK_2
43     #define LZO_UNALIGNED_OK_4
44    
45     #include "liblzo.h"
46    
47     #define LZO_MAX(a,b) ((a) >= (b) ? (a) : (b))
48     #define LZO_MIN(a,b) ((a) <= (b) ? (a) : (b))
49     #define LZO_MAX3(a,b,c) ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c))
50    
51     /***********************************************************************
52     //
53     ************************************************************************/
54     #define SWD_N M4_MAX_OFFSET /* size of ring buffer */
55     #define SWD_F 2048 /* upper limit for match length */
56    
57     #define SWD_BEST_OFF (LZO_MAX3(M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN) + 1)
58    
59     typedef struct {
60     int init;
61    
62     unsigned look; /* bytes in lookahead buffer */
63    
64     unsigned m_len;
65     unsigned m_off;
66    
67     const uint8_t *bp;
68     const uint8_t *ip;
69     const uint8_t *in;
70     const uint8_t *in_end;
71     uint8_t *out;
72    
73     unsigned r1_lit;
74    
75     } lzo1x_999_t;
76    
77     #define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
78    
79     /* lzo_swd.c -- sliding window dictionary */
80    
81     /***********************************************************************
82     //
83     ************************************************************************/
84     #define SWD_UINT_MAX USHRT_MAX
85    
86     #ifndef SWD_HSIZE
87     # define SWD_HSIZE 16384
88     #endif
89     #ifndef SWD_MAX_CHAIN
90     # define SWD_MAX_CHAIN 2048
91     #endif
92    
93     #define HEAD3(b, p) \
94     ( ((0x9f5f * ((((b[p]<<5)^b[p+1])<<5) ^ b[p+2])) >> 5) & (SWD_HSIZE-1) )
95    
96     #if defined(LZO_UNALIGNED_OK_2)
97     # define HEAD2(b,p) (* (uint16_t *) &(b[p]))
98     #else
99     # define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8))
100     #endif
101     #define NIL2 SWD_UINT_MAX
102    
103     typedef struct lzo_swd {
104     /* public - "built-in" */
105    
106     /* public - configuration */
107     unsigned max_chain;
108     int use_best_off;
109    
110     /* public - output */
111     unsigned m_len;
112     unsigned m_off;
113     unsigned look;
114     int b_char;
115     #if defined(SWD_BEST_OFF)
116     unsigned best_off[SWD_BEST_OFF];
117     #endif
118    
119     /* semi public */
120     lzo1x_999_t *c;
121     unsigned m_pos;
122     #if defined(SWD_BEST_OFF)
123     unsigned best_pos[SWD_BEST_OFF];
124     #endif
125    
126     /* private */
127     unsigned ip; /* input pointer (lookahead) */
128     unsigned bp; /* buffer pointer */
129     unsigned rp; /* remove pointer */
130    
131     unsigned node_count;
132     unsigned first_rp;
133    
134     uint8_t b[SWD_N + SWD_F];
135     uint8_t b_wrap[SWD_F]; /* must follow b */
136     uint16_t head3[SWD_HSIZE];
137     uint16_t succ3[SWD_N + SWD_F];
138     uint16_t best3[SWD_N + SWD_F];
139     uint16_t llen3[SWD_HSIZE];
140     #ifdef HEAD2
141     uint16_t head2[65536L];
142     #endif
143     } lzo_swd_t, *lzo_swd_p;
144    
145     #define SIZEOF_LZO_SWD_T (sizeof(lzo_swd_t))
146    
147    
148     /* Access macro for head3.
149     * head3[key] may be uninitialized, but then its value will never be used.
150     */
151     #define s_get_head3(s,key) s->head3[key]
152    
153    
154     /***********************************************************************
155     //
156     ************************************************************************/
157     #define B_SIZE (SWD_N + SWD_F)
158    
159     static int swd_init(lzo_swd_p s)
160     {
161     /* defaults */
162     s->node_count = SWD_N;
163    
164     memset(s->llen3, 0, sizeof(s->llen3[0]) * (unsigned)SWD_HSIZE);
165     #ifdef HEAD2
166     memset(s->head2, 0xff, sizeof(s->head2[0]) * 65536L);
167     assert(s->head2[0] == NIL2);
168     #endif
169    
170     s->ip = 0;
171     s->bp = s->ip;
172     s->first_rp = s->ip;
173    
174     assert(s->ip + SWD_F <= B_SIZE);
175     s->look = (unsigned) (s->c->in_end - s->c->ip);
176     if (s->look > 0) {
177     if (s->look > SWD_F)
178     s->look = SWD_F;
179     memcpy(&s->b[s->ip],s->c->ip,s->look);
180     s->c->ip += s->look;
181     s->ip += s->look;
182     }
183     if (s->ip == B_SIZE)
184     s->ip = 0;
185    
186     s->rp = s->first_rp;
187     if (s->rp >= s->node_count)
188     s->rp -= s->node_count;
189     else
190     s->rp += B_SIZE - s->node_count;
191    
192     return LZO_E_OK;
193     }
194    
195     #define swd_pos2off(s,pos) \
196     (s->bp > (pos) ? s->bp - (pos) : B_SIZE - ((pos) - s->bp))
197    
198    
199     /***********************************************************************
200     //
201     ************************************************************************/
202     static void swd_getbyte(lzo_swd_p s)
203     {
204     int c;
205    
206     if ((c = getbyte(*(s->c))) < 0) {
207     if (s->look > 0)
208     --s->look;
209     } else {
210     s->b[s->ip] = c;
211     if (s->ip < SWD_F)
212     s->b_wrap[s->ip] = c;
213     }
214     if (++s->ip == B_SIZE)
215     s->ip = 0;
216     if (++s->bp == B_SIZE)
217     s->bp = 0;
218     if (++s->rp == B_SIZE)
219     s->rp = 0;
220     }
221    
222    
223     /***********************************************************************
224     // remove node from lists
225     ************************************************************************/
226     static void swd_remove_node(lzo_swd_p s, unsigned node)
227     {
228     if (s->node_count == 0) {
229     unsigned key;
230    
231     key = HEAD3(s->b,node);
232     assert(s->llen3[key] > 0);
233     --s->llen3[key];
234    
235     #ifdef HEAD2
236     key = HEAD2(s->b,node);
237     assert(s->head2[key] != NIL2);
238     if ((unsigned) s->head2[key] == node)
239     s->head2[key] = NIL2;
240     #endif
241     } else
242     --s->node_count;
243     }
244    
245    
246     /***********************************************************************
247     //
248     ************************************************************************/
249     static void swd_accept(lzo_swd_p s, unsigned n)
250     {
251     assert(n <= s->look);
252    
253     while (n--) {
254     unsigned key;
255    
256     swd_remove_node(s,s->rp);
257    
258     /* add bp into HEAD3 */
259     key = HEAD3(s->b,s->bp);
260     s->succ3[s->bp] = s_get_head3(s,key);
261     s->head3[key] = s->bp;
262     s->best3[s->bp] = SWD_F + 1;
263     s->llen3[key]++;
264     assert(s->llen3[key] <= SWD_N);
265    
266     #ifdef HEAD2
267     /* add bp into HEAD2 */
268     key = HEAD2(s->b,s->bp);
269     s->head2[key] = s->bp;
270     #endif
271    
272     swd_getbyte(s);
273     }
274     }
275    
276    
277     /***********************************************************************
278     //
279     ************************************************************************/
280     static void swd_search(lzo_swd_p s, unsigned node, unsigned cnt)
281     {
282     const uint8_t *p1;
283     const uint8_t *p2;
284     const uint8_t *px;
285     unsigned m_len = s->m_len;
286     const uint8_t *b = s->b;
287     const uint8_t *bp = s->b + s->bp;
288     const uint8_t *bx = s->b + s->bp + s->look;
289     unsigned char scan_end1;
290    
291     assert(s->m_len > 0);
292    
293     scan_end1 = bp[m_len - 1];
294     for ( ; cnt-- > 0; node = s->succ3[node]) {
295     p1 = bp;
296     p2 = b + node;
297     px = bx;
298    
299     assert(m_len < s->look);
300    
301     if (p2[m_len - 1] == scan_end1 &&
302     p2[m_len] == p1[m_len] &&
303     p2[0] == p1[0] &&
304     p2[1] == p1[1]) {
305     unsigned i;
306     assert(lzo_memcmp(bp,&b[node],3) == 0);
307    
308     p1 += 2; p2 += 2;
309     do {} while (++p1 < px && *p1 == *++p2);
310     i = p1-bp;
311    
312     assert(lzo_memcmp(bp,&b[node],i) == 0);
313    
314     #if defined(SWD_BEST_OFF)
315     if (i < SWD_BEST_OFF) {
316     if (s->best_pos[i] == 0)
317     s->best_pos[i] = node + 1;
318     }
319     #endif
320     if (i > m_len) {
321     s->m_len = m_len = i;
322     s->m_pos = node;
323     if (m_len == s->look)
324     return;
325     if (m_len >= SWD_F)
326     return;
327     if (m_len > (unsigned) s->best3[node])
328     return;
329     scan_end1 = bp[m_len - 1];
330     }
331     }
332     }
333     }
334    
335    
336     /***********************************************************************
337     //
338     ************************************************************************/
339     #ifdef HEAD2
340    
341     static int swd_search2(lzo_swd_p s)
342     {
343     unsigned key;
344    
345     assert(s->look >= 2);
346     assert(s->m_len > 0);
347    
348     key = s->head2[ HEAD2(s->b,s->bp) ];
349     if (key == NIL2)
350     return 0;
351     assert(lzo_memcmp(&s->b[s->bp],&s->b[key],2) == 0);
352     #if defined(SWD_BEST_OFF)
353     if (s->best_pos[2] == 0)
354     s->best_pos[2] = key + 1;
355     #endif
356    
357     if (s->m_len < 2) {
358     s->m_len = 2;
359     s->m_pos = key;
360     }
361     return 1;
362     }
363    
364     #endif
365    
366    
367     /***********************************************************************
368     //
369     ************************************************************************/
370     static void swd_findbest(lzo_swd_p s)
371     {
372     unsigned key;
373     unsigned cnt, node;
374     unsigned len;
375    
376     assert(s->m_len > 0);
377    
378     /* get current head, add bp into HEAD3 */
379     key = HEAD3(s->b,s->bp);
380     node = s->succ3[s->bp] = s_get_head3(s,key);
381     cnt = s->llen3[key]++;
382     assert(s->llen3[key] <= SWD_N + SWD_F);
383     if (cnt > s->max_chain)
384     cnt = s->max_chain;
385     s->head3[key] = s->bp;
386    
387     s->b_char = s->b[s->bp];
388     len = s->m_len;
389     if (s->m_len >= s->look) {
390     if (s->look == 0)
391     s->b_char = -1;
392     s->m_off = 0;
393     s->best3[s->bp] = SWD_F + 1;
394     } else {
395     #ifdef HEAD2
396     if (swd_search2(s))
397     #endif
398     if (s->look >= 3)
399     swd_search(s,node,cnt);
400     if (s->m_len > len)
401     s->m_off = swd_pos2off(s,s->m_pos);
402     s->best3[s->bp] = s->m_len;
403    
404     #if defined(SWD_BEST_OFF)
405     if (s->use_best_off) {
406     int i;
407     for (i = 2; i < SWD_BEST_OFF; i++)
408     if (s->best_pos[i] > 0)
409     s->best_off[i] = swd_pos2off(s,s->best_pos[i]-1);
410     else
411     s->best_off[i] = 0;
412     }
413     #endif
414     }
415    
416     swd_remove_node(s,s->rp);
417    
418     #ifdef HEAD2
419     /* add bp into HEAD2 */
420     key = HEAD2(s->b,s->bp);
421     s->head2[key] = s->bp;
422     #endif
423     }
424    
425     #undef HEAD3
426     #undef HEAD2
427     #undef s_get_head3
428    
429    
430     /***********************************************************************
431     //
432     ************************************************************************/
433     static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
434     {
435     int r;
436    
437     assert(!c->init);
438     c->init = 1;
439    
440     s->c = c;
441    
442     r = swd_init(s);
443     if (r != 0)
444     return r;
445    
446     s->use_best_off = use_best_off;
447     return r;
448     }
449    
450    
451     /***********************************************************************
452     //
453     ************************************************************************/
454     static int find_match(lzo1x_999_t *c, lzo_swd_p s,
455     unsigned this_len, unsigned skip)
456     {
457     assert(c->init);
458    
459     if (skip > 0) {
460     assert(this_len >= skip);
461     swd_accept(s, this_len - skip);
462     } else {
463     assert(this_len <= 1);
464     }
465    
466     s->m_len = 1;
467     s->m_len = 1;
468     #ifdef SWD_BEST_OFF
469     if (s->use_best_off)
470     memset(s->best_pos,0,sizeof(s->best_pos));
471     #endif
472     swd_findbest(s);
473     c->m_len = s->m_len;
474     c->m_off = s->m_off;
475    
476     swd_getbyte(s);
477    
478     if (s->b_char < 0) {
479     c->look = 0;
480     c->m_len = 0;
481     } else {
482     c->look = s->look + 1;
483     }
484     c->bp = c->ip - c->look;
485    
486     return LZO_E_OK;
487     }
488    
489     /* this is a public functions, but there is no prototype in a header file */
490     static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
491     uint8_t *out, unsigned *out_len,
492     void *wrkmem,
493     unsigned good_length,
494     unsigned max_lazy,
495     unsigned max_chain,
496     uint32_t use_best_off);
497    
498    
499     /***********************************************************************
500     //
501     ************************************************************************/
502     static uint8_t *code_match(lzo1x_999_t *c,
503     uint8_t *op, unsigned m_len, unsigned m_off)
504     {
505     assert(op > c->out);
506     if (m_len == 2) {
507     assert(m_off <= M1_MAX_OFFSET);
508     assert(c->r1_lit > 0); assert(c->r1_lit < 4);
509     m_off -= 1;
510     *op++ = M1_MARKER | ((m_off & 3) << 2);
511     *op++ = m_off >> 2;
512     } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
513     assert(m_len >= 3);
514     m_off -= 1;
515     *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
516     *op++ = m_off >> 3;
517     assert(op[-2] >= M2_MARKER);
518     } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
519     assert(m_len == 3);
520     assert(m_off > M2_MAX_OFFSET);
521     m_off -= 1 + M2_MAX_OFFSET;
522     *op++ = M1_MARKER | ((m_off & 3) << 2);
523     *op++ = m_off >> 2;
524     } else if (m_off <= M3_MAX_OFFSET) {
525     assert(m_len >= 3);
526     m_off -= 1;
527     if (m_len <= M3_MAX_LEN)
528     *op++ = M3_MARKER | (m_len - 2);
529     else {
530     m_len -= M3_MAX_LEN;
531     *op++ = M3_MARKER | 0;
532     while (m_len > 255)
533     {
534     m_len -= 255;
535     *op++ = 0;
536     }
537     assert(m_len > 0);
538     *op++ = m_len;
539     }
540     *op++ = m_off << 2;
541     *op++ = m_off >> 6;
542     } else {
543     unsigned k;
544    
545     assert(m_len >= 3);
546     assert(m_off > 0x4000); assert(m_off <= 0xbfff);
547     m_off -= 0x4000;
548     k = (m_off & 0x4000) >> 11;
549     if (m_len <= M4_MAX_LEN)
550     *op++ = M4_MARKER | k | (m_len - 2);
551     else {
552     m_len -= M4_MAX_LEN;
553     *op++ = M4_MARKER | k | 0;
554     while (m_len > 255)
555     {
556     m_len -= 255;
557     *op++ = 0;
558     }
559     assert(m_len > 0);
560     *op++ = m_len;
561     }
562     *op++ = m_off << 2;
563     *op++ = m_off >> 6;
564     }
565    
566     return op;
567     }
568    
569    
570     static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
571     const uint8_t *ii, unsigned t)
572     {
573     if (op == c->out && t <= 238) {
574     *op++ = 17 + t;
575     } else if (t <= 3) {
576     op[-2] |= t;
577     } else if (t <= 18) {
578     *op++ = t - 3;
579     } else {
580     unsigned tt = t - 18;
581    
582     *op++ = 0;
583     while (tt > 255) {
584     tt -= 255;
585     *op++ = 0;
586     }
587     assert(tt > 0);
588     *op++ = tt;
589     }
590     do *op++ = *ii++; while (--t > 0);
591    
592     return op;
593     }
594    
595    
596     static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
597     unsigned lit)
598     {
599     if (lit > 0) {
600     assert(m_len >= 2);
601     op = STORE_RUN(c,op,ii,lit);
602     } else {
603     assert(m_len >= 3);
604     }
605     c->r1_lit = lit;
606    
607     return op;
608     }
609    
610    
611     /***********************************************************************
612     //
613     ************************************************************************/
614     static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
615     {
616     int n = 4;
617    
618     if (m_len < 2)
619     return -1;
620     if (m_len == 2)
621     return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
622     if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
623     return 2;
624     if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
625     return 2;
626     if (m_off <= M3_MAX_OFFSET) {
627     if (m_len <= M3_MAX_LEN)
628     return 3;
629     m_len -= M3_MAX_LEN;
630     } else if (m_off <= M4_MAX_OFFSET) {
631     if (m_len <= M4_MAX_LEN)
632     return 3;
633     m_len -= M4_MAX_LEN;
634     } else
635     return -1;
636     while (m_len > 255) {
637     m_len -= 255;
638     n++;
639     }
640     return n;
641     }
642    
643    
644     static int min_gain(unsigned ahead, unsigned lit1,
645     unsigned lit2, int l1, int l2, int l3)
646     {
647     int lazy_match_min_gain = 0;
648    
649     assert (ahead >= 1);
650     lazy_match_min_gain += ahead;
651    
652     if (lit1 <= 3)
653     lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
654     else if (lit1 <= 18)
655     lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
656    
657     lazy_match_min_gain += (l2 - l1) * 2;
658     if (l3 > 0)
659     lazy_match_min_gain -= (ahead - l3) * 2;
660    
661     if (lazy_match_min_gain < 0)
662     lazy_match_min_gain = 0;
663    
664     return lazy_match_min_gain;
665     }
666    
667    
668     /***********************************************************************
669     //
670     ************************************************************************/
671     #if defined(SWD_BEST_OFF)
672    
673     static void better_match(const lzo_swd_p swd,
674     unsigned *m_len, unsigned *m_off)
675     {
676    
677     if (*m_len <= M2_MIN_LEN)
678     return;
679    
680     if (*m_off <= M2_MAX_OFFSET)
681     return;
682    
683     /* M3/M4 -> M2 */
684     if (*m_off > M2_MAX_OFFSET &&
685     *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 &&
686     swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET)
687     {
688     *m_len = *m_len - 1;
689     *m_off = swd->best_off[*m_len];
690     return;
691     }
692    
693     /* M4 -> M2 */
694     if (*m_off > M3_MAX_OFFSET &&
695     *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2 &&
696     swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET)
697     {
698     *m_len = *m_len - 2;
699     *m_off = swd->best_off[*m_len];
700     return;
701     }
702     /* M4 -> M3 */
703     if (*m_off > M3_MAX_OFFSET &&
704     *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1 &&
705     swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET)
706     {
707     *m_len = *m_len - 1;
708     *m_off = swd->best_off[*m_len];
709     }
710     }
711    
712     #endif
713    
714    
715     /***********************************************************************
716     //
717     ************************************************************************/
718     static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
719     uint8_t *out, unsigned *out_len,
720     void *wrkmem,
721     unsigned good_length,
722     unsigned max_lazy,
723     unsigned max_chain,
724     uint32_t use_best_off)
725     {
726     uint8_t *op;
727     const uint8_t *ii;
728     unsigned lit;
729     unsigned m_len, m_off;
730     lzo1x_999_t cc;
731     lzo1x_999_t * const c = &cc;
732     lzo_swd_p const swd = (lzo_swd_p) wrkmem;
733     int r;
734    
735     c->init = 0;
736     c->ip = c->in = in;
737     c->in_end = in + in_len;
738     c->out = out;
739    
740     op = out;
741     ii = c->ip; /* point to start of literal run */
742     lit = 0;
743     c->r1_lit = 0;
744    
745     r = init_match(c, swd, use_best_off);
746     if (r != 0)
747     return r;
748     swd->max_chain = max_chain;
749    
750     r = find_match(c, swd, 0, 0);
751     if (r != 0)
752     return r;
753    
754     while (c->look > 0) {
755     unsigned ahead;
756     unsigned max_ahead;
757     int l1, l2, l3;
758    
759     m_len = c->m_len;
760     m_off = c->m_off;
761    
762     assert(c->bp == c->ip - c->look);
763     assert(c->bp >= in);
764     if (lit == 0)
765     ii = c->bp;
766     assert(ii + lit == c->bp);
767     assert(swd->b_char == *(c->bp));
768    
769     if ( m_len < 2 ||
770     (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4)) ||
771     /* Do not accept this match for compressed-data compatibility
772     * with LZO v1.01 and before
773     * [ might be a problem for decompress() and optimize() ]
774     */
775     (m_len == 2 && op == out) ||
776     (op == out && lit == 0))
777     {
778     /* a literal */
779     m_len = 0;
780     }
781     else if (m_len == M2_MIN_LEN) {
782     /* compression ratio improves if we code a literal in some cases */
783     if (m_off > MX_MAX_OFFSET && lit >= 4)
784     m_len = 0;
785     }
786    
787     if (m_len == 0) {
788     /* a literal */
789     lit++;
790     swd->max_chain = max_chain;
791     r = find_match(c,swd,1,0);
792     assert(r == 0);
793     continue;
794     }
795    
796     /* a match */
797     #if defined(SWD_BEST_OFF)
798     if (swd->use_best_off)
799     better_match(swd,&m_len,&m_off);
800     #endif
801    
802     /* shall we try a lazy match ? */
803     ahead = 0;
804     if (m_len >= max_lazy) {
805     /* no */
806     l1 = 0;
807     max_ahead = 0;
808     } else {
809     /* yes, try a lazy match */
810     l1 = len_of_coded_match(m_len,m_off,lit);
811     assert(l1 > 0);
812     max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
813     }
814    
815    
816     while (ahead < max_ahead && c->look > m_len) {
817     int lazy_match_min_gain;
818    
819     if (m_len >= good_length)
820     swd->max_chain = max_chain >> 2;
821     else
822     swd->max_chain = max_chain;
823     r = find_match(c,swd,1,0);
824     ahead++;
825    
826     assert(r == 0);
827     assert(c->look > 0);
828     assert(ii + lit + ahead == c->bp);
829    
830     if (c->m_len < m_len)
831     continue;
832     if (c->m_len == m_len && c->m_off >= m_off)
833     continue;
834     #if defined(SWD_BEST_OFF)
835     if (swd->use_best_off)
836     better_match(swd,&c->m_len,&c->m_off);
837     #endif
838     l2 = len_of_coded_match(c->m_len,c->m_off,lit+ahead);
839     if (l2 < 0)
840     continue;
841    
842     /* compressed-data compatibility [see above] */
843     l3 = (op == out) ? -1 : len_of_coded_match(ahead,m_off,lit);
844    
845     lazy_match_min_gain = min_gain(ahead,lit,lit+ahead,l1,l2,l3);
846     if (c->m_len >= m_len + lazy_match_min_gain) {
847     if (l3 > 0) {
848     /* code previous run */
849     op = code_run(c,op,ii,lit);
850     lit = 0;
851     /* code shortened match */
852     op = code_match(c,op,ahead,m_off);
853     } else {
854     lit += ahead;
855     assert(ii + lit == c->bp);
856     }
857     goto lazy_match_done;
858     }
859     }
860    
861     assert(ii + lit + ahead == c->bp);
862    
863     /* 1 - code run */
864     op = code_run(c,op,ii,lit);
865     lit = 0;
866    
867     /* 2 - code match */
868     op = code_match(c,op,m_len,m_off);
869     swd->max_chain = max_chain;
870     r = find_match(c,swd,m_len,1+ahead);
871     assert(r == 0);
872    
873     lazy_match_done: ;
874     }
875    
876     /* store final run */
877     if (lit > 0)
878     op = STORE_RUN(c,op,ii,lit);
879    
880     #if defined(LZO_EOF_CODE)
881     *op++ = M4_MARKER | 1;
882     *op++ = 0;
883     *op++ = 0;
884     #endif
885    
886     *out_len = op - out;
887    
888     return LZO_E_OK;
889     }
890    
891    
892     /***********************************************************************
893     //
894     ************************************************************************/
895     int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
896     uint8_t *out, unsigned *out_len,
897     void *wrkmem,
898     int compression_level)
899     {
900     static const struct {
901     uint16_t good_length;
902     uint16_t max_lazy;
903     uint16_t max_chain;
904     uint16_t use_best_off;
905     } c[3] = {
906     { 8, 32, 256, 0 },
907     { 32, 128, 2048, 1 },
908     { SWD_F, SWD_F, 4096, 1 } /* max. compression */
909     };
910    
911     if (compression_level < 7 || compression_level > 9)
912     return LZO_E_ERROR;
913    
914     compression_level -= 7;
915     return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
916     c[compression_level].good_length,
917     c[compression_level].max_lazy,
918     c[compression_level].max_chain,
919     c[compression_level].use_best_off);
920     }