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#ifndef STATIC
 15#include <linux/module.h>
 16#include <linux/kernel.h>
 17#endif
 18
 19#include <asm/unaligned.h>
 20#include <linux/lzo.h>
 21#include "lzodefs.h"
 22
 23#define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
 24#define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
 25#define HAVE_LB(m_pos, out, op) (m_pos < out || m_pos >= op)
 26
 27#define COPY4(dst, src)	\
 28		put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
 29
 30int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
 31			unsigned char *out, size_t *out_len)
 32{
 33	const unsigned char * const ip_end = in + in_len;
 34	unsigned char * const op_end = out + *out_len;
 35	const unsigned char *ip = in, *m_pos;
 36	unsigned char *op = out;
 37	size_t t;
 38
 39	*out_len = 0;
 40
 41	if (*ip > 17) {
 42		t = *ip++ - 17;
 43		if (t < 4)
 44			goto match_next;
 45		if (HAVE_OP(t, op_end, op))
 46			goto output_overrun;
 47		if (HAVE_IP(t + 1, ip_end, ip))
 48			goto input_overrun;
 49		do {
 50			*op++ = *ip++;
 51		} while (--t > 0);
 52		goto first_literal_run;
 53	}
 54
 55	while ((ip < ip_end)) {
 56		t = *ip++;
 57		if (t >= 16)
 58			goto match;
 59		if (t == 0) {
 60			if (HAVE_IP(1, ip_end, ip))
 61				goto input_overrun;
 62			while (*ip == 0) {
 63				t += 255;
 64				ip++;
 65				if (HAVE_IP(1, ip_end, ip))
 66					goto input_overrun;
 67			}
 68			t += 15 + *ip++;
 69		}
 70		if (HAVE_OP(t + 3, op_end, op))
 71			goto output_overrun;
 72		if (HAVE_IP(t + 4, ip_end, ip))
 73			goto input_overrun;
 74
 75		COPY4(op, ip);
 76		op += 4;
 77		ip += 4;
 78		if (--t > 0) {
 79			if (t >= 4) {
 80				do {
 81					COPY4(op, ip);
 82					op += 4;
 83					ip += 4;
 84					t -= 4;
 85				} while (t >= 4);
 86				if (t > 0) {
 87					do {
 88						*op++ = *ip++;
 89					} while (--t > 0);
 90				}
 91			} else {
 92				do {
 93					*op++ = *ip++;
 94				} while (--t > 0);
 95			}
 96		}
 97
 98first_literal_run:
 99		t = *ip++;
100		if (t >= 16)
101			goto match;
102		m_pos = op - (1 + M2_MAX_OFFSET);
103		m_pos -= t >> 2;
104		m_pos -= *ip++ << 2;
105
106		if (HAVE_LB(m_pos, out, op))
107			goto lookbehind_overrun;
108
109		if (HAVE_OP(3, op_end, op))
110			goto output_overrun;
111		*op++ = *m_pos++;
112		*op++ = *m_pos++;
113		*op++ = *m_pos;
114
115		goto match_done;
116
117		do {
118match:
119			if (t >= 64) {
120				m_pos = op - 1;
121				m_pos -= (t >> 2) & 7;
122				m_pos -= *ip++ << 3;
123				t = (t >> 5) - 1;
124				if (HAVE_LB(m_pos, out, op))
125					goto lookbehind_overrun;
126				if (HAVE_OP(t + 3 - 1, op_end, op))
127					goto output_overrun;
128				goto copy_match;
129			} else if (t >= 32) {
130				t &= 31;
131				if (t == 0) {
132					if (HAVE_IP(1, ip_end, ip))
133						goto input_overrun;
134					while (*ip == 0) {
135						t += 255;
136						ip++;
137						if (HAVE_IP(1, ip_end, ip))
138							goto input_overrun;
139					}
140					t += 31 + *ip++;
141				}
142				m_pos = op - 1;
143				m_pos -= get_unaligned_le16(ip) >> 2;
144				ip += 2;
145			} else if (t >= 16) {
146				m_pos = op;
147				m_pos -= (t & 8) << 11;
148
149				t &= 7;
150				if (t == 0) {
151					if (HAVE_IP(1, ip_end, ip))
152						goto input_overrun;
153					while (*ip == 0) {
154						t += 255;
155						ip++;
156						if (HAVE_IP(1, ip_end, ip))
157							goto input_overrun;
158					}
159					t += 7 + *ip++;
160				}
161				m_pos -= get_unaligned_le16(ip) >> 2;
162				ip += 2;
163				if (m_pos == op)
164					goto eof_found;
165				m_pos -= 0x4000;
166			} else {
167				m_pos = op - 1;
168				m_pos -= t >> 2;
169				m_pos -= *ip++ << 2;
170
171				if (HAVE_LB(m_pos, out, op))
172					goto lookbehind_overrun;
173				if (HAVE_OP(2, op_end, op))
174					goto output_overrun;
175
176				*op++ = *m_pos++;
177				*op++ = *m_pos;
178				goto match_done;
179			}
180
181			if (HAVE_LB(m_pos, out, op))
182				goto lookbehind_overrun;
183			if (HAVE_OP(t + 3 - 1, op_end, op))
184				goto output_overrun;
185
186			if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
187				COPY4(op, m_pos);
188				op += 4;
189				m_pos += 4;
190				t -= 4 - (3 - 1);
191				do {
192					COPY4(op, m_pos);
193					op += 4;
194					m_pos += 4;
195					t -= 4;
196				} while (t >= 4);
197				if (t > 0)
198					do {
199						*op++ = *m_pos++;
200					} while (--t > 0);
201			} else {
202copy_match:
203				*op++ = *m_pos++;
204				*op++ = *m_pos++;
205				do {
206					*op++ = *m_pos++;
207				} while (--t > 0);
208			}
209match_done:
210			t = ip[-2] & 3;
211			if (t == 0)
212				break;
213match_next:
214			if (HAVE_OP(t, op_end, op))
215				goto output_overrun;
216			if (HAVE_IP(t + 1, ip_end, ip))
217				goto input_overrun;
218
219			*op++ = *ip++;
220			if (t > 1) {
221				*op++ = *ip++;
222				if (t > 2)
223					*op++ = *ip++;
224			}
225
226			t = *ip++;
227		} while (ip < ip_end);
228	}
229
230	*out_len = op - out;
231	return LZO_E_EOF_NOT_FOUND;
232
233eof_found:
234	*out_len = op - out;
235	return (ip == ip_end ? LZO_E_OK :
236		(ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
237input_overrun:
238	*out_len = op - out;
239	return LZO_E_INPUT_OVERRUN;
240
241output_overrun:
242	*out_len = op - out;
243	return LZO_E_OUTPUT_OVERRUN;
244
245lookbehind_overrun:
246	*out_len = op - out;
247	return LZO_E_LOOKBEHIND_OVERRUN;
248}
249#ifndef STATIC
250EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
251
252MODULE_LICENSE("GPL");
253MODULE_DESCRIPTION("LZO1X Decompressor");
254
255#endif