3 LZMA Decoder (optimized for Speed version)
\r
5 LZMA SDK 4.22 Copyright (c) 1999-2005 Igor Pavlov (2005-06-10)
\r
6 http://www.7-zip.org/
\r
8 LZMA SDK is licensed under two licenses:
\r
9 1) GNU Lesser General Public License (GNU LGPL)
\r
10 2) Common Public License (CPL)
\r
11 It means that you can select one of these two licenses and
\r
12 follow rules of that license.
\r
15 Igor Pavlov, as the author of this Code, expressly permits you to
\r
16 statically or dynamically link your Code (or bind by name) to the
\r
17 interfaces of this file without subjecting your linked Code to the
\r
18 terms of the CPL or GNU LGPL. Any modifications or additions
\r
19 to this file, however, are subject to the LGPL or CPL terms.
\r
22 #include "LzmaDecode.h"
\r
25 #define Byte unsigned char
\r
28 #define kNumTopBits 24
\r
29 #define kTopValue ((UInt32)1 << kNumTopBits)
\r
31 #define kNumBitModelTotalBits 11
\r
32 #define kBitModelTotal (1 << kNumBitModelTotalBits)
\r
33 #define kNumMoveBits 5
\r
35 #define RC_READ_BYTE (*Buffer++)
\r
37 #define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \
\r
38 { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
\r
42 #define RC_TEST { if (Buffer == BufferLim) \
\r
43 { SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
\r
44 BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
\r
46 #define RC_INIT Buffer = BufferLim = 0; RC_INIT2
\r
50 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
\r
52 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
\r
56 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
\r
58 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
\r
59 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
\r
60 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
\r
62 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
\r
63 { UpdateBit0(p); mi <<= 1; A0; } else \
\r
64 { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
\r
66 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
\r
68 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
\r
69 { int i = numLevels; res = 1; \
\r
70 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
\r
71 res -= (1 << numLevels); }
\r
74 #define kNumPosBitsMax 4
\r
75 #define kNumPosStatesMax (1 << kNumPosBitsMax)
\r
77 #define kLenNumLowBits 3
\r
78 #define kLenNumLowSymbols (1 << kLenNumLowBits)
\r
79 #define kLenNumMidBits 3
\r
80 #define kLenNumMidSymbols (1 << kLenNumMidBits)
\r
81 #define kLenNumHighBits 8
\r
82 #define kLenNumHighSymbols (1 << kLenNumHighBits)
\r
85 #define LenChoice2 (LenChoice + 1)
\r
86 #define LenLow (LenChoice2 + 1)
\r
87 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
\r
88 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
\r
89 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
\r
92 #define kNumStates 12
\r
93 #define kNumLitStates 7
\r
95 #define kStartPosModelIndex 4
\r
96 #define kEndPosModelIndex 14
\r
97 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
\r
99 #define kNumPosSlotBits 6
\r
100 #define kNumLenToPosStates 4
\r
102 #define kNumAlignBits 4
\r
103 #define kAlignTableSize (1 << kNumAlignBits)
\r
105 #define kMatchMinLen 2
\r
108 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
\r
109 #define IsRepG0 (IsRep + kNumStates)
\r
110 #define IsRepG1 (IsRepG0 + kNumStates)
\r
111 #define IsRepG2 (IsRepG1 + kNumStates)
\r
112 #define IsRep0Long (IsRepG2 + kNumStates)
\r
113 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
\r
114 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
\r
115 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
\r
116 #define LenCoder (Align + kAlignTableSize)
\r
117 #define RepLenCoder (LenCoder + kNumLenProbs)
\r
118 #define Literal (RepLenCoder + kNumLenProbs)
\r
120 #if Literal != LZMA_BASE_SIZE
\r
121 StopCompilingDueBUG
\r
125 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
\r
127 unsigned char prop0;
\r
128 if (size < LZMA_PROPERTIES_SIZE)
\r
129 return LZMA_RESULT_DATA_ERROR;
\r
130 prop0 = propsData[0];
\r
131 if (prop0 >= (9 * 5 * 5))
\r
132 return LZMA_RESULT_DATA_ERROR;
\r
134 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
\r
135 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
\r
136 propsRes->lc = prop0;
\r
138 unsigned char remainder = (unsigned char)(prop0 / 9);
\r
139 propsRes->lc = prop0 % 9;
\r
140 propsRes->pb = remainder / 5;
\r
141 propsRes->lp = remainder % 5;
\r
145 #ifdef _LZMA_OUT_READ
\r
148 propsRes->DictionarySize = 0;
\r
149 for (i = 0; i < 4; i++)
\r
150 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
\r
151 if (propsRes->DictionarySize == 0)
\r
152 propsRes->DictionarySize = 1;
\r
155 return LZMA_RESULT_OK;
\r
159 #define kLzmaStreamWasFinishedId (-1)
\r
161 int LzmaDecode(CLzmaDecoderState *vs,
\r
163 ILzmaInCallback *InCallback,
\r
165 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
\r
167 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
\r
169 CProb *p = vs->Probs;
\r
171 Byte previousByte = 0;
\r
172 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
\r
173 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
\r
174 int lc = vs->Properties.lc;
\r
176 #ifdef _LZMA_OUT_READ
\r
178 UInt32 Range = vs->Range;
\r
179 UInt32 Code = vs->Code;
\r
181 const Byte *Buffer = vs->Buffer;
\r
182 const Byte *BufferLim = vs->BufferLim;
\r
184 const Byte *Buffer = inStream;
\r
185 const Byte *BufferLim = inStream + inSize;
\r
187 int state = vs->State;
\r
188 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
\r
189 int len = vs->RemainLen;
\r
190 UInt32 globalPos = vs->GlobalPos;
\r
191 UInt32 distanceLimit = vs->DistanceLimit;
\r
193 Byte *dictionary = vs->Dictionary;
\r
194 UInt32 dictionarySize = vs->Properties.DictionarySize;
\r
195 UInt32 dictionaryPos = vs->DictionaryPos;
\r
197 Byte tempDictionary[4];
\r
199 #ifndef _LZMA_IN_CB
\r
200 *inSizeProcessed = 0;
\r
202 *outSizeProcessed = 0;
\r
203 if (len == kLzmaStreamWasFinishedId)
\r
204 return LZMA_RESULT_OK;
\r
206 if (dictionarySize == 0)
\r
208 dictionary = tempDictionary;
\r
209 dictionarySize = 1;
\r
210 tempDictionary[0] = vs->TempDictionary[0];
\r
213 if (len == kLzmaNeedInitId)
\r
216 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
\r
218 for (i = 0; i < numProbs; i++)
\r
219 p[i] = kBitModelTotal >> 1;
\r
220 rep0 = rep1 = rep2 = rep3 = 1;
\r
225 dictionary[dictionarySize - 1] = 0;
\r
229 RC_INIT(inStream, inSize);
\r
234 while(len != 0 && nowPos < outSize)
\r
236 UInt32 pos = dictionaryPos - rep0;
\r
237 if (pos >= dictionarySize)
\r
238 pos += dictionarySize;
\r
239 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
\r
240 if (++dictionaryPos == dictionarySize)
\r
244 if (dictionaryPos == 0)
\r
245 previousByte = dictionary[dictionarySize - 1];
\r
247 previousByte = dictionary[dictionaryPos - 1];
\r
249 #else /* if !_LZMA_OUT_READ */
\r
252 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
\r
254 const Byte *Buffer;
\r
255 const Byte *BufferLim;
\r
259 #ifndef _LZMA_IN_CB
\r
260 *inSizeProcessed = 0;
\r
262 *outSizeProcessed = 0;
\r
266 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
\r
267 for (i = 0; i < numProbs; i++)
\r
268 p[i] = kBitModelTotal >> 1;
\r
274 RC_INIT(inStream, inSize);
\r
277 #endif /* _LZMA_OUT_READ */
\r
279 while(nowPos < outSize)
\r
283 int posState = (int)(
\r
285 #ifdef _LZMA_OUT_READ
\r
291 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
\r
296 prob = p + Literal + (LZMA_LIT_SIZE *
\r
299 #ifdef _LZMA_OUT_READ
\r
303 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
\r
305 if (state >= kNumLitStates)
\r
308 #ifdef _LZMA_OUT_READ
\r
309 UInt32 pos = dictionaryPos - rep0;
\r
310 if (pos >= dictionarySize)
\r
311 pos += dictionarySize;
\r
312 matchByte = dictionary[pos];
\r
314 matchByte = outStream[nowPos - rep0];
\r
321 bit = (matchByte & 0x100);
\r
322 probLit = prob + 0x100 + bit + symbol;
\r
323 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
\r
325 while (symbol < 0x100);
\r
327 while (symbol < 0x100)
\r
329 CProb *probLit = prob + symbol;
\r
330 RC_GET_BIT(probLit, symbol)
\r
332 previousByte = (Byte)symbol;
\r
334 outStream[nowPos++] = previousByte;
\r
335 #ifdef _LZMA_OUT_READ
\r
336 if (distanceLimit < dictionarySize)
\r
339 dictionary[dictionaryPos] = previousByte;
\r
340 if (++dictionaryPos == dictionarySize)
\r
343 if (state < 4) state = 0;
\r
344 else if (state < 10) state -= 3;
\r
350 prob = p + IsRep + state;
\r
357 state = state < kNumLitStates ? 0 : 3;
\r
358 prob = p + LenCoder;
\r
363 prob = p + IsRepG0 + state;
\r
367 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
\r
370 #ifdef _LZMA_OUT_READ
\r
375 #ifdef _LZMA_OUT_READ
\r
376 if (distanceLimit == 0)
\r
380 return LZMA_RESULT_DATA_ERROR;
\r
382 state = state < kNumLitStates ? 9 : 11;
\r
383 #ifdef _LZMA_OUT_READ
\r
384 pos = dictionaryPos - rep0;
\r
385 if (pos >= dictionarySize)
\r
386 pos += dictionarySize;
\r
387 previousByte = dictionary[pos];
\r
388 dictionary[dictionaryPos] = previousByte;
\r
389 if (++dictionaryPos == dictionarySize)
\r
392 previousByte = outStream[nowPos - rep0];
\r
394 outStream[nowPos++] = previousByte;
\r
395 #ifdef _LZMA_OUT_READ
\r
396 if (distanceLimit < dictionarySize)
\r
411 prob = p + IsRepG1 + state;
\r
420 prob = p + IsRepG2 + state;
\r
437 state = state < kNumLitStates ? 8 : 11;
\r
438 prob = p + RepLenCoder;
\r
441 int numBits, offset;
\r
442 CProb *probLen = prob + LenChoice;
\r
445 UpdateBit0(probLen);
\r
446 probLen = prob + LenLow + (posState << kLenNumLowBits);
\r
448 numBits = kLenNumLowBits;
\r
452 UpdateBit1(probLen);
\r
453 probLen = prob + LenChoice2;
\r
456 UpdateBit0(probLen);
\r
457 probLen = prob + LenMid + (posState << kLenNumMidBits);
\r
458 offset = kLenNumLowSymbols;
\r
459 numBits = kLenNumMidBits;
\r
463 UpdateBit1(probLen);
\r
464 probLen = prob + LenHigh;
\r
465 offset = kLenNumLowSymbols + kLenNumMidSymbols;
\r
466 numBits = kLenNumHighBits;
\r
469 RangeDecoderBitTreeDecode(probLen, numBits, len);
\r
476 state += kNumLitStates;
\r
477 prob = p + PosSlot +
\r
478 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
\r
480 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
\r
481 if (posSlot >= kStartPosModelIndex)
\r
483 int numDirectBits = ((posSlot >> 1) - 1);
\r
484 rep0 = (2 | ((UInt32)posSlot & 1));
\r
485 if (posSlot < kEndPosModelIndex)
\r
487 rep0 <<= numDirectBits;
\r
488 prob = p + SpecPos + rep0 - posSlot - 1;
\r
492 numDirectBits -= kNumAlignBits;
\r
504 while (--numDirectBits != 0);
\r
506 rep0 <<= kNumAlignBits;
\r
507 numDirectBits = kNumAlignBits;
\r
514 CProb *prob3 = prob + mi;
\r
515 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
\r
518 while(--numDirectBits != 0);
\r
523 if (++rep0 == (UInt32)(0))
\r
525 /* it's for stream version */
\r
526 len = kLzmaStreamWasFinishedId;
\r
531 len += kMatchMinLen;
\r
532 #ifdef _LZMA_OUT_READ
\r
533 if (rep0 > distanceLimit)
\r
537 return LZMA_RESULT_DATA_ERROR;
\r
539 #ifdef _LZMA_OUT_READ
\r
540 if (dictionarySize - distanceLimit > (UInt32)len)
\r
541 distanceLimit += len;
\r
543 distanceLimit = dictionarySize;
\r
548 #ifdef _LZMA_OUT_READ
\r
549 UInt32 pos = dictionaryPos - rep0;
\r
550 if (pos >= dictionarySize)
\r
551 pos += dictionarySize;
\r
552 previousByte = dictionary[pos];
\r
553 dictionary[dictionaryPos] = previousByte;
\r
554 if (++dictionaryPos == dictionarySize)
\r
557 previousByte = outStream[nowPos - rep0];
\r
560 outStream[nowPos++] = previousByte;
\r
562 while(len != 0 && nowPos < outSize);
\r
567 #ifdef _LZMA_OUT_READ
\r
570 vs->DictionaryPos = dictionaryPos;
\r
571 vs->GlobalPos = globalPos + (UInt32)nowPos;
\r
572 vs->DistanceLimit = distanceLimit;
\r
573 vs->Reps[0] = rep0;
\r
574 vs->Reps[1] = rep1;
\r
575 vs->Reps[2] = rep2;
\r
576 vs->Reps[3] = rep3;
\r
578 vs->RemainLen = len;
\r
579 vs->TempDictionary[0] = tempDictionary[0];
\r
583 vs->Buffer = Buffer;
\r
584 vs->BufferLim = BufferLim;
\r
586 *inSizeProcessed = (SizeT)(Buffer - inStream);
\r
588 *outSizeProcessed = nowPos;
\r
589 return LZMA_RESULT_OK;
\r