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