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