1 /*
2 LzmaDecode.c
3 LZMA Decoder
4 LZMA SDK 4.01 Copyright (c) 1999-2004 Igor Pavlov (2004-02-15)
5
6 Converted to a state machine by Amir Szekely
7 */
8
9 #include <stdlib.h>
10
11 #include "LzmaCompatDecode.h"
12
13 #define LEAVE { goto saveStateAndReturn; }
14 #define NEED_BYTE(c) case c: if (!avail_in) { mode = c; LEAVE; }
15 #define NEED_BYTE_ if (!avail_in) LEAVE;
16 #define NEXT_BYTE (avail_in--, *next_in++)
17 #define NEED_OUT(c) case c: if (!avail_out) { mode = c; LEAVE; }
18 #define PUT_BYTE_(b) { *next_out = b; next_out++; avail_out--; }
19 #define PUT_BYTE(b) { totalOut++; PUT_BYTE_(b) }
20 #define DECODE_BIT(c, x) prob = x; last = c; goto _LZMA_C_RDBD; case c:
21 #define DECODE_LEN(c, x) probs = x; last2 = c; goto _LZMA_C_LEND; case c:
22 #define DECODE_BIT_TREE(c, x, y) probs = x; numLevels = y; last3 = c; goto _LZMA_C_BTD; case c:
23
24 enum {
25 /* 0 */ LZMA_C_INIT = 0,
26 /* 1 */ LZMA_C_GETDICT,
27 /* 2 */ LZMA_C_BLOCK,
28 /* 3 */ LZMA_C_RDI, /* RangeDecoderInit */
29 /* 4 */ LZMA_C_RDBD, /* RangeDecoderBitDecode */
30 /* 5 */ LZMA_C_RDBD_IN, /* RangeDecoderBitDecode */
31 /* 6 */ LZMA_C_TYPE,
32 /* 7 */ LZMA_C_ISREP,
33 /* 8 */ LZMA_C_ISREPG0,
34 /* 9 */ LZMA_C_ISREP0LONG,
35 /* 10 */ LZMA_C_ISREPG1,
36 /* 11 */ LZMA_C_ISREPG2,
37 /* 12 */ LZMA_C_NORM,
38 /* 13 */ LZMA_C_LITDM1, /* LzmaLiteralDecodeMatch */
39 /* 14 */ LZMA_C_LITDM2, /* LzmaLiteralDecodeMatch */
40 /* 15 */ LZMA_C_LITD, /* LzmaLiteralDecode */
41 /* 16 */ LZMA_C_RDRBTD, /* RangeDecoderReverseBitTreeDecode */
42 /* 17 */ LZMA_C_LEND, /* LzmaLenDecode */
43 /* 18 */ LZMA_C_LEND1, /* LzmaLenDecode */
44 /* 19 */ LZMA_C_LEND2, /* LzmaLenDecode */
45 /* 20 */ LZMA_C_LEND_RES, /* LzmaLenDecode */
46 /* 21 */ LZMA_C_LEND_C1,
47 /* 22 */ LZMA_C_LEND_C2,
48 /* 23 */ LZMA_C_BTD, /* RangeDecoderBitTreeDecode */
49 /* 24 */ LZMA_C_BTD_LOOP,
50 /* 25 */ LZMA_C_BTD_C1,
51 /* 26 */ LZMA_C_OUTPUT_1,
52 /* 27 */ LZMA_C_OUTPUT_2,
53 /* 28 */ LZMA_C_OUTPUT_3
54 };
55
56 #define kNumTopBits 24
57 #define kTopValue ((UInt32)1 << kNumTopBits)
58
59 #define kNumBitModelTotalBits 11
60 #define kBitModelTotal (1 << kNumBitModelTotalBits)
61 #define kNumMoveBits 5
62
63 #define RC_NORMALIZE(c) if (range < kTopValue) { NEED_BYTE(c); range <<= 8; code = (code << 8) | NEXT_BYTE; }
64
65 #define RC_GET_BIT2(c, prob, mi, A0, A1) { \
66 bound = (range >> kNumBitModelTotalBits) * *prob; \
67 if (code < bound) \
68 { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
69 else \
70 { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
71 RC_NORMALIZE(c) \
72 }
73
74 #define RC_GET_BIT(c, prob, mi) RC_GET_BIT2(c, prob, mi, ; , ;)
75
76 #define kNumPosBitsMax 4
77 #define kNumPosStatesMax (1 << kNumPosBitsMax)
78
79 #define kLenNumLowBits 3
80 #define kLenNumLowSymbols (1 << kLenNumLowBits)
81 #define kLenNumMidBits 3
82 #define kLenNumMidSymbols (1 << kLenNumMidBits)
83 #define kLenNumHighBits 8
84 #define kLenNumHighSymbols (1 << kLenNumHighBits)
85
86 #define LenChoice 0
87 #define LenChoice2 (LenChoice + 1)
88 #define LenLow (LenChoice2 + 1)
89 #define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
90 #define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
91 #define kNumLenProbs (LenHigh + kLenNumHighSymbols)
92
93 #define kNumStates 12
94
95 #define kStartPosModelIndex 4
96 #define kEndPosModelIndex 14
97 #define kNumFullDistances (1 << (kEndPosModelIndex >> 1))
98
99 #define kNumPosSlotBits 6
100 #define kNumLenToPosStates 4
101
102 #define kNumAlignBits 4
103 #define kAlignTableSize (1 << kNumAlignBits)
104
105 #define kMatchMinLen 2
106
107 #define IsMatch 0
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)
119
120 #define LZMA_BASE_SIZE 1846
121 #define LZMA_LIT_SIZE 768
122
123 #if Literal != LZMA_BASE_SIZE
124 StopCompilingDueBUG
125 #endif
126
lzmaCompatInit(lzma_stream * s)127 void LZMACALL lzmaCompatInit(lzma_stream *s)
128 {
129 /* size of lzma_stream minus the size of the two allocated buffer pointers.
130 we don't want to lose to pointer or else we won't be able to free them. */
131 SizeT i = sizeof(lzma_stream) - (sizeof(unsigned char *) * 2);
132 while (i--)
133 ((Byte *)s)[i] = 0;
134
135 s->rep0 = s->rep1 = s->rep2 = s->rep3 = 1;
136 s->range = (0xFFFFFFFF);
137 }
138
lzmaCompatDecode(lzma_stream * s)139 int LZMACALL lzmaCompatDecode(lzma_stream *s)
140 {
141 UInt32 bound;
142 UInt32 pos;
143
144 /* restore decoder state */
145 lzma_stream _s = *s;
146
147 #define mode _s.mode
148 #define last _s.last
149 #define last2 _s.last2
150 #define last3 _s.last3
151
152 #define p ((CProb *) _s.dynamicData)
153 #define dynamicDataSize _s.dynamicDataSize
154
155 #define state _s.state
156 #define isPreviousMatch _s.isPreviousMatch
157 #define previousByte _s.previousByte
158 #define rep0 _s.rep0
159 #define rep1 _s.rep1
160 #define rep2 _s.rep2
161 #define rep3 _s.rep3
162 #define lc _s.lc
163 #define len _s.len
164 #define totalOut _s.totalOut
165
166 #define dictionary _s.dictionary
167 #define dictionarySize _s.dictionarySize
168 #define dictionaryPos _s.dictionaryPos
169
170 #define posStateMask _s.posStateMask
171 #define literalPosMask _s.literalPosMask
172
173 #define avail_in _s.avail_in
174 #define next_in _s.next_in
175 #define avail_out _s.avail_out
176 #define next_out _s.next_out
177
178 #define range _s.range
179 #define code _s.code
180
181 #define probs _s.probs
182 #define prob _s.prob
183
184 #define symbol _s.temp2
185 #define bit _s.temp3
186 #define matchBit _s.temp1
187 #define i _s.temp1
188 #define result _s.temp2
189 #define numLevels _s.temp3
190 #define posSlot _s.temp2
191 #define newDictionarySize ((UInt32) _s.temp3)
192
193 #define matchByte _s.matchByte
194 #define mi _s.mi
195 #define posState _s.posState
196
197 if (len == -1)
198 return LZMA_STREAM_END;
199
200 for (;;) switch (mode)
201 {
202 case LZMA_C_INIT:
203 {
204 Byte firstByte;
205 UInt32 newDynamicDataSize;
206 UInt32 numProbs;
207 int lp;
208 int pb;
209
210 NEED_BYTE_;
211
212 firstByte = NEXT_BYTE;
213
214 if (firstByte > (9*5*5))
215 return LZMA_DATA_ERROR;
216
217 pb = firstByte / (9*5);
218 firstByte %= (9*5);
219 lp = firstByte / 9;
220 firstByte %= 9;
221 lc = firstByte;
222
223 posStateMask = (1 << (pb)) - 1;
224 literalPosMask = (1 << (lp)) - 1;
225
226 numProbs = Literal + (LZMA_LIT_SIZE << (lc + pb));
227 newDynamicDataSize = numProbs * sizeof(CProb);
228
229 if (newDynamicDataSize != dynamicDataSize)
230 {
231 if (p)
232 lzmafree(p);
233 //p = lzmaalloc(newDynamicDataSize);
234 _s.dynamicData = (Byte *) lzmaalloc(newDynamicDataSize);
235 if (!p)
236 return LZMA_NOT_ENOUGH_MEM;
237 dynamicDataSize = newDynamicDataSize;
238 }
239
240 while (numProbs--)
241 p[numProbs] = kBitModelTotal >> 1;
242
243
244 //for (i = 0, newDictionarySize = 0; i < 4; i++)
245 for (i = 0, _s.temp3 = 0; i < 4; i++)
246 {
247 NEED_BYTE(LZMA_C_GETDICT);
248 //newDictionarySize |= NEXT_BYTE << (i * 8);
249 _s.temp3 |= NEXT_BYTE << (i * 8);
250 }
251
252 if (newDictionarySize != dictionarySize)
253 {
254 dictionarySize = newDictionarySize;
255 if (dictionary)
256 lzmafree(dictionary);
257 dictionary = (Byte *) lzmaalloc(dictionarySize);
258 if (!dictionary)
259 return LZMA_NOT_ENOUGH_MEM;
260 }
261
262 dictionary[dictionarySize - 1] = 0;
263
264 i = 5;
265 while (i--)
266 {
267 NEED_BYTE(LZMA_C_RDI);
268 code = (code << 8) | NEXT_BYTE;
269 }
270 }
271 case LZMA_C_BLOCK:
272 posState = (int)(totalOut & posStateMask);
273 DECODE_BIT(LZMA_C_TYPE, p + IsMatch + (state << kNumPosBitsMax) + posState);
274 if (bit == 0)
275 {
276 probs = p + Literal + (LZMA_LIT_SIZE *
277 (((totalOut & literalPosMask) << lc) + (previousByte >> (8 - lc))));
278
279 if (state < 4) state = 0;
280 else if (state < 10) state -= 3;
281 else state -= 6;
282 if (isPreviousMatch)
283 {
284 pos = dictionaryPos - rep0;
285 if (pos >= dictionarySize)
286 pos += dictionarySize;
287 matchByte = dictionary[pos];
288 {
289 symbol = 1;
290 do
291 {
292 matchBit = (matchByte >> 7) & 1;
293 matchByte <<= 1;
294 {
295 prob = probs + ((1 + matchBit) << 8) + symbol;
296 RC_GET_BIT2(LZMA_C_LITDM1, prob, symbol, bit = 0, bit = 1)
297 }
298 if (matchBit != bit)
299 {
300 while (symbol < 0x100)
301 {
302 prob = probs + symbol;
303 RC_GET_BIT(LZMA_C_LITDM2, prob, symbol)
304 }
305 break;
306 }
307 }
308 while (symbol < 0x100);
309 previousByte = symbol;
310 }
311 isPreviousMatch = 0;
312 }
313 else
314 {
315 symbol = 1;
316 do
317 {
318 prob = probs + symbol;
319 RC_GET_BIT(LZMA_C_LITD, prob, symbol)
320 }
321 while (symbol < 0x100);
322 previousByte = symbol;
323 }
324 NEED_OUT(LZMA_C_OUTPUT_1);
325 PUT_BYTE(previousByte);
326 dictionary[dictionaryPos] = previousByte;
327 dictionaryPos = (dictionaryPos + 1) % dictionarySize;
328 }
329 /* bit == 1 */
330 else
331 {
332 isPreviousMatch = 1;
333 DECODE_BIT(LZMA_C_ISREP, p + IsRep + state);
334 if (bit == 1)
335 {
336 DECODE_BIT(LZMA_C_ISREPG0, p + IsRepG0 + state);
337 if (bit == 0)
338 {
339 DECODE_BIT(LZMA_C_ISREP0LONG, p + IsRep0Long + (state << kNumPosBitsMax) + posState);
340 if (bit == 0)
341 {
342 if (totalOut == 0)
343 return LZMA_DATA_ERROR;
344 state = state < 7 ? 9 : 11;
345 NEED_OUT(LZMA_C_OUTPUT_2);
346 pos = dictionaryPos - rep0;
347 if (pos >= dictionarySize)
348 pos += dictionarySize;
349 previousByte = dictionary[pos];
350 dictionary[dictionaryPos] = previousByte;
351 dictionaryPos = (dictionaryPos + 1) % dictionarySize;
352 PUT_BYTE(previousByte);
353 mode = LZMA_C_BLOCK;
354 break;
355 }
356 }
357 else
358 {
359 UInt32 distance;
360 DECODE_BIT(LZMA_C_ISREPG1, p + IsRepG1 + state);
361 if (bit == 0)
362 {
363 distance = rep1;
364 }
365 else
366 {
367 DECODE_BIT(LZMA_C_ISREPG2, p + IsRepG2 + state);
368 if (bit == 0)
369 distance = rep2;
370 else
371 {
372 distance = rep3;
373 rep3 = rep2;
374 }
375 rep2 = rep1;
376 }
377 rep1 = rep0;
378 rep0 = distance;
379 }
380 DECODE_LEN(LZMA_C_LEND_C1, p + RepLenCoder);
381 state = state < 7 ? 8 : 11;
382 }
383 else
384 {
385 rep3 = rep2;
386 rep2 = rep1;
387 rep1 = rep0;
388 state = state < 7 ? 7 : 10;
389 DECODE_LEN(LZMA_C_LEND_C2, p + LenCoder);
390 DECODE_BIT_TREE(
391 LZMA_C_BTD_C1,
392 p + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits),
393 kNumPosSlotBits
394 );
395 if (posSlot >= kStartPosModelIndex)
396 {
397 int numDirectBits = ((posSlot >> 1) - 1);
398 rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
399 if (posSlot < kEndPosModelIndex)
400 {
401 probs = p + SpecPos + rep0 - posSlot - 1;
402 numLevels = numDirectBits;
403 }
404 else
405 {
406 int numTotalBits = numDirectBits - kNumAlignBits;
407 result = 0;
408 for (i = numTotalBits; i > 0; i--)
409 {
410 /* UInt32 t; */
411 range >>= 1;
412
413 result <<= 1;
414 if (code >= range)
415 {
416 code -= range;
417 result |= 1;
418 }
419 /*
420 t = (code - range) >> 31;
421 t &= 1;
422 code -= range & (t - 1);
423 result = (result + result) | (1 - t);
424 */
425 RC_NORMALIZE(LZMA_C_NORM)
426 }
427 rep0 += result << kNumAlignBits;
428 probs = p + Align;
429 numLevels = kNumAlignBits;
430 }
431 mi = 1;
432 symbol = 0;
433 for(i = 0; i < numLevels; i++)
434 {
435 prob = probs + mi;
436 RC_GET_BIT2(LZMA_C_RDRBTD, prob, mi, ; , symbol |= (1 << i));
437 }
438 rep0 += symbol;
439 }
440 else
441 rep0 = posSlot;
442 rep0++;
443 }
444 if (rep0 == (UInt32)(0))
445 {
446 len = -1;
447 LEAVE;
448 }
449 if (rep0 > totalOut)
450 {
451 return LZMA_DATA_ERROR;
452 }
453 len += kMatchMinLen;
454 do
455 {
456 NEED_OUT(LZMA_C_OUTPUT_3);
457 pos = dictionaryPos - rep0;
458 if (pos >= dictionarySize)
459 pos += dictionarySize;
460 previousByte = dictionary[pos];
461 dictionary[dictionaryPos] = previousByte;
462 dictionaryPos = (dictionaryPos + 1) % dictionarySize;
463 PUT_BYTE(previousByte);
464 len--;
465 }
466 while(len > 0);
467 }
468 mode = LZMA_C_BLOCK;
469 break;
470 case LZMA_C_RDBD:
471 _LZMA_C_RDBD:
472 {
473 UInt32 bound = (range >> kNumBitModelTotalBits) * *prob;
474 if (code < bound)
475 {
476 range = bound;
477 *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
478 bit = 0;
479 }
480 else
481 {
482 range -= bound;
483 code -= bound;
484 *prob -= (*prob) >> kNumMoveBits;
485 bit = 1;
486 }
487 RC_NORMALIZE(LZMA_C_RDBD_IN);
488 }
489 mode = last;
490 break;
491 case LZMA_C_LEND:
492 _LZMA_C_LEND:
493 DECODE_BIT(LZMA_C_LEND1, probs + LenChoice);
494 if (bit == 0)
495 {
496 len = 0;
497 probs += LenLow + (posState << kLenNumLowBits);
498 numLevels = kLenNumLowBits;
499 }
500 else {
501 DECODE_BIT(LZMA_C_LEND2, probs + LenChoice2);
502 if (bit == 0)
503 {
504 len = kLenNumLowSymbols;
505 probs += + LenMid + (posState << kLenNumMidBits);
506 numLevels = kLenNumMidBits;
507 }
508 else
509 {
510 len = kLenNumLowSymbols + kLenNumMidSymbols;
511 probs += LenHigh;
512 numLevels = kLenNumHighBits;
513 }
514 }
515
516 last3 = LZMA_C_LEND_RES;
517 case LZMA_C_BTD:
518 _LZMA_C_BTD:
519 mi = 1;
520 for(i = numLevels; i > 0; i--)
521 {
522 prob = probs + mi;
523 RC_GET_BIT(LZMA_C_BTD_LOOP, prob, mi)
524 }
525 result = mi - (1 << numLevels);
526 mode = last3;
527 break;
528 case LZMA_C_LEND_RES:
529 len += result;
530 mode = last2;
531 break;
532 default:
533 return LZMA_DATA_ERROR;
534 }
535
536 saveStateAndReturn:
537
538 /* save decoder state */
539 *s = _s;
540
541 return LZMA_OK;
542 }
543