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 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
286int lz4_decompress(const unsigned char *src, size_t *src_len,
287		unsigned char *dest, size_t actual_dest_len)
288{
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
302EXPORT_SYMBOL(lz4_decompress);
303#endif
304
305int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len,
306		unsigned char *dest, size_t *dest_len)
307{
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
322EXPORT_SYMBOL(lz4_decompress_unknownoutputsize);
323
324MODULE_LICENSE("Dual BSD/GPL");
325MODULE_DESCRIPTION("LZ4 Decompressor");
326#endif