3 LZMA Decoder (optimized for Speed version)
5 LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
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.
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.
25 #include "LzmaDecode.h"
27 #define kNumTopBits 24
28 #define kTopValue ((UInt32)1 << kNumTopBits)
30 #define kNumBitModelTotalBits 11
31 #define kBitModelTotal (1 << kNumBitModelTotalBits)
32 #define kNumMoveBits 5
34 #define RC_READ_BYTE (*Buffer++)
36 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
37 { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
41 #define RC_TEST { if (Buffer == BufferLim) \
42 { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
43 BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
45 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
49 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
51 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
55 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
57 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
58 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
59 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
61 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
62 { UpdateBit0(p); mi <<= 1; A0; } else \
63 { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
65 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
67 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
68 { int i = numLevels; res = 1; \
69 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
70 res -= (1 << numLevels); }
73 #define kNumPosBitsMax 4
74 #define kNumPosStatesMax (1 << kNumPosBitsMax)
76 #define kLenNumLowBits 3
77 #define kLenNumLowSymbols (1 << kLenNumLowBits)
78 #define kLenNumMidBits 3
79 #define kLenNumMidSymbols (1 << kLenNumMidBits)
80 #define kLenNumHighBits 8
81 #define kLenNumHighSymbols (1 << kLenNumHighBits)
84 #define LenChoice2 (LenChoice + 1)
85 #define LenLow (LenChoice2 + 1)
86 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
87 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
88 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
92 #define kNumLitStates 7
94 #define kStartPosModelIndex 4
95 #define kEndPosModelIndex 14
96 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
98 #define kNumPosSlotBits 6
99 #define kNumLenToPosStates 4
101 #define kNumAlignBits 4
102 #define kAlignTableSize (1 << kNumAlignBits)
104 #define kMatchMinLen 2
107 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
108 #define IsRepG0 (IsRep + kNumStates)
109 #define IsRepG1 (IsRepG0 + kNumStates)
110 #define IsRepG2 (IsRepG1 + kNumStates)
111 #define IsRep0Long (IsRepG2 + kNumStates)
112 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
113 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
114 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
115 #define LenCoder (Align + kAlignTableSize)
116 #define RepLenCoder (LenCoder + kNumLenProbs)
117 #define Literal (RepLenCoder + kNumLenProbs)
119 #if Literal != LZMA_BASE_SIZE
123 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
126 if (size < LZMA_PROPERTIES_SIZE)
127 return LZMA_RESULT_DATA_ERROR;
128 prop0 = propsData[0];
129 if (prop0 >= (9 * 5 * 5))
130 return LZMA_RESULT_DATA_ERROR;
132 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
133 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
134 propsRes->lc = prop0;
136 unsigned char remainder = (unsigned char)(prop0 / 9);
137 propsRes->lc = prop0 % 9;
138 propsRes->pb = remainder / 5;
139 propsRes->lp = remainder % 5;
143 #ifdef _LZMA_OUT_READ
146 propsRes->DictionarySize = 0;
147 for (i = 0; i < 4; i++)
148 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
149 if (propsRes->DictionarySize == 0)
150 propsRes->DictionarySize = 1;
153 return LZMA_RESULT_OK;
156 #define kLzmaStreamWasFinishedId (-1)
158 int LzmaDecode(CLzmaDecoderState *vs,
160 ILzmaInCallback *InCallback,
162 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
164 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
166 CProb *p = vs->Probs;
168 Byte previousByte = 0;
169 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
170 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
171 int lc = vs->Properties.lc;
173 #ifdef _LZMA_OUT_READ
175 UInt32 Range = vs->Range;
176 UInt32 Code = vs->Code;
178 const Byte *Buffer = vs->Buffer;
179 const Byte *BufferLim = vs->BufferLim;
181 const Byte *Buffer = inStream;
182 const Byte *BufferLim = inStream + inSize;
184 int state = vs->State;
185 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
186 int len = vs->RemainLen;
187 UInt32 globalPos = vs->GlobalPos;
188 UInt32 distanceLimit = vs->DistanceLimit;
190 Byte *dictionary = vs->Dictionary;
191 UInt32 dictionarySize = vs->Properties.DictionarySize;
192 UInt32 dictionaryPos = vs->DictionaryPos;
194 Byte tempDictionary[4];
197 *inSizeProcessed = 0;
199 *outSizeProcessed = 0;
200 if (len == kLzmaStreamWasFinishedId)
201 return LZMA_RESULT_OK;
203 if (dictionarySize == 0)
205 dictionary = tempDictionary;
207 tempDictionary[0] = vs->TempDictionary[0];
210 if (len == kLzmaNeedInitId)
213 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
215 for (i = 0; i < numProbs; i++)
216 p[i] = kBitModelTotal >> 1;
217 rep0 = rep1 = rep2 = rep3 = 1;
222 dictionary[dictionarySize - 1] = 0;
226 RC_INIT(inStream, inSize);
231 while(len != 0 && nowPos < outSize)
233 UInt32 pos = dictionaryPos - rep0;
234 if (pos >= dictionarySize)
235 pos += dictionarySize;
236 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
237 if (++dictionaryPos == dictionarySize)
241 if (dictionaryPos == 0)
242 previousByte = dictionary[dictionarySize - 1];
244 previousByte = dictionary[dictionaryPos - 1];
246 #else /* if !_LZMA_OUT_READ */
249 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
252 const Byte *BufferLim;
257 *inSizeProcessed = 0;
259 *outSizeProcessed = 0;
263 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
264 for (i = 0; i < numProbs; i++)
265 p[i] = kBitModelTotal >> 1;
271 RC_INIT(inStream, inSize);
274 #endif /* _LZMA_OUT_READ */
276 while(nowPos < outSize)
280 int posState = (int)(
282 #ifdef _LZMA_OUT_READ
288 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
293 prob = p + Literal + (LZMA_LIT_SIZE *
296 #ifdef _LZMA_OUT_READ
300 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
302 if (state >= kNumLitStates)
305 #ifdef _LZMA_OUT_READ
306 UInt32 pos = dictionaryPos - rep0;
307 if (pos >= dictionarySize)
308 pos += dictionarySize;
309 matchByte = dictionary[pos];
311 matchByte = outStream[nowPos - rep0];
318 bit = (matchByte & 0x100);
319 probLit = prob + 0x100 + bit + symbol;
320 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
322 while (symbol < 0x100);
324 while (symbol < 0x100)
326 CProb *probLit = prob + symbol;
327 RC_GET_BIT(probLit, symbol)
329 previousByte = (Byte)symbol;
331 outStream[nowPos++] = previousByte;
332 #ifdef _LZMA_OUT_READ
333 if (distanceLimit < dictionarySize)
336 dictionary[dictionaryPos] = previousByte;
337 if (++dictionaryPos == dictionarySize)
340 if (state < 4) state = 0;
341 else if (state < 10) state -= 3;
347 prob = p + IsRep + state;
354 state = state < kNumLitStates ? 0 : 3;
360 prob = p + IsRepG0 + state;
364 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
367 #ifdef _LZMA_OUT_READ
372 #ifdef _LZMA_OUT_READ
373 if (distanceLimit == 0)
378 printf("distanceLimit == 0\n");
379 return LZMA_RESULT_DATA_ERROR;
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)
392 previousByte = outStream[nowPos - rep0];
394 outStream[nowPos++] = previousByte;
395 #ifdef _LZMA_OUT_READ
396 if (distanceLimit < dictionarySize)
411 prob = p + IsRepG1 + state;
420 prob = p + IsRepG2 + state;
437 state = state < kNumLitStates ? 8 : 11;
438 prob = p + RepLenCoder;
442 CProb *probLen = prob + LenChoice;
446 probLen = prob + LenLow + (posState << kLenNumLowBits);
448 numBits = kLenNumLowBits;
453 probLen = prob + LenChoice2;
457 probLen = prob + LenMid + (posState << kLenNumMidBits);
458 offset = kLenNumLowSymbols;
459 numBits = kLenNumMidBits;
464 probLen = prob + LenHigh;
465 offset = kLenNumLowSymbols + kLenNumMidSymbols;
466 numBits = kLenNumHighBits;
469 RangeDecoderBitTreeDecode(probLen, numBits, len);
476 state += kNumLitStates;
478 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
480 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
481 if (posSlot >= kStartPosModelIndex)
483 int numDirectBits = ((posSlot >> 1) - 1);
484 rep0 = (2 | ((UInt32)posSlot & 1));
485 if (posSlot < kEndPosModelIndex)
487 rep0 <<= numDirectBits;
488 prob = p + SpecPos + rep0 - posSlot - 1;
492 numDirectBits -= kNumAlignBits;
504 while (--numDirectBits != 0);
506 rep0 <<= kNumAlignBits;
507 numDirectBits = kNumAlignBits;
514 CProb *prob3 = prob + mi;
515 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
518 while(--numDirectBits != 0);
523 if (++rep0 == (UInt32)(0))
525 /* it's for stream version */
526 len = kLzmaStreamWasFinishedId;
532 #ifdef _LZMA_OUT_READ
533 if (rep0 > distanceLimit)
538 printf("rep0 %d > distanceLimit %d\n", rep0, distanceLimit);
539 return LZMA_RESULT_DATA_ERROR;
542 #ifdef _LZMA_OUT_READ
543 if (dictionarySize - distanceLimit > (UInt32)len)
544 distanceLimit += len;
546 distanceLimit = dictionarySize;
551 #ifdef _LZMA_OUT_READ
552 UInt32 pos = dictionaryPos - rep0;
553 if (pos >= dictionarySize)
554 pos += dictionarySize;
555 previousByte = dictionary[pos];
556 dictionary[dictionaryPos] = previousByte;
557 if (++dictionaryPos == dictionarySize)
560 previousByte = outStream[nowPos - rep0];
563 outStream[nowPos++] = previousByte;
565 while(len != 0 && nowPos < outSize);
570 #ifdef _LZMA_OUT_READ
573 vs->DictionaryPos = dictionaryPos;
574 vs->GlobalPos = globalPos + (UInt32)nowPos;
575 vs->DistanceLimit = distanceLimit;
582 vs->TempDictionary[0] = tempDictionary[0];
587 vs->BufferLim = BufferLim;
589 *inSizeProcessed = (SizeT)(Buffer - inStream);
591 *outSizeProcessed = nowPos;
592 return LZMA_RESULT_OK;