xref: /openbmc/u-boot/lib/lzo/lzo1x_decompress.c (revision 1a459660) 
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;
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 
113 int 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 
181 first_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 {
201 match:
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 {
285 copy_match:
286 				*op++ = *m_pos++;
287 				*op++ = *m_pos++;
288 				do {
289 					*op++ = *m_pos++;
290 				} while (--t > 0);
291 			}
292 match_done:
293 			t = ip[-2] & 3;
294 			if (t == 0)
295 				break;
296 match_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 
316 eof_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));
320 input_overrun:
321 	*out_len = op - out;
322 	return LZO_E_INPUT_OVERRUN;
323 
324 output_overrun:
325 	*out_len = op - out;
326 	return LZO_E_OUTPUT_OVERRUN;
327 
328 lookbehind_overrun:
329 	*out_len = op - out;
330 	return LZO_E_LOOKBEHIND_OVERRUN;
331 }
332