00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "LzmaDecode.h"
00023
00024 #ifndef Byte
00025 #define Byte unsigned char
00026 #endif
00027
00028 #define kNumTopBits 24
00029 #define kTopValue ((UInt32)1 << kNumTopBits)
00030
00031 #define kNumBitModelTotalBits 11
00032 #define kBitModelTotal (1 << kNumBitModelTotalBits)
00033 #define kNumMoveBits 5
00034
00035 #define RC_READ_BYTE (*Buffer++)
00036
00037 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
00038 { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
00039
00040 #ifdef _LZMA_IN_CB
00041
00042 #define RC_TEST { if (Buffer == BufferLim) \
00043 { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
00044 BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
00045
00046 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
00047
00048 #else
00049
00050 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
00051
00052 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
00053
00054 #endif
00055
00056 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
00057
00058 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
00059 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
00060 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
00061
00062 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
00063 { UpdateBit0(p); mi <<= 1; A0; } else \
00064 { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
00065
00066 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
00067
00068 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
00069 { int i = numLevels; res = 1; \
00070 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
00071 res -= (1 << numLevels); }
00072
00073
00074 #define kNumPosBitsMax 4
00075 #define kNumPosStatesMax (1 << kNumPosBitsMax)
00076
00077 #define kLenNumLowBits 3
00078 #define kLenNumLowSymbols (1 << kLenNumLowBits)
00079 #define kLenNumMidBits 3
00080 #define kLenNumMidSymbols (1 << kLenNumMidBits)
00081 #define kLenNumHighBits 8
00082 #define kLenNumHighSymbols (1 << kLenNumHighBits)
00083
00084 #define LenChoice 0
00085 #define LenChoice2 (LenChoice + 1)
00086 #define LenLow (LenChoice2 + 1)
00087 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
00088 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
00089 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
00090
00091
00092 #define kNumStates 12
00093 #define kNumLitStates 7
00094
00095 #define kStartPosModelIndex 4
00096 #define kEndPosModelIndex 14
00097 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
00098
00099 #define kNumPosSlotBits 6
00100 #define kNumLenToPosStates 4
00101
00102 #define kNumAlignBits 4
00103 #define kAlignTableSize (1 << kNumAlignBits)
00104
00105 #define kMatchMinLen 2
00106
00107 #define IsMatch 0
00108 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
00109 #define IsRepG0 (IsRep + kNumStates)
00110 #define IsRepG1 (IsRepG0 + kNumStates)
00111 #define IsRepG2 (IsRepG1 + kNumStates)
00112 #define IsRep0Long (IsRepG2 + kNumStates)
00113 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
00114 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
00115 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
00116 #define LenCoder (Align + kAlignTableSize)
00117 #define RepLenCoder (LenCoder + kNumLenProbs)
00118 #define Literal (RepLenCoder + kNumLenProbs)
00119
00120 #if Literal != LZMA_BASE_SIZE
00121 StopCompilingDueBUG
00122 #endif
00123
00124 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
00125 {
00126 unsigned char prop0;
00127 if (size < LZMA_PROPERTIES_SIZE)
00128 return LZMA_RESULT_DATA_ERROR;
00129 prop0 = propsData[0];
00130 if (prop0 >= (9 * 5 * 5))
00131 return LZMA_RESULT_DATA_ERROR;
00132 {
00133 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
00134 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
00135 propsRes->lc = prop0;
00136
00137
00138
00139
00140
00141
00142 }
00143
00144 #ifdef _LZMA_OUT_READ
00145 {
00146 int i;
00147 propsRes->DictionarySize = 0;
00148 for (i = 0; i < 4; i++)
00149 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
00150 if (propsRes->DictionarySize == 0)
00151 propsRes->DictionarySize = 1;
00152 }
00153 #endif
00154 return LZMA_RESULT_OK;
00155 }
00156
00157 #define kLzmaStreamWasFinishedId (-1)
00158
00159 int LzmaDecode(CLzmaDecoderState *vs,
00160 #ifdef _LZMA_IN_CB
00161 ILzmaInCallback *InCallback,
00162 #else
00163 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
00164 #endif
00165 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
00166 {
00167 CProb *p = vs->Probs;
00168 SizeT nowPos = 0;
00169 Byte previousByte = 0;
00170 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
00171 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
00172 int lc = vs->Properties.lc;
00173
00174 #ifdef _LZMA_OUT_READ
00175
00176 UInt32 Range = vs->Range;
00177 UInt32 Code = vs->Code;
00178 #ifdef _LZMA_IN_CB
00179 const Byte *Buffer = vs->Buffer;
00180 const Byte *BufferLim = vs->BufferLim;
00181 #else
00182 const Byte *Buffer = inStream;
00183 const Byte *BufferLim = inStream + inSize;
00184 #endif
00185 int state = vs->State;
00186 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
00187 int len = vs->RemainLen;
00188 UInt32 globalPos = vs->GlobalPos;
00189 UInt32 distanceLimit = vs->DistanceLimit;
00190
00191 Byte *dictionary = vs->Dictionary;
00192 UInt32 dictionarySize = vs->Properties.DictionarySize;
00193 UInt32 dictionaryPos = vs->DictionaryPos;
00194
00195 Byte tempDictionary[4];
00196
00197 #ifndef _LZMA_IN_CB
00198 *inSizeProcessed = 0;
00199 #endif
00200 *outSizeProcessed = 0;
00201 if (len == kLzmaStreamWasFinishedId)
00202 return LZMA_RESULT_OK;
00203
00204 if (dictionarySize == 0)
00205 {
00206 dictionary = tempDictionary;
00207 dictionarySize = 1;
00208 tempDictionary[0] = vs->TempDictionary[0];
00209 }
00210
00211 if (len == kLzmaNeedInitId)
00212 {
00213 {
00214 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
00215 UInt32 i;
00216 for (i = 0; i < numProbs; i++)
00217 p[i] = kBitModelTotal >> 1;
00218 rep0 = rep1 = rep2 = rep3 = 1;
00219 state = 0;
00220 globalPos = 0;
00221 distanceLimit = 0;
00222 dictionaryPos = 0;
00223 dictionary[dictionarySize - 1] = 0;
00224 #ifdef _LZMA_IN_CB
00225 RC_INIT;
00226 #else
00227 RC_INIT(inStream, inSize);
00228 #endif
00229 }
00230 len = 0;
00231 }
00232 while(len != 0 && nowPos < outSize)
00233 {
00234 UInt32 pos = dictionaryPos - rep0;
00235 if (pos >= dictionarySize)
00236 pos += dictionarySize;
00237 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
00238 if (++dictionaryPos == dictionarySize)
00239 dictionaryPos = 0;
00240 len--;
00241 }
00242 if (dictionaryPos == 0)
00243 previousByte = dictionary[dictionarySize - 1];
00244 else
00245 previousByte = dictionary[dictionaryPos - 1];
00246
00247 #else
00248
00249 int state = 0;
00250 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
00251 int len = 0;
00252 const Byte *Buffer;
00253 const Byte *BufferLim;
00254 UInt32 Range;
00255 UInt32 Code;
00256
00257 #ifndef _LZMA_IN_CB
00258 *inSizeProcessed = 0;
00259 #endif
00260 *outSizeProcessed = 0;
00261
00262 {
00263 UInt32 i;
00264 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
00265 for (i = 0; i < numProbs; i++)
00266 p[i] = kBitModelTotal >> 1;
00267 }
00268
00269 #ifdef _LZMA_IN_CB
00270 RC_INIT;
00271 #else
00272 RC_INIT(inStream, inSize);
00273 #endif
00274
00275 #endif
00276
00277 while(nowPos < outSize)
00278 {
00279 CProb *prob;
00280 UInt32 bound;
00281 int posState = (int)(
00282 (nowPos
00283 #ifdef _LZMA_OUT_READ
00284 + globalPos
00285 #endif
00286 )
00287 & posStateMask);
00288
00289 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
00290 IfBit0(prob)
00291 {
00292 int symbol = 1;
00293 UpdateBit0(prob)
00294 prob = p + Literal + (LZMA_LIT_SIZE *
00295 (((
00296 (nowPos
00297 #ifdef _LZMA_OUT_READ
00298 + globalPos
00299 #endif
00300 )
00301 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
00302
00303 if (state >= kNumLitStates)
00304 {
00305 int matchByte;
00306 #ifdef _LZMA_OUT_READ
00307 UInt32 pos = dictionaryPos - rep0;
00308 if (pos >= dictionarySize)
00309 pos += dictionarySize;
00310 matchByte = dictionary[pos];
00311 #else
00312 matchByte = outStream[nowPos - rep0];
00313 #endif
00314 do
00315 {
00316 int bit;
00317 CProb *probLit;
00318 matchByte <<= 1;
00319 bit = (matchByte & 0x100);
00320 probLit = prob + 0x100 + bit + symbol;
00321 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
00322 }
00323 while (symbol < 0x100);
00324 }
00325 while (symbol < 0x100)
00326 {
00327 CProb *probLit = prob + symbol;
00328 RC_GET_BIT(probLit, symbol)
00329 }
00330 previousByte = (Byte)symbol;
00331
00332 outStream[nowPos++] = previousByte;
00333 #ifdef _LZMA_OUT_READ
00334 if (distanceLimit < dictionarySize)
00335 distanceLimit++;
00336
00337 dictionary[dictionaryPos] = previousByte;
00338 if (++dictionaryPos == dictionarySize)
00339 dictionaryPos = 0;
00340 #endif
00341 if (state < 4) state = 0;
00342 else if (state < 10) state -= 3;
00343 else state -= 6;
00344 }
00345 else
00346 {
00347 UpdateBit1(prob);
00348 prob = p + IsRep + state;
00349 IfBit0(prob)
00350 {
00351 UpdateBit0(prob);
00352 rep3 = rep2;
00353 rep2 = rep1;
00354 rep1 = rep0;
00355 state = state < kNumLitStates ? 0 : 3;
00356 prob = p + LenCoder;
00357 }
00358 else
00359 {
00360 UpdateBit1(prob);
00361 prob = p + IsRepG0 + state;
00362 IfBit0(prob)
00363 {
00364 UpdateBit0(prob);
00365 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
00366 IfBit0(prob)
00367 {
00368 #ifdef _LZMA_OUT_READ
00369 UInt32 pos;
00370 #endif
00371 UpdateBit0(prob);
00372
00373 #ifdef _LZMA_OUT_READ
00374 if (distanceLimit == 0)
00375 #else
00376 if (nowPos == 0)
00377 #endif
00378 return LZMA_RESULT_DATA_ERROR;
00379
00380 state = state < kNumLitStates ? 9 : 11;
00381 #ifdef _LZMA_OUT_READ
00382 pos = dictionaryPos - rep0;
00383 if (pos >= dictionarySize)
00384 pos += dictionarySize;
00385 previousByte = dictionary[pos];
00386 dictionary[dictionaryPos] = previousByte;
00387 if (++dictionaryPos == dictionarySize)
00388 dictionaryPos = 0;
00389 #else
00390 previousByte = outStream[nowPos - rep0];
00391 #endif
00392 outStream[nowPos++] = previousByte;
00393 #ifdef _LZMA_OUT_READ
00394 if (distanceLimit < dictionarySize)
00395 distanceLimit++;
00396 #endif
00397
00398 continue;
00399 }
00400 else
00401 {
00402 UpdateBit1(prob);
00403 }
00404 }
00405 else
00406 {
00407 UInt32 distance;
00408 UpdateBit1(prob);
00409 prob = p + IsRepG1 + state;
00410 IfBit0(prob)
00411 {
00412 UpdateBit0(prob);
00413 distance = rep1;
00414 }
00415 else
00416 {
00417 UpdateBit1(prob);
00418 prob = p + IsRepG2 + state;
00419 IfBit0(prob)
00420 {
00421 UpdateBit0(prob);
00422 distance = rep2;
00423 }
00424 else
00425 {
00426 UpdateBit1(prob);
00427 distance = rep3;
00428 rep3 = rep2;
00429 }
00430 rep2 = rep1;
00431 }
00432 rep1 = rep0;
00433 rep0 = distance;
00434 }
00435 state = state < kNumLitStates ? 8 : 11;
00436 prob = p + RepLenCoder;
00437 }
00438 {
00439 int numBits, offset;
00440 CProb *probLen = prob + LenChoice;
00441 IfBit0(probLen)
00442 {
00443 UpdateBit0(probLen);
00444 probLen = prob + LenLow + (posState << kLenNumLowBits);
00445 offset = 0;
00446 numBits = kLenNumLowBits;
00447 }
00448 else
00449 {
00450 UpdateBit1(probLen);
00451 probLen = prob + LenChoice2;
00452 IfBit0(probLen)
00453 {
00454 UpdateBit0(probLen);
00455 probLen = prob + LenMid + (posState << kLenNumMidBits);
00456 offset = kLenNumLowSymbols;
00457 numBits = kLenNumMidBits;
00458 }
00459 else
00460 {
00461 UpdateBit1(probLen);
00462 probLen = prob + LenHigh;
00463 offset = kLenNumLowSymbols + kLenNumMidSymbols;
00464 numBits = kLenNumHighBits;
00465 }
00466 }
00467 RangeDecoderBitTreeDecode(probLen, numBits, len);
00468 len += offset;
00469 }
00470
00471 if (state < 4)
00472 {
00473 int posSlot;
00474 state += kNumLitStates;
00475 prob = p + PosSlot +
00476 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
00477 kNumPosSlotBits);
00478 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
00479 if (posSlot >= kStartPosModelIndex)
00480 {
00481 int numDirectBits = ((posSlot >> 1) - 1);
00482 rep0 = (2 | ((UInt32)posSlot & 1));
00483 if (posSlot < kEndPosModelIndex)
00484 {
00485 rep0 <<= numDirectBits;
00486 prob = p + SpecPos + rep0 - posSlot - 1;
00487 }
00488 else
00489 {
00490 numDirectBits -= kNumAlignBits;
00491 do
00492 {
00493 RC_NORMALIZE
00494 Range >>= 1;
00495 rep0 <<= 1;
00496 if (Code >= Range)
00497 {
00498 Code -= Range;
00499 rep0 |= 1;
00500 }
00501 }
00502 while (--numDirectBits != 0);
00503 prob = p + Align;
00504 rep0 <<= kNumAlignBits;
00505 numDirectBits = kNumAlignBits;
00506 }
00507 {
00508 int i = 1;
00509 int mi = 1;
00510 do
00511 {
00512 CProb *prob3 = prob + mi;
00513 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
00514 i <<= 1;
00515 }
00516 while(--numDirectBits != 0);
00517 }
00518 }
00519 else
00520 rep0 = posSlot;
00521 if (++rep0 == (UInt32)(0))
00522 {
00523
00524 len = kLzmaStreamWasFinishedId;
00525 break;
00526 }
00527 }
00528
00529 len += kMatchMinLen;
00530 #ifdef _LZMA_OUT_READ
00531 if (rep0 > distanceLimit)
00532 #else
00533 if (rep0 > nowPos)
00534 #endif
00535 return LZMA_RESULT_DATA_ERROR;
00536
00537 #ifdef _LZMA_OUT_READ
00538 if (dictionarySize - distanceLimit > (UInt32)len)
00539 distanceLimit += len;
00540 else
00541 distanceLimit = dictionarySize;
00542 #endif
00543
00544 do
00545 {
00546 #ifdef _LZMA_OUT_READ
00547 UInt32 pos = dictionaryPos - rep0;
00548 if (pos >= dictionarySize)
00549 pos += dictionarySize;
00550 previousByte = dictionary[pos];
00551 dictionary[dictionaryPos] = previousByte;
00552 if (++dictionaryPos == dictionarySize)
00553 dictionaryPos = 0;
00554 #else
00555 previousByte = outStream[nowPos - rep0];
00556 #endif
00557 len--;
00558 outStream[nowPos++] = previousByte;
00559 }
00560 while(len != 0 && nowPos < outSize);
00561 }
00562 }
00563 RC_NORMALIZE;
00564
00565 #ifdef _LZMA_OUT_READ
00566 vs->Range = Range;
00567 vs->Code = Code;
00568 vs->DictionaryPos = dictionaryPos;
00569 vs->GlobalPos = globalPos + (UInt32)nowPos;
00570 vs->DistanceLimit = distanceLimit;
00571 vs->Reps[0] = rep0;
00572 vs->Reps[1] = rep1;
00573 vs->Reps[2] = rep2;
00574 vs->Reps[3] = rep3;
00575 vs->State = state;
00576 vs->RemainLen = len;
00577 vs->TempDictionary[0] = tempDictionary[0];
00578 #endif
00579
00580 #ifdef _LZMA_IN_CB
00581 vs->Buffer = Buffer;
00582 vs->BufferLim = BufferLim;
00583 #else
00584 *inSizeProcessed = (SizeT)(Buffer - inStream);
00585 #endif
00586 *outSizeProcessed = nowPos;
00587 return LZMA_RESULT_OK;
00588 }