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