blob: 09bdc8f6ca00324f8b7ec331da7ca58709e42bb9 [file] [log] [blame]
Stefan Roeseb1b4e892009-03-19 15:34:56 +01001/*
2 * LZO1X Decompressor from MiniLZO
3 *
4 * Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
5 *
6 * The full LZO package can be found at:
7 * http://www.oberhumer.com/opensource/lzo/
8 *
9 * Changed for kernel use by:
10 * Nitin Gupta <nitingupta910@gmail.com>
11 * Richard Purdie <rpurdie@openedhand.com>
12 */
13
14#include <common.h>
15#include <linux/lzo.h>
16#include <asm/byteorder.h>
17#include <asm/unaligned.h>
18#include "lzodefs.h"
19
20#define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
21#define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
22#define HAVE_LB(m_pos, out, op) (m_pos < out || m_pos >= op)
23
24#define COPY4(dst, src) \
25 put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
26
Peter Korsgaard20dde482009-11-19 11:37:51 +010027static const unsigned char lzop_magic[] = {
28 0x89, 0x4c, 0x5a, 0x4f, 0x00, 0x0d, 0x0a, 0x1a, 0x0a
29};
30
31#define HEADER_HAS_FILTER 0x00000800L
32
33static inline const unsigned char *parse_header(const unsigned char *src)
34{
35 u8 level = 0;
36 u16 version;
37 int i;
38
39 /* read magic: 9 first bytes */
40 for (i = 0; i < ARRAY_SIZE(lzop_magic); i++) {
41 if (*src++ != lzop_magic[i])
42 return NULL;
43 }
44 /* get version (2bytes), skip library version (2),
45 * 'need to be extracted' version (2) and
46 * method (1) */
47 version = get_unaligned_be16(src);
48 src += 7;
49 if (version >= 0x0940)
50 level = *src++;
51 if (get_unaligned_be32(src) & HEADER_HAS_FILTER)
52 src += 4; /* filter info */
53
54 /* skip flags, mode and mtime_low */
55 src += 12;
56 if (version >= 0x0940)
57 src += 4; /* skip mtime_high */
58
59 i = *src++;
60 /* don't care about the file name, and skip checksum */
61 src += i + 4;
62
63 return src;
64}
65
66int lzop_decompress(const unsigned char *src, size_t src_len,
67 unsigned char *dst, size_t *dst_len)
68{
69 unsigned char *start = dst;
70 const unsigned char *send = src + src_len;
71 u32 slen, dlen;
72 size_t tmp;
73 int r;
74
75 src = parse_header(src);
76 if (!src)
77 return LZO_E_ERROR;
78
79 while (src < send) {
80 /* read uncompressed block size */
81 dlen = get_unaligned_be32(src);
82 src += 4;
83
84 /* exit if last block */
85 if (dlen == 0) {
86 *dst_len = dst - start;
87 return LZO_E_OK;
88 }
89
90 /* read compressed block size, and skip block checksum info */
91 slen = get_unaligned_be32(src);
92 src += 8;
93
94 if (slen <= 0 || slen > dlen)
95 return LZO_E_ERROR;
96
97 /* decompress */
98 tmp = dlen;
99 r = lzo1x_decompress_safe((u8 *) src, slen, dst, &tmp);
100
101 if (r != LZO_E_OK)
102 return r;
103
104 if (dlen != tmp)
105 return LZO_E_ERROR;
106
107 src += slen;
108 dst += dlen;
109 }
110
111 return LZO_E_INPUT_OVERRUN;
112}
113
Stefan Roeseb1b4e892009-03-19 15:34:56 +0100114int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
115 unsigned char *out, size_t *out_len)
116{
117 const unsigned char * const ip_end = in + in_len;
118 unsigned char * const op_end = out + *out_len;
119 const unsigned char *ip = in, *m_pos;
120 unsigned char *op = out;
121 size_t t;
122
123 *out_len = 0;
124
125 if (*ip > 17) {
126 t = *ip++ - 17;
127 if (t < 4)
128 goto match_next;
129 if (HAVE_OP(t, op_end, op))
130 goto output_overrun;
131 if (HAVE_IP(t + 1, ip_end, ip))
132 goto input_overrun;
133 do {
134 *op++ = *ip++;
135 } while (--t > 0);
136 goto first_literal_run;
137 }
138
139 while ((ip < ip_end)) {
140 t = *ip++;
141 if (t >= 16)
142 goto match;
143 if (t == 0) {
144 if (HAVE_IP(1, ip_end, ip))
145 goto input_overrun;
146 while (*ip == 0) {
147 t += 255;
148 ip++;
149 if (HAVE_IP(1, ip_end, ip))
150 goto input_overrun;
151 }
152 t += 15 + *ip++;
153 }
154 if (HAVE_OP(t + 3, op_end, op))
155 goto output_overrun;
156 if (HAVE_IP(t + 4, ip_end, ip))
157 goto input_overrun;
158
159 COPY4(op, ip);
160 op += 4;
161 ip += 4;
162 if (--t > 0) {
163 if (t >= 4) {
164 do {
165 COPY4(op, ip);
166 op += 4;
167 ip += 4;
168 t -= 4;
169 } while (t >= 4);
170 if (t > 0) {
171 do {
172 *op++ = *ip++;
173 } while (--t > 0);
174 }
175 } else {
176 do {
177 *op++ = *ip++;
178 } while (--t > 0);
179 }
180 }
181
182first_literal_run:
183 t = *ip++;
184 if (t >= 16)
185 goto match;
186 m_pos = op - (1 + M2_MAX_OFFSET);
187 m_pos -= t >> 2;
188 m_pos -= *ip++ << 2;
189
190 if (HAVE_LB(m_pos, out, op))
191 goto lookbehind_overrun;
192
193 if (HAVE_OP(3, op_end, op))
194 goto output_overrun;
195 *op++ = *m_pos++;
196 *op++ = *m_pos++;
197 *op++ = *m_pos;
198
199 goto match_done;
200
201 do {
202match:
203 if (t >= 64) {
204 m_pos = op - 1;
205 m_pos -= (t >> 2) & 7;
206 m_pos -= *ip++ << 3;
207 t = (t >> 5) - 1;
208 if (HAVE_LB(m_pos, out, op))
209 goto lookbehind_overrun;
210 if (HAVE_OP(t + 3 - 1, op_end, op))
211 goto output_overrun;
212 goto copy_match;
213 } else if (t >= 32) {
214 t &= 31;
215 if (t == 0) {
216 if (HAVE_IP(1, ip_end, ip))
217 goto input_overrun;
218 while (*ip == 0) {
219 t += 255;
220 ip++;
221 if (HAVE_IP(1, ip_end, ip))
222 goto input_overrun;
223 }
224 t += 31 + *ip++;
225 }
226 m_pos = op - 1;
227 m_pos -= get_unaligned_le16(ip) >> 2;
228 ip += 2;
229 } else if (t >= 16) {
230 m_pos = op;
231 m_pos -= (t & 8) << 11;
232
233 t &= 7;
234 if (t == 0) {
235 if (HAVE_IP(1, ip_end, ip))
236 goto input_overrun;
237 while (*ip == 0) {
238 t += 255;
239 ip++;
240 if (HAVE_IP(1, ip_end, ip))
241 goto input_overrun;
242 }
243 t += 7 + *ip++;
244 }
245 m_pos -= get_unaligned_le16(ip) >> 2;
246 ip += 2;
247 if (m_pos == op)
248 goto eof_found;
249 m_pos -= 0x4000;
250 } else {
251 m_pos = op - 1;
252 m_pos -= t >> 2;
253 m_pos -= *ip++ << 2;
254
255 if (HAVE_LB(m_pos, out, op))
256 goto lookbehind_overrun;
257 if (HAVE_OP(2, op_end, op))
258 goto output_overrun;
259
260 *op++ = *m_pos++;
261 *op++ = *m_pos;
262 goto match_done;
263 }
264
265 if (HAVE_LB(m_pos, out, op))
266 goto lookbehind_overrun;
267 if (HAVE_OP(t + 3 - 1, op_end, op))
268 goto output_overrun;
269
270 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
271 COPY4(op, m_pos);
272 op += 4;
273 m_pos += 4;
274 t -= 4 - (3 - 1);
275 do {
276 COPY4(op, m_pos);
277 op += 4;
278 m_pos += 4;
279 t -= 4;
280 } while (t >= 4);
281 if (t > 0)
282 do {
283 *op++ = *m_pos++;
284 } while (--t > 0);
285 } else {
286copy_match:
287 *op++ = *m_pos++;
288 *op++ = *m_pos++;
289 do {
290 *op++ = *m_pos++;
291 } while (--t > 0);
292 }
293match_done:
294 t = ip[-2] & 3;
295 if (t == 0)
296 break;
297match_next:
298 if (HAVE_OP(t, op_end, op))
299 goto output_overrun;
300 if (HAVE_IP(t + 1, ip_end, ip))
301 goto input_overrun;
302
303 *op++ = *ip++;
304 if (t > 1) {
305 *op++ = *ip++;
306 if (t > 2)
307 *op++ = *ip++;
308 }
309
310 t = *ip++;
311 } while (ip < ip_end);
312 }
313
314 *out_len = op - out;
315 return LZO_E_EOF_NOT_FOUND;
316
317eof_found:
318 *out_len = op - out;
319 return (ip == ip_end ? LZO_E_OK :
320 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
321input_overrun:
322 *out_len = op - out;
323 return LZO_E_INPUT_OVERRUN;
324
325output_overrun:
326 *out_len = op - out;
327 return LZO_E_OUTPUT_OVERRUN;
328
329lookbehind_overrun:
330 *out_len = op - out;
331 return LZO_E_LOOKBEHIND_OVERRUN;
332}