blob: b6c590ac8f3a75615548633b2bfabd8255b86a37 [file] [log] [blame]
wdenk07cc0992005-05-05 00:04:14 +00001/*
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>
wdenk412babe2005-05-05 09:51:44 +000070#if ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI))
wdenk07cc0992005-05-05 00:04:14 +000071
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 */
77typedef unsigned long lzo_ptr_t;
78typedef 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
108typedef U32 lzo_uint32;
109typedef I32 lzo_int32;
110typedef U32 lzo_uint;
111typedef I32 lzo_int;
112typedef 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
149typedef ptrdiff_t lzo_ptrdiff_t;
150
151static int
152lzo1x_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
398int 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
wdenk412babe2005-05-05 09:51:44 +0000405#endif /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI)) */