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