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