xref: /openbmc/u-boot/lib/lzo/lzo1x_decompress.c (revision 274bced8) 
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 static inline const unsigned char *parse_header(const unsigned char *src)
34 {
35 	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)
49 		src++;
50 	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 
65 int 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, remaining;
72 	int r;
73 
74 	src = parse_header(src);
75 	if (!src)
76 		return LZO_E_ERROR;
77 
78 	remaining = *dst_len;
79 	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 
97 		/* abort if buffer ran out of room */
98 		if (dlen > remaining)
99 			return LZO_E_OUTPUT_OVERRUN;
100 
101 		/* When the input data is not compressed at all,
102 		 * lzo1x_decompress_safe will fail, so call memcpy()
103 		 * instead */
104 		if (dlen == slen) {
105 			memcpy(dst, src, slen);
106 		} else {
107 			/* decompress */
108 			tmp = dlen;
109 			r = lzo1x_decompress_safe((u8 *)src, slen, dst, &tmp);
110 
111 			if (r != LZO_E_OK) {
112 				*dst_len = dst - start;
113 				return r;
114 			}
115 
116 			if (dlen != tmp)
117 				return LZO_E_ERROR;
118 		}
119 
120 		src += slen;
121 		dst += dlen;
122 		remaining -= dlen;
123 	}
124 
125 	return LZO_E_INPUT_OVERRUN;
126 }
127 
128 int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
129 			unsigned char *out, size_t *out_len)
130 {
131 	const unsigned char * const ip_end = in + in_len;
132 	unsigned char * const op_end = out + *out_len;
133 	const unsigned char *ip = in, *m_pos;
134 	unsigned char *op = out;
135 	size_t t;
136 
137 	*out_len = 0;
138 
139 	if (*ip > 17) {
140 		t = *ip++ - 17;
141 		if (t < 4)
142 			goto match_next;
143 		if (HAVE_OP(t, op_end, op))
144 			goto output_overrun;
145 		if (HAVE_IP(t + 1, ip_end, ip))
146 			goto input_overrun;
147 		do {
148 			*op++ = *ip++;
149 		} while (--t > 0);
150 		goto first_literal_run;
151 	}
152 
153 	while ((ip < ip_end)) {
154 		t = *ip++;
155 		if (t >= 16)
156 			goto match;
157 		if (t == 0) {
158 			if (HAVE_IP(1, ip_end, ip))
159 				goto input_overrun;
160 			while (*ip == 0) {
161 				t += 255;
162 				ip++;
163 				if (HAVE_IP(1, ip_end, ip))
164 					goto input_overrun;
165 			}
166 			t += 15 + *ip++;
167 		}
168 		if (HAVE_OP(t + 3, op_end, op))
169 			goto output_overrun;
170 		if (HAVE_IP(t + 4, ip_end, ip))
171 			goto input_overrun;
172 
173 		COPY4(op, ip);
174 		op += 4;
175 		ip += 4;
176 		if (--t > 0) {
177 			if (t >= 4) {
178 				do {
179 					COPY4(op, ip);
180 					op += 4;
181 					ip += 4;
182 					t -= 4;
183 				} while (t >= 4);
184 				if (t > 0) {
185 					do {
186 						*op++ = *ip++;
187 					} while (--t > 0);
188 				}
189 			} else {
190 				do {
191 					*op++ = *ip++;
192 				} while (--t > 0);
193 			}
194 		}
195 
196 first_literal_run:
197 		t = *ip++;
198 		if (t >= 16)
199 			goto match;
200 		m_pos = op - (1 + M2_MAX_OFFSET);
201 		m_pos -= t >> 2;
202 		m_pos -= *ip++ << 2;
203 
204 		if (HAVE_LB(m_pos, out, op))
205 			goto lookbehind_overrun;
206 
207 		if (HAVE_OP(3, op_end, op))
208 			goto output_overrun;
209 		*op++ = *m_pos++;
210 		*op++ = *m_pos++;
211 		*op++ = *m_pos;
212 
213 		goto match_done;
214 
215 		do {
216 match:
217 			if (t >= 64) {
218 				m_pos = op - 1;
219 				m_pos -= (t >> 2) & 7;
220 				m_pos -= *ip++ << 3;
221 				t = (t >> 5) - 1;
222 				if (HAVE_LB(m_pos, out, op))
223 					goto lookbehind_overrun;
224 				if (HAVE_OP(t + 3 - 1, op_end, op))
225 					goto output_overrun;
226 				goto copy_match;
227 			} else if (t >= 32) {
228 				t &= 31;
229 				if (t == 0) {
230 					if (HAVE_IP(1, ip_end, ip))
231 						goto input_overrun;
232 					while (*ip == 0) {
233 						t += 255;
234 						ip++;
235 						if (HAVE_IP(1, ip_end, ip))
236 							goto input_overrun;
237 					}
238 					t += 31 + *ip++;
239 				}
240 				m_pos = op - 1;
241 				m_pos -= get_unaligned_le16(ip) >> 2;
242 				ip += 2;
243 			} else if (t >= 16) {
244 				m_pos = op;
245 				m_pos -= (t & 8) << 11;
246 
247 				t &= 7;
248 				if (t == 0) {
249 					if (HAVE_IP(1, ip_end, ip))
250 						goto input_overrun;
251 					while (*ip == 0) {
252 						t += 255;
253 						ip++;
254 						if (HAVE_IP(1, ip_end, ip))
255 							goto input_overrun;
256 					}
257 					t += 7 + *ip++;
258 				}
259 				m_pos -= get_unaligned_le16(ip) >> 2;
260 				ip += 2;
261 				if (m_pos == op)
262 					goto eof_found;
263 				m_pos -= 0x4000;
264 			} else {
265 				m_pos = op - 1;
266 				m_pos -= t >> 2;
267 				m_pos -= *ip++ << 2;
268 
269 				if (HAVE_LB(m_pos, out, op))
270 					goto lookbehind_overrun;
271 				if (HAVE_OP(2, op_end, op))
272 					goto output_overrun;
273 
274 				*op++ = *m_pos++;
275 				*op++ = *m_pos;
276 				goto match_done;
277 			}
278 
279 			if (HAVE_LB(m_pos, out, op))
280 				goto lookbehind_overrun;
281 			if (HAVE_OP(t + 3 - 1, op_end, op))
282 				goto output_overrun;
283 
284 			if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
285 				COPY4(op, m_pos);
286 				op += 4;
287 				m_pos += 4;
288 				t -= 4 - (3 - 1);
289 				do {
290 					COPY4(op, m_pos);
291 					op += 4;
292 					m_pos += 4;
293 					t -= 4;
294 				} while (t >= 4);
295 				if (t > 0)
296 					do {
297 						*op++ = *m_pos++;
298 					} while (--t > 0);
299 			} else {
300 copy_match:
301 				*op++ = *m_pos++;
302 				*op++ = *m_pos++;
303 				do {
304 					*op++ = *m_pos++;
305 				} while (--t > 0);
306 			}
307 match_done:
308 			t = ip[-2] & 3;
309 			if (t == 0)
310 				break;
311 match_next:
312 			if (HAVE_OP(t, op_end, op))
313 				goto output_overrun;
314 			if (HAVE_IP(t + 1, ip_end, ip))
315 				goto input_overrun;
316 
317 			*op++ = *ip++;
318 			if (t > 1) {
319 				*op++ = *ip++;
320 				if (t > 2)
321 					*op++ = *ip++;
322 			}
323 
324 			t = *ip++;
325 		} while (ip < ip_end);
326 	}
327 
328 	*out_len = op - out;
329 	return LZO_E_EOF_NOT_FOUND;
330 
331 eof_found:
332 	*out_len = op - out;
333 	return (ip == ip_end ? LZO_E_OK :
334 		(ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
335 input_overrun:
336 	*out_len = op - out;
337 	return LZO_E_INPUT_OVERRUN;
338 
339 output_overrun:
340 	*out_len = op - out;
341 	return LZO_E_OUTPUT_OVERRUN;
342 
343 lookbehind_overrun:
344 	*out_len = op - out;
345 	return LZO_E_LOOKBEHIND_OVERRUN;
346 }
347