xref: /openbmc/u-boot/lib/lzo/lzo1x_decompress.c (revision 8a23fc9c)
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 
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 
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 
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 
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