xref: /openbmc/u-boot/fs/jffs2/compr_lzo.c (revision 57efeb04) 
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 #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 }
402