GNU Linux-libre 4.4.284-gnu1
[releases.git] / lib / lz4 / lz4_decompress.c
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
50 static const int dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
51 #if LZ4_ARCH64
52 static const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
53 #endif
54
55 static 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
173 static 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
303 int 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;
315 exit_0:
316         return ret;
317 }
318 #ifndef STATIC
319 EXPORT_SYMBOL(lz4_decompress);
320 #endif
321
322 int 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;
335 exit_0:
336         return ret;
337 }
338 #ifndef STATIC
339 EXPORT_SYMBOL(lz4_decompress_unknownoutputsize);
340
341 MODULE_LICENSE("Dual BSD/GPL");
342 MODULE_DESCRIPTION("LZ4 Decompressor");
343 #endif