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