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