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.
22
#include "LzmaDecode.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_INIT2 Code = 0; Range = 0xFFFFFFFF; \
34
{ int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | RC_READ_BYTE; }}
38
#define RC_TEST { if (Buffer == BufferLim) \
39
{ SizeT size; int result = InCallback->Read(InCallback, &Buffer, &size); if (result != LZMA_RESULT_OK) return result; \
40
BufferLim = Buffer + size; if (size == 0) return LZMA_RESULT_DATA_ERROR; }}
42
#define RC_INIT Buffer = BufferLim = 0; RC_INIT2
46
#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
48
#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
52
#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
54
#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
55
#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
56
#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
58
#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
59
{ UpdateBit0(p); mi <<= 1; A0; } else \
60
{ UpdateBit1(p); mi = (mi + mi) + 1; A1; }
62
#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
64
#define RangeDecoderBitTreeDecode(probs, numLevels, res) \
65
{ int i = numLevels; res = 1; \
66
do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
67
res -= (1 << numLevels); }
70
#define kNumPosBitsMax 4
71
#define kNumPosStatesMax (1 << kNumPosBitsMax)
73
#define kLenNumLowBits 3
74
#define kLenNumLowSymbols (1 << kLenNumLowBits)
75
#define kLenNumMidBits 3
76
#define kLenNumMidSymbols (1 << kLenNumMidBits)
77
#define kLenNumHighBits 8
78
#define kLenNumHighSymbols (1 << kLenNumHighBits)
81
#define LenChoice2 (LenChoice + 1)
82
#define LenLow (LenChoice2 + 1)
83
#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
84
#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
85
#define kNumLenProbs (LenHigh + kLenNumHighSymbols)
89
#define kNumLitStates 7
91
#define kStartPosModelIndex 4
92
#define kEndPosModelIndex 14
93
#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
95
#define kNumPosSlotBits 6
96
#define kNumLenToPosStates 4
98
#define kNumAlignBits 4
99
#define kAlignTableSize (1 << kNumAlignBits)
101
#define kMatchMinLen 2
104
#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
105
#define IsRepG0 (IsRep + kNumStates)
106
#define IsRepG1 (IsRepG0 + kNumStates)
107
#define IsRepG2 (IsRepG1 + kNumStates)
108
#define IsRep0Long (IsRepG2 + kNumStates)
109
#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
110
#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
111
#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
112
#define LenCoder (Align + kAlignTableSize)
113
#define RepLenCoder (LenCoder + kNumLenProbs)
114
#define Literal (RepLenCoder + kNumLenProbs)
116
#if Literal != LZMA_BASE_SIZE
120
int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
123
if (size < LZMA_PROPERTIES_SIZE)
124
return LZMA_RESULT_DATA_ERROR;
125
prop0 = propsData[0];
126
if (prop0 >= (9 * 5 * 5))
127
return LZMA_RESULT_DATA_ERROR;
129
for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * 5));
130
for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9);
131
propsRes->lc = prop0;
133
unsigned char remainder = (unsigned char)(prop0 / 9);
134
propsRes->lc = prop0 % 9;
135
propsRes->pb = remainder / 5;
136
propsRes->lp = remainder % 5;
140
#ifdef _LZMA_OUT_READ
143
propsRes->DictionarySize = 0;
144
for (i = 0; i < 4; i++)
145
propsRes->DictionarySize += (UInt32)(propsData[1 + i]) << (i * 8);
146
if (propsRes->DictionarySize == 0)
147
propsRes->DictionarySize = 1;
150
return LZMA_RESULT_OK;
153
#define kLzmaStreamWasFinishedId (-1)
155
int LzmaDecode(CLzmaDecoderState *vs,
157
ILzmaInCallback *InCallback,
159
const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
161
unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
163
CProb *p = vs->Probs;
165
Byte previousByte = 0;
166
UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1;
167
UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1;
168
int lc = vs->Properties.lc;
170
#ifdef _LZMA_OUT_READ
172
UInt32 Range = vs->Range;
173
UInt32 Code = vs->Code;
175
const Byte *Buffer = vs->Buffer;
176
const Byte *BufferLim = vs->BufferLim;
178
const Byte *Buffer = inStream;
179
const Byte *BufferLim = inStream + inSize;
181
int state = vs->State;
182
UInt32 rep0 = vs->Reps[0], rep1 = vs->Reps[1], rep2 = vs->Reps[2], rep3 = vs->Reps[3];
183
int len = vs->RemainLen;
184
UInt32 globalPos = vs->GlobalPos;
185
UInt32 distanceLimit = vs->DistanceLimit;
187
Byte *dictionary = vs->Dictionary;
188
UInt32 dictionarySize = vs->Properties.DictionarySize;
189
UInt32 dictionaryPos = vs->DictionaryPos;
191
Byte tempDictionary[4];
194
*inSizeProcessed = 0;
196
*outSizeProcessed = 0;
197
if (len == kLzmaStreamWasFinishedId)
198
return LZMA_RESULT_OK;
200
if (dictionarySize == 0)
202
dictionary = tempDictionary;
204
tempDictionary[0] = vs->TempDictionary[0];
207
if (len == kLzmaNeedInitId)
210
UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
212
for (i = 0; i < numProbs; i++)
213
p[i] = kBitModelTotal >> 1;
214
rep0 = rep1 = rep2 = rep3 = 1;
219
dictionary[dictionarySize - 1] = 0;
223
RC_INIT(inStream, inSize);
228
while(len != 0 && nowPos < outSize)
230
UInt32 pos = dictionaryPos - rep0;
231
if (pos >= dictionarySize)
232
pos += dictionarySize;
233
outStream[nowPos++] = dictionary[dictionaryPos] = dictionary[pos];
234
if (++dictionaryPos == dictionarySize)
238
if (dictionaryPos == 0)
239
previousByte = dictionary[dictionarySize - 1];
241
previousByte = dictionary[dictionaryPos - 1];
243
#else /* if !_LZMA_OUT_READ */
246
UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
249
const Byte *BufferLim;
254
*inSizeProcessed = 0;
256
*outSizeProcessed = 0;
260
UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
261
for (i = 0; i < numProbs; i++)
262
p[i] = kBitModelTotal >> 1;
268
RC_INIT(inStream, inSize);
271
#endif /* _LZMA_OUT_READ */
273
while(nowPos < outSize)
277
int posState = (int)(
279
#ifdef _LZMA_OUT_READ
285
prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
290
prob = p + Literal + (LZMA_LIT_SIZE *
293
#ifdef _LZMA_OUT_READ
297
& literalPosMask) << lc) + (previousByte >> (8 - lc))));
299
if (state >= kNumLitStates)
302
#ifdef _LZMA_OUT_READ
303
UInt32 pos = dictionaryPos - rep0;
304
if (pos >= dictionarySize)
305
pos += dictionarySize;
306
matchByte = dictionary[pos];
308
matchByte = outStream[nowPos - rep0];
315
bit = (matchByte & 0x100);
316
probLit = prob + 0x100 + bit + symbol;
317
RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
319
while (symbol < 0x100);
321
while (symbol < 0x100)
323
CProb *probLit = prob + symbol;
324
RC_GET_BIT(probLit, symbol)
326
previousByte = (Byte)symbol;
328
outStream[nowPos++] = previousByte;
329
#ifdef _LZMA_OUT_READ
330
if (distanceLimit < dictionarySize)
333
dictionary[dictionaryPos] = previousByte;
334
if (++dictionaryPos == dictionarySize)
337
if (state < 4) state = 0;
338
else if (state < 10) state -= 3;
344
prob = p + IsRep + state;
351
state = state < kNumLitStates ? 0 : 3;
357
prob = p + IsRepG0 + state;
361
prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
364
#ifdef _LZMA_OUT_READ
369
#ifdef _LZMA_OUT_READ
370
if (distanceLimit == 0)
374
return LZMA_RESULT_DATA_ERROR;
376
state = state < kNumLitStates ? 9 : 11;
377
#ifdef _LZMA_OUT_READ
378
pos = dictionaryPos - rep0;
379
if (pos >= dictionarySize)
380
pos += dictionarySize;
381
previousByte = dictionary[pos];
382
dictionary[dictionaryPos] = previousByte;
383
if (++dictionaryPos == dictionarySize)
386
previousByte = outStream[nowPos - rep0];
388
outStream[nowPos++] = previousByte;
389
#ifdef _LZMA_OUT_READ
390
if (distanceLimit < dictionarySize)
405
prob = p + IsRepG1 + state;
414
prob = p + IsRepG2 + state;
431
state = state < kNumLitStates ? 8 : 11;
432
prob = p + RepLenCoder;
436
CProb *probLen = prob + LenChoice;
440
probLen = prob + LenLow + (posState << kLenNumLowBits);
442
numBits = kLenNumLowBits;
447
probLen = prob + LenChoice2;
451
probLen = prob + LenMid + (posState << kLenNumMidBits);
452
offset = kLenNumLowSymbols;
453
numBits = kLenNumMidBits;
458
probLen = prob + LenHigh;
459
offset = kLenNumLowSymbols + kLenNumMidSymbols;
460
numBits = kLenNumHighBits;
463
RangeDecoderBitTreeDecode(probLen, numBits, len);
470
state += kNumLitStates;
472
((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
474
RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
475
if (posSlot >= kStartPosModelIndex)
477
int numDirectBits = ((posSlot >> 1) - 1);
478
rep0 = (2 | ((UInt32)posSlot & 1));
479
if (posSlot < kEndPosModelIndex)
481
rep0 <<= numDirectBits;
482
prob = p + SpecPos + rep0 - posSlot - 1;
486
numDirectBits -= kNumAlignBits;
498
while (--numDirectBits != 0);
500
rep0 <<= kNumAlignBits;
501
numDirectBits = kNumAlignBits;
508
CProb *prob3 = prob + mi;
509
RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
512
while(--numDirectBits != 0);
517
if (++rep0 == (UInt32)(0))
519
/* it's for stream version */
520
len = kLzmaStreamWasFinishedId;
526
#ifdef _LZMA_OUT_READ
527
if (rep0 > distanceLimit)
531
return LZMA_RESULT_DATA_ERROR;
533
#ifdef _LZMA_OUT_READ
534
if (dictionarySize - distanceLimit > (UInt32)len)
535
distanceLimit += len;
537
distanceLimit = dictionarySize;
542
#ifdef _LZMA_OUT_READ
543
UInt32 pos = dictionaryPos - rep0;
544
if (pos >= dictionarySize)
545
pos += dictionarySize;
546
previousByte = dictionary[pos];
547
dictionary[dictionaryPos] = previousByte;
548
if (++dictionaryPos == dictionarySize)
551
previousByte = outStream[nowPos - rep0];
554
outStream[nowPos++] = previousByte;
556
while(len != 0 && nowPos < outSize);
561
#ifdef _LZMA_OUT_READ
564
vs->DictionaryPos = dictionaryPos;
565
vs->GlobalPos = globalPos + (UInt32)nowPos;
566
vs->DistanceLimit = distanceLimit;
573
vs->TempDictionary[0] = tempDictionary[0];
578
vs->BufferLim = BufferLim;
580
*inSizeProcessed = (SizeT)(Buffer - inStream);
582
*outSizeProcessed = nowPos;
583
return LZMA_RESULT_OK;