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