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