blob: 65819b53cf2215c4df714d7814cfaad797046279 [file] [log] [blame]
Kevin O'Connor592323f2009-04-26 23:17:49 -04001/*
2 LzmaDecode.c
3 LZMA Decoder (optimized for Speed version)
4
5 LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01)
6 http://www.7-zip.org/
7
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.
13
14 SPECIAL EXCEPTION:
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.
20*/
21
22#include "lzmadecode.h"
23
24#define kNumTopBits 24
25#define kTopValue ((UInt32)1 << kNumTopBits)
26
27#define kNumBitModelTotalBits 11
28#define kBitModelTotal (1 << kNumBitModelTotalBits)
29#define kNumMoveBits 5
30
31#define RC_READ_BYTE (*Buffer++)
32
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; }}
35
36
37#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; }
38
39#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + bufferSize; RC_INIT2
40
41
42#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = (Code << 8) | RC_READ_BYTE; }
43
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;
47
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; }
51
52#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;)
53
54#define RangeDecoderBitTreeDecode(probs, numLevels, res) \
55 { int i = numLevels; res = 1; \
56 do { CProb *cp = probs + res; RC_GET_BIT(cp, res) } while(--i != 0); \
57 res -= (1 << numLevels); }
58
59
60#define kNumPosBitsMax 4
61#define kNumPosStatesMax (1 << kNumPosBitsMax)
62
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)
69
70#define LenChoice 0
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)
76
77
78#define kNumStates 12
79#define kNumLitStates 7
80
81#define kStartPosModelIndex 4
82#define kEndPosModelIndex 14
83#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
84
85#define kNumPosSlotBits 6
86#define kNumLenToPosStates 4
87
88#define kNumAlignBits 4
89#define kAlignTableSize (1 << kNumAlignBits)
90
91#define kMatchMinLen 2
92
93#define IsMatch 0
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)
105
106#if Literal != LZMA_BASE_SIZE
107StopCompilingDueBUG
108#endif
109
110int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char *propsData, int size)
111{
112 unsigned char prop0;
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;
118 {
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;
122 /*
123 unsigned char remainder = (unsigned char)(prop0 / 9);
124 propsRes->lc = prop0 % 9;
125 propsRes->pb = remainder / 5;
126 propsRes->lp = remainder % 5;
127 */
128 }
129
130 return LZMA_RESULT_OK;
131}
132
133#define kLzmaStreamWasFinishedId (-1)
134
135int LzmaDecode(CLzmaDecoderState *vs,
136 const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed,
137 unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed)
138{
139 CProb *p = vs->Probs;
140 SizeT nowPos = 0;
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;
145
146
147 int state = 0;
148 UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
149 int len = 0;
150 const Byte *Buffer;
151 const Byte *BufferLim;
152 UInt32 Range;
153 UInt32 Code;
154
155 *inSizeProcessed = 0;
156 *outSizeProcessed = 0;
157
158 {
159 UInt32 i;
160 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + vs->Properties.lp));
161 for (i = 0; i < numProbs; i++)
162 p[i] = kBitModelTotal >> 1;
163 }
164
165 RC_INIT(inStream, inSize);
166
167
168 while(nowPos < outSize)
169 {
170 CProb *prob;
171 UInt32 bound;
172 int posState = (int)(
173 (nowPos
174 )
175 & posStateMask);
176
177 prob = p + IsMatch + (state << kNumPosBitsMax) + posState;
178 IfBit0(prob)
179 {
180 int symbol = 1;
181 UpdateBit0(prob)
182 prob = p + Literal + (LZMA_LIT_SIZE *
183 (((
184 (nowPos
185 )
186 & literalPosMask) << lc) + (previousByte >> (8 - lc))));
187
188 if (state >= kNumLitStates)
189 {
190 int matchByte;
191 matchByte = outStream[nowPos - rep0];
192 do
193 {
194 int bit;
195 CProb *probLit;
196 matchByte <<= 1;
197 bit = (matchByte & 0x100);
198 probLit = prob + 0x100 + bit + symbol;
199 RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) break)
200 }
201 while (symbol < 0x100);
202 }
203 while (symbol < 0x100)
204 {
205 CProb *probLit = prob + symbol;
206 RC_GET_BIT(probLit, symbol)
207 }
208 previousByte = (Byte)symbol;
209
210 outStream[nowPos++] = previousByte;
211 if (state < 4) state = 0;
212 else if (state < 10) state -= 3;
213 else state -= 6;
214 }
215 else
216 {
217 UpdateBit1(prob);
218 prob = p + IsRep + state;
219 IfBit0(prob)
220 {
221 UpdateBit0(prob);
222 rep3 = rep2;
223 rep2 = rep1;
224 rep1 = rep0;
225 state = state < kNumLitStates ? 0 : 3;
226 prob = p + LenCoder;
227 }
228 else
229 {
230 UpdateBit1(prob);
231 prob = p + IsRepG0 + state;
232 IfBit0(prob)
233 {
234 UpdateBit0(prob);
235 prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState;
236 IfBit0(prob)
237 {
238 UpdateBit0(prob);
239
240 if (nowPos == 0)
241 return LZMA_RESULT_DATA_ERROR;
242
243 state = state < kNumLitStates ? 9 : 11;
244 previousByte = outStream[nowPos - rep0];
245 outStream[nowPos++] = previousByte;
246
247 continue;
248 }
249 else
250 {
251 UpdateBit1(prob);
252 }
253 }
254 else
255 {
256 UInt32 distance;
257 UpdateBit1(prob);
258 prob = p + IsRepG1 + state;
259 IfBit0(prob)
260 {
261 UpdateBit0(prob);
262 distance = rep1;
263 }
264 else
265 {
266 UpdateBit1(prob);
267 prob = p + IsRepG2 + state;
268 IfBit0(prob)
269 {
270 UpdateBit0(prob);
271 distance = rep2;
272 }
273 else
274 {
275 UpdateBit1(prob);
276 distance = rep3;
277 rep3 = rep2;
278 }
279 rep2 = rep1;
280 }
281 rep1 = rep0;
282 rep0 = distance;
283 }
284 state = state < kNumLitStates ? 8 : 11;
285 prob = p + RepLenCoder;
286 }
287 {
288 int numBits, offset;
289 CProb *probLen = prob + LenChoice;
290 IfBit0(probLen)
291 {
292 UpdateBit0(probLen);
293 probLen = prob + LenLow + (posState << kLenNumLowBits);
294 offset = 0;
295 numBits = kLenNumLowBits;
296 }
297 else
298 {
299 UpdateBit1(probLen);
300 probLen = prob + LenChoice2;
301 IfBit0(probLen)
302 {
303 UpdateBit0(probLen);
304 probLen = prob + LenMid + (posState << kLenNumMidBits);
305 offset = kLenNumLowSymbols;
306 numBits = kLenNumMidBits;
307 }
308 else
309 {
310 UpdateBit1(probLen);
311 probLen = prob + LenHigh;
312 offset = kLenNumLowSymbols + kLenNumMidSymbols;
313 numBits = kLenNumHighBits;
314 }
315 }
316 RangeDecoderBitTreeDecode(probLen, numBits, len);
317 len += offset;
318 }
319
320 if (state < 4)
321 {
322 int posSlot;
323 state += kNumLitStates;
324 prob = p + PosSlot +
325 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
326 kNumPosSlotBits);
327 RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot);
328 if (posSlot >= kStartPosModelIndex)
329 {
330 int numDirectBits = ((posSlot >> 1) - 1);
331 rep0 = (2 | ((UInt32)posSlot & 1));
332 if (posSlot < kEndPosModelIndex)
333 {
334 rep0 <<= numDirectBits;
335 prob = p + SpecPos + rep0 - posSlot - 1;
336 }
337 else
338 {
339 numDirectBits -= kNumAlignBits;
340 do
341 {
342 RC_NORMALIZE
343 Range >>= 1;
344 rep0 <<= 1;
345 if (Code >= Range)
346 {
347 Code -= Range;
348 rep0 |= 1;
349 }
350 }
351 while (--numDirectBits != 0);
352 prob = p + Align;
353 rep0 <<= kNumAlignBits;
354 numDirectBits = kNumAlignBits;
355 }
356 {
357 int i = 1;
358 int mi = 1;
359 do
360 {
361 CProb *prob3 = prob + mi;
362 RC_GET_BIT2(prob3, mi, ; , rep0 |= i);
363 i <<= 1;
364 }
365 while(--numDirectBits != 0);
366 }
367 }
368 else
369 rep0 = posSlot;
370 if (++rep0 == (UInt32)(0))
371 {
372 /* it's for stream version */
373 len = kLzmaStreamWasFinishedId;
374 break;
375 }
376 }
377
378 len += kMatchMinLen;
379 if (rep0 > nowPos)
380 return LZMA_RESULT_DATA_ERROR;
381
382
383 do
384 {
385 previousByte = outStream[nowPos - rep0];
386 len--;
387 outStream[nowPos++] = previousByte;
388 }
389 while(len != 0 && nowPos < outSize);
390 }
391 }
392 RC_NORMALIZE;
393
394
395 *inSizeProcessed = (SizeT)(Buffer - inStream);
396 *outSizeProcessed = nowPos;
397 return LZMA_RESULT_OK;
398}