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