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