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