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