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