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