blob: e6ff708f11999e0ddf96efe06818d61c15fa382c [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;
71 size_t tmp;
72 int r;
73
74 src = parse_header(src);
75 if (!src)
76 return LZO_E_ERROR;
77
78 while (src < send) {
79 /* read uncompressed block size */
80 dlen = get_unaligned_be32(src);
81 src += 4;
82
83 /* exit if last block */
84 if (dlen == 0) {
85 *dst_len = dst - start;
86 return LZO_E_OK;
87 }
88
89 /* read compressed block size, and skip block checksum info */
90 slen = get_unaligned_be32(src);
91 src += 8;
92
93 if (slen <= 0 || slen > dlen)
94 return LZO_E_ERROR;
95
96 /* decompress */
97 tmp = dlen;
98 r = lzo1x_decompress_safe((u8 *) src, slen, dst, &tmp);
99
100 if (r != LZO_E_OK)
101 return r;
102
103 if (dlen != tmp)
104 return LZO_E_ERROR;
105
106 src += slen;
107 dst += dlen;
108 }
109
110 return LZO_E_INPUT_OVERRUN;
111}
112
Stefan Roeseb1b4e892009-03-19 15:34:56 +0100113int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
114 unsigned char *out, size_t *out_len)
115{
116 const unsigned char * const ip_end = in + in_len;
117 unsigned char * const op_end = out + *out_len;
118 const unsigned char *ip = in, *m_pos;
119 unsigned char *op = out;
120 size_t t;
121
122 *out_len = 0;
123
124 if (*ip > 17) {
125 t = *ip++ - 17;
126 if (t < 4)
127 goto match_next;
128 if (HAVE_OP(t, op_end, op))
129 goto output_overrun;
130 if (HAVE_IP(t + 1, ip_end, ip))
131 goto input_overrun;
132 do {
133 *op++ = *ip++;
134 } while (--t > 0);
135 goto first_literal_run;
136 }
137
138 while ((ip < ip_end)) {
139 t = *ip++;
140 if (t >= 16)
141 goto match;
142 if (t == 0) {
143 if (HAVE_IP(1, ip_end, ip))
144 goto input_overrun;
145 while (*ip == 0) {
146 t += 255;
147 ip++;
148 if (HAVE_IP(1, ip_end, ip))
149 goto input_overrun;
150 }
151 t += 15 + *ip++;
152 }
153 if (HAVE_OP(t + 3, op_end, op))
154 goto output_overrun;
155 if (HAVE_IP(t + 4, ip_end, ip))
156 goto input_overrun;
157
158 COPY4(op, ip);
159 op += 4;
160 ip += 4;
161 if (--t > 0) {
162 if (t >= 4) {
163 do {
164 COPY4(op, ip);
165 op += 4;
166 ip += 4;
167 t -= 4;
168 } while (t >= 4);
169 if (t > 0) {
170 do {
171 *op++ = *ip++;
172 } while (--t > 0);
173 }
174 } else {
175 do {
176 *op++ = *ip++;
177 } while (--t > 0);
178 }
179 }
180
181first_literal_run:
182 t = *ip++;
183 if (t >= 16)
184 goto match;
185 m_pos = op - (1 + M2_MAX_OFFSET);
186 m_pos -= t >> 2;
187 m_pos -= *ip++ << 2;
188
189 if (HAVE_LB(m_pos, out, op))
190 goto lookbehind_overrun;
191
192 if (HAVE_OP(3, op_end, op))
193 goto output_overrun;
194 *op++ = *m_pos++;
195 *op++ = *m_pos++;
196 *op++ = *m_pos;
197
198 goto match_done;
199
200 do {
201match:
202 if (t >= 64) {
203 m_pos = op - 1;
204 m_pos -= (t >> 2) & 7;
205 m_pos -= *ip++ << 3;
206 t = (t >> 5) - 1;
207 if (HAVE_LB(m_pos, out, op))
208 goto lookbehind_overrun;
209 if (HAVE_OP(t + 3 - 1, op_end, op))
210 goto output_overrun;
211 goto copy_match;
212 } else if (t >= 32) {
213 t &= 31;
214 if (t == 0) {
215 if (HAVE_IP(1, ip_end, ip))
216 goto input_overrun;
217 while (*ip == 0) {
218 t += 255;
219 ip++;
220 if (HAVE_IP(1, ip_end, ip))
221 goto input_overrun;
222 }
223 t += 31 + *ip++;
224 }
225 m_pos = op - 1;
226 m_pos -= get_unaligned_le16(ip) >> 2;
227 ip += 2;
228 } else if (t >= 16) {
229 m_pos = op;
230 m_pos -= (t & 8) << 11;
231
232 t &= 7;
233 if (t == 0) {
234 if (HAVE_IP(1, ip_end, ip))
235 goto input_overrun;
236 while (*ip == 0) {
237 t += 255;
238 ip++;
239 if (HAVE_IP(1, ip_end, ip))
240 goto input_overrun;
241 }
242 t += 7 + *ip++;
243 }
244 m_pos -= get_unaligned_le16(ip) >> 2;
245 ip += 2;
246 if (m_pos == op)
247 goto eof_found;
248 m_pos -= 0x4000;
249 } else {
250 m_pos = op - 1;
251 m_pos -= t >> 2;
252 m_pos -= *ip++ << 2;
253
254 if (HAVE_LB(m_pos, out, op))
255 goto lookbehind_overrun;
256 if (HAVE_OP(2, op_end, op))
257 goto output_overrun;
258
259 *op++ = *m_pos++;
260 *op++ = *m_pos;
261 goto match_done;
262 }
263
264 if (HAVE_LB(m_pos, out, op))
265 goto lookbehind_overrun;
266 if (HAVE_OP(t + 3 - 1, op_end, op))
267 goto output_overrun;
268
269 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
270 COPY4(op, m_pos);
271 op += 4;
272 m_pos += 4;
273 t -= 4 - (3 - 1);
274 do {
275 COPY4(op, m_pos);
276 op += 4;
277 m_pos += 4;
278 t -= 4;
279 } while (t >= 4);
280 if (t > 0)
281 do {
282 *op++ = *m_pos++;
283 } while (--t > 0);
284 } else {
285copy_match:
286 *op++ = *m_pos++;
287 *op++ = *m_pos++;
288 do {
289 *op++ = *m_pos++;
290 } while (--t > 0);
291 }
292match_done:
293 t = ip[-2] & 3;
294 if (t == 0)
295 break;
296match_next:
297 if (HAVE_OP(t, op_end, op))
298 goto output_overrun;
299 if (HAVE_IP(t + 1, ip_end, ip))
300 goto input_overrun;
301
302 *op++ = *ip++;
303 if (t > 1) {
304 *op++ = *ip++;
305 if (t > 2)
306 *op++ = *ip++;
307 }
308
309 t = *ip++;
310 } while (ip < ip_end);
311 }
312
313 *out_len = op - out;
314 return LZO_E_EOF_NOT_FOUND;
315
316eof_found:
317 *out_len = op - out;
318 return (ip == ip_end ? LZO_E_OK :
319 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
320input_overrun:
321 *out_len = op - out;
322 return LZO_E_INPUT_OVERRUN;
323
324output_overrun:
325 *out_len = op - out;
326 return LZO_E_OUTPUT_OVERRUN;
327
328lookbehind_overrun:
329 *out_len = op - out;
330 return LZO_E_LOOKBEHIND_OVERRUN;
331}