3 LZMA Decoder (optimized for Speed version)
5 LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
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.
22 #include "LzmaDecode.h"
25 #define Byte unsigned char
28 #define kNumTopBits 24
29 #define kTopValue ((UInt32)1 << kNumTopBits)
31 #define kNumBitModelTotalBits 11
32 #define kBitModelTotal (1 << kNumBitModelTotalBits)
33 #define kNumMoveBits 5
35 #define RC_READ_BYTE (*Buffer++)
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; }}
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; }}
46 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
50 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
52 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
56 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
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;
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; }
66 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
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); }
74 #define kNumPosBitsMax 4
75 #define kNumPosStatesMax (1 << kNumPosBitsMax)
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)
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)
93 #define kNumLitStates 7
95 #define kStartPosModelIndex 4
96 #define kEndPosModelIndex 14
97 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
99 #define kNumPosSlotBits 6
100 #define kNumLenToPosStates 4
102 #define kNumAlignBits 4
103 #define kAlignTableSize (1 << kNumAlignBits)
105 #define kMatchMinLen 2
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)
120 #if Literal != LZMA_BASE_SIZE
124 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
127 if (size < LZMA_PROPERTIES_SIZE)
128 return LZMA_RESULT_DATA_ERROR;
129 prop0 = propsData[0];
130 if (prop0 >= (9 * 5 * 5))
131 return LZMA_RESULT_DATA_ERROR;
133 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
134 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
135 propsRes->lc = prop0;
137 unsigned char remainder = (unsigned char)(prop0 / 9);
138 propsRes->lc = prop0 % 9;
139 propsRes->pb = remainder / 5;
140 propsRes->lp = remainder % 5;
144 #ifdef _LZMA_OUT_READ
147 propsRes->DictionarySize = 0;
148 for (i = 0; i < 4; i++)
149 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
150 if (propsRes->DictionarySize == 0)
151 propsRes->DictionarySize = 1;
154 return LZMA_RESULT_OK;
157 #define kLzmaStreamWasFinishedId (-1)
159 int LzmaDecode(CLzmaDecoderState *vs,
161 ILzmaInCallback *InCallback,
163 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
165 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
167 CProb *p = vs->Probs;
169 Byte previousByte = 0;
170 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
171 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
172 int lc = vs->Properties.lc;
174 #ifdef _LZMA_OUT_READ
176 UInt32 Range = vs->Range;
177 UInt32 Code = vs->Code;
179 const Byte *Buffer = vs->Buffer;
180 const Byte *BufferLim = vs->BufferLim;
182 const Byte *Buffer = inStream;
183 const Byte *BufferLim = inStream + inSize;
185 int state = vs->State;
186 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
187 int len = vs->RemainLen;
188 UInt32 globalPos = vs->GlobalPos;
189 UInt32 distanceLimit = vs->DistanceLimit;
191 Byte *dictionary = vs->Dictionary;
192 UInt32 dictionarySize = vs->Properties.DictionarySize;
193 UInt32 dictionaryPos = vs->DictionaryPos;
195 Byte tempDictionary[4];
198 *inSizeProcessed = 0;
200 *outSizeProcessed = 0;
201 if (len == kLzmaStreamWasFinishedId)
202 return LZMA_RESULT_OK;
204 if (dictionarySize == 0)
206 dictionary = tempDictionary;
208 tempDictionary[0] = vs->TempDictionary[0];
211 if (len == kLzmaNeedInitId)
214 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
216 for (i = 0; i < numProbs; i++)
217 p[i] = kBitModelTotal >> 1;
218 rep0 = rep1 = rep2 = rep3 = 1;
223 dictionary[dictionarySize - 1] = 0;
227 RC_INIT(inStream, inSize);
232 while(len != 0 && nowPos < outSize)
234 UInt32 pos = dictionaryPos - rep0;
235 if (pos >= dictionarySize)
236 pos += dictionarySize;
237 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
238 if (++dictionaryPos == dictionarySize)
242 if (dictionaryPos == 0)
243 previousByte = dictionary[dictionarySize - 1];
245 previousByte = dictionary[dictionaryPos - 1];
247 #else /* if !_LZMA_OUT_READ */
250 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
253 const Byte *BufferLim;
258 *inSizeProcessed = 0;
260 *outSizeProcessed = 0;
264 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
265 for (i = 0; i < numProbs; i++)
266 p[i] = kBitModelTotal >> 1;
272 RC_INIT(inStream, inSize);
275 #endif /* _LZMA_OUT_READ */
277 while(nowPos < outSize)
281 int posState = (int)(
283 #ifdef _LZMA_OUT_READ
289 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
294 prob = p + Literal + (LZMA_LIT_SIZE *
297 #ifdef _LZMA_OUT_READ
301 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
303 if (state >= kNumLitStates)
306 #ifdef _LZMA_OUT_READ
307 UInt32 pos = dictionaryPos - rep0;
308 if (pos >= dictionarySize)
309 pos += dictionarySize;
310 matchByte = dictionary[pos];
312 matchByte = outStream[nowPos - rep0];
319 bit = (matchByte & 0x100);
320 probLit = prob + 0x100 + bit + symbol;
321 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
323 while (symbol < 0x100);
325 while (symbol < 0x100)
327 CProb *probLit = prob + symbol;
328 RC_GET_BIT(probLit, symbol)
330 previousByte = (Byte)symbol;
332 outStream[nowPos++] = previousByte;
333 #ifdef _LZMA_OUT_READ
334 if (distanceLimit < dictionarySize)
337 dictionary[dictionaryPos] = previousByte;
338 if (++dictionaryPos == dictionarySize)
341 if (state < 4) state = 0;
342 else if (state < 10) state -= 3;
348 prob = p + IsRep + state;
355 state = state < kNumLitStates ? 0 : 3;
361 prob = p + IsRepG0 + state;
365 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
368 #ifdef _LZMA_OUT_READ
373 #ifdef _LZMA_OUT_READ
374 if (distanceLimit == 0)
378 return LZMA_RESULT_DATA_ERROR;
380 state = state < kNumLitStates ? 9 : 11;
381 #ifdef _LZMA_OUT_READ
382 pos = dictionaryPos - rep0;
383 if (pos >= dictionarySize)
384 pos += dictionarySize;
385 previousByte = dictionary[pos];
386 dictionary[dictionaryPos] = previousByte;
387 if (++dictionaryPos == dictionarySize)
390 previousByte = outStream[nowPos - rep0];
392 outStream[nowPos++] = previousByte;
393 #ifdef _LZMA_OUT_READ
394 if (distanceLimit < dictionarySize)
409 prob = p + IsRepG1 + state;
418 prob = p + IsRepG2 + state;
435 state = state < kNumLitStates ? 8 : 11;
436 prob = p + RepLenCoder;
440 CProb *probLen = prob + LenChoice;
444 probLen = prob + LenLow + (posState << kLenNumLowBits);
446 numBits = kLenNumLowBits;
451 probLen = prob + LenChoice2;
455 probLen = prob + LenMid + (posState << kLenNumMidBits);
456 offset = kLenNumLowSymbols;
457 numBits = kLenNumMidBits;
462 probLen = prob + LenHigh;
463 offset = kLenNumLowSymbols + kLenNumMidSymbols;
464 numBits = kLenNumHighBits;
467 RangeDecoderBitTreeDecode(probLen, numBits, len);
474 state += kNumLitStates;
476 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
478 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
479 if (posSlot >= kStartPosModelIndex)
481 int numDirectBits = ((posSlot >> 1) - 1);
482 rep0 = (2 | ((UInt32)posSlot & 1));
483 if (posSlot < kEndPosModelIndex)
485 rep0 <<= numDirectBits;
486 prob = p + SpecPos + rep0 - posSlot - 1;
490 numDirectBits -= kNumAlignBits;
502 while (--numDirectBits != 0);
504 rep0 <<= kNumAlignBits;
505 numDirectBits = kNumAlignBits;
512 CProb *prob3 = prob + mi;
513 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
516 while(--numDirectBits != 0);
521 if (++rep0 == (UInt32)(0))
523 /* it's for stream version */
524 len = kLzmaStreamWasFinishedId;
530 #ifdef _LZMA_OUT_READ
531 if (rep0 > distanceLimit)
535 return LZMA_RESULT_DATA_ERROR;
537 #ifdef _LZMA_OUT_READ
538 if (dictionarySize - distanceLimit > (UInt32)len)
539 distanceLimit += len;
541 distanceLimit = dictionarySize;
546 #ifdef _LZMA_OUT_READ
547 UInt32 pos = dictionaryPos - rep0;
548 if (pos >= dictionarySize)
549 pos += dictionarySize;
550 previousByte = dictionary[pos];
551 dictionary[dictionaryPos] = previousByte;
552 if (++dictionaryPos == dictionarySize)
555 previousByte = outStream[nowPos - rep0];
558 outStream[nowPos++] = previousByte;
560 while(len != 0 && nowPos < outSize);
565 #ifdef _LZMA_OUT_READ
568 vs->DictionaryPos = dictionaryPos;
569 vs->GlobalPos = globalPos + (UInt32)nowPos;
570 vs->DistanceLimit = distanceLimit;
577 vs->TempDictionary[0] = tempDictionary[0];
582 vs->BufferLim = BufferLim;
584 *inSizeProcessed = (SizeT)(Buffer - inStream);
586 *outSizeProcessed = nowPos;
587 return LZMA_RESULT_OK;