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