Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/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
344 

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us