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