1 /*
2 [0_MMMM_LLL] - 16-bit offset, 4-bit match length (4-15+), 3-bit literal length (0-7+)
3 [1_MMMM_LLL] - last offset, 4-bit match length (0-15+), 3-bit literal length (0-7+)
4 flag 31 - 24-bit offset, match length (47+), no literal length
5 flag 0-30 - 24-bit offset, 31 match lengths (16-46), no literal length
6 */
7
8 /*! Lizard_decompress_LIZv1() :
9 * This generic decompression function cover all use cases.
10 * It shall be instantiated several times, using different sets of directives
11 * Note that it is important this generic function is really inlined,
12 * in order to remove useless branches during compilation optimization.
13 */
Lizard_decompress_LIZv1(Lizard_dstream_t * ctx,BYTE * const dest,int outputSize,int partialDecoding,int targetOutputSize,int dict,const BYTE * const lowPrefix,const BYTE * const dictStart,const size_t dictSize,int compressionLevel)14 FORCE_INLINE int Lizard_decompress_LIZv1(
15 Lizard_dstream_t* ctx,
16 BYTE* const dest,
17 int outputSize, /* this value is the max size of Output Buffer. */
18
19 int partialDecoding, /* full, partial */
20 int targetOutputSize, /* only used if partialDecoding==partial */
21 int dict, /* noDict, withPrefix64k, usingExtDict */
22 const BYTE* const lowPrefix, /* == dest if dict == noDict */
23 const BYTE* const dictStart, /* only if dict==usingExtDict */
24 const size_t dictSize, /* note : = 0 if noDict */
25 int compressionLevel
26 )
27 {
28 /* Local Variables */
29 int inputSize = (int)(ctx->flagsEnd - ctx->flagsPtr);
30 const BYTE* const blockBase = ctx->flagsPtr;
31 const BYTE* const iend = ctx->literalsEnd;
32
33 BYTE* op = dest;
34 BYTE* const oend = op + outputSize;
35 BYTE* cpy = NULL;
36 BYTE* oexit = op + targetOutputSize;
37 const BYTE* const lowLimit = lowPrefix - dictSize;
38 const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
39
40 const int checkOffset = (dictSize < (int)(LIZARD_DICT_SIZE));
41
42 intptr_t last_off = ctx->last_off;
43 intptr_t length = 0;
44 (void)compressionLevel;
45
46 /* Special cases */
47 if (unlikely(outputSize==0)) return ((inputSize==1) && (*ctx->flagsPtr==0)) ? 0 : -1; /* Empty output buffer */
48
49 /* Main Loop : decode sequences */
50 while (ctx->flagsPtr < ctx->flagsEnd) {
51 unsigned token;
52 const BYTE* match;
53 // intptr_t litLength;
54
55 if ((partialDecoding) && (op >= oexit)) return (int) (op-dest);
56
57 /* get literal length */
58 token = *ctx->flagsPtr++;
59
60 if (token >= 32)
61 {
62 if ((length=(token & MAX_SHORT_LITLEN)) == MAX_SHORT_LITLEN) {
63 if (unlikely(ctx->literalsPtr > iend - 1)) { LIZARD_LOG_DECOMPRESS_LIZv1("1"); goto _output_error; }
64 length = *ctx->literalsPtr;
65 if unlikely(length >= 254) {
66 if (length == 254) {
67 length = MEM_readLE16(ctx->literalsPtr+1);
68 ctx->literalsPtr += 2;
69 } else {
70 length = MEM_readLE24(ctx->literalsPtr+1);
71 ctx->literalsPtr += 3;
72 }
73 }
74 length += MAX_SHORT_LITLEN;
75 ctx->literalsPtr++;
76 if (unlikely((size_t)(op+length)<(size_t)(op))) { LIZARD_LOG_DECOMPRESS_LIZv1("2"); goto _output_error; } /* overflow detection */
77 if (unlikely((size_t)(ctx->literalsPtr+length)<(size_t)(ctx->literalsPtr))) { LIZARD_LOG_DECOMPRESS_LIZv1("3"); goto _output_error; } /* overflow detection */
78 }
79
80 /* copy literals */
81 cpy = op + length;
82 if (unlikely(cpy > oend - WILDCOPYLENGTH || ctx->literalsPtr > iend - WILDCOPYLENGTH)) { LIZARD_LOG_DECOMPRESS_LIZv1("offset outside buffers\n"); goto _output_error; } /* Error : offset outside buffers */
83 #if 1
84 Lizard_wildCopy16(op, ctx->literalsPtr, cpy);
85 op = cpy;
86 ctx->literalsPtr += length;
87 #else
88 Lizard_copy8(op, ctx->literalsPtr);
89 Lizard_copy8(op+8, ctx->literalsPtr+8);
90 if (length > 16)
91 Lizard_wildCopy16(op + 16, ctx->literalsPtr + 16, cpy);
92 op = cpy;
93 ctx->literalsPtr += length;
94 #endif
95
96 /* get offset */
97 if (unlikely(ctx->offset16Ptr > ctx->offset16End)) { LIZARD_LOG_DECOMPRESS_LIZv1("(ctx->offset16Ptr > ctx->offset16End\n"); goto _output_error; }
98 #if 1
99 { /* branchless */
100 intptr_t new_off = MEM_readLE16(ctx->offset16Ptr);
101 uintptr_t not_repCode = (uintptr_t)(token >> ML_RUN_BITS) - 1;
102 last_off ^= not_repCode & (last_off ^ -new_off);
103 ctx->offset16Ptr = (BYTE*)((uintptr_t)ctx->offset16Ptr + (not_repCode & 2));
104 }
105 #else
106 if ((token >> ML_RUN_BITS_LIZv1) == 0)
107 {
108 last_off = -(intptr_t)MEM_readLE16(ctx->offset16Ptr);
109 ctx->offset16Ptr += 2;
110 }
111 #endif
112
113 /* get matchlength */
114 length = (token >> RUN_BITS_LIZv1) & MAX_SHORT_MATCHLEN;
115 if (length == MAX_SHORT_MATCHLEN) {
116 if (unlikely(ctx->literalsPtr > iend - 1)) { LIZARD_LOG_DECOMPRESS_LIZv1("6"); goto _output_error; }
117 length = *ctx->literalsPtr;
118 if unlikely(length >= 254) {
119 if (length == 254) {
120 length = MEM_readLE16(ctx->literalsPtr+1);
121 ctx->literalsPtr += 2;
122 } else {
123 length = MEM_readLE24(ctx->literalsPtr+1);
124 ctx->literalsPtr += 3;
125 }
126 }
127 length += MAX_SHORT_MATCHLEN;
128 ctx->literalsPtr++;
129 if (unlikely((size_t)(op+length)<(size_t)(op))) { LIZARD_LOG_DECOMPRESS_LIZv1("7"); goto _output_error; } /* overflow detection */
130 }
131
132 DECOMPLOG_CODEWORDS_LIZv1("T32+ literal=%u match=%u offset=%d ipos=%d opos=%d\n", (U32)litLength, (U32)length, (int)-last_off, (U32)(ctx->flagsPtr-blockBase), (U32)(op-dest));
133 }
134 else
135 if (token < LIZARD_LAST_LONG_OFF)
136 {
137 if (unlikely(ctx->offset24Ptr > ctx->offset24End - 3)) { LIZARD_LOG_DECOMPRESS_LIZv1("8"); goto _output_error; }
138 length = token + MM_LONGOFF;
139 last_off = -(intptr_t)MEM_readLE24(ctx->offset24Ptr);
140 ctx->offset24Ptr += 3;
141 DECOMPLOG_CODEWORDS_LIZv1("T0-30 literal=%u match=%u offset=%d\n", 0, (U32)length, (int)-last_off);
142 }
143 else
144 {
145 if (unlikely(ctx->literalsPtr > iend - 1)) { LIZARD_LOG_DECOMPRESS_LIZv1("9"); goto _output_error; }
146 length = *ctx->literalsPtr;
147 if unlikely(length >= 254) {
148 if (length == 254) {
149 length = MEM_readLE16(ctx->literalsPtr+1);
150 ctx->literalsPtr += 2;
151 } else {
152 length = MEM_readLE24(ctx->literalsPtr+1);
153 ctx->literalsPtr += 3;
154 }
155 }
156 ctx->literalsPtr++;
157 length += LIZARD_LAST_LONG_OFF + MM_LONGOFF;
158
159 if (unlikely(ctx->offset24Ptr > ctx->offset24End - 3)) { LIZARD_LOG_DECOMPRESS_LIZv1("10"); goto _output_error; }
160 last_off = -(intptr_t)MEM_readLE24(ctx->offset24Ptr);
161 ctx->offset24Ptr += 3;
162 }
163
164
165 match = op + last_off;
166 if ((checkOffset) && ((unlikely((uintptr_t)(-last_off) > (uintptr_t)op) || (match < lowLimit)))) { LIZARD_LOG_DECOMPRESS_LIZv1("lowPrefix[%p]-dictSize[%d]=lowLimit[%p] match[%p]=op[%p]-last_off[%d]\n", lowPrefix, (int)dictSize, lowLimit, match, op, (int)last_off); goto _output_error; } /* Error : offset outside buffers */
167
168 /* check external dictionary */
169 if ((dict==usingExtDict) && (match < lowPrefix)) {
170 if (unlikely(op + length > oend - WILDCOPYLENGTH)) { LIZARD_LOG_DECOMPRESS_LIZv1("12"); goto _output_error; } /* doesn't respect parsing restriction */
171
172 if (length <= (intptr_t)(lowPrefix - match)) {
173 /* match can be copied as a single segment from external dictionary */
174 memmove(op, dictEnd - (lowPrefix-match), length);
175 op += length;
176 } else {
177 /* match encompass external dictionary and current block */
178 size_t const copySize = (size_t)(lowPrefix-match);
179 size_t const restSize = length - copySize;
180 memcpy(op, dictEnd - copySize, copySize);
181 op += copySize;
182 if (restSize > (size_t)(op-lowPrefix)) { /* overlap copy */
183 BYTE* const endOfMatch = op + restSize;
184 const BYTE* copyFrom = lowPrefix;
185 while (op < endOfMatch) *op++ = *copyFrom++;
186 } else {
187 memcpy(op, lowPrefix, restSize);
188 op += restSize;
189 } }
190 continue;
191 }
192
193 /* copy match within block */
194 cpy = op + length;
195 if (unlikely(cpy > oend - WILDCOPYLENGTH)) { LIZARD_LOG_DECOMPRESS_LIZv1("13match=%p lowLimit=%p\n", match, lowLimit); goto _output_error; } /* Error : offset outside buffers */
196 Lizard_copy8(op, match);
197 Lizard_copy8(op+8, match+8);
198 if (length > 16)
199 Lizard_wildCopy16(op + 16, match + 16, cpy);
200 op = cpy;
201 }
202
203 /* last literals */
204 length = ctx->literalsEnd - ctx->literalsPtr;
205 cpy = op + length;
206 if ((ctx->literalsPtr+length != iend) || (cpy > oend)) { LIZARD_LOG_DECOMPRESS_LIZv1("14"); goto _output_error; } /* Error : input must be consumed */
207 memcpy(op, ctx->literalsPtr, length);
208 ctx->literalsPtr += length;
209 op += length;
210
211 /* end of decoding */
212 ctx->last_off = last_off;
213 return (int) (op-dest); /* Nb of output bytes decoded */
214
215 /* Overflow error detected */
216 _output_error:
217 LIZARD_LOG_DECOMPRESS_LIZv1("_output_error=%d ctx->flagsPtr=%p blockBase=%p\n", (int) (-(ctx->flagsPtr-blockBase))-1, ctx->flagsPtr, blockBase);
218 LIZARD_LOG_DECOMPRESS_LIZv1("cpy=%p oend=%p ctx->literalsPtr+length[%d]=%p iend=%p\n", cpy, oend, (int)length, ctx->literalsPtr+length, iend);
219 return (int) (-(ctx->flagsPtr-blockBase))-1;
220 }
221