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