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 }