1/* lzo2a_9x.c -- implementation of the LZO2A-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
45#include "config2a.h"
46
47
48/***********************************************************************
49//
50************************************************************************/
51
52#define SWD_THRESHOLD       1           /* lower limit for match length */
53#define SWD_F            2048           /* upper limit for match length */
54
55
56#define LZO2A 1
57#define LZO_COMPRESS_T  lzo2a_999_t
58#define lzo_swd_t       lzo2a_999_swd_t
59#include "lzo_mchw.ch"
60
61
62#if (LZO_CC_BORLANDC && LZO_MM_FLAT)
63#  if ((__BORLANDC__) >= 0x0450 && (__BORLANDC__) < 0x0460)
64     /* avoid internal compiler error */
65#    pragma option -Od
66#  endif
67#endif
68
69
70/***********************************************************************
71//
72************************************************************************/
73
74#define putbyte(x)      *op++ = LZO_BYTE(x)
75
76#define putbits(j,x) \
77    if (k == 0) bitp = op++; \
78    SETBITS(j,x); \
79    if (k >= 8) { *bitp = LZO_BYTE(MASKBITS(8)); DUMPBITS(8); \
80                    if (k > 0) bitp = op++; }
81
82#define putbit(x)       putbits(1,x)
83
84
85/***********************************************************************
86// this is a public function, but there is no prototype in a header file
87************************************************************************/
88
89LZO_EXTERN(int)
90lzo2a_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
91                                    lzo_bytep out, lzo_uintp out_len,
92                                    lzo_voidp wrkmem,
93                                    lzo_callback_p cb,
94                                    lzo_uint max_chain );
95
96LZO_PUBLIC(int)
97lzo2a_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
98                                    lzo_bytep out, lzo_uintp out_len,
99                                    lzo_voidp wrkmem,
100                                    lzo_callback_p cb,
101                                    lzo_uint max_chain )
102{
103    lzo_bytep op;
104    lzo_bytep bitp = 0;
105    lzo_uint m_len, m_off;
106    LZO_COMPRESS_T cc;
107    LZO_COMPRESS_T * const c = &cc;
108    lzo_swd_p const swd = (lzo_swd_p) wrkmem;
109    int r;
110
111    lzo_uint32 b = 0;       /* bit buffer */
112    unsigned k = 0;         /* bits in bit buffer */
113
114    /* sanity check */
115    LZO_COMPILE_TIME_ASSERT(LZO2A_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
116
117    c->init = 0;
118    c->ip = c->in = in;
119    c->in_end = in + in_len;
120    c->cb = cb;
121    c->m1 = c->m2 = c->m3 = c->m4 = 0;
122
123    op = out;
124
125    r = init_match(c,swd,NULL,0,0);
126    if (r != 0)
127        return r;
128    if (max_chain > 0)
129        swd->max_chain = max_chain;
130
131    r = find_match(c,swd,0,0);
132    if (r != 0)
133        return r;
134    while (c->look > 0)
135    {
136        lzo_uint lazy_match_min_gain = 0;
137#if (SWD_N >= 8192)
138        lzo_uint extra1 = 0;
139#endif
140        lzo_uint extra2 = 0;
141        lzo_uint ahead = 0;
142
143        m_len = c->m_len;
144        m_off = c->m_off;
145
146#if (SWD_N >= 8192)
147        if (m_off >= 8192)
148        {
149            if (m_len < M3_MIN_LEN)
150                m_len = 0;
151            else
152                lazy_match_min_gain = 1;
153        }
154        else
155#endif
156        if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
157        {
158            lazy_match_min_gain = 2;
159#if (SWD_N >= 8192)
160            extra1 = 3;
161#endif
162            extra2 = 2;
163        }
164        else if (m_len >= 10)
165            lazy_match_min_gain = 1;
166        else if (m_len >= 3)
167        {
168            lazy_match_min_gain = 1;
169#if (SWD_N >= 8192)
170            extra1 = 1;
171#endif
172        }
173        else
174            m_len = 0;
175
176
177        /* try a lazy match */
178        if (lazy_match_min_gain > 0 && c->look > m_len)
179        {
180            unsigned char lit = LZO_BYTE(swd->b_char);
181
182            r = find_match(c,swd,1,0);
183            assert(r == 0); LZO_UNUSED(r);
184            assert(c->look > 0);
185
186#if (SWD_N >= 8192)
187            if (m_off < 8192 && c->m_off >= 8192)
188                lazy_match_min_gain += extra1;
189            else
190#endif
191            if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
192            {
193                if (!(c->m_len >= M1_MIN_LEN &&
194                      c->m_len <= M1_MAX_LEN && c->m_off <= 256))
195                    lazy_match_min_gain += extra2;
196            }
197            if (c->m_len >= M1_MIN_LEN &&
198                c->m_len <= M1_MAX_LEN && c->m_off <= 256)
199            {
200                    lazy_match_min_gain -= 1;
201            }
202
203            if ((lzo_int) lazy_match_min_gain < 1)
204                lazy_match_min_gain = 1;
205
206            if (c->m_len >= m_len + lazy_match_min_gain)
207            {
208                c->lazy++;
209#if !defined(NDEBUG)
210                m_len = c->m_len;
211                m_off = c->m_off;
212                assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
213                                  m_len) == 0);
214                assert(m_len >= 3 || (m_len >= 2 && m_off <= 256));
215#endif
216                /* code literal */
217                putbit(0);
218                putbyte(lit);
219                c->lit_bytes++;
220                continue;
221            }
222            else
223                ahead = 1;
224            assert(m_len > 0);
225        }
226
227
228        if (m_len == 0)
229        {
230            /* a literal */
231            putbit(0);
232            putbyte(swd->b_char);
233            c->lit_bytes++;
234            r = find_match(c,swd,1,0);
235            assert(r == 0); LZO_UNUSED(r);
236        }
237        else
238        {
239            assert(m_len >= M1_MIN_LEN);
240            assert(m_off > 0);
241            assert(m_off <= SWD_N);
242
243            /* 2 - code match */
244            if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
245            {
246                putbit(1);
247                putbit(0);
248                putbits(2,m_len - M1_MIN_LEN);
249                putbyte(m_off - 1);
250                c->m1++;
251            }
252#if (SWD_N >= 8192)
253            else if (m_off >= 8192)
254            {
255                unsigned len = m_len;
256                assert(m_len >= M3_MIN_LEN);
257                putbit(1);
258                putbit(1);
259                putbyte(m_off & 31);
260                putbyte(m_off >> 5);
261                putbit(1);
262                len -= M3_MIN_LEN - 1;
263                while (len > 255)
264                {
265                    len -= 255;
266                    putbyte(0);
267                }
268                putbyte(len);
269                c->m4++;
270            }
271#endif
272            else
273            {
274                assert(m_len >= 3);
275
276                putbit(1);
277                putbit(1);
278                if (m_len <= 9)
279                {
280                    putbyte(((m_len - 2) << 5) | (m_off & 31));
281                    putbyte(m_off >> 5);
282                    c->m2++;
283                }
284                else
285                {
286                    lzo_uint len = m_len;
287                    putbyte(m_off & 31);
288                    putbyte(m_off >> 5);
289#if (SWD_N >= 8192)
290                    putbit(0);
291#endif
292                    len -= 10 - 1;
293                    while (len > 255)
294                    {
295                        len -= 255;
296                        putbyte(0);
297                    }
298                    putbyte(len);
299                    c->m3++;
300                }
301            }
302            r = find_match(c,swd,m_len,1+ahead);
303            assert(r == 0); LZO_UNUSED(r);
304        }
305
306        c->codesize = pd(op, out);
307    }
308
309#if defined(LZO_EOF_CODE)
310    /* code EOF code */
311    putbit(1);
312    putbit(1);
313    putbyte(1 << 5);
314    putbyte(0);
315#endif
316
317    /* flush remaining bits */
318    assert(k < CHAR_BIT);
319    if (k > 0)
320    {
321        assert(b == MASKBITS(k));
322        assert(op - bitp > 1);
323        *bitp = LZO_BYTE(MASKBITS(k));
324        DUMPBITS(k);
325        assert(b == 0);
326        assert(k == 0);
327    }
328
329    assert(c->textsize == in_len);
330    c->codesize = pd(op, out);
331
332    *out_len = pd(op, out);
333
334    if (c->cb && c->cb->nprogress)
335        (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
336
337#if 0
338    printf("%ld -> %ld: %ld %ld %ld %ld %ld %ld\n",
339        (long) c->textsize, (long) c->codesize,
340        c->lit_bytes, c->m1, c->m2, c->m3, c->m4, c->lazy);
341#endif
342    return LZO_E_OK;
343}
344
345
346
347/***********************************************************************
348//
349************************************************************************/
350
351LZO_PUBLIC(int)
352lzo2a_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
353                            lzo_bytep out, lzo_uintp out_len,
354                            lzo_voidp wrkmem )
355{
356    return lzo2a_999_compress_callback(in,in_len,out,out_len,wrkmem,
357                                       (lzo_callback_p) 0, 0);
358}
359
360
361/*
362vi:ts=4:et
363*/
364
365