1 /* LzmaDec.c -- LZMA Decoder
2 2018-02-28 : Igor Pavlov : Public domain */
3 
4 #include "Precomp.h"
5 
6 /* #include "CpuArch.h" */
7 #include "LzmaDec.h"
8 
9 #include <string.h>
10 
11 #define kNumTopBits 24
12 #define kTopValue ((UInt32)1 << kNumTopBits)
13 
14 #define kNumBitModelTotalBits 11
15 #define kBitModelTotal (1 << kNumBitModelTotalBits)
16 #define kNumMoveBits 5
17 
18 #define RC_INIT_SIZE 5
19 
20 #define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
21 
22 #define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
23 #define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
24 #define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
25 #define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
26   { UPDATE_0(p); i = (i + i); A0; } else \
27   { UPDATE_1(p); i = (i + i) + 1; A1; }
28 
29 #define TREE_GET_BIT(probs, i) { GET_BIT2(probs + i, i, ;, ;); }
30 
31 #define REV_BIT(p, i, A0, A1) IF_BIT_0(p + i) \
32   { UPDATE_0(p + i); A0; } else \
33   { UPDATE_1(p + i); A1; }
34 #define REV_BIT_VAR(  p, i, m) REV_BIT(p, i, i += m; m += m, m += m; i += m; )
35 #define REV_BIT_CONST(p, i, m) REV_BIT(p, i, i += m;       , i += m * 2; )
36 #define REV_BIT_LAST( p, i, m) REV_BIT(p, i, i -= m        , ; )
37 
38 #define TREE_DECODE(probs, limit, i) \
39   { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
40 
41 /* #define _LZMA_SIZE_OPT */
42 
43 #ifdef _LZMA_SIZE_OPT
44 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
45 #else
46 #define TREE_6_DECODE(probs, i) \
47   { i = 1; \
48   TREE_GET_BIT(probs, i); \
49   TREE_GET_BIT(probs, i); \
50   TREE_GET_BIT(probs, i); \
51   TREE_GET_BIT(probs, i); \
52   TREE_GET_BIT(probs, i); \
53   TREE_GET_BIT(probs, i); \
54   i -= 0x40; }
55 #endif
56 
57 #define NORMAL_LITER_DEC TREE_GET_BIT(prob, symbol)
58 #define MATCHED_LITER_DEC \
59   matchByte += matchByte; \
60   bit = offs; \
61   offs &= matchByte; \
62   probLit = prob + (offs + bit + symbol); \
63   GET_BIT2(probLit, symbol, offs ^= bit; , ;)
64 
65 
66 
67 #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }
68 
69 #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
70 #define UPDATE_0_CHECK range = bound;
71 #define UPDATE_1_CHECK range -= bound; code -= bound;
72 #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
73   { UPDATE_0_CHECK; i = (i + i); A0; } else \
74   { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
75 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
76 #define TREE_DECODE_CHECK(probs, limit, i) \
77   { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }
78 
79 
80 #define REV_BIT_CHECK(p, i, m) IF_BIT_0_CHECK(p + i) \
81   { UPDATE_0_CHECK; i += m; m += m; } else \
82   { UPDATE_1_CHECK; m += m; i += m; }
83 
84 
85 #define kNumPosBitsMax 4
86 #define kNumPosStatesMax (1 << kNumPosBitsMax)
87 
88 #define kLenNumLowBits 3
89 #define kLenNumLowSymbols (1 << kLenNumLowBits)
90 #define kLenNumHighBits 8
91 #define kLenNumHighSymbols (1 << kLenNumHighBits)
92 
93 #define LenLow 0
94 #define LenHigh (LenLow + 2 * (kNumPosStatesMax << kLenNumLowBits))
95 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
96 
97 #define LenChoice LenLow
98 #define LenChoice2 (LenLow + (1 << kLenNumLowBits))
99 
100 #define kNumStates 12
101 #define kNumStates2 16
102 #define kNumLitStates 7
103 
104 #define kStartPosModelIndex 4
105 #define kEndPosModelIndex 14
106 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
107 
108 #define kNumPosSlotBits 6
109 #define kNumLenToPosStates 4
110 
111 #define kNumAlignBits 4
112 #define kAlignTableSize (1 << kNumAlignBits)
113 
114 #define kMatchMinLen 2
115 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols * 2 + kLenNumHighSymbols)
116 
117 /* External ASM code needs same CLzmaProb array layout. So don't change it. */
118 
119 /* (probs_1664) is faster and better for code size at some platforms */
120 /*
121 #ifdef MY_CPU_X86_OR_AMD64
122 */
123 #define kStartOffset 1664
124 #define GET_PROBS p->probs_1664
125 /*
126 #define GET_PROBS p->probs + kStartOffset
127 #else
128 #define kStartOffset 0
129 #define GET_PROBS p->probs
130 #endif
131 */
132 
133 #define SpecPos (-kStartOffset)
134 #define IsRep0Long (SpecPos + kNumFullDistances)
135 #define RepLenCoder (IsRep0Long + (kNumStates2 << kNumPosBitsMax))
136 #define LenCoder (RepLenCoder + kNumLenProbs)
137 #define IsMatch (LenCoder + kNumLenProbs)
138 #define Align (IsMatch + (kNumStates2 << kNumPosBitsMax))
139 #define IsRep (Align + kAlignTableSize)
140 #define IsRepG0 (IsRep + kNumStates)
141 #define IsRepG1 (IsRepG0 + kNumStates)
142 #define IsRepG2 (IsRepG1 + kNumStates)
143 #define PosSlot (IsRepG2 + kNumStates)
144 #define Literal (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
145 #define NUM_BASE_PROBS (Literal + kStartOffset)
146 
147 #if Align != 0 && kStartOffset != 0
148   #error Stop_Compiling_Bad_LZMA_kAlign
149 #endif
150 
151 #if NUM_BASE_PROBS != 1984
152   #error Stop_Compiling_Bad_LZMA_PROBS
153 #endif
154 
155 
156 #define LZMA_LIT_SIZE 0x300
157 
158 #define LzmaProps_GetNumProbs(p) (NUM_BASE_PROBS + ((UInt32)LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
159 
160 
161 #define CALC_POS_STATE(processedPos, pbMask) (((processedPos) & (pbMask)) << 4)
162 #define COMBINED_PS_STATE (posState + state)
163 #define GET_LEN_STATE (posState)
164 
165 #define LZMA_DIC_MIN (1 << 12)
166 
167 /*
168 p->remainLen : shows status of LZMA decoder:
169     < kMatchSpecLenStart : normal remain
170     = kMatchSpecLenStart : finished
171     = kMatchSpecLenStart + 1 : need init range coder
172     = kMatchSpecLenStart + 2 : need init range coder and state
173 */
174 
175 /* ---------- LZMA_DECODE_REAL ---------- */
176 /*
177 LzmaDec_DecodeReal_3() can be implemented in external ASM file.
178 3 - is the code compatibility version of that function for check at link time.
179 */
180 
181 #define LZMA_DECODE_REAL LzmaDec_DecodeReal_3
182 
183 /*
184 LZMA_DECODE_REAL()
185 In:
186   RangeCoder is normalized
187   if (p->dicPos == limit)
188   {
189     LzmaDec_TryDummy() was called before to exclude LITERAL and MATCH-REP cases.
190     So first symbol can be only MATCH-NON-REP. And if that MATCH-NON-REP symbol
191     is not END_OF_PAYALOAD_MARKER, then function returns error code.
192   }
193 
194 Processing:
195   first LZMA symbol will be decoded in any case
196   All checks for limits are at the end of main loop,
197   It will decode new LZMA-symbols while (p->buf < bufLimit && dicPos < limit),
198   RangeCoder is still without last normalization when (p->buf < bufLimit) is being checked.
199 
200 Out:
201   RangeCoder is normalized
202   Result:
203     SZ_OK - OK
204     SZ_ERROR_DATA - Error
205   p->remainLen:
206     < kMatchSpecLenStart : normal remain
207     = kMatchSpecLenStart : finished
208 */
209 
210 
211 #ifdef _LZMA_DEC_OPT
212 
213 int MY_FAST_CALL LZMA_DECODE_REAL(CLzmaDec *p, SizeT limit, const Byte *bufLimit);
214 
215 #else
216 
217 static
LZMA_DECODE_REAL(CLzmaDec * p,SizeT limit,const Byte * bufLimit)218 int MY_FAST_CALL LZMA_DECODE_REAL(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
219 {
220   CLzmaProb *probs = GET_PROBS;
221   unsigned state = (unsigned)p->state;
222   UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
223   unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
224   unsigned lc = p->prop.lc;
225   unsigned lpMask = ((unsigned)0x100 << p->prop.lp) - ((unsigned)0x100 >> lc);
226 
227   Byte *dic = p->dic;
228   SizeT dicBufSize = p->dicBufSize;
229   SizeT dicPos = p->dicPos;
230 
231   UInt32 processedPos = p->processedPos;
232   UInt32 checkDicSize = p->checkDicSize;
233   unsigned len = 0;
234 
235   const Byte *buf = p->buf;
236   UInt32 range = p->range;
237   UInt32 code = p->code;
238 
239   do
240   {
241     CLzmaProb *prob;
242     UInt32 bound;
243     unsigned ttt;
244     unsigned posState = CALC_POS_STATE(processedPos, pbMask);
245 
246     prob = probs + IsMatch + COMBINED_PS_STATE;
247     IF_BIT_0(prob)
248     {
249       unsigned symbol;
250       UPDATE_0(prob);
251       prob = probs + Literal;
252       if (processedPos != 0 || checkDicSize != 0)
253         prob += (UInt32)3 * ((((processedPos << 8) + dic[(dicPos == 0 ? dicBufSize : dicPos) - 1]) & lpMask) << lc);
254       processedPos++;
255 
256       if (state < kNumLitStates)
257       {
258         state -= (state < 4) ? state : 3;
259         symbol = 1;
260         #ifdef _LZMA_SIZE_OPT
261         do { NORMAL_LITER_DEC } while (symbol < 0x100);
262         #else
263         NORMAL_LITER_DEC
264         NORMAL_LITER_DEC
265         NORMAL_LITER_DEC
266         NORMAL_LITER_DEC
267         NORMAL_LITER_DEC
268         NORMAL_LITER_DEC
269         NORMAL_LITER_DEC
270         NORMAL_LITER_DEC
271         #endif
272       }
273       else
274       {
275         unsigned matchByte = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];
276         unsigned offs = 0x100;
277         state -= (state < 10) ? 3 : 6;
278         symbol = 1;
279         #ifdef _LZMA_SIZE_OPT
280         do
281         {
282           unsigned bit;
283           CLzmaProb *probLit;
284           MATCHED_LITER_DEC
285         }
286         while (symbol < 0x100);
287         #else
288         {
289           unsigned bit;
290           CLzmaProb *probLit;
291           MATCHED_LITER_DEC
292           MATCHED_LITER_DEC
293           MATCHED_LITER_DEC
294           MATCHED_LITER_DEC
295           MATCHED_LITER_DEC
296           MATCHED_LITER_DEC
297           MATCHED_LITER_DEC
298           MATCHED_LITER_DEC
299         }
300         #endif
301       }
302 
303       dic[dicPos++] = (Byte)symbol;
304       continue;
305     }
306 
307     {
308       UPDATE_1(prob);
309       prob = probs + IsRep + state;
310       IF_BIT_0(prob)
311       {
312         UPDATE_0(prob);
313         state += kNumStates;
314         prob = probs + LenCoder;
315       }
316       else
317       {
318         UPDATE_1(prob);
319         /*
320         // that case was checked before with kBadRepCode
321         if (checkDicSize == 0 && processedPos == 0)
322           return SZ_ERROR_DATA;
323         */
324         prob = probs + IsRepG0 + state;
325         IF_BIT_0(prob)
326         {
327           UPDATE_0(prob);
328           prob = probs + IsRep0Long + COMBINED_PS_STATE;
329           IF_BIT_0(prob)
330           {
331             UPDATE_0(prob);
332             dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];
333             dicPos++;
334             processedPos++;
335             state = state < kNumLitStates ? 9 : 11;
336             continue;
337           }
338           UPDATE_1(prob);
339         }
340         else
341         {
342           UInt32 distance;
343           UPDATE_1(prob);
344           prob = probs + IsRepG1 + state;
345           IF_BIT_0(prob)
346           {
347             UPDATE_0(prob);
348             distance = rep1;
349           }
350           else
351           {
352             UPDATE_1(prob);
353             prob = probs + IsRepG2 + state;
354             IF_BIT_0(prob)
355             {
356               UPDATE_0(prob);
357               distance = rep2;
358             }
359             else
360             {
361               UPDATE_1(prob);
362               distance = rep3;
363               rep3 = rep2;
364             }
365             rep2 = rep1;
366           }
367           rep1 = rep0;
368           rep0 = distance;
369         }
370         state = state < kNumLitStates ? 8 : 11;
371         prob = probs + RepLenCoder;
372       }
373 
374       #ifdef _LZMA_SIZE_OPT
375       {
376         unsigned lim, offset;
377         CLzmaProb *probLen = prob + LenChoice;
378         IF_BIT_0(probLen)
379         {
380           UPDATE_0(probLen);
381           probLen = prob + LenLow + GET_LEN_STATE;
382           offset = 0;
383           lim = (1 << kLenNumLowBits);
384         }
385         else
386         {
387           UPDATE_1(probLen);
388           probLen = prob + LenChoice2;
389           IF_BIT_0(probLen)
390           {
391             UPDATE_0(probLen);
392             probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);
393             offset = kLenNumLowSymbols;
394             lim = (1 << kLenNumLowBits);
395           }
396           else
397           {
398             UPDATE_1(probLen);
399             probLen = prob + LenHigh;
400             offset = kLenNumLowSymbols * 2;
401             lim = (1 << kLenNumHighBits);
402           }
403         }
404         TREE_DECODE(probLen, lim, len);
405         len += offset;
406       }
407       #else
408       {
409         CLzmaProb *probLen = prob + LenChoice;
410         IF_BIT_0(probLen)
411         {
412           UPDATE_0(probLen);
413           probLen = prob + LenLow + GET_LEN_STATE;
414           len = 1;
415           TREE_GET_BIT(probLen, len);
416           TREE_GET_BIT(probLen, len);
417           TREE_GET_BIT(probLen, len);
418           len -= 8;
419         }
420         else
421         {
422           UPDATE_1(probLen);
423           probLen = prob + LenChoice2;
424           IF_BIT_0(probLen)
425           {
426             UPDATE_0(probLen);
427             probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);
428             len = 1;
429             TREE_GET_BIT(probLen, len);
430             TREE_GET_BIT(probLen, len);
431             TREE_GET_BIT(probLen, len);
432           }
433           else
434           {
435             UPDATE_1(probLen);
436             probLen = prob + LenHigh;
437             TREE_DECODE(probLen, (1 << kLenNumHighBits), len);
438             len += kLenNumLowSymbols * 2;
439           }
440         }
441       }
442       #endif
443 
444       if (state >= kNumStates)
445       {
446         UInt32 distance;
447         prob = probs + PosSlot +
448             ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
449         TREE_6_DECODE(prob, distance);
450         if (distance >= kStartPosModelIndex)
451         {
452           unsigned posSlot = (unsigned)distance;
453           unsigned numDirectBits = (unsigned)(((distance >> 1) - 1));
454           distance = (2 | (distance & 1));
455           if (posSlot < kEndPosModelIndex)
456           {
457             distance <<= numDirectBits;
458             prob = probs + SpecPos;
459             {
460               UInt32 m = 1;
461               distance++;
462               do
463               {
464                 REV_BIT_VAR(prob, distance, m);
465               }
466               while (--numDirectBits);
467               distance -= m;
468             }
469           }
470           else
471           {
472             numDirectBits -= kNumAlignBits;
473             do
474             {
475               NORMALIZE
476               range >>= 1;
477 
478               {
479                 UInt32 t;
480                 code -= range;
481                 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
482                 distance = (distance << 1) + (t + 1);
483                 code += range & t;
484               }
485               /*
486               distance <<= 1;
487               if (code >= range)
488               {
489                 code -= range;
490                 distance |= 1;
491               }
492               */
493             }
494             while (--numDirectBits);
495             prob = probs + Align;
496             distance <<= kNumAlignBits;
497             {
498               unsigned i = 1;
499               REV_BIT_CONST(prob, i, 1);
500               REV_BIT_CONST(prob, i, 2);
501               REV_BIT_CONST(prob, i, 4);
502               REV_BIT_LAST (prob, i, 8);
503               distance |= i;
504             }
505             if (distance == (UInt32)0xFFFFFFFF)
506             {
507               len = kMatchSpecLenStart;
508               state -= kNumStates;
509               break;
510             }
511           }
512         }
513 
514         rep3 = rep2;
515         rep2 = rep1;
516         rep1 = rep0;
517         rep0 = distance + 1;
518         state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
519         if (distance >= (checkDicSize == 0 ? processedPos: checkDicSize))
520         {
521           p->dicPos = dicPos;
522           return SZ_ERROR_DATA;
523         }
524       }
525 
526       len += kMatchMinLen;
527 
528       {
529         SizeT rem;
530         unsigned curLen;
531         SizeT pos;
532 
533         if ((rem = limit - dicPos) == 0)
534         {
535           p->dicPos = dicPos;
536           return SZ_ERROR_DATA;
537         }
538 
539         curLen = ((rem < len) ? (unsigned)rem : len);
540         pos = dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0);
541 
542         processedPos += curLen;
543 
544         len -= curLen;
545         if (curLen <= dicBufSize - pos)
546         {
547           Byte *dest = dic + dicPos;
548           ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
549           const Byte *lim = dest + curLen;
550           dicPos += curLen;
551           do
552             *(dest) = (Byte)*(dest + src);
553           while (++dest != lim);
554         }
555         else
556         {
557           do
558           {
559             dic[dicPos++] = dic[pos];
560             if (++pos == dicBufSize)
561               pos = 0;
562           }
563           while (--curLen != 0);
564         }
565       }
566     }
567   }
568   while (dicPos < limit && buf < bufLimit);
569 
570   NORMALIZE;
571 
572   p->buf = buf;
573   p->range = range;
574   p->code = code;
575   p->remainLen = len;
576   p->dicPos = dicPos;
577   p->processedPos = processedPos;
578   p->reps[0] = rep0;
579   p->reps[1] = rep1;
580   p->reps[2] = rep2;
581   p->reps[3] = rep3;
582   p->state = state;
583 
584   return SZ_OK;
585 }
586 #endif
587 
LzmaDec_WriteRem(CLzmaDec * p,SizeT limit)588 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
589 {
590   if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
591   {
592     Byte *dic = p->dic;
593     SizeT dicPos = p->dicPos;
594     SizeT dicBufSize = p->dicBufSize;
595     unsigned len = (unsigned)p->remainLen;
596     SizeT rep0 = p->reps[0]; /* we use SizeT to avoid the BUG of VC14 for AMD64 */
597     SizeT rem = limit - dicPos;
598     if (rem < len)
599       len = (unsigned)(rem);
600 
601     if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
602       p->checkDicSize = p->prop.dicSize;
603 
604     p->processedPos += len;
605     p->remainLen -= len;
606     while (len != 0)
607     {
608       len--;
609       dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];
610       dicPos++;
611     }
612     p->dicPos = dicPos;
613   }
614 }
615 
616 
617 #define kRange0 0xFFFFFFFF
618 #define kBound0 ((kRange0 >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1))
619 #define kBadRepCode (kBound0 + (((kRange0 - kBound0) >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1)))
620 #if kBadRepCode != (0xC0000000 - 0x400)
621   #error Stop_Compiling_Bad_LZMA_Check
622 #endif
623 
LzmaDec_DecodeReal2(CLzmaDec * p,SizeT limit,const Byte * bufLimit)624 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
625 {
626   do
627   {
628     SizeT limit2 = limit;
629     if (p->checkDicSize == 0)
630     {
631       UInt32 rem = p->prop.dicSize - p->processedPos;
632       if (limit - p->dicPos > rem)
633         limit2 = p->dicPos + rem;
634 
635       if (p->processedPos == 0)
636         if (p->code >= kBadRepCode)
637           return SZ_ERROR_DATA;
638     }
639 
640     RINOK(LZMA_DECODE_REAL(p, limit2, bufLimit));
641 
642     if (p->checkDicSize == 0 && p->processedPos >= p->prop.dicSize)
643       p->checkDicSize = p->prop.dicSize;
644 
645     LzmaDec_WriteRem(p, limit);
646   }
647   while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
648 
649   return 0;
650 }
651 
652 typedef enum
653 {
654   DUMMY_ERROR, /* unexpected end of input stream */
655   DUMMY_LIT,
656   DUMMY_MATCH,
657   DUMMY_REP
658 } ELzmaDummy;
659 
LzmaDec_TryDummy(const CLzmaDec * p,const Byte * buf,SizeT inSize)660 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
661 {
662   UInt32 range = p->range;
663   UInt32 code = p->code;
664   const Byte *bufLimit = buf + inSize;
665   const CLzmaProb *probs = GET_PROBS;
666   unsigned state = (unsigned)p->state;
667   ELzmaDummy res;
668 
669   {
670     const CLzmaProb *prob;
671     UInt32 bound;
672     unsigned ttt;
673     unsigned posState = CALC_POS_STATE(p->processedPos, (1 << p->prop.pb) - 1);
674 
675     prob = probs + IsMatch + COMBINED_PS_STATE;
676     IF_BIT_0_CHECK(prob)
677     {
678       UPDATE_0_CHECK
679 
680       /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
681 
682       prob = probs + Literal;
683       if (p->checkDicSize != 0 || p->processedPos != 0)
684         prob += ((UInt32)LZMA_LIT_SIZE *
685             ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
686             (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
687 
688       if (state < kNumLitStates)
689       {
690         unsigned symbol = 1;
691         do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
692       }
693       else
694       {
695         unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
696             (p->dicPos < p->reps[0] ? p->dicBufSize : 0)];
697         unsigned offs = 0x100;
698         unsigned symbol = 1;
699         do
700         {
701           unsigned bit;
702           const CLzmaProb *probLit;
703           matchByte += matchByte;
704           bit = offs;
705           offs &= matchByte;
706           probLit = prob + (offs + bit + symbol);
707           GET_BIT2_CHECK(probLit, symbol, offs ^= bit; , ; )
708         }
709         while (symbol < 0x100);
710       }
711       res = DUMMY_LIT;
712     }
713     else
714     {
715       unsigned len;
716       UPDATE_1_CHECK;
717 
718       prob = probs + IsRep + state;
719       IF_BIT_0_CHECK(prob)
720       {
721         UPDATE_0_CHECK;
722         state = 0;
723         prob = probs + LenCoder;
724         res = DUMMY_MATCH;
725       }
726       else
727       {
728         UPDATE_1_CHECK;
729         res = DUMMY_REP;
730         prob = probs + IsRepG0 + state;
731         IF_BIT_0_CHECK(prob)
732         {
733           UPDATE_0_CHECK;
734           prob = probs + IsRep0Long + COMBINED_PS_STATE;
735           IF_BIT_0_CHECK(prob)
736           {
737             UPDATE_0_CHECK;
738             NORMALIZE_CHECK;
739             return DUMMY_REP;
740           }
741           else
742           {
743             UPDATE_1_CHECK;
744           }
745         }
746         else
747         {
748           UPDATE_1_CHECK;
749           prob = probs + IsRepG1 + state;
750           IF_BIT_0_CHECK(prob)
751           {
752             UPDATE_0_CHECK;
753           }
754           else
755           {
756             UPDATE_1_CHECK;
757             prob = probs + IsRepG2 + state;
758             IF_BIT_0_CHECK(prob)
759             {
760               UPDATE_0_CHECK;
761             }
762             else
763             {
764               UPDATE_1_CHECK;
765             }
766           }
767         }
768         state = kNumStates;
769         prob = probs + RepLenCoder;
770       }
771       {
772         unsigned limit, offset;
773         const CLzmaProb *probLen = prob + LenChoice;
774         IF_BIT_0_CHECK(probLen)
775         {
776           UPDATE_0_CHECK;
777           probLen = prob + LenLow + GET_LEN_STATE;
778           offset = 0;
779           limit = 1 << kLenNumLowBits;
780         }
781         else
782         {
783           UPDATE_1_CHECK;
784           probLen = prob + LenChoice2;
785           IF_BIT_0_CHECK(probLen)
786           {
787             UPDATE_0_CHECK;
788             probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);
789             offset = kLenNumLowSymbols;
790             limit = 1 << kLenNumLowBits;
791           }
792           else
793           {
794             UPDATE_1_CHECK;
795             probLen = prob + LenHigh;
796             offset = kLenNumLowSymbols * 2;
797             limit = 1 << kLenNumHighBits;
798           }
799         }
800         TREE_DECODE_CHECK(probLen, limit, len);
801         len += offset;
802       }
803 
804       if (state < 4)
805       {
806         unsigned posSlot;
807         prob = probs + PosSlot +
808             ((len < kNumLenToPosStates - 1 ? len : kNumLenToPosStates - 1) <<
809             kNumPosSlotBits);
810         TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
811         if (posSlot >= kStartPosModelIndex)
812         {
813           unsigned numDirectBits = ((posSlot >> 1) - 1);
814 
815           /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
816 
817           if (posSlot < kEndPosModelIndex)
818           {
819             prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits);
820           }
821           else
822           {
823             numDirectBits -= kNumAlignBits;
824             do
825             {
826               NORMALIZE_CHECK
827               range >>= 1;
828               code -= range & (((code - range) >> 31) - 1);
829               /* if (code >= range) code -= range; */
830             }
831             while (--numDirectBits);
832             prob = probs + Align;
833             numDirectBits = kNumAlignBits;
834           }
835           {
836             unsigned i = 1;
837             unsigned m = 1;
838             do
839             {
840               REV_BIT_CHECK(prob, i, m);
841             }
842             while (--numDirectBits);
843           }
844         }
845       }
846     }
847   }
848   NORMALIZE_CHECK;
849   return res;
850 }
851 
852 
LzmaDec_InitDicAndState(CLzmaDec * p,Bool initDic,Bool initState)853 void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
854 {
855   p->remainLen = kMatchSpecLenStart + 1;
856   p->tempBufSize = 0;
857 
858   if (initDic)
859   {
860     p->processedPos = 0;
861     p->checkDicSize = 0;
862     p->remainLen = kMatchSpecLenStart + 2;
863   }
864   if (initState)
865     p->remainLen = kMatchSpecLenStart + 2;
866 }
867 
LzmaDec_Init(CLzmaDec * p)868 void LzmaDec_Init(CLzmaDec *p)
869 {
870   p->dicPos = 0;
871   LzmaDec_InitDicAndState(p, True, True);
872 }
873 
874 
LzmaDec_DecodeToDic(CLzmaDec * p,SizeT dicLimit,const Byte * src,SizeT * srcLen,ELzmaFinishMode finishMode,ELzmaStatus * status)875 SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
876     ELzmaFinishMode finishMode, ELzmaStatus *status)
877 {
878   SizeT inSize = *srcLen;
879   (*srcLen) = 0;
880 
881   *status = LZMA_STATUS_NOT_SPECIFIED;
882 
883   if (p->remainLen > kMatchSpecLenStart)
884   {
885     for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
886       p->tempBuf[p->tempBufSize++] = *src++;
887     if (p->tempBufSize != 0 && p->tempBuf[0] != 0)
888       return SZ_ERROR_DATA;
889     if (p->tempBufSize < RC_INIT_SIZE)
890     {
891       *status = LZMA_STATUS_NEEDS_MORE_INPUT;
892       return SZ_OK;
893     }
894     p->code =
895         ((UInt32)p->tempBuf[1] << 24)
896       | ((UInt32)p->tempBuf[2] << 16)
897       | ((UInt32)p->tempBuf[3] << 8)
898       | ((UInt32)p->tempBuf[4]);
899     p->range = 0xFFFFFFFF;
900     p->tempBufSize = 0;
901 
902     if (p->remainLen > kMatchSpecLenStart + 1)
903     {
904       SizeT numProbs = LzmaProps_GetNumProbs(&p->prop);
905       SizeT i;
906       CLzmaProb *probs = p->probs;
907       for (i = 0; i < numProbs; i++)
908         probs[i] = kBitModelTotal >> 1;
909       p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
910       p->state = 0;
911     }
912 
913     p->remainLen = 0;
914   }
915 
916   LzmaDec_WriteRem(p, dicLimit);
917 
918   while (p->remainLen != kMatchSpecLenStart)
919   {
920       int checkEndMarkNow = 0;
921 
922       if (p->dicPos >= dicLimit)
923       {
924         if (p->remainLen == 0 && p->code == 0)
925         {
926           *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
927           return SZ_OK;
928         }
929         if (finishMode == LZMA_FINISH_ANY)
930         {
931           *status = LZMA_STATUS_NOT_FINISHED;
932           return SZ_OK;
933         }
934         if (p->remainLen != 0)
935         {
936           *status = LZMA_STATUS_NOT_FINISHED;
937           return SZ_ERROR_DATA;
938         }
939         checkEndMarkNow = 1;
940       }
941 
942       if (p->tempBufSize == 0)
943       {
944         SizeT processed;
945         const Byte *bufLimit;
946         if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
947         {
948           int dummyRes = LzmaDec_TryDummy(p, src, inSize);
949           if (dummyRes == DUMMY_ERROR)
950           {
951             memcpy(p->tempBuf, src, inSize);
952             p->tempBufSize = (unsigned)inSize;
953             (*srcLen) += inSize;
954             *status = LZMA_STATUS_NEEDS_MORE_INPUT;
955             return SZ_OK;
956           }
957           if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
958           {
959             *status = LZMA_STATUS_NOT_FINISHED;
960             return SZ_ERROR_DATA;
961           }
962           bufLimit = src;
963         }
964         else
965           bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
966         p->buf = src;
967         if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
968           return SZ_ERROR_DATA;
969         processed = (SizeT)(p->buf - src);
970         (*srcLen) += processed;
971         src += processed;
972         inSize -= processed;
973       }
974       else
975       {
976         unsigned rem = p->tempBufSize, lookAhead = 0;
977         while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
978           p->tempBuf[rem++] = src[lookAhead++];
979         p->tempBufSize = rem;
980         if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
981         {
982           int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
983           if (dummyRes == DUMMY_ERROR)
984           {
985             (*srcLen) += lookAhead;
986             *status = LZMA_STATUS_NEEDS_MORE_INPUT;
987             return SZ_OK;
988           }
989           if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
990           {
991             *status = LZMA_STATUS_NOT_FINISHED;
992             return SZ_ERROR_DATA;
993           }
994         }
995         p->buf = p->tempBuf;
996         if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
997           return SZ_ERROR_DATA;
998 
999         {
1000           unsigned kkk = (unsigned)(p->buf - p->tempBuf);
1001           if (rem < kkk)
1002             return SZ_ERROR_FAIL; /* some internal error */
1003           rem -= kkk;
1004           if (lookAhead < rem)
1005             return SZ_ERROR_FAIL; /* some internal error */
1006           lookAhead -= rem;
1007         }
1008         (*srcLen) += lookAhead;
1009         src += lookAhead;
1010         inSize -= lookAhead;
1011         p->tempBufSize = 0;
1012       }
1013   }
1014 
1015   if (p->code != 0)
1016     return SZ_ERROR_DATA;
1017   *status = LZMA_STATUS_FINISHED_WITH_MARK;
1018   return SZ_OK;
1019 }
1020 
1021 
LzmaDec_DecodeToBuf(CLzmaDec * p,Byte * dest,SizeT * destLen,const Byte * src,SizeT * srcLen,ELzmaFinishMode finishMode,ELzmaStatus * status)1022 SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
1023 {
1024   SizeT outSize = *destLen;
1025   SizeT inSize = *srcLen;
1026   *srcLen = *destLen = 0;
1027   for (;;)
1028   {
1029     SizeT inSizeCur = inSize, outSizeCur, dicPos;
1030     ELzmaFinishMode curFinishMode;
1031     SRes res;
1032     if (p->dicPos == p->dicBufSize)
1033       p->dicPos = 0;
1034     dicPos = p->dicPos;
1035     if (outSize > p->dicBufSize - dicPos)
1036     {
1037       outSizeCur = p->dicBufSize;
1038       curFinishMode = LZMA_FINISH_ANY;
1039     }
1040     else
1041     {
1042       outSizeCur = dicPos + outSize;
1043       curFinishMode = finishMode;
1044     }
1045 
1046     res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
1047     src += inSizeCur;
1048     inSize -= inSizeCur;
1049     *srcLen += inSizeCur;
1050     outSizeCur = p->dicPos - dicPos;
1051     memcpy(dest, p->dic + dicPos, outSizeCur);
1052     dest += outSizeCur;
1053     outSize -= outSizeCur;
1054     *destLen += outSizeCur;
1055     if (res != 0)
1056       return res;
1057     if (outSizeCur == 0 || outSize == 0)
1058       return SZ_OK;
1059   }
1060 }
1061 
LzmaDec_FreeProbs(CLzmaDec * p,ISzAllocPtr alloc)1062 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAllocPtr alloc)
1063 {
1064   ISzAlloc_Free(alloc, p->probs);
1065   p->probs = NULL;
1066 }
1067 
LzmaDec_FreeDict(CLzmaDec * p,ISzAllocPtr alloc)1068 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAllocPtr alloc)
1069 {
1070   ISzAlloc_Free(alloc, p->dic);
1071   p->dic = NULL;
1072 }
1073 
LzmaDec_Free(CLzmaDec * p,ISzAllocPtr alloc)1074 void LzmaDec_Free(CLzmaDec *p, ISzAllocPtr alloc)
1075 {
1076   LzmaDec_FreeProbs(p, alloc);
1077   LzmaDec_FreeDict(p, alloc);
1078 }
1079 
LzmaProps_Decode(CLzmaProps * p,const Byte * data,unsigned size)1080 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
1081 {
1082   UInt32 dicSize;
1083   Byte d;
1084 
1085   if (size < LZMA_PROPS_SIZE)
1086     return SZ_ERROR_UNSUPPORTED;
1087   else
1088     dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
1089 
1090   if (dicSize < LZMA_DIC_MIN)
1091     dicSize = LZMA_DIC_MIN;
1092   p->dicSize = dicSize;
1093 
1094   d = data[0];
1095   if (d >= (9 * 5 * 5))
1096     return SZ_ERROR_UNSUPPORTED;
1097 
1098   p->lc = (Byte)(d % 9);
1099   d /= 9;
1100   p->pb = (Byte)(d / 5);
1101   p->lp = (Byte)(d % 5);
1102 
1103   return SZ_OK;
1104 }
1105 
LzmaDec_AllocateProbs2(CLzmaDec * p,const CLzmaProps * propNew,ISzAllocPtr alloc)1106 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAllocPtr alloc)
1107 {
1108   UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
1109   if (!p->probs || numProbs != p->numProbs)
1110   {
1111     LzmaDec_FreeProbs(p, alloc);
1112     p->probs = (CLzmaProb *)ISzAlloc_Alloc(alloc, numProbs * sizeof(CLzmaProb));
1113     if (!p->probs)
1114       return SZ_ERROR_MEM;
1115     p->probs_1664 = p->probs + 1664;
1116     p->numProbs = numProbs;
1117   }
1118   return SZ_OK;
1119 }
1120 
LzmaDec_AllocateProbs(CLzmaDec * p,const Byte * props,unsigned propsSize,ISzAllocPtr alloc)1121 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAllocPtr alloc)
1122 {
1123   CLzmaProps propNew;
1124   RINOK(LzmaProps_Decode(&propNew, props, propsSize));
1125   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
1126   p->prop = propNew;
1127   return SZ_OK;
1128 }
1129 
LzmaDec_Allocate(CLzmaDec * p,const Byte * props,unsigned propsSize,ISzAllocPtr alloc)1130 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAllocPtr alloc)
1131 {
1132   CLzmaProps propNew;
1133   SizeT dicBufSize;
1134   RINOK(LzmaProps_Decode(&propNew, props, propsSize));
1135   RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
1136 
1137   {
1138     UInt32 dictSize = propNew.dicSize;
1139     SizeT mask = ((UInt32)1 << 12) - 1;
1140          if (dictSize >= ((UInt32)1 << 30)) mask = ((UInt32)1 << 22) - 1;
1141     else if (dictSize >= ((UInt32)1 << 22)) mask = ((UInt32)1 << 20) - 1;;
1142     dicBufSize = ((SizeT)dictSize + mask) & ~mask;
1143     if (dicBufSize < dictSize)
1144       dicBufSize = dictSize;
1145   }
1146 
1147   if (!p->dic || dicBufSize != p->dicBufSize)
1148   {
1149     LzmaDec_FreeDict(p, alloc);
1150     p->dic = (Byte *)ISzAlloc_Alloc(alloc, dicBufSize);
1151     if (!p->dic)
1152     {
1153       LzmaDec_FreeProbs(p, alloc);
1154       return SZ_ERROR_MEM;
1155     }
1156   }
1157   p->dicBufSize = dicBufSize;
1158   p->prop = propNew;
1159   return SZ_OK;
1160 }
1161 
LzmaDecode(Byte * dest,SizeT * destLen,const Byte * src,SizeT * srcLen,const Byte * propData,unsigned propSize,ELzmaFinishMode finishMode,ELzmaStatus * status,ISzAllocPtr alloc)1162 SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
1163     const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
1164     ELzmaStatus *status, ISzAllocPtr alloc)
1165 {
1166   CLzmaDec p;
1167   SRes res;
1168   SizeT outSize = *destLen, inSize = *srcLen;
1169   *destLen = *srcLen = 0;
1170   *status = LZMA_STATUS_NOT_SPECIFIED;
1171   if (inSize < RC_INIT_SIZE)
1172     return SZ_ERROR_INPUT_EOF;
1173   LzmaDec_Construct(&p);
1174   RINOK(LzmaDec_AllocateProbs(&p, propData, propSize, alloc));
1175   p.dic = dest;
1176   p.dicBufSize = outSize;
1177   LzmaDec_Init(&p);
1178   *srcLen = inSize;
1179   res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
1180   *destLen = p.dicPos;
1181   if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
1182     res = SZ_ERROR_INPUT_EOF;
1183   LzmaDec_FreeProbs(&p, alloc);
1184   return res;
1185 }
1186