[people/ms/u-boot.git] / fs / jffs2 / compr_lzo.c

/*
 * JFFS2 -- Journalling Flash File System, Version 2.
 *
 * Copyright (C) 2004 Patrik Kluba,
 *		      University of Szeged, Hungary
 *
 * For licensing information, see the file 'LICENCE' in the
 * jffs2 directory.
 *
 * $Id: compr_lzo.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
 *
 */

/*
   LZO1X-1 (and -999) compression module for jffs2
   based on the original LZO sources
*/

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */

/*
   Original copyright notice follows:

   lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
   lzo_ptr.h -- low-level pointer constructs
   lzo_swd.ch -- sliding window dictionary
   lzoconf.h -- configuration for the LZO real-time data compression library
   lzo_mchw.ch -- matching functions using a window
   minilzo.c -- mini subset of the LZO real-time data compression library
   config1x.h -- configuration for the LZO1X algorithm
   lzo1x.h -- public interface of the LZO1X compression algorithm

   These files are part of the LZO real-time data compression library.

   Copyright (C) 1996-2002 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.,
   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

   Markus F.X.J. Oberhumer
   <markus@oberhumer.com>
*/

/*

	2004-02-16  pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
				Initial release
					-removed all 16 bit code
					-all sensitive data will be on 4 byte boundary
					-removed check parts for library use
					-removed all but LZO1X-* compression

*/


#include <config.h>
#include <linux/stddef.h>
#include <jffs2/jffs2.h>
#include <jffs2/compr_rubin.h>

/* Integral types that have *exactly* the same number of bits as a lzo_voidp */
typedef unsigned long lzo_ptr_t;
typedef long lzo_sptr_t;

/* data type definitions */
#define U32 unsigned long
#define S32 signed long
#define I32 long
#define U16 unsigned short
#define S16 signed short
#define I16 short
#define U8 unsigned char
#define S8 signed char
#define I8 char

#define M1_MAX_OFFSET	0x0400
#define M2_MAX_OFFSET	0x0800
#define M3_MAX_OFFSET	0x4000
#define M4_MAX_OFFSET	0xbfff

#define __COPY4(dst,src)  * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
#define COPY4(dst,src)	__COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src))

#define TEST_IP		(ip < ip_end)
#define TEST_OP		(op <= op_end)

#define NEED_IP(x) \
	    if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x))  goto input_overrun
#define NEED_OP(x) \
	    if ((lzo_uint)(op_end - op) < (lzo_uint)(x))  goto output_overrun
#define TEST_LOOKBEHIND(m_pos,out)    if (m_pos < out) goto lookbehind_overrun

typedef U32 lzo_uint32;
typedef I32 lzo_int32;
typedef U32 lzo_uint;
typedef I32 lzo_int;
typedef int lzo_bool;

#define lzo_byte		U8
#define lzo_bytep		U8 *
#define lzo_charp		char *
#define lzo_voidp		void *
#define lzo_shortp		short *
#define lzo_ushortp		unsigned short *
#define lzo_uint32p		lzo_uint32 *
#define lzo_int32p		lzo_int32 *
#define lzo_uintp		lzo_uint *
#define lzo_intp		lzo_int *
#define lzo_voidpp		lzo_voidp *
#define lzo_bytepp		lzo_bytep *
#define lzo_sizeof_dict_t		sizeof(lzo_bytep)

#define LZO_E_OK		    0
#define LZO_E_ERROR		    (-1)
#define LZO_E_OUT_OF_MEMORY	    (-2)	/* not used right now */
#define LZO_E_NOT_COMPRESSIBLE	    (-3)	/* not used right now */
#define LZO_E_INPUT_OVERRUN	    (-4)
#define LZO_E_OUTPUT_OVERRUN	    (-5)
#define LZO_E_LOOKBEHIND_OVERRUN    (-6)
#define LZO_E_EOF_NOT_FOUND	    (-7)
#define LZO_E_INPUT_NOT_CONSUMED    (-8)

#define PTR(a)				((lzo_ptr_t) (a))
#define PTR_LINEAR(a)		PTR(a)
#define PTR_ALIGNED_4(a)	((PTR_LINEAR(a) & 3) == 0)
#define PTR_ALIGNED_8(a)	((PTR_LINEAR(a) & 7) == 0)
#define PTR_ALIGNED2_4(a,b)	(((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0)
#define PTR_ALIGNED2_8(a,b)	(((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0)
#define PTR_LT(a,b)			(PTR(a) < PTR(b))
#define PTR_GE(a,b)			(PTR(a) >= PTR(b))
#define PTR_DIFF(a,b)		((lzo_ptrdiff_t) (PTR(a) - PTR(b)))
#define pd(a,b)			((lzo_uint) ((a)-(b)))

typedef ptrdiff_t lzo_ptrdiff_t;

static int
lzo1x_decompress (const lzo_byte * in, lzo_uint in_len,
		  lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
{
	register lzo_byte *op;
	register const lzo_byte *ip;
	register lzo_uint t;

	register const lzo_byte *m_pos;

	const lzo_byte *const ip_end = in + in_len;
	lzo_byte *const op_end = out + *out_len;

	*out_len = 0;

	op = out;
	ip = in;

	if (*ip > 17)
	{
		t = *ip++ - 17;
		if (t < 4)
			goto match_next;
		NEED_OP (t);
		NEED_IP (t + 1);
		do
			*op++ = *ip++;
		while (--t > 0);
		goto first_literal_run;
	}

	while (TEST_IP && TEST_OP)
	{
		t = *ip++;
		if (t >= 16)
			goto match;
		if (t == 0)
		{
			NEED_IP (1);
			while (*ip == 0)
			{
				t += 255;
				ip++;
				NEED_IP (1);
			}
			t += 15 + *ip++;
		}
		NEED_OP (t + 3);
		NEED_IP (t + 4);
		if (PTR_ALIGNED2_4 (op, ip))
		{
			COPY4 (op, ip);

			op += 4;
			ip += 4;
			if (--t > 0)
			{
				if (t >= 4)
				{
					do
					{
						COPY4 (op, ip);
						op += 4;
						ip += 4;
						t -= 4;
					}
					while (t >= 4);
					if (t > 0)
						do
							*op++ = *ip++;
						while (--t > 0);
				}
				else
					do
						*op++ = *ip++;
					while (--t > 0);
			}
		}
		else
		{
			*op++ = *ip++;
			*op++ = *ip++;
			*op++ = *ip++;
			do
				*op++ = *ip++;
			while (--t > 0);
		}
	      first_literal_run:

		t = *ip++;
		if (t >= 16)
			goto match;

		m_pos = op - (1 + M2_MAX_OFFSET);
		m_pos -= t >> 2;
		m_pos -= *ip++ << 2;
		TEST_LOOKBEHIND (m_pos, out);
		NEED_OP (3);
		*op++ = *m_pos++;
		*op++ = *m_pos++;
		*op++ = *m_pos;

		goto match_done;

		while (TEST_IP && TEST_OP)
		{
		      match:
			if (t >= 64)
			{
				m_pos = op - 1;
				m_pos -= (t >> 2) & 7;
				m_pos -= *ip++ << 3;
				t = (t >> 5) - 1;
				TEST_LOOKBEHIND (m_pos, out);
				NEED_OP (t + 3 - 1);
				goto copy_match;

			}
			else if (t >= 32)
			{
				t &= 31;
				if (t == 0)
				{
					NEED_IP (1);
					while (*ip == 0)
					{
						t += 255;
						ip++;
						NEED_IP (1);
					}
					t += 31 + *ip++;
				}

				m_pos = op - 1;
				m_pos -= (ip[0] >> 2) + (ip[1] << 6);

				ip += 2;
			}
			else if (t >= 16)
			{
				m_pos = op;
				m_pos -= (t & 8) << 11;

				t &= 7;
				if (t == 0)
				{
					NEED_IP (1);
					while (*ip == 0)
					{
						t += 255;
						ip++;
						NEED_IP (1);
					}
					t += 7 + *ip++;
				}

				m_pos -= (ip[0] >> 2) + (ip[1] << 6);

				ip += 2;
				if (m_pos == op)
					goto eof_found;
				m_pos -= 0x4000;
			}
			else
			{

				m_pos = op - 1;
				m_pos -= t >> 2;
				m_pos -= *ip++ << 2;
				TEST_LOOKBEHIND (m_pos, out);
				NEED_OP (2);
				*op++ = *m_pos++;
				*op++ = *m_pos;

				goto match_done;
			}

			TEST_LOOKBEHIND (m_pos, out);
			NEED_OP (t + 3 - 1);
			if (t >= 2 * 4 - (3 - 1)
			    && PTR_ALIGNED2_4 (op, m_pos))
			{
				COPY4 (op, m_pos);
				op += 4;
				m_pos += 4;
				t -= 4 - (3 - 1);
				do
				{
					COPY4 (op, m_pos);
					op += 4;
					m_pos += 4;
					t -= 4;
				}
				while (t >= 4);
				if (t > 0)
					do
						*op++ = *m_pos++;
					while (--t > 0);
			}
			else

			{
			      copy_match:
				*op++ = *m_pos++;
				*op++ = *m_pos++;
				do
					*op++ = *m_pos++;
				while (--t > 0);
			}

		      match_done:
			t = ip[-2] & 3;

			if (t == 0)
				break;

		      match_next:
			NEED_OP (t);
			NEED_IP (t + 1);
			do
				*op++ = *ip++;
			while (--t > 0);
			t = *ip++;
		}
	}
	*out_len = op - out;
	return LZO_E_EOF_NOT_FOUND;

      eof_found:
	*out_len = op - out;
	return (ip == ip_end ? LZO_E_OK :
		(ip <
		 ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));

      input_overrun:
	*out_len = op - out;
	return LZO_E_INPUT_OVERRUN;

      output_overrun:
	*out_len = op - out;
	return LZO_E_OUTPUT_OVERRUN;

      lookbehind_overrun:
	*out_len = op - out;
	return LZO_E_LOOKBEHIND_OVERRUN;
}

int lzo_decompress(unsigned char *data_in, unsigned char *cpage_out,
		      u32 srclen, u32 destlen)
{
	lzo_uint outlen = destlen;
	return lzo1x_decompress (data_in, srclen, cpage_out, &outlen, NULL);
}
Commit	Line	Data
07cc0999 WD	1	/*
	2	* JFFS2 -- Journalling Flash File System, Version 2.
	3	*
	4	* Copyright (C) 2004 Patrik Kluba,
	5	* University of Szeged, Hungary
	6	*
	7	* For licensing information, see the file 'LICENCE' in the
	8	* jffs2 directory.
	9	*
	10	* $Id: compr_lzo.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
	11	*
	12	*/
	13
	14	/*
	15	LZO1X-1 (and -999) compression module for jffs2
	16	based on the original LZO sources
	17	*/
	18
	19	/* -- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -- */
	20
	21	/*
	22	Original copyright notice follows:
	23
	24	lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
	25	lzo_ptr.h -- low-level pointer constructs
	26	lzo_swd.ch -- sliding window dictionary
	27	lzoconf.h -- configuration for the LZO real-time data compression library
	28	lzo_mchw.ch -- matching functions using a window
	29	minilzo.c -- mini subset of the LZO real-time data compression library
	30	config1x.h -- configuration for the LZO1X algorithm
	31	lzo1x.h -- public interface of the LZO1X compression algorithm
	32
	33	These files are part of the LZO real-time data compression library.
	34
	35	Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer
	36	All Rights Reserved.
	37
	38	The LZO library is free software; you can redistribute it and/or
	39	modify it under the terms of the GNU General Public License as
	40	published by the Free Software Foundation; either version 2 of
	41	the License, or (at your option) any later version.
	42
	43	The LZO library is distributed in the hope that it will be useful,
	44	but WITHOUT ANY WARRANTY; without even the implied warranty of
	45	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	46	GNU General Public License for more details.
	47
	48	You should have received a copy of the GNU General Public License
	49	along with the LZO library; see the file COPYING.
	50	If not, write to the Free Software Foundation, Inc.,
	51	59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
	52
	53	Markus F.X.J. Oberhumer
	54	<markus@oberhumer.com>
	55	*/
	56
	57	/*
	58
	59	2004-02-16 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
	60	Initial release
	61	-removed all 16 bit code
	62	-all sensitive data will be on 4 byte boundary
	63	-removed check parts for library use
	64	-removed all but LZO1X-* compression
65
66	*/
67
68
69	#include <config.h>
07cc0999 WD	70	#include <linux/stddef.h>
	71	#include <jffs2/jffs2.h>
	72	#include <jffs2/compr_rubin.h>
	73
	74	/* Integral types that have exactly the same number of bits as a lzo_voidp */
	75	typedef unsigned long lzo_ptr_t;
	76	typedef long lzo_sptr_t;
	77
	78	/* data type definitions */
	79	#define U32 unsigned long
	80	#define S32 signed long
	81	#define I32 long
	82	#define U16 unsigned short
	83	#define S16 signed short
	84	#define I16 short
	85	#define U8 unsigned char
	86	#define S8 signed char
	87	#define I8 char
	88
	89	#define M1_MAX_OFFSET 0x0400
	90	#define M2_MAX_OFFSET 0x0800
	91	#define M3_MAX_OFFSET 0x4000
	92	#define M4_MAX_OFFSET 0xbfff
	93
	94	#define __COPY4(dst,src) * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
	95	#define COPY4(dst,src) __COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src))
	96
	97	#define TEST_IP (ip < ip_end)
	98	#define TEST_OP (op <= op_end)
	99
	100	#define NEED_IP(x) \
	101	if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x)) goto input_overrun
	102	#define NEED_OP(x) \
	103	if ((lzo_uint)(op_end - op) < (lzo_uint)(x)) goto output_overrun
	104	#define TEST_LOOKBEHIND(m_pos,out) if (m_pos < out) goto lookbehind_overrun
	105
	106	typedef U32 lzo_uint32;
	107	typedef I32 lzo_int32;
	108	typedef U32 lzo_uint;
	109	typedef I32 lzo_int;
	110	typedef int lzo_bool;
	111
	112	#define lzo_byte U8
	113	#define lzo_bytep U8 *
	114	#define lzo_charp char *
	115	#define lzo_voidp void *
	116	#define lzo_shortp short *
	117	#define lzo_ushortp unsigned short *
	118	#define lzo_uint32p lzo_uint32 *
	119	#define lzo_int32p lzo_int32 *
	120	#define lzo_uintp lzo_uint *
	121	#define lzo_intp lzo_int *
	122	#define lzo_voidpp lzo_voidp *
	123	#define lzo_bytepp lzo_bytep *
	124	#define lzo_sizeof_dict_t sizeof(lzo_bytep)
	125
	126	#define LZO_E_OK 0
	127	#define LZO_E_ERROR (-1)
	128	#define LZO_E_OUT_OF_MEMORY (-2) /* not used right now */
	129	#define LZO_E_NOT_COMPRESSIBLE (-3) /* not used right now */
	130	#define LZO_E_INPUT_OVERRUN (-4)
	131	#define LZO_E_OUTPUT_OVERRUN (-5)
	132	#define LZO_E_LOOKBEHIND_OVERRUN (-6)
	133	#define LZO_E_EOF_NOT_FOUND (-7)
134	#define LZO_E_INPUT_NOT_CONSUMED (-8)
135
136	#define PTR(a) ((lzo_ptr_t) (a))
137	#define PTR_LINEAR(a) PTR(a)
138	#define PTR_ALIGNED_4(a) ((PTR_LINEAR(a) & 3) == 0)
139	#define PTR_ALIGNED_8(a) ((PTR_LINEAR(a) & 7) == 0)
140	#define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) \| PTR_LINEAR(b)) & 3) == 0)
141	#define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) \| PTR_LINEAR(b)) & 7) == 0)
142	#define PTR_LT(a,b) (PTR(a) < PTR(b))
143	#define PTR_GE(a,b) (PTR(a) >= PTR(b))
144	#define PTR_DIFF(a,b) ((lzo_ptrdiff_t) (PTR(a) - PTR(b)))
145	#define pd(a,b) ((lzo_uint) ((a)-(b)))
146
147	typedef ptrdiff_t lzo_ptrdiff_t;
148
149	static int
150	lzo1x_decompress (const lzo_byte * in, lzo_uint in_len,
151	lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
152	{
153	register lzo_byte *op;
154	register const lzo_byte *ip;
155	register lzo_uint t;
156
157	register const lzo_byte *m_pos;
158
159	const lzo_byte *const ip_end = in + in_len;
160	lzo_byte const op_end = out + out_len;
161
162	*out_len = 0;
163
164	op = out;
165	ip = in;
166
167	if (*ip > 17)
168	{
169	t = *ip++ - 17;
170	if (t < 4)
171	goto match_next;
172	NEED_OP (t);
173	NEED_IP (t + 1);
174	do
175	op++ = ip++;
176	while (--t > 0);
177	goto first_literal_run;
178	}
179
180	while (TEST_IP && TEST_OP)
181	{
182	t = *ip++;
183	if (t >= 16)
184	goto match;
185	if (t == 0)
186	{
187	NEED_IP (1);
188	while (*ip == 0)
189	{
190	t += 255;
191	ip++;
192	NEED_IP (1);
193	}
194	t += 15 + *ip++;
195	}
196	NEED_OP (t + 3);
197	NEED_IP (t + 4);
198	if (PTR_ALIGNED2_4 (op, ip))
199	{
200	COPY4 (op, ip);
201
202	op += 4;
203	ip += 4;
204	if (--t > 0)
205	{
206	if (t >= 4)
207	{
208	do
209	{
210	COPY4 (op, ip);
211	op += 4;
212	ip += 4;
213	t -= 4;
214	}
215	while (t >= 4);
216	if (t > 0)
217	do
218	op++ = ip++;
219	while (--t > 0);
220	}
221	else
222	do
223	op++ = ip++;
224	while (--t > 0);
225	}
226	}
227	else
228	{
229	op++ = ip++;
230	op++ = ip++;
231	op++ = ip++;
232	do
233	op++ = ip++;
234	while (--t > 0);
235	}
236	first_literal_run:
237
238	t = *ip++;
239	if (t >= 16)
240	goto match;
241
242	m_pos = op - (1 + M2_MAX_OFFSET);
243	m_pos -= t >> 2;
244	m_pos -= *ip++ << 2;
245	TEST_LOOKBEHIND (m_pos, out);
246	NEED_OP (3);
247	op++ = m_pos++;
248	op++ = m_pos++;
249	op++ = m_pos;
250
251	goto match_done;
252
253	while (TEST_IP && TEST_OP)
254	{
255	match:
256	if (t >= 64)
257	{
258	m_pos = op - 1;
259	m_pos -= (t >> 2) & 7;
260	m_pos -= *ip++ << 3;
261	t = (t >> 5) - 1;
262	TEST_LOOKBEHIND (m_pos, out);
263	NEED_OP (t + 3 - 1);
264	goto copy_match;
265
266	}
267	else if (t >= 32)
268	{
269	t &= 31;
270	if (t == 0)
271	{
272	NEED_IP (1);
273	while (*ip == 0)
274	{
275	t += 255;
276	ip++;
277	NEED_IP (1);
278	}
279	t += 31 + *ip++;
280	}
281
282	m_pos = op - 1;
283	m_pos -= (ip[0] >> 2) + (ip[1] << 6);
284
285	ip += 2;
286	}
287	else if (t >= 16)
288	{
289	m_pos = op;
290	m_pos -= (t & 8) << 11;
291
292	t &= 7;
293	if (t == 0)
294	{
295	NEED_IP (1);
296	while (*ip == 0)
297	{
298	t += 255;
299	ip++;
300	NEED_IP (1);
301	}
302	t += 7 + *ip++;
303	}
304
305	m_pos -= (ip[0] >> 2) + (ip[1] << 6);
306
307	ip += 2;
308	if (m_pos == op)
309	goto eof_found;
310	m_pos -= 0x4000;
311	}
312	else
313	{
314
315	m_pos = op - 1;
316	m_pos -= t >> 2;
317	m_pos -= *ip++ << 2;
318	TEST_LOOKBEHIND (m_pos, out);
319	NEED_OP (2);
320	op++ = m_pos++;
321	op++ = m_pos;
322
323	goto match_done;
324	}
325
326	TEST_LOOKBEHIND (m_pos, out);
327	NEED_OP (t + 3 - 1);
328	if (t >= 2 * 4 - (3 - 1)
329	&& PTR_ALIGNED2_4 (op, m_pos))
330	{
331	COPY4 (op, m_pos);
332	op += 4;
333	m_pos += 4;
334	t -= 4 - (3 - 1);
335	do
336	{
337	COPY4 (op, m_pos);
338	op += 4;
339	m_pos += 4;
340	t -= 4;
341	}
342	while (t >= 4);
343	if (t > 0)
344	do
345	op++ = m_pos++;
346	while (--t > 0);
347	}
348	else
349
350	{
351	copy_match:
352	op++ = m_pos++;
353	op++ = m_pos++;
354	do
355	op++ = m_pos++;
356	while (--t > 0);
357	}
358
359	match_done:
360	t = ip[-2] & 3;
361
362	if (t == 0)
363	break;
364
365	match_next:
366	NEED_OP (t);
367	NEED_IP (t + 1);
368	do
369	op++ = ip++;
370	while (--t > 0);
371	t = *ip++;
372	}
373	}
374	*out_len = op - out;
375	return LZO_E_EOF_NOT_FOUND;
376
377	eof_found:
378	*out_len = op - out;
379	return (ip == ip_end ? LZO_E_OK :
380	(ip <
381	ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
382
383	input_overrun:
384	*out_len = op - out;
385	return LZO_E_INPUT_OVERRUN;
386
387	output_overrun:
388	*out_len = op - out;
389	return LZO_E_OUTPUT_OVERRUN;
390
391	lookbehind_overrun:
392	*out_len = op - out;
393	return LZO_E_LOOKBEHIND_OVERRUN;
394	}
395
396	int lzo_decompress(unsigned char data_in, unsigned char cpage_out,
397	u32 srclen, u32 destlen)
398	{
399	lzo_uint outlen = destlen;
400	return lzo1x_decompress (data_in, srclen, cpage_out, &outlen, NULL);
401	}