lib/lz4/lz4_decompress.c

   1 /*
   2  * LZ4 - Fast LZ compression algorithm
   3  * Copyright (C) 2011 - 2016, Yann Collet.
   4  * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php)
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *      * Redistributions of source code must retain the above copyright
   9  *        notice, this list of conditions and the following disclaimer.
  10  *      * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  15  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  16  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  17  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  18  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  19  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  20  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  * You can contact the author at :
  26  *      - LZ4 homepage : http://www.lz4.org
  27  *      - LZ4 source repository : https://github.com/lz4/lz4
  28  *
  29  *      Changed for kernel usage by:
  30  *      Sven Schmidt <4sschmid@informatik.uni-hamburg.de>
  31  */
  32
  33 /*-************************************
  34  *      Dependencies
  35  **************************************/
  36 #include <linux/lz4.h>
  37 #include "lz4defs.h"
  38 #include <linux/init.h>
  39 #include <linux/module.h>
  40 #include <linux/kernel.h>
  41 #include <asm/unaligned.h>
  42
  43 /*-*****************************
  44  *      Decompression functions
  45  *******************************/
  46 /* LZ4_decompress_generic() :
  47  * This generic decompression function cover all use cases.
  48  * It shall be instantiated several times, using different sets of directives
  49  * Note that it is important this generic function is really inlined,
  50  * in order to remove useless branches during compilation optimization.
  51  */
  52 static FORCE_INLINE int LZ4_decompress_generic(
  53          const char * const source,
  54          char * const dest,
  55          int inputSize,
  56                 /*
  57                  * If endOnInput == endOnInputSize,
  58                  * this value is the max size of Output Buffer.
  59                  */
  60          int outputSize,
  61          /* endOnOutputSize, endOnInputSize */
  62          int endOnInput,
  63          /* full, partial */
  64          int partialDecoding,
  65          /* only used if partialDecoding == partial */
  66          int targetOutputSize,
  67          /* noDict, withPrefix64k, usingExtDict */
  68          int dict,
  69          /* == dest when no prefix */
  70          const BYTE * const lowPrefix,
  71          /* only if dict == usingExtDict */
  72          const BYTE * const dictStart,
  73          /* note : = 0 if noDict */
  74          const size_t dictSize
  75          )
  76 {
  77         /* Local Variables */
  78         const BYTE *ip = (const BYTE *) source;
  79         const BYTE * const iend = ip + inputSize;
  80
  81         BYTE *op = (BYTE *) dest;
  82         BYTE * const oend = op + outputSize;
  83         BYTE *cpy;
  84         BYTE *oexit = op + targetOutputSize;
  85         const BYTE * const lowLimit = lowPrefix - dictSize;
  86
  87         const BYTE * const dictEnd = (const BYTE *)dictStart + dictSize;
  88         static const unsigned int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };
  89         static const int dec64table[] = { 0, 0, 0, -1, 0, 1, 2, 3 };
  90
  91         const int safeDecode = (endOnInput == endOnInputSize);
  92         const int checkOffset = ((safeDecode) && (dictSize < (int)(64 * KB)));
  93
  94         /* Special cases */
  95         /* targetOutputSize too high => decode everything */
  96         if ((partialDecoding) && (oexit > oend - MFLIMIT))
  97                 oexit = oend - MFLIMIT;
  98
  99         /* Empty output buffer */
 100         if ((endOnInput) && (unlikely(outputSize == 0)))
 101                 return ((inputSize == 1) && (*ip == 0)) ? 0 : -1;
 102
 103         if ((!endOnInput) && (unlikely(outputSize == 0)))
 104                 return (*ip == 0 ? 1 : -1);
 105
 106         /* Main Loop : decode sequences */
 107         while (1) {
 108                 size_t length;
 109                 const BYTE *match;
 110                 size_t offset;
 111
 112                 /* get literal length */
 113                 unsigned int const token = *ip++;
 114
 115                 length = token>>ML_BITS;
 116
 117                 if (length == RUN_MASK) {
 118                         unsigned int s;
 119
 120                         do {
 121                                 s = *ip++;
 122                                 length += s;
 123                         } while (likely(endOnInput
 124                                 ? ip < iend - RUN_MASK
 125                                 : 1) & (s == 255));
 126
 127                         if ((safeDecode)
 128                                 && unlikely(
 129                                         (size_t)(op + length) < (size_t)(op))) {
 130                                 /* overflow detection */
 131                                 goto _output_error;
 132                         }
 133                         if ((safeDecode)
 134                                 && unlikely(
 135                                         (size_t)(ip + length) < (size_t)(ip))) {
 136                                 /* overflow detection */
 137                                 goto _output_error;
 138                         }
 139                 }
 140
 141                 /* copy literals */
 142                 cpy = op + length;
 143                 if (((endOnInput) && ((cpy > (partialDecoding ? oexit : oend - MFLIMIT))
 144                         || (ip + length > iend - (2 + 1 + LASTLITERALS))))
 145                         || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) {
 146                         if (partialDecoding) {
 147                                 if (cpy > oend) {
 148                                         /*
 149                                          * Error :
 150                                          * write attempt beyond end of output buffer
 151                                          */
 152                                         goto _output_error;
 153                                 }
 154                                 if ((endOnInput)
 155                                         && (ip + length > iend)) {
 156                                         /*
 157                                          * Error :
 158                                          * read attempt beyond
 159                                          * end of input buffer
 160                                          */
 161                                         goto _output_error;
 162                                 }
 163                         } else {
 164                                 if ((!endOnInput)
 165                                         && (cpy != oend)) {
 166                                         /*
 167                                          * Error :
 168                                          * block decoding must
 169                                          * stop exactly there
 170                                          */
 171                                         goto _output_error;
 172                                 }
 173                                 if ((endOnInput)
 174                                         && ((ip + length != iend)
 175                                         || (cpy > oend))) {
 176                                         /*
 177                                          * Error :
 178                                          * input must be consumed
 179                                          */
 180                                         goto _output_error;
 181                                 }
 182                         }
 183
 184                         memcpy(op, ip, length);
 185                         ip += length;
 186                         op += length;
 187                         /* Necessarily EOF, due to parsing restrictions */
 188                         break;
 189                 }
 190
 191                 LZ4_wildCopy(op, ip, cpy);
 192                 ip += length;
 193                 op = cpy;
 194
 195                 /* get offset */
 196                 offset = LZ4_readLE16(ip);
 197                 ip += 2;
 198                 match = op - offset;
 199
 200                 if ((checkOffset) && (unlikely(match < lowLimit))) {
 201                         /* Error : offset outside buffers */
 202                         goto _output_error;
 203                 }
 204
 205                 /* costs ~1%; silence an msan warning when offset == 0 */
 206                 LZ4_write32(op, (U32)offset);
 207
 208                 /* get matchlength */
 209                 length = token & ML_MASK;
 210                 if (length == ML_MASK) {
 211                         unsigned int s;
 212
 213                         do {
 214                                 s = *ip++;
 215
 216                                 if ((endOnInput) && (ip > iend - LASTLITERALS))
 217                                         goto _output_error;
 218
 219                                 length += s;
 220                         } while (s == 255);
 221
 222                         if ((safeDecode)
 223                                 && unlikely(
 224                                         (size_t)(op + length) < (size_t)op)) {
 225                                 /* overflow detection */
 226                                 goto _output_error;
 227                         }
 228                 }
 229
 230                 length += MINMATCH;
 231
 232                 /* check external dictionary */
 233                 if ((dict == usingExtDict) && (match < lowPrefix)) {
 234                         if (unlikely(op + length > oend - LASTLITERALS)) {
 235                                 /* doesn't respect parsing restriction */
 236                                 goto _output_error;
 237                         }
 238
 239                         if (length <= (size_t)(lowPrefix - match)) {
 240                                 /*
 241                                  * match can be copied as a single segment
 242                                  * from external dictionary
 243                                  */
 244                                 memmove(op, dictEnd - (lowPrefix - match),
 245                                         length);
 246                                 op += length;
 247                         } else {
 248                                 /*
 249                                  * match encompass external
 250                                  * dictionary and current block
 251                                  */
 252                                 size_t const copySize = (size_t)(lowPrefix - match);
 253                                 size_t const restSize = length - copySize;
 254
 255                                 memcpy(op, dictEnd - copySize, copySize);
 256                                 op += copySize;
 257
 258                                 if (restSize > (size_t)(op - lowPrefix)) {
 259                                         /* overlap copy */
 260                                         BYTE * const endOfMatch = op + restSize;
 261                                         const BYTE *copyFrom = lowPrefix;
 262
 263                                         while (op < endOfMatch)
 264                                                 *op++ = *copyFrom++;
 265                                 } else {
 266                                         memcpy(op, lowPrefix, restSize);
 267                                         op += restSize;
 268                                 }
 269                         }
 270
 271                         continue;
 272                 }
 273
 274                 /* copy match within block */
 275                 cpy = op + length;
 276
 277                 if (unlikely(offset < 8)) {
 278                         const int dec64 = dec64table[offset];
 279
 280                         op[0] = match[0];
 281                         op[1] = match[1];
 282                         op[2] = match[2];
 283                         op[3] = match[3];
 284                         match += dec32table[offset];
 285                         memcpy(op + 4, match, 4);
 286                         match -= dec64;
 287                 } else {
 288                         LZ4_copy8(op, match);
 289                         match += 8;
 290                 }
 291
 292                 op += 8;
 293
 294                 if (unlikely(cpy > oend - 12)) {
 295                         BYTE * const oCopyLimit = oend - (WILDCOPYLENGTH - 1);
 296
 297                         if (cpy > oend - LASTLITERALS) {
 298                                 /*
 299                                  * Error : last LASTLITERALS bytes
 300                                  * must be literals (uncompressed)
 301                                  */
 302                                 goto _output_error;
 303                         }
 304
 305                         if (op < oCopyLimit) {
 306                                 LZ4_wildCopy(op, match, oCopyLimit);
 307                                 match += oCopyLimit - op;
 308                                 op = oCopyLimit;
 309                         }
 310
 311                         while (op < cpy)
 312                                 *op++ = *match++;
 313                 } else {
 314                         LZ4_copy8(op, match);
 315
 316                         if (length > 16)
 317                                 LZ4_wildCopy(op + 8, match + 8, cpy);
 318                 }
 319
 320                 op = cpy; /* correction */
 321         }
 322
 323         /* end of decoding */
 324         if (endOnInput) {
 325                 /* Nb of output bytes decoded */
 326                 return (int) (((char *)op) - dest);
 327         } else {
 328                 /* Nb of input bytes read */
 329                 return (int) (((const char *)ip) - source);
 330         }
 331
 332         /* Overflow error detected */
 333 _output_error:
 334         return -1;
 335 }
 336
 337 int LZ4_decompress_safe(const char *source, char *dest,
 338         int compressedSize, int maxDecompressedSize)
 339 {
 340         return LZ4_decompress_generic(source, dest, compressedSize,
 341                 maxDecompressedSize, endOnInputSize, full, 0,
 342                 noDict, (BYTE *)dest, NULL, 0);
 343 }
 344
 345 int LZ4_decompress_safe_partial(const char *source, char *dest,
 346         int compressedSize, int targetOutputSize, int maxDecompressedSize)
 347 {
 348         return LZ4_decompress_generic(source, dest, compressedSize,
 349                 maxDecompressedSize, endOnInputSize, partial,
 350                 targetOutputSize, noDict, (BYTE *)dest, NULL, 0);
 351 }
 352
 353 int LZ4_decompress_fast(const char *source, char *dest, int originalSize)
 354 {
 355         return LZ4_decompress_generic(source, dest, 0, originalSize,
 356                 endOnOutputSize, full, 0, withPrefix64k,
 357                 (BYTE *)(dest - 64 * KB), NULL, 64 * KB);
 358 }
 359
 360 int LZ4_setStreamDecode(LZ4_streamDecode_t *LZ4_streamDecode,
 361         const char *dictionary, int dictSize)
 362 {
 363         LZ4_streamDecode_t_internal *lz4sd = (LZ4_streamDecode_t_internal *) LZ4_streamDecode;
 364
 365         lz4sd->prefixSize = (size_t) dictSize;
 366         lz4sd->prefixEnd = (const BYTE *) dictionary + dictSize;
 367         lz4sd->externalDict = NULL;
 368         lz4sd->extDictSize      = 0;
 369         return 1;
 370 }
 371
 372 /*
 373  * *_continue() :
 374  * These decoding functions allow decompression of multiple blocks
 375  * in "streaming" mode.
 376  * Previously decoded blocks must still be available at the memory
 377  * position where they were decoded.
 378  * If it's not possible, save the relevant part of
 379  * decoded data into a safe buffer,
 380  * and indicate where it stands using LZ4_setStreamDecode()
 381  */
 382 int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode,
 383         const char *source, char *dest, int compressedSize, int maxOutputSize)
 384 {
 385         LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse;
 386         int result;
 387
 388         if (lz4sd->prefixEnd == (BYTE *)dest) {
 389                 result = LZ4_decompress_generic(source, dest,
 390                         compressedSize,
 391                         maxOutputSize,
 392                         endOnInputSize, full, 0,
 393                         usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize,
 394                         lz4sd->externalDict,
 395                         lz4sd->extDictSize);
 396
 397                 if (result <= 0)
 398                         return result;
 399
 400                 lz4sd->prefixSize += result;
 401                 lz4sd->prefixEnd        += result;
 402         } else {
 403                 lz4sd->extDictSize = lz4sd->prefixSize;
 404                 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
 405                 result = LZ4_decompress_generic(source, dest,
 406                         compressedSize, maxOutputSize,
 407                         endOnInputSize, full, 0,
 408                         usingExtDict, (BYTE *)dest,
 409                         lz4sd->externalDict, lz4sd->extDictSize);
 410                 if (result <= 0)
 411                         return result;
 412                 lz4sd->prefixSize = result;
 413                 lz4sd->prefixEnd        = (BYTE *)dest + result;
 414         }
 415
 416         return result;
 417 }
 418
 419 int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode,
 420         const char *source, char *dest, int originalSize)
 421 {
 422         LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse;
 423         int result;
 424
 425         if (lz4sd->prefixEnd == (BYTE *)dest) {
 426                 result = LZ4_decompress_generic(source, dest, 0, originalSize,
 427                         endOnOutputSize, full, 0,
 428                         usingExtDict,
 429                         lz4sd->prefixEnd - lz4sd->prefixSize,
 430                         lz4sd->externalDict, lz4sd->extDictSize);
 431
 432                 if (result <= 0)
 433                         return result;
 434
 435                 lz4sd->prefixSize += originalSize;
 436                 lz4sd->prefixEnd        += originalSize;
 437         } else {
 438                 lz4sd->extDictSize = lz4sd->prefixSize;
 439                 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
 440                 result = LZ4_decompress_generic(source, dest, 0, originalSize,
 441                         endOnOutputSize, full, 0,
 442                         usingExtDict, (BYTE *)dest,
 443                         lz4sd->externalDict, lz4sd->extDictSize);
 444                 if (result <= 0)
 445                         return result;
 446                 lz4sd->prefixSize = originalSize;
 447                 lz4sd->prefixEnd        = (BYTE *)dest + originalSize;
 448         }
 449
 450         return result;
 451 }
 452
 453 /*
 454  * Advanced decoding functions :
 455  * *_usingDict() :
 456  * These decoding functions work the same as "_continue" ones,
 457  * the dictionary must be explicitly provided within parameters
 458  */
 459 static FORCE_INLINE int LZ4_decompress_usingDict_generic(const char *source,
 460         char *dest, int compressedSize, int maxOutputSize, int safe,
 461         const char *dictStart, int dictSize)
 462 {
 463         if (dictSize == 0)
 464                 return LZ4_decompress_generic(source, dest,
 465                         compressedSize, maxOutputSize, safe, full, 0,
 466                         noDict, (BYTE *)dest, NULL, 0);
 467         if (dictStart + dictSize == dest) {
 468                 if (dictSize >= (int)(64 * KB - 1))
 469                         return LZ4_decompress_generic(source, dest,
 470                                 compressedSize, maxOutputSize, safe, full, 0,
 471                                 withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0);
 472                 return LZ4_decompress_generic(source, dest, compressedSize,
 473                         maxOutputSize, safe, full, 0, noDict,
 474                         (BYTE *)dest - dictSize, NULL, 0);
 475         }
 476         return LZ4_decompress_generic(source, dest, compressedSize,
 477                 maxOutputSize, safe, full, 0, usingExtDict,
 478                 (BYTE *)dest, (const BYTE *)dictStart, dictSize);
 479 }
 480
 481 int LZ4_decompress_safe_usingDict(const char *source, char *dest,
 482         int compressedSize, int maxOutputSize,
 483         const char *dictStart, int dictSize)
 484 {
 485         return LZ4_decompress_usingDict_generic(source, dest,
 486                 compressedSize, maxOutputSize, 1, dictStart, dictSize);
 487 }
 488
 489 int LZ4_decompress_fast_usingDict(const char *source, char *dest,
 490         int originalSize, const char *dictStart, int dictSize)
 491 {
 492         return LZ4_decompress_usingDict_generic(source, dest, 0,
 493                 originalSize, 0, dictStart, dictSize);
 494 }
 495
 496 #ifndef STATIC
 497 EXPORT_SYMBOL(LZ4_decompress_safe);
 498 EXPORT_SYMBOL(LZ4_decompress_safe_partial);
 499 EXPORT_SYMBOL(LZ4_decompress_fast);
 500 EXPORT_SYMBOL(LZ4_setStreamDecode);
 501 EXPORT_SYMBOL(LZ4_decompress_safe_continue);
 502 EXPORT_SYMBOL(LZ4_decompress_fast_continue);
 503 EXPORT_SYMBOL(LZ4_decompress_safe_usingDict);
 504 EXPORT_SYMBOL(LZ4_decompress_fast_usingDict);
 505
 506 MODULE_LICENSE("Dual BSD/GPL");
 507 MODULE_DESCRIPTION("LZ4 decompressor");
 508 #endif