git.sesse.net Git - bcachefs-tools-debian/blob - linux/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/kernel.h>
  39 #include <asm/unaligned.h>
  40
  41 /*-*****************************
  42  *      Decompression functions
  43  *******************************/
  44 /* LZ4_decompress_generic() :
  45  * This generic decompression function cover all use cases.
  46  * It shall be instantiated several times, using different sets of directives
  47  * Note that it is important this generic function is really inlined,
  48  * in order to remove useless branches during compilation optimization.
  49  */
  50 static FORCE_INLINE int LZ4_decompress_generic(
  51          const char * const source,
  52          char * const dest,
  53          int inputSize,
  54                 /*
  55                  * If endOnInput == endOnInputSize,
  56                  * this value is the max size of Output Buffer.
  57                  */
  58          int outputSize,
  59          /* endOnOutputSize, endOnInputSize */
  60          int endOnInput,
  61          /* full, partial */
  62          int partialDecoding,
  63          /* only used if partialDecoding == partial */
  64          int targetOutputSize,
  65          /* noDict, withPrefix64k, usingExtDict */
  66          int dict,
  67          /* == dest when no prefix */
  68          const BYTE * const lowPrefix,
  69          /* only if dict == usingExtDict */
  70          const BYTE * const dictStart,
  71          /* note : = 0 if noDict */
  72          const size_t dictSize
  73          )
  74 {
  75         /* Local Variables */
  76         const BYTE *ip = (const BYTE *) source;
  77         const BYTE * const iend = ip + inputSize;
  78
  79         BYTE *op = (BYTE *) dest;
  80         BYTE * const oend = op + outputSize;
  81         BYTE *cpy;
  82         BYTE *oexit = op + targetOutputSize;
  83         const BYTE * const lowLimit = lowPrefix - dictSize;
  84
  85         const BYTE * const dictEnd = (const BYTE *)dictStart + dictSize;
  86         const unsigned int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };
  87         const int dec64table[] = { 0, 0, 0, -1, 0, 1, 2, 3 };
  88
  89         const int safeDecode = (endOnInput == endOnInputSize);
  90         const int checkOffset = ((safeDecode) && (dictSize < (int)(64 * KB)));
  91
  92         /* Special cases */
  93         /* targetOutputSize too high => decode everything */
  94         if ((partialDecoding) && (oexit > oend - MFLIMIT))
  95                 oexit = oend - MFLIMIT;
  96
  97         /* Empty output buffer */
  98         if ((endOnInput) && (unlikely(outputSize == 0)))
  99                 return ((inputSize == 1) && (*ip == 0)) ? 0 : -1;
 100
 101         if ((!endOnInput) && (unlikely(outputSize == 0)))
 102                 return (*ip == 0 ? 1 : -1);
 103
 104         /* Main Loop : decode sequences */
 105         while (1) {
 106                 size_t length;
 107                 const BYTE *match;
 108                 size_t offset;
 109
 110                 /* get literal length */
 111                 unsigned int const token = *ip++;
 112
 113                 length = token>>ML_BITS;
 114
 115                 if (length == RUN_MASK) {
 116                         unsigned int s;
 117
 118                         do {
 119                                 s = *ip++;
 120                                 length += s;
 121                         } while (likely(endOnInput
 122                                 ? ip < iend - RUN_MASK
 123                                 : 1) & (s == 255));
 124
 125                         if ((safeDecode)
 126                                 && unlikely(
 127                                         (size_t)(op + length) < (size_t)(op))) {
 128                                 /* overflow detection */
 129                                 goto _output_error;
 130                         }
 131                         if ((safeDecode)
 132                                 && unlikely(
 133                                         (size_t)(ip + length) < (size_t)(ip))) {
 134                                 /* overflow detection */
 135                                 goto _output_error;
 136                         }
 137                 }
 138
 139                 /* copy literals */
 140                 cpy = op + length;
 141                 if (((endOnInput) && ((cpy > (partialDecoding ? oexit : oend - MFLIMIT))
 142                         || (ip + length > iend - (2 + 1 + LASTLITERALS))))
 143                         || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) {
 144                         if (partialDecoding) {
 145                                 if (cpy > oend) {
 146                                         /*
 147                                          * Error :
 148                                          * write attempt beyond end of output buffer
 149                                          */
 150                                         goto _output_error;
 151                                 }
 152                                 if ((endOnInput)
 153                                         && (ip + length > iend)) {
 154                                         /*
 155                                          * Error :
 156                                          * read attempt beyond
 157                                          * end of input buffer
 158                                          */
 159                                         goto _output_error;
 160                                 }
 161                         } else {
 162                                 if ((!endOnInput)
 163                                         && (cpy != oend)) {
 164                                         /*
 165                                          * Error :
 166                                          * block decoding must
 167                                          * stop exactly there
 168                                          */
 169                                         goto _output_error;
 170                                 }
 171                                 if ((endOnInput)
 172                                         && ((ip + length != iend)
 173                                         || (cpy > oend))) {
 174                                         /*
 175                                          * Error :
 176                                          * input must be consumed
 177                                          */
 178                                         goto _output_error;
 179                                 }
 180                         }
 181
 182                         memcpy(op, ip, length);
 183                         ip += length;
 184                         op += length;
 185                         /* Necessarily EOF, due to parsing restrictions */
 186                         break;
 187                 }
 188
 189                 LZ4_wildCopy(op, ip, cpy);
 190                 ip += length;
 191                 op = cpy;
 192
 193                 /* get offset */
 194                 offset = LZ4_readLE16(ip);
 195                 ip += 2;
 196                 match = op - offset;
 197
 198                 if ((checkOffset) && (unlikely(match < lowLimit))) {
 199                         /* Error : offset outside buffers */
 200                         goto _output_error;
 201                 }
 202
 203                 /* costs ~1%; silence an msan warning when offset == 0 */
 204                 LZ4_write32(op, (U32)offset);
 205
 206                 /* get matchlength */
 207                 length = token & ML_MASK;
 208                 if (length == ML_MASK) {
 209                         unsigned int s;
 210
 211                         do {
 212                                 s = *ip++;
 213
 214                                 if ((endOnInput) && (ip > iend - LASTLITERALS))
 215                                         goto _output_error;
 216
 217                                 length += s;
 218                         } while (s == 255);
 219
 220                         if ((safeDecode)
 221                                 && unlikely(
 222                                         (size_t)(op + length) < (size_t)op)) {
 223                                 /* overflow detection */
 224                                 goto _output_error;
 225                         }
 226                 }
 227
 228                 length += MINMATCH;
 229
 230                 /* check external dictionary */
 231                 if ((dict == usingExtDict) && (match < lowPrefix)) {
 232                         if (unlikely(op + length > oend - LASTLITERALS)) {
 233                                 /* doesn't respect parsing restriction */
 234                                 goto _output_error;
 235                         }
 236
 237                         if (length <= (size_t)(lowPrefix - match)) {
 238                                 /*
 239                                  * match can be copied as a single segment
 240                                  * from external dictionary
 241                                  */
 242                                 memmove(op, dictEnd - (lowPrefix - match),
 243                                         length);
 244                                 op += length;
 245                         } else {
 246                                 /*
 247                                  * match encompass external
 248                                  * dictionary and current block
 249                                  */
 250                                 size_t const copySize = (size_t)(lowPrefix - match);
 251                                 size_t const restSize = length - copySize;
 252
 253                                 memcpy(op, dictEnd - copySize, copySize);
 254                                 op += copySize;
 255
 256                                 if (restSize > (size_t)(op - lowPrefix)) {
 257                                         /* overlap copy */
 258                                         BYTE * const endOfMatch = op + restSize;
 259                                         const BYTE *copyFrom = lowPrefix;
 260
 261                                         while (op < endOfMatch)
 262                                                 *op++ = *copyFrom++;
 263                                 } else {
 264                                         memcpy(op, lowPrefix, restSize);
 265                                         op += restSize;
 266                                 }
 267                         }
 268
 269                         continue;
 270                 }
 271
 272                 /* copy match within block */
 273                 cpy = op + length;
 274
 275                 if (unlikely(offset < 8)) {
 276                         const int dec64 = dec64table[offset];
 277
 278                         op[0] = match[0];
 279                         op[1] = match[1];
 280                         op[2] = match[2];
 281                         op[3] = match[3];
 282                         match += dec32table[offset];
 283                         memcpy(op + 4, match, 4);
 284                         match -= dec64;
 285                 } else {
 286                         LZ4_copy8(op, match);
 287                         match += 8;
 288                 }
 289
 290                 op += 8;
 291
 292                 if (unlikely(cpy > oend - 12)) {
 293                         BYTE * const oCopyLimit = oend - (WILDCOPYLENGTH - 1);
 294
 295                         if (cpy > oend - LASTLITERALS) {
 296                                 /*
 297                                  * Error : last LASTLITERALS bytes
 298                                  * must be literals (uncompressed)
 299                                  */
 300                                 goto _output_error;
 301                         }
 302
 303                         if (op < oCopyLimit) {
 304                                 LZ4_wildCopy(op, match, oCopyLimit);
 305                                 match += oCopyLimit - op;
 306                                 op = oCopyLimit;
 307                         }
 308
 309                         while (op < cpy)
 310                                 *op++ = *match++;
 311                 } else {
 312                         LZ4_copy8(op, match);
 313
 314                         if (length > 16)
 315                                 LZ4_wildCopy(op + 8, match + 8, cpy);
 316                 }
 317
 318                 op = cpy; /* correction */
 319         }
 320
 321         /* end of decoding */
 322         if (endOnInput) {
 323                 /* Nb of output bytes decoded */
 324                 return (int) (((char *)op) - dest);
 325         } else {
 326                 /* Nb of input bytes read */
 327                 return (int) (((const char *)ip) - source);
 328         }
 329
 330         /* Overflow error detected */
 331 _output_error:
 332         return -1;
 333 }
 334
 335 int LZ4_decompress_safe(const char *source, char *dest,
 336         int compressedSize, int maxDecompressedSize)
 337 {
 338         return LZ4_decompress_generic(source, dest, compressedSize,
 339                 maxDecompressedSize, endOnInputSize, full, 0,
 340                 noDict, (BYTE *)dest, NULL, 0);
 341 }
 342
 343 int LZ4_decompress_safe_partial(const char *source, char *dest,
 344         int compressedSize, int targetOutputSize, int maxDecompressedSize)
 345 {
 346         return LZ4_decompress_generic(source, dest, compressedSize,
 347                 maxDecompressedSize, endOnInputSize, partial,
 348                 targetOutputSize, noDict, (BYTE *)dest, NULL, 0);
 349 }
 350
 351 int LZ4_decompress_fast(const char *source, char *dest, int originalSize)
 352 {
 353         return LZ4_decompress_generic(source, dest, 0, originalSize,
 354                 endOnOutputSize, full, 0, withPrefix64k,
 355                 (BYTE *)(dest - 64 * KB), NULL, 64 * KB);
 356 }
 357
 358 int LZ4_setStreamDecode(LZ4_streamDecode_t *LZ4_streamDecode,
 359         const char *dictionary, int dictSize)
 360 {
 361         LZ4_streamDecode_t_internal *lz4sd = (LZ4_streamDecode_t_internal *) LZ4_streamDecode;
 362
 363         lz4sd->prefixSize = (size_t) dictSize;
 364         lz4sd->prefixEnd = (const BYTE *) dictionary + dictSize;
 365         lz4sd->externalDict = NULL;
 366         lz4sd->extDictSize      = 0;
 367         return 1;
 368 }
 369
 370 /*
 371  * *_continue() :
 372  * These decoding functions allow decompression of multiple blocks
 373  * in "streaming" mode.
 374  * Previously decoded blocks must still be available at the memory
 375  * position where they were decoded.
 376  * If it's not possible, save the relevant part of
 377  * decoded data into a safe buffer,
 378  * and indicate where it stands using LZ4_setStreamDecode()
 379  */
 380 int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode,
 381         const char *source, char *dest, int compressedSize, int maxOutputSize)
 382 {
 383         LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse;
 384         int result;
 385
 386         if (lz4sd->prefixEnd == (BYTE *)dest) {
 387                 result = LZ4_decompress_generic(source, dest,
 388                         compressedSize,
 389                         maxOutputSize,
 390                         endOnInputSize, full, 0,
 391                         usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize,
 392                         lz4sd->externalDict,
 393                         lz4sd->extDictSize);
 394
 395                 if (result <= 0)
 396                         return result;
 397
 398                 lz4sd->prefixSize += result;
 399                 lz4sd->prefixEnd        += result;
 400         } else {
 401                 lz4sd->extDictSize = lz4sd->prefixSize;
 402                 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
 403                 result = LZ4_decompress_generic(source, dest,
 404                         compressedSize, maxOutputSize,
 405                         endOnInputSize, full, 0,
 406                         usingExtDict, (BYTE *)dest,
 407                         lz4sd->externalDict, lz4sd->extDictSize);
 408                 if (result <= 0)
 409                         return result;
 410                 lz4sd->prefixSize = result;
 411                 lz4sd->prefixEnd        = (BYTE *)dest + result;
 412         }
 413
 414         return result;
 415 }
 416
 417 int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode,
 418         const char *source, char *dest, int originalSize)
 419 {
 420         LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse;
 421         int result;
 422
 423         if (lz4sd->prefixEnd == (BYTE *)dest) {
 424                 result = LZ4_decompress_generic(source, dest, 0, originalSize,
 425                         endOnOutputSize, full, 0,
 426                         usingExtDict,
 427                         lz4sd->prefixEnd - lz4sd->prefixSize,
 428                         lz4sd->externalDict, lz4sd->extDictSize);
 429
 430                 if (result <= 0)
 431                         return result;
 432
 433                 lz4sd->prefixSize += originalSize;
 434                 lz4sd->prefixEnd        += originalSize;
 435         } else {
 436                 lz4sd->extDictSize = lz4sd->prefixSize;
 437                 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
 438                 result = LZ4_decompress_generic(source, dest, 0, originalSize,
 439                         endOnOutputSize, full, 0,
 440                         usingExtDict, (BYTE *)dest,
 441                         lz4sd->externalDict, lz4sd->extDictSize);
 442                 if (result <= 0)
 443                         return result;
 444                 lz4sd->prefixSize = originalSize;
 445                 lz4sd->prefixEnd        = (BYTE *)dest + originalSize;
 446         }
 447
 448         return result;
 449 }
 450
 451 /*
 452  * Advanced decoding functions :
 453  * *_usingDict() :
 454  * These decoding functions work the same as "_continue" ones,
 455  * the dictionary must be explicitly provided within parameters
 456  */
 457 static FORCE_INLINE int LZ4_decompress_usingDict_generic(const char *source,
 458         char *dest, int compressedSize, int maxOutputSize, int safe,
 459         const char *dictStart, int dictSize)
 460 {
 461         if (dictSize == 0)
 462                 return LZ4_decompress_generic(source, dest,
 463                         compressedSize, maxOutputSize, safe, full, 0,
 464                         noDict, (BYTE *)dest, NULL, 0);
 465         if (dictStart + dictSize == dest) {
 466                 if (dictSize >= (int)(64 * KB - 1))
 467                         return LZ4_decompress_generic(source, dest,
 468                                 compressedSize, maxOutputSize, safe, full, 0,
 469                                 withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0);
 470                 return LZ4_decompress_generic(source, dest, compressedSize,
 471                         maxOutputSize, safe, full, 0, noDict,
 472                         (BYTE *)dest - dictSize, NULL, 0);
 473         }
 474         return LZ4_decompress_generic(source, dest, compressedSize,
 475                 maxOutputSize, safe, full, 0, usingExtDict,
 476                 (BYTE *)dest, (const BYTE *)dictStart, dictSize);
 477 }
 478
 479 int LZ4_decompress_safe_usingDict(const char *source, char *dest,
 480         int compressedSize, int maxOutputSize,
 481         const char *dictStart, int dictSize)
 482 {
 483         return LZ4_decompress_usingDict_generic(source, dest,
 484                 compressedSize, maxOutputSize, 1, dictStart, dictSize);
 485 }
 486
 487 int LZ4_decompress_fast_usingDict(const char *source, char *dest,
 488         int originalSize, const char *dictStart, int dictSize)
 489 {
 490         return LZ4_decompress_usingDict_generic(source, dest, 0,
 491                 originalSize, 0, dictStart, dictSize);
 492 }