/src/lzo-2.10/src/lzo1f_9x.c

Source
/* lzo1f_9x.c -- implementation of the LZO1F-999 compression algorithm

   This file is part of the LZO real-time data compression library.

   Copyright (C) 1996-2017 Markus Franz Xaver Johannes Oberhumer
   All Rights Reserved.

   The LZO library is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of
   the License, or (at your option) any later version.

   The LZO library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with the LZO library; see the file COPYING.
   If not, write to the Free Software Foundation, Inc.,
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

   Markus F.X.J. Oberhumer
   <markus@oberhumer.com>
   http://www.oberhumer.com/opensource/lzo/
 */


#include "config1f.h"


/***********************************************************************
//
************************************************************************/

#define SWD_N           16383           /* size of ring buffer */
#define SWD_THRESHOLD       2           /* lower limit for match length */
#define SWD_F            2048           /* upper limit for match length */


#define LZO1F 1
#define LZO_COMPRESS_T  lzo1f_999_t
#define lzo_swd_t       lzo1f_999_swd_t
#include "lzo_mchw.ch"



/***********************************************************************
//
************************************************************************/

static lzo_bytep
code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
{
    if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
    {
        m_off -= 1;
        *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2));
        *op++ = LZO_BYTE(m_off >> 3);
        c->m2_m++;
    }
    else if (m_len == M2_MIN_LEN && m_off <= 2 * M2_MAX_OFFSET &&
             c->r1_lit > 0)
    {
        assert(m_off > M2_MAX_OFFSET);
        m_off -= 1 + M2_MAX_OFFSET;
        *op++ = LZO_BYTE(((m_off & 7) << 2));
        *op++ = LZO_BYTE(m_off >> 3);
        c->r1_r++;
    }
    else
    {
        if (m_len <= M3_MAX_LEN)
            *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
        else
        {
            m_len -= M3_MAX_LEN;
            *op++ = M3_MARKER | 0;
            while (m_len > 255)
            {
                m_len -= 255;
                *op++ = 0;
            }
            assert(m_len > 0);
            *op++ = LZO_BYTE(m_len);
        }
        *op++ = LZO_BYTE((m_off & 63) << 2);
        *op++ = LZO_BYTE(m_off >> 6);
        c->m3_m++;
    }

    return op;
}


static lzo_bytep
STORE_RUN ( lzo_bytep op, const lzo_bytep ii, lzo_uint t, lzo_bytep out )
{
    if (t < 4 && op > out)
        op[-2] = LZO_BYTE(op[-2] | t);
    else if (t <= 31)
        *op++ = LZO_BYTE(t);
    else
    {
        lzo_uint tt = t - 31;

        *op++ = 0;
        while (tt > 255)
        {
            tt -= 255;
            *op++ = 0;
        }
        assert(tt > 0);
        *op++ = LZO_BYTE(tt);
    }
    do *op++ = *ii++; while (--t > 0);

    return op;
}


/***********************************************************************
// this is a public function, but there is no prototype in a header file
************************************************************************/

LZO_EXTERN(int)
lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
                                    lzo_bytep out, lzo_uintp out_len,
                                    lzo_voidp wrkmem,
                                    lzo_callback_p cb,
                                    lzo_uint max_chain );

LZO_PUBLIC(int)
lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
                                    lzo_bytep out, lzo_uintp out_len,
                                    lzo_voidp wrkmem,
                                    lzo_callback_p cb,
                                    lzo_uint max_chain )
{
    lzo_bytep op;
    const lzo_bytep ii;
    lzo_uint lit;
    lzo_uint m_len, m_off;
    LZO_COMPRESS_T cc;
    LZO_COMPRESS_T * const c = &cc;
    lzo_swd_p const swd = (lzo_swd_p) wrkmem;
    int r;

    /* sanity check */
    LZO_COMPILE_TIME_ASSERT(LZO1F_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)

    c->init = 0;
    c->ip = c->in = in;
    c->in_end = in + in_len;
    c->cb = cb;
    c->r1_r = c->m2_m = c->m3_m = 0;

    op = out;
    ii = c->ip;             /* point to start of literal run */
    lit = 0;
    c->r1_lit = c->r1_m_len = 0;

    r = init_match(c,swd,NULL,0,0);
    if (r != 0)
        return r;
    if (max_chain > 0)
        swd->max_chain = max_chain;

    r = find_match(c,swd,0,0);
    if (r != 0)
        return r;
    while (c->look > 0)
    {
        int lazy_match_min_gain = -1;
        lzo_uint ahead = 0;

        m_len = c->m_len;
        m_off = c->m_off;

        assert(c->ip - c->look >= in);
        if (lit == 0)
            ii = c->ip - c->look;
        assert(ii + lit == c->ip - c->look);
        assert(swd->b_char == *(c->ip - c->look));

        if ((m_len < M2_MIN_LEN) ||
            (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
        {
            m_len = 0;
        }
        else
        {
            assert(c->ip - c->look - m_off >= in);
            assert(c->ip - c->look - m_off + m_len < c->ip);
            assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
                              m_len) == 0);

            if (lit < 3)
                lazy_match_min_gain = 1;
            else if (lit == 3)
                lazy_match_min_gain = 3;
            else if (lit == 31)
                lazy_match_min_gain = 3;
            else
                lazy_match_min_gain = 1;
        }

        /* try a lazy match */
        if (m_len > 0 && lazy_match_min_gain >= 0 && c->look > m_len)
        {
            r = find_match(c,swd,1,0);
            assert(r == 0); LZO_UNUSED(r);
            assert(c->look > 0);

            if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
                c->m_off > M2_MAX_OFFSET)
            {
                lazy_match_min_gain += 1;
            }
            else if (c->m_len <= M2_MAX_LEN &&
                     c->m_off <= M2_MAX_OFFSET &&
                     m_off > M2_MAX_OFFSET)
            {
                if (lazy_match_min_gain > 0)
                    lazy_match_min_gain -= 1;
            }
            else if (m_len == M2_MIN_LEN && c->m_len == M2_MIN_LEN &&
                     c->m_off <= 2 * M2_MAX_OFFSET &&
                     m_off > M2_MAX_OFFSET)
            {
                if (lazy_match_min_gain > 0)
                    lazy_match_min_gain -= 1;
            }

            if (c->m_len >= m_len + lazy_match_min_gain)
            {
                c->lazy++;
#if !defined(NDEBUG)
                m_len = c->m_len;
                m_off = c->m_off;
                assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
                                  m_len) == 0);
#endif
                lit++;
                assert(ii + lit == c->ip - c->look);
                continue;
            }
            else
            {
                ahead = 1;
                assert(ii + lit + 1 == c->ip - c->look);
            }
            assert(m_len > 0);
        }
        assert(ii + lit + ahead == c->ip - c->look);


        if (m_len == 0)
        {
            /* a literal */
            lit++;
            r = find_match(c,swd,1,0);
            assert(r == 0); LZO_UNUSED(r);
        }
        else
        {
            /* 1 - store run */
            if (lit > 0)
            {
                op = STORE_RUN(op,ii,lit,out);
                c->r1_m_len = m_len;
                c->r1_lit = lit;
                lit = 0;
            }
            else
                c->r1_lit = c->r1_m_len = 0;

            /* 2 - code match */
            op = code_match(c,op,m_len,m_off);
            r = find_match(c,swd,m_len,1+ahead);
            assert(r == 0); LZO_UNUSED(r);
        }

        c->codesize = pd(op, out);
    }


    /* store final run */
    if (lit > 0)
        op = STORE_RUN(op,ii,lit,out);

#if defined(LZO_EOF_CODE)
    *op++ = M3_MARKER | 1;
    *op++ = 0;
    *op++ = 0;
#endif

    c->codesize = pd(op, out);
    assert(c->textsize == in_len);

    *out_len = pd(op, out);

    if (c->cb && c->cb->nprogress)
        (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);

#if 0
    printf("%ld %ld -> %ld: %ld %ld %ld %ld\n",
        (long) c->textsize, (long)in_len, (long) c->codesize,
        c->r1_r, c->m2_m, c->m3_m, c->lazy);
#endif
    return LZO_E_OK;
}



/***********************************************************************
//
************************************************************************/

LZO_PUBLIC(int)
lzo1f_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
                            lzo_bytep out, lzo_uintp out_len,
                            lzo_voidp wrkmem )
{
    return lzo1f_999_compress_callback(in,in_len,out,out_len,wrkmem,
                                       (lzo_callback_p) 0, 0);
}


/* vim:set ts=4 sw=4 et: */

Coverage Report

Created: 2025-12-10 06:47

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