lib/lz4.c

   1 // SPDX-License-Identifier: BSD-2-Clause
   2 /*
   3    LZ4 - Fast LZ compression algorithm
   4    Copyright (C) 2011-2015, Yann Collet.
   5
   6    You can contact the author at :
   7    - LZ4 source repository : https://github.com/Cyan4973/lz4
   8    - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
   9 */
  10
  11
  12 /**************************************
  13 *  Reading and writing into memory
  14 **************************************/
  15
  16 /* customized version of memcpy, which may overwrite up to 7 bytes beyond dstEnd */
  17 static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
  18 {
  19     BYTE* d = (BYTE*)dstPtr;
  20     const BYTE* s = (const BYTE*)srcPtr;
  21     BYTE* e = (BYTE*)dstEnd;
  22     do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
  23 }
  24
  25
  26 /**************************************
  27 *  Common Constants
  28 **************************************/
  29 #define MINMATCH 4
  30
  31 #define COPYLENGTH 8
  32 #define LASTLITERALS 5
  33 #define MFLIMIT (COPYLENGTH+MINMATCH)
  34 static const int LZ4_minLength = (MFLIMIT+1);
  35
  36 #define KB *(1 <<10)
  37 #define MB *(1 <<20)
  38 #define GB *(1U<<30)
  39
  40 #define MAXD_LOG 16
  41 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
  42
  43 #define ML_BITS  4
  44 #define ML_MASK  ((1U<<ML_BITS)-1)
  45 #define RUN_BITS (8-ML_BITS)
  46 #define RUN_MASK ((1U<<RUN_BITS)-1)
  47
  48
  49 /**************************************
  50 *  Local Structures and types
  51 **************************************/
  52 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
  53 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
  54 typedef enum { full = 0, partial = 1 } earlyEnd_directive;
  55
  56
  57
  58 /*******************************
  59 *  Decompression functions
  60 *******************************/
  61 /*
  62  * This generic decompression function cover all use cases.
  63  * It shall be instantiated several times, using different sets of directives
  64  * Note that it is essential this generic function is really inlined,
  65  * in order to remove useless branches during compilation optimization.
  66  */
  67 FORCE_INLINE int LZ4_decompress_generic(
  68                  const char* const source,
  69                  char* const dest,
  70                  int inputSize,
  71                  int outputSize,         /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
  72
  73                  int endOnInput,         /* endOnOutputSize, endOnInputSize */
  74                  int partialDecoding,    /* full, partial */
  75                  int targetOutputSize,   /* only used if partialDecoding==partial */
  76                  int dict,               /* noDict, withPrefix64k, usingExtDict */
  77                  const BYTE* const lowPrefix,  /* == dest if dict == noDict */
  78                  const BYTE* const dictStart,  /* only if dict==usingExtDict */
  79                  const size_t dictSize         /* note : = 0 if noDict */
  80                  )
  81 {
  82     /* Local Variables */
  83     const BYTE* ip = (const BYTE*) source;
  84     const BYTE* const iend = ip + inputSize;
  85
  86     BYTE* op = (BYTE*) dest;
  87     BYTE* const oend = op + outputSize;
  88     BYTE* cpy;
  89     BYTE* oexit = op + targetOutputSize;
  90     const BYTE* const lowLimit = lowPrefix - dictSize;
  91
  92     const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
  93     const size_t dec32table[] = {4, 1, 2, 1, 4, 4, 4, 4};
  94     const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
  95
  96     const int safeDecode = (endOnInput==endOnInputSize);
  97     const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
  98
  99
 100     /* Special cases */
 101     if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT;                         /* targetOutputSize too high => decode everything */
 102     if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1;  /* Empty output buffer */
 103     if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
 104
 105
 106     /* Main Loop */
 107     while (1)
 108     {
 109         unsigned token;
 110         size_t length;
 111         const BYTE* match;
 112
 113         /* get literal length */
 114         token = *ip++;
 115         if ((length=(token>>ML_BITS)) == RUN_MASK)
 116         {
 117             unsigned s;
 118             do
 119             {
 120                 s = *ip++;
 121                 length += s;
 122             }
 123             while (likely((endOnInput)?ip<iend-RUN_MASK:1) && (s==255));
 124             if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error;   /* overflow detection */
 125             if ((safeDecode) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error;   /* overflow detection */
 126         }
 127
 128         /* copy literals */
 129         cpy = op+length;
 130         if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
 131             || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
 132         {
 133             if (partialDecoding)
 134             {
 135                 if (cpy > oend) goto _output_error;                           /* Error : write attempt beyond end of output buffer */
 136                 if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
 137             }
 138             else
 139             {
 140                 if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
 141                 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
 142             }
 143             memcpy(op, ip, length);
 144             ip += length;
 145             op += length;
 146             break;     /* Necessarily EOF, due to parsing restrictions */
 147         }
 148         LZ4_wildCopy(op, ip, cpy);
 149         ip += length; op = cpy;
 150
 151         /* get offset */
 152         match = cpy - LZ4_readLE16(ip); ip+=2;
 153         if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error;   /* Error : offset outside destination buffer */
 154
 155         /* get matchlength */
 156         length = token & ML_MASK;
 157         if (length == ML_MASK)
 158         {
 159             unsigned s;
 160             do
 161             {
 162                 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
 163                 s = *ip++;
 164                 length += s;
 165             } while (s==255);
 166             if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error;   /* overflow detection */
 167         }
 168         length += MINMATCH;
 169
 170         /* check external dictionary */
 171         if ((dict==usingExtDict) && (match < lowPrefix))
 172         {
 173             if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error;   /* doesn't respect parsing restriction */
 174
 175             if (length <= (size_t)(lowPrefix-match))
 176             {
 177                 /* match can be copied as a single segment from external dictionary */
 178                 match = dictEnd - (lowPrefix-match);
 179                 memmove(op, match, length); op += length;
 180             }
 181             else
 182             {
 183                 /* match encompass external dictionary and current segment */
 184                 size_t copySize = (size_t)(lowPrefix-match);
 185                 memcpy(op, dictEnd - copySize, copySize);
 186                 op += copySize;
 187                 copySize = length - copySize;
 188                 if (copySize > (size_t)(op-lowPrefix))   /* overlap within current segment */
 189                 {
 190                     BYTE* const endOfMatch = op + copySize;
 191                     const BYTE* copyFrom = lowPrefix;
 192                     while (op < endOfMatch) *op++ = *copyFrom++;
 193                 }
 194                 else
 195                 {
 196                     memcpy(op, lowPrefix, copySize);
 197                     op += copySize;
 198                 }
 199             }
 200             continue;
 201         }
 202
 203         /* copy repeated sequence */
 204         cpy = op + length;
 205         if (unlikely((op-match)<8))
 206         {
 207             const size_t dec64 = dec64table[op-match];
 208             op[0] = match[0];
 209             op[1] = match[1];
 210             op[2] = match[2];
 211             op[3] = match[3];
 212             match += dec32table[op-match];
 213             LZ4_copy4(op+4, match);
 214             op += 8; match -= dec64;
 215         } else { LZ4_copy8(op, match); op+=8; match+=8; }
 216
 217         if (unlikely(cpy>oend-12))
 218         {
 219             if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last LASTLITERALS bytes must be literals */
 220             if (op < oend-8)
 221             {
 222                 LZ4_wildCopy(op, match, oend-8);
 223                 match += (oend-8) - op;
 224                 op = oend-8;
 225             }
 226             while (op<cpy) *op++ = *match++;
 227         }
 228         else
 229             LZ4_wildCopy(op, match, cpy);
 230         op=cpy;   /* correction */
 231     }
 232
 233     /* end of decoding */
 234     if (endOnInput)
 235        return (int) (((char*)op)-dest);     /* Nb of output bytes decoded */
 236     else
 237        return (int) (((const char*)ip)-source);   /* Nb of input bytes read */
 238
 239     /* Overflow error detected */
 240 _output_error:
 241     return (int) (-(((const char*)ip)-source))-1;
 242 }