LzmaDec.c (33031B)
1 /* LzmaDec.c -- LZMA Decoder 2 2018-02-28 : Igor Pavlov : Public domain */ 3 4 #include "Precomp.h" 5 6 /* #include "CpuArch.h" */ 7 #include "LzmaDec.h" 8 9 #include <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 29 #define TREE_GET_BIT(probs, i) { GET_BIT2(probs + i, i, ;, ;); } 30 31 #define REV_BIT(p, i, A0, A1) IF_BIT_0(p + i) \ 32 { UPDATE_0(p + i); A0; } else \ 33 { UPDATE_1(p + i); A1; } 34 #define REV_BIT_VAR( p, i, m) REV_BIT(p, i, i += m; m += m, m += m; i += m; ) 35 #define REV_BIT_CONST(p, i, m) REV_BIT(p, i, i += m; , i += m * 2; ) 36 #define REV_BIT_LAST( p, i, m) REV_BIT(p, i, i -= m , ; ) 37 38 #define TREE_DECODE(probs, limit, i) \ 39 { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; } 40 41 /* #define _LZMA_SIZE_OPT */ 42 43 #ifdef _LZMA_SIZE_OPT 44 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i) 45 #else 46 #define TREE_6_DECODE(probs, i) \ 47 { i = 1; \ 48 TREE_GET_BIT(probs, i); \ 49 TREE_GET_BIT(probs, i); \ 50 TREE_GET_BIT(probs, i); \ 51 TREE_GET_BIT(probs, i); \ 52 TREE_GET_BIT(probs, i); \ 53 TREE_GET_BIT(probs, i); \ 54 i -= 0x40; } 55 #endif 56 57 #define NORMAL_LITER_DEC TREE_GET_BIT(prob, symbol) 58 #define MATCHED_LITER_DEC \ 59 matchByte += matchByte; \ 60 bit = offs; \ 61 offs &= matchByte; \ 62 probLit = prob + (offs + bit + symbol); \ 63 GET_BIT2(probLit, symbol, offs ^= bit; , ;) 64 65 66 67 #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); } 68 69 #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound) 70 #define UPDATE_0_CHECK range = bound; 71 #define UPDATE_1_CHECK range -= bound; code -= bound; 72 #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \ 73 { UPDATE_0_CHECK; i = (i + i); A0; } else \ 74 { UPDATE_1_CHECK; i = (i + i) + 1; A1; } 75 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;) 76 #define TREE_DECODE_CHECK(probs, limit, i) \ 77 { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; } 78 79 80 #define REV_BIT_CHECK(p, i, m) IF_BIT_0_CHECK(p + i) \ 81 { UPDATE_0_CHECK; i += m; m += m; } else \ 82 { UPDATE_1_CHECK; m += m; i += m; } 83 84 85 #define kNumPosBitsMax 4 86 #define kNumPosStatesMax (1 << kNumPosBitsMax) 87 88 #define kLenNumLowBits 3 89 #define kLenNumLowSymbols (1 << kLenNumLowBits) 90 #define kLenNumHighBits 8 91 #define kLenNumHighSymbols (1 << kLenNumHighBits) 92 93 #define LenLow 0 94 #define LenHigh (LenLow + 2 * (kNumPosStatesMax << kLenNumLowBits)) 95 #define kNumLenProbs (LenHigh + kLenNumHighSymbols) 96 97 #define LenChoice LenLow 98 #define LenChoice2 (LenLow + (1 << kLenNumLowBits)) 99 100 #define kNumStates 12 101 #define kNumStates2 16 102 #define kNumLitStates 7 103 104 #define kStartPosModelIndex 4 105 #define kEndPosModelIndex 14 106 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 107 108 #define kNumPosSlotBits 6 109 #define kNumLenToPosStates 4 110 111 #define kNumAlignBits 4 112 #define kAlignTableSize (1 << kNumAlignBits) 113 114 #define kMatchMinLen 2 115 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols * 2 + kLenNumHighSymbols) 116 117 /* External ASM code needs same CLzmaProb array layout. So don't change it. */ 118 119 /* (probs_1664) is faster and better for code size at some platforms */ 120 /* 121 #ifdef MY_CPU_X86_OR_AMD64 122 */ 123 #define kStartOffset 1664 124 #define GET_PROBS p->probs_1664 125 /* 126 #define GET_PROBS p->probs + kStartOffset 127 #else 128 #define kStartOffset 0 129 #define GET_PROBS p->probs 130 #endif 131 */ 132 133 #define SpecPos (-kStartOffset) 134 #define IsRep0Long (SpecPos + kNumFullDistances) 135 #define RepLenCoder (IsRep0Long + (kNumStates2 << kNumPosBitsMax)) 136 #define LenCoder (RepLenCoder + kNumLenProbs) 137 #define IsMatch (LenCoder + kNumLenProbs) 138 #define Align (IsMatch + (kNumStates2 << kNumPosBitsMax)) 139 #define IsRep (Align + kAlignTableSize) 140 #define IsRepG0 (IsRep + kNumStates) 141 #define IsRepG1 (IsRepG0 + kNumStates) 142 #define IsRepG2 (IsRepG1 + kNumStates) 143 #define PosSlot (IsRepG2 + kNumStates) 144 #define Literal (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) 145 #define NUM_BASE_PROBS (Literal + kStartOffset) 146 147 #if Align != 0 && kStartOffset != 0 148 #error Stop_Compiling_Bad_LZMA_kAlign 149 #endif 150 151 #if NUM_BASE_PROBS != 1984 152 #error Stop_Compiling_Bad_LZMA_PROBS 153 #endif 154 155 156 #define LZMA_LIT_SIZE 0x300 157 158 #define LzmaProps_GetNumProbs(p) (NUM_BASE_PROBS + ((UInt32)LZMA_LIT_SIZE << ((p)->lc + (p)->lp))) 159 160 161 #define CALC_POS_STATE(processedPos, pbMask) (((processedPos) & (pbMask)) << 4) 162 #define COMBINED_PS_STATE (posState + state) 163 #define GET_LEN_STATE (posState) 164 165 #define LZMA_DIC_MIN (1 << 12) 166 167 /* 168 p->remainLen : shows status of LZMA decoder: 169 < kMatchSpecLenStart : normal remain 170 = kMatchSpecLenStart : finished 171 = kMatchSpecLenStart + 1 : need init range coder 172 = kMatchSpecLenStart + 2 : need init range coder and state 173 */ 174 175 /* ---------- LZMA_DECODE_REAL ---------- */ 176 /* 177 LzmaDec_DecodeReal_3() can be implemented in external ASM file. 178 3 - is the code compatibility version of that function for check at link time. 179 */ 180 181 #define LZMA_DECODE_REAL LzmaDec_DecodeReal_3 182 183 /* 184 LZMA_DECODE_REAL() 185 In: 186 RangeCoder is normalized 187 if (p->dicPos == limit) 188 { 189 LzmaDec_TryDummy() was called before to exclude LITERAL and MATCH-REP cases. 190 So first symbol can be only MATCH-NON-REP. And if that MATCH-NON-REP symbol 191 is not END_OF_PAYALOAD_MARKER, then function returns error code. 192 } 193 194 Processing: 195 first LZMA symbol will be decoded in any case 196 All checks for limits are at the end of main loop, 197 It will decode new LZMA-symbols while (p->buf < bufLimit && dicPos < limit), 198 RangeCoder is still without last normalization when (p->buf < bufLimit) is being checked. 199 200 Out: 201 RangeCoder is normalized 202 Result: 203 SZ_OK - OK 204 SZ_ERROR_DATA - Error 205 p->remainLen: 206 < kMatchSpecLenStart : normal remain 207 = kMatchSpecLenStart : finished 208 */ 209 210 211 #ifdef _LZMA_DEC_OPT 212 213 int MY_FAST_CALL LZMA_DECODE_REAL(CLzmaDec *p, SizeT limit, const Byte *bufLimit); 214 215 #else 216 217 static 218 int MY_FAST_CALL LZMA_DECODE_REAL(CLzmaDec *p, SizeT limit, const Byte *bufLimit) 219 { 220 CLzmaProb *probs = GET_PROBS; 221 unsigned state = (unsigned)p->state; 222 UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3]; 223 unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1; 224 unsigned lc = p->prop.lc; 225 unsigned lpMask = ((unsigned)0x100 << p->prop.lp) - ((unsigned)0x100 >> lc); 226 227 Byte *dic = p->dic; 228 SizeT dicBufSize = p->dicBufSize; 229 SizeT dicPos = p->dicPos; 230 231 UInt32 processedPos = p->processedPos; 232 UInt32 checkDicSize = p->checkDicSize; 233 unsigned len = 0; 234 235 const Byte *buf = p->buf; 236 UInt32 range = p->range; 237 UInt32 code = p->code; 238 239 do 240 { 241 CLzmaProb *prob; 242 UInt32 bound; 243 unsigned ttt; 244 unsigned posState = CALC_POS_STATE(processedPos, pbMask); 245 246 prob = probs + IsMatch + COMBINED_PS_STATE; 247 IF_BIT_0(prob) 248 { 249 unsigned symbol; 250 UPDATE_0(prob); 251 prob = probs + Literal; 252 if (processedPos != 0 || checkDicSize != 0) 253 prob += (UInt32)3 * ((((processedPos << 8) + dic[(dicPos == 0 ? dicBufSize : dicPos) - 1]) & lpMask) << lc); 254 processedPos++; 255 256 if (state < kNumLitStates) 257 { 258 state -= (state < 4) ? state : 3; 259 symbol = 1; 260 #ifdef _LZMA_SIZE_OPT 261 do { NORMAL_LITER_DEC } while (symbol < 0x100); 262 #else 263 NORMAL_LITER_DEC 264 NORMAL_LITER_DEC 265 NORMAL_LITER_DEC 266 NORMAL_LITER_DEC 267 NORMAL_LITER_DEC 268 NORMAL_LITER_DEC 269 NORMAL_LITER_DEC 270 NORMAL_LITER_DEC 271 #endif 272 } 273 else 274 { 275 unsigned matchByte = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)]; 276 unsigned offs = 0x100; 277 state -= (state < 10) ? 3 : 6; 278 symbol = 1; 279 #ifdef _LZMA_SIZE_OPT 280 do 281 { 282 unsigned bit; 283 CLzmaProb *probLit; 284 MATCHED_LITER_DEC 285 } 286 while (symbol < 0x100); 287 #else 288 { 289 unsigned bit; 290 CLzmaProb *probLit; 291 MATCHED_LITER_DEC 292 MATCHED_LITER_DEC 293 MATCHED_LITER_DEC 294 MATCHED_LITER_DEC 295 MATCHED_LITER_DEC 296 MATCHED_LITER_DEC 297 MATCHED_LITER_DEC 298 MATCHED_LITER_DEC 299 } 300 #endif 301 } 302 303 dic[dicPos++] = (Byte)symbol; 304 continue; 305 } 306 307 { 308 UPDATE_1(prob); 309 prob = probs + IsRep + state; 310 IF_BIT_0(prob) 311 { 312 UPDATE_0(prob); 313 state += kNumStates; 314 prob = probs + LenCoder; 315 } 316 else 317 { 318 UPDATE_1(prob); 319 /* 320 // that case was checked before with kBadRepCode 321 if (checkDicSize == 0 && processedPos == 0) 322 return SZ_ERROR_DATA; 323 */ 324 prob = probs + IsRepG0 + state; 325 IF_BIT_0(prob) 326 { 327 UPDATE_0(prob); 328 prob = probs + IsRep0Long + COMBINED_PS_STATE; 329 IF_BIT_0(prob) 330 { 331 UPDATE_0(prob); 332 dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)]; 333 dicPos++; 334 processedPos++; 335 state = state < kNumLitStates ? 9 : 11; 336 continue; 337 } 338 UPDATE_1(prob); 339 } 340 else 341 { 342 UInt32 distance; 343 UPDATE_1(prob); 344 prob = probs + IsRepG1 + state; 345 IF_BIT_0(prob) 346 { 347 UPDATE_0(prob); 348 distance = rep1; 349 } 350 else 351 { 352 UPDATE_1(prob); 353 prob = probs + IsRepG2 + state; 354 IF_BIT_0(prob) 355 { 356 UPDATE_0(prob); 357 distance = rep2; 358 } 359 else 360 { 361 UPDATE_1(prob); 362 distance = rep3; 363 rep3 = rep2; 364 } 365 rep2 = rep1; 366 } 367 rep1 = rep0; 368 rep0 = distance; 369 } 370 state = state < kNumLitStates ? 8 : 11; 371 prob = probs + RepLenCoder; 372 } 373 374 #ifdef _LZMA_SIZE_OPT 375 { 376 unsigned lim, offset; 377 CLzmaProb *probLen = prob + LenChoice; 378 IF_BIT_0(probLen) 379 { 380 UPDATE_0(probLen); 381 probLen = prob + LenLow + GET_LEN_STATE; 382 offset = 0; 383 lim = (1 << kLenNumLowBits); 384 } 385 else 386 { 387 UPDATE_1(probLen); 388 probLen = prob + LenChoice2; 389 IF_BIT_0(probLen) 390 { 391 UPDATE_0(probLen); 392 probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits); 393 offset = kLenNumLowSymbols; 394 lim = (1 << kLenNumLowBits); 395 } 396 else 397 { 398 UPDATE_1(probLen); 399 probLen = prob + LenHigh; 400 offset = kLenNumLowSymbols * 2; 401 lim = (1 << kLenNumHighBits); 402 } 403 } 404 TREE_DECODE(probLen, lim, len); 405 len += offset; 406 } 407 #else 408 { 409 CLzmaProb *probLen = prob + LenChoice; 410 IF_BIT_0(probLen) 411 { 412 UPDATE_0(probLen); 413 probLen = prob + LenLow + GET_LEN_STATE; 414 len = 1; 415 TREE_GET_BIT(probLen, len); 416 TREE_GET_BIT(probLen, len); 417 TREE_GET_BIT(probLen, len); 418 len -= 8; 419 } 420 else 421 { 422 UPDATE_1(probLen); 423 probLen = prob + LenChoice2; 424 IF_BIT_0(probLen) 425 { 426 UPDATE_0(probLen); 427 probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits); 428 len = 1; 429 TREE_GET_BIT(probLen, len); 430 TREE_GET_BIT(probLen, len); 431 TREE_GET_BIT(probLen, len); 432 } 433 else 434 { 435 UPDATE_1(probLen); 436 probLen = prob + LenHigh; 437 TREE_DECODE(probLen, (1 << kLenNumHighBits), len); 438 len += kLenNumLowSymbols * 2; 439 } 440 } 441 } 442 #endif 443 444 if (state >= kNumStates) 445 { 446 UInt32 distance; 447 prob = probs + PosSlot + 448 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits); 449 TREE_6_DECODE(prob, distance); 450 if (distance >= kStartPosModelIndex) 451 { 452 unsigned posSlot = (unsigned)distance; 453 unsigned numDirectBits = (unsigned)(((distance >> 1) - 1)); 454 distance = (2 | (distance & 1)); 455 if (posSlot < kEndPosModelIndex) 456 { 457 distance <<= numDirectBits; 458 prob = probs + SpecPos; 459 { 460 UInt32 m = 1; 461 distance++; 462 do 463 { 464 REV_BIT_VAR(prob, distance, m); 465 } 466 while (--numDirectBits); 467 distance -= m; 468 } 469 } 470 else 471 { 472 numDirectBits -= kNumAlignBits; 473 do 474 { 475 NORMALIZE 476 range >>= 1; 477 478 { 479 UInt32 t; 480 code -= range; 481 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */ 482 distance = (distance << 1) + (t + 1); 483 code += range & t; 484 } 485 /* 486 distance <<= 1; 487 if (code >= range) 488 { 489 code -= range; 490 distance |= 1; 491 } 492 */ 493 } 494 while (--numDirectBits); 495 prob = probs + Align; 496 distance <<= kNumAlignBits; 497 { 498 unsigned i = 1; 499 REV_BIT_CONST(prob, i, 1); 500 REV_BIT_CONST(prob, i, 2); 501 REV_BIT_CONST(prob, i, 4); 502 REV_BIT_LAST (prob, i, 8); 503 distance |= i; 504 } 505 if (distance == (UInt32)0xFFFFFFFF) 506 { 507 len = kMatchSpecLenStart; 508 state -= kNumStates; 509 break; 510 } 511 } 512 } 513 514 rep3 = rep2; 515 rep2 = rep1; 516 rep1 = rep0; 517 rep0 = distance + 1; 518 state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3; 519 if (distance >= (checkDicSize == 0 ? processedPos: checkDicSize)) 520 { 521 p->dicPos = dicPos; 522 return SZ_ERROR_DATA; 523 } 524 } 525 526 len += kMatchMinLen; 527 528 { 529 SizeT rem; 530 unsigned curLen; 531 SizeT pos; 532 533 if ((rem = limit - dicPos) == 0) 534 { 535 p->dicPos = dicPos; 536 return SZ_ERROR_DATA; 537 } 538 539 curLen = ((rem < len) ? (unsigned)rem : len); 540 pos = dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0); 541 542 processedPos += curLen; 543 544 len -= curLen; 545 if (curLen <= dicBufSize - pos) 546 { 547 Byte *dest = dic + dicPos; 548 ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos; 549 const Byte *lim = dest + curLen; 550 dicPos += curLen; 551 do 552 *(dest) = (Byte)*(dest + src); 553 while (++dest != lim); 554 } 555 else 556 { 557 do 558 { 559 dic[dicPos++] = dic[pos]; 560 if (++pos == dicBufSize) 561 pos = 0; 562 } 563 while (--curLen != 0); 564 } 565 } 566 } 567 } 568 while (dicPos < limit && buf < bufLimit); 569 570 NORMALIZE; 571 572 p->buf = buf; 573 p->range = range; 574 p->code = code; 575 p->remainLen = len; 576 p->dicPos = dicPos; 577 p->processedPos = processedPos; 578 p->reps[0] = rep0; 579 p->reps[1] = rep1; 580 p->reps[2] = rep2; 581 p->reps[3] = rep3; 582 p->state = state; 583 584 return SZ_OK; 585 } 586 #endif 587 588 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit) 589 { 590 if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart) 591 { 592 Byte *dic = p->dic; 593 SizeT dicPos = p->dicPos; 594 SizeT dicBufSize = p->dicBufSize; 595 unsigned len = (unsigned)p->remainLen; 596 SizeT rep0 = p->reps[0]; /* we use SizeT to avoid the BUG of VC14 for AMD64 */ 597 SizeT rem = limit - dicPos; 598 if (rem < len) 599 len = (unsigned)(rem); 600 601 if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len) 602 p->checkDicSize = p->prop.dicSize; 603 604 p->processedPos += len; 605 p->remainLen -= len; 606 while (len != 0) 607 { 608 len--; 609 dic[dicPos] = dic[dicPos - rep0 + (dicPos < rep0 ? dicBufSize : 0)]; 610 dicPos++; 611 } 612 p->dicPos = dicPos; 613 } 614 } 615 616 617 #define kRange0 0xFFFFFFFF 618 #define kBound0 ((kRange0 >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1)) 619 #define kBadRepCode (kBound0 + (((kRange0 - kBound0) >> kNumBitModelTotalBits) << (kNumBitModelTotalBits - 1))) 620 #if kBadRepCode != (0xC0000000 - 0x400) 621 #error Stop_Compiling_Bad_LZMA_Check 622 #endif 623 624 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit) 625 { 626 do 627 { 628 SizeT limit2 = limit; 629 if (p->checkDicSize == 0) 630 { 631 UInt32 rem = p->prop.dicSize - p->processedPos; 632 if (limit - p->dicPos > rem) 633 limit2 = p->dicPos + rem; 634 635 if (p->processedPos == 0) 636 if (p->code >= kBadRepCode) 637 return SZ_ERROR_DATA; 638 } 639 640 RINOK(LZMA_DECODE_REAL(p, limit2, bufLimit)); 641 642 if (p->checkDicSize == 0 && p->processedPos >= p->prop.dicSize) 643 p->checkDicSize = p->prop.dicSize; 644 645 LzmaDec_WriteRem(p, limit); 646 } 647 while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart); 648 649 return 0; 650 } 651 652 typedef enum 653 { 654 DUMMY_ERROR, /* unexpected end of input stream */ 655 DUMMY_LIT, 656 DUMMY_MATCH, 657 DUMMY_REP 658 } ELzmaDummy; 659 660 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize) 661 { 662 UInt32 range = p->range; 663 UInt32 code = p->code; 664 const Byte *bufLimit = buf + inSize; 665 const CLzmaProb *probs = GET_PROBS; 666 unsigned state = (unsigned)p->state; 667 ELzmaDummy res; 668 669 { 670 const CLzmaProb *prob; 671 UInt32 bound; 672 unsigned ttt; 673 unsigned posState = CALC_POS_STATE(p->processedPos, (1 << p->prop.pb) - 1); 674 675 prob = probs + IsMatch + COMBINED_PS_STATE; 676 IF_BIT_0_CHECK(prob) 677 { 678 UPDATE_0_CHECK 679 680 /* if (bufLimit - buf >= 7) return DUMMY_LIT; */ 681 682 prob = probs + Literal; 683 if (p->checkDicSize != 0 || p->processedPos != 0) 684 prob += ((UInt32)LZMA_LIT_SIZE * 685 ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) + 686 (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc)))); 687 688 if (state < kNumLitStates) 689 { 690 unsigned symbol = 1; 691 do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100); 692 } 693 else 694 { 695 unsigned matchByte = p->dic[p->dicPos - p->reps[0] + 696 (p->dicPos < p->reps[0] ? p->dicBufSize : 0)]; 697 unsigned offs = 0x100; 698 unsigned symbol = 1; 699 do 700 { 701 unsigned bit; 702 const CLzmaProb *probLit; 703 matchByte += matchByte; 704 bit = offs; 705 offs &= matchByte; 706 probLit = prob + (offs + bit + symbol); 707 GET_BIT2_CHECK(probLit, symbol, offs ^= bit; , ; ) 708 } 709 while (symbol < 0x100); 710 } 711 res = DUMMY_LIT; 712 } 713 else 714 { 715 unsigned len; 716 UPDATE_1_CHECK; 717 718 prob = probs + IsRep + state; 719 IF_BIT_0_CHECK(prob) 720 { 721 UPDATE_0_CHECK; 722 state = 0; 723 prob = probs + LenCoder; 724 res = DUMMY_MATCH; 725 } 726 else 727 { 728 UPDATE_1_CHECK; 729 res = DUMMY_REP; 730 prob = probs + IsRepG0 + state; 731 IF_BIT_0_CHECK(prob) 732 { 733 UPDATE_0_CHECK; 734 prob = probs + IsRep0Long + COMBINED_PS_STATE; 735 IF_BIT_0_CHECK(prob) 736 { 737 UPDATE_0_CHECK; 738 NORMALIZE_CHECK; 739 return DUMMY_REP; 740 } 741 else 742 { 743 UPDATE_1_CHECK; 744 } 745 } 746 else 747 { 748 UPDATE_1_CHECK; 749 prob = probs + IsRepG1 + state; 750 IF_BIT_0_CHECK(prob) 751 { 752 UPDATE_0_CHECK; 753 } 754 else 755 { 756 UPDATE_1_CHECK; 757 prob = probs + IsRepG2 + state; 758 IF_BIT_0_CHECK(prob) 759 { 760 UPDATE_0_CHECK; 761 } 762 else 763 { 764 UPDATE_1_CHECK; 765 } 766 } 767 } 768 state = kNumStates; 769 prob = probs + RepLenCoder; 770 } 771 { 772 unsigned limit, offset; 773 const CLzmaProb *probLen = prob + LenChoice; 774 IF_BIT_0_CHECK(probLen) 775 { 776 UPDATE_0_CHECK; 777 probLen = prob + LenLow + GET_LEN_STATE; 778 offset = 0; 779 limit = 1 << kLenNumLowBits; 780 } 781 else 782 { 783 UPDATE_1_CHECK; 784 probLen = prob + LenChoice2; 785 IF_BIT_0_CHECK(probLen) 786 { 787 UPDATE_0_CHECK; 788 probLen = prob + LenLow + GET_LEN_STATE + (1 << kLenNumLowBits); 789 offset = kLenNumLowSymbols; 790 limit = 1 << kLenNumLowBits; 791 } 792 else 793 { 794 UPDATE_1_CHECK; 795 probLen = prob + LenHigh; 796 offset = kLenNumLowSymbols * 2; 797 limit = 1 << kLenNumHighBits; 798 } 799 } 800 TREE_DECODE_CHECK(probLen, limit, len); 801 len += offset; 802 } 803 804 if (state < 4) 805 { 806 unsigned posSlot; 807 prob = probs + PosSlot + 808 ((len < kNumLenToPosStates - 1 ? len : kNumLenToPosStates - 1) << 809 kNumPosSlotBits); 810 TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot); 811 if (posSlot >= kStartPosModelIndex) 812 { 813 unsigned numDirectBits = ((posSlot >> 1) - 1); 814 815 /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */ 816 817 if (posSlot < kEndPosModelIndex) 818 { 819 prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits); 820 } 821 else 822 { 823 numDirectBits -= kNumAlignBits; 824 do 825 { 826 NORMALIZE_CHECK 827 range >>= 1; 828 code -= range & (((code - range) >> 31) - 1); 829 /* if (code >= range) code -= range; */ 830 } 831 while (--numDirectBits); 832 prob = probs + Align; 833 numDirectBits = kNumAlignBits; 834 } 835 { 836 unsigned i = 1; 837 unsigned m = 1; 838 do 839 { 840 REV_BIT_CHECK(prob, i, m); 841 } 842 while (--numDirectBits); 843 } 844 } 845 } 846 } 847 } 848 NORMALIZE_CHECK; 849 return res; 850 } 851 852 853 void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState) 854 { 855 p->remainLen = kMatchSpecLenStart + 1; 856 p->tempBufSize = 0; 857 858 if (initDic) 859 { 860 p->processedPos = 0; 861 p->checkDicSize = 0; 862 p->remainLen = kMatchSpecLenStart + 2; 863 } 864 if (initState) 865 p->remainLen = kMatchSpecLenStart + 2; 866 } 867 868 void LzmaDec_Init(CLzmaDec *p) 869 { 870 p->dicPos = 0; 871 LzmaDec_InitDicAndState(p, True, True); 872 } 873 874 875 SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen, 876 ELzmaFinishMode finishMode, ELzmaStatus *status) 877 { 878 SizeT inSize = *srcLen; 879 (*srcLen) = 0; 880 881 *status = LZMA_STATUS_NOT_SPECIFIED; 882 883 if (p->remainLen > kMatchSpecLenStart) 884 { 885 for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--) 886 p->tempBuf[p->tempBufSize++] = *src++; 887 if (p->tempBufSize != 0 && p->tempBuf[0] != 0) 888 return SZ_ERROR_DATA; 889 if (p->tempBufSize < RC_INIT_SIZE) 890 { 891 *status = LZMA_STATUS_NEEDS_MORE_INPUT; 892 return SZ_OK; 893 } 894 p->code = 895 ((UInt32)p->tempBuf[1] << 24) 896 | ((UInt32)p->tempBuf[2] << 16) 897 | ((UInt32)p->tempBuf[3] << 8) 898 | ((UInt32)p->tempBuf[4]); 899 p->range = 0xFFFFFFFF; 900 p->tempBufSize = 0; 901 902 if (p->remainLen > kMatchSpecLenStart + 1) 903 { 904 SizeT numProbs = LzmaProps_GetNumProbs(&p->prop); 905 SizeT i; 906 CLzmaProb *probs = p->probs; 907 for (i = 0; i < numProbs; i++) 908 probs[i] = kBitModelTotal >> 1; 909 p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1; 910 p->state = 0; 911 } 912 913 p->remainLen = 0; 914 } 915 916 LzmaDec_WriteRem(p, dicLimit); 917 918 while (p->remainLen != kMatchSpecLenStart) 919 { 920 int checkEndMarkNow = 0; 921 922 if (p->dicPos >= dicLimit) 923 { 924 if (p->remainLen == 0 && p->code == 0) 925 { 926 *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK; 927 return SZ_OK; 928 } 929 if (finishMode == LZMA_FINISH_ANY) 930 { 931 *status = LZMA_STATUS_NOT_FINISHED; 932 return SZ_OK; 933 } 934 if (p->remainLen != 0) 935 { 936 *status = LZMA_STATUS_NOT_FINISHED; 937 return SZ_ERROR_DATA; 938 } 939 checkEndMarkNow = 1; 940 } 941 942 if (p->tempBufSize == 0) 943 { 944 SizeT processed; 945 const Byte *bufLimit; 946 if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) 947 { 948 int dummyRes = LzmaDec_TryDummy(p, src, inSize); 949 if (dummyRes == DUMMY_ERROR) 950 { 951 memcpy(p->tempBuf, src, inSize); 952 p->tempBufSize = (unsigned)inSize; 953 (*srcLen) += inSize; 954 *status = LZMA_STATUS_NEEDS_MORE_INPUT; 955 return SZ_OK; 956 } 957 if (checkEndMarkNow && dummyRes != DUMMY_MATCH) 958 { 959 *status = LZMA_STATUS_NOT_FINISHED; 960 return SZ_ERROR_DATA; 961 } 962 bufLimit = src; 963 } 964 else 965 bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX; 966 p->buf = src; 967 if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0) 968 return SZ_ERROR_DATA; 969 processed = (SizeT)(p->buf - src); 970 (*srcLen) += processed; 971 src += processed; 972 inSize -= processed; 973 } 974 else 975 { 976 unsigned rem = p->tempBufSize, lookAhead = 0; 977 while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize) 978 p->tempBuf[rem++] = src[lookAhead++]; 979 p->tempBufSize = rem; 980 if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow) 981 { 982 int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem); 983 if (dummyRes == DUMMY_ERROR) 984 { 985 (*srcLen) += lookAhead; 986 *status = LZMA_STATUS_NEEDS_MORE_INPUT; 987 return SZ_OK; 988 } 989 if (checkEndMarkNow && dummyRes != DUMMY_MATCH) 990 { 991 *status = LZMA_STATUS_NOT_FINISHED; 992 return SZ_ERROR_DATA; 993 } 994 } 995 p->buf = p->tempBuf; 996 if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0) 997 return SZ_ERROR_DATA; 998 999 { 1000 unsigned kkk = (unsigned)(p->buf - p->tempBuf); 1001 if (rem < kkk) 1002 return SZ_ERROR_FAIL; /* some internal error */ 1003 rem -= kkk; 1004 if (lookAhead < rem) 1005 return SZ_ERROR_FAIL; /* some internal error */ 1006 lookAhead -= rem; 1007 } 1008 (*srcLen) += lookAhead; 1009 src += lookAhead; 1010 inSize -= lookAhead; 1011 p->tempBufSize = 0; 1012 } 1013 } 1014 1015 if (p->code != 0) 1016 return SZ_ERROR_DATA; 1017 *status = LZMA_STATUS_FINISHED_WITH_MARK; 1018 return SZ_OK; 1019 } 1020 1021 1022 SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status) 1023 { 1024 SizeT outSize = *destLen; 1025 SizeT inSize = *srcLen; 1026 *srcLen = *destLen = 0; 1027 for (;;) 1028 { 1029 SizeT inSizeCur = inSize, outSizeCur, dicPos; 1030 ELzmaFinishMode curFinishMode; 1031 SRes res; 1032 if (p->dicPos == p->dicBufSize) 1033 p->dicPos = 0; 1034 dicPos = p->dicPos; 1035 if (outSize > p->dicBufSize - dicPos) 1036 { 1037 outSizeCur = p->dicBufSize; 1038 curFinishMode = LZMA_FINISH_ANY; 1039 } 1040 else 1041 { 1042 outSizeCur = dicPos + outSize; 1043 curFinishMode = finishMode; 1044 } 1045 1046 res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status); 1047 src += inSizeCur; 1048 inSize -= inSizeCur; 1049 *srcLen += inSizeCur; 1050 outSizeCur = p->dicPos - dicPos; 1051 memcpy(dest, p->dic + dicPos, outSizeCur); 1052 dest += outSizeCur; 1053 outSize -= outSizeCur; 1054 *destLen += outSizeCur; 1055 if (res != 0) 1056 return res; 1057 if (outSizeCur == 0 || outSize == 0) 1058 return SZ_OK; 1059 } 1060 } 1061 1062 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAllocPtr alloc) 1063 { 1064 ISzAlloc_Free(alloc, p->probs); 1065 p->probs = NULL; 1066 } 1067 1068 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAllocPtr alloc) 1069 { 1070 ISzAlloc_Free(alloc, p->dic); 1071 p->dic = NULL; 1072 } 1073 1074 void LzmaDec_Free(CLzmaDec *p, ISzAllocPtr alloc) 1075 { 1076 LzmaDec_FreeProbs(p, alloc); 1077 LzmaDec_FreeDict(p, alloc); 1078 } 1079 1080 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size) 1081 { 1082 UInt32 dicSize; 1083 Byte d; 1084 1085 if (size < LZMA_PROPS_SIZE) 1086 return SZ_ERROR_UNSUPPORTED; 1087 else 1088 dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24); 1089 1090 if (dicSize < LZMA_DIC_MIN) 1091 dicSize = LZMA_DIC_MIN; 1092 p->dicSize = dicSize; 1093 1094 d = data[0]; 1095 if (d >= (9 * 5 * 5)) 1096 return SZ_ERROR_UNSUPPORTED; 1097 1098 p->lc = (Byte)(d % 9); 1099 d /= 9; 1100 p->pb = (Byte)(d / 5); 1101 p->lp = (Byte)(d % 5); 1102 1103 return SZ_OK; 1104 } 1105 1106 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAllocPtr alloc) 1107 { 1108 UInt32 numProbs = LzmaProps_GetNumProbs(propNew); 1109 if (!p->probs || numProbs != p->numProbs) 1110 { 1111 LzmaDec_FreeProbs(p, alloc); 1112 p->probs = (CLzmaProb *)ISzAlloc_Alloc(alloc, numProbs * sizeof(CLzmaProb)); 1113 if (!p->probs) 1114 return SZ_ERROR_MEM; 1115 p->probs_1664 = p->probs + 1664; 1116 p->numProbs = numProbs; 1117 } 1118 return SZ_OK; 1119 } 1120 1121 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAllocPtr alloc) 1122 { 1123 CLzmaProps propNew; 1124 RINOK(LzmaProps_Decode(&propNew, props, propsSize)); 1125 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc)); 1126 p->prop = propNew; 1127 return SZ_OK; 1128 } 1129 1130 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAllocPtr alloc) 1131 { 1132 CLzmaProps propNew; 1133 SizeT dicBufSize; 1134 RINOK(LzmaProps_Decode(&propNew, props, propsSize)); 1135 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc)); 1136 1137 { 1138 UInt32 dictSize = propNew.dicSize; 1139 SizeT mask = ((UInt32)1 << 12) - 1; 1140 if (dictSize >= ((UInt32)1 << 30)) mask = ((UInt32)1 << 22) - 1; 1141 else if (dictSize >= ((UInt32)1 << 22)) mask = ((UInt32)1 << 20) - 1;; 1142 dicBufSize = ((SizeT)dictSize + mask) & ~mask; 1143 if (dicBufSize < dictSize) 1144 dicBufSize = dictSize; 1145 } 1146 1147 if (!p->dic || dicBufSize != p->dicBufSize) 1148 { 1149 LzmaDec_FreeDict(p, alloc); 1150 p->dic = (Byte *)ISzAlloc_Alloc(alloc, dicBufSize); 1151 if (!p->dic) 1152 { 1153 LzmaDec_FreeProbs(p, alloc); 1154 return SZ_ERROR_MEM; 1155 } 1156 } 1157 p->dicBufSize = dicBufSize; 1158 p->prop = propNew; 1159 return SZ_OK; 1160 } 1161 1162 SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, 1163 const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode, 1164 ELzmaStatus *status, ISzAllocPtr alloc) 1165 { 1166 CLzmaDec p; 1167 SRes res; 1168 SizeT outSize = *destLen, inSize = *srcLen; 1169 *destLen = *srcLen = 0; 1170 *status = LZMA_STATUS_NOT_SPECIFIED; 1171 if (inSize < RC_INIT_SIZE) 1172 return SZ_ERROR_INPUT_EOF; 1173 LzmaDec_Construct(&p); 1174 RINOK(LzmaDec_AllocateProbs(&p, propData, propSize, alloc)); 1175 p.dic = dest; 1176 p.dicBufSize = outSize; 1177 LzmaDec_Init(&p); 1178 *srcLen = inSize; 1179 res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status); 1180 *destLen = p.dicPos; 1181 if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT) 1182 res = SZ_ERROR_INPUT_EOF; 1183 LzmaDec_FreeProbs(&p, alloc); 1184 return res; 1185 }