source: branches/2.2.9/mindi-busybox/archival/libarchive/lzo1x_9x.c @ 2725

Last change on this file since 2725 was 2725, checked in by Bruno Cornec, 9 years ago
  • Update mindi-busybox to 1.18.3 to avoid problems with the tar command which is now failing on recent versions with busybox 1.7.3
  • Property svn:eol-style set to native
File size: 20.5 KB
Line 
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) 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
59typedef 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
103typedef 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
159static 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************************************************************************/
202static 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************************************************************************/
226static 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************************************************************************/
249static 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************************************************************************/
280static 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 *= 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        ) {
306            unsigned i;
307            assert(lzo_memcmp(bp, &b[node], 3) == 0);
308
309            p1 += 2; p2 += 2;
310            do {} while (++p1 < px && *p1 == *++p2);
311            i = p1-bp;
312
313            assert(lzo_memcmp(bp, &b[node], i) == 0);
314
315#if defined(SWD_BEST_OFF)
316            if (i < SWD_BEST_OFF) {
317                if (s->best_pos[i] == 0)
318                    s->best_pos[i] = node + 1;
319            }
320#endif
321            if (i > m_len) {
322                s->m_len = m_len = i;
323                s->m_pos = node;
324                if (m_len == s->look)
325                    return;
326                if (m_len >= SWD_F)
327                    return;
328                if (m_len > (unsigned) s->best3[node])
329                    return;
330                scan_end1 = bp[m_len - 1];
331            }
332        }
333    }
334}
335
336
337/***********************************************************************
338//
339************************************************************************/
340#ifdef HEAD2
341
342static int swd_search2(lzo_swd_p s)
343{
344    unsigned key;
345
346    assert(s->look >= 2);
347    assert(s->m_len > 0);
348
349    key = s->head2[HEAD2(s->b, s->bp)];
350    if (key == NIL2)
351        return 0;
352    assert(lzo_memcmp(&s->b[s->bp], &s->b[key], 2) == 0);
353#if defined(SWD_BEST_OFF)
354    if (s->best_pos[2] == 0)
355        s->best_pos[2] = key + 1;
356#endif
357
358    if (s->m_len < 2) {
359        s->m_len = 2;
360        s->m_pos = key;
361    }
362    return 1;
363}
364
365#endif
366
367
368/***********************************************************************
369//
370************************************************************************/
371static void swd_findbest(lzo_swd_p s)
372{
373    unsigned key;
374    unsigned cnt, node;
375    unsigned len;
376
377    assert(s->m_len > 0);
378
379    /* get current head, add bp into HEAD3 */
380    key = HEAD3(s->b,s->bp);
381    node = s->succ3[s->bp] = s_get_head3(s, key);
382    cnt = s->llen3[key]++;
383    assert(s->llen3[key] <= SWD_N + SWD_F);
384    if (cnt > s->max_chain)
385        cnt = s->max_chain;
386    s->head3[key] = s->bp;
387
388    s->b_char = s->b[s->bp];
389    len = s->m_len;
390    if (s->m_len >= s->look) {
391        if (s->look == 0)
392            s->b_char = -1;
393        s->m_off = 0;
394        s->best3[s->bp] = SWD_F + 1;
395    } else {
396#ifdef HEAD2
397        if (swd_search2(s))
398#endif
399            if (s->look >= 3)
400                swd_search(s, node, cnt);
401        if (s->m_len > len)
402            s->m_off = swd_pos2off(s,s->m_pos);
403        s->best3[s->bp] = s->m_len;
404
405#if defined(SWD_BEST_OFF)
406        if (s->use_best_off) {
407            int i;
408            for (i = 2; i < SWD_BEST_OFF; i++) {
409                if (s->best_pos[i] > 0)
410                    s->best_off[i] = swd_pos2off(s, s->best_pos[i]-1);
411                else
412                    s->best_off[i] = 0;
413            }
414        }
415#endif
416    }
417
418    swd_remove_node(s,s->rp);
419
420#ifdef HEAD2
421    /* add bp into HEAD2 */
422    key = HEAD2(s->b, s->bp);
423    s->head2[key] = s->bp;
424#endif
425}
426
427#undef HEAD3
428#undef HEAD2
429#undef s_get_head3
430
431
432/***********************************************************************
433//
434************************************************************************/
435static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
436{
437    int r;
438
439    assert(!c->init);
440    c->init = 1;
441
442    s->c = c;
443
444    r = swd_init(s);
445    if (r != 0)
446        return r;
447
448    s->use_best_off = use_best_off;
449    return r;
450}
451
452
453/***********************************************************************
454//
455************************************************************************/
456static int find_match(lzo1x_999_t *c, lzo_swd_p s,
457        unsigned this_len, unsigned skip)
458{
459    assert(c->init);
460
461    if (skip > 0) {
462        assert(this_len >= skip);
463        swd_accept(s, this_len - skip);
464    } else {
465        assert(this_len <= 1);
466    }
467
468    s->m_len = 1;
469    s->m_len = 1;
470#ifdef SWD_BEST_OFF
471    if (s->use_best_off)
472        memset(s->best_pos, 0, sizeof(s->best_pos));
473#endif
474    swd_findbest(s);
475    c->m_len = s->m_len;
476    c->m_off = s->m_off;
477
478    swd_getbyte(s);
479
480    if (s->b_char < 0) {
481        c->look = 0;
482        c->m_len = 0;
483    } else {
484        c->look = s->look + 1;
485    }
486    c->bp = c->ip - c->look;
487
488    return LZO_E_OK;
489}
490
491/* this is a public functions, but there is no prototype in a header file */
492static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
493        uint8_t *out, unsigned *out_len,
494        void *wrkmem,
495        unsigned good_length,
496        unsigned max_lazy,
497        unsigned max_chain,
498        uint32_t use_best_off);
499
500
501/***********************************************************************
502//
503************************************************************************/
504static uint8_t *code_match(lzo1x_999_t *c,
505        uint8_t *op, unsigned m_len, unsigned m_off)
506{
507    assert(op > c->out);
508    if (m_len == 2) {
509        assert(m_off <= M1_MAX_OFFSET);
510        assert(c->r1_lit > 0);
511        assert(c->r1_lit < 4);
512        m_off -= 1;
513        *op++ = M1_MARKER | ((m_off & 3) << 2);
514        *op++ = m_off >> 2;
515    } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
516        assert(m_len >= 3);
517        m_off -= 1;
518        *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
519        *op++ = m_off >> 3;
520        assert(op[-2] >= M2_MARKER);
521    } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
522        assert(m_len == 3);
523        assert(m_off > M2_MAX_OFFSET);
524        m_off -= 1 + M2_MAX_OFFSET;
525        *op++ = M1_MARKER | ((m_off & 3) << 2);
526        *op++ = m_off >> 2;
527    } else if (m_off <= M3_MAX_OFFSET) {
528        assert(m_len >= 3);
529        m_off -= 1;
530        if (m_len <= M3_MAX_LEN)
531            *op++ = M3_MARKER | (m_len - 2);
532        else {
533            m_len -= M3_MAX_LEN;
534            *op++ = M3_MARKER | 0;
535            while (m_len > 255) {
536                m_len -= 255;
537                *op++ = 0;
538            }
539            assert(m_len > 0);
540            *op++ = m_len;
541        }
542        *op++ = m_off << 2;
543        *op++ = m_off >> 6;
544    } else {
545        unsigned k;
546
547        assert(m_len >= 3);
548        assert(m_off > 0x4000);
549        assert(m_off <= 0xbfff);
550        m_off -= 0x4000;
551        k = (m_off & 0x4000) >> 11;
552        if (m_len <= M4_MAX_LEN)
553            *op++ = M4_MARKER | k | (m_len - 2);
554        else {
555            m_len -= M4_MAX_LEN;
556            *op++ = M4_MARKER | k | 0;
557            while (m_len > 255) {
558                m_len -= 255;
559                *op++ = 0;
560            }
561            assert(m_len > 0);
562            *op++ = m_len;
563        }
564        *op++ = m_off << 2;
565        *op++ = m_off >> 6;
566    }
567
568    return op;
569}
570
571
572static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
573        const uint8_t *ii, unsigned t)
574{
575    if (op == c->out && t <= 238) {
576        *op++ = 17 + t;
577    } else if (t <= 3) {
578        op[-2] |= t;
579    } else if (t <= 18) {
580        *op++ = t - 3;
581    } else {
582        unsigned tt = t - 18;
583
584        *op++ = 0;
585        while (tt > 255) {
586            tt -= 255;
587            *op++ = 0;
588        }
589        assert(tt > 0);
590        *op++ = tt;
591    }
592    do *op++ = *ii++; while (--t > 0);
593
594    return op;
595}
596
597
598static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
599        unsigned lit)
600{
601    if (lit > 0) {
602        assert(m_len >= 2);
603        op = STORE_RUN(c, op, ii, lit);
604    } else {
605        assert(m_len >= 3);
606    }
607    c->r1_lit = lit;
608
609    return op;
610}
611
612
613/***********************************************************************
614//
615************************************************************************/
616static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
617{
618    int n = 4;
619
620    if (m_len < 2)
621        return -1;
622    if (m_len == 2)
623        return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
624    if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
625        return 2;
626    if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
627        return 2;
628    if (m_off <= M3_MAX_OFFSET) {
629        if (m_len <= M3_MAX_LEN)
630            return 3;
631        m_len -= M3_MAX_LEN;
632    } else if (m_off <= M4_MAX_OFFSET) {
633        if (m_len <= M4_MAX_LEN)
634            return 3;
635        m_len -= M4_MAX_LEN;
636    } else
637        return -1;
638    while (m_len > 255) {
639        m_len -= 255;
640        n++;
641    }
642    return n;
643}
644
645
646static int min_gain(unsigned ahead, unsigned lit1,
647            unsigned lit2, int l1, int l2, int l3)
648{
649    int lazy_match_min_gain = 0;
650
651    assert (ahead >= 1);
652    lazy_match_min_gain += ahead;
653
654    if (lit1 <= 3)
655        lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
656    else if (lit1 <= 18)
657        lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
658
659    lazy_match_min_gain += (l2 - l1) * 2;
660    if (l3 > 0)
661        lazy_match_min_gain -= (ahead - l3) * 2;
662
663    if (lazy_match_min_gain < 0)
664        lazy_match_min_gain = 0;
665
666    return lazy_match_min_gain;
667}
668
669
670/***********************************************************************
671//
672************************************************************************/
673#if defined(SWD_BEST_OFF)
674
675static void better_match(const lzo_swd_p swd,
676               unsigned *m_len, unsigned *m_off)
677{
678    if (*m_len <= M2_MIN_LEN)
679        return;
680
681    if (*m_off <= M2_MAX_OFFSET)
682        return;
683
684    /* M3/M4 -> M2 */
685    if (*m_off > M2_MAX_OFFSET
686     && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
687     && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
688    ) {
689        *m_len = *m_len - 1;
690        *m_off = swd->best_off[*m_len];
691        return;
692    }
693
694    /* M4 -> M2 */
695    if (*m_off > M3_MAX_OFFSET
696     && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
697     && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
698    ) {
699        *m_len = *m_len - 2;
700        *m_off = swd->best_off[*m_len];
701        return;
702    }
703    /* M4 -> M3 */
704    if (*m_off > M3_MAX_OFFSET
705     && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
706     && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
707    ) {
708        *m_len = *m_len - 1;
709        *m_off = swd->best_off[*m_len];
710    }
711}
712
713#endif
714
715
716/***********************************************************************
717//
718************************************************************************/
719static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
720        uint8_t *out, unsigned *out_len,
721        void *wrkmem,
722        unsigned good_length,
723        unsigned max_lazy,
724        unsigned max_chain,
725        uint32_t use_best_off)
726{
727    uint8_t *op;
728    const uint8_t *ii;
729    unsigned lit;
730    unsigned m_len, m_off;
731    lzo1x_999_t cc;
732    lzo1x_999_t *const c = &cc;
733    const lzo_swd_p swd = (lzo_swd_p) wrkmem;
734    int r;
735
736    c->init = 0;
737    c->ip = c->in = in;
738    c->in_end = in + in_len;
739    c->out = out;
740
741    op = out;
742    ii = c->ip;             /* point to start of literal run */
743    lit = 0;
744    c->r1_lit = 0;
745
746    r = init_match(c, swd, use_best_off);
747    if (r != 0)
748        return r;
749    swd->max_chain = max_chain;
750
751    r = find_match(c, swd, 0, 0);
752    if (r != 0)
753        return r;
754
755    while (c->look > 0) {
756        unsigned ahead;
757        unsigned max_ahead;
758        int l1, l2, l3;
759
760        m_len = c->m_len;
761        m_off = c->m_off;
762
763        assert(c->bp == c->ip - c->look);
764        assert(c->bp >= in);
765        if (lit == 0)
766            ii = c->bp;
767        assert(ii + lit == c->bp);
768        assert(swd->b_char == *(c->bp));
769
770        if (m_len < 2
771         || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
772            /* Do not accept this match for compressed-data compatibility
773             * with LZO v1.01 and before
774             * [ might be a problem for decompress() and optimize() ]
775             */
776         || (m_len == 2 && op == out)
777         || (op == out && lit == 0)
778        ) {
779            /* a literal */
780            m_len = 0;
781        }
782        else if (m_len == M2_MIN_LEN) {
783            /* compression ratio improves if we code a literal in some cases */
784            if (m_off > MX_MAX_OFFSET && lit >= 4)
785                m_len = 0;
786        }
787
788        if (m_len == 0) {
789            /* a literal */
790            lit++;
791            swd->max_chain = max_chain;
792            r = find_match(c, swd, 1, 0);
793            assert(r == 0);
794            continue;
795        }
796
797        /* a match */
798#if defined(SWD_BEST_OFF)
799        if (swd->use_best_off)
800            better_match(swd, &m_len, &m_off);
801#endif
802
803        /* shall we try a lazy match ? */
804        ahead = 0;
805        if (m_len >= max_lazy) {
806            /* no */
807            l1 = 0;
808            max_ahead = 0;
809        } else {
810            /* yes, try a lazy match */
811            l1 = len_of_coded_match(m_len, m_off, lit);
812            assert(l1 > 0);
813            max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
814        }
815
816
817        while (ahead < max_ahead && c->look > m_len) {
818            int lazy_match_min_gain;
819
820            if (m_len >= good_length)
821                swd->max_chain = max_chain >> 2;
822            else
823                swd->max_chain = max_chain;
824            r = find_match(c, swd, 1, 0);
825            ahead++;
826
827            assert(r == 0);
828            assert(c->look > 0);
829            assert(ii + lit + ahead == c->bp);
830
831            if (c->m_len < m_len)
832                continue;
833            if (c->m_len == m_len && c->m_off >= m_off)
834                continue;
835#if defined(SWD_BEST_OFF)
836            if (swd->use_best_off)
837                better_match(swd, &c->m_len, &c->m_off);
838#endif
839            l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
840            if (l2 < 0)
841                continue;
842
843            /* compressed-data compatibility [see above] */
844            l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
845
846            lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
847            if (c->m_len >= m_len + lazy_match_min_gain) {
848                if (l3 > 0) {
849                    /* code previous run */
850                    op = code_run(c, op, ii, lit);
851                    lit = 0;
852                    /* code shortened match */
853                    op = code_match(c, op, ahead, m_off);
854                } else {
855                    lit += ahead;
856                    assert(ii + lit == c->bp);
857                }
858                goto lazy_match_done;
859            }
860        }
861
862        assert(ii + lit + ahead == c->bp);
863
864        /* 1 - code run */
865        op = code_run(c, op, ii, lit);
866        lit = 0;
867
868        /* 2 - code match */
869        op = code_match(c, op, m_len, m_off);
870        swd->max_chain = max_chain;
871        r = find_match(c, swd, m_len, 1+ahead);
872        assert(r == 0);
873
874 lazy_match_done: ;
875    }
876
877    /* store final run */
878    if (lit > 0)
879        op = STORE_RUN(c, op, ii, lit);
880
881#if defined(LZO_EOF_CODE)
882    *op++ = M4_MARKER | 1;
883    *op++ = 0;
884    *op++ = 0;
885#endif
886
887    *out_len = op - out;
888
889    return LZO_E_OK;
890}
891
892
893/***********************************************************************
894//
895************************************************************************/
896int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
897        uint8_t *out, unsigned *out_len,
898        void *wrkmem,
899        int compression_level)
900{
901    static const struct {
902        uint16_t good_length;
903        uint16_t max_lazy;
904        uint16_t max_chain;
905        uint16_t use_best_off;
906    } c[3] = {
907        {     8,    32,  256,   0 },
908        {    32,   128, 2048,   1 },
909        { SWD_F, SWD_F, 4096,   1 }       /* max. compression */
910    };
911
912    if (compression_level < 7 || compression_level > 9)
913        return LZO_E_ERROR;
914
915    compression_level -= 7;
916    return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
917                       c[compression_level].good_length,
918                       c[compression_level].max_lazy,
919                       c[compression_level].max_chain,
920                       c[compression_level].use_best_off);
921}
Note: See TracBrowser for help on using the repository browser.