3 LZMA Decoder (State 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.
22 #include "LzmaStateDecode.h"
24 #define kNumTopBits 24
25 #define kTopValue ((UInt32)1 << kNumTopBits)
27 #define kNumBitModelTotalBits 11
28 #define kBitModelTotal (1 << kNumBitModelTotalBits)
29 #define kNumMoveBits 5
31 #define RC_READ_BYTE (*Buffer++)
33 #define RC_INIT Code = 0; Range = 0xFFFFFFFF; \
34 { int i; for(i = 0; i < 5; i++) { Code = (Code << 8) | RC_READ_BYTE; }}
36 #define RC_NORMALIZE if (Range < kTopValue) { Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
38 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
39 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
40 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
42 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
43 { UpdateBit0(p); mi <<= 1; A0; } else \
44 { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
46 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
48 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
49 { int i = numLevels; res = 1; \
50 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
51 res -= (1 << numLevels); }
54 #define kNumPosBitsMax 4
55 #define kNumPosStatesMax (1 << kNumPosBitsMax)
57 #define kLenNumLowBits 3
58 #define kLenNumLowSymbols (1 << kLenNumLowBits)
59 #define kLenNumMidBits 3
60 #define kLenNumMidSymbols (1 << kLenNumMidBits)
61 #define kLenNumHighBits 8
62 #define kLenNumHighSymbols (1 << kLenNumHighBits)
65 #define LenChoice2 (LenChoice + 1)
66 #define LenLow (LenChoice2 + 1)
67 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
68 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
69 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
73 #define kNumLitStates 7
75 #define kStartPosModelIndex 4
76 #define kEndPosModelIndex 14
77 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
79 #define kNumPosSlotBits 6
80 #define kNumLenToPosStates 4
82 #define kNumAlignBits 4
83 #define kAlignTableSize (1 << kNumAlignBits)
85 #define kMatchMinLen 2
88 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
89 #define IsRepG0 (IsRep + kNumStates)
90 #define IsRepG1 (IsRepG0 + kNumStates)
91 #define IsRepG2 (IsRepG1 + kNumStates)
92 #define IsRep0Long (IsRepG2 + kNumStates)
93 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
94 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
95 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
96 #define LenCoder (Align + kAlignTableSize)
97 #define RepLenCoder (LenCoder + kNumLenProbs)
98 #define Literal (RepLenCoder + kNumLenProbs)
100 #if Literal != LZMA_BASE_SIZE
104 /* kRequiredInBufferSize = number of required input bytes for worst case:
105 longest match with longest distance.
106 kLzmaInBufferSize must be larger than kRequiredInBufferSize
107 23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4(align) + 1 (RC_NORMALIZE)
110 #define kRequiredInBufferSize ((23 * (kNumBitModelTotalBits - kNumMoveBits + 1) + 26 + 9) / 8)
112 #define kLzmaStreamWasFinishedId (-1)
114 int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
117 if (size < LZMA_PROPERTIES_SIZE)
118 return LZMA_RESULT_DATA_ERROR;
119 prop0 = propsData[0];
120 if (prop0 >= (9 * 5 * 5))
121 return LZMA_RESULT_DATA_ERROR;
123 for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
124 for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
125 propsRes->lc = prop0;
127 unsigned char remainder = (unsigned char)(prop0 / 9);
128 propsRes->lc = prop0 % 9;
129 propsRes->pb = remainder / 5;
130 propsRes->lp = remainder % 5;
136 propsRes->DictionarySize = 0;
137 for (i = 0; i < 4; i++)
138 propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
139 if (propsRes->DictionarySize == 0)
140 propsRes->DictionarySize = 1;
141 return LZMA_RESULT_OK;
146 CLzmaDecoderState *vs,
147 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
148 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed,
151 UInt32 Range = vs->Range;
152 UInt32 Code = vs->Code;
154 unsigned char *Buffer = vs->Buffer;
155 int BufferSize = vs->BufferSize; /* don't change it to unsigned int */
156 CProb *p = vs->Probs;
158 int state = vs->State;
159 unsigned char previousByte;
160 UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
162 UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
163 UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
164 int lc = vs->Properties.lc;
165 int len = vs->RemainLen;
166 UInt32 globalPos = vs->GlobalPos;
167 UInt32 distanceLimit = vs->DistanceLimit;
169 unsigned char *dictionary = vs->Dictionary;
170 UInt32 dictionarySize = vs->Properties.DictionarySize;
171 UInt32 dictionaryPos = vs->DictionaryPos;
173 unsigned char tempDictionary[4];
175 (*inSizeProcessed) = 0;
176 (*outSizeProcessed) = 0;
177 if (len == kLzmaStreamWasFinishedId)
178 return LZMA_RESULT_OK;
180 if (dictionarySize == 0)
182 dictionary = tempDictionary;
184 tempDictionary[0] = vs->TempDictionary[0];
187 if (len == kLzmaNeedInitId)
189 while (inSize > 0 && BufferSize < kLzmaInBufferSize)
191 Buffer[BufferSize++] = *inStream++;
192 (*inSizeProcessed)++;
197 vs->BufferSize = BufferSize;
198 return finishDecoding ? LZMA_RESULT_DATA_ERROR : LZMA_RESULT_OK;
201 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
203 for (i = 0; i < numProbs; i++)
204 p[i] = kBitModelTotal >> 1;
205 rep0 = rep1 = rep2 = rep3 = 1;
210 dictionary[dictionarySize - 1] = 0;
215 while(len != 0 && nowPos < outSize)
217 UInt32 pos = dictionaryPos - rep0;
218 if (pos >= dictionarySize)
219 pos += dictionarySize;
220 outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
221 if (++dictionaryPos == dictionarySize)
225 if (dictionaryPos == 0)
226 previousByte = dictionary[dictionarySize - 1];
228 previousByte = dictionary[dictionaryPos - 1];
232 int bufferPos = (int)(Buffer - vs->Buffer);
233 if (BufferSize - bufferPos < kRequiredInBufferSize)
236 BufferSize -= bufferPos;
238 return LZMA_RESULT_DATA_ERROR;
239 for (i = 0; i < BufferSize; i++)
240 vs->Buffer[i] = Buffer[i];
242 while (inSize > 0 && BufferSize < kLzmaInBufferSize)
244 Buffer[BufferSize++] = *inStream++;
245 (*inSizeProcessed)++;
248 if (BufferSize < kRequiredInBufferSize && !finishDecoding)
251 if (nowPos >= outSize)
256 int posState = (int)((nowPos + globalPos) & posStateMask);
258 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
263 prob = p + Literal + (LZMA_LIT_SIZE *
264 ((((nowPos + globalPos)& literalPosMask) << lc) + (previousByte >> (8 - lc))));
266 if (state >= kNumLitStates)
269 UInt32 pos = dictionaryPos - rep0;
270 if (pos >= dictionarySize)
271 pos += dictionarySize;
272 matchByte = dictionary[pos];
278 bit = (matchByte & 0x100);
279 probLit = prob + 0x100 + bit + symbol;
280 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
282 while (symbol < 0x100);
284 while (symbol < 0x100)
286 CProb *probLit = prob + symbol;
287 RC_GET_BIT(probLit, symbol)
289 previousByte = (unsigned char)symbol;
291 outStream[nowPos++] = previousByte;
292 if (distanceLimit < dictionarySize)
295 dictionary[dictionaryPos] = previousByte;
296 if (++dictionaryPos == dictionarySize)
298 if (state < 4) state = 0;
299 else if (state < 10) state -= 3;
305 prob = p + IsRep + state;
312 state = state < kNumLitStates ? 0 : 3;
318 prob = p + IsRepG0 + state;
322 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
327 if (distanceLimit == 0)
328 return LZMA_RESULT_DATA_ERROR;
329 if (distanceLimit < dictionarySize)
331 state = state < kNumLitStates ? 9 : 11;
332 pos = dictionaryPos - rep0;
333 if (pos >= dictionarySize)
334 pos += dictionarySize;
335 previousByte = dictionary[pos];
336 dictionary[dictionaryPos] = previousByte;
337 if (++dictionaryPos == dictionarySize)
339 outStream[nowPos++] = previousByte;
351 prob = p + IsRepG1 + state;
360 prob = p + IsRepG2 + state;
377 state = state < kNumLitStates ? 8 : 11;
378 prob = p + RepLenCoder;
382 CProb *probLen = prob + LenChoice;
386 probLen = prob + LenLow + (posState << kLenNumLowBits);
388 numBits = kLenNumLowBits;
393 probLen = prob + LenChoice2;
397 probLen = prob + LenMid + (posState << kLenNumMidBits);
398 offset = kLenNumLowSymbols;
399 numBits = kLenNumMidBits;
404 probLen = prob + LenHigh;
405 offset = kLenNumLowSymbols + kLenNumMidSymbols;
406 numBits = kLenNumHighBits;
409 RangeDecoderBitTreeDecode(probLen, numBits, len);
416 state += kNumLitStates;
418 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
420 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
421 if (posSlot >= kStartPosModelIndex)
423 int numDirectBits = ((posSlot >> 1) - 1);
424 rep0 = (2 | ((UInt32)posSlot & 1));
425 if (posSlot < kEndPosModelIndex)
427 rep0 <<= numDirectBits;
428 prob = p + SpecPos + rep0 - posSlot - 1;
432 numDirectBits -= kNumAlignBits;
444 while (--numDirectBits != 0);
446 rep0 <<= kNumAlignBits;
447 numDirectBits = kNumAlignBits;
454 CProb *prob3 = prob + mi;
455 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
458 while(--numDirectBits != 0);
463 if (++rep0 == (UInt32)(0))
465 /* it's for stream version */
466 len = kLzmaStreamWasFinishedId;
472 if (rep0 > distanceLimit)
473 return LZMA_RESULT_DATA_ERROR;
474 if (dictionarySize - distanceLimit > (UInt32)len)
475 distanceLimit += len;
477 distanceLimit = dictionarySize;
481 UInt32 pos = dictionaryPos - rep0;
482 if (pos >= dictionarySize)
483 pos += dictionarySize;
484 previousByte = dictionary[pos];
485 dictionary[dictionaryPos] = previousByte;
486 if (++dictionaryPos == dictionarySize)
489 outStream[nowPos++] = previousByte;
491 while(len != 0 && nowPos < outSize);
497 BufferSize -= (int)(Buffer - vs->Buffer);
499 return LZMA_RESULT_DATA_ERROR;
502 for (i = 0; i < BufferSize; i++)
503 vs->Buffer[i] = Buffer[i];
505 vs->BufferSize = BufferSize;
508 vs->DictionaryPos = dictionaryPos;
509 vs->GlobalPos = (UInt32)(globalPos + nowPos);
510 vs->DistanceLimit = distanceLimit;
517 vs->TempDictionary[0] = tempDictionary[0];
519 (*outSizeProcessed) = nowPos;
520 return LZMA_RESULT_OK;