1/* 2 LzmaDecode.c 3 LZMA Decoder 4 5 LZMA SDK 4.05 Copyright (c) 1999-2004 Igor Pavlov (2004-08-25) 6 http://www.7-zip.org/ 7 8 LZMA SDK is licensed under two licenses: 9 1) GNU Lesser General Public License (GNU LGPL) 10 2) Common Public License (CPL) 11 It means that you can select one of these two licenses and 12 follow rules of that license. 13 14 SPECIAL EXCEPTION: 15 Igor Pavlov, as the author of this code, expressly permits you to 16 statically or dynamically link your code (or bind by name) to the 17 interfaces of this file without subjecting your linked code to the 18 terms of the CPL or GNU LGPL. Any modifications or additions 19 to this file, however, are subject to the LGPL or CPL terms. 20*/ 21 22#include "LzmaDecode.h" 23 24#ifndef Byte 25#define Byte unsigned char 26#endif 27 28#define kNumTopBits 24 29#define kTopValue ((UInt32)1 << kNumTopBits) 30 31#define kNumBitModelTotalBits 11 32#define kBitModelTotal (1 << kNumBitModelTotalBits) 33#define kNumMoveBits 5 34 35typedef struct _CRangeDecoder 36{ 37 Byte *Buffer; 38 Byte *BufferLim; 39 UInt32 Range; 40 UInt32 Code; 41 #ifdef _LZMA_IN_CB 42 ILzmaInCallback *InCallback; 43 int Result; 44 #endif 45 int ExtraBytes; 46} CRangeDecoder; 47 48Byte RangeDecoderReadByte(CRangeDecoder *rd) 49{ 50 if (rd->Buffer == rd->BufferLim) 51 { 52 #ifdef _LZMA_IN_CB 53 UInt32 size; 54 rd->Result = rd->InCallback->Read(rd->InCallback, &rd->Buffer, &size); 55 rd->BufferLim = rd->Buffer + size; 56 if (size == 0) 57 #endif 58 { 59 rd->ExtraBytes = 1; 60 return 0xFF; 61 } 62 } 63 return (*rd->Buffer++); 64} 65 66/* #define ReadByte (*rd->Buffer++) */ 67#define ReadByte (RangeDecoderReadByte(rd)) 68 69void RangeDecoderInit(CRangeDecoder *rd, 70 #ifdef _LZMA_IN_CB 71 ILzmaInCallback *inCallback 72 #else 73 Byte *stream, UInt32 bufferSize 74 #endif 75 ) 76{ 77 int i; 78 #ifdef _LZMA_IN_CB 79 rd->InCallback = inCallback; 80 rd->Buffer = rd->BufferLim = 0; 81 #else 82 rd->Buffer = stream; 83 rd->BufferLim = stream + bufferSize; 84 #endif 85 rd->ExtraBytes = 0; 86 rd->Code = 0; 87 rd->Range = (0xFFFFFFFF); 88 for(i = 0; i < 5; i++) 89 rd->Code = (rd->Code << 8) | ReadByte; 90} 91 92#define RC_INIT_VAR UInt32 range = rd->Range; UInt32 code = rd->Code; 93#define RC_FLUSH_VAR rd->Range = range; rd->Code = code; 94#define RC_NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | ReadByte; } 95 96UInt32 RangeDecoderDecodeDirectBits(CRangeDecoder *rd, int numTotalBits) 97{ 98 RC_INIT_VAR 99 UInt32 result = 0; 100 int i; 101 for (i = numTotalBits; i > 0; i--) 102 { 103 /* UInt32 t; */ 104 range >>= 1; 105 106 result <<= 1; 107 if (code >= range) 108 { 109 code -= range; 110 result |= 1; 111 } 112 /* 113 t = (code - range) >> 31; 114 t &= 1; 115 code -= range & (t - 1); 116 result = (result + result) | (1 - t); 117 */ 118 RC_NORMALIZE 119 } 120 RC_FLUSH_VAR 121 return result; 122} 123 124int RangeDecoderBitDecode(CProb *prob, CRangeDecoder *rd) 125{ 126 UInt32 bound = (rd->Range >> kNumBitModelTotalBits) * *prob; 127 if (rd->Code < bound) 128 { 129 rd->Range = bound; 130 *prob += (kBitModelTotal - *prob) >> kNumMoveBits; 131 if (rd->Range < kTopValue) 132 { 133 rd->Code = (rd->Code << 8) | ReadByte; 134 rd->Range <<= 8; 135 } 136 return 0; 137 } 138 else 139 { 140 rd->Range -= bound; 141 rd->Code -= bound; 142 *prob -= (*prob) >> kNumMoveBits; 143 if (rd->Range < kTopValue) 144 { 145 rd->Code = (rd->Code << 8) | ReadByte; 146 rd->Range <<= 8; 147 } 148 return 1; 149 } 150} 151 152#define RC_GET_BIT2(prob, mi, A0, A1) \ 153 UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \ 154 if (code < bound) \ 155 { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \ 156 else \ 157 { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \ 158 RC_NORMALIZE 159 160#define RC_GET_BIT(prob, mi) RC_GET_BIT2(prob, mi, ; , ;) 161 162int RangeDecoderBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd) 163{ 164 int mi = 1; 165 int i; 166 #ifdef _LZMA_LOC_OPT 167 RC_INIT_VAR 168 #endif 169 for(i = numLevels; i > 0; i--) 170 { 171 #ifdef _LZMA_LOC_OPT 172 CProb *prob = probs + mi; 173 RC_GET_BIT(prob, mi) 174 #else 175 mi = (mi + mi) + RangeDecoderBitDecode(probs + mi, rd); 176 #endif 177 } 178 #ifdef _LZMA_LOC_OPT 179 RC_FLUSH_VAR 180 #endif 181 return mi - (1 << numLevels); 182} 183 184int RangeDecoderReverseBitTreeDecode(CProb *probs, int numLevels, CRangeDecoder *rd) 185{ 186 int mi = 1; 187 int i; 188 int symbol = 0; 189 #ifdef _LZMA_LOC_OPT 190 RC_INIT_VAR 191 #endif 192 for(i = 0; i < numLevels; i++) 193 { 194 #ifdef _LZMA_LOC_OPT 195 CProb *prob = probs + mi; 196 RC_GET_BIT2(prob, mi, ; , symbol |= (1 << i)) 197 #else 198 int bit = RangeDecoderBitDecode(probs + mi, rd); 199 mi = mi + mi + bit; 200 symbol |= (bit << i); 201 #endif 202 } 203 #ifdef _LZMA_LOC_OPT 204 RC_FLUSH_VAR 205 #endif 206 return symbol; 207} 208 209Byte LzmaLiteralDecode(CProb *probs, CRangeDecoder *rd) 210{ 211 int symbol = 1; 212 #ifdef _LZMA_LOC_OPT 213 RC_INIT_VAR 214 #endif 215 do 216 { 217 #ifdef _LZMA_LOC_OPT 218 CProb *prob = probs + symbol; 219 RC_GET_BIT(prob, symbol) 220 #else 221 symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd); 222 #endif 223 } 224 while (symbol < 0x100); 225 #ifdef _LZMA_LOC_OPT 226 RC_FLUSH_VAR 227 #endif 228 return symbol; 229} 230 231Byte LzmaLiteralDecodeMatch(CProb *probs, CRangeDecoder *rd, Byte matchByte) 232{ 233 int symbol = 1; 234 #ifdef _LZMA_LOC_OPT 235 RC_INIT_VAR 236 #endif 237 do 238 { 239 int bit; 240 int matchBit = (matchByte >> 7) & 1; 241 matchByte <<= 1; 242 #ifdef _LZMA_LOC_OPT 243 { 244 CProb *prob = probs + ((1 + matchBit) << 8) + symbol; 245 RC_GET_BIT2(prob, symbol, bit = 0, bit = 1) 246 } 247 #else 248 bit = RangeDecoderBitDecode(probs + ((1 + matchBit) << 8) + symbol, rd); 249 symbol = (symbol << 1) | bit; 250 #endif 251 if (matchBit != bit) 252 { 253 while (symbol < 0x100) 254 { 255 #ifdef _LZMA_LOC_OPT 256 CProb *prob = probs + symbol; 257 RC_GET_BIT(prob, symbol) 258 #else 259 symbol = (symbol + symbol) | RangeDecoderBitDecode(probs + symbol, rd); 260 #endif 261 } 262 break; 263 } 264 } 265 while (symbol < 0x100); 266 #ifdef _LZMA_LOC_OPT 267 RC_FLUSH_VAR 268 #endif 269 return symbol; 270} 271 272#define kNumPosBitsMax 4 273#define kNumPosStatesMax (1 << kNumPosBitsMax) 274 275#define kLenNumLowBits 3 276#define kLenNumLowSymbols (1 << kLenNumLowBits) 277#define kLenNumMidBits 3 278#define kLenNumMidSymbols (1 << kLenNumMidBits) 279#define kLenNumHighBits 8 280#define kLenNumHighSymbols (1 << kLenNumHighBits) 281 282#define LenChoice 0 283#define LenChoice2 (LenChoice + 1) 284#define LenLow (LenChoice2 + 1) 285#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) 286#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) 287#define kNumLenProbs (LenHigh + kLenNumHighSymbols) 288 289int LzmaLenDecode(CProb *p, CRangeDecoder *rd, int posState) 290{ 291 if(RangeDecoderBitDecode(p + LenChoice, rd) == 0) 292 return RangeDecoderBitTreeDecode(p + LenLow + 293 (posState << kLenNumLowBits), kLenNumLowBits, rd); 294 if(RangeDecoderBitDecode(p + LenChoice2, rd) == 0) 295 return kLenNumLowSymbols + RangeDecoderBitTreeDecode(p + LenMid + 296 (posState << kLenNumMidBits), kLenNumMidBits, rd); 297 return kLenNumLowSymbols + kLenNumMidSymbols + 298 RangeDecoderBitTreeDecode(p + LenHigh, kLenNumHighBits, rd); 299} 300 301#define kNumStates 12 302 303#define kStartPosModelIndex 4 304#define kEndPosModelIndex 14 305#define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 306 307#define kNumPosSlotBits 6 308#define kNumLenToPosStates 4 309 310#define kNumAlignBits 4 311#define kAlignTableSize (1 << kNumAlignBits) 312 313#define kMatchMinLen 2 314 315#define IsMatch 0 316#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) 317#define IsRepG0 (IsRep + kNumStates) 318#define IsRepG1 (IsRepG0 + kNumStates) 319#define IsRepG2 (IsRepG1 + kNumStates) 320#define IsRep0Long (IsRepG2 + kNumStates) 321#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) 322#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) 323#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) 324#define LenCoder (Align + kAlignTableSize) 325#define RepLenCoder (LenCoder + kNumLenProbs) 326#define Literal (RepLenCoder + kNumLenProbs) 327 328#if Literal != LZMA_BASE_SIZE 329StopCompilingDueBUG 330#endif 331 332#ifdef _LZMA_OUT_READ 333 334typedef struct _LzmaVarState 335{ 336 CRangeDecoder RangeDecoder; 337 Byte *Dictionary; 338 UInt32 DictionarySize; 339 UInt32 DictionaryPos; 340 UInt32 GlobalPos; 341 UInt32 Reps[4]; 342 int lc; 343 int lp; 344 int pb; 345 int State; 346 int PreviousIsMatch; 347 int RemainLen; 348} LzmaVarState; 349 350int LzmaDecoderInit( 351 unsigned char *buffer, UInt32 bufferSize, 352 int lc, int lp, int pb, 353 unsigned char *dictionary, UInt32 dictionarySize, 354 #ifdef _LZMA_IN_CB 355 ILzmaInCallback *inCallback 356 #else 357 unsigned char *inStream, UInt32 inSize 358 #endif 359 ) 360{ 361 LzmaVarState *vs = (LzmaVarState *)buffer; 362 CProb *p = (CProb *)(buffer + sizeof(LzmaVarState)); 363 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp)); 364 UInt32 i; 365 if (bufferSize < numProbs * sizeof(CProb) + sizeof(LzmaVarState)) 366 return LZMA_RESULT_NOT_ENOUGH_MEM; 367 vs->Dictionary = dictionary; 368 vs->DictionarySize = dictionarySize; 369 vs->DictionaryPos = 0; 370 vs->GlobalPos = 0; 371 vs->Reps[0] = vs->Reps[1] = vs->Reps[2] = vs->Reps[3] = 1; 372 vs->lc = lc; 373 vs->lp = lp; 374 vs->pb = pb; 375 vs->State = 0; 376 vs->PreviousIsMatch = 0; 377 vs->RemainLen = 0; 378 dictionary[dictionarySize - 1] = 0; 379 for (i = 0; i < numProbs; i++) 380 p[i] = kBitModelTotal >> 1; 381 RangeDecoderInit(&vs->RangeDecoder, 382 #ifdef _LZMA_IN_CB 383 inCallback 384 #else 385 inStream, inSize 386 #endif 387 ); 388 return LZMA_RESULT_OK; 389} 390 391int LzmaDecode(unsigned char *buffer, 392 unsigned char *outStream, UInt32 outSize, 393 UInt32 *outSizeProcessed) 394{ 395 LzmaVarState *vs = (LzmaVarState *)buffer; 396 CProb *p = (CProb *)(buffer + sizeof(LzmaVarState)); 397 CRangeDecoder rd = vs->RangeDecoder; 398 int state = vs->State; 399 int previousIsMatch = vs->PreviousIsMatch; 400 Byte previousByte; 401 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; 402 UInt32 nowPos = 0; 403 UInt32 posStateMask = (1 << (vs->pb)) - 1; 404 UInt32 literalPosMask = (1 << (vs->lp)) - 1; 405 int lc = vs->lc; 406 int len = vs->RemainLen; 407 UInt32 globalPos = vs->GlobalPos; 408 409 Byte *dictionary = vs->Dictionary; 410 UInt32 dictionarySize = vs->DictionarySize; 411 UInt32 dictionaryPos = vs->DictionaryPos; 412 413 if (len == -1) 414 { 415 *outSizeProcessed = 0; 416 return LZMA_RESULT_OK; 417 } 418 419 while(len > 0 && nowPos < outSize) 420 { 421 UInt32 pos = dictionaryPos - rep0; 422 if (pos >= dictionarySize) 423 pos += dictionarySize; 424 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; 425 if (++dictionaryPos == dictionarySize) 426 dictionaryPos = 0; 427 len--; 428 } 429 if (dictionaryPos == 0) 430 previousByte = dictionary[dictionarySize - 1]; 431 else 432 previousByte = dictionary[dictionaryPos - 1]; 433#else 434 435int LzmaDecode( 436 Byte *buffer, UInt32 bufferSize, 437 int lc, int lp, int pb, 438 #ifdef _LZMA_IN_CB 439 ILzmaInCallback *inCallback, 440 #else 441 unsigned char *inStream, UInt32 inSize, 442 #endif 443 unsigned char *outStream, UInt32 outSize, 444 UInt32 *outSizeProcessed) 445{ 446 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + lp)); 447 CProb *p = (CProb *)buffer; 448 CRangeDecoder rd; 449 UInt32 i; 450 int state = 0; 451 int previousIsMatch = 0; 452 Byte previousByte = 0; 453 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; 454 UInt32 nowPos = 0; 455 UInt32 posStateMask = (1 << pb) - 1; 456 UInt32 literalPosMask = (1 << lp) - 1; 457 int len = 0; 458 if (bufferSize < numProbs * sizeof(CProb)) 459 return LZMA_RESULT_NOT_ENOUGH_MEM; 460 for (i = 0; i < numProbs; i++) 461 p[i] = kBitModelTotal >> 1; 462 RangeDecoderInit(&rd, 463 #ifdef _LZMA_IN_CB 464 inCallback 465 #else 466 inStream, inSize 467 #endif 468 ); 469#endif 470 471 *outSizeProcessed = 0; 472 while(nowPos < outSize) 473 { 474 int posState = (int)( 475 (nowPos 476 #ifdef _LZMA_OUT_READ 477 + globalPos 478 #endif 479 ) 480 & posStateMask); 481 #ifdef _LZMA_IN_CB 482 if (rd.Result != LZMA_RESULT_OK) 483 return rd.Result; 484 #endif 485 if (rd.ExtraBytes != 0) 486 return LZMA_RESULT_DATA_ERROR; 487 if (RangeDecoderBitDecode(p + IsMatch + (state << kNumPosBitsMax) + posState, &rd) == 0) 488 { 489 CProb *probs = p + Literal + (LZMA_LIT_SIZE * 490 ((( 491 (nowPos 492 #ifdef _LZMA_OUT_READ 493 + globalPos 494 #endif 495 ) 496 & literalPosMask) << lc) + (previousByte >> (8 - lc)))); 497 498 if (state < 4) state = 0; 499 else if (state < 10) state -= 3; 500 else state -= 6; 501 if (previousIsMatch) 502 { 503 Byte matchByte; 504 #ifdef _LZMA_OUT_READ 505 UInt32 pos = dictionaryPos - rep0; 506 if (pos >= dictionarySize) 507 pos += dictionarySize; 508 matchByte = dictionary[pos]; 509 #else 510 matchByte = outStream[nowPos - rep0]; 511 #endif 512 previousByte = LzmaLiteralDecodeMatch(probs, &rd, matchByte); 513 previousIsMatch = 0; 514 } 515 else 516 previousByte = LzmaLiteralDecode(probs, &rd); 517 outStream[nowPos++] = previousByte; 518 #ifdef _LZMA_OUT_READ 519 dictionary[dictionaryPos] = previousByte; 520 if (++dictionaryPos == dictionarySize) 521 dictionaryPos = 0; 522 #endif 523 } 524 else 525 { 526 previousIsMatch = 1; 527 if (RangeDecoderBitDecode(p + IsRep + state, &rd) == 1) 528 { 529 if (RangeDecoderBitDecode(p + IsRepG0 + state, &rd) == 0) 530 { 531 if (RangeDecoderBitDecode(p + IsRep0Long + (state << kNumPosBitsMax) + posState, &rd) == 0) 532 { 533 #ifdef _LZMA_OUT_READ 534 UInt32 pos; 535 #endif 536 if ( 537 (nowPos 538 #ifdef _LZMA_OUT_READ 539 + globalPos 540 #endif 541 ) 542 == 0) 543 return LZMA_RESULT_DATA_ERROR; 544 state = state < 7 ? 9 : 11; 545 #ifdef _LZMA_OUT_READ 546 pos = dictionaryPos - rep0; 547 if (pos >= dictionarySize) 548 pos += dictionarySize; 549 previousByte = dictionary[pos]; 550 dictionary[dictionaryPos] = previousByte; 551 if (++dictionaryPos == dictionarySize) 552 dictionaryPos = 0; 553 #else 554 previousByte = outStream[nowPos - rep0]; 555 #endif 556 outStream[nowPos++] = previousByte; 557 continue; 558 } 559 } 560 else 561 { 562 UInt32 distance; 563 if(RangeDecoderBitDecode(p + IsRepG1 + state, &rd) == 0) 564 distance = rep1; 565 else 566 { 567 if(RangeDecoderBitDecode(p + IsRepG2 + state, &rd) == 0) 568 distance = rep2; 569 else 570 { 571 distance = rep3; 572 rep3 = rep2; 573 } 574 rep2 = rep1; 575 } 576 rep1 = rep0; 577 rep0 = distance; 578 } 579 len = LzmaLenDecode(p + RepLenCoder, &rd, posState); 580 state = state < 7 ? 8 : 11; 581 } 582 else 583 { 584 int posSlot; 585 rep3 = rep2; 586 rep2 = rep1; 587 rep1 = rep0; 588 state = state < 7 ? 7 : 10; 589 len = LzmaLenDecode(p + LenCoder, &rd, posState); 590 posSlot = RangeDecoderBitTreeDecode(p + PosSlot + 591 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << 592 kNumPosSlotBits), kNumPosSlotBits, &rd); 593 if (posSlot >= kStartPosModelIndex) 594 { 595 int numDirectBits = ((posSlot >> 1) - 1); 596 rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits); 597 if (posSlot < kEndPosModelIndex) 598 { 599 rep0 += RangeDecoderReverseBitTreeDecode( 600 p + SpecPos + rep0 - posSlot - 1, numDirectBits, &rd); 601 } 602 else 603 { 604 rep0 += RangeDecoderDecodeDirectBits(&rd, 605 numDirectBits - kNumAlignBits) << kNumAlignBits; 606 rep0 += RangeDecoderReverseBitTreeDecode(p + Align, kNumAlignBits, &rd); 607 } 608 } 609 else 610 rep0 = posSlot; 611 rep0++; 612 } 613 if (rep0 == (UInt32)(0)) 614 { 615 /* it's for stream version */ 616 len = -1; 617 break; 618 } 619 if (rep0 > nowPos 620 #ifdef _LZMA_OUT_READ 621 + globalPos 622 #endif 623 ) 624 { 625 return LZMA_RESULT_DATA_ERROR; 626 } 627 len += kMatchMinLen; 628 do 629 { 630 #ifdef _LZMA_OUT_READ 631 UInt32 pos = dictionaryPos - rep0; 632 if (pos >= dictionarySize) 633 pos += dictionarySize; 634 previousByte = dictionary[pos]; 635 dictionary[dictionaryPos] = previousByte; 636 if (++dictionaryPos == dictionarySize) 637 dictionaryPos = 0; 638 #else 639 previousByte = outStream[nowPos - rep0]; 640 #endif 641 outStream[nowPos++] = previousByte; 642 len--; 643 } 644 while(len > 0 && nowPos < outSize); 645 } 646 } 647 648 #ifdef _LZMA_OUT_READ 649 vs->RangeDecoder = rd; 650 vs->DictionaryPos = dictionaryPos; 651 vs->GlobalPos = globalPos + nowPos; 652 vs->Reps[0] = rep0; 653 vs->Reps[1] = rep1; 654 vs->Reps[2] = rep2; 655 vs->Reps[3] = rep3; 656 vs->State = state; 657 vs->PreviousIsMatch = previousIsMatch; 658 vs->RemainLen = len; 659 #endif 660 661 *outSizeProcessed = nowPos; 662 return LZMA_RESULT_OK; 663} 664