Context Navigation

lzo1x_c.ch

Last change on this file was e16e8f2, checked in by Edwin Eefting <edwin@datux.nl>, 3 years ago
bootstuff
Property mode set to `100644`
File size: 11.7 KB

Line
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) 1996-2014 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
30	#if 1 && defined(DO_COMPRESS) && !defined(do_compress)
31	/* choose a unique name to better help PGO optimizations */
32	# define do_compress LZO_PP_ECONCAT2(DO_COMPRESS,_core)
33	#endif
34
35
36	/***********************************************************************
37	// compress a block of data.
38	************************************************************************/
39
40	static __lzo_noinline lzo_uint
41	do_compress ( const lzo_bytep in , lzo_uint in_len,
42	lzo_bytep out, lzo_uintp out_len,
43	lzo_uint ti, lzo_voidp wrkmem)
44	{
45	const lzo_bytep ip;
46	lzo_bytep op;
47	const lzo_bytep const in_end = in + in_len;
48	const lzo_bytep const ip_end = in + in_len - 20;
49	const lzo_bytep ii;
50	lzo_dict_p const dict = (lzo_dict_p) wrkmem;
51
52	op = out;
53	ip = in;
54	ii = ip;
55
56	ip += ti < 4 ? 4 - ti : 0;
57	for (;;)
58	{
59	const lzo_bytep m_pos;
60	#if !(LZO_DETERMINISTIC)
61	LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
62	lzo_uint m_len;
63	lzo_uint dindex;
64	next:
65	if __lzo_unlikely(ip >= ip_end)
66	break;
67	DINDEX1(dindex,ip);
68	GINDEX(m_pos,m_off,dict,dindex,in);
69	if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
70	goto literal;
71	#if 1
72	if (m_off <= M2_MAX_OFFSET \|\| m_pos[3] == ip[3])
73	goto try_match;
74	DINDEX2(dindex,ip);
75	#endif
76	GINDEX(m_pos,m_off,dict,dindex,in);
77	if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
78	goto literal;
79	if (m_off <= M2_MAX_OFFSET \|\| m_pos[3] == ip[3])
80	goto try_match;
81	goto literal;
82
83	try_match:
84	#if (LZO_OPT_UNALIGNED32)
85	if (UA_GET_NE32(m_pos) != UA_GET_NE32(ip))
86	#else
87	if (m_pos[0] != ip[0] \|\| m_pos[1] != ip[1] \|\| m_pos[2] != ip[2] \|\| m_pos[3] != ip[3])
88	#endif
89	{
90	/* a literal */
91	literal:
92	UPDATE_I(dict,0,dindex,ip,in);
93	ip += 1 + ((ip - ii) >> 5);
94	continue;
95	}
96	/match:/
97	UPDATE_I(dict,0,dindex,ip,in);
98	#else
99	lzo_uint m_off;
100	lzo_uint m_len;
101	{
102	lzo_uint32_t dv;
103	lzo_uint dindex;
104	literal:
105	ip += 1 + ((ip - ii) >> 5);
106	next:
107	if __lzo_unlikely(ip >= ip_end)
108	break;
109	dv = UA_GET_LE32(ip);
110	dindex = DINDEX(dv,ip);
111	GINDEX(m_off,m_pos,in+dict,dindex,in);
112	UPDATE_I(dict,0,dindex,ip,in);
113	if __lzo_unlikely(dv != UA_GET_LE32(m_pos))
114	goto literal;
115	}
116	#endif
117
118	/* a match */
119
120	ii -= ti; ti = 0;
121	{
122	lzo_uint t = pd(ip,ii);
123	if (t != 0)
124	{
125	if (t <= 3)
126	{
127	op[-2] = LZO_BYTE(op[-2] \| t);
128	#if (LZO_OPT_UNALIGNED32)
129	UA_COPY4(op, ii);
130	op += t;
131	#else
132	{ do op++ = ii++; while (--t > 0); }
133	#endif
134	}
135	#if (LZO_OPT_UNALIGNED32) \|\| (LZO_OPT_UNALIGNED64)
136	else if (t <= 16)
137	{
138	*op++ = LZO_BYTE(t - 3);
139	UA_COPY8(op, ii);
140	UA_COPY8(op+8, ii+8);
141	op += t;
142	}
143	#endif
144	else
145	{
146	if (t <= 18)
147	*op++ = LZO_BYTE(t - 3);
148	else
149	{
150	lzo_uint tt = t - 18;
151	*op++ = 0;
152	while __lzo_unlikely(tt > 255)
153	{
154	tt -= 255;
155	UA_SET1(op, 0);
156	op++;
157	}
158	assert(tt > 0);
159	*op++ = LZO_BYTE(tt);
160	}
161	#if (LZO_OPT_UNALIGNED32) \|\| (LZO_OPT_UNALIGNED64)
162	do {
163	UA_COPY8(op, ii);
164	UA_COPY8(op+8, ii+8);
165	op += 16; ii += 16; t -= 16;
166	} while (t >= 16); if (t > 0)
167	#endif
168	{ do op++ = ii++; while (--t > 0); }
169	}
170	}
171	}
172	m_len = 4;
173	{
174	#if (LZO_OPT_UNALIGNED64)
175	lzo_uint64_t v;
176	v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len);
177	if __lzo_unlikely(v == 0) {
178	do {
179	m_len += 8;
180	v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len);
181	if __lzo_unlikely(ip + m_len >= ip_end)
182	goto m_len_done;
183	} while (v == 0);
184	}
185	#if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz64)
186	m_len += lzo_bitops_ctlz64(v) / CHAR_BIT;
187	#elif (LZO_ABI_BIG_ENDIAN)
188	if ((v >> (64 - CHAR_BIT)) == 0) do {
189	v <<= CHAR_BIT;
190	m_len += 1;
191	} while ((v >> (64 - CHAR_BIT)) == 0);
192	#elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz64)
193	m_len += lzo_bitops_cttz64(v) / CHAR_BIT;
194	#elif (LZO_ABI_LITTLE_ENDIAN)
195	if ((v & UCHAR_MAX) == 0) do {
196	v >>= CHAR_BIT;
197	m_len += 1;
198	} while ((v & UCHAR_MAX) == 0);
199	#else
200	if (ip[m_len] == m_pos[m_len]) do {
201	m_len += 1;
202	} while (ip[m_len] == m_pos[m_len]);
203	#endif
204	#elif (LZO_OPT_UNALIGNED32)
205	lzo_uint32_t v;
206	v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);
207	if __lzo_unlikely(v == 0) {
208	do {
209	m_len += 4;
210	v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);
211	if (v != 0)
212	break;
213	m_len += 4;
214	v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);
215	if __lzo_unlikely(ip + m_len >= ip_end)
216	goto m_len_done;
217	} while (v == 0);
218	}
219	#if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz32)
220	m_len += lzo_bitops_ctlz32(v) / CHAR_BIT;
221	#elif (LZO_ABI_BIG_ENDIAN)
222	if ((v >> (32 - CHAR_BIT)) == 0) do {
223	v <<= CHAR_BIT;
224	m_len += 1;
225	} while ((v >> (32 - CHAR_BIT)) == 0);
226	#elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz32)
227	m_len += lzo_bitops_cttz32(v) / CHAR_BIT;
228	#elif (LZO_ABI_LITTLE_ENDIAN)
229	if ((v & UCHAR_MAX) == 0) do {
230	v >>= CHAR_BIT;
231	m_len += 1;
232	} while ((v & UCHAR_MAX) == 0);
233	#else
234	if (ip[m_len] == m_pos[m_len]) do {
235	m_len += 1;
236	} while (ip[m_len] == m_pos[m_len]);
237	#endif
238	#else
239	if __lzo_unlikely(ip[m_len] == m_pos[m_len]) {
240	do {
241	m_len += 1;
242	if (ip[m_len] != m_pos[m_len])
243	break;
244	m_len += 1;
245	if (ip[m_len] != m_pos[m_len])
246	break;
247	m_len += 1;
248	if (ip[m_len] != m_pos[m_len])
249	break;
250	m_len += 1;
251	if (ip[m_len] != m_pos[m_len])
252	break;
253	m_len += 1;
254	if (ip[m_len] != m_pos[m_len])
255	break;
256	m_len += 1;
257	if (ip[m_len] != m_pos[m_len])
258	break;
259	m_len += 1;
260	if (ip[m_len] != m_pos[m_len])
261	break;
262	m_len += 1;
263	if __lzo_unlikely(ip + m_len >= ip_end)
264	goto m_len_done;
265	} while (ip[m_len] == m_pos[m_len]);
266	}
267	#endif
268	}
269	m_len_done:
270	m_off = pd(ip,m_pos);
271	ip += m_len;
272	ii = ip;
273	if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
274	{
275	m_off -= 1;
276	#if defined(LZO1X)
277	*op++ = LZO_BYTE(((m_len - 1) << 5) \| ((m_off & 7) << 2));
278	*op++ = LZO_BYTE(m_off >> 3);
279	#elif defined(LZO1Y)
280	*op++ = LZO_BYTE(((m_len + 1) << 4) \| ((m_off & 3) << 2));
281	*op++ = LZO_BYTE(m_off >> 2);
282	#endif
283	}
284	else if (m_off <= M3_MAX_OFFSET)
285	{
286	m_off -= 1;
287	if (m_len <= M3_MAX_LEN)
288	*op++ = LZO_BYTE(M3_MARKER \| (m_len - 2));
289	else
290	{
291	m_len -= M3_MAX_LEN;
292	*op++ = M3_MARKER \| 0;
293	while __lzo_unlikely(m_len > 255)
294	{
295	m_len -= 255;
296	UA_SET1(op, 0);
297	op++;
298	}
299	*op++ = LZO_BYTE(m_len);
300	}
301	*op++ = LZO_BYTE(m_off << 2);
302	*op++ = LZO_BYTE(m_off >> 6);
303	}
304	else
305	{
306	m_off -= 0x4000;
307	if (m_len <= M4_MAX_LEN)
308	*op++ = LZO_BYTE(M4_MARKER \| ((m_off >> 11) & 8) \| (m_len - 2));
309	else
310	{
311	m_len -= M4_MAX_LEN;
312	*op++ = LZO_BYTE(M4_MARKER \| ((m_off >> 11) & 8));
313	while __lzo_unlikely(m_len > 255)
314	{
315	m_len -= 255;
316	UA_SET1(op, 0);
317	op++;
318	}
319	*op++ = LZO_BYTE(m_len);
320	}
321	*op++ = LZO_BYTE(m_off << 2);
322	*op++ = LZO_BYTE(m_off >> 6);
323	}
324	goto next;
325	}
326
327	*out_len = pd(op, out);
328	return pd(in_end,ii-ti);
329	}
330
331
332	/***********************************************************************
333	// public entry point
334	************************************************************************/
335
336	LZO_PUBLIC(int)
337	DO_COMPRESS ( const lzo_bytep in , lzo_uint in_len,
338	lzo_bytep out, lzo_uintp out_len,
339	lzo_voidp wrkmem )
340	{
341	const lzo_bytep ip = in;
342	lzo_bytep op = out;
343	lzo_uint l = in_len;
344	lzo_uint t = 0;
345
346	while (l > 20)
347	{
348	lzo_uint ll = l;
349	lzo_uintptr_t ll_end;
350	#if 0 \|\| (LZO_DETERMINISTIC)
351	ll = LZO_MIN(ll, 49152);
352	#endif
353	ll_end = (lzo_uintptr_t)ip + ll;
354	if ((ll_end + ((t + ll) >> 5)) <= ll_end \|\| (const lzo_bytep)(ll_end + ((t + ll) >> 5)) <= ip + ll)
355	break;
356	#if (LZO_DETERMINISTIC)
357	lzo_memset(wrkmem, 0, ((lzo_uint)1 << D_BITS) * sizeof(lzo_dict_t));
358	#endif
359	t = do_compress(ip,ll,op,out_len,t,wrkmem);
360	ip += ll;
361	op += *out_len;
362	l -= ll;
363	}
364	t += l;
365
366	if (t > 0)
367	{
368	const lzo_bytep ii = in + in_len - t;
369
370	if (op == out && t <= 238)
371	*op++ = LZO_BYTE(17 + t);
372	else if (t <= 3)
373	op[-2] = LZO_BYTE(op[-2] \| t);
374	else if (t <= 18)
375	*op++ = LZO_BYTE(t - 3);
376	else
377	{
378	lzo_uint tt = t - 18;
379
380	*op++ = 0;
381	while (tt > 255)
382	{
383	tt -= 255;
384	UA_SET1(op, 0);
385	op++;
386	}
387	assert(tt > 0);
388	*op++ = LZO_BYTE(tt);
389	}
390	UA_COPYN(op, ii, t);
391	op += t;
392	}
393
394	*op++ = M4_MARKER \| 1;
395	*op++ = 0;
396	*op++ = 0;
397
398	*out_len = pd(op, out);
399	return LZO_E_OK;
400	}
401
402
403	/*
404	vi:ts=4:et
405	*/

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format