1/* 2 LzmaDecode.c 3 LZMA Decoder (optimized for Speed version) 4 5 LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10) 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 35#define RC_READ_BYTE (*Buffer++) 36 37#define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \ 38 { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }} 39 40#ifdef _LZMA_IN_CB 41 42#define RC_TEST { if (Buffer == BufferLim) \ 43 { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \ 44 BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }} 45 46#define RC_INIT Buffer = BufferLim = 0; RC_INIT2 47 48#else 49 50#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; } 51 52#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2 53 54#endif 55 56#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; } 57 58#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound) 59#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits; 60#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits; 61 62#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \ 63 { UpdateBit0(p); mi <<= 1; A0; } else \ 64 { UpdateBit1(p); mi = (mi + mi) + 1; A1; } 65 66#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;) 67 68#define RangeDecoderBitTreeDecode(probs, numLevels, res) \ 69 { int i = numLevels; res = 1; \ 70 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \ 71 res -= (1 << numLevels); } 72 73 74#define kNumPosBitsMax 4 75#define kNumPosStatesMax (1 << kNumPosBitsMax) 76 77#define kLenNumLowBits 3 78#define kLenNumLowSymbols (1 << kLenNumLowBits) 79#define kLenNumMidBits 3 80#define kLenNumMidSymbols (1 << kLenNumMidBits) 81#define kLenNumHighBits 8 82#define kLenNumHighSymbols (1 << kLenNumHighBits) 83 84#define LenChoice 0 85#define LenChoice2 (LenChoice + 1) 86#define LenLow (LenChoice2 + 1) 87#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) 88#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) 89#define kNumLenProbs (LenHigh + kLenNumHighSymbols) 90 91 92#define kNumStates 12 93#define kNumLitStates 7 94 95#define kStartPosModelIndex 4 96#define kEndPosModelIndex 14 97#define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) 98 99#define kNumPosSlotBits 6 100#define kNumLenToPosStates 4 101 102#define kNumAlignBits 4 103#define kAlignTableSize (1 << kNumAlignBits) 104 105#define kMatchMinLen 2 106 107#define IsMatch 0 108#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) 109#define IsRepG0 (IsRep + kNumStates) 110#define IsRepG1 (IsRepG0 + kNumStates) 111#define IsRepG2 (IsRepG1 + kNumStates) 112#define IsRep0Long (IsRepG2 + kNumStates) 113#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) 114#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) 115#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) 116#define LenCoder (Align + kAlignTableSize) 117#define RepLenCoder (LenCoder + kNumLenProbs) 118#define Literal (RepLenCoder + kNumLenProbs) 119 120#if Literal != LZMA_BASE_SIZE 121StopCompilingDueBUG 122#endif 123 124#if 0 125int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size) 126{ 127 unsigned char prop0; 128 if (size < LZMA_PROPERTIES_SIZE) 129 return LZMA_RESULT_DATA_ERROR; 130 prop0 = propsData[0]; 131 if (prop0 >= (9 * 5 * 5)) 132 return LZMA_RESULT_DATA_ERROR; 133 { 134 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5)); 135 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9); 136 propsRes->lc = prop0; 137 /* 138 unsigned char remainder = (unsigned char)(prop0 / 9); 139 propsRes->lc = prop0 % 9; 140 propsRes->pb = remainder / 5; 141 propsRes->lp = remainder % 5; 142 */ 143 } 144 145 #ifdef _LZMA_OUT_READ 146 { 147 int i; 148 propsRes->DictionarySize = 0; 149 for (i = 0; i < 4; i++) 150 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8); 151 if (propsRes->DictionarySize == 0) 152 propsRes->DictionarySize = 1; 153 } 154 #endif 155 return LZMA_RESULT_OK; 156} 157#endif 158 159#define kLzmaStreamWasFinishedId (-1) 160 161int LzmaDecode(CLzmaDecoderState *vs, 162 #ifdef _LZMA_IN_CB 163 ILzmaInCallback *InCallback, 164 #else 165 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, 166 #endif 167 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed) 168{ 169 CProb *p = vs->Probs; 170 SizeT nowPos = 0; 171 Byte previousByte = 0; 172 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; 173 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; 174 int lc = vs->Properties.lc; 175 176 #ifdef _LZMA_OUT_READ 177 178 UInt32 Range = vs->Range; 179 UInt32 Code = vs->Code; 180 #ifdef _LZMA_IN_CB 181 const Byte *Buffer = vs->Buffer; 182 const Byte *BufferLim = vs->BufferLim; 183 #else 184 const Byte *Buffer = inStream; 185 const Byte *BufferLim = inStream + inSize; 186 #endif 187 int state = vs->State; 188 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3]; 189 int len = vs->RemainLen; 190 UInt32 globalPos = vs->GlobalPos; 191 UInt32 distanceLimit = vs->DistanceLimit; 192 193 Byte *dictionary = vs->Dictionary; 194 UInt32 dictionarySize = vs->Properties.DictionarySize; 195 UInt32 dictionaryPos = vs->DictionaryPos; 196 197 Byte tempDictionary[4]; 198 199 #ifndef _LZMA_IN_CB 200 *inSizeProcessed = 0; 201 #endif 202 *outSizeProcessed = 0; 203 if (len == kLzmaStreamWasFinishedId) 204 return LZMA_RESULT_OK; 205 206 if (dictionarySize == 0) 207 { 208 dictionary = tempDictionary; 209 dictionarySize = 1; 210 tempDictionary[0] = vs->TempDictionary[0]; 211 } 212 213 if (len == kLzmaNeedInitId) 214 { 215 { 216 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); 217 UInt32 i; 218 for (i = 0; i < numProbs; i++) 219 p[i] = kBitModelTotal >> 1; 220 rep0 = rep1 = rep2 = rep3 = 1; 221 state = 0; 222 globalPos = 0; 223 distanceLimit = 0; 224 dictionaryPos = 0; 225 dictionary[dictionarySize - 1] = 0; 226 #ifdef _LZMA_IN_CB 227 RC_INIT; 228 #else 229 RC_INIT(inStream, inSize); 230 #endif 231 } 232 len = 0; 233 } 234 while(len != 0 && nowPos < outSize) 235 { 236 UInt32 pos = dictionaryPos - rep0; 237 if (pos >= dictionarySize) 238 pos += dictionarySize; 239 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos]; 240 if (++dictionaryPos == dictionarySize) 241 dictionaryPos = 0; 242 len--; 243 } 244 if (dictionaryPos == 0) 245 previousByte = dictionary[dictionarySize - 1]; 246 else 247 previousByte = dictionary[dictionaryPos - 1]; 248 249 #else /* if !_LZMA_OUT_READ */ 250 251 int state = 0; 252 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; 253 int len = 0; 254 const Byte *Buffer; 255 const Byte *BufferLim; 256 UInt32 Range; 257 UInt32 Code; 258 259 #ifndef _LZMA_IN_CB 260 *inSizeProcessed = 0; 261 #endif 262 *outSizeProcessed = 0; 263 264 { 265 UInt32 i; 266 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp)); 267 for (i = 0; i < numProbs; i++) 268 p[i] = kBitModelTotal >> 1; 269 } 270 271 #ifdef _LZMA_IN_CB 272 RC_INIT; 273 #else 274 RC_INIT(inStream, inSize); 275 #endif 276 277 #endif /* _LZMA_OUT_READ */ 278 279 while(nowPos < outSize) 280 { 281 CProb *prob; 282 UInt32 bound; 283 int posState = (int)( 284 (nowPos 285 #ifdef _LZMA_OUT_READ 286 + globalPos 287 #endif 288 ) 289 & posStateMask); 290 291 prob = p + IsMatch + (state << kNumPosBitsMax) + posState; 292 IfBit0(prob) 293 { 294 int symbol = 1; 295 UpdateBit0(prob) 296 prob = p + Literal + (LZMA_LIT_SIZE * 297 ((( 298 (nowPos 299 #ifdef _LZMA_OUT_READ 300 + globalPos 301 #endif 302 ) 303 & literalPosMask) << lc) + (previousByte >> (8 - lc)))); 304 305 if (state >= kNumLitStates) 306 { 307 int matchByte; 308 #ifdef _LZMA_OUT_READ 309 UInt32 pos = dictionaryPos - rep0; 310 if (pos >= dictionarySize) 311 pos += dictionarySize; 312 matchByte = dictionary[pos]; 313 #else 314 matchByte = outStream[nowPos - rep0]; 315 #endif 316 do 317 { 318 int bit; 319 CProb *probLit; 320 matchByte <<= 1; 321 bit = (matchByte & 0x100); 322 probLit = prob + 0x100 + bit + symbol; 323 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break) 324 } 325 while (symbol < 0x100); 326 } 327 while (symbol < 0x100) 328 { 329 CProb *probLit = prob + symbol; 330 RC_GET_BIT(probLit, symbol) 331 } 332 previousByte = (Byte)symbol; 333 334 outStream[nowPos++] = previousByte; 335 #ifdef _LZMA_OUT_READ 336 if (distanceLimit < dictionarySize) 337 distanceLimit++; 338 339 dictionary[dictionaryPos] = previousByte; 340 if (++dictionaryPos == dictionarySize) 341 dictionaryPos = 0; 342 #endif 343 if (state < 4) state = 0; 344 else if (state < 10) state -= 3; 345 else state -= 6; 346 } 347 else 348 { 349 UpdateBit1(prob); 350 prob = p + IsRep + state; 351 IfBit0(prob) 352 { 353 UpdateBit0(prob); 354 rep3 = rep2; 355 rep2 = rep1; 356 rep1 = rep0; 357 state = state < kNumLitStates ? 0 : 3; 358 prob = p + LenCoder; 359 } 360 else 361 { 362 UpdateBit1(prob); 363 prob = p + IsRepG0 + state; 364 IfBit0(prob) 365 { 366 UpdateBit0(prob); 367 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; 368 IfBit0(prob) 369 { 370 #ifdef _LZMA_OUT_READ 371 UInt32 pos; 372 #endif 373 UpdateBit0(prob); 374 375 #ifdef _LZMA_OUT_READ 376 if (distanceLimit == 0) 377 #else 378 if (nowPos == 0) 379 #endif 380 return LZMA_RESULT_DATA_ERROR; 381 382 state = state < kNumLitStates ? 9 : 11; 383 #ifdef _LZMA_OUT_READ 384 pos = dictionaryPos - rep0; 385 if (pos >= dictionarySize) 386 pos += dictionarySize; 387 previousByte = dictionary[pos]; 388 dictionary[dictionaryPos] = previousByte; 389 if (++dictionaryPos == dictionarySize) 390 dictionaryPos = 0; 391 #else 392 previousByte = outStream[nowPos - rep0]; 393 #endif 394 outStream[nowPos++] = previousByte; 395 #ifdef _LZMA_OUT_READ 396 if (distanceLimit < dictionarySize) 397 distanceLimit++; 398 #endif 399 400 continue; 401 } 402 else 403 { 404 UpdateBit1(prob); 405 } 406 } 407 else 408 { 409 UInt32 distance; 410 UpdateBit1(prob); 411 prob = p + IsRepG1 + state; 412 IfBit0(prob) 413 { 414 UpdateBit0(prob); 415 distance = rep1; 416 } 417 else 418 { 419 UpdateBit1(prob); 420 prob = p + IsRepG2 + state; 421 IfBit0(prob) 422 { 423 UpdateBit0(prob); 424 distance = rep2; 425 } 426 else 427 { 428 UpdateBit1(prob); 429 distance = rep3; 430 rep3 = rep2; 431 } 432 rep2 = rep1; 433 } 434 rep1 = rep0; 435 rep0 = distance; 436 } 437 state = state < kNumLitStates ? 8 : 11; 438 prob = p + RepLenCoder; 439 } 440 { 441 int numBits, offset; 442 CProb *probLen = prob + LenChoice; 443 IfBit0(probLen) 444 { 445 UpdateBit0(probLen); 446 probLen = prob + LenLow + (posState << kLenNumLowBits); 447 offset = 0; 448 numBits = kLenNumLowBits; 449 } 450 else 451 { 452 UpdateBit1(probLen); 453 probLen = prob + LenChoice2; 454 IfBit0(probLen) 455 { 456 UpdateBit0(probLen); 457 probLen = prob + LenMid + (posState << kLenNumMidBits); 458 offset = kLenNumLowSymbols; 459 numBits = kLenNumMidBits; 460 } 461 else 462 { 463 UpdateBit1(probLen); 464 probLen = prob + LenHigh; 465 offset = kLenNumLowSymbols + kLenNumMidSymbols; 466 numBits = kLenNumHighBits; 467 } 468 } 469 RangeDecoderBitTreeDecode(probLen, numBits, len); 470 len += offset; 471 } 472 473 if (state < 4) 474 { 475 int posSlot; 476 state += kNumLitStates; 477 prob = p + PosSlot + 478 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << 479 kNumPosSlotBits); 480 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); 481 if (posSlot >= kStartPosModelIndex) 482 { 483 int numDirectBits = ((posSlot >> 1) - 1); 484 rep0 = (2 | ((UInt32)posSlot & 1)); 485 if (posSlot < kEndPosModelIndex) 486 { 487 rep0 <<= numDirectBits; 488 prob = p + SpecPos + rep0 - posSlot - 1; 489 } 490 else 491 { 492 numDirectBits -= kNumAlignBits; 493 do 494 { 495 RC_NORMALIZE 496 Range >>= 1; 497 rep0 <<= 1; 498 if (Code >= Range) 499 { 500 Code -= Range; 501 rep0 |= 1; 502 } 503 } 504 while (--numDirectBits != 0); 505 prob = p + Align; 506 rep0 <<= kNumAlignBits; 507 numDirectBits = kNumAlignBits; 508 } 509 { 510 int i = 1; 511 int mi = 1; 512 do 513 { 514 CProb *prob3 = prob + mi; 515 RC_GET_BIT2(prob3, mi, ; , rep0 |= i); 516 i <<= 1; 517 } 518 while(--numDirectBits != 0); 519 } 520 } 521 else 522 rep0 = posSlot; 523 if (++rep0 == (UInt32)(0)) 524 { 525 /* it's for stream version */ 526 len = kLzmaStreamWasFinishedId; 527 break; 528 } 529 } 530 531 len += kMatchMinLen; 532 #ifdef _LZMA_OUT_READ 533 if (rep0 > distanceLimit) 534 #else 535 if (rep0 > nowPos) 536 #endif 537 return LZMA_RESULT_DATA_ERROR; 538 539 #ifdef _LZMA_OUT_READ 540 if (dictionarySize - distanceLimit > (UInt32)len) 541 distanceLimit += len; 542 else 543 distanceLimit = dictionarySize; 544 #endif 545 546 do 547 { 548 #ifdef _LZMA_OUT_READ 549 UInt32 pos = dictionaryPos - rep0; 550 if (pos >= dictionarySize) 551 pos += dictionarySize; 552 previousByte = dictionary[pos]; 553 dictionary[dictionaryPos] = previousByte; 554 if (++dictionaryPos == dictionarySize) 555 dictionaryPos = 0; 556 #else 557 previousByte = outStream[nowPos - rep0]; 558 #endif 559 len--; 560 outStream[nowPos++] = previousByte; 561 } 562 while(len != 0 && nowPos < outSize); 563 } 564 } 565 RC_NORMALIZE; 566 567 #ifdef _LZMA_OUT_READ 568 vs->Range = Range; 569 vs->Code = Code; 570 vs->DictionaryPos = dictionaryPos; 571 vs->GlobalPos = globalPos + (UInt32)nowPos; 572 vs->DistanceLimit = distanceLimit; 573 vs->Reps[0] = rep0; 574 vs->Reps[1] = rep1; 575 vs->Reps[2] = rep2; 576 vs->Reps[3] = rep3; 577 vs->State = state; 578 vs->RemainLen = len; 579 vs->TempDictionary[0] = tempDictionary[0]; 580 #endif 581 582 #ifdef _LZMA_IN_CB 583 vs->Buffer = Buffer; 584 vs->BufferLim = BufferLim; 585 #else 586 *inSizeProcessed = (SizeT)(Buffer - inStream); 587 #endif 588 *outSizeProcessed = nowPos; 589 return LZMA_RESULT_OK; 590} 591