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 #if defined(__XEN__) || defined(__MINIOS__)
43
lz4_uncompress(const unsigned char * source,unsigned char * dest,int osize)44 static int INIT lz4_uncompress(const unsigned char *source, unsigned char *dest,
45 int osize)
46 {
47 const BYTE *ip = (const BYTE *) source;
48 const BYTE *ref;
49 BYTE *op = (BYTE *) dest;
50 BYTE * const oend = op + osize;
51 BYTE *cpy;
52 unsigned token;
53 size_t length;
54 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
55 #if LZ4_ARCH64
56 size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
57 #endif
58
59 while (1) {
60
61 /* get runlength */
62 token = *ip++;
63 length = (token >> ML_BITS);
64 if (length == RUN_MASK) {
65 size_t len;
66
67 len = *ip++;
68 for (; len == 255; length += 255)
69 len = *ip++;
70 length += len;
71 }
72
73 /* copy literals */
74 cpy = op + length;
75 if (unlikely(cpy > oend - COPYLENGTH)) {
76 /*
77 * Error: not enough place for another match
78 * (min 4) + 5 literals
79 */
80 if (cpy != oend)
81 goto _output_error;
82
83 memcpy(op, ip, length);
84 ip += length;
85 break; /* EOF */
86 }
87 if (unlikely((unsigned long)cpy < (unsigned long)op))
88 goto _output_error;
89 LZ4_WILDCOPY(ip, op, cpy);
90 ip -= (op - cpy);
91 op = cpy;
92
93 /* get offset */
94 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
95 ip += 2;
96
97 /* Error: offset create reference outside destination buffer */
98 if (unlikely(ref < (BYTE *const) dest))
99 goto _output_error;
100
101 /* get matchlength */
102 length = token & ML_MASK;
103 if (length == ML_MASK) {
104 for (; *ip == 255; length += 255)
105 ip++;
106 length += *ip++;
107 }
108
109 /* copy repeated sequence */
110 if (unlikely((op - ref) < STEPSIZE)) {
111 #if LZ4_ARCH64
112 size_t dec64 = dec64table[op - ref];
113 #else
114 const int dec64 = 0;
115 #endif
116 op[0] = ref[0];
117 op[1] = ref[1];
118 op[2] = ref[2];
119 op[3] = ref[3];
120 op += 4;
121 ref += 4;
122 ref -= dec32table[op-ref];
123 PUT4(ref, op);
124 op += STEPSIZE - 4;
125 ref -= dec64;
126 } else {
127 LZ4_COPYSTEP(ref, op);
128 }
129 cpy = op + length - (STEPSIZE - 4);
130 if (cpy > (oend - COPYLENGTH)) {
131
132 /* Error: request to write beyond destination buffer */
133 if (cpy > oend)
134 goto _output_error;
135 if ((ref + COPYLENGTH) > oend ||
136 (op + COPYLENGTH) > oend)
137 goto _output_error;
138 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
139 while (op < cpy)
140 *op++ = *ref++;
141 op = cpy;
142 /*
143 * Check EOF (should never happen, since last 5 bytes
144 * are supposed to be literals)
145 */
146 if (op == oend)
147 goto _output_error;
148 continue;
149 }
150 if (unlikely((unsigned long)cpy < (unsigned long)op))
151 goto _output_error;
152 LZ4_SECURECOPY(ref, op, cpy);
153 op = cpy; /* correction */
154 }
155 /* end of decoding */
156 return (int) (ip - source);
157
158 /* write overflow error detected */
159 _output_error:
160 return (int) (-(ip - source));
161 }
162
163 #else /* defined(__XEN__) || defined(__MINIOS__) */
164
lz4_uncompress_unknownoutputsize(const unsigned char * source,unsigned char * dest,int isize,size_t maxoutputsize)165 static int lz4_uncompress_unknownoutputsize(const unsigned char *source,
166 unsigned char *dest, int isize,
167 size_t maxoutputsize)
168 {
169 const BYTE *ip = (const BYTE *) source;
170 const BYTE *const iend = ip + isize;
171 const BYTE *ref;
172
173
174 BYTE *op = (BYTE *) dest;
175 BYTE * const oend = op + maxoutputsize;
176 BYTE *cpy;
177
178 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
179 #if LZ4_ARCH64
180 size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
181 #endif
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 size_t 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
270 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
271 while (op < cpy)
272 *op++ = *ref++;
273 op = cpy;
274 /*
275 * Check EOF (should never happen, since last 5 bytes
276 * are supposed to be literals)
277 */
278 if (op == oend)
279 goto _output_error;
280 continue;
281 }
282 if (unlikely((unsigned long)cpy < (unsigned long)op))
283 goto _output_error;
284 LZ4_SECURECOPY(ref, op, cpy);
285 op = cpy; /* correction */
286 }
287 /* end of decoding */
288 return (int) (op - dest);
289
290 /* write overflow error detected */
291 _output_error:
292 return (int) (-(ip - source));
293 }
294
295 #endif
296
297 #if defined(__XEN__) || defined(__MINIOS__)
298
lz4_decompress(const unsigned char * src,size_t * src_len,unsigned char * dest,size_t actual_dest_len)299 int INIT lz4_decompress(const unsigned char *src, size_t *src_len,
300 unsigned char *dest, size_t actual_dest_len)
301 {
302 int ret = -1;
303 int input_len = 0;
304
305 input_len = lz4_uncompress(src, dest, actual_dest_len);
306 if (input_len < 0)
307 goto exit_0;
308 *src_len = input_len;
309
310 return 0;
311 exit_0:
312 return ret;
313 }
314
315 #else /* defined(__XEN__) || defined(__MINIOS__) */
316
lz4_decompress_unknownoutputsize(const unsigned char * src,size_t src_len,unsigned char * dest,size_t * dest_len)317 int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len,
318 unsigned char *dest, size_t *dest_len)
319 {
320 int ret = -1;
321 int out_len = 0;
322
323 out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len,
324 *dest_len);
325 if (out_len < 0)
326 goto exit_0;
327 *dest_len = out_len;
328
329 return 0;
330 exit_0:
331 return ret;
332 }
333
334 #endif
335