Context Navigation

lzo1x_d.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: 12.4 KB

Line
1	/* lzo1x_d.ch -- implementation of the LZO1X decompression 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	#include "lzo1_d.ch"
30
31
32	/***********************************************************************
33	// decompress a block of data.
34	************************************************************************/
35
36	#if defined(DO_DECOMPRESS)
37	LZO_PUBLIC(int)
38	DO_DECOMPRESS ( const lzo_bytep in , lzo_uint in_len,
39	lzo_bytep out, lzo_uintp out_len,
40	lzo_voidp wrkmem )
41	#endif
42	{
43	lzo_bytep op;
44	const lzo_bytep ip;
45	lzo_uint t;
46	#if defined(COPY_DICT)
47	lzo_uint m_off;
48	const lzo_bytep dict_end;
49	#else
50	const lzo_bytep m_pos;
51	#endif
52
53	const lzo_bytep const ip_end = in + in_len;
54	#if defined(HAVE_ANY_OP)
55	lzo_bytep const op_end = out + *out_len;
56	#endif
57	#if defined(LZO1Z)
58	lzo_uint last_m_off = 0;
59	#endif
60
61	LZO_UNUSED(wrkmem);
62
63	#if defined(COPY_DICT)
64	if (dict)
65	{
66	if (dict_len > M4_MAX_OFFSET)
67	{
68	dict += dict_len - M4_MAX_OFFSET;
69	dict_len = M4_MAX_OFFSET;
70	}
71	dict_end = dict + dict_len;
72	}
73	else
74	{
75	dict_len = 0;
76	dict_end = NULL;
77	}
78	#endif /* COPY_DICT */
79
80	*out_len = 0;
81
82	op = out;
83	ip = in;
84
85	NEED_IP(1);
86	if (*ip > 17)
87	{
88	t = *ip++ - 17;
89	if (t < 4)
90	goto match_next;
91	assert(t > 0); NEED_OP(t); NEED_IP(t+3);
92	do op++ = ip++; while (--t > 0);
93	goto first_literal_run;
94	}
95
96	for (;;)
97	{
98	NEED_IP(3);
99	t = *ip++;
100	if (t >= 16)
101	goto match;
102	/* a literal run */
103	if (t == 0)
104	{
105	while (*ip == 0)
106	{
107	t += 255;
108	ip++;
109	TEST_IV(t);
110	NEED_IP(1);
111	}
112	t += 15 + *ip++;
113	}
114	/* copy literals */
115	assert(t > 0); NEED_OP(t+3); NEED_IP(t+6);
116	#if (LZO_OPT_UNALIGNED64) && (LZO_OPT_UNALIGNED32)
117	t += 3;
118	if (t >= 8) do
119	{
120	UA_COPY8(op,ip);
121	op += 8; ip += 8; t -= 8;
122	} while (t >= 8);
123	if (t >= 4)
124	{
125	UA_COPY4(op,ip);
126	op += 4; ip += 4; t -= 4;
127	}
128	if (t > 0)
129	{
130	op++ = ip++;
131	if (t > 1) { op++ = ip++; if (t > 2) { op++ = ip++; } }
132	}
133	#elif (LZO_OPT_UNALIGNED32) \|\| (LZO_ALIGNED_OK_4)
134	#if !(LZO_OPT_UNALIGNED32)
135	if (PTR_ALIGNED2_4(op,ip))
136	{
137	#endif
138	UA_COPY4(op,ip);
139	op += 4; ip += 4;
140	if (--t > 0)
141	{
142	if (t >= 4)
143	{
144	do {
145	UA_COPY4(op,ip);
146	op += 4; ip += 4; t -= 4;
147	} while (t >= 4);
148	if (t > 0) do op++ = ip++; while (--t > 0);
149	}
150	else
151	do op++ = ip++; while (--t > 0);
152	}
153	#if !(LZO_OPT_UNALIGNED32)
154	}
155	else
156	#endif
157	#endif
158	#if !(LZO_OPT_UNALIGNED32)
159	{
160	op++ = ip++; op++ = ip++; op++ = ip++;
161	do op++ = ip++; while (--t > 0);
162	}
163	#endif
164
165
166	first_literal_run:
167
168
169	t = *ip++;
170	if (t >= 16)
171	goto match;
172	#if defined(COPY_DICT)
173	#if defined(LZO1Z)
174	m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
175	last_m_off = m_off;
176	#else
177	m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
178	#endif
179	NEED_OP(3);
180	t = 3; COPY_DICT(t,m_off)
181	#else /* !COPY_DICT */
182	#if defined(LZO1Z)
183	t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
184	m_pos = op - t;
185	last_m_off = t;
186	#else
187	m_pos = op - (1 + M2_MAX_OFFSET);
188	m_pos -= t >> 2;
189	m_pos -= *ip++ << 2;
190	#endif
191	TEST_LB(m_pos); NEED_OP(3);
192	op++ = m_pos++; op++ = m_pos++; op++ = m_pos;
193	#endif /* COPY_DICT */
194	goto match_done;
195
196
197	/* handle matches */
198	for (;;) {
199	match:
200	if (t >= 64) /* a M2 match */
201	{
202	#if defined(COPY_DICT)
203	#if defined(LZO1X)
204	m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
205	t = (t >> 5) - 1;
206	#elif defined(LZO1Y)
207	m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
208	t = (t >> 4) - 3;
209	#elif defined(LZO1Z)
210	m_off = t & 0x1f;
211	if (m_off >= 0x1c)
212	m_off = last_m_off;
213	else
214	{
215	m_off = 1 + (m_off << 6) + (*ip++ >> 2);
216	last_m_off = m_off;
217	}
218	t = (t >> 5) - 1;
219	#endif
220	#else /* !COPY_DICT */
221	#if defined(LZO1X)
222	m_pos = op - 1;
223	m_pos -= (t >> 2) & 7;
224	m_pos -= *ip++ << 3;
225	t = (t >> 5) - 1;
226	#elif defined(LZO1Y)
227	m_pos = op - 1;
228	m_pos -= (t >> 2) & 3;
229	m_pos -= *ip++ << 2;
230	t = (t >> 4) - 3;
231	#elif defined(LZO1Z)
232	{
233	lzo_uint off = t & 0x1f;
234	m_pos = op;
235	if (off >= 0x1c)
236	{
237	assert(last_m_off > 0);
238	m_pos -= last_m_off;
239	}
240	else
241	{
242	off = 1 + (off << 6) + (*ip++ >> 2);
243	m_pos -= off;
244	last_m_off = off;
245	}
246	}
247	t = (t >> 5) - 1;
248	#endif
249	TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
250	goto copy_match;
251	#endif /* COPY_DICT */
252	}
253	else if (t >= 32) /* a M3 match */
254	{
255	t &= 31;
256	if (t == 0)
257	{
258	while (*ip == 0)
259	{
260	t += 255;
261	ip++;
262	TEST_OV(t);
263	NEED_IP(1);
264	}
265	t += 31 + *ip++;
266	NEED_IP(2);
267	}
268	#if defined(COPY_DICT)
269	#if defined(LZO1Z)
270	m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
271	last_m_off = m_off;
272	#else
273	m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
274	#endif
275	#else /* !COPY_DICT */
276	#if defined(LZO1Z)
277	{
278	lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2);
279	m_pos = op - off;
280	last_m_off = off;
281	}
282	#elif (LZO_OPT_UNALIGNED16) && (LZO_ABI_LITTLE_ENDIAN)
283	m_pos = op - 1;
284	m_pos -= UA_GET_LE16(ip) >> 2;
285	#else
286	m_pos = op - 1;
287	m_pos -= (ip[0] >> 2) + (ip[1] << 6);
288	#endif
289	#endif /* COPY_DICT */
290	ip += 2;
291	}
292	else if (t >= 16) /* a M4 match */
293	{
294	#if defined(COPY_DICT)
295	m_off = (t & 8) << 11;
296	#else /* !COPY_DICT */
297	m_pos = op;
298	m_pos -= (t & 8) << 11;
299	#endif /* COPY_DICT */
300	t &= 7;
301	if (t == 0)
302	{
303	while (*ip == 0)
304	{
305	t += 255;
306	ip++;
307	TEST_OV(t);
308	NEED_IP(1);
309	}
310	t += 7 + *ip++;
311	NEED_IP(2);
312	}
313	#if defined(COPY_DICT)
314	#if defined(LZO1Z)
315	m_off += (ip[0] << 6) + (ip[1] >> 2);
316	#else
317	m_off += (ip[0] >> 2) + (ip[1] << 6);
318	#endif
319	ip += 2;
320	if (m_off == 0)
321	goto eof_found;
322	m_off += 0x4000;
323	#if defined(LZO1Z)
324	last_m_off = m_off;
325	#endif
326	#else /* !COPY_DICT */
327	#if defined(LZO1Z)
328	m_pos -= (ip[0] << 6) + (ip[1] >> 2);
329	#elif (LZO_OPT_UNALIGNED16) && (LZO_ABI_LITTLE_ENDIAN)
330	m_pos -= UA_GET_LE16(ip) >> 2;
331	#else
332	m_pos -= (ip[0] >> 2) + (ip[1] << 6);
333	#endif
334	ip += 2;
335	if (m_pos == op)
336	goto eof_found;
337	m_pos -= 0x4000;
338	#if defined(LZO1Z)
339	last_m_off = pd((const lzo_bytep)op, m_pos);
340	#endif
341	#endif /* COPY_DICT */
342	}
343	else /* a M1 match */
344	{
345	#if defined(COPY_DICT)
346	#if defined(LZO1Z)
347	m_off = 1 + (t << 6) + (*ip++ >> 2);
348	last_m_off = m_off;
349	#else
350	m_off = 1 + (t >> 2) + (*ip++ << 2);
351	#endif
352	NEED_OP(2);
353	t = 2; COPY_DICT(t,m_off)
354	#else /* !COPY_DICT */
355	#if defined(LZO1Z)
356	t = 1 + (t << 6) + (*ip++ >> 2);
357	m_pos = op - t;
358	last_m_off = t;
359	#else
360	m_pos = op - 1;
361	m_pos -= t >> 2;
362	m_pos -= *ip++ << 2;
363	#endif
364	TEST_LB(m_pos); NEED_OP(2);
365	op++ = m_pos++; op++ = m_pos;
366	#endif /* COPY_DICT */
367	goto match_done;
368	}
369
370	/* copy match */
371	#if defined(COPY_DICT)
372
373	NEED_OP(t+3-1);
374	t += 3-1; COPY_DICT(t,m_off)
375
376	#else /* !COPY_DICT */
377
378	TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
379	#if (LZO_OPT_UNALIGNED64) && (LZO_OPT_UNALIGNED32)
380	if (op - m_pos >= 8)
381	{
382	t += (3 - 1);
383	if (t >= 8) do
384	{
385	UA_COPY8(op,m_pos);
386	op += 8; m_pos += 8; t -= 8;
387	} while (t >= 8);
388	if (t >= 4)
389	{
390	UA_COPY4(op,m_pos);
391	op += 4; m_pos += 4; t -= 4;
392	}
393	if (t > 0)
394	{
395	*op++ = m_pos[0];
396	if (t > 1) { op++ = m_pos[1]; if (t > 2) { op++ = m_pos[2]; } }
397	}
398	}
399	else
400	#elif (LZO_OPT_UNALIGNED32) \|\| (LZO_ALIGNED_OK_4)
401	#if !(LZO_OPT_UNALIGNED32)
402	if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos))
403	{
404	assert((op - m_pos) >= 4); /* both pointers are aligned */
405	#else
406	if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
407	{
408	#endif
409	UA_COPY4(op,m_pos);
410	op += 4; m_pos += 4; t -= 4 - (3 - 1);
411	do {
412	UA_COPY4(op,m_pos);
413	op += 4; m_pos += 4; t -= 4;
414	} while (t >= 4);
415	if (t > 0) do op++ = m_pos++; while (--t > 0);
416	}
417	else
418	#endif
419	{
420	copy_match:
421	op++ = m_pos++; op++ = m_pos++;
422	do op++ = m_pos++; while (--t > 0);
423	}
424
425	#endif /* COPY_DICT */
426
427	match_done:
428	#if defined(LZO1Z)
429	t = ip[-1] & 3;
430	#else
431	t = ip[-2] & 3;
432	#endif
433	if (t == 0)
434	break;
435
436	/* copy literals */
437	match_next:
438	assert(t > 0); assert(t < 4); NEED_OP(t); NEED_IP(t+3);
439	#if 0
440	do op++ = ip++; while (--t > 0);
441	#else
442	op++ = ip++;
443	if (t > 1) { op++ = ip++; if (t > 2) { op++ = ip++; } }
444	#endif
445	t = *ip++;
446	}
447	}
448
449	eof_found:
450	*out_len = pd(op, out);
451	return (ip == ip_end ? LZO_E_OK :
452	(ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
453
454
455	#if defined(HAVE_NEED_IP)
456	input_overrun:
457	*out_len = pd(op, out);
458	return LZO_E_INPUT_OVERRUN;
459	#endif
460
461	#if defined(HAVE_NEED_OP)
462	output_overrun:
463	*out_len = pd(op, out);
464	return LZO_E_OUTPUT_OVERRUN;
465	#endif
466
467	#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
468	lookbehind_overrun:
469	*out_len = pd(op, out);
470	return LZO_E_LOOKBEHIND_OVERRUN;
471	#endif
472	}
473
474
475	/*
476	vi:ts=4:et
477	*/
478

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

Download in other formats:

Original Format