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

Rev	Line
[e16e8f2]	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