1 /*
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
27 static const unsigned char lzop_magic[] = {
28 0x89, 0x4c, 0x5a, 0x4f, 0x00, 0x0d, 0x0a, 0x1a, 0x0a
29 };
30
31 #define HEADER_HAS_FILTER 0x00000800L
32
33
lzop_is_valid_header(const unsigned char * src)34 bool lzop_is_valid_header(const unsigned char *src)
35 {
36 int i;
37 /* read magic: 9 first bytes */
38 for (i = 0; i < ARRAY_SIZE(lzop_magic); i++) {
39 if (*src++ != lzop_magic[i])
40 return false;
41 }
42 return true;
43 }
44
parse_header(const unsigned char * src)45 static inline const unsigned char *parse_header(const unsigned char *src)
46 {
47 u16 version;
48 int i;
49
50 if (!lzop_is_valid_header(src))
51 return NULL;
52
53 /* skip header */
54 src += 9;
55
56 /* get version (2bytes), skip library version (2),
57 * 'need to be extracted' version (2) and
58 * method (1) */
59 version = get_unaligned_be16(src);
60 src += 7;
61 if (version >= 0x0940)
62 src++;
63 if (get_unaligned_be32(src) & HEADER_HAS_FILTER)
64 src += 4; /* filter info */
65
66 /* skip flags, mode and mtime_low */
67 src += 12;
68 if (version >= 0x0940)
69 src += 4; /* skip mtime_high */
70
71 i = *src++;
72 /* don't care about the file name, and skip checksum */
73 src += i + 4;
74
75 return src;
76 }
77
lzop_decompress(const unsigned char * src,size_t src_len,unsigned char * dst,size_t * dst_len)78 int lzop_decompress(const unsigned char *src, size_t src_len,
79 unsigned char *dst, size_t *dst_len)
80 {
81 unsigned char *start = dst;
82 const unsigned char *send = src + src_len;
83 u32 slen, dlen;
84 size_t tmp, remaining;
85 int r;
86
87 src = parse_header(src);
88 if (!src)
89 return LZO_E_ERROR;
90
91 remaining = *dst_len;
92 while (src < send) {
93 /* read uncompressed block size */
94 dlen = get_unaligned_be32(src);
95 src += 4;
96
97 /* exit if last block */
98 if (dlen == 0) {
99 *dst_len = dst - start;
100 return LZO_E_OK;
101 }
102
103 /* read compressed block size, and skip block checksum info */
104 slen = get_unaligned_be32(src);
105 src += 8;
106
107 if (slen <= 0 || slen > dlen)
108 return LZO_E_ERROR;
109
110 /* abort if buffer ran out of room */
111 if (dlen > remaining)
112 return LZO_E_OUTPUT_OVERRUN;
113
114 /* When the input data is not compressed at all,
115 * lzo1x_decompress_safe will fail, so call memcpy()
116 * instead */
117 if (dlen == slen) {
118 memcpy(dst, src, slen);
119 } else {
120 /* decompress */
121 tmp = dlen;
122 r = lzo1x_decompress_safe((u8 *)src, slen, dst, &tmp);
123
124 if (r != LZO_E_OK) {
125 *dst_len = dst - start;
126 return r;
127 }
128
129 if (dlen != tmp)
130 return LZO_E_ERROR;
131 }
132
133 src += slen;
134 dst += dlen;
135 remaining -= dlen;
136 }
137
138 return LZO_E_INPUT_OVERRUN;
139 }
140
lzo1x_decompress_safe(const unsigned char * in,size_t in_len,unsigned char * out,size_t * out_len)141 int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
142 unsigned char *out, size_t *out_len)
143 {
144 const unsigned char * const ip_end = in + in_len;
145 unsigned char * const op_end = out + *out_len;
146 const unsigned char *ip = in, *m_pos;
147 unsigned char *op = out;
148 size_t t;
149
150 *out_len = 0;
151
152 if (*ip > 17) {
153 t = *ip++ - 17;
154 if (t < 4)
155 goto match_next;
156 if (HAVE_OP(t, op_end, op))
157 goto output_overrun;
158 if (HAVE_IP(t + 1, ip_end, ip))
159 goto input_overrun;
160 do {
161 *op++ = *ip++;
162 } while (--t > 0);
163 goto first_literal_run;
164 }
165
166 while ((ip < ip_end)) {
167 t = *ip++;
168 if (t >= 16)
169 goto match;
170 if (t == 0) {
171 if (HAVE_IP(1, ip_end, ip))
172 goto input_overrun;
173 while (*ip == 0) {
174 t += 255;
175 ip++;
176 if (HAVE_IP(1, ip_end, ip))
177 goto input_overrun;
178 }
179 t += 15 + *ip++;
180 }
181 if (HAVE_OP(t + 3, op_end, op))
182 goto output_overrun;
183 if (HAVE_IP(t + 4, ip_end, ip))
184 goto input_overrun;
185
186 COPY4(op, ip);
187 op += 4;
188 ip += 4;
189 if (--t > 0) {
190 if (t >= 4) {
191 do {
192 COPY4(op, ip);
193 op += 4;
194 ip += 4;
195 t -= 4;
196 } while (t >= 4);
197 if (t > 0) {
198 do {
199 *op++ = *ip++;
200 } while (--t > 0);
201 }
202 } else {
203 do {
204 *op++ = *ip++;
205 } while (--t > 0);
206 }
207 }
208
209 first_literal_run:
210 t = *ip++;
211 if (t >= 16)
212 goto match;
213 m_pos = op - (1 + M2_MAX_OFFSET);
214 m_pos -= t >> 2;
215 m_pos -= *ip++ << 2;
216
217 if (HAVE_LB(m_pos, out, op))
218 goto lookbehind_overrun;
219
220 if (HAVE_OP(3, op_end, op))
221 goto output_overrun;
222 *op++ = *m_pos++;
223 *op++ = *m_pos++;
224 *op++ = *m_pos;
225
226 goto match_done;
227
228 do {
229 match:
230 if (t >= 64) {
231 m_pos = op - 1;
232 m_pos -= (t >> 2) & 7;
233 m_pos -= *ip++ << 3;
234 t = (t >> 5) - 1;
235 if (HAVE_LB(m_pos, out, op))
236 goto lookbehind_overrun;
237 if (HAVE_OP(t + 3 - 1, op_end, op))
238 goto output_overrun;
239 goto copy_match;
240 } else if (t >= 32) {
241 t &= 31;
242 if (t == 0) {
243 if (HAVE_IP(1, ip_end, ip))
244 goto input_overrun;
245 while (*ip == 0) {
246 t += 255;
247 ip++;
248 if (HAVE_IP(1, ip_end, ip))
249 goto input_overrun;
250 }
251 t += 31 + *ip++;
252 }
253 m_pos = op - 1;
254 m_pos -= get_unaligned_le16(ip) >> 2;
255 ip += 2;
256 } else if (t >= 16) {
257 m_pos = op;
258 m_pos -= (t & 8) << 11;
259
260 t &= 7;
261 if (t == 0) {
262 if (HAVE_IP(1, ip_end, ip))
263 goto input_overrun;
264 while (*ip == 0) {
265 t += 255;
266 ip++;
267 if (HAVE_IP(1, ip_end, ip))
268 goto input_overrun;
269 }
270 t += 7 + *ip++;
271 }
272 m_pos -= get_unaligned_le16(ip) >> 2;
273 ip += 2;
274 if (m_pos == op)
275 goto eof_found;
276 m_pos -= 0x4000;
277 } else {
278 m_pos = op - 1;
279 m_pos -= t >> 2;
280 m_pos -= *ip++ << 2;
281
282 if (HAVE_LB(m_pos, out, op))
283 goto lookbehind_overrun;
284 if (HAVE_OP(2, op_end, op))
285 goto output_overrun;
286
287 *op++ = *m_pos++;
288 *op++ = *m_pos;
289 goto match_done;
290 }
291
292 if (HAVE_LB(m_pos, out, op))
293 goto lookbehind_overrun;
294 if (HAVE_OP(t + 3 - 1, op_end, op))
295 goto output_overrun;
296
297 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
298 COPY4(op, m_pos);
299 op += 4;
300 m_pos += 4;
301 t -= 4 - (3 - 1);
302 do {
303 COPY4(op, m_pos);
304 op += 4;
305 m_pos += 4;
306 t -= 4;
307 } while (t >= 4);
308 if (t > 0)
309 do {
310 *op++ = *m_pos++;
311 } while (--t > 0);
312 } else {
313 copy_match:
314 *op++ = *m_pos++;
315 *op++ = *m_pos++;
316 do {
317 *op++ = *m_pos++;
318 } while (--t > 0);
319 }
320 match_done:
321 t = ip[-2] & 3;
322 if (t == 0)
323 break;
324 match_next:
325 if (HAVE_OP(t, op_end, op))
326 goto output_overrun;
327 if (HAVE_IP(t + 1, ip_end, ip))
328 goto input_overrun;
329
330 *op++ = *ip++;
331 if (t > 1) {
332 *op++ = *ip++;
333 if (t > 2)
334 *op++ = *ip++;
335 }
336
337 t = *ip++;
338 } while (ip < ip_end);
339 }
340
341 *out_len = op - out;
342 return LZO_E_EOF_NOT_FOUND;
343
344 eof_found:
345 *out_len = op - out;
346 return (ip == ip_end ? LZO_E_OK :
347 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
348 input_overrun:
349 *out_len = op - out;
350 return LZO_E_INPUT_OVERRUN;
351
352 output_overrun:
353 *out_len = op - out;
354 return LZO_E_OUTPUT_OVERRUN;
355
356 lookbehind_overrun:
357 *out_len = op - out;
358 return LZO_E_LOOKBEHIND_OVERRUN;
359 }
360