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