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