blob: ebdf10b988de5964bb7769f2433ab91d8d99bffa [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
Simon Glass670c0172014-12-02 13:17:40 -0700105 if (r != LZO_E_OK) {
106 *dst_len = dst - start;
Peter Korsgaard20dde482009-11-19 11:37:51 +0100107 return r;
Simon Glass670c0172014-12-02 13:17:40 -0700108 }
Peter Korsgaard20dde482009-11-19 11:37:51 +0100109
110 if (dlen != tmp)
111 return LZO_E_ERROR;
112
113 src += slen;
114 dst += dlen;
Kees Cookff9d2ef2013-08-16 07:59:15 -0700115 remaining -= dlen;
Peter Korsgaard20dde482009-11-19 11:37:51 +0100116 }
117
118 return LZO_E_INPUT_OVERRUN;
119}
120
Stefan Roeseb1b4e892009-03-19 15:34:56 +0100121int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
122 unsigned char *out, size_t *out_len)
123{
124 const unsigned char * const ip_end = in + in_len;
125 unsigned char * const op_end = out + *out_len;
126 const unsigned char *ip = in, *m_pos;
127 unsigned char *op = out;
128 size_t t;
129
130 *out_len = 0;
131
132 if (*ip > 17) {
133 t = *ip++ - 17;
134 if (t < 4)
135 goto match_next;
136 if (HAVE_OP(t, op_end, op))
137 goto output_overrun;
138 if (HAVE_IP(t + 1, ip_end, ip))
139 goto input_overrun;
140 do {
141 *op++ = *ip++;
142 } while (--t > 0);
143 goto first_literal_run;
144 }
145
146 while ((ip < ip_end)) {
147 t = *ip++;
148 if (t >= 16)
149 goto match;
150 if (t == 0) {
151 if (HAVE_IP(1, ip_end, ip))
152 goto input_overrun;
153 while (*ip == 0) {
154 t += 255;
155 ip++;
156 if (HAVE_IP(1, ip_end, ip))
157 goto input_overrun;
158 }
159 t += 15 + *ip++;
160 }
161 if (HAVE_OP(t + 3, op_end, op))
162 goto output_overrun;
163 if (HAVE_IP(t + 4, ip_end, ip))
164 goto input_overrun;
165
166 COPY4(op, ip);
167 op += 4;
168 ip += 4;
169 if (--t > 0) {
170 if (t >= 4) {
171 do {
172 COPY4(op, ip);
173 op += 4;
174 ip += 4;
175 t -= 4;
176 } while (t >= 4);
177 if (t > 0) {
178 do {
179 *op++ = *ip++;
180 } while (--t > 0);
181 }
182 } else {
183 do {
184 *op++ = *ip++;
185 } while (--t > 0);
186 }
187 }
188
189first_literal_run:
190 t = *ip++;
191 if (t >= 16)
192 goto match;
193 m_pos = op - (1 + M2_MAX_OFFSET);
194 m_pos -= t >> 2;
195 m_pos -= *ip++ << 2;
196
197 if (HAVE_LB(m_pos, out, op))
198 goto lookbehind_overrun;
199
200 if (HAVE_OP(3, op_end, op))
201 goto output_overrun;
202 *op++ = *m_pos++;
203 *op++ = *m_pos++;
204 *op++ = *m_pos;
205
206 goto match_done;
207
208 do {
209match:
210 if (t >= 64) {
211 m_pos = op - 1;
212 m_pos -= (t >> 2) & 7;
213 m_pos -= *ip++ << 3;
214 t = (t >> 5) - 1;
215 if (HAVE_LB(m_pos, out, op))
216 goto lookbehind_overrun;
217 if (HAVE_OP(t + 3 - 1, op_end, op))
218 goto output_overrun;
219 goto copy_match;
220 } else if (t >= 32) {
221 t &= 31;
222 if (t == 0) {
223 if (HAVE_IP(1, ip_end, ip))
224 goto input_overrun;
225 while (*ip == 0) {
226 t += 255;
227 ip++;
228 if (HAVE_IP(1, ip_end, ip))
229 goto input_overrun;
230 }
231 t += 31 + *ip++;
232 }
233 m_pos = op - 1;
234 m_pos -= get_unaligned_le16(ip) >> 2;
235 ip += 2;
236 } else if (t >= 16) {
237 m_pos = op;
238 m_pos -= (t & 8) << 11;
239
240 t &= 7;
241 if (t == 0) {
242 if (HAVE_IP(1, ip_end, ip))
243 goto input_overrun;
244 while (*ip == 0) {
245 t += 255;
246 ip++;
247 if (HAVE_IP(1, ip_end, ip))
248 goto input_overrun;
249 }
250 t += 7 + *ip++;
251 }
252 m_pos -= get_unaligned_le16(ip) >> 2;
253 ip += 2;
254 if (m_pos == op)
255 goto eof_found;
256 m_pos -= 0x4000;
257 } else {
258 m_pos = op - 1;
259 m_pos -= t >> 2;
260 m_pos -= *ip++ << 2;
261
262 if (HAVE_LB(m_pos, out, op))
263 goto lookbehind_overrun;
264 if (HAVE_OP(2, op_end, op))
265 goto output_overrun;
266
267 *op++ = *m_pos++;
268 *op++ = *m_pos;
269 goto match_done;
270 }
271
272 if (HAVE_LB(m_pos, out, op))
273 goto lookbehind_overrun;
274 if (HAVE_OP(t + 3 - 1, op_end, op))
275 goto output_overrun;
276
277 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
278 COPY4(op, m_pos);
279 op += 4;
280 m_pos += 4;
281 t -= 4 - (3 - 1);
282 do {
283 COPY4(op, m_pos);
284 op += 4;
285 m_pos += 4;
286 t -= 4;
287 } while (t >= 4);
288 if (t > 0)
289 do {
290 *op++ = *m_pos++;
291 } while (--t > 0);
292 } else {
293copy_match:
294 *op++ = *m_pos++;
295 *op++ = *m_pos++;
296 do {
297 *op++ = *m_pos++;
298 } while (--t > 0);
299 }
300match_done:
301 t = ip[-2] & 3;
302 if (t == 0)
303 break;
304match_next:
305 if (HAVE_OP(t, op_end, op))
306 goto output_overrun;
307 if (HAVE_IP(t + 1, ip_end, ip))
308 goto input_overrun;
309
310 *op++ = *ip++;
311 if (t > 1) {
312 *op++ = *ip++;
313 if (t > 2)
314 *op++ = *ip++;
315 }
316
317 t = *ip++;
318 } while (ip < ip_end);
319 }
320
321 *out_len = op - out;
322 return LZO_E_EOF_NOT_FOUND;
323
324eof_found:
325 *out_len = op - out;
326 return (ip == ip_end ? LZO_E_OK :
327 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
328input_overrun:
329 *out_len = op - out;
330 return LZO_E_INPUT_OVERRUN;
331
332output_overrun:
333 *out_len = op - out;
334 return LZO_E_OUTPUT_OVERRUN;
335
336lookbehind_overrun:
337 *out_len = op - out;
338 return LZO_E_LOOKBEHIND_OVERRUN;
339}