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