1/* LzmaDec.c -- LZMA Decoder
22015-01-01 : 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 768
118
119#define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
120
121#if Literal != LZMA_BASE_SIZE
122StopCompilingDueBUG
123#endif
124
125#define LZMA_DIC_MIN (1 << 12)
126
127/* First LZMA-symbol is always decoded.
128And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
129Out:
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
137    = kMatchSpecLenStart + 2 : State Init Marker
138*/
139
140static 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 (checkDicSize != 0 || processedPos != 0)
176        prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +
177        (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
178
179      if (state < kNumLitStates)
180      {
181        state -= (state < 4) ? state : 3;
182        symbol = 1;
183        #ifdef _LZMA_SIZE_OPT
184        do { NORMAL_LITER_DEC } while (symbol < 0x100);
185        #else
186        NORMAL_LITER_DEC
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        #endif
195      }
196      else
197      {
198        unsigned matchByte = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
199        unsigned offs = 0x100;
200        state -= (state < 10) ? 3 : 6;
201        symbol = 1;
202        #ifdef _LZMA_SIZE_OPT
203        do
204        {
205          unsigned bit;
206          CLzmaProb *probLit;
207          MATCHED_LITER_DEC
208        }
209        while (symbol < 0x100);
210        #else
211        {
212          unsigned bit;
213          CLzmaProb *probLit;
214          MATCHED_LITER_DEC
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        }
223        #endif
224      }
225      dic[dicPos++] = (Byte)symbol;
226      processedPos++;
227      continue;
228    }
229    else
230    {
231      UPDATE_1(prob);
232      prob = probs + IsRep + state;
233      IF_BIT_0(prob)
234      {
235        UPDATE_0(prob);
236        state += kNumStates;
237        prob = probs + LenCoder;
238      }
239      else
240      {
241        UPDATE_1(prob);
242        if (checkDicSize == 0 && processedPos == 0)
243          return SZ_ERROR_DATA;
244        prob = probs + IsRepG0 + state;
245        IF_BIT_0(prob)
246        {
247          UPDATE_0(prob);
248          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
249          IF_BIT_0(prob)
250          {
251            UPDATE_0(prob);
252            dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
253            dicPos++;
254            processedPos++;
255            state = state < kNumLitStates ? 9 : 11;
256            continue;
257          }
258          UPDATE_1(prob);
259        }
260        else
261        {
262          UInt32 distance;
263          UPDATE_1(prob);
264          prob = probs + IsRepG1 + state;
265          IF_BIT_0(prob)
266          {
267            UPDATE_0(prob);
268            distance = rep1;
269          }
270          else
271          {
272            UPDATE_1(prob);
273            prob = probs + IsRepG2 + state;
274            IF_BIT_0(prob)
275            {
276              UPDATE_0(prob);
277              distance = rep2;
278            }
279            else
280            {
281              UPDATE_1(prob);
282              distance = rep3;
283              rep3 = rep2;
284            }
285            rep2 = rep1;
286          }
287          rep1 = rep0;
288          rep0 = distance;
289        }
290        state = state < kNumLitStates ? 8 : 11;
291        prob = probs + RepLenCoder;
292      }
293      {
294        unsigned limit, offset;
295        CLzmaProb *probLen = prob + LenChoice;
296        IF_BIT_0(probLen)
297        {
298          UPDATE_0(probLen);
299          probLen = prob + LenLow + (posState << kLenNumLowBits);
300          offset = 0;
301          limit = (1 << kLenNumLowBits);
302        }
303        else
304        {
305          UPDATE_1(probLen);
306          probLen = prob + LenChoice2;
307          IF_BIT_0(probLen)
308          {
309            UPDATE_0(probLen);
310            probLen = prob + LenMid + (posState << kLenNumMidBits);
311            offset = kLenNumLowSymbols;
312            limit = (1 << kLenNumMidBits);
313          }
314          else
315          {
316            UPDATE_1(probLen);
317            probLen = prob + LenHigh;
318            offset = kLenNumLowSymbols + kLenNumMidSymbols;
319            limit = (1 << kLenNumHighBits);
320          }
321        }
322        TREE_DECODE(probLen, limit, len);
323        len += offset;
324      }
325
326      if (state >= kNumStates)
327      {
328        UInt32 distance;
329        prob = probs + PosSlot +
330            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
331        TREE_6_DECODE(prob, distance);
332        if (distance >= kStartPosModelIndex)
333        {
334          unsigned posSlot = (unsigned)distance;
335          int numDirectBits = (int)(((distance >> 1) - 1));
336          distance = (2 | (distance & 1));
337          if (posSlot < kEndPosModelIndex)
338          {
339            distance <<= numDirectBits;
340            prob = probs + SpecPos + distance - posSlot - 1;
341            {
342              UInt32 mask = 1;
343              unsigned i = 1;
344              do
345              {
346                GET_BIT2(prob + i, i, ; , distance |= mask);
347                mask <<= 1;
348              }
349              while (--numDirectBits != 0);
350            }
351          }
352          else
353          {
354            numDirectBits -= kNumAlignBits;
355            do
356            {
357              NORMALIZE
358              range >>= 1;
359
360              {
361                UInt32 t;
362                code -= range;
363                t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
364                distance = (distance << 1) + (t + 1);
365                code += range & t;
366              }
367              /*
368              distance <<= 1;
369              if (code >= range)
370              {
371                code -= range;
372                distance |= 1;
373              }
374              */
375            }
376            while (--numDirectBits != 0);
377            prob = probs + Align;
378            distance <<= kNumAlignBits;
379            {
380              unsigned i = 1;
381              GET_BIT2(prob + i, i, ; , distance |= 1);
382              GET_BIT2(prob + i, i, ; , distance |= 2);
383              GET_BIT2(prob + i, i, ; , distance |= 4);
384              GET_BIT2(prob + i, i, ; , distance |= 8);
385            }
386            if (distance == (UInt32)0xFFFFFFFF)
387            {
388              len += kMatchSpecLenStart;
389              state -= kNumStates;
390              break;
391            }
392          }
393        }
394        rep3 = rep2;
395        rep2 = rep1;
396        rep1 = rep0;
397        rep0 = distance + 1;
398        if (checkDicSize == 0)
399        {
400          if (distance >= processedPos)
401            return SZ_ERROR_DATA;
402        }
403        else if (distance >= checkDicSize)
404          return SZ_ERROR_DATA;
405        state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
406      }
407
408      len += kMatchMinLen;
409
410      if (limit == dicPos)
411        return SZ_ERROR_DATA;
412      {
413        SizeT rem = limit - dicPos;
414        unsigned curLen = ((rem < len) ? (unsigned)rem : len);
415        SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
416
417        processedPos += curLen;
418
419        len -= curLen;
420        if (pos + curLen <= dicBufSize)
421        {
422          Byte *dest = dic + dicPos;
423          ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
424          const Byte *lim = dest + curLen;
425          dicPos += curLen;
426          do
427            *(dest) = (Byte)*(dest + src);
428          while (++dest != lim);
429        }
430        else
431        {
432          do
433          {
434            dic[dicPos++] = dic[pos];
435            if (++pos == dicBufSize)
436              pos = 0;
437          }
438          while (--curLen != 0);
439        }
440      }
441    }
442  }
443  while (dicPos < limit && buf < bufLimit);
444  NORMALIZE;
445  p->buf = buf;
446  p->range = range;
447  p->code = code;
448  p->remainLen = len;
449  p->dicPos = dicPos;
450  p->processedPos = processedPos;
451  p->reps[0] = rep0;
452  p->reps[1] = rep1;
453  p->reps[2] = rep2;
454  p->reps[3] = rep3;
455  p->state = state;
456
457  return SZ_OK;
458}
459
460static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
461{
462  if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
463  {
464    Byte *dic = p->dic;
465    SizeT dicPos = p->dicPos;
466    SizeT dicBufSize = p->dicBufSize;
467    unsigned len = p->remainLen;
468    UInt32 rep0 = p->reps[0];
469    if (limit - dicPos < len)
470      len = (unsigned)(limit - dicPos);
471
472    if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
473      p->checkDicSize = p->prop.dicSize;
474
475    p->processedPos += len;
476    p->remainLen -= len;
477    while (len != 0)
478    {
479      len--;
480      dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
481      dicPos++;
482    }
483    p->dicPos = dicPos;
484  }
485}
486
487static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
488{
489  do
490  {
491    SizeT limit2 = limit;
492    if (p->checkDicSize == 0)
493    {
494      UInt32 rem = p->prop.dicSize - p->processedPos;
495      if (limit - p->dicPos > rem)
496        limit2 = p->dicPos + rem;
497    }
498    RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
499    if (p->processedPos >= p->prop.dicSize)
500      p->checkDicSize = p->prop.dicSize;
501    LzmaDec_WriteRem(p, limit);
502  }
503  while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
504
505  if (p->remainLen > kMatchSpecLenStart)
506  {
507    p->remainLen = kMatchSpecLenStart;
508  }
509  return 0;
510}
511
512typedef enum
513{
514  DUMMY_ERROR, /* unexpected end of input stream */
515  DUMMY_LIT,
516  DUMMY_MATCH,
517  DUMMY_REP
518} ELzmaDummy;
519
520static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
521{
522  UInt32 range = p->range;
523  UInt32 code = p->code;
524  const Byte *bufLimit = buf + inSize;
525  CLzmaProb *probs = p->probs;
526  unsigned state = p->state;
527  ELzmaDummy res;
528
529  {
530    CLzmaProb *prob;
531    UInt32 bound;
532    unsigned ttt;
533    unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
534
535    prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
536    IF_BIT_0_CHECK(prob)
537    {
538      UPDATE_0_CHECK
539
540      /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
541
542      prob = probs + Literal;
543      if (p->checkDicSize != 0 || p->processedPos != 0)
544        prob += (LZMA_LIT_SIZE *
545          ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
546          (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
547
548      if (state < kNumLitStates)
549      {
550        unsigned symbol = 1;
551        do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
552      }
553      else
554      {
555        unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
556            ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
557        unsigned offs = 0x100;
558        unsigned symbol = 1;
559        do
560        {
561          unsigned bit;
562          CLzmaProb *probLit;
563          matchByte <<= 1;
564          bit = (matchByte & offs);
565          probLit = prob + offs + bit + symbol;
566          GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
567        }
568        while (symbol < 0x100);
569      }
570      res = DUMMY_LIT;
571    }
572    else
573    {
574      unsigned len;
575      UPDATE_1_CHECK;
576
577      prob = probs + IsRep + state;
578      IF_BIT_0_CHECK(prob)
579      {
580        UPDATE_0_CHECK;
581        state = 0;
582        prob = probs + LenCoder;
583        res = DUMMY_MATCH;
584      }
585      else
586      {
587        UPDATE_1_CHECK;
588        res = DUMMY_REP;
589        prob = probs + IsRepG0 + state;
590        IF_BIT_0_CHECK(prob)
591        {
592          UPDATE_0_CHECK;
593          prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
594          IF_BIT_0_CHECK(prob)
595          {
596            UPDATE_0_CHECK;
597            NORMALIZE_CHECK;
598            return DUMMY_REP;
599          }
600          else
601          {
602            UPDATE_1_CHECK;
603          }
604        }
605        else
606        {
607          UPDATE_1_CHECK;
608          prob = probs + IsRepG1 + state;
609          IF_BIT_0_CHECK(prob)
610          {
611            UPDATE_0_CHECK;
612          }
613          else
614          {
615            UPDATE_1_CHECK;
616            prob = probs + IsRepG2 + state;
617            IF_BIT_0_CHECK(prob)
618            {
619              UPDATE_0_CHECK;
620            }
621            else
622            {
623              UPDATE_1_CHECK;
624            }
625          }
626        }
627        state = kNumStates;
628        prob = probs + RepLenCoder;
629      }
630      {
631        unsigned limit, offset;
632        CLzmaProb *probLen = prob + LenChoice;
633        IF_BIT_0_CHECK(probLen)
634        {
635          UPDATE_0_CHECK;
636          probLen = prob + LenLow + (posState << kLenNumLowBits);
637          offset = 0;
638          limit = 1 << kLenNumLowBits;
639        }
640        else
641        {
642          UPDATE_1_CHECK;
643          probLen = prob + LenChoice2;
644          IF_BIT_0_CHECK(probLen)
645          {
646            UPDATE_0_CHECK;
647            probLen = prob + LenMid + (posState << kLenNumMidBits);
648            offset = kLenNumLowSymbols;
649            limit = 1 << kLenNumMidBits;
650          }
651          else
652          {
653            UPDATE_1_CHECK;
654            probLen = prob + LenHigh;
655            offset = kLenNumLowSymbols + kLenNumMidSymbols;
656            limit = 1 << kLenNumHighBits;
657          }
658        }
659        TREE_DECODE_CHECK(probLen, limit, len);
660        len += offset;
661      }
662
663      if (state < 4)
664      {
665        unsigned posSlot;
666        prob = probs + PosSlot +
667            ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
668            kNumPosSlotBits);
669        TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
670        if (posSlot >= kStartPosModelIndex)
671        {
672          int numDirectBits = ((posSlot >> 1) - 1);
673
674          /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
675
676          if (posSlot < kEndPosModelIndex)
677          {
678            prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
679          }
680          else
681          {
682            numDirectBits -= kNumAlignBits;
683            do
684            {
685              NORMALIZE_CHECK
686              range >>= 1;
687              code -= range & (((code - range) >> 31) - 1);
688              /* if (code >= range) code -= range; */
689            }
690            while (--numDirectBits != 0);
691            prob = probs + Align;
692            numDirectBits = kNumAlignBits;
693          }
694          {
695            unsigned i = 1;
696            do
697            {
698              GET_BIT_CHECK(prob + i, i);
699            }
700            while (--numDirectBits != 0);
701          }
702        }
703      }
704    }
705  }
706  NORMALIZE_CHECK;
707  return res;
708}
709
710
711static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)
712{
713  p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
714  p->range = 0xFFFFFFFF;
715  p->needFlush = 0;
716}
717
718void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
719{
720  p->needFlush = 1;
721  p->remainLen = 0;
722  p->tempBufSize = 0;
723
724  if (initDic)
725  {
726    p->processedPos = 0;
727    p->checkDicSize = 0;
728    p->needInitState = 1;
729  }
730  if (initState)
731    p->needInitState = 1;
732}
733
734void LzmaDec_Init(CLzmaDec *p)
735{
736  p->dicPos = 0;
737  LzmaDec_InitDicAndState(p, True, True);
738}
739
740static void LzmaDec_InitStateReal(CLzmaDec *p)
741{
742  UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
743  UInt32 i;
744  CLzmaProb *probs = p->probs;
745  for (i = 0; i < numProbs; i++)
746    probs[i] = kBitModelTotal >> 1;
747  p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
748  p->state = 0;
749  p->needInitState = 0;
750}
751
752SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
753    ELzmaFinishMode finishMode, ELzmaStatus *status)
754{
755  SizeT inSize = *srcLen;
756  (*srcLen) = 0;
757  LzmaDec_WriteRem(p, dicLimit);
758
759  *status = LZMA_STATUS_NOT_SPECIFIED;
760
761  while (p->remainLen != kMatchSpecLenStart)
762  {
763      int checkEndMarkNow;
764
765      if (p->needFlush != 0)
766      {
767        for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
768          p->tempBuf[p->tempBufSize++] = *src++;
769        if (p->tempBufSize < RC_INIT_SIZE)
770        {
771          *status = LZMA_STATUS_NEEDS_MORE_INPUT;
772          return SZ_OK;
773        }
774        if (p->tempBuf[0] != 0)
775          return SZ_ERROR_DATA;
776
777        LzmaDec_InitRc(p, p->tempBuf);
778        p->tempBufSize = 0;
779      }
780
781      checkEndMarkNow = 0;
782      if (p->dicPos >= dicLimit)
783      {
784        if (p->remainLen == 0 && p->code == 0)
785        {
786          *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
787          return SZ_OK;
788        }
789        if (finishMode == LZMA_FINISH_ANY)
790        {
791          *status = LZMA_STATUS_NOT_FINISHED;
792          return SZ_OK;
793        }
794        if (p->remainLen != 0)
795        {
796          *status = LZMA_STATUS_NOT_FINISHED;
797          return SZ_ERROR_DATA;
798        }
799        checkEndMarkNow = 1;
800      }
801
802      if (p->needInitState)
803        LzmaDec_InitStateReal(p);
804
805      if (p->tempBufSize == 0)
806      {
807        SizeT processed;
808        const Byte *bufLimit;
809        if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
810        {
811          int dummyRes = LzmaDec_TryDummy(p, src, inSize);
812          if (dummyRes == DUMMY_ERROR)
813          {
814            memcpy(p->tempBuf, src, inSize);
815            p->tempBufSize = (unsigned)inSize;
816            (*srcLen) += inSize;
817            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
818            return SZ_OK;
819          }
820          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
821          {
822            *status = LZMA_STATUS_NOT_FINISHED;
823            return SZ_ERROR_DATA;
824          }
825          bufLimit = src;
826        }
827        else
828          bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
829        p->buf = src;
830        if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
831          return SZ_ERROR_DATA;
832        processed = (SizeT)(p->buf - src);
833        (*srcLen) += processed;
834        src += processed;
835        inSize -= processed;
836      }
837      else
838      {
839        unsigned rem = p->tempBufSize, lookAhead = 0;
840        while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
841          p->tempBuf[rem++] = src[lookAhead++];
842        p->tempBufSize = rem;
843        if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
844        {
845          int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
846          if (dummyRes == DUMMY_ERROR)
847          {
848            (*srcLen) += lookAhead;
849            *status = LZMA_STATUS_NEEDS_MORE_INPUT;
850            return SZ_OK;
851          }
852          if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
853          {
854            *status = LZMA_STATUS_NOT_FINISHED;
855            return SZ_ERROR_DATA;
856          }
857        }
858        p->buf = p->tempBuf;
859        if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
860          return SZ_ERROR_DATA;
861        lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
862        (*srcLen) += lookAhead;
863        src += lookAhead;
864        inSize -= lookAhead;
865        p->tempBufSize = 0;
866      }
867  }
868  if (p->code == 0)
869    *status = LZMA_STATUS_FINISHED_WITH_MARK;
870  return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
871}
872
873SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
874{
875  SizeT outSize = *destLen;
876  SizeT inSize = *srcLen;
877  *srcLen = *destLen = 0;
878  for (;;)
879  {
880    SizeT inSizeCur = inSize, outSizeCur, dicPos;
881    ELzmaFinishMode curFinishMode;
882    SRes res;
883    if (p->dicPos == p->dicBufSize)
884      p->dicPos = 0;
885    dicPos = p->dicPos;
886    if (outSize > p->dicBufSize - dicPos)
887    {
888      outSizeCur = p->dicBufSize;
889      curFinishMode = LZMA_FINISH_ANY;
890    }
891    else
892    {
893      outSizeCur = dicPos + outSize;
894      curFinishMode = finishMode;
895    }
896
897    res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
898    src += inSizeCur;
899    inSize -= inSizeCur;
900    *srcLen += inSizeCur;
901    outSizeCur = p->dicPos - dicPos;
902    memcpy(dest, p->dic + dicPos, outSizeCur);
903    dest += outSizeCur;
904    outSize -= outSizeCur;
905    *destLen += outSizeCur;
906    if (res != 0)
907      return res;
908    if (outSizeCur == 0 || outSize == 0)
909      return SZ_OK;
910  }
911}
912
913void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)
914{
915  alloc->Free(alloc, p->probs);
916  p->probs = 0;
917}
918
919static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
920{
921  alloc->Free(alloc, p->dic);
922  p->dic = 0;
923}
924
925void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
926{
927  LzmaDec_FreeProbs(p, alloc);
928  LzmaDec_FreeDict(p, alloc);
929}
930
931SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
932{
933  UInt32 dicSize;
934  Byte d;
935
936  if (size < LZMA_PROPS_SIZE)
937    return SZ_ERROR_UNSUPPORTED;
938  else
939    dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
940
941  if (dicSize < LZMA_DIC_MIN)
942    dicSize = LZMA_DIC_MIN;
943  p->dicSize = dicSize;
944
945  d = data[0];
946  if (d >= (9 * 5 * 5))
947    return SZ_ERROR_UNSUPPORTED;
948
949  p->lc = d % 9;
950  d /= 9;
951  p->pb = d / 5;
952  p->lp = d % 5;
953
954  return SZ_OK;
955}
956
957static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)
958{
959  UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
960  if (p->probs == 0 || numProbs != p->numProbs)
961  {
962    LzmaDec_FreeProbs(p, alloc);
963    p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
964    p->numProbs = numProbs;
965    if (p->probs == 0)
966      return SZ_ERROR_MEM;
967  }
968  return SZ_OK;
969}
970
971SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
972{
973  CLzmaProps propNew;
974  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
975  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
976  p->prop = propNew;
977  return SZ_OK;
978}
979
980SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
981{
982  CLzmaProps propNew;
983  SizeT dicBufSize;
984  RINOK(LzmaProps_Decode(&propNew, props, propsSize));
985  RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
986  dicBufSize = propNew.dicSize;
987  if (p->dic == 0 || dicBufSize != p->dicBufSize)
988  {
989    LzmaDec_FreeDict(p, alloc);
990    p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
991    if (p->dic == 0)
992    {
993      LzmaDec_FreeProbs(p, alloc);
994      return SZ_ERROR_MEM;
995    }
996  }
997  p->dicBufSize = dicBufSize;
998  p->prop = propNew;
999  return SZ_OK;
1000}
1001
1002SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
1003    const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
1004    ELzmaStatus *status, ISzAlloc *alloc)
1005{
1006  CLzmaDec p;
1007  SRes res;
1008  SizeT outSize = *destLen, inSize = *srcLen;
1009  *destLen = *srcLen = 0;
1010  *status = LZMA_STATUS_NOT_SPECIFIED;
1011  if (inSize < RC_INIT_SIZE)
1012    return SZ_ERROR_INPUT_EOF;
1013  LzmaDec_Construct(&p);
1014  RINOK(LzmaDec_AllocateProbs(&p, propData, propSize, alloc));
1015  p.dic = dest;
1016  p.dicBufSize = outSize;
1017  LzmaDec_Init(&p);
1018  *srcLen = inSize;
1019  res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
1020  *destLen = p.dicPos;
1021  if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
1022    res = SZ_ERROR_INPUT_EOF;
1023  LzmaDec_FreeProbs(&p, alloc);
1024  return res;
1025}
1026