1 /* -*- mode: C; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: expandtab:ts=8:sw=4:softtabstop=4:
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file lzma_decoder.c
6 /// \brief LZMA decoder
7 ///
8 // Authors: Igor Pavlov
9 // Lasse Collin
10 //
11 // This file has been put into the public domain.
12 // You can do whatever you want with this file.
13 //
14 ///////////////////////////////////////////////////////////////////////////////
15
16 #include "lz_decoder.h"
17 #include "lzma_common.h"
18 #include "lzma_decoder.h"
19 #include "range_decoder.h"
20
21
22 #ifdef HAVE_SMALL
23
24 // Macros for (somewhat) size-optimized code.
25 #define seq_4(seq) seq
26
27 #define seq_6(seq) seq
28
29 #define seq_8(seq) seq
30
31 #define seq_len(seq) \
32 seq ## _CHOICE, \
33 seq ## _CHOICE2, \
34 seq ## _BITTREE
35
36 #define len_decode(target, ld, pos_state, seq) \
37 do { \
38 case seq ## _CHOICE: \
39 rc_if_0(ld.choice, seq ## _CHOICE) { \
40 rc_update_0(ld.choice); \
41 probs = ld.low[pos_state];\
42 limit = LEN_LOW_SYMBOLS; \
43 target = MATCH_LEN_MIN; \
44 } else { \
45 rc_update_1(ld.choice); \
46 case seq ## _CHOICE2: \
47 rc_if_0(ld.choice2, seq ## _CHOICE2) { \
48 rc_update_0(ld.choice2); \
49 probs = ld.mid[pos_state]; \
50 limit = LEN_MID_SYMBOLS; \
51 target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \
52 } else { \
53 rc_update_1(ld.choice2); \
54 probs = ld.high; \
55 limit = LEN_HIGH_SYMBOLS; \
56 target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS \
57 + LEN_MID_SYMBOLS; \
58 } \
59 } \
60 symbol = 1; \
61 case seq ## _BITTREE: \
62 do { \
63 rc_bit(probs[symbol], , , seq ## _BITTREE); \
64 } while (symbol < limit); \
65 target += symbol - limit; \
66 } while (0)
67
68 #else // HAVE_SMALL
69
70 // Unrolled versions
71 #define seq_4(seq) \
72 seq ## 0, \
73 seq ## 1, \
74 seq ## 2, \
75 seq ## 3
76
77 #define seq_6(seq) \
78 seq ## 0, \
79 seq ## 1, \
80 seq ## 2, \
81 seq ## 3, \
82 seq ## 4, \
83 seq ## 5
84
85 #define seq_8(seq) \
86 seq ## 0, \
87 seq ## 1, \
88 seq ## 2, \
89 seq ## 3, \
90 seq ## 4, \
91 seq ## 5, \
92 seq ## 6, \
93 seq ## 7
94
95 #define seq_len(seq) \
96 seq ## _CHOICE, \
97 seq ## _LOW0, \
98 seq ## _LOW1, \
99 seq ## _LOW2, \
100 seq ## _CHOICE2, \
101 seq ## _MID0, \
102 seq ## _MID1, \
103 seq ## _MID2, \
104 seq ## _HIGH0, \
105 seq ## _HIGH1, \
106 seq ## _HIGH2, \
107 seq ## _HIGH3, \
108 seq ## _HIGH4, \
109 seq ## _HIGH5, \
110 seq ## _HIGH6, \
111 seq ## _HIGH7
112
113 #define len_decode(target, ld, pos_state, seq) \
114 do { \
115 symbol = 1; \
116 case seq ## _CHOICE: \
117 rc_if_0(ld.choice, seq ## _CHOICE) { \
118 rc_update_0(ld.choice); \
119 rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW0); \
120 rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW1); \
121 rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW2); \
122 target = symbol - LEN_LOW_SYMBOLS + MATCH_LEN_MIN; \
123 } else { \
124 rc_update_1(ld.choice); \
125 case seq ## _CHOICE2: \
126 rc_if_0(ld.choice2, seq ## _CHOICE2) { \
127 rc_update_0(ld.choice2); \
128 rc_bit_case(ld.mid[pos_state][symbol], , , \
129 seq ## _MID0); \
130 rc_bit_case(ld.mid[pos_state][symbol], , , \
131 seq ## _MID1); \
132 rc_bit_case(ld.mid[pos_state][symbol], , , \
133 seq ## _MID2); \
134 target = symbol - LEN_MID_SYMBOLS \
135 + MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \
136 } else { \
137 rc_update_1(ld.choice2); \
138 rc_bit_case(ld.high[symbol], , , seq ## _HIGH0); \
139 rc_bit_case(ld.high[symbol], , , seq ## _HIGH1); \
140 rc_bit_case(ld.high[symbol], , , seq ## _HIGH2); \
141 rc_bit_case(ld.high[symbol], , , seq ## _HIGH3); \
142 rc_bit_case(ld.high[symbol], , , seq ## _HIGH4); \
143 rc_bit_case(ld.high[symbol], , , seq ## _HIGH5); \
144 rc_bit_case(ld.high[symbol], , , seq ## _HIGH6); \
145 rc_bit_case(ld.high[symbol], , , seq ## _HIGH7); \
146 target = symbol - LEN_HIGH_SYMBOLS \
147 + MATCH_LEN_MIN \
148 + LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \
149 } \
150 } \
151 } while (0)
152
153 #endif // HAVE_SMALL
154
155
156 /// Length decoder probabilities; see comments in lzma_common.h.
157 typedef struct {
158 probability choice;
159 probability choice2;
160 probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
161 probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
162 probability high[LEN_HIGH_SYMBOLS];
163 } lzma_length_decoder;
164
165
166 struct lzma_coder_s {
167 ///////////////////
168 // Probabilities //
169 ///////////////////
170
171 /// Literals; see comments in lzma_common.h.
172 probability literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE];
173
174 /// If 1, it's a match. Otherwise it's a single 8-bit literal.
175 probability is_match[STATES][POS_STATES_MAX];
176
177 /// If 1, it's a repeated match. The distance is one of rep0 .. rep3.
178 probability is_rep[STATES];
179
180 /// If 0, distance of a repeated match is rep0.
181 /// Otherwise check is_rep1.
182 probability is_rep0[STATES];
183
184 /// If 0, distance of a repeated match is rep1.
185 /// Otherwise check is_rep2.
186 probability is_rep1[STATES];
187
188 /// If 0, distance of a repeated match is rep2. Otherwise it is rep3.
189 probability is_rep2[STATES];
190
191 /// If 1, the repeated match has length of one byte. Otherwise
192 /// the length is decoded from rep_len_decoder.
193 probability is_rep0_long[STATES][POS_STATES_MAX];
194
195 /// Probability tree for the highest two bits of the match distance.
196 /// There is a separate probability tree for match lengths of
197 /// 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
198 probability pos_slot[LEN_TO_POS_STATES][POS_SLOTS];
199
200 /// Probility trees for additional bits for match distance when the
201 /// distance is in the range [4, 127].
202 probability pos_special[FULL_DISTANCES - END_POS_MODEL_INDEX];
203
204 /// Probability tree for the lowest four bits of a match distance
205 /// that is equal to or greater than 128.
206 probability pos_align[ALIGN_TABLE_SIZE];
207
208 /// Length of a normal match
209 lzma_length_decoder match_len_decoder;
210
211 /// Length of a repeated match
212 lzma_length_decoder rep_len_decoder;
213
214 ///////////////////
215 // Decoder state //
216 ///////////////////
217
218 // Range coder
219 lzma_range_decoder rc;
220
221 // Types of the most recently seen LZMA symbols
222 lzma_lzma_state state;
223
224 uint32_t rep0; ///< Distance of the latest match
225 uint32_t rep1; ///< Distance of second latest match
226 uint32_t rep2; ///< Distance of third latest match
227 uint32_t rep3; ///< Distance of fourth latest match
228
229 uint32_t pos_mask; // (1U << pb) - 1
230 uint32_t literal_context_bits;
231 uint32_t literal_pos_mask;
232
233 /// Uncompressed size as bytes, or LZMA_VLI_UNKNOWN if end of
234 /// payload marker is expected.
235 lzma_vli uncompressed_size;
236
237 ////////////////////////////////
238 // State of incomplete symbol //
239 ////////////////////////////////
240
241 /// Position where to continue the decoder loop
242 enum {
243 SEQ_NORMALIZE,
244 SEQ_IS_MATCH,
245 seq_8(SEQ_LITERAL),
246 seq_8(SEQ_LITERAL_MATCHED),
247 SEQ_LITERAL_WRITE,
248 SEQ_IS_REP,
249 seq_len(SEQ_MATCH_LEN),
250 seq_6(SEQ_POS_SLOT),
251 SEQ_POS_MODEL,
252 SEQ_DIRECT,
253 seq_4(SEQ_ALIGN),
254 SEQ_EOPM,
255 SEQ_IS_REP0,
256 SEQ_SHORTREP,
257 SEQ_IS_REP0_LONG,
258 SEQ_IS_REP1,
259 SEQ_IS_REP2,
260 seq_len(SEQ_REP_LEN),
261 SEQ_COPY,
262 } sequence;
263
264 /// Base of the current probability tree
265 probability *probs;
266
267 /// Symbol being decoded. This is also used as an index variable in
268 /// bittree decoders: probs[symbol]
269 uint32_t symbol;
270
271 /// Used as a loop termination condition on bittree decoders and
272 /// direct bits decoder.
273 uint32_t limit;
274
275 /// Matched literal decoder: 0x100 or 0 to help avoiding branches.
276 /// Bittree reverse decoders: Offset of the next bit: 1 << offset
277 uint32_t offset;
278
279 /// If decoding a literal: match byte.
280 /// If decoding a match: length of the match.
281 uint32_t len;
282 };
283
284
285 static lzma_ret
lzma_decode(lzma_coder * restrict coder,lzma_dict * restrict dictptr,const uint8_t * restrict in,size_t * restrict in_pos,size_t in_size)286 lzma_decode(lzma_coder *restrict coder, lzma_dict *restrict dictptr,
287 const uint8_t *restrict in,
288 size_t *restrict in_pos, size_t in_size)
289 {
290 ////////////////////
291 // Initialization //
292 ////////////////////
293
294 if (!rc_read_init(&coder->rc, in, in_pos, in_size))
295 return LZMA_OK;
296
297 ///////////////
298 // Variables //
299 ///////////////
300
301 // Making local copies of often-used variables improves both
302 // speed and readability.
303
304 lzma_dict dict = *dictptr;
305
306 const size_t dict_start = dict.pos;
307
308 // Range decoder
309 rc_to_local(coder->rc, *in_pos);
310
311 // State
312 uint32_t state = coder->state;
313 uint32_t rep0 = coder->rep0;
314 uint32_t rep1 = coder->rep1;
315 uint32_t rep2 = coder->rep2;
316 uint32_t rep3 = coder->rep3;
317
318 const uint32_t pos_mask = coder->pos_mask;
319
320 // These variables are actually needed only if we last time ran
321 // out of input in the middle of the decoder loop.
322 probability *probs = coder->probs;
323 uint32_t symbol = coder->symbol;
324 uint32_t limit = coder->limit;
325 uint32_t offset = coder->offset;
326 uint32_t len = coder->len;
327
328 const uint32_t literal_pos_mask = coder->literal_pos_mask;
329 const uint32_t literal_context_bits = coder->literal_context_bits;
330
331 // Temporary variables
332 uint32_t pos_state = dict.pos & pos_mask;
333
334 lzma_ret ret = LZMA_OK;
335
336 // If uncompressed size is known, there must be no end of payload
337 // marker.
338 const bool no_eopm = coder->uncompressed_size
339 != LZMA_VLI_UNKNOWN;
340 if (no_eopm && coder->uncompressed_size < dict.limit - dict.pos)
341 dict.limit = dict.pos + (size_t)(coder->uncompressed_size);
342
343 // The main decoder loop. The "switch" is used to restart the decoder at
344 // correct location. Once restarted, the "switch" is no longer used.
345 switch (coder->sequence)
346 while (true) {
347 // Calculate new pos_state. This is skipped on the first loop
348 // since we already calculated it when setting up the local
349 // variables.
350 pos_state = dict.pos & pos_mask;
351
352 case SEQ_NORMALIZE:
353 case SEQ_IS_MATCH:
354 if (unlikely(no_eopm && dict.pos == dict.limit))
355 break;
356
357 rc_if_0(coder->is_match[state][pos_state], SEQ_IS_MATCH) {
358 rc_update_0(coder->is_match[state][pos_state]);
359
360 // It's a literal i.e. a single 8-bit byte.
361
362 probs = literal_subcoder(coder->literal,
363 literal_context_bits, literal_pos_mask,
364 dict.pos, dict_get(&dict, 0));
365 symbol = 1;
366
367 if (is_literal_state(state)) {
368 // Decode literal without match byte.
369 #ifdef HAVE_SMALL
370 case SEQ_LITERAL:
371 do {
372 rc_bit(probs[symbol], , , SEQ_LITERAL);
373 } while (symbol < (1 << 8));
374 #else
375 rc_bit_case(probs[symbol], , , SEQ_LITERAL0);
376 rc_bit_case(probs[symbol], , , SEQ_LITERAL1);
377 rc_bit_case(probs[symbol], , , SEQ_LITERAL2);
378 rc_bit_case(probs[symbol], , , SEQ_LITERAL3);
379 rc_bit_case(probs[symbol], , , SEQ_LITERAL4);
380 rc_bit_case(probs[symbol], , , SEQ_LITERAL5);
381 rc_bit_case(probs[symbol], , , SEQ_LITERAL6);
382 rc_bit_case(probs[symbol], , , SEQ_LITERAL7);
383 #endif
384 } else {
385 // Decode literal with match byte.
386 //
387 // We store the byte we compare against
388 // ("match byte") to "len" to minimize the
389 // number of variables we need to store
390 // between decoder calls.
391 len = dict_get(&dict, rep0) << 1;
392
393 // The usage of "offset" allows omitting some
394 // branches, which should give tiny speed
395 // improvement on some CPUs. "offset" gets
396 // set to zero if match_bit didn't match.
397 offset = 0x100;
398
399 #ifdef HAVE_SMALL
400 case SEQ_LITERAL_MATCHED:
401 do {
402 const uint32_t match_bit
403 = len & offset;
404 const uint32_t subcoder_index
405 = offset + match_bit
406 + symbol;
407
408 rc_bit(probs[subcoder_index],
409 offset &= ~match_bit,
410 offset &= match_bit,
411 SEQ_LITERAL_MATCHED);
412
413 // It seems to be faster to do this
414 // here instead of putting it to the
415 // beginning of the loop and then
416 // putting the "case" in the middle
417 // of the loop.
418 len <<= 1;
419
420 } while (symbol < (1 << 8));
421 #else
422 // Unroll the loop.
423 uint32_t match_bit;
424 uint32_t subcoder_index;
425
426 # define d(seq) \
427 case seq: \
428 match_bit = len & offset; \
429 subcoder_index = offset + match_bit + symbol; \
430 rc_bit(probs[subcoder_index], \
431 offset &= ~match_bit, \
432 offset &= match_bit, \
433 seq)
434
435 d(SEQ_LITERAL_MATCHED0);
436 len <<= 1;
437 d(SEQ_LITERAL_MATCHED1);
438 len <<= 1;
439 d(SEQ_LITERAL_MATCHED2);
440 len <<= 1;
441 d(SEQ_LITERAL_MATCHED3);
442 len <<= 1;
443 d(SEQ_LITERAL_MATCHED4);
444 len <<= 1;
445 d(SEQ_LITERAL_MATCHED5);
446 len <<= 1;
447 d(SEQ_LITERAL_MATCHED6);
448 len <<= 1;
449 d(SEQ_LITERAL_MATCHED7);
450 # undef d
451 #endif
452 }
453
454 //update_literal(state);
455 // Use a lookup table to update to literal state,
456 // since compared to other state updates, this would
457 // need two branches.
458 static const lzma_lzma_state next_state[] = {
459 STATE_LIT_LIT,
460 STATE_LIT_LIT,
461 STATE_LIT_LIT,
462 STATE_LIT_LIT,
463 STATE_MATCH_LIT_LIT,
464 STATE_REP_LIT_LIT,
465 STATE_SHORTREP_LIT_LIT,
466 STATE_MATCH_LIT,
467 STATE_REP_LIT,
468 STATE_SHORTREP_LIT,
469 STATE_MATCH_LIT,
470 STATE_REP_LIT
471 };
472 state = next_state[state];
473
474 case SEQ_LITERAL_WRITE:
475 if (unlikely(dict_put(&dict, symbol))) {
476 coder->sequence = SEQ_LITERAL_WRITE;
477 goto out;
478 }
479
480 continue;
481 }
482
483 // Instead of a new byte we are going to get a byte range
484 // (distance and length) which will be repeated from our
485 // output history.
486
487 rc_update_1(coder->is_match[state][pos_state]);
488
489 case SEQ_IS_REP:
490 rc_if_0(coder->is_rep[state], SEQ_IS_REP) {
491 // Not a repeated match
492 rc_update_0(coder->is_rep[state]);
493 update_match(state);
494
495 // The latest three match distances are kept in
496 // memory in case there are repeated matches.
497 rep3 = rep2;
498 rep2 = rep1;
499 rep1 = rep0;
500
501 // Decode the length of the match.
502 len_decode(len, coder->match_len_decoder,
503 pos_state, SEQ_MATCH_LEN);
504
505 // Prepare to decode the highest two bits of the
506 // match distance.
507 probs = coder->pos_slot[get_len_to_pos_state(len)];
508 symbol = 1;
509
510 #ifdef HAVE_SMALL
511 case SEQ_POS_SLOT:
512 do {
513 rc_bit(probs[symbol], , , SEQ_POS_SLOT);
514 } while (symbol < POS_SLOTS);
515 #else
516 rc_bit_case(probs[symbol], , , SEQ_POS_SLOT0);
517 rc_bit_case(probs[symbol], , , SEQ_POS_SLOT1);
518 rc_bit_case(probs[symbol], , , SEQ_POS_SLOT2);
519 rc_bit_case(probs[symbol], , , SEQ_POS_SLOT3);
520 rc_bit_case(probs[symbol], , , SEQ_POS_SLOT4);
521 rc_bit_case(probs[symbol], , , SEQ_POS_SLOT5);
522 #endif
523 // Get rid of the highest bit that was needed for
524 // indexing of the probability array.
525 symbol -= POS_SLOTS;
526 assert(symbol <= 63);
527
528 if (symbol < START_POS_MODEL_INDEX) {
529 // Match distances [0, 3] have only two bits.
530 rep0 = symbol;
531 } else {
532 // Decode the lowest [1, 29] bits of
533 // the match distance.
534 limit = (symbol >> 1) - 1;
535 assert(limit >= 1 && limit <= 30);
536 rep0 = 2 + (symbol & 1);
537
538 if (symbol < END_POS_MODEL_INDEX) {
539 // Prepare to decode the low bits for
540 // a distance of [4, 127].
541 assert(limit <= 5);
542 rep0 <<= limit;
543 assert(rep0 <= 96);
544 // -1 is fine, because we start
545 // decoding at probs[1], not probs[0].
546 // NOTE: This violates the C standard,
547 // since we are doing pointer
548 // arithmetic past the beginning of
549 // the array.
550 assert((int32_t)(rep0 - symbol - 1)
551 >= -1);
552 assert((int32_t)(rep0 - symbol - 1)
553 <= 82);
554 probs = coder->pos_special + rep0
555 - symbol - 1;
556 symbol = 1;
557 offset = 0;
558 case SEQ_POS_MODEL:
559 #ifdef HAVE_SMALL
560 do {
561 rc_bit(probs[symbol], ,
562 rep0 += 1 << offset,
563 SEQ_POS_MODEL);
564 } while (++offset < limit);
565 #else
566 switch (limit) {
567 case 5:
568 assert(offset == 0);
569 rc_bit(probs[symbol], ,
570 rep0 += 1,
571 SEQ_POS_MODEL);
572 ++offset;
573 --limit;
574 case 4:
575 rc_bit(probs[symbol], ,
576 rep0 += 1 << offset,
577 SEQ_POS_MODEL);
578 ++offset;
579 --limit;
580 case 3:
581 rc_bit(probs[symbol], ,
582 rep0 += 1 << offset,
583 SEQ_POS_MODEL);
584 ++offset;
585 --limit;
586 case 2:
587 rc_bit(probs[symbol], ,
588 rep0 += 1 << offset,
589 SEQ_POS_MODEL);
590 ++offset;
591 --limit;
592 case 1:
593 // We need "symbol" only for
594 // indexing the probability
595 // array, thus we can use
596 // rc_bit_last() here to omit
597 // the unneeded updating of
598 // "symbol".
599 rc_bit_last(probs[symbol], ,
600 rep0 += 1 << offset,
601 SEQ_POS_MODEL);
602 }
603 #endif
604 } else {
605 // The distace is >= 128. Decode the
606 // lower bits without probabilities
607 // except the lowest four bits.
608 assert(symbol >= 14);
609 assert(limit >= 6);
610 limit -= ALIGN_BITS;
611 assert(limit >= 2);
612 case SEQ_DIRECT:
613 // Not worth manual unrolling
614 do {
615 rc_direct(rep0, SEQ_DIRECT);
616 } while (--limit > 0);
617
618 // Decode the lowest four bits using
619 // probabilities.
620 rep0 <<= ALIGN_BITS;
621 symbol = 1;
622 #ifdef HAVE_SMALL
623 offset = 0;
624 case SEQ_ALIGN:
625 do {
626 rc_bit(coder->pos_align[
627 symbol], ,
628 rep0 += 1 << offset,
629 SEQ_ALIGN);
630 } while (++offset < ALIGN_BITS);
631 #else
632 case SEQ_ALIGN0:
633 rc_bit(coder->pos_align[symbol], ,
634 rep0 += 1, SEQ_ALIGN0);
635 case SEQ_ALIGN1:
636 rc_bit(coder->pos_align[symbol], ,
637 rep0 += 2, SEQ_ALIGN1);
638 case SEQ_ALIGN2:
639 rc_bit(coder->pos_align[symbol], ,
640 rep0 += 4, SEQ_ALIGN2);
641 case SEQ_ALIGN3:
642 // Like in SEQ_POS_MODEL, we don't
643 // need "symbol" for anything else
644 // than indexing the probability array.
645 rc_bit_last(coder->pos_align[symbol], ,
646 rep0 += 8, SEQ_ALIGN3);
647 #endif
648
649 if (rep0 == UINT32_MAX) {
650 // End of payload marker was
651 // found. It must not be
652 // present if uncompressed
653 // size is known.
654 if (coder->uncompressed_size
655 != LZMA_VLI_UNKNOWN) {
656 ret = LZMA_DATA_ERROR;
657 goto out;
658 }
659
660 case SEQ_EOPM:
661 // TODO Comment
662 rc_normalize(SEQ_EOPM);
663 ret = LZMA_STREAM_END;
664 goto out;
665 }
666 }
667 }
668
669 // Validate the distance we just decoded.
670 if (unlikely(!dict_is_distance_valid(&dict, rep0))) {
671 ret = LZMA_DATA_ERROR;
672 goto out;
673 }
674
675 } else {
676 rc_update_1(coder->is_rep[state]);
677
678 // Repeated match
679 //
680 // The match distance is a value that we have had
681 // earlier. The latest four match distances are
682 // available as rep0, rep1, rep2 and rep3. We will
683 // now decode which of them is the new distance.
684 //
685 // There cannot be a match if we haven't produced
686 // any output, so check that first.
687 if (unlikely(!dict_is_distance_valid(&dict, 0))) {
688 ret = LZMA_DATA_ERROR;
689 goto out;
690 }
691
692 case SEQ_IS_REP0:
693 rc_if_0(coder->is_rep0[state], SEQ_IS_REP0) {
694 rc_update_0(coder->is_rep0[state]);
695 // The distance is rep0.
696
697 case SEQ_IS_REP0_LONG:
698 rc_if_0(coder->is_rep0_long[state][pos_state],
699 SEQ_IS_REP0_LONG) {
700 rc_update_0(coder->is_rep0_long[
701 state][pos_state]);
702
703 update_short_rep(state);
704
705 case SEQ_SHORTREP:
706 if (unlikely(dict_put(&dict, dict_get(
707 &dict, rep0)))) {
708 coder->sequence = SEQ_SHORTREP;
709 goto out;
710 }
711
712 continue;
713 }
714
715 // Repeating more than one byte at
716 // distance of rep0.
717 rc_update_1(coder->is_rep0_long[
718 state][pos_state]);
719
720 } else {
721 rc_update_1(coder->is_rep0[state]);
722
723 case SEQ_IS_REP1:
724 // The distance is rep1, rep2 or rep3. Once
725 // we find out which one of these three, it
726 // is stored to rep0 and rep1, rep2 and rep3
727 // are updated accordingly.
728 rc_if_0(coder->is_rep1[state], SEQ_IS_REP1) {
729 rc_update_0(coder->is_rep1[state]);
730
731 const uint32_t distance = rep1;
732 rep1 = rep0;
733 rep0 = distance;
734
735 } else {
736 rc_update_1(coder->is_rep1[state]);
737 case SEQ_IS_REP2:
738 rc_if_0(coder->is_rep2[state],
739 SEQ_IS_REP2) {
740 rc_update_0(coder->is_rep2[
741 state]);
742
743 const uint32_t distance = rep2;
744 rep2 = rep1;
745 rep1 = rep0;
746 rep0 = distance;
747
748 } else {
749 rc_update_1(coder->is_rep2[
750 state]);
751
752 const uint32_t distance = rep3;
753 rep3 = rep2;
754 rep2 = rep1;
755 rep1 = rep0;
756 rep0 = distance;
757 }
758 }
759 }
760
761 update_long_rep(state);
762
763 // Decode the length of the repeated match.
764 len_decode(len, coder->rep_len_decoder,
765 pos_state, SEQ_REP_LEN);
766 }
767
768 /////////////////////////////////
769 // Repeat from history buffer. //
770 /////////////////////////////////
771
772 // The length is always between these limits. There is no way
773 // to trigger the algorithm to set len outside this range.
774 assert(len >= MATCH_LEN_MIN);
775 assert(len <= MATCH_LEN_MAX);
776
777 case SEQ_COPY:
778 // Repeat len bytes from distance of rep0.
779 if (unlikely(dict_repeat(&dict, rep0, &len))) {
780 coder->sequence = SEQ_COPY;
781 goto out;
782 }
783 }
784
785 rc_normalize(SEQ_NORMALIZE);
786 coder->sequence = SEQ_IS_MATCH;
787
788 out:
789 // Save state
790
791 // NOTE: Must not copy dict.limit.
792 dictptr->pos = dict.pos;
793 dictptr->full = dict.full;
794
795 rc_from_local(coder->rc, *in_pos);
796
797 coder->state = state;
798 coder->rep0 = rep0;
799 coder->rep1 = rep1;
800 coder->rep2 = rep2;
801 coder->rep3 = rep3;
802
803 coder->probs = probs;
804 coder->symbol = symbol;
805 coder->limit = limit;
806 coder->offset = offset;
807 coder->len = len;
808
809 // Update the remaining amount of uncompressed data if uncompressed
810 // size was known.
811 if (coder->uncompressed_size != LZMA_VLI_UNKNOWN) {
812 coder->uncompressed_size -= dict.pos - dict_start;
813
814 // Since there cannot be end of payload marker if the
815 // uncompressed size was known, we check here if we
816 // finished decoding.
817 if (coder->uncompressed_size == 0 && ret == LZMA_OK
818 && coder->sequence != SEQ_NORMALIZE)
819 ret = coder->sequence == SEQ_IS_MATCH
820 ? LZMA_STREAM_END : LZMA_DATA_ERROR;
821 }
822
823 // We can do an additional check in the range decoder to catch some
824 // corrupted files.
825 if (ret == LZMA_STREAM_END) {
826 if (!rc_is_finished(coder->rc))
827 ret = LZMA_DATA_ERROR;
828
829 // Reset the range decoder so that it is ready to reinitialize
830 // for a new LZMA2 chunk.
831 rc_reset(coder->rc);
832 }
833
834 return ret;
835 }
836
837
838
839 static void
lzma_decoder_uncompressed(lzma_coder * coder,lzma_vli uncompressed_size)840 lzma_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size)
841 {
842 coder->uncompressed_size = uncompressed_size;
843 }
844
845 /*
846 extern void
847 lzma_lzma_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size)
848 {
849 // This is hack.
850 (*(lzma_coder **)(coder))->uncompressed_size = uncompressed_size;
851 }
852 */
853
854 static void
lzma_decoder_reset(lzma_coder * coder,const void * opt)855 lzma_decoder_reset(lzma_coder *coder, const void *opt)
856 {
857 const lzma_options_lzma *options = opt;
858
859 // NOTE: We assume that lc/lp/pb are valid since they were
860 // successfully decoded with lzma_lzma_decode_properties().
861 // FIXME?
862
863 // Calculate pos_mask. We don't need pos_bits as is for anything.
864 coder->pos_mask = (1U << options->pb) - 1;
865
866 // Initialize the literal decoder.
867 literal_init(coder->literal, options->lc, options->lp);
868
869 coder->literal_context_bits = options->lc;
870 coder->literal_pos_mask = (1U << options->lp) - 1;
871
872 // State
873 coder->state = STATE_LIT_LIT;
874 coder->rep0 = 0;
875 coder->rep1 = 0;
876 coder->rep2 = 0;
877 coder->rep3 = 0;
878 coder->pos_mask = (1U << options->pb) - 1;
879
880 // Range decoder
881 rc_reset(coder->rc);
882
883 // Bit and bittree decoders
884 for (uint32_t i = 0; i < STATES; ++i) {
885 for (uint32_t j = 0; j <= coder->pos_mask; ++j) {
886 bit_reset(coder->is_match[i][j]);
887 bit_reset(coder->is_rep0_long[i][j]);
888 }
889
890 bit_reset(coder->is_rep[i]);
891 bit_reset(coder->is_rep0[i]);
892 bit_reset(coder->is_rep1[i]);
893 bit_reset(coder->is_rep2[i]);
894 }
895
896 for (uint32_t i = 0; i < LEN_TO_POS_STATES; ++i)
897 bittree_reset(coder->pos_slot[i], POS_SLOT_BITS);
898
899 for (uint32_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
900 bit_reset(coder->pos_special[i]);
901
902 bittree_reset(coder->pos_align, ALIGN_BITS);
903
904 // Len decoders (also bit/bittree)
905 const uint32_t num_pos_states = 1U << options->pb;
906 bit_reset(coder->match_len_decoder.choice);
907 bit_reset(coder->match_len_decoder.choice2);
908 bit_reset(coder->rep_len_decoder.choice);
909 bit_reset(coder->rep_len_decoder.choice2);
910
911 for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
912 bittree_reset(coder->match_len_decoder.low[pos_state],
913 LEN_LOW_BITS);
914 bittree_reset(coder->match_len_decoder.mid[pos_state],
915 LEN_MID_BITS);
916
917 bittree_reset(coder->rep_len_decoder.low[pos_state],
918 LEN_LOW_BITS);
919 bittree_reset(coder->rep_len_decoder.mid[pos_state],
920 LEN_MID_BITS);
921 }
922
923 bittree_reset(coder->match_len_decoder.high, LEN_HIGH_BITS);
924 bittree_reset(coder->rep_len_decoder.high, LEN_HIGH_BITS);
925
926 coder->sequence = SEQ_IS_MATCH;
927 coder->probs = NULL;
928 coder->symbol = 0;
929 coder->limit = 0;
930 coder->offset = 0;
931 coder->len = 0;
932
933 return;
934 }
935
936
937 extern lzma_ret
lzma_lzma_decoder_create(lzma_lz_decoder * lz,lzma_allocator * allocator,const void * opt,lzma_lz_options * lz_options)938 lzma_lzma_decoder_create(lzma_lz_decoder *lz, lzma_allocator *allocator,
939 const void *opt, lzma_lz_options *lz_options)
940 {
941 if (lz->coder == NULL) {
942 lz->coder = lzma_alloc(sizeof(lzma_coder), allocator);
943 if (lz->coder == NULL)
944 return LZMA_MEM_ERROR;
945
946 lz->code = &lzma_decode;
947 lz->reset = &lzma_decoder_reset;
948 lz->set_uncompressed = &lzma_decoder_uncompressed;
949 }
950
951 // All dictionary sizes are OK here. LZ decoder will take care of
952 // the special cases.
953 const lzma_options_lzma *options = opt;
954 lz_options->dict_size = options->dict_size;
955 lz_options->preset_dict = options->preset_dict;
956 lz_options->preset_dict_size = options->preset_dict_size;
957
958 return LZMA_OK;
959 }
960
961
962 /// Allocate and initialize LZMA decoder. This is used only via LZ
963 /// initialization (lzma_lzma_decoder_init() passes function pointer to
964 /// the LZ initialization).
965 static lzma_ret
lzma_decoder_init(lzma_lz_decoder * lz,lzma_allocator * allocator,const void * options,lzma_lz_options * lz_options)966 lzma_decoder_init(lzma_lz_decoder *lz, lzma_allocator *allocator,
967 const void *options, lzma_lz_options *lz_options)
968 {
969 if (!is_lclppb_valid(options))
970 return LZMA_PROG_ERROR;
971
972 return_if_error(lzma_lzma_decoder_create(
973 lz, allocator, options, lz_options));
974
975 lzma_decoder_reset(lz->coder, options);
976 lzma_decoder_uncompressed(lz->coder, LZMA_VLI_UNKNOWN);
977
978 return LZMA_OK;
979 }
980
981
982 extern lzma_ret
lzma_lzma_decoder_init(lzma_next_coder * next,lzma_allocator * allocator,const lzma_filter_info * filters)983 lzma_lzma_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
984 const lzma_filter_info *filters)
985 {
986 // LZMA can only be the last filter in the chain. This is enforced
987 // by the raw_decoder initialization.
988 assert(filters[1].init == NULL);
989
990 return lzma_lz_decoder_init(next, allocator, filters,
991 &lzma_decoder_init);
992 }
993
994
995 extern bool
lzma_lzma_lclppb_decode(lzma_options_lzma * options,uint8_t byte)996 lzma_lzma_lclppb_decode(lzma_options_lzma *options, uint8_t byte)
997 {
998 if (byte > (4 * 5 + 4) * 9 + 8)
999 return true;
1000
1001 // See the file format specification to understand this.
1002 options->pb = byte / (9 * 5);
1003 byte -= options->pb * 9 * 5;
1004 options->lp = byte / 9;
1005 options->lc = byte - options->lp * 9;
1006
1007 return options->lc + options->lp > LZMA_LCLP_MAX;
1008 }
1009
1010
1011 extern uint64_t
lzma_lzma_decoder_memusage_nocheck(const void * options)1012 lzma_lzma_decoder_memusage_nocheck(const void *options)
1013 {
1014 const lzma_options_lzma *const opt = options;
1015 return sizeof(lzma_coder) + lzma_lz_decoder_memusage(opt->dict_size);
1016 }
1017
1018
1019 extern uint64_t
lzma_lzma_decoder_memusage(const void * options)1020 lzma_lzma_decoder_memusage(const void *options)
1021 {
1022 if (!is_lclppb_valid(options))
1023 return UINT64_MAX;
1024
1025 return lzma_lzma_decoder_memusage_nocheck(options);
1026 }
1027
1028
1029 extern lzma_ret
lzma_lzma_props_decode(void ** options,lzma_allocator * allocator,const uint8_t * props,size_t props_size)1030 lzma_lzma_props_decode(void **options, lzma_allocator *allocator,
1031 const uint8_t *props, size_t props_size)
1032 {
1033 if (props_size != 5)
1034 return LZMA_OPTIONS_ERROR;
1035
1036 lzma_options_lzma *opt
1037 = lzma_alloc(sizeof(lzma_options_lzma), allocator);
1038 if (opt == NULL)
1039 return LZMA_MEM_ERROR;
1040
1041 if (lzma_lzma_lclppb_decode(opt, props[0]))
1042 goto error;
1043
1044 // All dictionary sizes are accepted, including zero. LZ decoder
1045 // will automatically use a dictionary at least a few KiB even if
1046 // a smaller dictionary is requested.
1047 opt->dict_size = integer_read_32(props + 1);
1048
1049 opt->preset_dict = NULL;
1050 opt->preset_dict_size = 0;
1051
1052 *options = opt;
1053
1054 return LZMA_OK;
1055
1056 error:
1057 lzma_free(opt, allocator);
1058 return LZMA_OPTIONS_ERROR;
1059 }
1060