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 } 243