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
lzo1x_decompress(const lzo_byte * in,lzo_uint in_len,lzo_byte * out,lzo_uintp out_len,lzo_voidp wrkmem)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
lzo_decompress(unsigned char * data_in,unsigned char * cpage_out,u32 srclen,u32 destlen)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