1 /* LzmaDec.c -- LZMA Decoder
\r
2 2021-04-01 : Igor Pavlov : Public domain */
\r
8 /* #include "CpuArch.h" */
\r
11 #define kNumTopBits 24
\r
12 #define kTopValue ((UInt32)1 << kNumTopBits)
\r
14 #define kNumBitModelTotalBits 11
\r
15 #define kBitModelTotal (1 << kNumBitModelTotalBits)
\r
17 #define RC_INIT_SIZE 5
\r
19 #ifndef _LZMA_DEC_OPT
\r
21 #define kNumMoveBits 5
\r
22 #define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
\r
24 #define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * (UInt32)ttt; if (code < bound)
\r
25 #define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
\r
26 #define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
\r
27 #define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
\r
28 { UPDATE_0(p); i = (i + i); A0; } else \
\r
29 { UPDATE_1(p); i = (i + i) + 1; A1; }
\r
31 #define TREE_GET_BIT(probs, i) { GET_BIT2(probs + i, i, ;, ;); }
\r
33 #define REV_BIT(p, i, A0, A1) IF_BIT_0(p + i) \
\r
34 { UPDATE_0(p + i); A0; } else \
\r
35 { UPDATE_1(p + i); A1; }
\r
36 #define REV_BIT_VAR( p, i, m) REV_BIT(p, i, i += m; m += m, m += m; i += m; )
\r
37 #define REV_BIT_CONST(p, i, m) REV_BIT(p, i, i += m; , i += m * 2; )
\r
38 #define REV_BIT_LAST( p, i, m) REV_BIT(p, i, i -= m , ; )
\r
40 #define TREE_DECODE(probs, limit, i) \
\r
41 { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
\r
43 /* #define _LZMA_SIZE_OPT */
\r
45 #ifdef _LZMA_SIZE_OPT
\r
46 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
\r
48 #define TREE_6_DECODE(probs, i) \
\r
50 TREE_GET_BIT(probs, i); \
\r
51 TREE_GET_BIT(probs, i); \
\r
52 TREE_GET_BIT(probs, i); \
\r
53 TREE_GET_BIT(probs, i); \
\r
54 TREE_GET_BIT(probs, i); \
\r
55 TREE_GET_BIT(probs, i); \
\r
59 #define NORMAL_LITER_DEC TREE_GET_BIT(prob, symbol)
\r
60 #define MATCHED_LITER_DEC \
\r
61 matchByte += matchByte; \
\r
63 offs &= matchByte; \
\r
64 probLit = prob + (offs + bit + symbol); \
\r
65 GET_BIT2(probLit, symbol, offs ^= bit; , ;)
\r
67 #endif // _LZMA_DEC_OPT
\r
70 #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_INPUT_EOF; range <<= 8; code = (code << 8) | (*buf++); }
\r
72 #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * (UInt32)ttt; if (code < bound)
\r
73 #define UPDATE_0_CHECK range = bound;
\r
74 #define UPDATE_1_CHECK range -= bound; code -= bound;
\r
75 #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
\r
76 { UPDATE_0_CHECK; i = (i + i); A0; } else \
\r
77 { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
\r
78 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
\r
79 #define TREE_DECODE_CHECK(probs, limit, i) \
\r
80 { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }
\r
83 #define REV_BIT_CHECK(p, i, m) IF_BIT_0_CHECK(p + i) \
\r
84 { UPDATE_0_CHECK; i += m; m += m; } else \
\r
85 { UPDATE_1_CHECK; m += m; i += m; }
\r
88 #define kNumPosBitsMax 4
\r
89 #define kNumPosStatesMax (1 << kNumPosBitsMax)
\r
91 #define kLenNumLowBits 3
\r
92 #define kLenNumLowSymbols (1 << kLenNumLowBits)
\r
93 #define kLenNumHighBits 8
\r
94 #define kLenNumHighSymbols (1 << kLenNumHighBits)
\r
97 #define LenHigh (LenLow + 2 * (kNumPosStatesMax << kLenNumLowBits))
\r
98 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
\r
100 #define LenChoice LenLow
\r
101 #define LenChoice2 (LenLow + (1 << kLenNumLowBits))
\r
103 #define kNumStates 12
\r
104 #define kNumStates2 16
\r
105 #define kNumLitStates 7
\r
107 #define kStartPosModelIndex 4
\r
108 #define kEndPosModelIndex 14
\r
109 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
\r
111 #define kNumPosSlotBits 6
\r
112 #define kNumLenToPosStates 4
\r
114 #define kNumAlignBits 4
\r
115 #define kAlignTableSize (1 << kNumAlignBits)
\r
117 #define kMatchMinLen 2
\r
118 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols * 2 + kLenNumHighSymbols)
\r
120 #define kMatchSpecLen_Error_Data (1 << 9)
\r
121 #define kMatchSpecLen_Error_Fail (kMatchSpecLen_Error_Data - 1)
\r
123 /* External ASM code needs same CLzmaProb array layout. So don't change it. */
\r
125 /* (probs_1664) is faster and better for code size at some platforms */
\r
127 #ifdef MY_CPU_X86_OR_AMD64
\r
129 #define kStartOffset 1664
\r
130 #define GET_PROBS p->probs_1664
\r
132 #define GET_PROBS p->probs + kStartOffset
\r
134 #define kStartOffset 0
\r
135 #define GET_PROBS p->probs
\r
139 #define SpecPos (-kStartOffset)
\r
140 #define IsRep0Long (SpecPos + kNumFullDistances)
\r
141 #define RepLenCoder (IsRep0Long + (kNumStates2 << kNumPosBitsMax))
\r
142 #define LenCoder (RepLenCoder + kNumLenProbs)
\r
143 #define IsMatch (LenCoder + kNumLenProbs)
\r
144 #define Align (IsMatch + (kNumStates2 << kNumPosBitsMax))
\r
145 #define IsRep (Align + kAlignTableSize)
\r
146 #define IsRepG0 (IsRep + kNumStates)
\r
147 #define IsRepG1 (IsRepG0 + kNumStates)
\r
148 #define IsRepG2 (IsRepG1 + kNumStates)
\r
149 #define PosSlot (IsRepG2 + kNumStates)
\r
150 #define Literal (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
\r
151 #define NUM_BASE_PROBS (Literal + kStartOffset)
\r
153 #if Align != 0 && kStartOffset != 0
\r
154 #error Stop_Compiling_Bad_LZMA_kAlign
\r
157 #if NUM_BASE_PROBS != 1984
\r
158 #error Stop_Compiling_Bad_LZMA_PROBS
\r
162 #define LZMA_LIT_SIZE 0x300
\r
164 #define LzmaProps_GetNumProbs(p) (NUM_BASE_PROBS + ((UInt32)LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
\r
167 #define CALC_POS_STATE(processedPos, pbMask) (((processedPos) & (pbMask)) << 4)
\r
168 #define COMBINED_PS_STATE (posState + state)
\r
169 #define GET_LEN_STATE (posState)
\r
171 #define LZMA_DIC_MIN (1 << 12)
\r
174 p->remainLen : shows status of LZMA decoder:
\r
175 < kMatchSpecLenStart : the number of bytes to be copied with (p->rep0) offset
\r
176 = kMatchSpecLenStart : the LZMA stream was finished with end mark
\r
177 = kMatchSpecLenStart + 1 : need init range coder
\r
178 = kMatchSpecLenStart + 2 : need init range coder and state
\r
179 = kMatchSpecLen_Error_Fail : Internal Code Failure
\r
180 = kMatchSpecLen_Error_Data + [0 ... 273] : LZMA Data Error
\r
183 /* ---------- LZMA_DECODE_REAL ---------- */
\r
185 LzmaDec_DecodeReal_3() can be implemented in external ASM file.
\r
186 3 - is the code compatibility version of that function for check at link time.
\r
189 #define LZMA_DECODE_REAL LzmaDec_DecodeReal_3
\r
194 RangeCoder is normalized
\r
195 if (p->dicPos == limit)
\r
197 LzmaDec_TryDummy() was called before to exclude LITERAL and MATCH-REP cases.
\r
198 So first symbol can be only MATCH-NON-REP. And if that MATCH-NON-REP symbol
\r
199 is not END_OF_PAYALOAD_MARKER, then the function doesn't write any byte to dictionary,
\r
200 the function returns SZ_OK, and the caller can use (p->remainLen) and (p->reps[0]) later.
\r
204 The first LZMA symbol will be decoded in any case.
\r
205 All main checks for limits are at the end of main loop,
\r
206 It decodes additional LZMA-symbols while (p->buf < bufLimit && dicPos < limit),
\r
207 RangeCoder is still without last normalization when (p->buf < bufLimit) is being checked.
\r
208 But if (p->buf < bufLimit), the caller provided at least (LZMA_REQUIRED_INPUT_MAX + 1) bytes for
\r
209 next iteration before limit (bufLimit + LZMA_REQUIRED_INPUT_MAX),
\r
210 that is enough for worst case LZMA symbol with one additional RangeCoder normalization for one bit.
\r
211 So that function never reads bufLimit [LZMA_REQUIRED_INPUT_MAX] byte.
\r
214 RangeCoder is normalized
\r
218 < kMatchSpecLenStart : the number of bytes to be copied with (p->reps[0]) offset
\r
219 = kMatchSpecLenStart : the LZMA stream was finished with end mark
\r
221 SZ_ERROR_DATA - error, when the MATCH-Symbol refers out of dictionary
\r
222 p->remainLen : undefined
\r
223 p->reps[*] : undefined
\r
227 #ifdef _LZMA_DEC_OPT
\r
229 int MY_FAST_CALL LZMA_DECODE_REAL(CLzmaDec *p, SizeT limit, const Byte *bufLimit);
\r
234 int MY_FAST_CALL LZMA_DECODE_REAL(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
\r
236 CLzmaProb *probs = GET_PROBS;
\r
237 unsigned state = (unsigned)p->state;
\r
238 UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
\r
239 unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
\r
240 unsigned lc = p->prop.lc;
\r
241 unsigned lpMask = ((unsigned)0x100 << p->prop.lp) - ((unsigned)0x100 >> lc);
\r
243 Byte *dic = p->dic;
\r
244 SizeT dicBufSize = p->dicBufSize;
\r
245 SizeT dicPos = p->dicPos;
\r
247 UInt32 processedPos = p->processedPos;
\r
248 UInt32 checkDicSize = p->checkDicSize;
\r
251 const Byte *buf = p->buf;
\r
252 UInt32 range = p->range;
\r
253 UInt32 code = p->code;
\r
260 unsigned posState = CALC_POS_STATE(processedPos, pbMask);
\r
262 prob = probs + IsMatch + COMBINED_PS_STATE;
\r
267 prob = probs + Literal;
\r
268 if (processedPos != 0 || checkDicSize != 0)
\r
269 prob += (UInt32)3 * ((((processedPos << 8) + dic[(dicPos == 0 ? dicBufSize : dicPos) - 1]) & lpMask) << lc);
\r
272 if (state < kNumLitStates)
\r
274 state -= (state < 4) ? state : 3;
\r
276 #ifdef _LZMA_SIZE_OPT
\r
277 do { NORMAL_LITER_DEC } while (symbol < 0x100);
\r
291 unsigned matchByte = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];
\r
292 unsigned offs = 0x100;
\r
293 state -= (state < 10) ? 3 : 6;
\r
295 #ifdef _LZMA_SIZE_OPT
\r
299 CLzmaProb *probLit;
\r
302 while (symbol < 0x100);
\r
306 CLzmaProb *probLit;
\r
319 dic[dicPos++] = (Byte)symbol;
\r
325 prob = probs + IsRep + state;
\r
329 state += kNumStates;
\r
330 prob = probs + LenCoder;
\r
335 prob = probs + IsRepG0 + state;
\r
339 prob = probs + IsRep0Long + COMBINED_PS_STATE;
\r
344 // that case was checked before with kBadRepCode
\r
345 // if (checkDicSize == 0 && processedPos == 0) { len = kMatchSpecLen_Error_Data + 1; break; }
\r
346 // The caller doesn't allow (dicPos == limit) case here
\r
347 // so we don't need the following check:
\r
348 // if (dicPos == limit) { state = state < kNumLitStates ? 9 : 11; len = 1; break; }
\r
350 dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];
\r
353 state = state < kNumLitStates ? 9 : 11;
\r
362 prob = probs + IsRepG1 + state;
\r
371 prob = probs + IsRepG2 + state;
\r
388 state = state < kNumLitStates ? 8 : 11;
\r
389 prob = probs + RepLenCoder;
\r
392 #ifdef _LZMA_SIZE_OPT
\r
394 unsigned lim, offset;
\r
395 CLzmaProb *probLen = prob + LenChoice;
\r
399 probLen = prob + LenLow + GET_LEN_STATE;
\r
401 lim = (1 << kLenNumLowBits);
\r
406 probLen = prob + LenChoice2;
\r
410 probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);
\r
411 offset = kLenNumLowSymbols;
\r
412 lim = (1 << kLenNumLowBits);
\r
417 probLen = prob + LenHigh;
\r
418 offset = kLenNumLowSymbols * 2;
\r
419 lim = (1 << kLenNumHighBits);
\r
422 TREE_DECODE(probLen, lim, len);
\r
427 CLzmaProb *probLen = prob + LenChoice;
\r
431 probLen = prob + LenLow + GET_LEN_STATE;
\r
433 TREE_GET_BIT(probLen, len);
\r
434 TREE_GET_BIT(probLen, len);
\r
435 TREE_GET_BIT(probLen, len);
\r
441 probLen = prob + LenChoice2;
\r
445 probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);
\r
447 TREE_GET_BIT(probLen, len);
\r
448 TREE_GET_BIT(probLen, len);
\r
449 TREE_GET_BIT(probLen, len);
\r
454 probLen = prob + LenHigh;
\r
455 TREE_DECODE(probLen, (1 << kLenNumHighBits), len);
\r
456 len += kLenNumLowSymbols * 2;
\r
462 if (state >= kNumStates)
\r
465 prob = probs + PosSlot +
\r
466 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
\r
467 TREE_6_DECODE(prob, distance);
\r
468 if (distance >= kStartPosModelIndex)
\r
470 unsigned posSlot = (unsigned)distance;
\r
471 unsigned numDirectBits = (unsigned)(((distance >> 1) - 1));
\r
472 distance = (2 | (distance & 1));
\r
473 if (posSlot < kEndPosModelIndex)
\r
475 distance <<= numDirectBits;
\r
476 prob = probs + SpecPos;
\r
482 REV_BIT_VAR(prob, distance, m);
\r
484 while (--numDirectBits);
\r
490 numDirectBits -= kNumAlignBits;
\r
499 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
\r
500 distance = (distance << 1) + (t + 1);
\r
512 while (--numDirectBits);
\r
513 prob = probs + Align;
\r
514 distance <<= kNumAlignBits;
\r
517 REV_BIT_CONST(prob, i, 1);
\r
518 REV_BIT_CONST(prob, i, 2);
\r
519 REV_BIT_CONST(prob, i, 4);
\r
520 REV_BIT_LAST (prob, i, 8);
\r
523 if (distance == (UInt32)0xFFFFFFFF)
\r
525 len = kMatchSpecLenStart;
\r
526 state -= kNumStates;
\r
535 rep0 = distance + 1;
\r
536 state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
\r
537 if (distance >= (checkDicSize == 0 ? processedPos: checkDicSize))
\r
539 len += kMatchSpecLen_Error_Data + kMatchMinLen;
\r
540 // len = kMatchSpecLen_Error_Data;
\r
541 // len += kMatchMinLen;
\r
546 len += kMatchMinLen;
\r
553 if ((rem = limit - dicPos) == 0)
\r
556 We stop decoding and return SZ_OK, and we can resume decoding later.
\r
557 Any error conditions can be tested later in caller code.
\r
558 For more strict mode we can stop decoding with error
\r
559 // len += kMatchSpecLen_Error_Data;
\r
564 curLen = ((rem < len) ? (unsigned)rem : len);
\r
565 pos = dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0);
\r
567 processedPos += (UInt32)curLen;
\r
570 if (curLen <= dicBufSize - pos)
\r
572 Byte *dest = dic + dicPos;
\r
573 ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
\r
574 const Byte *lim = dest + curLen;
\r
575 dicPos += (SizeT)curLen;
\r
577 *(dest) = (Byte)*(dest + src);
\r
578 while (++dest != lim);
\r
584 dic[dicPos++] = dic[pos];
\r
585 if (++pos == dicBufSize)
\r
588 while (--curLen != 0);
\r
593 while (dicPos < limit && buf < bufLimit);
\r
600 p->remainLen = (UInt32)len; // & (kMatchSpecLen_Error_Data - 1); // we can write real length for error matches too.
\r
601 p->dicPos = dicPos;
\r
602 p->processedPos = processedPos;
\r
607 p->state = (UInt32)state;
\r
608 if (len >= kMatchSpecLen_Error_Data)
\r
609 return SZ_ERROR_DATA;
\r
616 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
\r
618 unsigned len = (unsigned)p->remainLen;
\r
619 if (len == 0 /* || len >= kMatchSpecLenStart */)
\r
622 SizeT dicPos = p->dicPos;
\r
625 SizeT rep0; /* we use SizeT to avoid the BUG of VC14 for AMD64 */
\r
627 SizeT rem = limit - dicPos;
\r
630 len = (unsigned)(rem);
\r
636 if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
\r
637 p->checkDicSize = p->prop.dicSize;
\r
639 p->processedPos += (UInt32)len;
\r
640 p->remainLen -= (UInt32)len;
\r
643 dicBufSize = p->dicBufSize;
\r
646 dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)];
\r
650 p->dicPos = dicPos;
\r
656 At staring of new stream we have one of the following symbols:
\r
657 - Literal - is allowed
\r
658 - Non-Rep-Match - is allowed only if it's end marker symbol
\r
659 - Rep-Match - is not allowed
\r
660 We use early check of (RangeCoder:Code) over kBadRepCode to simplify main decoding code
\r
663 #define kRange0 0xFFFFFFFF
\r
664 #define kBound0 ((kRange0 >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1))
\r
665 #define kBadRepCode (kBound0 + (((kRange0 - kBound0) >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1)))
\r
666 #if kBadRepCode != (0xC0000000 - 0x400)
\r
667 #error Stop_Compiling_Bad_LZMA_Check
\r
672 LzmaDec_DecodeReal2():
\r
673 It calls LZMA_DECODE_REAL() and it adjusts limit according (p->checkDicSize).
\r
675 We correct (p->checkDicSize) after LZMA_DECODE_REAL() and in LzmaDec_WriteRem(),
\r
676 and we support the following state of (p->checkDicSize):
\r
677 if (total_processed < p->prop.dicSize) then
\r
679 (total_processed == p->processedPos)
\r
680 (p->checkDicSize == 0)
\r
683 (p->checkDicSize == p->prop.dicSize)
\r
686 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
\r
688 if (p->checkDicSize == 0)
\r
690 UInt32 rem = p->prop.dicSize - p->processedPos;
\r
691 if (limit - p->dicPos > rem)
\r
692 limit = p->dicPos + rem;
\r
695 int res = LZMA_DECODE_REAL(p, limit, bufLimit);
\r
696 if (p->checkDicSize == 0 && p->processedPos >= p->prop.dicSize)
\r
697 p->checkDicSize = p->prop.dicSize;
\r
706 DUMMY_INPUT_EOF, /* need more input data */
\r
713 #define IS_DUMMY_END_MARKER_POSSIBLE(dummyRes) ((dummyRes) == DUMMY_MATCH)
\r
715 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, const Byte **bufOut)
\r
717 UInt32 range = p->range;
\r
718 UInt32 code = p->code;
\r
719 const Byte *bufLimit = *bufOut;
\r
720 const CLzmaProb *probs = GET_PROBS;
\r
721 unsigned state = (unsigned)p->state;
\r
726 const CLzmaProb *prob;
\r
729 unsigned posState = CALC_POS_STATE(p->processedPos, ((unsigned)1 << p->prop.pb) - 1);
\r
731 prob = probs + IsMatch + COMBINED_PS_STATE;
\r
732 IF_BIT_0_CHECK(prob)
\r
736 prob = probs + Literal;
\r
737 if (p->checkDicSize != 0 || p->processedPos != 0)
\r
738 prob += ((UInt32)LZMA_LIT_SIZE *
\r
739 ((((p->processedPos) & (((unsigned)1 << (p->prop.lp)) - 1)) << p->prop.lc) +
\r
740 ((unsigned)p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
\r
742 if (state < kNumLitStates)
\r
744 unsigned symbol = 1;
\r
745 do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
\r
749 unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
\r
750 (p->dicPos < p->reps[0] ? p->dicBufSize : 0)];
\r
751 unsigned offs = 0x100;
\r
752 unsigned symbol = 1;
\r
756 const CLzmaProb *probLit;
\r
757 matchByte += matchByte;
\r
760 probLit = prob + (offs + bit + symbol);
\r
761 GET_BIT2_CHECK(probLit, symbol, offs ^= bit; , ; )
\r
763 while (symbol < 0x100);
\r
772 prob = probs + IsRep + state;
\r
773 IF_BIT_0_CHECK(prob)
\r
777 prob = probs + LenCoder;
\r
784 prob = probs + IsRepG0 + state;
\r
785 IF_BIT_0_CHECK(prob)
\r
788 prob = probs + IsRep0Long + COMBINED_PS_STATE;
\r
789 IF_BIT_0_CHECK(prob)
\r
802 prob = probs + IsRepG1 + state;
\r
803 IF_BIT_0_CHECK(prob)
\r
810 prob = probs + IsRepG2 + state;
\r
811 IF_BIT_0_CHECK(prob)
\r
821 state = kNumStates;
\r
822 prob = probs + RepLenCoder;
\r
825 unsigned limit, offset;
\r
826 const CLzmaProb *probLen = prob + LenChoice;
\r
827 IF_BIT_0_CHECK(probLen)
\r
830 probLen = prob + LenLow + GET_LEN_STATE;
\r
832 limit = 1 << kLenNumLowBits;
\r
837 probLen = prob + LenChoice2;
\r
838 IF_BIT_0_CHECK(probLen)
\r
841 probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits);
\r
842 offset = kLenNumLowSymbols;
\r
843 limit = 1 << kLenNumLowBits;
\r
848 probLen = prob + LenHigh;
\r
849 offset = kLenNumLowSymbols * 2;
\r
850 limit = 1 << kLenNumHighBits;
\r
853 TREE_DECODE_CHECK(probLen, limit, len);
\r
860 prob = probs + PosSlot +
\r
861 ((len < kNumLenToPosStates - 1 ? len : kNumLenToPosStates - 1) <<
\r
863 TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
\r
864 if (posSlot >= kStartPosModelIndex)
\r
866 unsigned numDirectBits = ((posSlot >> 1) - 1);
\r
868 if (posSlot < kEndPosModelIndex)
\r
870 prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits);
\r
874 numDirectBits -= kNumAlignBits;
\r
879 code -= range & (((code - range) >> 31) - 1);
\r
880 /* if (code >= range) code -= range; */
\r
882 while (--numDirectBits);
\r
883 prob = probs + Align;
\r
884 numDirectBits = kNumAlignBits;
\r
891 REV_BIT_CHECK(prob, i, m);
\r
893 while (--numDirectBits);
\r
906 void LzmaDec_InitDicAndState(CLzmaDec *p, BoolInt initDic, BoolInt initState);
\r
907 void LzmaDec_InitDicAndState(CLzmaDec *p, BoolInt initDic, BoolInt initState)
\r
909 p->remainLen = kMatchSpecLenStart + 1;
\r
910 p->tempBufSize = 0;
\r
914 p->processedPos = 0;
\r
915 p->checkDicSize = 0;
\r
916 p->remainLen = kMatchSpecLenStart + 2;
\r
919 p->remainLen = kMatchSpecLenStart + 2;
\r
922 void LzmaDec_Init(CLzmaDec *p)
\r
925 LzmaDec_InitDicAndState(p, True, True);
\r
930 LZMA supports optional end_marker.
\r
931 So the decoder can lookahead for one additional LZMA-Symbol to check end_marker.
\r
932 That additional LZMA-Symbol can require up to LZMA_REQUIRED_INPUT_MAX bytes in input stream.
\r
933 When the decoder reaches dicLimit, it looks (finishMode) parameter:
\r
934 if (finishMode == LZMA_FINISH_ANY), the decoder doesn't lookahead
\r
935 if (finishMode != LZMA_FINISH_ANY), the decoder lookahead, if end_marker is possible for current position
\r
937 When the decoder lookahead, and the lookahead symbol is not end_marker, we have two ways:
\r
938 1) Strict mode (default) : the decoder returns SZ_ERROR_DATA.
\r
939 2) The relaxed mode (alternative mode) : we could return SZ_OK, and the caller
\r
940 must check (status) value. The caller can show the error,
\r
941 if the end of stream is expected, and the (status) is noit
\r
942 LZMA_STATUS_FINISHED_WITH_MARK or LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK.
\r
946 #define RETURN__NOT_FINISHED__FOR_FINISH \
\r
947 *status = LZMA_STATUS_NOT_FINISHED; \
\r
948 return SZ_ERROR_DATA; // for strict mode
\r
949 // return SZ_OK; // for relaxed mode
\r
952 SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
\r
953 ELzmaFinishMode finishMode, ELzmaStatus *status)
\r
955 SizeT inSize = *srcLen;
\r
957 *status = LZMA_STATUS_NOT_SPECIFIED;
\r
959 if (p->remainLen > kMatchSpecLenStart)
\r
961 if (p->remainLen > kMatchSpecLenStart + 2)
\r
962 return p->remainLen == kMatchSpecLen_Error_Fail ? SZ_ERROR_FAIL : SZ_ERROR_DATA;
\r
964 for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
\r
965 p->tempBuf[p->tempBufSize++] = *src++;
\r
966 if (p->tempBufSize != 0 && p->tempBuf[0] != 0)
\r
967 return SZ_ERROR_DATA;
\r
968 if (p->tempBufSize < RC_INIT_SIZE)
\r
970 *status = LZMA_STATUS_NEEDS_MORE_INPUT;
\r
974 ((UInt32)p->tempBuf[1] << 24)
\r
975 | ((UInt32)p->tempBuf[2] << 16)
\r
976 | ((UInt32)p->tempBuf[3] << 8)
\r
977 | ((UInt32)p->tempBuf[4]);
\r
979 if (p->checkDicSize == 0
\r
980 && p->processedPos == 0
\r
981 && p->code >= kBadRepCode)
\r
982 return SZ_ERROR_DATA;
\r
984 p->range = 0xFFFFFFFF;
\r
985 p->tempBufSize = 0;
\r
987 if (p->remainLen > kMatchSpecLenStart + 1)
\r
989 SizeT numProbs = LzmaProps_GetNumProbs(&p->prop);
\r
991 CLzmaProb *probs = p->probs;
\r
992 for (i = 0; i < numProbs; i++)
\r
993 probs[i] = kBitModelTotal >> 1;
\r
994 p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
\r
1003 if (p->remainLen == kMatchSpecLenStart)
\r
1006 return SZ_ERROR_DATA;
\r
1007 *status = LZMA_STATUS_FINISHED_WITH_MARK;
\r
1011 LzmaDec_WriteRem(p, dicLimit);
\r
1014 // (p->remainLen == 0 || p->dicPos == dicLimit)
\r
1016 int checkEndMarkNow = 0;
\r
1018 if (p->dicPos >= dicLimit)
\r
1020 if (p->remainLen == 0 && p->code == 0)
\r
1022 *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
\r
1025 if (finishMode == LZMA_FINISH_ANY)
\r
1027 *status = LZMA_STATUS_NOT_FINISHED;
\r
1030 if (p->remainLen != 0)
\r
1032 RETURN__NOT_FINISHED__FOR_FINISH;
\r
1034 checkEndMarkNow = 1;
\r
1037 // (p->remainLen == 0)
\r
1039 if (p->tempBufSize == 0)
\r
1041 const Byte *bufLimit;
\r
1042 int dummyProcessed = -1;
\r
1044 if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
\r
1046 const Byte *bufOut = src + inSize;
\r
1048 ELzmaDummy dummyRes = LzmaDec_TryDummy(p, src, &bufOut);
\r
1050 if (dummyRes == DUMMY_INPUT_EOF)
\r
1053 if (inSize >= LZMA_REQUIRED_INPUT_MAX)
\r
1055 (*srcLen) += inSize;
\r
1056 p->tempBufSize = (unsigned)inSize;
\r
1057 for (i = 0; i < inSize; i++)
\r
1058 p->tempBuf[i] = src[i];
\r
1059 *status = LZMA_STATUS_NEEDS_MORE_INPUT;
\r
1063 dummyProcessed = (int)(bufOut - src);
\r
1064 if ((unsigned)dummyProcessed > LZMA_REQUIRED_INPUT_MAX)
\r
1067 if (checkEndMarkNow && !IS_DUMMY_END_MARKER_POSSIBLE(dummyRes))
\r
1070 (*srcLen) += (unsigned)dummyProcessed;
\r
1071 p->tempBufSize = (unsigned)dummyProcessed;
\r
1072 for (i = 0; i < (unsigned)dummyProcessed; i++)
\r
1073 p->tempBuf[i] = src[i];
\r
1074 // p->remainLen = kMatchSpecLen_Error_Data;
\r
1075 RETURN__NOT_FINISHED__FOR_FINISH;
\r
1079 // we will decode only one iteration
\r
1082 bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
\r
1087 int res = LzmaDec_DecodeReal2(p, dicLimit, bufLimit);
\r
1089 SizeT processed = (SizeT)(p->buf - src);
\r
1091 if (dummyProcessed < 0)
\r
1093 if (processed > inSize)
\r
1096 else if ((unsigned)dummyProcessed != processed)
\r
1100 inSize -= processed;
\r
1101 (*srcLen) += processed;
\r
1105 p->remainLen = kMatchSpecLen_Error_Data;
\r
1106 return SZ_ERROR_DATA;
\r
1113 // we have some data in (p->tempBuf)
\r
1114 // in strict mode: tempBufSize is not enough for one Symbol decoding.
\r
1115 // in relaxed mode: tempBufSize not larger than required for one Symbol decoding.
\r
1117 unsigned rem = p->tempBufSize;
\r
1118 unsigned ahead = 0;
\r
1119 int dummyProcessed = -1;
\r
1121 while (rem < LZMA_REQUIRED_INPUT_MAX && ahead < inSize)
\r
1122 p->tempBuf[rem++] = src[ahead++];
\r
1124 // ahead - the size of new data copied from (src) to (p->tempBuf)
\r
1125 // rem - the size of temp buffer including new data from (src)
\r
1127 if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
\r
1129 const Byte *bufOut = p->tempBuf + rem;
\r
1131 ELzmaDummy dummyRes = LzmaDec_TryDummy(p, p->tempBuf, &bufOut);
\r
1133 if (dummyRes == DUMMY_INPUT_EOF)
\r
1135 if (rem >= LZMA_REQUIRED_INPUT_MAX)
\r
1137 p->tempBufSize = rem;
\r
1138 (*srcLen) += (SizeT)ahead;
\r
1139 *status = LZMA_STATUS_NEEDS_MORE_INPUT;
\r
1143 dummyProcessed = (int)(bufOut - p->tempBuf);
\r
1145 if ((unsigned)dummyProcessed < p->tempBufSize)
\r
1148 if (checkEndMarkNow && !IS_DUMMY_END_MARKER_POSSIBLE(dummyRes))
\r
1150 (*srcLen) += (unsigned)dummyProcessed - p->tempBufSize;
\r
1151 p->tempBufSize = (unsigned)dummyProcessed;
\r
1152 // p->remainLen = kMatchSpecLen_Error_Data;
\r
1153 RETURN__NOT_FINISHED__FOR_FINISH;
\r
1157 p->buf = p->tempBuf;
\r
1160 // we decode one symbol from (p->tempBuf) here, so the (bufLimit) is equal to (p->buf)
\r
1161 int res = LzmaDec_DecodeReal2(p, dicLimit, p->buf);
\r
1163 SizeT processed = (SizeT)(p->buf - p->tempBuf);
\r
1164 rem = p->tempBufSize;
\r
1166 if (dummyProcessed < 0)
\r
1168 if (processed > LZMA_REQUIRED_INPUT_MAX)
\r
1170 if (processed < rem)
\r
1173 else if ((unsigned)dummyProcessed != processed)
\r
1179 inSize -= processed;
\r
1180 (*srcLen) += processed;
\r
1181 p->tempBufSize = 0;
\r
1185 p->remainLen = kMatchSpecLen_Error_Data;
\r
1186 return SZ_ERROR_DATA;
\r
1193 /* Some unexpected error: internal error of code, memory corruption or hardware failure */
\r
1194 p->remainLen = kMatchSpecLen_Error_Fail;
\r
1195 return SZ_ERROR_FAIL;
\r
1200 SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
\r
1202 SizeT outSize = *destLen;
\r
1203 SizeT inSize = *srcLen;
\r
1204 *srcLen = *destLen = 0;
\r
1207 SizeT inSizeCur = inSize, outSizeCur, dicPos;
\r
1208 ELzmaFinishMode curFinishMode;
\r
1210 if (p->dicPos == p->dicBufSize)
\r
1212 dicPos = p->dicPos;
\r
1213 if (outSize > p->dicBufSize - dicPos)
\r
1215 outSizeCur = p->dicBufSize;
\r
1216 curFinishMode = LZMA_FINISH_ANY;
\r
1220 outSizeCur = dicPos + outSize;
\r
1221 curFinishMode = finishMode;
\r
1224 res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
\r
1226 inSize -= inSizeCur;
\r
1227 *srcLen += inSizeCur;
\r
1228 outSizeCur = p->dicPos - dicPos;
\r
1229 memcpy(dest, p->dic + dicPos, outSizeCur);
\r
1230 dest += outSizeCur;
\r
1231 outSize -= outSizeCur;
\r
1232 *destLen += outSizeCur;
\r
1235 if (outSizeCur == 0 || outSize == 0)
\r
1240 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAllocPtr alloc)
\r
1242 ISzAlloc_Free(alloc, p->probs);
\r
1246 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAllocPtr alloc)
\r
1248 ISzAlloc_Free(alloc, p->dic);
\r
1252 void LzmaDec_Free(CLzmaDec *p, ISzAllocPtr alloc)
\r
1254 LzmaDec_FreeProbs(p, alloc);
\r
1255 LzmaDec_FreeDict(p, alloc);
\r
1258 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
\r
1263 if (size < LZMA_PROPS_SIZE)
\r
1264 return SZ_ERROR_UNSUPPORTED;
\r
1266 dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
\r
1268 if (dicSize < LZMA_DIC_MIN)
\r
1269 dicSize = LZMA_DIC_MIN;
\r
1270 p->dicSize = dicSize;
\r
1273 if (d >= (9 * 5 * 5))
\r
1274 return SZ_ERROR_UNSUPPORTED;
\r
1276 p->lc = (Byte)(d % 9);
\r
1278 p->pb = (Byte)(d / 5);
\r
1279 p->lp = (Byte)(d % 5);
\r
1284 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAllocPtr alloc)
\r
1286 UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
\r
1287 if (!p->probs || numProbs != p->numProbs)
\r
1289 LzmaDec_FreeProbs(p, alloc);
\r
1290 p->probs = (CLzmaProb *)ISzAlloc_Alloc(alloc, numProbs * sizeof(CLzmaProb));
\r
1292 return SZ_ERROR_MEM;
\r
1293 p->probs_1664 = p->probs + 1664;
\r
1294 p->numProbs = numProbs;
\r
1299 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAllocPtr alloc)
\r
1301 CLzmaProps propNew;
\r
1302 RINOK(LzmaProps_Decode(&propNew, props, propsSize));
\r
1303 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
\r
1304 p->prop = propNew;
\r
1308 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAllocPtr alloc)
\r
1310 CLzmaProps propNew;
\r
1312 RINOK(LzmaProps_Decode(&propNew, props, propsSize));
\r
1313 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
\r
1316 UInt32 dictSize = propNew.dicSize;
\r
1317 SizeT mask = ((UInt32)1 << 12) - 1;
\r
1318 if (dictSize >= ((UInt32)1 << 30)) mask = ((UInt32)1 << 22) - 1;
\r
1319 else if (dictSize >= ((UInt32)1 << 22)) mask = ((UInt32)1 << 20) - 1;;
\r
1320 dicBufSize = ((SizeT)dictSize + mask) & ~mask;
\r
1321 if (dicBufSize < dictSize)
\r
1322 dicBufSize = dictSize;
\r
1325 if (!p->dic || dicBufSize != p->dicBufSize)
\r
1327 LzmaDec_FreeDict(p, alloc);
\r
1328 p->dic = (Byte *)ISzAlloc_Alloc(alloc, dicBufSize);
\r
1331 LzmaDec_FreeProbs(p, alloc);
\r
1332 return SZ_ERROR_MEM;
\r
1335 p->dicBufSize = dicBufSize;
\r
1336 p->prop = propNew;
\r
1340 SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
\r
1341 const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
\r
1342 ELzmaStatus *status, ISzAllocPtr alloc)
\r
1346 SizeT outSize = *destLen, inSize = *srcLen;
\r
1347 *destLen = *srcLen = 0;
\r
1348 *status = LZMA_STATUS_NOT_SPECIFIED;
\r
1349 if (inSize < RC_INIT_SIZE)
\r
1350 return SZ_ERROR_INPUT_EOF;
\r
1351 LzmaDec_Construct(&p);
\r
1352 RINOK(LzmaDec_AllocateProbs(&p, propData, propSize, alloc));
\r
1354 p.dicBufSize = outSize;
\r
1357 res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
\r
1358 *destLen = p.dicPos;
\r
1359 if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
\r
1360 res = SZ_ERROR_INPUT_EOF;
\r
1361 LzmaDec_FreeProbs(&p, alloc);
\r