blob: f518341af5c2b608d3c1aa45d1acb0e1f66f577d [file] [log] [blame]
Julius Werner027b7282015-10-06 20:03:53 -07001/*
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 */
18static 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)
35static 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**************************************/
53typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
54typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
55typedef 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 */
68FORCE_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}