1 /*
2 * lzo.c -- LZO1X Compressor from LZO
3 *
4 * Copyright (C) 1996-2012 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 * Adapted for Xen (files combined and syntactic/header changes) by:
10 * Dan Magenheimer <dan.magenheimer@oracle.com>
11 *
12 */
13
14 /*
15 * lzodefs.h -- architecture, OS and compiler specific defines
16 *
17 * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
18 *
19 * The full LZO package can be found at:
20 * http://www.oberhumer.com/opensource/lzo/
21 *
22 * Changed for Linux kernel use by:
23 * Nitin Gupta <nitingupta910@gmail.com>
24 * Richard Purdie <rpurdie@openedhand.com>
25 */
26
27
28 #define COPY4(dst, src) memcpy(dst, src, 4)
29 #define COPY8(dst, src) memcpy(dst, src, 8)
30
31 #define M1_MAX_OFFSET 0x0400
32 #define M2_MAX_OFFSET 0x0800
33 #define M3_MAX_OFFSET 0x4000
34 #define M4_MAX_OFFSET 0xbfff
35
36 #define M1_MIN_LEN 2
37 #define M1_MAX_LEN 2
38 #define M2_MIN_LEN 3
39 #define M2_MAX_LEN 8
40 #define M3_MIN_LEN 3
41 #define M3_MAX_LEN 33
42 #define M4_MIN_LEN 3
43 #define M4_MAX_LEN 9
44
45 #define M1_MARKER 0
46 #define M2_MARKER 64
47 #define M3_MARKER 32
48 #define M4_MARKER 16
49
50 #define lzo_dict_t unsigned short
51 #define D_BITS 13
52 #define D_SIZE (1u << D_BITS)
53 #define D_MASK (D_SIZE - 1)
54 #define D_HIGH ((D_MASK >> 1) + 1)
55
56 /*
57 * LZO1X Compressor from LZO
58 *
59 * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
60 *
61 * The full LZO package can be found at:
62 * http://www.oberhumer.com/opensource/lzo/
63 *
64 * Changed for Linux kernel use by:
65 * Nitin Gupta <nitingupta910@gmail.com>
66 * Richard Purdie <rpurdie@openedhand.com>
67 */
68
69 #ifdef __XEN__
70 #include <xen/lib.h>
71 #include <xen/unaligned.h>
72 #else
73 #define get_unaligned_le16(_p) (*(u16 *)(_p))
74 #endif
75
76 #include <xen/lzo.h>
77
78 #include "decompress.h"
79
80 /*
81 * LZO1X Decompressor from LZO
82 *
83 * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
84 *
85 * The full LZO package can be found at:
86 * http://www.oberhumer.com/opensource/lzo/
87 *
88 * Changed for Linux kernel use by:
89 * Nitin Gupta <nitingupta910@gmail.com>
90 * Richard Purdie <rpurdie@openedhand.com>
91 */
92
93 #define HAVE_IP(x) ((size_t)(ip_end - ip) >= (size_t)(x))
94 #define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x))
95 #define NEED_IP(x) if (!HAVE_IP(x)) goto input_overrun
96 #define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun
97 #define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun
98
99 /* This MAX_255_COUNT is the maximum number of times we can add 255 to a base
100 * count without overflowing an integer. The multiply will overflow when
101 * multiplying 255 by more than MAXINT/255. The sum will overflow earlier
102 * depending on the base count. Since the base count is taken from a u8
103 * and a few bits, it is safe to assume that it will always be lower than
104 * or equal to 2*255, thus we can always prevent any overflow by accepting
105 * two less 255 steps. See Documentation/lzo.txt for more information.
106 */
107 #define MAX_255_COUNT ((((size_t)~0) / 255) - 2)
108
lzo1x_decompress_safe(const unsigned char * in,size_t in_len,unsigned char * out,size_t * out_len)109 int __init lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
110 unsigned char *out, size_t *out_len)
111 {
112 unsigned char *op;
113 const unsigned char *ip;
114 size_t t, next;
115 size_t state = 0;
116 const unsigned char *m_pos;
117 const unsigned char * const ip_end = in + in_len;
118 unsigned char * const op_end = out + *out_len;
119
120 op = out;
121 ip = in;
122
123 if (unlikely(in_len < 3))
124 goto input_overrun;
125 if (*ip > 17) {
126 t = *ip++ - 17;
127 if (t < 4) {
128 next = t;
129 goto match_next;
130 }
131 goto copy_literal_run;
132 }
133
134 for (;;) {
135 t = *ip++;
136 if (t < 16) {
137 if (likely(state == 0)) {
138 if (unlikely(t == 0)) {
139 size_t offset;
140 const unsigned char *ip_last = ip;
141
142 while (unlikely(*ip == 0)) {
143 ip++;
144 NEED_IP(1);
145 }
146 offset = ip - ip_last;
147 if (unlikely(offset > MAX_255_COUNT))
148 return LZO_E_ERROR;
149
150 offset = (offset << 8) - offset;
151 t += offset + 15 + *ip++;
152 }
153 t += 3;
154 copy_literal_run:
155 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
156 if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {
157 const unsigned char *ie = ip + t;
158 unsigned char *oe = op + t;
159 do {
160 COPY8(op, ip);
161 op += 8;
162 ip += 8;
163 COPY8(op, ip);
164 op += 8;
165 ip += 8;
166 } while (ip < ie);
167 ip = ie;
168 op = oe;
169 } else
170 #endif
171 {
172 NEED_OP(t);
173 NEED_IP(t + 3);
174 do {
175 *op++ = *ip++;
176 } while (--t > 0);
177 }
178 state = 4;
179 continue;
180 } else if (state != 4) {
181 next = t & 3;
182 m_pos = op - 1;
183 m_pos -= t >> 2;
184 m_pos -= *ip++ << 2;
185 TEST_LB(m_pos);
186 NEED_OP(2);
187 op[0] = m_pos[0];
188 op[1] = m_pos[1];
189 op += 2;
190 goto match_next;
191 } else {
192 next = t & 3;
193 m_pos = op - (1 + M2_MAX_OFFSET);
194 m_pos -= t >> 2;
195 m_pos -= *ip++ << 2;
196 t = 3;
197 }
198 } else if (t >= 64) {
199 next = t & 3;
200 m_pos = op - 1;
201 m_pos -= (t >> 2) & 7;
202 m_pos -= *ip++ << 3;
203 t = (t >> 5) - 1 + (3 - 1);
204 } else if (t >= 32) {
205 t = (t & 31) + (3 - 1);
206 if (unlikely(t == 2)) {
207 size_t offset;
208 const unsigned char *ip_last = ip;
209
210 while (unlikely(*ip == 0)) {
211 ip++;
212 NEED_IP(1);
213 }
214 offset = ip - ip_last;
215 if (unlikely(offset > MAX_255_COUNT))
216 return LZO_E_ERROR;
217
218 offset = (offset << 8) - offset;
219 t += offset + 31 + *ip++;
220 NEED_IP(2);
221 }
222 m_pos = op - 1;
223 next = get_unaligned_le16(ip);
224 ip += 2;
225 m_pos -= next >> 2;
226 next &= 3;
227 } else {
228 m_pos = op;
229 m_pos -= (t & 8) << 11;
230 t = (t & 7) + (3 - 1);
231 if (unlikely(t == 2)) {
232 size_t offset;
233 const unsigned char *ip_last = ip;
234
235 while (unlikely(*ip == 0)) {
236 ip++;
237 NEED_IP(1);
238 }
239 offset = ip - ip_last;
240 if (unlikely(offset > MAX_255_COUNT))
241 return LZO_E_ERROR;
242
243 offset = (offset << 8) - offset;
244 t += offset + 7 + *ip++;
245 NEED_IP(2);
246 }
247 next = get_unaligned_le16(ip);
248 ip += 2;
249 m_pos -= next >> 2;
250 next &= 3;
251 if (m_pos == op)
252 goto eof_found;
253 m_pos -= 0x4000;
254 }
255 TEST_LB(m_pos);
256 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
257 if (op - m_pos >= 8) {
258 unsigned char *oe = op + t;
259 if (likely(HAVE_OP(t + 15))) {
260 do {
261 COPY8(op, m_pos);
262 op += 8;
263 m_pos += 8;
264 COPY8(op, m_pos);
265 op += 8;
266 m_pos += 8;
267 } while (op < oe);
268 op = oe;
269 if (HAVE_IP(6)) {
270 state = next;
271 COPY4(op, ip);
272 op += next;
273 ip += next;
274 continue;
275 }
276 } else {
277 NEED_OP(t);
278 do {
279 *op++ = *m_pos++;
280 } while (op < oe);
281 }
282 } else
283 #endif
284 {
285 unsigned char *oe = op + t;
286 NEED_OP(t);
287 op[0] = m_pos[0];
288 op[1] = m_pos[1];
289 op += 2;
290 m_pos += 2;
291 do {
292 *op++ = *m_pos++;
293 } while (op < oe);
294 }
295 match_next:
296 state = next;
297 t = next;
298 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
299 if (likely(HAVE_IP(6) && HAVE_OP(4))) {
300 COPY4(op, ip);
301 op += t;
302 ip += t;
303 } else
304 #endif
305 {
306 NEED_IP(t + 3);
307 NEED_OP(t);
308 while (t > 0) {
309 *op++ = *ip++;
310 t--;
311 }
312 }
313 }
314
315 eof_found:
316 *out_len = op - out;
317 return (t != 3 ? LZO_E_ERROR :
318 ip == ip_end ? LZO_E_OK :
319 ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN);
320
321 input_overrun:
322 *out_len = op - out;
323 return LZO_E_INPUT_OVERRUN;
324
325 output_overrun:
326 *out_len = op - out;
327 return LZO_E_OUTPUT_OVERRUN;
328
329 lookbehind_overrun:
330 *out_len = op - out;
331 return LZO_E_LOOKBEHIND_OVERRUN;
332 }
333