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; }}
37 #define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
39 #define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
42 #define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
44 #define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * *(p); if (Code < bound)
45 #define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> kNumMoveBits;
46 #define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> kNumMoveBits;
48 #define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \
49 { UpdateBit0(p); mi <<= 1; A0; } else \
50 { UpdateBit1(p); mi = (mi + mi) + 1; A1; }
52 #define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
54 #define RangeDecoderBitTreeDecode(probs, numLevels, res) \
55 { int i = numLevels; res = 1; \
56 do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \
57 res -= (1 << numLevels); }
60 #define kNumPosBitsMax 4
61 #define kNumPosStatesMax (1 << kNumPosBitsMax)
63 #define kLenNumLowBits 3
64 #define kLenNumLowSymbols (1 << kLenNumLowBits)
65 #define kLenNumMidBits 3
66 #define kLenNumMidSymbols (1 << kLenNumMidBits)
67 #define kLenNumHighBits 8
68 #define kLenNumHighSymbols (1 << kLenNumHighBits)
71 #define LenChoice2 (LenChoice + 1)
72 #define LenLow (LenChoice2 + 1)
73 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
74 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
75 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
79 #define kNumLitStates 7
81 #define kStartPosModelIndex 4
82 #define kEndPosModelIndex 14
83 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
85 #define kNumPosSlotBits 6
86 #define kNumLenToPosStates 4
88 #define kNumAlignBits 4
89 #define kAlignTableSize (1 << kNumAlignBits)
91 #define kMatchMinLen 2
94 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
95 #define IsRepG0 (IsRep + kNumStates)
96 #define IsRepG1 (IsRepG0 + kNumStates)
97 #define IsRepG2 (IsRepG1 + kNumStates)
98 #define IsRep0Long (IsRepG2 + kNumStates)
99 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
100 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
101 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
102 #define LenCoder (Align + kAlignTableSize)
103 #define RepLenCoder (LenCoder + kNumLenProbs)
104 #define Literal (RepLenCoder + kNumLenProbs)
106 #if Literal != LZMA_BASE_SIZE
110 int LzmaDecodeProperties(CLzmaProperties
*propsRes
, const unsigned char *propsData
, int size
)
113 if (size
< LZMA_PROPERTIES_SIZE
)
114 return LZMA_RESULT_DATA_ERROR
;
115 prop0
= propsData
[0];
116 if (prop0
>= (9 * 5 * 5))
117 return LZMA_RESULT_DATA_ERROR
;
119 for (propsRes
->pb
= 0; prop0
>= (9 * 5); propsRes
->pb
++, prop0
-= (9 * 5));
120 for (propsRes
->lp
= 0; prop0
>= 9; propsRes
->lp
++, prop0
-= 9);
121 propsRes
->lc
= prop0
;
123 unsigned char remainder = (unsigned char)(prop0 / 9);
124 propsRes->lc = prop0 % 9;
125 propsRes->pb = remainder / 5;
126 propsRes->lp = remainder % 5;
130 return LZMA_RESULT_OK
;
133 #define kLzmaStreamWasFinishedId (-1)
135 int LzmaDecode(CLzmaDecoderState
*vs
,
136 const unsigned char *inStream
, SizeT inSize
, SizeT
*inSizeProcessed
,
137 unsigned char *outStream
, SizeT outSize
, SizeT
*outSizeProcessed
)
139 CProb
*p
= vs
->Probs
;
141 Byte previousByte
= 0;
142 UInt32 posStateMask
= (1 << (vs
->Properties
.pb
)) - 1;
143 UInt32 literalPosMask
= (1 << (vs
->Properties
.lp
)) - 1;
144 int lc
= vs
->Properties
.lc
;
148 UInt32 rep0
= 1, rep1
= 1, rep2
= 1, rep3
= 1;
151 const Byte
*BufferLim
;
155 *inSizeProcessed
= 0;
156 *outSizeProcessed
= 0;
160 UInt32 numProbs
= Literal
+ ((UInt32
)LZMA_LIT_SIZE
<< (lc
+ vs
->Properties
.lp
));
161 for (i
= 0; i
< numProbs
; i
++)
162 p
[i
] = kBitModelTotal
>> 1;
165 RC_INIT(inStream
, inSize
);
168 while(nowPos
< outSize
)
172 int posState
= (int)(
177 prob
= p
+ IsMatch
+ (state
<< kNumPosBitsMax
) + posState
;
182 prob
= p
+ Literal
+ (LZMA_LIT_SIZE
*
186 & literalPosMask
) << lc
) + (previousByte
>> (8 - lc
))));
188 if (state
>= kNumLitStates
)
191 matchByte
= outStream
[nowPos
- rep0
];
197 bit
= (matchByte
& 0x100);
198 probLit
= prob
+ 0x100 + bit
+ symbol
;
199 RC_GET_BIT2(probLit
, symbol
, if (bit
!= 0) break, if (bit
== 0) break)
201 while (symbol
< 0x100);
203 while (symbol
< 0x100)
205 CProb
*probLit
= prob
+ symbol
;
206 RC_GET_BIT(probLit
, symbol
)
208 previousByte
= (Byte
)symbol
;
210 outStream
[nowPos
++] = previousByte
;
211 if (state
< 4) state
= 0;
212 else if (state
< 10) state
-= 3;
218 prob
= p
+ IsRep
+ state
;
225 state
= state
< kNumLitStates
? 0 : 3;
231 prob
= p
+ IsRepG0
+ state
;
235 prob
= p
+ IsRep0Long
+ (state
<< kNumPosBitsMax
) + posState
;
241 return LZMA_RESULT_DATA_ERROR
;
243 state
= state
< kNumLitStates
? 9 : 11;
244 previousByte
= outStream
[nowPos
- rep0
];
245 outStream
[nowPos
++] = previousByte
;
258 prob
= p
+ IsRepG1
+ state
;
267 prob
= p
+ IsRepG2
+ state
;
284 state
= state
< kNumLitStates
? 8 : 11;
285 prob
= p
+ RepLenCoder
;
289 CProb
*probLen
= prob
+ LenChoice
;
293 probLen
= prob
+ LenLow
+ (posState
<< kLenNumLowBits
);
295 numBits
= kLenNumLowBits
;
300 probLen
= prob
+ LenChoice2
;
304 probLen
= prob
+ LenMid
+ (posState
<< kLenNumMidBits
);
305 offset
= kLenNumLowSymbols
;
306 numBits
= kLenNumMidBits
;
311 probLen
= prob
+ LenHigh
;
312 offset
= kLenNumLowSymbols
+ kLenNumMidSymbols
;
313 numBits
= kLenNumHighBits
;
316 RangeDecoderBitTreeDecode(probLen
, numBits
, len
);
323 state
+= kNumLitStates
;
325 ((len
< kNumLenToPosStates
? len
: kNumLenToPosStates
- 1) <<
327 RangeDecoderBitTreeDecode(prob
, kNumPosSlotBits
, posSlot
);
328 if (posSlot
>= kStartPosModelIndex
)
330 int numDirectBits
= ((posSlot
>> 1) - 1);
331 rep0
= (2 | ((UInt32
)posSlot
& 1));
332 if (posSlot
< kEndPosModelIndex
)
334 rep0
<<= numDirectBits
;
335 prob
= p
+ SpecPos
+ rep0
- posSlot
- 1;
339 numDirectBits
-= kNumAlignBits
;
351 while (--numDirectBits
!= 0);
353 rep0
<<= kNumAlignBits
;
354 numDirectBits
= kNumAlignBits
;
361 CProb
*prob3
= prob
+ mi
;
362 RC_GET_BIT2(prob3
, mi
, ; , rep0
|= i
);
365 while(--numDirectBits
!= 0);
370 if (++rep0
== (UInt32
)(0))
372 /* it's for stream version */
373 len
= kLzmaStreamWasFinishedId
;
380 return LZMA_RESULT_DATA_ERROR
;
385 previousByte
= outStream
[nowPos
- rep0
];
387 outStream
[nowPos
++] = previousByte
;
389 while(len
!= 0 && nowPos
< outSize
);
395 *inSizeProcessed
= (SizeT
)(Buffer
- inStream
);
396 *outSizeProcessed
= nowPos
;
397 return LZMA_RESULT_OK
;