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