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