xref: /openbmc/u-boot/fs/jffs2/compr_lzo.c (revision 4e109ae9) 
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>
70 #if ((CONFIG_COMMANDS & CFG_CMD_JFFS2) || defined(CONFIG_CMD_JFFS2)) && defined(CONFIG_JFFS2_LZO_LZARI)
71 
72 #include <linux/stddef.h>
73 #include <jffs2/jffs2.h>
74 #include <jffs2/compr_rubin.h>
75 
76 /* Integral types that have *exactly* the same number of bits as a lzo_voidp */
77 typedef unsigned long lzo_ptr_t;
78 typedef long lzo_sptr_t;
79 
80 /* data type definitions */
81 #define U32 unsigned long
82 #define S32 signed long
83 #define I32 long
84 #define U16 unsigned short
85 #define S16 signed short
86 #define I16 short
87 #define U8 unsigned char
88 #define S8 signed char
89 #define I8 char
90 
91 #define M1_MAX_OFFSET	0x0400
92 #define M2_MAX_OFFSET	0x0800
93 #define M3_MAX_OFFSET	0x4000
94 #define M4_MAX_OFFSET	0xbfff
95 
96 #define __COPY4(dst,src)  * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
97 #define COPY4(dst,src)	__COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src))
98 
99 #define TEST_IP		(ip < ip_end)
100 #define TEST_OP		(op <= op_end)
101 
102 #define NEED_IP(x) \
103 	    if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x))  goto input_overrun
104 #define NEED_OP(x) \
105 	    if ((lzo_uint)(op_end - op) < (lzo_uint)(x))  goto output_overrun
106 #define TEST_LOOKBEHIND(m_pos,out)    if (m_pos < out) goto lookbehind_overrun
107 
108 typedef U32 lzo_uint32;
109 typedef I32 lzo_int32;
110 typedef U32 lzo_uint;
111 typedef I32 lzo_int;
112 typedef int lzo_bool;
113 
114 #define lzo_byte		U8
115 #define lzo_bytep		U8 *
116 #define lzo_charp		char *
117 #define lzo_voidp		void *
118 #define lzo_shortp		short *
119 #define lzo_ushortp		unsigned short *
120 #define lzo_uint32p		lzo_uint32 *
121 #define lzo_int32p		lzo_int32 *
122 #define lzo_uintp		lzo_uint *
123 #define lzo_intp		lzo_int *
124 #define lzo_voidpp		lzo_voidp *
125 #define lzo_bytepp		lzo_bytep *
126 #define lzo_sizeof_dict_t		sizeof(lzo_bytep)
127 
128 #define LZO_E_OK		    0
129 #define LZO_E_ERROR		    (-1)
130 #define LZO_E_OUT_OF_MEMORY	    (-2)	/* not used right now */
131 #define LZO_E_NOT_COMPRESSIBLE	    (-3)	/* not used right now */
132 #define LZO_E_INPUT_OVERRUN	    (-4)
133 #define LZO_E_OUTPUT_OVERRUN	    (-5)
134 #define LZO_E_LOOKBEHIND_OVERRUN    (-6)
135 #define LZO_E_EOF_NOT_FOUND	    (-7)
136 #define LZO_E_INPUT_NOT_CONSUMED    (-8)
137 
138 #define PTR(a)				((lzo_ptr_t) (a))
139 #define PTR_LINEAR(a)		PTR(a)
140 #define PTR_ALIGNED_4(a)	((PTR_LINEAR(a) & 3) == 0)
141 #define PTR_ALIGNED_8(a)	((PTR_LINEAR(a) & 7) == 0)
142 #define PTR_ALIGNED2_4(a,b)	(((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0)
143 #define PTR_ALIGNED2_8(a,b)	(((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0)
144 #define PTR_LT(a,b)			(PTR(a) < PTR(b))
145 #define PTR_GE(a,b)			(PTR(a) >= PTR(b))
146 #define PTR_DIFF(a,b)		((lzo_ptrdiff_t) (PTR(a) - PTR(b)))
147 #define pd(a,b)			((lzo_uint) ((a)-(b)))
148 
149 typedef ptrdiff_t lzo_ptrdiff_t;
150 
151 static int
152 lzo1x_decompress (const lzo_byte * in, lzo_uint in_len,
153 		  lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
154 {
155 	register lzo_byte *op;
156 	register const lzo_byte *ip;
157 	register lzo_uint t;
158 
159 	register const lzo_byte *m_pos;
160 
161 	const lzo_byte *const ip_end = in + in_len;
162 	lzo_byte *const op_end = out + *out_len;
163 
164 	*out_len = 0;
165 
166 	op = out;
167 	ip = in;
168 
169 	if (*ip > 17)
170 	{
171 		t = *ip++ - 17;
172 		if (t < 4)
173 			goto match_next;
174 		NEED_OP (t);
175 		NEED_IP (t + 1);
176 		do
177 			*op++ = *ip++;
178 		while (--t > 0);
179 		goto first_literal_run;
180 	}
181 
182 	while (TEST_IP && TEST_OP)
183 	{
184 		t = *ip++;
185 		if (t >= 16)
186 			goto match;
187 		if (t == 0)
188 		{
189 			NEED_IP (1);
190 			while (*ip == 0)
191 			{
192 				t += 255;
193 				ip++;
194 				NEED_IP (1);
195 			}
196 			t += 15 + *ip++;
197 		}
198 		NEED_OP (t + 3);
199 		NEED_IP (t + 4);
200 		if (PTR_ALIGNED2_4 (op, ip))
201 		{
202 			COPY4 (op, ip);
203 
204 			op += 4;
205 			ip += 4;
206 			if (--t > 0)
207 			{
208 				if (t >= 4)
209 				{
210 					do
211 					{
212 						COPY4 (op, ip);
213 						op += 4;
214 						ip += 4;
215 						t -= 4;
216 					}
217 					while (t >= 4);
218 					if (t > 0)
219 						do
220 							*op++ = *ip++;
221 						while (--t > 0);
222 				}
223 				else
224 					do
225 						*op++ = *ip++;
226 					while (--t > 0);
227 			}
228 		}
229 		else
230 		{
231 			*op++ = *ip++;
232 			*op++ = *ip++;
233 			*op++ = *ip++;
234 			do
235 				*op++ = *ip++;
236 			while (--t > 0);
237 		}
238 	      first_literal_run:
239 
240 		t = *ip++;
241 		if (t >= 16)
242 			goto match;
243 
244 		m_pos = op - (1 + M2_MAX_OFFSET);
245 		m_pos -= t >> 2;
246 		m_pos -= *ip++ << 2;
247 		TEST_LOOKBEHIND (m_pos, out);
248 		NEED_OP (3);
249 		*op++ = *m_pos++;
250 		*op++ = *m_pos++;
251 		*op++ = *m_pos;
252 
253 		goto match_done;
254 
255 		while (TEST_IP && TEST_OP)
256 		{
257 		      match:
258 			if (t >= 64)
259 			{
260 				m_pos = op - 1;
261 				m_pos -= (t >> 2) & 7;
262 				m_pos -= *ip++ << 3;
263 				t = (t >> 5) - 1;
264 				TEST_LOOKBEHIND (m_pos, out);
265 				NEED_OP (t + 3 - 1);
266 				goto copy_match;
267 
268 			}
269 			else if (t >= 32)
270 			{
271 				t &= 31;
272 				if (t == 0)
273 				{
274 					NEED_IP (1);
275 					while (*ip == 0)
276 					{
277 						t += 255;
278 						ip++;
279 						NEED_IP (1);
280 					}
281 					t += 31 + *ip++;
282 				}
283 
284 				m_pos = op - 1;
285 				m_pos -= (ip[0] >> 2) + (ip[1] << 6);
286 
287 				ip += 2;
288 			}
289 			else if (t >= 16)
290 			{
291 				m_pos = op;
292 				m_pos -= (t & 8) << 11;
293 
294 				t &= 7;
295 				if (t == 0)
296 				{
297 					NEED_IP (1);
298 					while (*ip == 0)
299 					{
300 						t += 255;
301 						ip++;
302 						NEED_IP (1);
303 					}
304 					t += 7 + *ip++;
305 				}
306 
307 				m_pos -= (ip[0] >> 2) + (ip[1] << 6);
308 
309 				ip += 2;
310 				if (m_pos == op)
311 					goto eof_found;
312 				m_pos -= 0x4000;
313 			}
314 			else
315 			{
316 
317 				m_pos = op - 1;
318 				m_pos -= t >> 2;
319 				m_pos -= *ip++ << 2;
320 				TEST_LOOKBEHIND (m_pos, out);
321 				NEED_OP (2);
322 				*op++ = *m_pos++;
323 				*op++ = *m_pos;
324 
325 				goto match_done;
326 			}
327 
328 			TEST_LOOKBEHIND (m_pos, out);
329 			NEED_OP (t + 3 - 1);
330 			if (t >= 2 * 4 - (3 - 1)
331 			    && PTR_ALIGNED2_4 (op, m_pos))
332 			{
333 				COPY4 (op, m_pos);
334 				op += 4;
335 				m_pos += 4;
336 				t -= 4 - (3 - 1);
337 				do
338 				{
339 					COPY4 (op, m_pos);
340 					op += 4;
341 					m_pos += 4;
342 					t -= 4;
343 				}
344 				while (t >= 4);
345 				if (t > 0)
346 					do
347 						*op++ = *m_pos++;
348 					while (--t > 0);
349 			}
350 			else
351 
352 			{
353 			      copy_match:
354 				*op++ = *m_pos++;
355 				*op++ = *m_pos++;
356 				do
357 					*op++ = *m_pos++;
358 				while (--t > 0);
359 			}
360 
361 		      match_done:
362 			t = ip[-2] & 3;
363 
364 			if (t == 0)
365 				break;
366 
367 		      match_next:
368 			NEED_OP (t);
369 			NEED_IP (t + 1);
370 			do
371 				*op++ = *ip++;
372 			while (--t > 0);
373 			t = *ip++;
374 		}
375 	}
376 	*out_len = op - out;
377 	return LZO_E_EOF_NOT_FOUND;
378 
379       eof_found:
380 	*out_len = op - out;
381 	return (ip == ip_end ? LZO_E_OK :
382 		(ip <
383 		 ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
384 
385       input_overrun:
386 	*out_len = op - out;
387 	return LZO_E_INPUT_OVERRUN;
388 
389       output_overrun:
390 	*out_len = op - out;
391 	return LZO_E_OUTPUT_OVERRUN;
392 
393       lookbehind_overrun:
394 	*out_len = op - out;
395 	return LZO_E_LOOKBEHIND_OVERRUN;
396 }
397 
398 int lzo_decompress(unsigned char *data_in, unsigned char *cpage_out,
399 		      u32 srclen, u32 destlen)
400 {
401 	lzo_uint outlen = destlen;
402 	return lzo1x_decompress (data_in, srclen, cpage_out, &outlen, NULL);
403 }
404 
405 #endif /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI)) */
406