1 /* LzmaDec.c -- LZMA Decoder
2 2008-11-06 : Igor Pavlov : Public domain */
3
4 #include "LzmaDec.h"
5
6 #include <string.h>
7
8 #define kNumTopBits 24
9 #define kTopValue ((UInt32)1 << kNumTopBits)
10
11 #define kNumBitModelTotalBits 11
12 #define kBitModelTotal (1 << kNumBitModelTotalBits)
13 #define kNumMoveBits 5
14
15 #define RC_INIT_SIZE 5
16
17 #define NORMALIZE if (range < kTopValue) { range <<= 8; code = (code << 8) | (*buf++); }
18
19 #define IF_BIT_0(p) ttt = *(p); NORMALIZE; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
20 #define UPDATE_0(p) range = bound; *(p) = (CLzmaProb)(ttt + ((kBitModelTotal - ttt) >> kNumMoveBits));
21 #define UPDATE_1(p) range -= bound; code -= bound; *(p) = (CLzmaProb)(ttt - (ttt >> kNumMoveBits));
22 #define GET_BIT2(p, i, A0, A1) IF_BIT_0(p) \
23 { UPDATE_0(p); i = (i + i); A0; } else \
24 { UPDATE_1(p); i = (i + i) + 1; A1; }
25 #define GET_BIT(p, i) GET_BIT2(p, i, ; , ;)
26
27 #define TREE_GET_BIT(probs, i) { GET_BIT((probs + i), i); }
28 #define TREE_DECODE(probs, limit, i) \
29 { i = 1; do { TREE_GET_BIT(probs, i); } while (i < limit); i -= limit; }
30
31 /* #define _LZMA_SIZE_OPT */
32
33 #ifdef _LZMA_SIZE_OPT
34 #define TREE_6_DECODE(probs, i) TREE_DECODE(probs, (1 << 6), i)
35 #else
36 #define TREE_6_DECODE(probs, i) \
37 { i = 1; \
38 TREE_GET_BIT(probs, i); \
39 TREE_GET_BIT(probs, i); \
40 TREE_GET_BIT(probs, i); \
41 TREE_GET_BIT(probs, i); \
42 TREE_GET_BIT(probs, i); \
43 TREE_GET_BIT(probs, i); \
44 i -= 0x40; }
45 #endif
46
47 #define NORMALIZE_CHECK if (range < kTopValue) { if (buf >= bufLimit) return DUMMY_ERROR; range <<= 8; code = (code << 8) | (*buf++); }
48
49 #define IF_BIT_0_CHECK(p) ttt = *(p); NORMALIZE_CHECK; bound = (range >> kNumBitModelTotalBits) * ttt; if (code < bound)
50 #define UPDATE_0_CHECK range = bound;
51 #define UPDATE_1_CHECK range -= bound; code -= bound;
52 #define GET_BIT2_CHECK(p, i, A0, A1) IF_BIT_0_CHECK(p) \
53 { UPDATE_0_CHECK; i = (i + i); A0; } else \
54 { UPDATE_1_CHECK; i = (i + i) + 1; A1; }
55 #define GET_BIT_CHECK(p, i) GET_BIT2_CHECK(p, i, ; , ;)
56 #define TREE_DECODE_CHECK(probs, limit, i) \
57 { i = 1; do { GET_BIT_CHECK(probs + i, i) } while (i < limit); i -= limit; }
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 #define kMatchSpecLenStart (kMatchMinLen + kLenNumLowSymbols + kLenNumMidSymbols + kLenNumHighSymbols)
93
94 #define IsMatch 0
95 #define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
96 #define IsRepG0 (IsRep + kNumStates)
97 #define IsRepG1 (IsRepG0 + kNumStates)
98 #define IsRepG2 (IsRepG1 + kNumStates)
99 #define IsRep0Long (IsRepG2 + kNumStates)
100 #define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
101 #define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
102 #define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
103 #define LenCoder (Align + kAlignTableSize)
104 #define RepLenCoder (LenCoder + kNumLenProbs)
105 #define Literal (RepLenCoder + kNumLenProbs)
106
107 #define LZMA_BASE_SIZE 1846
108 #define LZMA_LIT_SIZE 768
109
110 #define LzmaProps_GetNumProbs(p) ((UInt32)LZMA_BASE_SIZE + (LZMA_LIT_SIZE << ((p)->lc + (p)->lp)))
111
112 #if Literal != LZMA_BASE_SIZE
113 StopCompilingDueBUG
114 #endif
115
116 static const Byte kLiteralNextStates[kNumStates * 2] =
117 {
118 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5,
119 7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10
120 };
121
122 #define LZMA_DIC_MIN (1 << 12)
123
124 /* First LZMA-symbol is always decoded.
125 And it decodes new LZMA-symbols while (buf < bufLimit), but "buf" is without last normalization
126 Out:
127 Result:
128 SZ_OK - OK
129 SZ_ERROR_DATA - Error
130 p->remainLen:
131 < kMatchSpecLenStart : normal remain
132 = kMatchSpecLenStart : finished
133 = kMatchSpecLenStart + 1 : Flush marker
134 = kMatchSpecLenStart + 2 : State Init Marker
135 */
136
LzmaDec_DecodeReal(CLzmaDec * p,SizeT limit,const Byte * bufLimit)137 static int MY_FAST_CALL LzmaDec_DecodeReal(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
138 {
139 CLzmaProb *probs = p->probs;
140
141 unsigned state = p->state;
142 UInt32 rep0 = p->reps[0], rep1 = p->reps[1], rep2 = p->reps[2], rep3 = p->reps[3];
143 unsigned pbMask = ((unsigned)1 << (p->prop.pb)) - 1;
144 unsigned lpMask = ((unsigned)1 << (p->prop.lp)) - 1;
145 unsigned lc = p->prop.lc;
146
147 Byte *dic = p->dic;
148 SizeT dicBufSize = p->dicBufSize;
149 SizeT dicPos = p->dicPos;
150
151 UInt32 processedPos = p->processedPos;
152 UInt32 checkDicSize = p->checkDicSize;
153 unsigned len = 0;
154
155 const Byte *buf = p->buf;
156 UInt32 range = p->range;
157 UInt32 code = p->code;
158
159 do
160 {
161 CLzmaProb *prob;
162 UInt32 bound;
163 unsigned ttt;
164 unsigned posState = processedPos & pbMask;
165
166 prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
167 IF_BIT_0(prob)
168 {
169 unsigned symbol;
170 UPDATE_0(prob);
171 prob = probs + Literal;
172 if (checkDicSize != 0 || processedPos != 0)
173 prob += (LZMA_LIT_SIZE * (((processedPos & lpMask) << lc) +
174 (dic[(dicPos == 0 ? dicBufSize : dicPos) - 1] >> (8 - lc))));
175
176 if (state < kNumLitStates)
177 {
178 symbol = 1;
179 do { GET_BIT(prob + symbol, symbol) } while (symbol < 0x100);
180 }
181 else
182 {
183 unsigned matchByte = p->dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
184 unsigned offs = 0x100;
185 symbol = 1;
186 do
187 {
188 unsigned bit;
189 CLzmaProb *probLit;
190 matchByte <<= 1;
191 bit = (matchByte & offs);
192 probLit = prob + offs + bit + symbol;
193 GET_BIT2(probLit, symbol, offs &= ~bit, offs &= bit)
194 }
195 while (symbol < 0x100);
196 }
197 dic[dicPos++] = (Byte)symbol;
198 processedPos++;
199
200 state = kLiteralNextStates[state];
201 /* if (state < 4) state = 0; else if (state < 10) state -= 3; else state -= 6; */
202 continue;
203 }
204 else
205 {
206 UPDATE_1(prob);
207 prob = probs + IsRep + state;
208 IF_BIT_0(prob)
209 {
210 UPDATE_0(prob);
211 state += kNumStates;
212 prob = probs + LenCoder;
213 }
214 else
215 {
216 UPDATE_1(prob);
217 if (checkDicSize == 0 && processedPos == 0)
218 return SZ_ERROR_DATA;
219 prob = probs + IsRepG0 + state;
220 IF_BIT_0(prob)
221 {
222 UPDATE_0(prob);
223 prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
224 IF_BIT_0(prob)
225 {
226 UPDATE_0(prob);
227 dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
228 dicPos++;
229 processedPos++;
230 state = state < kNumLitStates ? 9 : 11;
231 continue;
232 }
233 UPDATE_1(prob);
234 }
235 else
236 {
237 UInt32 distance;
238 UPDATE_1(prob);
239 prob = probs + IsRepG1 + state;
240 IF_BIT_0(prob)
241 {
242 UPDATE_0(prob);
243 distance = rep1;
244 }
245 else
246 {
247 UPDATE_1(prob);
248 prob = probs + IsRepG2 + state;
249 IF_BIT_0(prob)
250 {
251 UPDATE_0(prob);
252 distance = rep2;
253 }
254 else
255 {
256 UPDATE_1(prob);
257 distance = rep3;
258 rep3 = rep2;
259 }
260 rep2 = rep1;
261 }
262 rep1 = rep0;
263 rep0 = distance;
264 }
265 state = state < kNumLitStates ? 8 : 11;
266 prob = probs + RepLenCoder;
267 }
268 {
269 unsigned limit, offset;
270 CLzmaProb *probLen = prob + LenChoice;
271 IF_BIT_0(probLen)
272 {
273 UPDATE_0(probLen);
274 probLen = prob + LenLow + (posState << kLenNumLowBits);
275 offset = 0;
276 limit = (1 << kLenNumLowBits);
277 }
278 else
279 {
280 UPDATE_1(probLen);
281 probLen = prob + LenChoice2;
282 IF_BIT_0(probLen)
283 {
284 UPDATE_0(probLen);
285 probLen = prob + LenMid + (posState << kLenNumMidBits);
286 offset = kLenNumLowSymbols;
287 limit = (1 << kLenNumMidBits);
288 }
289 else
290 {
291 UPDATE_1(probLen);
292 probLen = prob + LenHigh;
293 offset = kLenNumLowSymbols + kLenNumMidSymbols;
294 limit = (1 << kLenNumHighBits);
295 }
296 }
297 TREE_DECODE(probLen, limit, len);
298 len += offset;
299 }
300
301 if (state >= kNumStates)
302 {
303 UInt32 distance;
304 prob = probs + PosSlot +
305 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits);
306 TREE_6_DECODE(prob, distance);
307 if (distance >= kStartPosModelIndex)
308 {
309 unsigned posSlot = (unsigned)distance;
310 int numDirectBits = (int)(((distance >> 1) - 1));
311 distance = (2 | (distance & 1));
312 if (posSlot < kEndPosModelIndex)
313 {
314 distance <<= numDirectBits;
315 prob = probs + SpecPos + distance - posSlot - 1;
316 {
317 UInt32 mask = 1;
318 unsigned i = 1;
319 do
320 {
321 GET_BIT2(prob + i, i, ; , distance |= mask);
322 mask <<= 1;
323 }
324 while (--numDirectBits != 0);
325 }
326 }
327 else
328 {
329 numDirectBits -= kNumAlignBits;
330 do
331 {
332 NORMALIZE
333 range >>= 1;
334
335 {
336 UInt32 t;
337 code -= range;
338 t = (0 - ((UInt32)code >> 31)); /* (UInt32)((Int32)code >> 31) */
339 distance = (distance << 1) + (t + 1);
340 code += range & t;
341 }
342 /*
343 distance <<= 1;
344 if (code >= range)
345 {
346 code -= range;
347 distance |= 1;
348 }
349 */
350 }
351 while (--numDirectBits != 0);
352 prob = probs + Align;
353 distance <<= kNumAlignBits;
354 {
355 unsigned i = 1;
356 GET_BIT2(prob + i, i, ; , distance |= 1);
357 GET_BIT2(prob + i, i, ; , distance |= 2);
358 GET_BIT2(prob + i, i, ; , distance |= 4);
359 GET_BIT2(prob + i, i, ; , distance |= 8);
360 }
361 if (distance == (UInt32)0xFFFFFFFF)
362 {
363 len += kMatchSpecLenStart;
364 state -= kNumStates;
365 break;
366 }
367 }
368 }
369 rep3 = rep2;
370 rep2 = rep1;
371 rep1 = rep0;
372 rep0 = distance + 1;
373 if (checkDicSize == 0)
374 {
375 if (distance >= processedPos)
376 return SZ_ERROR_DATA;
377 }
378 else if (distance >= checkDicSize)
379 return SZ_ERROR_DATA;
380 state = (state < kNumStates + kNumLitStates) ? kNumLitStates : kNumLitStates + 3;
381 /* state = kLiteralNextStates[state]; */
382 }
383
384 len += kMatchMinLen;
385
386 if (limit == dicPos)
387 return SZ_ERROR_DATA;
388 {
389 SizeT rem = limit - dicPos;
390 unsigned curLen = ((rem < len) ? (unsigned)rem : len);
391 SizeT pos = (dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0);
392
393 processedPos += curLen;
394
395 len -= curLen;
396 if (pos + curLen <= dicBufSize)
397 {
398 Byte *dest = dic + dicPos;
399 ptrdiff_t src = (ptrdiff_t)pos - (ptrdiff_t)dicPos;
400 const Byte *lim = dest + curLen;
401 dicPos += curLen;
402 do
403 *(dest) = (Byte)*(dest + src);
404 while (++dest != lim);
405 }
406 else
407 {
408 do
409 {
410 dic[dicPos++] = dic[pos];
411 if (++pos == dicBufSize)
412 pos = 0;
413 }
414 while (--curLen != 0);
415 }
416 }
417 }
418 }
419 while (dicPos < limit && buf < bufLimit);
420 NORMALIZE;
421 p->buf = buf;
422 p->range = range;
423 p->code = code;
424 p->remainLen = len;
425 p->dicPos = dicPos;
426 p->processedPos = processedPos;
427 p->reps[0] = rep0;
428 p->reps[1] = rep1;
429 p->reps[2] = rep2;
430 p->reps[3] = rep3;
431 p->state = state;
432
433 return SZ_OK;
434 }
435
LzmaDec_WriteRem(CLzmaDec * p,SizeT limit)436 static void MY_FAST_CALL LzmaDec_WriteRem(CLzmaDec *p, SizeT limit)
437 {
438 if (p->remainLen != 0 && p->remainLen < kMatchSpecLenStart)
439 {
440 Byte *dic = p->dic;
441 SizeT dicPos = p->dicPos;
442 SizeT dicBufSize = p->dicBufSize;
443 unsigned len = p->remainLen;
444 UInt32 rep0 = p->reps[0];
445 if (limit - dicPos < len)
446 len = (unsigned)(limit - dicPos);
447
448 if (p->checkDicSize == 0 && p->prop.dicSize - p->processedPos <= len)
449 p->checkDicSize = p->prop.dicSize;
450
451 p->processedPos += len;
452 p->remainLen -= len;
453 while (len-- != 0)
454 {
455 dic[dicPos] = dic[(dicPos - rep0) + ((dicPos < rep0) ? dicBufSize : 0)];
456 dicPos++;
457 }
458 p->dicPos = dicPos;
459 }
460 }
461
LzmaDec_DecodeReal2(CLzmaDec * p,SizeT limit,const Byte * bufLimit)462 static int MY_FAST_CALL LzmaDec_DecodeReal2(CLzmaDec *p, SizeT limit, const Byte *bufLimit)
463 {
464 do
465 {
466 SizeT limit2 = limit;
467 if (p->checkDicSize == 0)
468 {
469 UInt32 rem = p->prop.dicSize - p->processedPos;
470 if (limit - p->dicPos > rem)
471 limit2 = p->dicPos + rem;
472 }
473 RINOK(LzmaDec_DecodeReal(p, limit2, bufLimit));
474 if (p->processedPos >= p->prop.dicSize)
475 p->checkDicSize = p->prop.dicSize;
476 LzmaDec_WriteRem(p, limit);
477 }
478 while (p->dicPos < limit && p->buf < bufLimit && p->remainLen < kMatchSpecLenStart);
479
480 if (p->remainLen > kMatchSpecLenStart)
481 {
482 p->remainLen = kMatchSpecLenStart;
483 }
484 return 0;
485 }
486
487 typedef enum
488 {
489 DUMMY_ERROR, /* unexpected end of input stream */
490 DUMMY_LIT,
491 DUMMY_MATCH,
492 DUMMY_REP
493 } ELzmaDummy;
494
LzmaDec_TryDummy(const CLzmaDec * p,const Byte * buf,SizeT inSize)495 static ELzmaDummy LzmaDec_TryDummy(const CLzmaDec *p, const Byte *buf, SizeT inSize)
496 {
497 UInt32 range = p->range;
498 UInt32 code = p->code;
499 const Byte *bufLimit = buf + inSize;
500 CLzmaProb *probs = p->probs;
501 unsigned state = p->state;
502 ELzmaDummy res;
503
504 {
505 CLzmaProb *prob;
506 UInt32 bound;
507 unsigned ttt;
508 unsigned posState = (p->processedPos) & ((1 << p->prop.pb) - 1);
509
510 prob = probs + IsMatch + (state << kNumPosBitsMax) + posState;
511 IF_BIT_0_CHECK(prob)
512 {
513 UPDATE_0_CHECK
514
515 /* if (bufLimit - buf >= 7) return DUMMY_LIT; */
516
517 prob = probs + Literal;
518 if (p->checkDicSize != 0 || p->processedPos != 0)
519 prob += (LZMA_LIT_SIZE *
520 ((((p->processedPos) & ((1 << (p->prop.lp)) - 1)) << p->prop.lc) +
521 (p->dic[(p->dicPos == 0 ? p->dicBufSize : p->dicPos) - 1] >> (8 - p->prop.lc))));
522
523 if (state < kNumLitStates)
524 {
525 unsigned symbol = 1;
526 do { GET_BIT_CHECK(prob + symbol, symbol) } while (symbol < 0x100);
527 }
528 else
529 {
530 unsigned matchByte = p->dic[p->dicPos - p->reps[0] +
531 ((p->dicPos < p->reps[0]) ? p->dicBufSize : 0)];
532 unsigned offs = 0x100;
533 unsigned symbol = 1;
534 do
535 {
536 unsigned bit;
537 CLzmaProb *probLit;
538 matchByte <<= 1;
539 bit = (matchByte & offs);
540 probLit = prob + offs + bit + symbol;
541 GET_BIT2_CHECK(probLit, symbol, offs &= ~bit, offs &= bit)
542 }
543 while (symbol < 0x100);
544 }
545 res = DUMMY_LIT;
546 }
547 else
548 {
549 unsigned len;
550 UPDATE_1_CHECK;
551
552 prob = probs + IsRep + state;
553 IF_BIT_0_CHECK(prob)
554 {
555 UPDATE_0_CHECK;
556 state = 0;
557 prob = probs + LenCoder;
558 res = DUMMY_MATCH;
559 }
560 else
561 {
562 UPDATE_1_CHECK;
563 res = DUMMY_REP;
564 prob = probs + IsRepG0 + state;
565 IF_BIT_0_CHECK(prob)
566 {
567 UPDATE_0_CHECK;
568 prob = probs + IsRep0Long + (state << kNumPosBitsMax) + posState;
569 IF_BIT_0_CHECK(prob)
570 {
571 UPDATE_0_CHECK;
572 NORMALIZE_CHECK;
573 return DUMMY_REP;
574 }
575 else
576 {
577 UPDATE_1_CHECK;
578 }
579 }
580 else
581 {
582 UPDATE_1_CHECK;
583 prob = probs + IsRepG1 + state;
584 IF_BIT_0_CHECK(prob)
585 {
586 UPDATE_0_CHECK;
587 }
588 else
589 {
590 UPDATE_1_CHECK;
591 prob = probs + IsRepG2 + state;
592 IF_BIT_0_CHECK(prob)
593 {
594 UPDATE_0_CHECK;
595 }
596 else
597 {
598 UPDATE_1_CHECK;
599 }
600 }
601 }
602 state = kNumStates;
603 prob = probs + RepLenCoder;
604 }
605 {
606 unsigned limit, offset;
607 CLzmaProb *probLen = prob + LenChoice;
608 IF_BIT_0_CHECK(probLen)
609 {
610 UPDATE_0_CHECK;
611 probLen = prob + LenLow + (posState << kLenNumLowBits);
612 offset = 0;
613 limit = 1 << kLenNumLowBits;
614 }
615 else
616 {
617 UPDATE_1_CHECK;
618 probLen = prob + LenChoice2;
619 IF_BIT_0_CHECK(probLen)
620 {
621 UPDATE_0_CHECK;
622 probLen = prob + LenMid + (posState << kLenNumMidBits);
623 offset = kLenNumLowSymbols;
624 limit = 1 << kLenNumMidBits;
625 }
626 else
627 {
628 UPDATE_1_CHECK;
629 probLen = prob + LenHigh;
630 offset = kLenNumLowSymbols + kLenNumMidSymbols;
631 limit = 1 << kLenNumHighBits;
632 }
633 }
634 TREE_DECODE_CHECK(probLen, limit, len);
635 len += offset;
636 }
637
638 if (state < 4)
639 {
640 unsigned posSlot;
641 prob = probs + PosSlot +
642 ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) <<
643 kNumPosSlotBits);
644 TREE_DECODE_CHECK(prob, 1 << kNumPosSlotBits, posSlot);
645 if (posSlot >= kStartPosModelIndex)
646 {
647 int numDirectBits = ((posSlot >> 1) - 1);
648
649 /* if (bufLimit - buf >= 8) return DUMMY_MATCH; */
650
651 if (posSlot < kEndPosModelIndex)
652 {
653 prob = probs + SpecPos + ((2 | (posSlot & 1)) << numDirectBits) - posSlot - 1;
654 }
655 else
656 {
657 numDirectBits -= kNumAlignBits;
658 do
659 {
660 NORMALIZE_CHECK
661 range >>= 1;
662 code -= range & (((code - range) >> 31) - 1);
663 /* if (code >= range) code -= range; */
664 }
665 while (--numDirectBits != 0);
666 prob = probs + Align;
667 numDirectBits = kNumAlignBits;
668 }
669 {
670 unsigned i = 1;
671 do
672 {
673 GET_BIT_CHECK(prob + i, i);
674 }
675 while (--numDirectBits != 0);
676 }
677 }
678 }
679 }
680 }
681 NORMALIZE_CHECK;
682 return res;
683 }
684
685
LzmaDec_InitRc(CLzmaDec * p,const Byte * data)686 static void LzmaDec_InitRc(CLzmaDec *p, const Byte *data)
687 {
688 p->code = ((UInt32)data[1] << 24) | ((UInt32)data[2] << 16) | ((UInt32)data[3] << 8) | ((UInt32)data[4]);
689 p->range = 0xFFFFFFFF;
690 p->needFlush = 0;
691 }
692
LzmaDec_InitDicAndState(CLzmaDec * p,Bool initDic,Bool initState)693 void LzmaDec_InitDicAndState(CLzmaDec *p, Bool initDic, Bool initState)
694 {
695 p->needFlush = 1;
696 p->remainLen = 0;
697 p->tempBufSize = 0;
698
699 if (initDic)
700 {
701 p->processedPos = 0;
702 p->checkDicSize = 0;
703 p->needInitState = 1;
704 }
705 if (initState)
706 p->needInitState = 1;
707 }
708
LzmaDec_Init(CLzmaDec * p)709 void LzmaDec_Init(CLzmaDec *p)
710 {
711 p->dicPos = 0;
712 LzmaDec_InitDicAndState(p, True, True);
713 }
714
LzmaDec_InitStateReal(CLzmaDec * p)715 static void LzmaDec_InitStateReal(CLzmaDec *p)
716 {
717 UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (p->prop.lc + p->prop.lp));
718 UInt32 i;
719 CLzmaProb *probs = p->probs;
720 for (i = 0; i < numProbs; i++)
721 probs[i] = kBitModelTotal >> 1;
722 p->reps[0] = p->reps[1] = p->reps[2] = p->reps[3] = 1;
723 p->state = 0;
724 p->needInitState = 0;
725 }
726
LzmaDec_DecodeToDic(CLzmaDec * p,SizeT dicLimit,const Byte * src,SizeT * srcLen,ELzmaFinishMode finishMode,ELzmaStatus * status)727 SRes LzmaDec_DecodeToDic(CLzmaDec *p, SizeT dicLimit, const Byte *src, SizeT *srcLen,
728 ELzmaFinishMode finishMode, ELzmaStatus *status)
729 {
730 SizeT inSize = *srcLen;
731 (*srcLen) = 0;
732 LzmaDec_WriteRem(p, dicLimit);
733
734 *status = LZMA_STATUS_NOT_SPECIFIED;
735
736 while (p->remainLen != kMatchSpecLenStart)
737 {
738 int checkEndMarkNow;
739
740 if (p->needFlush != 0)
741 {
742 for (; inSize > 0 && p->tempBufSize < RC_INIT_SIZE; (*srcLen)++, inSize--)
743 p->tempBuf[p->tempBufSize++] = *src++;
744 if (p->tempBufSize < RC_INIT_SIZE)
745 {
746 *status = LZMA_STATUS_NEEDS_MORE_INPUT;
747 return SZ_OK;
748 }
749 if (p->tempBuf[0] != 0)
750 return SZ_ERROR_DATA;
751
752 LzmaDec_InitRc(p, p->tempBuf);
753 p->tempBufSize = 0;
754 }
755
756 checkEndMarkNow = 0;
757 if (p->dicPos >= dicLimit)
758 {
759 if (p->remainLen == 0 && p->code == 0)
760 {
761 *status = LZMA_STATUS_MAYBE_FINISHED_WITHOUT_MARK;
762 return SZ_OK;
763 }
764 if (finishMode == LZMA_FINISH_ANY)
765 {
766 *status = LZMA_STATUS_NOT_FINISHED;
767 return SZ_OK;
768 }
769 if (p->remainLen != 0)
770 {
771 *status = LZMA_STATUS_NOT_FINISHED;
772 return SZ_ERROR_DATA;
773 }
774 checkEndMarkNow = 1;
775 }
776
777 if (p->needInitState)
778 LzmaDec_InitStateReal(p);
779
780 if (p->tempBufSize == 0)
781 {
782 SizeT processed;
783 const Byte *bufLimit;
784 if (inSize < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
785 {
786 int dummyRes = LzmaDec_TryDummy(p, src, inSize);
787 if (dummyRes == DUMMY_ERROR)
788 {
789 memcpy(p->tempBuf, src, inSize);
790 p->tempBufSize = (unsigned)inSize;
791 (*srcLen) += inSize;
792 *status = LZMA_STATUS_NEEDS_MORE_INPUT;
793 return SZ_OK;
794 }
795 if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
796 {
797 *status = LZMA_STATUS_NOT_FINISHED;
798 return SZ_ERROR_DATA;
799 }
800 bufLimit = src;
801 }
802 else
803 bufLimit = src + inSize - LZMA_REQUIRED_INPUT_MAX;
804 p->buf = src;
805 if (LzmaDec_DecodeReal2(p, dicLimit, bufLimit) != 0)
806 return SZ_ERROR_DATA;
807 processed = (SizeT)(p->buf - src);
808 (*srcLen) += processed;
809 src += processed;
810 inSize -= processed;
811 }
812 else
813 {
814 unsigned rem = p->tempBufSize, lookAhead = 0;
815 while (rem < LZMA_REQUIRED_INPUT_MAX && lookAhead < inSize)
816 p->tempBuf[rem++] = src[lookAhead++];
817 p->tempBufSize = rem;
818 if (rem < LZMA_REQUIRED_INPUT_MAX || checkEndMarkNow)
819 {
820 int dummyRes = LzmaDec_TryDummy(p, p->tempBuf, rem);
821 if (dummyRes == DUMMY_ERROR)
822 {
823 (*srcLen) += lookAhead;
824 *status = LZMA_STATUS_NEEDS_MORE_INPUT;
825 return SZ_OK;
826 }
827 if (checkEndMarkNow && dummyRes != DUMMY_MATCH)
828 {
829 *status = LZMA_STATUS_NOT_FINISHED;
830 return SZ_ERROR_DATA;
831 }
832 }
833 p->buf = p->tempBuf;
834 if (LzmaDec_DecodeReal2(p, dicLimit, p->buf) != 0)
835 return SZ_ERROR_DATA;
836 lookAhead -= (rem - (unsigned)(p->buf - p->tempBuf));
837 (*srcLen) += lookAhead;
838 src += lookAhead;
839 inSize -= lookAhead;
840 p->tempBufSize = 0;
841 }
842 }
843 if (p->code == 0)
844 *status = LZMA_STATUS_FINISHED_WITH_MARK;
845 return (p->code == 0) ? SZ_OK : SZ_ERROR_DATA;
846 }
847
LzmaDec_DecodeToBuf(CLzmaDec * p,Byte * dest,SizeT * destLen,const Byte * src,SizeT * srcLen,ELzmaFinishMode finishMode,ELzmaStatus * status)848 SRes LzmaDec_DecodeToBuf(CLzmaDec *p, Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen, ELzmaFinishMode finishMode, ELzmaStatus *status)
849 {
850 SizeT outSize = *destLen;
851 SizeT inSize = *srcLen;
852 *srcLen = *destLen = 0;
853 for (;;)
854 {
855 SizeT inSizeCur = inSize, outSizeCur, dicPos;
856 ELzmaFinishMode curFinishMode;
857 SRes res;
858 if (p->dicPos == p->dicBufSize)
859 p->dicPos = 0;
860 dicPos = p->dicPos;
861 if (outSize > p->dicBufSize - dicPos)
862 {
863 outSizeCur = p->dicBufSize;
864 curFinishMode = LZMA_FINISH_ANY;
865 }
866 else
867 {
868 outSizeCur = dicPos + outSize;
869 curFinishMode = finishMode;
870 }
871
872 res = LzmaDec_DecodeToDic(p, outSizeCur, src, &inSizeCur, curFinishMode, status);
873 src += inSizeCur;
874 inSize -= inSizeCur;
875 *srcLen += inSizeCur;
876 outSizeCur = p->dicPos - dicPos;
877 memcpy(dest, p->dic + dicPos, outSizeCur);
878 dest += outSizeCur;
879 outSize -= outSizeCur;
880 *destLen += outSizeCur;
881 if (res != 0)
882 return res;
883 if (outSizeCur == 0 || outSize == 0)
884 return SZ_OK;
885 }
886 }
887
LzmaDec_FreeProbs(CLzmaDec * p,ISzAlloc * alloc)888 void LzmaDec_FreeProbs(CLzmaDec *p, ISzAlloc *alloc)
889 {
890 alloc->Free(alloc, p->probs);
891 p->probs = 0;
892 }
893
LzmaDec_FreeDict(CLzmaDec * p,ISzAlloc * alloc)894 static void LzmaDec_FreeDict(CLzmaDec *p, ISzAlloc *alloc)
895 {
896 alloc->Free(alloc, p->dic);
897 p->dic = 0;
898 }
899
LzmaDec_Free(CLzmaDec * p,ISzAlloc * alloc)900 void LzmaDec_Free(CLzmaDec *p, ISzAlloc *alloc)
901 {
902 LzmaDec_FreeProbs(p, alloc);
903 LzmaDec_FreeDict(p, alloc);
904 }
905
LzmaProps_Decode(CLzmaProps * p,const Byte * data,unsigned size)906 SRes LzmaProps_Decode(CLzmaProps *p, const Byte *data, unsigned size)
907 {
908 UInt32 dicSize;
909 Byte d;
910
911 if (size < LZMA_PROPS_SIZE)
912 return SZ_ERROR_UNSUPPORTED;
913 else
914 dicSize = data[1] | ((UInt32)data[2] << 8) | ((UInt32)data[3] << 16) | ((UInt32)data[4] << 24);
915
916 if (dicSize < LZMA_DIC_MIN)
917 dicSize = LZMA_DIC_MIN;
918 p->dicSize = dicSize;
919
920 d = data[0];
921 if (d >= (9 * 5 * 5))
922 return SZ_ERROR_UNSUPPORTED;
923
924 p->lc = d % 9;
925 d /= 9;
926 p->pb = d / 5;
927 p->lp = d % 5;
928
929 return SZ_OK;
930 }
931
LzmaDec_AllocateProbs2(CLzmaDec * p,const CLzmaProps * propNew,ISzAlloc * alloc)932 static SRes LzmaDec_AllocateProbs2(CLzmaDec *p, const CLzmaProps *propNew, ISzAlloc *alloc)
933 {
934 UInt32 numProbs = LzmaProps_GetNumProbs(propNew);
935 if (p->probs == 0 || numProbs != p->numProbs)
936 {
937 LzmaDec_FreeProbs(p, alloc);
938 p->probs = (CLzmaProb *)alloc->Alloc(alloc, numProbs * sizeof(CLzmaProb));
939 p->numProbs = numProbs;
940 if (p->probs == 0)
941 return SZ_ERROR_MEM;
942 }
943 return SZ_OK;
944 }
945
LzmaDec_AllocateProbs(CLzmaDec * p,const Byte * props,unsigned propsSize,ISzAlloc * alloc)946 SRes LzmaDec_AllocateProbs(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
947 {
948 CLzmaProps propNew;
949 RINOK(LzmaProps_Decode(&propNew, props, propsSize));
950 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
951 p->prop = propNew;
952 return SZ_OK;
953 }
954
LzmaDec_Allocate(CLzmaDec * p,const Byte * props,unsigned propsSize,ISzAlloc * alloc)955 SRes LzmaDec_Allocate(CLzmaDec *p, const Byte *props, unsigned propsSize, ISzAlloc *alloc)
956 {
957 CLzmaProps propNew;
958 SizeT dicBufSize;
959 RINOK(LzmaProps_Decode(&propNew, props, propsSize));
960 RINOK(LzmaDec_AllocateProbs2(p, &propNew, alloc));
961 dicBufSize = propNew.dicSize;
962 if (p->dic == 0 || dicBufSize != p->dicBufSize)
963 {
964 LzmaDec_FreeDict(p, alloc);
965 p->dic = (Byte *)alloc->Alloc(alloc, dicBufSize);
966 if (p->dic == 0)
967 {
968 LzmaDec_FreeProbs(p, alloc);
969 return SZ_ERROR_MEM;
970 }
971 }
972 p->dicBufSize = dicBufSize;
973 p->prop = propNew;
974 return SZ_OK;
975 }
976
LzmaDecode(Byte * dest,SizeT * destLen,const Byte * src,SizeT * srcLen,const Byte * propData,unsigned propSize,ELzmaFinishMode finishMode,ELzmaStatus * status,ISzAlloc * alloc)977 SRes LzmaDecode(Byte *dest, SizeT *destLen, const Byte *src, SizeT *srcLen,
978 const Byte *propData, unsigned propSize, ELzmaFinishMode finishMode,
979 ELzmaStatus *status, ISzAlloc *alloc)
980 {
981 CLzmaDec p;
982 SRes res;
983 SizeT inSize = *srcLen;
984 SizeT outSize = *destLen;
985 *srcLen = *destLen = 0;
986 if (inSize < RC_INIT_SIZE)
987 return SZ_ERROR_INPUT_EOF;
988
989 LzmaDec_Construct(&p);
990 res = LzmaDec_AllocateProbs(&p, propData, propSize, alloc);
991 if (res != 0)
992 return res;
993 p.dic = dest;
994 p.dicBufSize = outSize;
995
996 LzmaDec_Init(&p);
997
998 *srcLen = inSize;
999 res = LzmaDec_DecodeToDic(&p, outSize, src, srcLen, finishMode, status);
1000
1001 if (res == SZ_OK && *status == LZMA_STATUS_NEEDS_MORE_INPUT)
1002 res = SZ_ERROR_INPUT_EOF;
1003
1004 (*destLen) = p.dicPos;
1005 LzmaDec_FreeProbs(&p, alloc);
1006 return res;
1007 }
1008