blob: 35f3793f31c61e045df3c634b5299d7c735fc623 [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{
Peter Korsgaard20dde482009-11-19 11:37:51 +010035 u16 version;
36 int i;
37
38 /* read magic: 9 first bytes */
39 for (i = 0; i < ARRAY_SIZE(lzop_magic); i++) {
40 if (*src++ != lzop_magic[i])
41 return NULL;
42 }
43 /* get version (2bytes), skip library version (2),
44 * 'need to be extracted' version (2) and
45 * method (1) */
46 version = get_unaligned_be16(src);
47 src += 7;
48 if (version >= 0x0940)
Marek Vasut7b8ffea2011-09-30 12:13:26 +020049 src++;
Peter Korsgaard20dde482009-11-19 11:37:51 +010050 if (get_unaligned_be32(src) & HEADER_HAS_FILTER)
51 src += 4; /* filter info */
52
53 /* skip flags, mode and mtime_low */
54 src += 12;
55 if (version >= 0x0940)
56 src += 4; /* skip mtime_high */
57
58 i = *src++;
59 /* don't care about the file name, and skip checksum */
60 src += i + 4;
61
62 return src;
63}
64
65int lzop_decompress(const unsigned char *src, size_t src_len,
66 unsigned char *dst, size_t *dst_len)
67{
68 unsigned char *start = dst;
69 const unsigned char *send = src + src_len;
70 u32 slen, dlen;
Kees Cookff9d2ef2013-08-16 07:59:15 -070071 size_t tmp, remaining;
Peter Korsgaard20dde482009-11-19 11:37:51 +010072 int r;
73
74 src = parse_header(src);
75 if (!src)
76 return LZO_E_ERROR;
77
Kees Cookff9d2ef2013-08-16 07:59:15 -070078 remaining = *dst_len;
Peter Korsgaard20dde482009-11-19 11:37:51 +010079 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
Kees Cookff9d2ef2013-08-16 07:59:15 -070097 /* abort if buffer ran out of room */
98 if (dlen > remaining)
99 return LZO_E_OUTPUT_OVERRUN;
100
Peter Korsgaard20dde482009-11-19 11:37:51 +0100101 /* decompress */
102 tmp = dlen;
103 r = lzo1x_decompress_safe((u8 *) src, slen, dst, &tmp);
104
105 if (r != LZO_E_OK)
106 return r;
107
108 if (dlen != tmp)
109 return LZO_E_ERROR;
110
111 src += slen;
112 dst += dlen;
Kees Cookff9d2ef2013-08-16 07:59:15 -0700113 remaining -= dlen;
Peter Korsgaard20dde482009-11-19 11:37:51 +0100114 }
115
116 return LZO_E_INPUT_OVERRUN;
117}
118
Stefan Roeseb1b4e892009-03-19 15:34:56 +0100119int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
120 unsigned char *out, size_t *out_len)
121{
122 const unsigned char * const ip_end = in + in_len;
123 unsigned char * const op_end = out + *out_len;
124 const unsigned char *ip = in, *m_pos;
125 unsigned char *op = out;
126 size_t t;
127
128 *out_len = 0;
129
130 if (*ip > 17) {
131 t = *ip++ - 17;
132 if (t < 4)
133 goto match_next;
134 if (HAVE_OP(t, op_end, op))
135 goto output_overrun;
136 if (HAVE_IP(t + 1, ip_end, ip))
137 goto input_overrun;
138 do {
139 *op++ = *ip++;
140 } while (--t > 0);
141 goto first_literal_run;
142 }
143
144 while ((ip < ip_end)) {
145 t = *ip++;
146 if (t >= 16)
147 goto match;
148 if (t == 0) {
149 if (HAVE_IP(1, ip_end, ip))
150 goto input_overrun;
151 while (*ip == 0) {
152 t += 255;
153 ip++;
154 if (HAVE_IP(1, ip_end, ip))
155 goto input_overrun;
156 }
157 t += 15 + *ip++;
158 }
159 if (HAVE_OP(t + 3, op_end, op))
160 goto output_overrun;
161 if (HAVE_IP(t + 4, ip_end, ip))
162 goto input_overrun;
163
164 COPY4(op, ip);
165 op += 4;
166 ip += 4;
167 if (--t > 0) {
168 if (t >= 4) {
169 do {
170 COPY4(op, ip);
171 op += 4;
172 ip += 4;
173 t -= 4;
174 } while (t >= 4);
175 if (t > 0) {
176 do {
177 *op++ = *ip++;
178 } while (--t > 0);
179 }
180 } else {
181 do {
182 *op++ = *ip++;
183 } while (--t > 0);
184 }
185 }
186
187first_literal_run:
188 t = *ip++;
189 if (t >= 16)
190 goto match;
191 m_pos = op - (1 + M2_MAX_OFFSET);
192 m_pos -= t >> 2;
193 m_pos -= *ip++ << 2;
194
195 if (HAVE_LB(m_pos, out, op))
196 goto lookbehind_overrun;
197
198 if (HAVE_OP(3, op_end, op))
199 goto output_overrun;
200 *op++ = *m_pos++;
201 *op++ = *m_pos++;
202 *op++ = *m_pos;
203
204 goto match_done;
205
206 do {
207match:
208 if (t >= 64) {
209 m_pos = op - 1;
210 m_pos -= (t >> 2) & 7;
211 m_pos -= *ip++ << 3;
212 t = (t >> 5) - 1;
213 if (HAVE_LB(m_pos, out, op))
214 goto lookbehind_overrun;
215 if (HAVE_OP(t + 3 - 1, op_end, op))
216 goto output_overrun;
217 goto copy_match;
218 } else if (t >= 32) {
219 t &= 31;
220 if (t == 0) {
221 if (HAVE_IP(1, ip_end, ip))
222 goto input_overrun;
223 while (*ip == 0) {
224 t += 255;
225 ip++;
226 if (HAVE_IP(1, ip_end, ip))
227 goto input_overrun;
228 }
229 t += 31 + *ip++;
230 }
231 m_pos = op - 1;
232 m_pos -= get_unaligned_le16(ip) >> 2;
233 ip += 2;
234 } else if (t >= 16) {
235 m_pos = op;
236 m_pos -= (t & 8) << 11;
237
238 t &= 7;
239 if (t == 0) {
240 if (HAVE_IP(1, ip_end, ip))
241 goto input_overrun;
242 while (*ip == 0) {
243 t += 255;
244 ip++;
245 if (HAVE_IP(1, ip_end, ip))
246 goto input_overrun;
247 }
248 t += 7 + *ip++;
249 }
250 m_pos -= get_unaligned_le16(ip) >> 2;
251 ip += 2;
252 if (m_pos == op)
253 goto eof_found;
254 m_pos -= 0x4000;
255 } else {
256 m_pos = op - 1;
257 m_pos -= t >> 2;
258 m_pos -= *ip++ << 2;
259
260 if (HAVE_LB(m_pos, out, op))
261 goto lookbehind_overrun;
262 if (HAVE_OP(2, op_end, op))
263 goto output_overrun;
264
265 *op++ = *m_pos++;
266 *op++ = *m_pos;
267 goto match_done;
268 }
269
270 if (HAVE_LB(m_pos, out, op))
271 goto lookbehind_overrun;
272 if (HAVE_OP(t + 3 - 1, op_end, op))
273 goto output_overrun;
274
275 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
276 COPY4(op, m_pos);
277 op += 4;
278 m_pos += 4;
279 t -= 4 - (3 - 1);
280 do {
281 COPY4(op, m_pos);
282 op += 4;
283 m_pos += 4;
284 t -= 4;
285 } while (t >= 4);
286 if (t > 0)
287 do {
288 *op++ = *m_pos++;
289 } while (--t > 0);
290 } else {
291copy_match:
292 *op++ = *m_pos++;
293 *op++ = *m_pos++;
294 do {
295 *op++ = *m_pos++;
296 } while (--t > 0);
297 }
298match_done:
299 t = ip[-2] & 3;
300 if (t == 0)
301 break;
302match_next:
303 if (HAVE_OP(t, op_end, op))
304 goto output_overrun;
305 if (HAVE_IP(t + 1, ip_end, ip))
306 goto input_overrun;
307
308 *op++ = *ip++;
309 if (t > 1) {
310 *op++ = *ip++;
311 if (t > 2)
312 *op++ = *ip++;
313 }
314
315 t = *ip++;
316 } while (ip < ip_end);
317 }
318
319 *out_len = op - out;
320 return LZO_E_EOF_NOT_FOUND;
321
322eof_found:
323 *out_len = op - out;
324 return (ip == ip_end ? LZO_E_OK :
325 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
326input_overrun:
327 *out_len = op - out;
328 return LZO_E_INPUT_OVERRUN;
329
330output_overrun:
331 *out_len = op - out;
332 return LZO_E_OUTPUT_OVERRUN;
333
334lookbehind_overrun:
335 *out_len = op - out;
336 return LZO_E_LOOKBEHIND_OVERRUN;
337}