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
;
This page took 0.073245 seconds and 5 git commands to generate.