OptIO/src/lzo1x_c.ch

/* lzo1x_c.ch -- implementation of the LZO1[XY]-1 compression algorithm

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

   Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
   Copyright (C) 1996 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/
 */


/***********************************************************************
// compress a block of data.
************************************************************************/

static __lzo_noinline lzo_uint
do_compress ( const lzo_bytep in , lzo_uint  in_len,
                    lzo_bytep out, lzo_uintp out_len,
                    lzo_voidp wrkmem )
{
    register const lzo_bytep ip;
    lzo_bytep op;
    const lzo_bytep const in_end = in + in_len;
    const lzo_bytep const ip_end = in + in_len - M2_MAX_LEN - 5;
    const lzo_bytep ii;
    lzo_dict_p const dict = (lzo_dict_p) wrkmem;

    op = out;
    ip = in;
    ii = ip;

    ip += 4;
    for (;;)
    {
        register const lzo_bytep m_pos;
        lzo_uint m_off;
        lzo_uint m_len;
        lzo_uint dindex;

        DINDEX1(dindex,ip);
        GINDEX(m_pos,m_off,dict,dindex,in);
        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
            goto literal;
#if 1
        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
            goto try_match;
        DINDEX2(dindex,ip);
#endif
        GINDEX(m_pos,m_off,dict,dindex,in);
        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
            goto literal;
        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
            goto try_match;
        goto literal;


try_match:
#if 1 && defined(LZO_UNALIGNED_OK_2)
        if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
#else
        if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
#endif
        {
        }
        else
        {
            if __lzo_likely(m_pos[2] == ip[2])
            {
#if 0
                if (m_off <= M2_MAX_OFFSET)
                    goto match;
                if (lit <= 3)
                    goto match;
                if (lit == 3)           /* better compression, but slower */
                {
                    assert(op - 2 > out); op[-2] |= LZO_BYTE(3);
                    *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
                    goto code_match;
                }
                if (m_pos[3] == ip[3])
#endif
                    goto match;
            }
            else
            {
                /* still need a better way for finding M1 matches */
#if 0
                /* a M1 match */
#if 0
                if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
#else
                if (m_off <= M1_MAX_OFFSET && lit == 3)
#endif
                {
                    register lzo_uint t;

                    t = lit;
                    assert(op - 2 > out); op[-2] |= LZO_BYTE(t);
                    do *op++ = *ii++; while (--t > 0);
                    assert(ii == ip);
                    m_off -= 1;
                    *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
                    *op++ = LZO_BYTE(m_off >> 2);
                    ip += 2;
                    goto match_done;
                }
#endif
            }
        }


    /* a literal */
literal:
        UPDATE_I(dict,0,dindex,ip,in);
        ++ip;
        if __lzo_unlikely(ip >= ip_end)
            break;
        continue;


    /* a match */
match:
        UPDATE_I(dict,0,dindex,ip,in);
        /* store current literal run */
        if (pd(ip,ii) > 0)
        {
            register lzo_uint t = pd(ip,ii);

            if (t <= 3)
            {
                assert(op - 2 > out);
                op[-2] |= LZO_BYTE(t);
            }
            else if (t <= 18)
                *op++ = LZO_BYTE(t - 3);
            else
            {
                register lzo_uint tt = t - 18;

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

        /* code the match */
        assert(ii == ip);
        ip += 3;
        if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ ||
            m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++
#ifdef LZO1Y
            || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++
            || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++
#endif
           )
        {
            --ip;
            m_len = pd(ip, ii);
            assert(m_len >= 3); assert(m_len <= M2_MAX_LEN);

            if (m_off <= M2_MAX_OFFSET)
            {
                m_off -= 1;
#if defined(LZO1X)
                *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
                *op++ = LZO_BYTE(m_off >> 3);
#elif defined(LZO1Y)
                *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
                *op++ = LZO_BYTE(m_off >> 2);
#endif
            }
            else if (m_off <= M3_MAX_OFFSET)
            {
                m_off -= 1;
                *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
                goto m3_m4_offset;
            }
            else
#if defined(LZO1X)
            {
                m_off -= 0x4000;
                assert(m_off > 0); assert(m_off <= 0x7fff);
                *op++ = LZO_BYTE(M4_MARKER |
                                 ((m_off & 0x4000) >> 11) | (m_len - 2));
                goto m3_m4_offset;
            }
#elif defined(LZO1Y)
                goto m4_match;
#endif
        }
        else
        {
            {
                const lzo_bytep end = in_end;
                const lzo_bytep m = m_pos + M2_MAX_LEN + 1;
                while (ip < end && *m == *ip)
                    m++, ip++;
                m_len = pd(ip, ii);
            }
            assert(m_len > M2_MAX_LEN);

            if (m_off <= M3_MAX_OFFSET)
            {
                m_off -= 1;
                if (m_len <= 33)
                    *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
                else
                {
                    m_len -= 33;
                    *op++ = M3_MARKER | 0;
                    goto m3_m4_len;
                }
            }
            else
            {
#if defined(LZO1Y)
m4_match:
#endif
                m_off -= 0x4000;
                assert(m_off > 0); assert(m_off <= 0x7fff);
                if (m_len <= M4_MAX_LEN)
                    *op++ = LZO_BYTE(M4_MARKER |
                                     ((m_off & 0x4000) >> 11) | (m_len - 2));
                else
                {
                    m_len -= M4_MAX_LEN;
                    *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11));
m3_m4_len:
                    while (m_len > 255)
                    {
                        m_len -= 255;
                        *op++ = 0;
                    }
                    assert(m_len > 0);
                    *op++ = LZO_BYTE(m_len);
                }
            }

m3_m4_offset:
            *op++ = LZO_BYTE((m_off & 63) << 2);
            *op++ = LZO_BYTE(m_off >> 6);
        }

#if 0
match_done:
#endif
        ii = ip;
        if __lzo_unlikely(ip >= ip_end)
            break;
    }

    *out_len = pd(op, out);
    return pd(in_end,ii);
}


/***********************************************************************
// public entry point
************************************************************************/

LZO_PUBLIC(int)
DO_COMPRESS      ( const lzo_bytep in , lzo_uint  in_len,
                         lzo_bytep out, lzo_uintp out_len,
                         lzo_voidp wrkmem )
{
    lzo_bytep op = out;
    lzo_uint t;

    if __lzo_unlikely(in_len <= M2_MAX_LEN + 5)
        t = in_len;
    else
    {
        t = do_compress(in,in_len,op,out_len,wrkmem);
        op += *out_len;
    }

    if (t > 0)
    {
        const lzo_bytep ii = in + in_len - t;

        if (op == out && t <= 238)
            *op++ = LZO_BYTE(17 + t);
        else if (t <= 3)
            op[-2] |= LZO_BYTE(t);
        else if (t <= 18)
            *op++ = LZO_BYTE(t - 3);
        else
        {
            lzo_uint tt = t - 18;

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

    *op++ = M4_MARKER | 1;
    *op++ = 0;
    *op++ = 0;

    *out_len = pd(op, out);
    return LZO_E_OK;
}


/*
vi:ts=4:et
*/

Revision:	1.1
Committed:	Tue Feb 24 11:56:43 2009 UTC (16 years, 2 months ago) by loizides
Branch:	MAIN
CVS Tags:	Mit_032, Mit_031, Mit_025c_branch2, Mit_025c_branch1, Mit_030, Mit_029c, Mit_030_pre1, Mit_029a, Mit_029, Mit_029_pre1, Mit_028a, Mit_025c_branch0, Mit_028, Mit_027a, Mit_027, Mit_026, Mit_025e, Mit_025d, Mit_025c, Mit_025b, Mit_025a, Mit_025, Mit_025pre2, Mit_024b, Mit_025pre1, Mit_024a, Mit_024, Mit_023, Mit_022a, Mit_022, Mit_020d, TMit_020d, Mit_020c, Mit_021, Mit_021pre2, Mit_021pre1, Mit_020b, Mit_020a, Mit_020, Mit_020pre1, Mit_018, Mit_017, Mit_017pre3, Mit_017pre2, Mit_017pre1, V07-05-00, Mit_016, Mit_015b, Mit_015a, Mit_015, Mit_014e, Mit_014d, Mit_014c, Mit_014b, ConvRejection-10-06-09, Mit_014a, Mit_014, Mit_014pre3, Mit_014pre2, Mit_014pre1, Mit_013d, Mit_013c, Mit_013b, Mit_013a, Mit_013, Mit_013pre1, Mit_012i, Mit_012g, Mit_012f, Mit_012e, Mit_012d, Mit_012c, Mit_012b, Mit_012a, Mit_012, Mit_011a, Mit_011, Mit_010a, Mit_010, Mit_009c, Mit_009b, Mit_009a, Mit_009, Mit_008, Mit_008pre2, Mit_008pre1, HEAD
Branch point for:	Mit_025c_branch
Log Message:	Preload lib for compression improvements.
#	Content
1	/* lzo1x_c.ch -- implementation of the LZO1[XY]-1 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	/***********************************************************************
43	// compress a block of data.
44	************************************************************************/
45
46	static __lzo_noinline lzo_uint
47	do_compress ( const lzo_bytep in , lzo_uint in_len,
48	lzo_bytep out, lzo_uintp out_len,
49	lzo_voidp wrkmem )
50	{
51	register const lzo_bytep ip;
52	lzo_bytep op;
53	const lzo_bytep const in_end = in + in_len;
54	const lzo_bytep const ip_end = in + in_len - M2_MAX_LEN - 5;
55	const lzo_bytep ii;
56	lzo_dict_p const dict = (lzo_dict_p) wrkmem;
57
58	op = out;
59	ip = in;
60	ii = ip;
61
62	ip += 4;
63	for (;;)
64	{
65	register const lzo_bytep m_pos;
66	lzo_uint m_off;
67	lzo_uint m_len;
68	lzo_uint dindex;
69
70	DINDEX1(dindex,ip);
71	GINDEX(m_pos,m_off,dict,dindex,in);
72	if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
73	goto literal;
74	#if 1
75	if (m_off <= M2_MAX_OFFSET \|\| m_pos[3] == ip[3])
76	goto try_match;
77	DINDEX2(dindex,ip);
78	#endif
79	GINDEX(m_pos,m_off,dict,dindex,in);
80	if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
81	goto literal;
82	if (m_off <= M2_MAX_OFFSET \|\| m_pos[3] == ip[3])
83	goto try_match;
84	goto literal;
85
86
87	try_match:
88	#if 1 && defined(LZO_UNALIGNED_OK_2)
89	if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
90	#else
91	if (m_pos[0] != ip[0] \|\| m_pos[1] != ip[1])
92	#endif
93	{
94	}
95	else
96	{
97	if __lzo_likely(m_pos[2] == ip[2])
98	{
99	#if 0
100	if (m_off <= M2_MAX_OFFSET)
101	goto match;
102	if (lit <= 3)
103	goto match;
104	if (lit == 3) /* better compression, but slower */
105	{
106	assert(op - 2 > out); op[-2] \|= LZO_BYTE(3);
107	op++ = ii++; op++ = ii++; op++ = ii++;
108	goto code_match;
109	}
110	if (m_pos[3] == ip[3])
111	#endif
112	goto match;
113	}
114	else
115	{
116	/* still need a better way for finding M1 matches */
117	#if 0
118	/* a M1 match */
119	#if 0
120	if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
121	#else
122	if (m_off <= M1_MAX_OFFSET && lit == 3)
123	#endif
124	{
125	register lzo_uint t;
126
127	t = lit;
128	assert(op - 2 > out); op[-2] \|= LZO_BYTE(t);
129	do op++ = ii++; while (--t > 0);
130	assert(ii == ip);
131	m_off -= 1;
132	*op++ = LZO_BYTE(M1_MARKER \| ((m_off & 3) << 2));
133	*op++ = LZO_BYTE(m_off >> 2);
134	ip += 2;
135	goto match_done;
136	}
137	#endif
138	}
139	}
140
141
142	/* a literal */
143	literal:
144	UPDATE_I(dict,0,dindex,ip,in);
145	++ip;
146	if __lzo_unlikely(ip >= ip_end)
147	break;
148	continue;
149
150
151	/* a match */
152	match:
153	UPDATE_I(dict,0,dindex,ip,in);
154	/* store current literal run */
155	if (pd(ip,ii) > 0)
156	{
157	register lzo_uint t = pd(ip,ii);
158
159	if (t <= 3)
160	{
161	assert(op - 2 > out);
162	op[-2] \|= LZO_BYTE(t);
163	}
164	else if (t <= 18)
165	*op++ = LZO_BYTE(t - 3);
166	else
167	{
168	register lzo_uint tt = t - 18;
169
170	*op++ = 0;
171	while (tt > 255)
172	{
173	tt -= 255;
174	*op++ = 0;
175	}
176	assert(tt > 0);
177	*op++ = LZO_BYTE(tt);
178	}
179	do op++ = ii++; while (--t > 0);
180	}
181
182	/* code the match */
183	assert(ii == ip);
184	ip += 3;
185	if (m_pos[3] != ip++ \|\| m_pos[4] != ip++ \|\| m_pos[5] != *ip++ \|\|
186	m_pos[6] != ip++ \|\| m_pos[7] != ip++ \|\| m_pos[8] != *ip++
187	#ifdef LZO1Y
188	\|\| m_pos[ 9] != ip++ \|\| m_pos[10] != ip++ \|\| m_pos[11] != *ip++
189	\|\| m_pos[12] != ip++ \|\| m_pos[13] != ip++ \|\| m_pos[14] != *ip++
190	#endif
191	)
192	{
193	--ip;
194	m_len = pd(ip, ii);
195	assert(m_len >= 3); assert(m_len <= M2_MAX_LEN);
196
197	if (m_off <= M2_MAX_OFFSET)
198	{
199	m_off -= 1;
200	#if defined(LZO1X)
201	*op++ = LZO_BYTE(((m_len - 1) << 5) \| ((m_off & 7) << 2));
202	*op++ = LZO_BYTE(m_off >> 3);
203	#elif defined(LZO1Y)
204	*op++ = LZO_BYTE(((m_len + 1) << 4) \| ((m_off & 3) << 2));
205	*op++ = LZO_BYTE(m_off >> 2);
206	#endif
207	}
208	else if (m_off <= M3_MAX_OFFSET)
209	{
210	m_off -= 1;
211	*op++ = LZO_BYTE(M3_MARKER \| (m_len - 2));
212	goto m3_m4_offset;
213	}
214	else
215	#if defined(LZO1X)
216	{
217	m_off -= 0x4000;
218	assert(m_off > 0); assert(m_off <= 0x7fff);
219	*op++ = LZO_BYTE(M4_MARKER \|
220	((m_off & 0x4000) >> 11) \| (m_len - 2));
221	goto m3_m4_offset;
222	}
223	#elif defined(LZO1Y)
224	goto m4_match;
225	#endif
226	}
227	else
228	{
229	{
230	const lzo_bytep end = in_end;
231	const lzo_bytep m = m_pos + M2_MAX_LEN + 1;
232	while (ip < end && m == ip)
233	m++, ip++;
234	m_len = pd(ip, ii);
235	}
236	assert(m_len > M2_MAX_LEN);
237
238	if (m_off <= M3_MAX_OFFSET)
239	{
240	m_off -= 1;
241	if (m_len <= 33)
242	*op++ = LZO_BYTE(M3_MARKER \| (m_len - 2));
243	else
244	{
245	m_len -= 33;
246	*op++ = M3_MARKER \| 0;
247	goto m3_m4_len;
248	}
249	}
250	else
251	{
252	#if defined(LZO1Y)
253	m4_match:
254	#endif
255	m_off -= 0x4000;
256	assert(m_off > 0); assert(m_off <= 0x7fff);
257	if (m_len <= M4_MAX_LEN)
258	*op++ = LZO_BYTE(M4_MARKER \|
259	((m_off & 0x4000) >> 11) \| (m_len - 2));
260	else
261	{
262	m_len -= M4_MAX_LEN;
263	*op++ = LZO_BYTE(M4_MARKER \| ((m_off & 0x4000) >> 11));
264	m3_m4_len:
265	while (m_len > 255)
266	{
267	m_len -= 255;
268	*op++ = 0;
269	}
270	assert(m_len > 0);
271	*op++ = LZO_BYTE(m_len);
272	}
273	}
274
275	m3_m4_offset:
276	*op++ = LZO_BYTE((m_off & 63) << 2);
277	*op++ = LZO_BYTE(m_off >> 6);
278	}
279
280	#if 0
281	match_done:
282	#endif
283	ii = ip;
284	if __lzo_unlikely(ip >= ip_end)
285	break;
286	}
287
288	*out_len = pd(op, out);
289	return pd(in_end,ii);
290	}
291
292
293	/***********************************************************************
294	// public entry point
295	************************************************************************/
296
297	LZO_PUBLIC(int)
298	DO_COMPRESS ( const lzo_bytep in , lzo_uint in_len,
299	lzo_bytep out, lzo_uintp out_len,
300	lzo_voidp wrkmem )
301	{
302	lzo_bytep op = out;
303	lzo_uint t;
304
305	if __lzo_unlikely(in_len <= M2_MAX_LEN + 5)
306	t = in_len;
307	else
308	{
309	t = do_compress(in,in_len,op,out_len,wrkmem);
310	op += *out_len;
311	}
312
313	if (t > 0)
314	{
315	const lzo_bytep ii = in + in_len - t;
316
317	if (op == out && t <= 238)
318	*op++ = LZO_BYTE(17 + t);
319	else if (t <= 3)
320	op[-2] \|= LZO_BYTE(t);
321	else if (t <= 18)
322	*op++ = LZO_BYTE(t - 3);
323	else
324	{
325	lzo_uint tt = t - 18;
326
327	*op++ = 0;
328	while (tt > 255)
329	{
330	tt -= 255;
331	*op++ = 0;
332	}
333	assert(tt > 0);
334	*op++ = LZO_BYTE(tt);
335	}
336	do op++ = ii++; while (--t > 0);
337	}
338
339	*op++ = M4_MARKER \| 1;
340	*op++ = 0;
341	*op++ = 0;
342
343	*out_len = pd(op, out);
344	return LZO_E_OK;
345	}
346
347
348	/*
349	vi:ts=4:et
350	*/
351