1 /*
2 * LZ4 Decompressor for Linux kernel
3 *
4 * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com>
5 *
6 * Based on LZ4 implementation by Yann Collet.
7 *
8 * LZ4 - Fast LZ compression algorithm
9 * Copyright (C) 2011-2012, Yann Collet.
10 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions are
14 * met:
15 *
16 * * Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * * Redistributions in binary form must reproduce the above
19 * copyright notice, this list of conditions and the following disclaimer
20 * in the documentation and/or other materials provided with the
21 * distribution.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 *
35 * You can contact the author at :
36 * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
37 * - LZ4 source repository : http://code.google.com/p/lz4/
38 */
39
40 #include "defs.h"
41
42 static const uint8_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
43 #if LZ4_ARCH64
44 static const int8_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
45 #endif
46
47 #if defined(__XEN__) || defined(__MINIOS__)
48
lz4_uncompress(const unsigned char * source,unsigned char * dest,int osize)49 static int __init lz4_uncompress(const unsigned char *source, unsigned char *dest,
50 int osize)
51 {
52 const BYTE *ip = (const BYTE *) source;
53 const BYTE *ref;
54 BYTE *op = (BYTE *) dest;
55 BYTE * const oend = op + osize;
56 BYTE *cpy;
57 unsigned token;
58 size_t length;
59
60 while (1) {
61
62 /* get runlength */
63 token = *ip++;
64 length = (token >> ML_BITS);
65 if (length == RUN_MASK) {
66 size_t len;
67
68 len = *ip++;
69 for (; len == 255; length += 255)
70 len = *ip++;
71 length += len;
72 }
73
74 /* copy literals */
75 cpy = op + length;
76 if (unlikely(cpy > oend - COPYLENGTH)) {
77 /*
78 * Error: not enough place for another match
79 * (min 4) + 5 literals
80 */
81 if (cpy != oend)
82 goto _output_error;
83
84 memcpy(op, ip, length);
85 ip += length;
86 break; /* EOF */
87 }
88 if (unlikely((unsigned long)cpy < (unsigned long)op))
89 goto _output_error;
90 LZ4_WILDCOPY(ip, op, cpy);
91 ip -= (op - cpy);
92 op = cpy;
93
94 /* get offset */
95 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
96 ip += 2;
97
98 /* Error: offset create reference outside destination buffer */
99 if (unlikely(ref < (BYTE *const) dest))
100 goto _output_error;
101
102 /* get matchlength */
103 length = token & ML_MASK;
104 if (length == ML_MASK) {
105 for (; *ip == 255; length += 255)
106 ip++;
107 length += *ip++;
108 }
109
110 /* copy repeated sequence */
111 if (unlikely((op - ref) < STEPSIZE)) {
112 #if LZ4_ARCH64
113 int dec64 = dec64table[op - ref];
114 #else
115 const int dec64 = 0;
116 #endif
117 op[0] = ref[0];
118 op[1] = ref[1];
119 op[2] = ref[2];
120 op[3] = ref[3];
121 op += 4;
122 ref += 4;
123 ref -= dec32table[op-ref];
124 PUT4(ref, op);
125 op += STEPSIZE - 4;
126 ref -= dec64;
127 } else {
128 LZ4_COPYSTEP(ref, op);
129 }
130 cpy = op + length - (STEPSIZE - 4);
131 if (cpy > (oend - COPYLENGTH)) {
132
133 /* Error: request to write beyond destination buffer */
134 if (cpy > oend)
135 goto _output_error;
136 #if LZ4_ARCH64
137 if ((ref + COPYLENGTH) > oend)
138 #else
139 if ((ref + COPYLENGTH) > oend ||
140 (op + COPYLENGTH) > oend)
141 #endif
142 goto _output_error;
143 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
144 while (op < cpy)
145 *op++ = *ref++;
146 op = cpy;
147 /*
148 * Check EOF (should never happen, since last 5 bytes
149 * are supposed to be literals)
150 */
151 if (op == oend)
152 goto _output_error;
153 continue;
154 }
155 if (unlikely((unsigned long)cpy < (unsigned long)op - (STEPSIZE - 4)))
156 goto _output_error;
157 LZ4_SECURECOPY(ref, op, cpy);
158 op = cpy; /* correction */
159 }
160 /* end of decoding */
161 return (int) (ip - source);
162
163 /* write overflow error detected */
164 _output_error:
165 return (int) (-(ip - source));
166 }
167
168 #else /* defined(__XEN__) || defined(__MINIOS__) */
169
lz4_uncompress_unknownoutputsize(const unsigned char * source,unsigned char * dest,int isize,size_t maxoutputsize)170 static int lz4_uncompress_unknownoutputsize(const unsigned char *source,
171 unsigned char *dest, int isize,
172 size_t maxoutputsize)
173 {
174 const BYTE *ip = (const BYTE *) source;
175 const BYTE *const iend = ip + isize;
176 const BYTE *ref;
177
178
179 BYTE *op = (BYTE *) dest;
180 BYTE * const oend = op + maxoutputsize;
181 BYTE *cpy;
182
183 /* Main Loop */
184 while (ip < iend) {
185
186 unsigned token;
187 size_t length;
188
189 /* get runlength */
190 token = *ip++;
191 length = (token >> ML_BITS);
192 if (length == RUN_MASK) {
193 int s = 255;
194 while ((ip < iend) && (s == 255)) {
195 s = *ip++;
196 length += s;
197 }
198 }
199 /* copy literals */
200 cpy = op + length;
201 if ((cpy > oend - COPYLENGTH) ||
202 (ip + length > iend - COPYLENGTH)) {
203
204 if (cpy > oend)
205 goto _output_error;/* writes beyond buffer */
206
207 if (ip + length != iend)
208 goto _output_error;/*
209 * Error: LZ4 format requires
210 * to consume all input
211 * at this stage
212 */
213 memcpy(op, ip, length);
214 op += length;
215 break;/* Necessarily EOF, due to parsing restrictions */
216 }
217 if (unlikely((unsigned long)cpy < (unsigned long)op))
218 goto _output_error;
219 LZ4_WILDCOPY(ip, op, cpy);
220 ip -= (op - cpy);
221 op = cpy;
222
223 /* get offset */
224 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
225 ip += 2;
226 if (ref < (BYTE * const) dest)
227 goto _output_error;
228 /*
229 * Error : offset creates reference
230 * outside of destination buffer
231 */
232
233 /* get matchlength */
234 length = (token & ML_MASK);
235 if (length == ML_MASK) {
236 while (ip < iend) {
237 int s = *ip++;
238 length += s;
239 if (s == 255)
240 continue;
241 break;
242 }
243 }
244
245 /* copy repeated sequence */
246 if (unlikely((op - ref) < STEPSIZE)) {
247 #if LZ4_ARCH64
248 int dec64 = dec64table[op - ref];
249 #else
250 const int dec64 = 0;
251 #endif
252 op[0] = ref[0];
253 op[1] = ref[1];
254 op[2] = ref[2];
255 op[3] = ref[3];
256 op += 4;
257 ref += 4;
258 ref -= dec32table[op - ref];
259 PUT4(ref, op);
260 op += STEPSIZE - 4;
261 ref -= dec64;
262 } else {
263 LZ4_COPYSTEP(ref, op);
264 }
265 cpy = op + length - (STEPSIZE-4);
266 if (cpy > oend - COPYLENGTH) {
267 if (cpy > oend)
268 goto _output_error; /* write outside of buf */
269 #if LZ4_ARCH64
270 if ((ref + COPYLENGTH) > oend)
271 #else
272 if ((ref + COPYLENGTH) > oend ||
273 (op + COPYLENGTH) > oend)
274 #endif
275 goto _output_error;
276 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
277 while (op < cpy)
278 *op++ = *ref++;
279 op = cpy;
280 /*
281 * Check EOF (should never happen, since last 5 bytes
282 * are supposed to be literals)
283 */
284 if (op == oend)
285 goto _output_error;
286 continue;
287 }
288 if (unlikely((unsigned long)cpy < (unsigned long)op - (STEPSIZE - 4)))
289 goto _output_error;
290 LZ4_SECURECOPY(ref, op, cpy);
291 op = cpy; /* correction */
292 }
293 /* end of decoding */
294 return (int) (op - dest);
295
296 /* write overflow error detected */
297 _output_error:
298 return (int) (-(ip - source));
299 }
300
301 #endif
302
303 #if defined(__XEN__) || defined(__MINIOS__)
304
lz4_decompress(const unsigned char * src,size_t * src_len,unsigned char * dest,size_t actual_dest_len)305 int __init lz4_decompress(const unsigned char *src, size_t *src_len,
306 unsigned char *dest, size_t actual_dest_len)
307 {
308 int ret = -1;
309 int input_len = 0;
310
311 input_len = lz4_uncompress(src, dest, actual_dest_len);
312 if (input_len < 0)
313 goto exit_0;
314 *src_len = input_len;
315
316 return 0;
317 exit_0:
318 return ret;
319 }
320
321 #else /* defined(__XEN__) || defined(__MINIOS__) */
322
lz4_decompress_unknownoutputsize(const unsigned char * src,size_t src_len,unsigned char * dest,size_t * dest_len)323 int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len,
324 unsigned char *dest, size_t *dest_len)
325 {
326 int ret = -1;
327 int out_len = 0;
328
329 out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len,
330 *dest_len);
331 if (out_len < 0)
332 goto exit_0;
333 *dest_len = out_len;
334
335 return 0;
336 exit_0:
337 return ret;
338 }
339
340 #endif
341