Debian Codegraph @

src/lzma/LzmaDec.c

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