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