1/* lzo1f_9x.c -- implementation of the LZO1F-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 "config1f.h"
42
43
44/***********************************************************************
45//
46************************************************************************/
47
48#define N           16383           /* 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 LZO1F
54#define LZO_COMPRESS_T  lzo1f_999_t
55#define lzo_swd_t       lzo1f_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        m_off -= 1;
70        *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2));
71        *op++ = LZO_BYTE(m_off >> 3);
72        c->m2_m++;
73    }
74    else if (m_len == M2_MIN_LEN && m_off <= 2 * M2_MAX_OFFSET &&
75             c->r1_lit > 0)
76    {
77        assert(m_off > M2_MAX_OFFSET);
78        m_off -= 1 + M2_MAX_OFFSET;
79        *op++ = LZO_BYTE(((m_off & 7) << 2));
80        *op++ = LZO_BYTE(m_off >> 3);
81        c->r1_r++;
82    }
83    else
84    {
85        if (m_len <= M3_MAX_LEN)
86            *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
87        else
88        {
89            m_len -= M3_MAX_LEN;
90            *op++ = M3_MARKER | 0;
91            while (m_len > 255)
92            {
93                m_len -= 255;
94                *op++ = 0;
95            }
96            assert(m_len > 0);
97            *op++ = LZO_BYTE(m_len);
98        }
99        *op++ = LZO_BYTE((m_off & 63) << 2);
100        *op++ = LZO_BYTE(m_off >> 6);
101        c->m3_m++;
102    }
103
104    return op;
105}
106
107
108static lzo_bytep
109STORE_RUN ( lzo_bytep op, const lzo_bytep ii, lzo_uint t, lzo_bytep out )
110{
111    if (t < 4 && op > out)
112        op[-2] |= LZO_BYTE(t);
113    else if (t <= 31)
114        *op++ = LZO_BYTE(t);
115    else
116    {
117        lzo_uint tt = t - 31;
118
119        *op++ = 0;
120        while (tt > 255)
121        {
122            tt -= 255;
123            *op++ = 0;
124        }
125        assert(tt > 0);
126        *op++ = LZO_BYTE(tt);
127    }
128    do *op++ = *ii++; while (--t > 0);
129
130    return op;
131}
132
133
134/***********************************************************************
135// this is a public function, but there is no prototype in a header file
136************************************************************************/
137
138LZO_EXTERN(int)
139lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
140                                    lzo_bytep out, lzo_uintp out_len,
141                                    lzo_voidp wrkmem,
142                                    lzo_callback_p cb,
143                                    lzo_uint max_chain );
144
145LZO_PUBLIC(int)
146lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
147                                    lzo_bytep out, lzo_uintp out_len,
148                                    lzo_voidp wrkmem,
149                                    lzo_callback_p cb,
150                                    lzo_uint max_chain )
151{
152    lzo_bytep op;
153    const lzo_bytep ii;
154    lzo_uint lit;
155    lzo_uint m_len, m_off;
156    LZO_COMPRESS_T cc;
157    LZO_COMPRESS_T * const c = &cc;
158    lzo_swd_p const swd = (lzo_swd_p) wrkmem;
159    int r;
160
161    /* sanity check */
162    LZO_COMPILE_TIME_ASSERT(LZO1F_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
163
164    c->init = 0;
165    c->ip = c->in = in;
166    c->in_end = in + in_len;
167    c->cb = cb;
168    c->r1_r = c->m2_m = c->m3_m = 0;
169
170    op = out;
171    ii = c->ip;             /* point to start of literal run */
172    lit = 0;
173    c->r1_lit = c->r1_m_len = 0;
174
175    r = init_match(c,swd,NULL,0,0);
176    if (r != 0)
177        return r;
178    if (max_chain > 0)
179        swd->max_chain = max_chain;
180
181    r = find_match(c,swd,0,0);
182    if (r != 0)
183        return r;
184    while (c->look > 0)
185    {
186        int lazy_match_min_gain = -1;
187        lzo_uint ahead = 0;
188
189        m_len = c->m_len;
190        m_off = c->m_off;
191
192        assert(c->ip - c->look >= in);
193        if (lit == 0)
194            ii = c->ip - c->look;
195        assert(ii + lit == c->ip - c->look);
196        assert(swd->b_char == *(c->ip - c->look));
197
198        if ((m_len < M2_MIN_LEN) ||
199            (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
200        {
201            m_len = 0;
202        }
203        else
204        {
205            assert(c->ip - c->look - m_off >= in);
206            assert(c->ip - c->look - m_off + m_len < c->ip);
207            assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
208                              m_len) == 0);
209
210            if (lit < 3)
211                lazy_match_min_gain = 1;
212            else if (lit == 3)
213                lazy_match_min_gain = 3;
214            else if (lit == 31)
215                lazy_match_min_gain = 3;
216            else
217                lazy_match_min_gain = 1;
218        }
219
220        /* try a lazy match */
221        if (m_len > 0 && lazy_match_min_gain >= 0 && c->look > m_len)
222        {
223            r = find_match(c,swd,1,0);
224            assert(r == 0);
225            assert(c->look > 0);
226
227            if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
228                c->m_off > M2_MAX_OFFSET)
229            {
230                lazy_match_min_gain += 1;
231            }
232            else if (c->m_len <= M2_MAX_LEN &&
233                     c->m_off <= M2_MAX_OFFSET &&
234                     m_off > M2_MAX_OFFSET)
235            {
236                if (lazy_match_min_gain > 0)
237                    lazy_match_min_gain -= 1;
238            }
239            else if (m_len == M2_MIN_LEN && c->m_len == M2_MIN_LEN &&
240                     c->m_off <= 2 * M2_MAX_OFFSET &&
241                     m_off > M2_MAX_OFFSET)
242            {
243                if (lazy_match_min_gain > 0)
244                    lazy_match_min_gain -= 1;
245            }
246
247            if (c->m_len >= m_len + lazy_match_min_gain)
248            {
249                c->lazy++;
250#if !defined(NDEBUG)
251                m_len = c->m_len;
252                m_off = c->m_off;
253                assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
254                                  m_len) == 0);
255#endif
256                lit++;
257                assert(ii + lit == c->ip - c->look);
258                continue;
259            }
260            else
261            {
262                ahead = 1;
263                assert(ii + lit + 1 == c->ip - c->look);
264            }
265            assert(m_len > 0);
266        }
267        assert(ii + lit + ahead == c->ip - c->look);
268
269
270        if (m_len == 0)
271        {
272            /* a literal */
273            lit++;
274            r = find_match(c,swd,1,0);
275            assert(r == 0);
276        }
277        else
278        {
279            /* 1 - store run */
280            if (lit > 0)
281            {
282                op = STORE_RUN(op,ii,lit,out);
283                c->r1_m_len = m_len;
284                c->r1_lit = lit;
285                lit = 0;
286            }
287            else
288                c->r1_lit = c->r1_m_len = 0;
289
290            /* 2 - code match */
291            op = code_match(c,op,m_len,m_off);
292            r = find_match(c,swd,m_len,1+ahead);
293            assert(r == 0);
294        }
295
296        c->codesize = pd(op, out);
297    }
298
299
300    /* store final run */
301    if (lit > 0)
302        op = STORE_RUN(op,ii,lit,out);
303
304#if defined(LZO_EOF_CODE)
305    *op++ = M3_MARKER | 1;
306    *op++ = 0;
307    *op++ = 0;
308#endif
309
310    c->codesize = pd(op, out);
311    assert(c->textsize == in_len);
312
313    *out_len = pd(op, out);
314
315    if (c->cb && c->cb->nprogress)
316        (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
317
318#if 0
319    printf("%ld %ld -> %ld: %ld %ld %ld %ld\n",
320        (long) c->textsize, (long)in_len, (long) c->codesize,
321        c->r1_r, c->m2_m, c->m3_m, c->lazy);
322#endif
323    return LZO_E_OK;
324}
325
326
327
328/***********************************************************************
329//
330************************************************************************/
331
332LZO_PUBLIC(int)
333lzo1f_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
334                            lzo_bytep out, lzo_uintp out_len,
335                            lzo_voidp wrkmem )
336{
337    return lzo1f_999_compress_callback(in,in_len,out,out_len,wrkmem,
338                                       (lzo_callback_p) 0, 0);
339}
340
341
342/*
343vi:ts=4:et
344*/
345
346