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