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 LZ4_ARCH64
144			if ((ref + COPYLENGTH) > oend)
145#else
146			if ((ref + COPYLENGTH) > oend ||
147					(op + COPYLENGTH) > oend)
148#endif
149				goto _output_error;
150			LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
151			while (op < cpy)
152				*op++ = *ref++;
153			op = cpy;
154			/*
155			 * Check EOF (should never happen, since last 5 bytes
156			 * are supposed to be literals)
157			 */
158			if (op == oend)
159				goto _output_error;
160			continue;
161		}
162		LZ4_SECURECOPY(ref, op, cpy);
163		op = cpy; /* correction */
164	}
165	/* end of decoding */
166	return (int) (((char *)ip) - source);
167
168	/* write overflow error detected */
169_output_error:
170	return -1;
171}
172
173static int lz4_uncompress_unknownoutputsize(const char *source, char *dest,
174				int isize, size_t maxoutputsize)
175{
176	const BYTE *ip = (const BYTE *) source;
177	const BYTE *const iend = ip + isize;
178	const BYTE *ref;
179
180
181	BYTE *op = (BYTE *) dest;
182	BYTE * const oend = op + maxoutputsize;
183	BYTE *cpy;
184
185	/* Main Loop */
186	while (ip < iend) {
187
188		unsigned token;
189		size_t length;
190
191		/* get runlength */
192		token = *ip++;
193		length = (token >> ML_BITS);
194		if (length == RUN_MASK) {
195			int s = 255;
196			while ((ip < iend) && (s == 255)) {
197				s = *ip++;
198				if (unlikely(length > (size_t)(length + s)))
199					goto _output_error;
200				length += s;
201			}
202		}
203		/* copy literals */
204		cpy = op + length;
205		if ((cpy > oend - COPYLENGTH) ||
206			(ip + length > iend - COPYLENGTH)) {
207
208			if (cpy > oend)
209				goto _output_error;/* writes beyond buffer */
210
211			if (ip + length != iend)
212				goto _output_error;/*
213						    * Error: LZ4 format requires
214						    * to consume all input
215						    * at this stage
216						    */
217			memcpy(op, ip, length);
218			op += length;
219			break;/* Necessarily EOF, due to parsing restrictions */
220		}
221		LZ4_WILDCOPY(ip, op, cpy);
222		ip -= (op - cpy);
223		op = cpy;
224
225		/* get offset */
226		LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
227		ip += 2;
228		if (ref < (BYTE * const) dest)
229			goto _output_error;
230			/*
231			 * Error : offset creates reference
232			 * outside of destination buffer
233			 */
234
235		/* get matchlength */
236		length = (token & ML_MASK);
237		if (length == ML_MASK) {
238			while (ip < iend) {
239				int s = *ip++;
240				if (unlikely(length > (size_t)(length + s)))
241					goto _output_error;
242				length += s;
243				if (s == 255)
244					continue;
245				break;
246			}
247		}
248
249		/* copy repeated sequence */
250		if (unlikely((op - ref) < STEPSIZE)) {
251#if LZ4_ARCH64
252			int dec64 = dec64table[op - ref];
253#else
254			const int dec64 = 0;
255#endif
256				op[0] = ref[0];
257				op[1] = ref[1];
258				op[2] = ref[2];
259				op[3] = ref[3];
260				op += 4;
261				ref += 4;
262				ref -= dec32table[op - ref];
263				PUT4(ref, op);
264				op += STEPSIZE - 4;
265				ref -= dec64;
266		} else {
267			LZ4_COPYSTEP(ref, op);
268		}
269		cpy = op + length - (STEPSIZE-4);
270		if (cpy > oend - COPYLENGTH) {
271			if (cpy > oend)
272				goto _output_error; /* write outside of buf */
273#if LZ4_ARCH64
274			if ((ref + COPYLENGTH) > oend)
275#else
276			if ((ref + COPYLENGTH) > oend ||
277					(op + COPYLENGTH) > oend)
278#endif
279				goto _output_error;
280			LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
281			while (op < cpy)
282				*op++ = *ref++;
283			op = cpy;
284			/*
285			 * Check EOF (should never happen, since last 5 bytes
286			 * are supposed to be literals)
287			 */
288			if (op == oend)
289				goto _output_error;
290			continue;
291		}
292		LZ4_SECURECOPY(ref, op, cpy);
293		op = cpy; /* correction */
294	}
295	/* end of decoding */
296	return (int) (((char *) op) - dest);
297
298	/* write overflow error detected */
299_output_error:
300	return -1;
301}
302
303int lz4_decompress(const unsigned char *src, size_t *src_len,
304		unsigned char *dest, size_t actual_dest_len)
305{
306	int ret = -1;
307	int input_len = 0;
308
309	input_len = lz4_uncompress(src, dest, actual_dest_len);
310	if (input_len < 0)
311		goto exit_0;
312	*src_len = input_len;
313
314	return 0;
315exit_0:
316	return ret;
317}
318#ifndef STATIC
319EXPORT_SYMBOL(lz4_decompress);
320#endif
321
322int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len,
323		unsigned char *dest, size_t *dest_len)
324{
325	int ret = -1;
326	int out_len = 0;
327
328	out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len,
329					*dest_len);
330	if (out_len < 0)
331		goto exit_0;
332	*dest_len = out_len;
333
334	return 0;
335exit_0:
336	return ret;
337}
338#ifndef STATIC
339EXPORT_SYMBOL(lz4_decompress_unknownoutputsize);
340
341MODULE_LICENSE("Dual BSD/GPL");
342MODULE_DESCRIPTION("LZ4 Decompressor");
343#endif