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 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
 161 static 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
 286 int lz4_decompress(const char *src, size_t *src_len, char *dest,
 287                 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;
 298 exit_0:
 299         return ret;
 300 }
 301 #ifndef STATIC
 302 EXPORT_SYMBOL_GPL(lz4_decompress);
 303 #endif
 304
 305 int lz4_decompress_unknownoutputsize(const char *src, size_t src_len,
 306                 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;
 318 exit_0:
 319         return ret;
 320 }
 321 #ifndef STATIC
 322 EXPORT_SYMBOL_GPL(lz4_decompress_unknownoutputsize);
 323
 324 MODULE_LICENSE("GPL");
 325 MODULE_DESCRIPTION("LZ4 Decompressor");
 326 #endif