2 LZ4 - Fast LZ compression algorithm
3 Copyright (C) 2011-2015, Yann Collet.
5 SPDX-License-Identifier: BSD-2-Clause
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
13 /**************************************
14 * Reading and writing into memory
15 **************************************/
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)
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);
27 /**************************************
29 **************************************/
33 #define LASTLITERALS 5
34 #define MFLIMIT (COPYLENGTH+MINMATCH)
35 static const int LZ4_minLength = (MFLIMIT+1);
42 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
45 #define ML_MASK ((1U<<ML_BITS)-1)
46 #define RUN_BITS (8-ML_BITS)
47 #define RUN_MASK ((1U<<RUN_BITS)-1)
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;
59 /*******************************
60 * Decompression functions
61 *******************************/
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.
68 FORCE_INLINE int LZ4_decompress_generic(
69 const char* const source,
72 int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
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 */
84 const BYTE* ip = (const BYTE*) source;
85 const BYTE* const iend = ip + inputSize;
87 BYTE* op = (BYTE*) dest;
88 BYTE* const oend = op + outputSize;
90 BYTE* oexit = op + targetOutputSize;
91 const BYTE* const lowLimit = lowPrefix - dictSize;
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};
97 const int safeDecode = (endOnInput==endOnInputSize);
98 const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
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);
114 /* get literal length */
116 if ((length=(token>>ML_BITS)) == RUN_MASK)
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 */
131 if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
132 || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
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 */
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 */
144 memcpy(op, ip, length);
147 break; /* Necessarily EOF, due to parsing restrictions */
149 LZ4_wildCopy(op, ip, cpy);
150 ip += length; op = cpy;
153 match = cpy - LZ4_readLE16(ip); ip+=2;
154 if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error; /* Error : offset outside destination buffer */
156 /* get matchlength */
157 length = token & ML_MASK;
158 if (length == ML_MASK)
163 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
167 if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error; /* overflow detection */
171 /* check external dictionary */
172 if ((dict==usingExtDict) && (match < lowPrefix))
174 if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error; /* doesn't respect parsing restriction */
176 if (length <= (size_t)(lowPrefix-match))
178 /* match can be copied as a single segment from external dictionary */
179 match = dictEnd - (lowPrefix-match);
180 memmove(op, match, length); op += length;
184 /* match encompass external dictionary and current segment */
185 size_t copySize = (size_t)(lowPrefix-match);
186 memcpy(op, dictEnd - copySize, copySize);
188 copySize = length - copySize;
189 if (copySize > (size_t)(op-lowPrefix)) /* overlap within current segment */
191 BYTE* const endOfMatch = op + copySize;
192 const BYTE* copyFrom = lowPrefix;
193 while (op < endOfMatch) *op++ = *copyFrom++;
197 memcpy(op, lowPrefix, copySize);
204 /* copy repeated sequence */
206 if (unlikely((op-match)<8))
208 const size_t dec64 = dec64table[op-match];
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; }
218 if (unlikely(cpy>oend-12))
220 if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last LASTLITERALS bytes must be literals */
223 LZ4_wildCopy(op, match, oend-8);
224 match += (oend-8) - op;
227 while (op<cpy) *op++ = *match++;
230 LZ4_wildCopy(op, match, cpy);
231 op=cpy; /* correction */
234 /* end of decoding */
236 return (int) (((char*)op)-dest); /* Nb of output bytes decoded */
238 return (int) (((const char*)ip)-source); /* Nb of input bytes read */
240 /* Overflow error detected */
242 return (int) (-(((const char*)ip)-source))-1;