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