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