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