1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 *p = probs + res; RC_GET_BIT(p, 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
124
125
126
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
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}
399
