blob: df6839e3ce0886a481e8565f8b19d5c71c9b299a [file] [log] [blame]
Kyungsik Leecffb78b2013-07-08 16:01:45 -07001/*
2 * LZ4 Decompressor for Linux kernel
3 *
Kyungsik Leee76e1fd2013-07-08 16:01:46 -07004 * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com>
Kyungsik Leecffb78b2013-07-08 16:01:45 -07005 *
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#ifndef STATIC
41#include <linux/module.h>
42#include <linux/kernel.h>
43#endif
44#include <linux/lz4.h>
45
46#include <asm/unaligned.h>
47
48#include "lz4defs.h"
49
50static int lz4_uncompress(const char *source, char *dest, 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 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
60#if LZ4_ARCH64
61 size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
62#endif
63
64 while (1) {
65
66 /* get runlength */
67 token = *ip++;
68 length = (token >> ML_BITS);
69 if (length == RUN_MASK) {
70 size_t len;
71
72 len = *ip++;
73 for (; len == 255; length += 255)
74 len = *ip++;
75 length += len;
76 }
77
78 /* copy literals */
79 cpy = op + length;
80 if (unlikely(cpy > oend - COPYLENGTH)) {
81 /*
82 * Error: not enough place for another match
83 * (min 4) + 5 literals
84 */
85 if (cpy != oend)
86 goto _output_error;
87
88 memcpy(op, ip, length);
89 ip += length;
90 break; /* EOF */
91 }
92 LZ4_WILDCOPY(ip, op, cpy);
93 ip -= (op - cpy);
94 op = cpy;
95
96 /* get offset */
97 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
98 ip += 2;
99
100 /* Error: offset create reference outside destination buffer */
101 if (unlikely(ref < (BYTE *const) dest))
102 goto _output_error;
103
104 /* get matchlength */
105 length = token & ML_MASK;
106 if (length == ML_MASK) {
107 for (; *ip == 255; length += 255)
108 ip++;
109 length += *ip++;
110 }
111
112 /* copy repeated sequence */
113 if (unlikely((op - ref) < STEPSIZE)) {
114#if LZ4_ARCH64
115 size_t dec64 = dec64table[op - ref];
116#else
117 const int dec64 = 0;
118#endif
119 op[0] = ref[0];
120 op[1] = ref[1];
121 op[2] = ref[2];
122 op[3] = ref[3];
123 op += 4;
124 ref += 4;
125 ref -= dec32table[op-ref];
126 PUT4(ref, op);
127 op += STEPSIZE - 4;
128 ref -= dec64;
129 } else {
130 LZ4_COPYSTEP(ref, op);
131 }
132 cpy = op + length - (STEPSIZE - 4);
133 if (cpy > (oend - COPYLENGTH)) {
134
135 /* Error: request to write beyond destination buffer */
136 if (cpy > 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 LZ4_SECURECOPY(ref, op, cpy);
151 op = cpy; /* correction */
152 }
153 /* end of decoding */
154 return (int) (((char *)ip) - source);
155
156 /* write overflow error detected */
157_output_error:
158 return (int) (-(((char *)ip) - source));
159}
160
161static int lz4_uncompress_unknownoutputsize(const char *source, char *dest,
162 int isize, size_t maxoutputsize)
163{
164 const BYTE *ip = (const BYTE *) source;
165 const BYTE *const iend = ip + isize;
166 const BYTE *ref;
167
168
169 BYTE *op = (BYTE *) dest;
170 BYTE * const oend = op + maxoutputsize;
171 BYTE *cpy;
172
173 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
174#if LZ4_ARCH64
175 size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
176#endif
177
178 /* Main Loop */
179 while (ip < iend) {
180
181 unsigned token;
182 size_t length;
183
184 /* get runlength */
185 token = *ip++;
186 length = (token >> ML_BITS);
187 if (length == RUN_MASK) {
188 int s = 255;
189 while ((ip < iend) && (s == 255)) {
190 s = *ip++;
191 length += s;
192 }
193 }
194 /* copy literals */
195 cpy = op + length;
196 if ((cpy > oend - COPYLENGTH) ||
197 (ip + length > iend - COPYLENGTH)) {
198
199 if (cpy > oend)
200 goto _output_error;/* writes beyond buffer */
201
202 if (ip + length != iend)
203 goto _output_error;/*
204 * Error: LZ4 format requires
205 * to consume all input
206 * at this stage
207 */
208 memcpy(op, ip, length);
209 op += length;
210 break;/* Necessarily EOF, due to parsing restrictions */
211 }
212 LZ4_WILDCOPY(ip, op, cpy);
213 ip -= (op - cpy);
214 op = cpy;
215
216 /* get offset */
217 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
218 ip += 2;
219 if (ref < (BYTE * const) dest)
220 goto _output_error;
221 /*
222 * Error : offset creates reference
223 * outside of destination buffer
224 */
225
226 /* get matchlength */
227 length = (token & ML_MASK);
228 if (length == ML_MASK) {
229 while (ip < iend) {
230 int s = *ip++;
231 length += s;
232 if (s == 255)
233 continue;
234 break;
235 }
236 }
237
238 /* copy repeated sequence */
239 if (unlikely((op - ref) < STEPSIZE)) {
240#if LZ4_ARCH64
241 size_t dec64 = dec64table[op - ref];
242#else
243 const int dec64 = 0;
244#endif
245 op[0] = ref[0];
246 op[1] = ref[1];
247 op[2] = ref[2];
248 op[3] = ref[3];
249 op += 4;
250 ref += 4;
251 ref -= dec32table[op - ref];
252 PUT4(ref, op);
253 op += STEPSIZE - 4;
254 ref -= dec64;
255 } else {
256 LZ4_COPYSTEP(ref, op);
257 }
258 cpy = op + length - (STEPSIZE-4);
259 if (cpy > oend - COPYLENGTH) {
260 if (cpy > oend)
261 goto _output_error; /* write outside of buf */
262
263 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
264 while (op < cpy)
265 *op++ = *ref++;
266 op = cpy;
267 /*
268 * Check EOF (should never happen, since last 5 bytes
269 * are supposed to be literals)
270 */
271 if (op == oend)
272 goto _output_error;
273 continue;
274 }
275 LZ4_SECURECOPY(ref, op, cpy);
276 op = cpy; /* correction */
277 }
278 /* end of decoding */
279 return (int) (((char *) op) - dest);
280
281 /* write overflow error detected */
282_output_error:
283 return (int) (-(((char *) ip) - source));
284}
285
Sergey Senozhatskyb34081f12013-09-11 14:26:32 -0700286int lz4_decompress(const unsigned char *src, size_t *src_len,
287 unsigned char *dest, size_t actual_dest_len)
Kyungsik Leecffb78b2013-07-08 16:01:45 -0700288{
289 int ret = -1;
290 int input_len = 0;
291
292 input_len = lz4_uncompress(src, dest, actual_dest_len);
293 if (input_len < 0)
294 goto exit_0;
295 *src_len = input_len;
296
297 return 0;
298exit_0:
299 return ret;
300}
301#ifndef STATIC
Richard Laageree8a99b2013-08-22 16:35:47 -0700302EXPORT_SYMBOL(lz4_decompress);
Kyungsik Leecffb78b2013-07-08 16:01:45 -0700303#endif
304
Sergey Senozhatskyb34081f12013-09-11 14:26:32 -0700305int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len,
306 unsigned char *dest, size_t *dest_len)
Kyungsik Leecffb78b2013-07-08 16:01:45 -0700307{
308 int ret = -1;
309 int out_len = 0;
310
311 out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len,
312 *dest_len);
313 if (out_len < 0)
314 goto exit_0;
315 *dest_len = out_len;
316
317 return 0;
318exit_0:
319 return ret;
320}
321#ifndef STATIC
Richard Laageree8a99b2013-08-22 16:35:47 -0700322EXPORT_SYMBOL(lz4_decompress_unknownoutputsize);
Kyungsik Leecffb78b2013-07-08 16:01:45 -0700323
Richard Laageree8a99b2013-08-22 16:35:47 -0700324MODULE_LICENSE("Dual BSD/GPL");
Kyungsik Leecffb78b2013-07-08 16:01:45 -0700325MODULE_DESCRIPTION("LZ4 Decompressor");
326#endif