File indexing completed on 2025-02-02 04:25:59
0001 /* LzmaDec.c -- LZMA Decoder 0002 2015-01-01 : Igor Pavlov : Public domain */ 0003 0004 #include "Precomp.h" 0005 0006 #include "LzmaDec.h" 0007 0008 #include <string.h> 0009 0010 #define kNumTopBits 24 0011 #define kTopValue ((UInt32)1 << kNumTopBits) 0012 0013 #define kNumBitModelTotalBits 11 0014 #define kBitModelTotal (1 << kNumBitModelTotalBits) 0015 #define kNumMoveBits 5 0016 0017 #define RC_INIT_SIZE 5 0018 0019 #define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); } 0020 0021 #define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound) 0022 #define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits)); 0023 #define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits)); 0024 #define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \ 0025 { UPDATE_0(p); i = (i + i); A0; } else \ 0026 { UPDATE_1(p); i = (i + i) + 1; A1; } 0027 #define GET_BIT(p, i) GET_BIT2(p, i, ; , ;) 0028 0029 #define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); } 0030 #define TREE_DECODE(probs, limit, i) \ 0031 { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; } 0032 0033 /* #define _LZMA_SIZE_OPT */ 0034 0035 #ifdef _LZMA_SIZE_OPT 0036 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i) 0037 #else 0038 #define TREE_6_DECODE(probs, i) \ 0039 { i = 1; \ 0040 TREE_GET_BIT(probs, i); \ 0041 TREE_GET_BIT(probs, i); \ 0042 TREE_GET_BIT(probs, i); \ 0043 TREE_GET_BIT(probs, i); \ 0044 TREE_GET_BIT(probs, i); \ 0045 TREE_GET_BIT(probs, i); \ 0046 i -= 0x40; } 0047 #endif 0048 0049 #define NORMAL_LITER_DEC GET_BIT(prob + symbol, symbol) 0050 #define MATCHED_LITER_DEC \ 0051 matchByte <<= 1; \ 0052 bit = (matchByte & offs); \ 0053 probLit = prob + offs + bit + symbol; \ 0054 GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit) 0055 0056 #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); } 0057 0058 #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound) 0059 #define UPDATE_0_CHECK range = bound; 0060 #define UPDATE_1_CHECK range -= bound; code -= bound; 0061 #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \ 0062 { UPDATE_0_CHECK; i = (i + i); A0; } else \ 0063 { UPDATE_1_CHECK; i = (i + i) + 1; A1; } 0064 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;) 0065 #define TREE_DECODE_CHECK(probs, limit, i) \ 0066 { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; } 0067 0068 0069 #define kNumPosBitsMax 4 0070 #define kNumPosStatesMax (1 << kNumPosBitsMax) 0071 0072 #define kLenNumLowBits 3 0073 #define kLenNumLowSymbols (1 << kLenNumLowBits) 0074 #define kLenNumMidBits 3 0075 #define kLenNumMidSymbols (1 << kLenNumMidBits) 0076 #define kLenNumHighBits 8 0077 #define kLenNumHighSymbols (1 << kLenNumHighBits) 0078 0079 #define LenChoice 0 0080 #define LenChoice2 (LenChoice + 1) 0081 #define LenLow (LenChoice2 + 1) 0082 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) 0083 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) 0084 #define kNumLenProbs (LenHigh + kLenNumHighSymbols) 0085 0086 0087 #define kNumStates 12 0088 #define kNumLitStates 7 0089 0090 #define kStartPosModelIndex 4 0091 #define kEndPosModelIndex 14 0092 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 0093 0094 #define kNumPosSlotBits 6 0095 #define kNumLenToPosStates 4 0096 0097 #define kNumAlignBits 4 0098 #define kAlignTableSize (1 << kNumAlignBits) 0099 0100 #define kMatchMinLen 2 0101 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols) 0102 0103 #define IsMatch 0 0104 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) 0105 #define IsRepG0 (IsRep + kNumStates) 0106 #define IsRepG1 (IsRepG0 + kNumStates) 0107 #define IsRepG2 (IsRepG1 + kNumStates) 0108 #define IsRep0Long (IsRepG2 + kNumStates) 0109 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) 0110 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) 0111 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) 0112 #define LenCoder (Align + kAlignTableSize) 0113 #define RepLenCoder (LenCoder + kNumLenProbs) 0114 #define Literal (RepLenCoder + kNumLenProbs) 0115 0116 #define LZMA_BASE_SIZE 1846 0117 #define LZMA_LIT_SIZE 768 0118 0119 #define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp))) 0120 0121 #if Literal != LZMA_BASE_SIZE 0122 StopCompilingDueBUG 0123 #endif 0124 0125 #define LZMA_DIC_MIN (1 << 12) 0126 0127 /* First LZMA-symbol is always decoded. 0128 And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization 0129 Out: 0130 Result: 0131 SZ_OK - OK 0132 SZ_ERROR_DATA - Error 0133 p->remainLen: 0134 < kMatchSpecLenStart : normal remain 0135 = kMatchSpecLenStart : finished 0136 = kMatchSpecLenStart + 1 : Flush marker 0137 = kMatchSpecLenStart + 2 : State Init Marker 0138 */ 0139 0140 static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit) 0141 { 0142 CLzmaProb *probs = p->probs; 0143 0144 unsigned state = p->state; 0145 UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3]; 0146 unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1; 0147 unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1; 0148 unsigned lc = p->prop.lc; 0149 0150 Byte *dic = p->dic; 0151 SizeT dicBufSize = p->dicBufSize; 0152 SizeT dicPos = p->dicPos; 0153 0154 UInt32 processedPos = p->processedPos; 0155 UInt32 checkDicSize = p->checkDicSize; 0156 unsigned len = 0; 0157 0158 const Byte *buf = p->buf; 0159 UInt32 range = p->range; 0160 UInt32 code = p->code; 0161 0162 do 0163 { 0164 CLzmaProb *prob; 0165 UInt32 bound; 0166 unsigned ttt; 0167 unsigned posState = processedPos & pbMask; 0168 0169 prob = probs + IsMatch + (state << kNumPosBitsMax) + posState; 0170 IF_BIT_0(prob) 0171 { 0172 unsigned symbol; 0173 UPDATE_0(prob); 0174 prob = probs + Literal; 0175 if (checkDicSize != 0 || processedPos != 0) 0176 prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) + 0177 (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc)))); 0178 0179 if (state < kNumLitStates) 0180 { 0181 state -= (state < 4) ? state : 3; 0182 symbol = 1; 0183 #ifdef _LZMA_SIZE_OPT 0184 do { NORMAL_LITER_DEC } while (symbol < 0x100); 0185 #else 0186 NORMAL_LITER_DEC 0187 NORMAL_LITER_DEC 0188 NORMAL_LITER_DEC 0189 NORMAL_LITER_DEC 0190 NORMAL_LITER_DEC 0191 NORMAL_LITER_DEC 0192 NORMAL_LITER_DEC 0193 NORMAL_LITER_DEC 0194 #endif 0195 } 0196 else 0197 { 0198 unsigned matchByte = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; 0199 unsigned offs = 0x100; 0200 state -= (state < 10) ? 3 : 6; 0201 symbol = 1; 0202 #ifdef _LZMA_SIZE_OPT 0203 do 0204 { 0205 unsigned bit; 0206 CLzmaProb *probLit; 0207 MATCHED_LITER_DEC 0208 } 0209 while (symbol < 0x100); 0210 #else 0211 { 0212 unsigned bit; 0213 CLzmaProb *probLit; 0214 MATCHED_LITER_DEC 0215 MATCHED_LITER_DEC 0216 MATCHED_LITER_DEC 0217 MATCHED_LITER_DEC 0218 MATCHED_LITER_DEC 0219 MATCHED_LITER_DEC 0220 MATCHED_LITER_DEC 0221 MATCHED_LITER_DEC 0222 } 0223 #endif 0224 } 0225 dic[dicPos++] = (Byte)symbol; 0226 processedPos++; 0227 continue; 0228 } 0229 else 0230 { 0231 UPDATE_1(prob); 0232 prob = probs + IsRep + state; 0233 IF_BIT_0(prob) 0234 { 0235 UPDATE_0(prob); 0236 state += kNumStates; 0237 prob = probs + LenCoder; 0238 } 0239 else 0240 { 0241 UPDATE_1(prob); 0242 if (checkDicSize == 0 && processedPos == 0) 0243 return SZ_ERROR_DATA; 0244 prob = probs + IsRepG0 + state; 0245 IF_BIT_0(prob) 0246 { 0247 UPDATE_0(prob); 0248 prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState; 0249 IF_BIT_0(prob) 0250 { 0251 UPDATE_0(prob); 0252 dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; 0253 dicPos++; 0254 processedPos++; 0255 state = state < kNumLitStates ? 9 : 11; 0256 continue; 0257 } 0258 UPDATE_1(prob); 0259 } 0260 else 0261 { 0262 UInt32 distance; 0263 UPDATE_1(prob); 0264 prob = probs + IsRepG1 + state; 0265 IF_BIT_0(prob) 0266 { 0267 UPDATE_0(prob); 0268 distance = rep1; 0269 } 0270 else 0271 { 0272 UPDATE_1(prob); 0273 prob = probs + IsRepG2 + state; 0274 IF_BIT_0(prob) 0275 { 0276 UPDATE_0(prob); 0277 distance = rep2; 0278 } 0279 else 0280 { 0281 UPDATE_1(prob); 0282 distance = rep3; 0283 rep3 = rep2; 0284 } 0285 rep2 = rep1; 0286 } 0287 rep1 = rep0; 0288 rep0 = distance; 0289 } 0290 state = state < kNumLitStates ? 8 : 11; 0291 prob = probs + RepLenCoder; 0292 } 0293 { 0294 unsigned limit, offset; 0295 CLzmaProb *probLen = prob + LenChoice; 0296 IF_BIT_0(probLen) 0297 { 0298 UPDATE_0(probLen); 0299 probLen = prob + LenLow + (posState << kLenNumLowBits); 0300 offset = 0; 0301 limit = (1 << kLenNumLowBits); 0302 } 0303 else 0304 { 0305 UPDATE_1(probLen); 0306 probLen = prob + LenChoice2; 0307 IF_BIT_0(probLen) 0308 { 0309 UPDATE_0(probLen); 0310 probLen = prob + LenMid + (posState << kLenNumMidBits); 0311 offset = kLenNumLowSymbols; 0312 limit = (1 << kLenNumMidBits); 0313 } 0314 else 0315 { 0316 UPDATE_1(probLen); 0317 probLen = prob + LenHigh; 0318 offset = kLenNumLowSymbols + kLenNumMidSymbols; 0319 limit = (1 << kLenNumHighBits); 0320 } 0321 } 0322 TREE_DECODE(probLen, limit, len); 0323 len += offset; 0324 } 0325 0326 if (state >= kNumStates) 0327 { 0328 UInt32 distance; 0329 prob = probs + PosSlot + 0330 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits); 0331 TREE_6_DECODE(prob, distance); 0332 if (distance >= kStartPosModelIndex) 0333 { 0334 unsigned posSlot = (unsigned)distance; 0335 int numDirectBits = (int)(((distance >> 1) - 1)); 0336 distance = (2 | (distance & 1)); 0337 if (posSlot < kEndPosModelIndex) 0338 { 0339 distance <<= numDirectBits; 0340 prob = probs + SpecPos + distance - posSlot - 1; 0341 { 0342 UInt32 mask = 1; 0343 unsigned i = 1; 0344 do 0345 { 0346 GET_BIT2(prob + i, i, ; , distance |= mask); 0347 mask <<= 1; 0348 } 0349 while (--numDirectBits != 0); 0350 } 0351 } 0352 else 0353 { 0354 numDirectBits -= kNumAlignBits; 0355 do 0356 { 0357 NORMALIZE 0358 range >>= 1; 0359 0360 { 0361 UInt32 t; 0362 code -= range; 0363 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */ 0364 distance = (distance << 1) + (t + 1); 0365 code += range & t; 0366 } 0367 /* 0368 distance <<= 1; 0369 if (code >= range) 0370 { 0371 code -= range; 0372 distance |= 1; 0373 } 0374 */ 0375 } 0376 while (--numDirectBits != 0); 0377 prob = probs + Align; 0378 distance <<= kNumAlignBits; 0379 { 0380 unsigned i = 1; 0381 GET_BIT2(prob + i, i, ; , distance |= 1); 0382 GET_BIT2(prob + i, i, ; , distance |= 2); 0383 GET_BIT2(prob + i, i, ; , distance |= 4); 0384 GET_BIT2(prob + i, i, ; , distance |= 8); 0385 } 0386 if (distance == (UInt32)0xFFFFFFFF) 0387 { 0388 len += kMatchSpecLenStart; 0389 state -= kNumStates; 0390 break; 0391 } 0392 } 0393 } 0394 rep3 = rep2; 0395 rep2 = rep1; 0396 rep1 = rep0; 0397 rep0 = distance + 1; 0398 if (checkDicSize == 0) 0399 { 0400 if (distance >= processedPos) 0401 return SZ_ERROR_DATA; 0402 } 0403 else if (distance >= checkDicSize) 0404 return SZ_ERROR_DATA; 0405 state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3; 0406 } 0407 0408 len += kMatchMinLen; 0409 0410 if (limit == dicPos) 0411 return SZ_ERROR_DATA; 0412 { 0413 SizeT rem = limit - dicPos; 0414 unsigned curLen = ((rem < len) ? (unsigned)rem : len); 0415 SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0); 0416 0417 processedPos += curLen; 0418 0419 len -= curLen; 0420 if (pos + curLen <= dicBufSize) 0421 { 0422 Byte *dest = dic + dicPos; 0423 ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos; 0424 const Byte *lim = dest + curLen; 0425 dicPos += curLen; 0426 do 0427 *(dest) = (Byte)*(dest + src); 0428 while (++dest != lim); 0429 } 0430 else 0431 { 0432 do 0433 { 0434 dic[dicPos++] = dic[pos]; 0435 if (++pos == dicBufSize) 0436 pos = 0; 0437 } 0438 while (--curLen != 0); 0439 } 0440 } 0441 } 0442 } 0443 while (dicPos < limit && buf < bufLimit); 0444 NORMALIZE; 0445 p->buf = buf; 0446 p->range = range; 0447 p->code = code; 0448 p->remainLen = len; 0449 p->dicPos = dicPos; 0450 p->processedPos = processedPos; 0451 p->reps[0] = rep0; 0452 p->reps[1] = rep1; 0453 p->reps[2] = rep2; 0454 p->reps[3] = rep3; 0455 p->state = state; 0456 0457 return SZ_OK; 0458 } 0459 0460 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit) 0461 { 0462 if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart) 0463 { 0464 Byte *dic = p->dic; 0465 SizeT dicPos = p->dicPos; 0466 SizeT dicBufSize = p->dicBufSize; 0467 unsigned len = p->remainLen; 0468 UInt32 rep0 = p->reps[0]; 0469 if (limit - dicPos < len) 0470 len = (unsigned)(limit - dicPos); 0471 0472 if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len) 0473 p->checkDicSize = p->prop.dicSize; 0474 0475 p->processedPos += len; 0476 p->remainLen -= len; 0477 while (len != 0) 0478 { 0479 len--; 0480 dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)]; 0481 dicPos++; 0482 } 0483 p->dicPos = dicPos; 0484 } 0485 } 0486 0487 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit) 0488 { 0489 do 0490 { 0491 SizeT limit2 = limit; 0492 if (p->checkDicSize == 0) 0493 { 0494 UInt32 rem = p->prop.dicSize - p->processedPos; 0495 if (limit - p->dicPos > rem) 0496 limit2 = p->dicPos + rem; 0497 } 0498 RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit)); 0499 if (p->processedPos >= p->prop.dicSize) 0500 p->checkDicSize = p->prop.dicSize; 0501 LzmaDec_WriteRem(p, limit); 0502 } 0503 while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart); 0504 0505 if (p->remainLen > kMatchSpecLenStart) 0506 { 0507 p->remainLen = kMatchSpecLenStart; 0508 } 0509 return 0; 0510 } 0511 0512 typedef enum 0513 { 0514 DUMMY_ERROR, /* unexpected end of input stream */ 0515 DUMMY_LIT, 0516 DUMMY_MATCH, 0517 DUMMY_REP 0518 } ELzmaDummy; 0519 0520 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize) 0521 { 0522 UInt32 range = p->range; 0523 UInt32 code = p->code; 0524 const Byte *bufLimit = buf + inSize; 0525 CLzmaProb *probs = p->probs; 0526 unsigned state = p->state; 0527 ELzmaDummy res; 0528 0529 { 0530 CLzmaProb *prob; 0531 UInt32 bound; 0532 unsigned ttt; 0533 unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1); 0534 0535 prob = probs + IsMatch + (state << kNumPosBitsMax) + posState; 0536 IF_BIT_0_CHECK(prob) 0537 { 0538 UPDATE_0_CHECK 0539 0540 /* if (bufLimit - buf >= 7) return DUMMY_LIT; */ 0541 0542 prob = probs + Literal; 0543 if (p->checkDicSize != 0 || p->processedPos != 0) 0544 prob += (LZMA_LIT_SIZE * 0545 ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) + 0546 (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc)))); 0547 0548 if (state < kNumLitStates) 0549 { 0550 unsigned symbol = 1; 0551 do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100); 0552 } 0553 else 0554 { 0555 unsigned matchByte = p->dic[p->dicPos - p->reps[0] + 0556 ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)]; 0557 unsigned offs = 0x100; 0558 unsigned symbol = 1; 0559 do 0560 { 0561 unsigned bit; 0562 CLzmaProb *probLit; 0563 matchByte <<= 1; 0564 bit = (matchByte & offs); 0565 probLit = prob + offs + bit + symbol; 0566 GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit) 0567 } 0568 while (symbol < 0x100); 0569 } 0570 res = DUMMY_LIT; 0571 } 0572 else 0573 { 0574 unsigned len; 0575 UPDATE_1_CHECK; 0576 0577 prob = probs + IsRep + state; 0578 IF_BIT_0_CHECK(prob) 0579 { 0580 UPDATE_0_CHECK; 0581 state = 0; 0582 prob = probs + LenCoder; 0583 res = DUMMY_MATCH; 0584 } 0585 else 0586 { 0587 UPDATE_1_CHECK; 0588 res = DUMMY_REP; 0589 prob = probs + IsRepG0 + state; 0590 IF_BIT_0_CHECK(prob) 0591 { 0592 UPDATE_0_CHECK; 0593 prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState; 0594 IF_BIT_0_CHECK(prob) 0595 { 0596 UPDATE_0_CHECK; 0597 NORMALIZE_CHECK; 0598 return DUMMY_REP; 0599 } 0600 else 0601 { 0602 UPDATE_1_CHECK; 0603 } 0604 } 0605 else 0606 { 0607 UPDATE_1_CHECK; 0608 prob = probs + IsRepG1 + state; 0609 IF_BIT_0_CHECK(prob) 0610 { 0611 UPDATE_0_CHECK; 0612 } 0613 else 0614 { 0615 UPDATE_1_CHECK; 0616 prob = probs + IsRepG2 + state; 0617 IF_BIT_0_CHECK(prob) 0618 { 0619 UPDATE_0_CHECK; 0620 } 0621 else 0622 { 0623 UPDATE_1_CHECK; 0624 } 0625 } 0626 } 0627 state = kNumStates; 0628 prob = probs + RepLenCoder; 0629 } 0630 { 0631 unsigned limit, offset; 0632 CLzmaProb *probLen = prob + LenChoice; 0633 IF_BIT_0_CHECK(probLen) 0634 { 0635 UPDATE_0_CHECK; 0636 probLen = prob + LenLow + (posState << kLenNumLowBits); 0637 offset = 0; 0638 limit = 1 << kLenNumLowBits; 0639 } 0640 else 0641 { 0642 UPDATE_1_CHECK; 0643 probLen = prob + LenChoice2; 0644 IF_BIT_0_CHECK(probLen) 0645 { 0646 UPDATE_0_CHECK; 0647 probLen = prob + LenMid + (posState << kLenNumMidBits); 0648 offset = kLenNumLowSymbols; 0649 limit = 1 << kLenNumMidBits; 0650 } 0651 else 0652 { 0653 UPDATE_1_CHECK; 0654 probLen = prob + LenHigh; 0655 offset = kLenNumLowSymbols + kLenNumMidSymbols; 0656 limit = 1 << kLenNumHighBits; 0657 } 0658 } 0659 TREE_DECODE_CHECK(probLen, limit, len); 0660 len += offset; 0661 } 0662 0663 if (state < 4) 0664 { 0665 unsigned posSlot; 0666 prob = probs + PosSlot + 0667 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << 0668 kNumPosSlotBits); 0669 TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot); 0670 if (posSlot >= kStartPosModelIndex) 0671 { 0672 int numDirectBits = ((posSlot >> 1) - 1); 0673 0674 /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */ 0675 0676 if (posSlot < kEndPosModelIndex) 0677 { 0678 prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1; 0679 } 0680 else 0681 { 0682 numDirectBits -= kNumAlignBits; 0683 do 0684 { 0685 NORMALIZE_CHECK 0686 range >>= 1; 0687 code -= range & (((code - range) >> 31) - 1); 0688 /* if (code >= range) code -= range; */ 0689 } 0690 while (--numDirectBits != 0); 0691 prob = probs + Align; 0692 numDirectBits = kNumAlignBits; 0693 } 0694 { 0695 unsigned i = 1; 0696 do 0697 { 0698 GET_BIT_CHECK(prob + i, i); 0699 } 0700 while (--numDirectBits != 0); 0701 } 0702 } 0703 } 0704 } 0705 } 0706 NORMALIZE_CHECK; 0707 return res; 0708 } 0709 0710 0711 static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data) 0712 { 0713 p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]); 0714 p->range = 0xFFFFFFFF; 0715 p->needFlush = 0; 0716 } 0717 0718 void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState) 0719 { 0720 p->needFlush = 1; 0721 p->remainLen = 0; 0722 p->tempBufSize = 0; 0723 0724 if (initDic) 0725 { 0726 p->processedPos = 0; 0727 p->checkDicSize = 0; 0728 p->needInitState = 1; 0729 } 0730 if (initState) 0731 p->needInitState = 1; 0732 } 0733 0734 void LzmaDec_Init(CLzmaDec *p) 0735 { 0736 p->dicPos = 0; 0737 LzmaDec_InitDicAndState(p, True, True); 0738 } 0739 0740 static void LzmaDec_InitStateReal(CLzmaDec *p) 0741 { 0742 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp)); 0743 UInt32 i; 0744 CLzmaProb *probs = p->probs; 0745 for (i = 0; i < numProbs; i++) 0746 probs[i] = kBitModelTotal >> 1; 0747 p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1; 0748 p->state = 0; 0749 p->needInitState = 0; 0750 } 0751 0752 SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen, 0753 ELzmaFinishMode finishMode, ELzmaStatus *status) 0754 { 0755 SizeT inSize = *srcLen; 0756 (*srcLen) = 0; 0757 LzmaDec_WriteRem(p, dicLimit); 0758 0759 *status = LZMA_STATUS_NOT_SPECIFIED; 0760 0761 while (p->remainLen != kMatchSpecLenStart) 0762 { 0763 int checkEndMarkNow; 0764 0765 if (p->needFlush != 0) 0766 { 0767 for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--) 0768 p->tempBuf[p->tempBufSize++] = *src++; 0769 if (p->tempBufSize < RC_INIT_SIZE) 0770 { 0771 *status = LZMA_STATUS_NEEDS_MORE_INPUT; 0772 return SZ_OK; 0773 } 0774 if (p->tempBuf[0] != 0) 0775 return SZ_ERROR_DATA; 0776 0777 LzmaDec_InitRc(p, p->tempBuf); 0778 p->tempBufSize = 0; 0779 } 0780 0781 checkEndMarkNow = 0; 0782 if (p->dicPos >= dicLimit) 0783 { 0784 if (p->remainLen == 0 && p->code == 0) 0785 { 0786 *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK; 0787 return SZ_OK; 0788 } 0789 if (finishMode == LZMA_FINISH_ANY) 0790 { 0791 *status = LZMA_STATUS_NOT_FINISHED; 0792 return SZ_OK; 0793 } 0794 if (p->remainLen != 0) 0795 { 0796 *status = LZMA_STATUS_NOT_FINISHED; 0797 return SZ_ERROR_DATA; 0798 } 0799 checkEndMarkNow = 1; 0800 } 0801 0802 if (p->needInitState) 0803 LzmaDec_InitStateReal(p); 0804 0805 if (p->tempBufSize == 0) 0806 { 0807 SizeT processed; 0808 const Byte *bufLimit; 0809 if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) 0810 { 0811 int dummyRes = LzmaDec_TryDummy(p, src, inSize); 0812 if (dummyRes == DUMMY_ERROR) 0813 { 0814 memcpy(p->tempBuf, src, inSize); 0815 p->tempBufSize = (unsigned)inSize; 0816 (*srcLen) += inSize; 0817 *status = LZMA_STATUS_NEEDS_MORE_INPUT; 0818 return SZ_OK; 0819 } 0820 if (checkEndMarkNow && dummyRes != DUMMY_MATCH) 0821 { 0822 *status = LZMA_STATUS_NOT_FINISHED; 0823 return SZ_ERROR_DATA; 0824 } 0825 bufLimit = src; 0826 } 0827 else 0828 bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX; 0829 p->buf = src; 0830 if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0) 0831 return SZ_ERROR_DATA; 0832 processed = (SizeT)(p->buf - src); 0833 (*srcLen) += processed; 0834 src += processed; 0835 inSize -= processed; 0836 } 0837 else 0838 { 0839 unsigned rem = p->tempBufSize, lookAhead = 0; 0840 while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize) 0841 p->tempBuf[rem++] = src[lookAhead++]; 0842 p->tempBufSize = rem; 0843 if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) 0844 { 0845 int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem); 0846 if (dummyRes == DUMMY_ERROR) 0847 { 0848 (*srcLen) += lookAhead; 0849 *status = LZMA_STATUS_NEEDS_MORE_INPUT; 0850 return SZ_OK; 0851 } 0852 if (checkEndMarkNow && dummyRes != DUMMY_MATCH) 0853 { 0854 *status = LZMA_STATUS_NOT_FINISHED; 0855 return SZ_ERROR_DATA; 0856 } 0857 } 0858 p->buf = p->tempBuf; 0859 if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0) 0860 return SZ_ERROR_DATA; 0861 lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf)); 0862 (*srcLen) += lookAhead; 0863 src += lookAhead; 0864 inSize -= lookAhead; 0865 p->tempBufSize = 0; 0866 } 0867 } 0868 if (p->code == 0) 0869 *status = LZMA_STATUS_FINISHED_WITH_MARK; 0870 return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA; 0871 } 0872 0873 SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status) 0874 { 0875 SizeT outSize = *destLen; 0876 SizeT inSize = *srcLen; 0877 *srcLen = *destLen = 0; 0878 for (;;) 0879 { 0880 SizeT inSizeCur = inSize, outSizeCur, dicPos; 0881 ELzmaFinishMode curFinishMode; 0882 SRes res; 0883 if (p->dicPos == p->dicBufSize) 0884 p->dicPos = 0; 0885 dicPos = p->dicPos; 0886 if (outSize > p->dicBufSize - dicPos) 0887 { 0888 outSizeCur = p->dicBufSize; 0889 curFinishMode = LZMA_FINISH_ANY; 0890 } 0891 else 0892 { 0893 outSizeCur = dicPos + outSize; 0894 curFinishMode = finishMode; 0895 } 0896 0897 res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status); 0898 src += inSizeCur; 0899 inSize -= inSizeCur; 0900 *srcLen += inSizeCur; 0901 outSizeCur = p->dicPos - dicPos; 0902 memcpy(dest, p->dic + dicPos, outSizeCur); 0903 dest += outSizeCur; 0904 outSize -= outSizeCur; 0905 *destLen += outSizeCur; 0906 if (res != 0) 0907 return res; 0908 if (outSizeCur == 0 || outSize == 0) 0909 return SZ_OK; 0910 } 0911 } 0912 0913 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc) 0914 { 0915 alloc->Free(alloc, p->probs); 0916 p->probs = 0; 0917 } 0918 0919 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc) 0920 { 0921 alloc->Free(alloc, p->dic); 0922 p->dic = 0; 0923 } 0924 0925 void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc) 0926 { 0927 LzmaDec_FreeProbs(p, alloc); 0928 LzmaDec_FreeDict(p, alloc); 0929 } 0930 0931 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size) 0932 { 0933 UInt32 dicSize; 0934 Byte d; 0935 0936 if (size < LZMA_PROPS_SIZE) 0937 return SZ_ERROR_UNSUPPORTED; 0938 else 0939 dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24); 0940 0941 if (dicSize < LZMA_DIC_MIN) 0942 dicSize = LZMA_DIC_MIN; 0943 p->dicSize = dicSize; 0944 0945 d = data[0]; 0946 if (d >= (9 * 5 * 5)) 0947 return SZ_ERROR_UNSUPPORTED; 0948 0949 p->lc = d % 9; 0950 d /= 9; 0951 p->pb = d / 5; 0952 p->lp = d % 5; 0953 0954 return SZ_OK; 0955 } 0956 0957 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc) 0958 { 0959 UInt32 numProbs = LzmaProps_GetNumProbs(propNew); 0960 if (p->probs == 0 || numProbs != p->numProbs) 0961 { 0962 LzmaDec_FreeProbs(p, alloc); 0963 p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb)); 0964 p->numProbs = numProbs; 0965 if (p->probs == 0) 0966 return SZ_ERROR_MEM; 0967 } 0968 return SZ_OK; 0969 } 0970 0971 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc) 0972 { 0973 CLzmaProps propNew; 0974 RINOK(LzmaProps_Decode(&propNew, props, propsSize)); 0975 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc)); 0976 p->prop = propNew; 0977 return SZ_OK; 0978 } 0979 0980 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc) 0981 { 0982 CLzmaProps propNew; 0983 SizeT dicBufSize; 0984 RINOK(LzmaProps_Decode(&propNew, props, propsSize)); 0985 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc)); 0986 dicBufSize = propNew.dicSize; 0987 if (p->dic == 0 || dicBufSize != p->dicBufSize) 0988 { 0989 LzmaDec_FreeDict(p, alloc); 0990 p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize); 0991 if (p->dic == 0) 0992 { 0993 LzmaDec_FreeProbs(p, alloc); 0994 return SZ_ERROR_MEM; 0995 } 0996 } 0997 p->dicBufSize = dicBufSize; 0998 p->prop = propNew; 0999 return SZ_OK; 1000 } 1001 1002 SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, 1003 const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode, 1004 ELzmaStatus *status, ISzAlloc *alloc) 1005 { 1006 CLzmaDec p; 1007 SRes res; 1008 SizeT outSize = *destLen, inSize = *srcLen; 1009 *destLen = *srcLen = 0; 1010 *status = LZMA_STATUS_NOT_SPECIFIED; 1011 if (inSize < RC_INIT_SIZE) 1012 return SZ_ERROR_INPUT_EOF; 1013 LzmaDec_Construct(&p); 1014 RINOK(LzmaDec_AllocateProbs(&p, propData, propSize, alloc)); 1015 p.dic = dest; 1016 p.dicBufSize = outSize; 1017 LzmaDec_Init(&p); 1018 *srcLen = inSize; 1019 res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status); 1020 *destLen = p.dicPos; 1021 if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT) 1022 res = SZ_ERROR_INPUT_EOF; 1023 LzmaDec_FreeProbs(&p, alloc); 1024 return res; 1025 }