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