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