src/commonlib/bsd/lz4.c.inc

   1 /*
   2    LZ4 - Fast LZ compression algorithm
   3    Copyright (C) 2011-2015, Yann Collet.
   4
   5    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
   6
   7    Redistribution and use in source and binary forms, with or without
   8    modification, are permitted provided that the following conditions are
   9    met:
  10
  11        * Redistributions of source code must retain the above copyright
  12    notice, this list of conditions and the following disclaimer.
  13        * Redistributions in binary form must reproduce the above
  14    copyright notice, this list of conditions and the following disclaimer
  15    in the documentation and/or other materials provided with the
  16    distribution.
  17
  18    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30    You can contact the author at :
  31    - LZ4 source repository : https://github.com/Cyan4973/lz4
  32    - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
  33 */
  34
  35
  36 /**************************************
  37 *  Reading and writing into memory
  38 **************************************/
  39
  40 /* customized variant of memcpy, which can overwrite up to 7 bytes beyond dstEnd */
  41 static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
  42 {
  43     BYTE* d = (BYTE*)dstPtr;
  44     const BYTE* s = (const BYTE*)srcPtr;
  45     BYTE* const e = (BYTE*)dstEnd;
  46
  47 #if 0
  48     const size_t l2 = 8 - (((size_t)d) & (sizeof(void*)-1));
  49     LZ4_copy8(d,s); if (d>e-9) return;
  50     d+=l2; s+=l2;
  51 #endif /* join to align */
  52
  53     do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
  54 }
  55
  56
  57 /**************************************
  58 *  Common Constants
  59 **************************************/
  60 #define MINMATCH 4
  61
  62 #define WILDCOPYLENGTH 8
  63 #define LASTLITERALS 5
  64 #define MFLIMIT (WILDCOPYLENGTH+MINMATCH)
  65 static const int LZ4_minLength = (MFLIMIT+1);
  66
  67 #define KB *(1 <<10)
  68 #define MB *(1 <<20)
  69 #define GB *(1U<<30)
  70
  71 #define MAXD_LOG 16
  72 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
  73
  74 #define ML_BITS  4
  75 #define ML_MASK  ((1U<<ML_BITS)-1)
  76 #define RUN_BITS (8-ML_BITS)
  77 #define RUN_MASK ((1U<<RUN_BITS)-1)
  78
  79
  80 /**************************************
  81 *  Local Structures and types
  82 **************************************/
  83 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
  84 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
  85 typedef enum { full = 0, partial = 1 } earlyEnd_directive;
  86
  87
  88
  89 /*******************************
  90 *  Decompression functions
  91 *******************************/
  92 /*
  93  * This generic decompression function cover all use cases.
  94  * It shall be instantiated several times, using different sets of directives
  95  * Note that it is essential this generic function is really inlined,
  96  * in order to remove useless branches during compilation optimization.
  97  */
  98 FORCE_INLINE int LZ4_decompress_generic(
  99                  const char* const source,
 100                  char* const dest,
 101                  int inputSize,
 102                  int outputSize,         /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
 103
 104                  int endOnInput,         /* endOnOutputSize, endOnInputSize */
 105                  int partialDecoding,    /* full, partial */
 106                  int targetOutputSize,   /* only used if partialDecoding==partial */
 107                  int dict,               /* noDict, withPrefix64k, usingExtDict */
 108                  const BYTE* const lowPrefix,  /* == dest if dict == noDict */
 109                  const BYTE* const dictStart,  /* only if dict==usingExtDict */
 110                  const size_t dictSize         /* note : = 0 if noDict */
 111                  )
 112 {
 113     /* Local Variables */
 114     const BYTE* ip = (const BYTE*) source;
 115     const BYTE* const iend = ip + inputSize;
 116
 117     BYTE* op = (BYTE*) dest;
 118     BYTE* const oend = op + outputSize;
 119     BYTE* cpy;
 120     BYTE* oexit = op + targetOutputSize;
 121     const BYTE* const lowLimit = lowPrefix - dictSize;
 122
 123     const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
 124     const unsigned dec32table[] = {4, 1, 2, 1, 4, 4, 4, 4};
 125     const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
 126
 127     const int safeDecode = (endOnInput==endOnInputSize);
 128     const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
 129     const int inPlaceDecode = ((ip >= op) && (ip < oend));
 130
 131
 132     /* Special cases */
 133     if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT;                         /* targetOutputSize too high => decode everything */
 134     if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1;  /* Empty output buffer */
 135     if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
 136
 137
 138     /* Main Loop */
 139     while (1)
 140     {
 141         unsigned token;
 142         size_t length;
 143         const BYTE* match;
 144         size_t offset;
 145
 146         if (unlikely((inPlaceDecode) && (op + WILDCOPYLENGTH > ip))) goto _output_error;   /* output stream ran over input stream */
 147
 148         /* get literal length */
 149         token = *ip++;
 150         if ((length=(token>>ML_BITS)) == RUN_MASK)
 151         {
 152             unsigned s;
 153             if ((endOnInput) && unlikely(ip>=iend-RUN_MASK)) goto _output_error;   /* overflow detection */
 154             do
 155             {
 156                 s = *ip++;
 157                 length += s;
 158             }
 159             while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) && (s==255) );
 160             if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error;   /* overflow detection */
 161             if ((safeDecode) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error;   /* overflow detection */
 162         }
 163
 164         /* copy literals */
 165         cpy = op+length;
 166         if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
 167             || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)))
 168         {
 169             if (partialDecoding)
 170             {
 171                 if (cpy > oend) goto _output_error;                           /* Error : write attempt beyond end of output buffer */
 172                 if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
 173             }
 174             else
 175             {
 176                 if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
 177                 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
 178             }
 179             memmove(op, ip, length);
 180             ip += length;
 181             op += length;
 182             break;     /* Necessarily EOF, due to parsing restrictions */
 183         }
 184         LZ4_wildCopy(op, ip, cpy);
 185         ip += length; op = cpy;
 186
 187         /* get offset */
 188         offset = LZ4_readLE16(ip); ip+=2;
 189         match = op - offset;
 190         if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error;   /* Error : offset outside buffers */
 191
 192         /* get matchlength */
 193         length = token & ML_MASK;
 194         if (length == ML_MASK)
 195         {
 196             unsigned s;
 197             do
 198             {
 199                 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
 200                 s = *ip++;
 201                 length += s;
 202             } while (s==255);
 203             if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error;   /* overflow detection */
 204         }
 205         length += MINMATCH;
 206
 207         /* check external dictionary */
 208         if ((dict==usingExtDict) && (match < lowPrefix))
 209         {
 210             if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error;   /* doesn't respect parsing restriction */
 211
 212             if (length <= (size_t)(lowPrefix-match))
 213             {
 214                 /* match can be copied as a single segment from external dictionary */
 215                 match = dictEnd - (lowPrefix-match);
 216                 memmove(op, match, length); op += length;
 217             }
 218             else
 219             {
 220                 /* match encompass external dictionary and current block */
 221                 size_t copySize = (size_t)(lowPrefix-match);
 222                 memcpy(op, dictEnd - copySize, copySize);
 223                 op += copySize;
 224                 copySize = length - copySize;
 225                 if (copySize > (size_t)(op-lowPrefix))   /* overlap copy */
 226                 {
 227                     BYTE* const endOfMatch = op + copySize;
 228                     const BYTE* copyFrom = lowPrefix;
 229                     while (op < endOfMatch) *op++ = *copyFrom++;
 230                 }
 231                 else
 232                 {
 233                     memcpy(op, lowPrefix, copySize);
 234                     op += copySize;
 235                 }
 236             }
 237             continue;
 238         }
 239
 240         /* copy match within block */
 241         cpy = op + length;
 242         if (unlikely(offset<8))
 243         {
 244             const int dec64 = dec64table[offset];
 245             op[0] = match[0];
 246             op[1] = match[1];
 247             op[2] = match[2];
 248             op[3] = match[3];
 249             match += dec32table[offset];
 250             memcpy(op+4, match, 4);
 251             match -= dec64;
 252         } else { LZ4_copy8(op, match); match+=8; }
 253         op += 8;
 254
 255         if (unlikely(cpy>oend-12))
 256         {
 257             BYTE* const oCopyLimit = oend-(WILDCOPYLENGTH-1);
 258             if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last LASTLITERALS bytes must be literals (uncompressed) */
 259             if (op < oCopyLimit)
 260             {
 261                 LZ4_wildCopy(op, match, oCopyLimit);
 262                 match += oCopyLimit - op;
 263                 op = oCopyLimit;
 264             }
 265             while (op<cpy) *op++ = *match++;
 266         }
 267         else
 268             LZ4_wildCopy(op, match, cpy);
 269         op=cpy;   /* correction */
 270     }
 271
 272     /* end of decoding */
 273     if (endOnInput)
 274        return (int) (((char*)op)-dest);     /* Nb of output bytes decoded */
 275     else
 276        return (int) (((const char*)ip)-source);   /* Nb of input bytes read */
 277
 278     /* Overflow error detected */
 279 _output_error:
 280     return (int) (-(((const char*)ip)-source))-1;
 281 }