4 * Authors: Lasse Collin <lasse.collin@tukaani.org>
5 * Igor Pavlov <http://7-zip.org/>
7 * This file has been put into the public domain.
8 * You can do whatever you want with this file.
11 #include "xz_private.h"
15 * Range decoder initialization eats the first five bytes of each LZMA chunk.
17 #define RC_INIT_BYTES 5
20 * Minimum number of usable input buffer to safely decode one LZMA symbol.
21 * The worst case is that we decode 22 bits using probabilities and 26
22 * direct bits. This may decode at maximum of 20 bytes of input. However,
23 * lzma_main() does an extra normalization before returning, thus we
24 * need to put 21 here.
26 #define LZMA_IN_REQUIRED 21
29 * Dictionary (history buffer)
31 * These are always true:
32 * start <= pos <= full <= end
35 * In multi-call mode, also these are true:
40 * Most of these variables are size_t to support single-call mode,
41 * in which the dictionary variables address the actual output
45 /* Beginning of the history buffer */
48 /* Old position in buf (before decoding more data) */
55 * How full dictionary is. This is used to detect corrupt input that
56 * would read beyond the beginning of the uncompressed stream.
60 /* Write limit; we don't write to buf[limit] or later bytes. */
64 * End of the dictionary buffer. In multi-call mode, this is
65 * the same as the dictionary size. In single-call mode, this
66 * indicates the size of the output buffer.
71 * Size of the dictionary as specified in Block Header. This is used
72 * together with "full" to detect corrupt input that would make us
73 * read beyond the beginning of the uncompressed stream.
78 * Maximum allowed dictionary size in multi-call mode.
79 * This is ignored in single-call mode.
84 * Amount of memory currently allocated for the dictionary.
85 * This is used only with XZ_DYNALLOC. (With XZ_PREALLOC,
86 * size_max is always the same as the allocated size.)
100 * Number of initializing bytes remaining to be read
103 uint32_t init_bytes_left
;
106 * Buffer from which we read our input. It can be either
107 * temp.buf or the caller-provided input buffer.
114 /* Probabilities for a length decoder. */
115 struct lzma_len_dec
{
116 /* Probability of match length being at least 10 */
119 /* Probability of match length being at least 18 */
122 /* Probabilities for match lengths 2-9 */
123 uint16_t low
[POS_STATES_MAX
][LEN_LOW_SYMBOLS
];
125 /* Probabilities for match lengths 10-17 */
126 uint16_t mid
[POS_STATES_MAX
][LEN_MID_SYMBOLS
];
128 /* Probabilities for match lengths 18-273 */
129 uint16_t high
[LEN_HIGH_SYMBOLS
];
133 /* Distances of latest four matches */
139 /* Types of the most recently seen LZMA symbols */
140 enum lzma_state state
;
143 * Length of a match. This is updated so that dict_repeat can
144 * be called again to finish repeating the whole match.
149 * LZMA properties or related bit masks (number of literal
150 * context bits, a mask dervied from the number of literal
151 * position bits, and a mask dervied from the number
155 uint32_t literal_pos_mask
; /* (1 << lp) - 1 */
156 uint32_t pos_mask
; /* (1 << pb) - 1 */
158 /* If 1, it's a match. Otherwise it's a single 8-bit literal. */
159 uint16_t is_match
[STATES
][POS_STATES_MAX
];
161 /* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */
162 uint16_t is_rep
[STATES
];
165 * If 0, distance of a repeated match is rep0.
166 * Otherwise check is_rep1.
168 uint16_t is_rep0
[STATES
];
171 * If 0, distance of a repeated match is rep1.
172 * Otherwise check is_rep2.
174 uint16_t is_rep1
[STATES
];
176 /* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */
177 uint16_t is_rep2
[STATES
];
180 * If 1, the repeated match has length of one byte. Otherwise
181 * the length is decoded from rep_len_decoder.
183 uint16_t is_rep0_long
[STATES
][POS_STATES_MAX
];
186 * Probability tree for the highest two bits of the match
187 * distance. There is a separate probability tree for match
188 * lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
190 uint16_t dist_slot
[DIST_STATES
][DIST_SLOTS
];
193 * Probility trees for additional bits for match distance
194 * when the distance is in the range [4, 127].
196 uint16_t dist_special
[FULL_DISTANCES
- DIST_MODEL_END
];
199 * Probability tree for the lowest four bits of a match
200 * distance that is equal to or greater than 128.
202 uint16_t dist_align
[ALIGN_SIZE
];
204 /* Length of a normal match */
205 struct lzma_len_dec match_len_dec
;
207 /* Length of a repeated match */
208 struct lzma_len_dec rep_len_dec
;
210 /* Probabilities of literals */
211 uint16_t literal
[LITERAL_CODERS_MAX
][LITERAL_CODER_SIZE
];
215 /* Position in xz_dec_lzma2_run(). */
228 /* Next position after decoding the compressed size of the chunk. */
229 enum lzma2_seq next_sequence
;
231 /* Uncompressed size of LZMA chunk (2 MiB at maximum) */
232 uint32_t uncompressed
;
235 * Compressed size of LZMA chunk or compressed/uncompressed
236 * size of uncompressed chunk (64 KiB at maximum)
241 * True if dictionary reset is needed. This is false before
242 * the first chunk (LZMA or uncompressed).
244 bool need_dict_reset
;
247 * True if new LZMA properties are needed. This is false
248 * before the first LZMA chunk.
253 struct xz_dec_lzma2
{
255 * The order below is important on x86 to reduce code size and
256 * it shouldn't hurt on other platforms. Everything up to and
257 * including lzma.pos_mask are in the first 128 bytes on x86-32,
258 * which allows using smaller instructions to access those
259 * variables. On x86-64, fewer variables fit into the first 128
260 * bytes, but this is still the best order without sacrificing
261 * the readability by splitting the structures.
264 struct dictionary dict
;
265 struct lzma2_dec lzma2
;
266 struct lzma_dec lzma
;
269 * Temporary buffer which holds small number of input bytes between
270 * decoder calls. See lzma2_lzma() for details.
274 uint8_t buf
[3 * LZMA_IN_REQUIRED
];
283 * Reset the dictionary state. When in single-call mode, set up the beginning
284 * of the dictionary to point to the actual output buffer.
286 static void XZ_FUNC
dict_reset(struct dictionary
*dict
, struct xz_buf
*b
)
288 if (DEC_IS_SINGLE(dict
->mode
)) {
289 dict
->buf
= b
->out
+ b
->out_pos
;
290 dict
->end
= b
->out_size
- b
->out_pos
;
299 /* Set dictionary write limit */
300 static void XZ_FUNC
dict_limit(struct dictionary
*dict
, size_t out_max
)
302 if (dict
->end
- dict
->pos
<= out_max
)
303 dict
->limit
= dict
->end
;
305 dict
->limit
= dict
->pos
+ out_max
;
308 /* Return true if at least one byte can be written into the dictionary. */
309 static __always_inline
bool XZ_FUNC
dict_has_space(const struct dictionary
*dict
)
311 return dict
->pos
< dict
->limit
;
315 * Get a byte from the dictionary at the given distance. The distance is
316 * assumed to valid, or as a special case, zero when the dictionary is
317 * still empty. This special case is needed for single-call decoding to
318 * avoid writing a '\0' to the end of the destination buffer.
320 static __always_inline
uint32_t XZ_FUNC
dict_get(
321 const struct dictionary
*dict
, uint32_t dist
)
323 size_t offset
= dict
->pos
- dist
- 1;
325 if (dist
>= dict
->pos
)
328 return dict
->full
> 0 ? dict
->buf
[offset
] : 0;
332 * Put one byte into the dictionary. It is assumed that there is space for it.
334 static inline void XZ_FUNC
dict_put(struct dictionary
*dict
, uint8_t byte
)
336 dict
->buf
[dict
->pos
++] = byte
;
338 if (dict
->full
< dict
->pos
)
339 dict
->full
= dict
->pos
;
343 * Repeat given number of bytes from the given distance. If the distance is
344 * invalid, false is returned. On success, true is returned and *len is
345 * updated to indicate how many bytes were left to be repeated.
347 static bool XZ_FUNC
dict_repeat(
348 struct dictionary
*dict
, uint32_t *len
, uint32_t dist
)
353 if (dist
>= dict
->full
|| dist
>= dict
->size
)
356 left
= min_t(size_t, dict
->limit
- dict
->pos
, *len
);
359 back
= dict
->pos
- dist
- 1;
360 if (dist
>= dict
->pos
)
364 dict
->buf
[dict
->pos
++] = dict
->buf
[back
++];
365 if (back
== dict
->end
)
367 } while (--left
> 0);
369 if (dict
->full
< dict
->pos
)
370 dict
->full
= dict
->pos
;
375 /* Copy uncompressed data as is from input to dictionary and output buffers. */
376 static void XZ_FUNC
dict_uncompressed(
377 struct dictionary
*dict
, struct xz_buf
*b
, uint32_t *left
)
381 while (*left
> 0 && b
->in_pos
< b
->in_size
382 && b
->out_pos
< b
->out_size
) {
383 copy_size
= min(b
->in_size
- b
->in_pos
,
384 b
->out_size
- b
->out_pos
);
385 if (copy_size
> dict
->end
- dict
->pos
)
386 copy_size
= dict
->end
- dict
->pos
;
387 if (copy_size
> *left
)
392 memcpy(dict
->buf
+ dict
->pos
, b
->in
+ b
->in_pos
, copy_size
);
393 dict
->pos
+= copy_size
;
395 if (dict
->full
< dict
->pos
)
396 dict
->full
= dict
->pos
;
398 if (DEC_IS_MULTI(dict
->mode
)) {
399 if (dict
->pos
== dict
->end
)
402 memcpy(b
->out
+ b
->out_pos
, b
->in
+ b
->in_pos
,
406 dict
->start
= dict
->pos
;
408 b
->out_pos
+= copy_size
;
409 b
->in_pos
+= copy_size
;
414 * Flush pending data from dictionary to b->out. It is assumed that there is
415 * enough space in b->out. This is guaranteed because caller uses dict_limit()
416 * before decoding data into the dictionary.
418 static uint32_t XZ_FUNC
dict_flush(struct dictionary
*dict
, struct xz_buf
*b
)
420 size_t copy_size
= dict
->pos
- dict
->start
;
422 if (DEC_IS_MULTI(dict
->mode
)) {
423 if (dict
->pos
== dict
->end
)
426 memcpy(b
->out
+ b
->out_pos
, dict
->buf
+ dict
->start
,
430 dict
->start
= dict
->pos
;
431 b
->out_pos
+= copy_size
;
439 /* Reset the range decoder. */
440 static void XZ_FUNC
rc_reset(struct rc_dec
*rc
)
442 rc
->range
= (uint32_t)-1;
444 rc
->init_bytes_left
= RC_INIT_BYTES
;
448 * Read the first five initial bytes into rc->code if they haven't been
449 * read already. (Yes, the first byte gets completely ignored.)
451 static bool XZ_FUNC
rc_read_init(struct rc_dec
*rc
, struct xz_buf
*b
)
453 while (rc
->init_bytes_left
> 0) {
454 if (b
->in_pos
== b
->in_size
)
457 rc
->code
= (rc
->code
<< 8) + b
->in
[b
->in_pos
++];
458 --rc
->init_bytes_left
;
464 /* Return true if there may not be enough input for the next decoding loop. */
465 static inline bool XZ_FUNC
rc_limit_exceeded(const struct rc_dec
*rc
)
467 return rc
->in_pos
> rc
->in_limit
;
471 * Return true if it is possible (from point of view of range decoder) that
472 * we have reached the end of the LZMA chunk.
474 static inline bool XZ_FUNC
rc_is_finished(const struct rc_dec
*rc
)
476 return rc
->code
== 0;
479 /* Read the next input byte if needed. */
480 static __always_inline
void XZ_FUNC
rc_normalize(struct rc_dec
*rc
)
482 if (rc
->range
< RC_TOP_VALUE
) {
483 rc
->range
<<= RC_SHIFT_BITS
;
484 rc
->code
= (rc
->code
<< RC_SHIFT_BITS
) + rc
->in
[rc
->in_pos
++];
489 * Decode one bit. In some versions, this function has been splitted in three
490 * functions so that the compiler is supposed to be able to more easily avoid
491 * an extra branch. In this particular version of the LZMA decoder, this
492 * doesn't seem to be a good idea (tested with GCC 3.3.6, 3.4.6, and 4.3.3
493 * on x86). Using a non-splitted version results in nicer looking code too.
495 * NOTE: This must return an int. Do not make it return a bool or the speed
496 * of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care,
497 * and it generates 10-20 % faster code than GCC 3.x from this file anyway.)
499 static __always_inline
int XZ_FUNC
rc_bit(struct rc_dec
*rc
, uint16_t *prob
)
505 bound
= (rc
->range
>> RC_BIT_MODEL_TOTAL_BITS
) * *prob
;
506 if (rc
->code
< bound
) {
508 *prob
+= (RC_BIT_MODEL_TOTAL
- *prob
) >> RC_MOVE_BITS
;
513 *prob
-= *prob
>> RC_MOVE_BITS
;
520 /* Decode a bittree starting from the most significant bit. */
521 static __always_inline
uint32_t XZ_FUNC
rc_bittree(
522 struct rc_dec
*rc
, uint16_t *probs
, uint32_t limit
)
527 if (rc_bit(rc
, &probs
[symbol
]))
528 symbol
= (symbol
<< 1) + 1;
531 } while (symbol
< limit
);
536 /* Decode a bittree starting from the least significant bit. */
537 static __always_inline
void XZ_FUNC
rc_bittree_reverse(struct rc_dec
*rc
,
538 uint16_t *probs
, uint32_t *dest
, uint32_t limit
)
544 if (rc_bit(rc
, &probs
[symbol
])) {
545 symbol
= (symbol
<< 1) + 1;
550 } while (++i
< limit
);
553 /* Decode direct bits (fixed fifty-fifty probability) */
554 static inline void XZ_FUNC
rc_direct(
555 struct rc_dec
*rc
, uint32_t *dest
, uint32_t limit
)
562 rc
->code
-= rc
->range
;
563 mask
= (uint32_t)0 - (rc
->code
>> 31);
564 rc
->code
+= rc
->range
& mask
;
565 *dest
= (*dest
<< 1) + (mask
+ 1);
566 } while (--limit
> 0);
573 /* Get pointer to literal coder probability array. */
574 static uint16_t * XZ_FUNC
lzma_literal_probs(struct xz_dec_lzma2
*s
)
576 uint32_t prev_byte
= dict_get(&s
->dict
, 0);
577 uint32_t low
= prev_byte
>> (8 - s
->lzma
.lc
);
578 uint32_t high
= (s
->dict
.pos
& s
->lzma
.literal_pos_mask
) << s
->lzma
.lc
;
579 return s
->lzma
.literal
[low
+ high
];
582 /* Decode a literal (one 8-bit byte) */
583 static void XZ_FUNC
lzma_literal(struct xz_dec_lzma2
*s
)
592 probs
= lzma_literal_probs(s
);
594 if (lzma_state_is_literal(s
->lzma
.state
)) {
595 symbol
= rc_bittree(&s
->rc
, probs
, 0x100);
598 match_byte
= dict_get(&s
->dict
, s
->lzma
.rep0
) << 1;
602 match_bit
= match_byte
& offset
;
604 i
= offset
+ match_bit
+ symbol
;
606 if (rc_bit(&s
->rc
, &probs
[i
])) {
607 symbol
= (symbol
<< 1) + 1;
611 offset
&= ~match_bit
;
613 } while (symbol
< 0x100);
616 dict_put(&s
->dict
, (uint8_t)symbol
);
617 lzma_state_literal(&s
->lzma
.state
);
620 /* Decode the length of the match into s->lzma.len. */
621 static void XZ_FUNC
lzma_len(struct xz_dec_lzma2
*s
, struct lzma_len_dec
*l
,
627 if (!rc_bit(&s
->rc
, &l
->choice
)) {
628 probs
= l
->low
[pos_state
];
629 limit
= LEN_LOW_SYMBOLS
;
630 s
->lzma
.len
= MATCH_LEN_MIN
;
632 if (!rc_bit(&s
->rc
, &l
->choice2
)) {
633 probs
= l
->mid
[pos_state
];
634 limit
= LEN_MID_SYMBOLS
;
635 s
->lzma
.len
= MATCH_LEN_MIN
+ LEN_LOW_SYMBOLS
;
638 limit
= LEN_HIGH_SYMBOLS
;
639 s
->lzma
.len
= MATCH_LEN_MIN
+ LEN_LOW_SYMBOLS
644 s
->lzma
.len
+= rc_bittree(&s
->rc
, probs
, limit
) - limit
;
647 /* Decode a match. The distance will be stored in s->lzma.rep0. */
648 static void XZ_FUNC
lzma_match(struct xz_dec_lzma2
*s
, uint32_t pos_state
)
654 lzma_state_match(&s
->lzma
.state
);
656 s
->lzma
.rep3
= s
->lzma
.rep2
;
657 s
->lzma
.rep2
= s
->lzma
.rep1
;
658 s
->lzma
.rep1
= s
->lzma
.rep0
;
660 lzma_len(s
, &s
->lzma
.match_len_dec
, pos_state
);
662 probs
= s
->lzma
.dist_slot
[lzma_get_dist_state(s
->lzma
.len
)];
663 dist_slot
= rc_bittree(&s
->rc
, probs
, DIST_SLOTS
) - DIST_SLOTS
;
665 if (dist_slot
< DIST_MODEL_START
) {
666 s
->lzma
.rep0
= dist_slot
;
668 limit
= (dist_slot
>> 1) - 1;
669 s
->lzma
.rep0
= 2 + (dist_slot
& 1);
671 if (dist_slot
< DIST_MODEL_END
) {
672 s
->lzma
.rep0
<<= limit
;
673 probs
= s
->lzma
.dist_special
+ s
->lzma
.rep0
675 rc_bittree_reverse(&s
->rc
, probs
,
676 &s
->lzma
.rep0
, limit
);
678 rc_direct(&s
->rc
, &s
->lzma
.rep0
, limit
- ALIGN_BITS
);
679 s
->lzma
.rep0
<<= ALIGN_BITS
;
680 rc_bittree_reverse(&s
->rc
, s
->lzma
.dist_align
,
681 &s
->lzma
.rep0
, ALIGN_BITS
);
687 * Decode a repeated match. The distance is one of the four most recently
688 * seen matches. The distance will be stored in s->lzma.rep0.
690 static void XZ_FUNC
lzma_rep_match(struct xz_dec_lzma2
*s
, uint32_t pos_state
)
694 if (!rc_bit(&s
->rc
, &s
->lzma
.is_rep0
[s
->lzma
.state
])) {
695 if (!rc_bit(&s
->rc
, &s
->lzma
.is_rep0_long
[
696 s
->lzma
.state
][pos_state
])) {
697 lzma_state_short_rep(&s
->lzma
.state
);
702 if (!rc_bit(&s
->rc
, &s
->lzma
.is_rep1
[s
->lzma
.state
])) {
705 if (!rc_bit(&s
->rc
, &s
->lzma
.is_rep2
[s
->lzma
.state
])) {
709 s
->lzma
.rep3
= s
->lzma
.rep2
;
712 s
->lzma
.rep2
= s
->lzma
.rep1
;
715 s
->lzma
.rep1
= s
->lzma
.rep0
;
719 lzma_state_long_rep(&s
->lzma
.state
);
720 lzma_len(s
, &s
->lzma
.rep_len_dec
, pos_state
);
723 /* LZMA decoder core */
724 static bool XZ_FUNC
lzma_main(struct xz_dec_lzma2
*s
)
729 * If the dictionary was reached during the previous call, try to
730 * finish the possibly pending repeat in the dictionary.
732 if (dict_has_space(&s
->dict
) && s
->lzma
.len
> 0)
733 dict_repeat(&s
->dict
, &s
->lzma
.len
, s
->lzma
.rep0
);
736 * Decode more LZMA symbols. One iteration may consume up to
737 * LZMA_IN_REQUIRED - 1 bytes.
739 while (dict_has_space(&s
->dict
) && !rc_limit_exceeded(&s
->rc
)) {
740 pos_state
= s
->dict
.pos
& s
->lzma
.pos_mask
;
742 if (!rc_bit(&s
->rc
, &s
->lzma
.is_match
[
743 s
->lzma
.state
][pos_state
])) {
746 if (rc_bit(&s
->rc
, &s
->lzma
.is_rep
[s
->lzma
.state
]))
747 lzma_rep_match(s
, pos_state
);
749 lzma_match(s
, pos_state
);
751 if (!dict_repeat(&s
->dict
, &s
->lzma
.len
, s
->lzma
.rep0
))
757 * Having the range decoder always normalized when we are outside
758 * this function makes it easier to correctly handle end of the chunk.
760 rc_normalize(&s
->rc
);
766 * Reset the LZMA decoder and range decoder state. Dictionary is nore reset
767 * here, because LZMA state may be reset without resetting the dictionary.
769 static void XZ_FUNC
lzma_reset(struct xz_dec_lzma2
*s
)
774 s
->lzma
.state
= STATE_LIT_LIT
;
781 * All probabilities are initialized to the same value. This hack
782 * makes the code smaller by avoiding a separate loop for each
785 * This could be optimized so that only that part of literal
786 * probabilities that are actually required. In the common case
787 * we would write 12 KiB less.
789 probs
= s
->lzma
.is_match
[0];
790 for (i
= 0; i
< PROBS_TOTAL
; ++i
)
791 probs
[i
] = RC_BIT_MODEL_TOTAL
/ 2;
797 * Decode and validate LZMA properties (lc/lp/pb) and calculate the bit masks
798 * from the decoded lp and pb values. On success, the LZMA decoder state is
799 * reset and true is returned.
801 static bool XZ_FUNC
lzma_props(struct xz_dec_lzma2
*s
, uint8_t props
)
803 if (props
> (4 * 5 + 4) * 9 + 8)
806 s
->lzma
.pos_mask
= 0;
807 while (props
>= 9 * 5) {
812 s
->lzma
.pos_mask
= (1 << s
->lzma
.pos_mask
) - 1;
814 s
->lzma
.literal_pos_mask
= 0;
817 ++s
->lzma
.literal_pos_mask
;
822 if (s
->lzma
.lc
+ s
->lzma
.literal_pos_mask
> 4)
825 s
->lzma
.literal_pos_mask
= (1 << s
->lzma
.literal_pos_mask
) - 1;
837 * The LZMA decoder assumes that if the input limit (s->rc.in_limit) hasn't
838 * been exceeded, it is safe to read up to LZMA_IN_REQUIRED bytes. This
839 * wrapper function takes care of making the LZMA decoder's assumption safe.
841 * As long as there is plenty of input left to be decoded in the current LZMA
842 * chunk, we decode directly from the caller-supplied input buffer until
843 * there's LZMA_IN_REQUIRED bytes left. Those remaining bytes are copied into
844 * s->temp.buf, which (hopefully) gets filled on the next call to this
845 * function. We decode a few bytes from the temporary buffer so that we can
846 * continue decoding from the caller-supplied input buffer again.
848 static bool XZ_FUNC
lzma2_lzma(struct xz_dec_lzma2
*s
, struct xz_buf
*b
)
853 in_avail
= b
->in_size
- b
->in_pos
;
854 if (s
->temp
.size
> 0 || s
->lzma2
.compressed
== 0) {
855 tmp
= 2 * LZMA_IN_REQUIRED
- s
->temp
.size
;
856 if (tmp
> s
->lzma2
.compressed
- s
->temp
.size
)
857 tmp
= s
->lzma2
.compressed
- s
->temp
.size
;
861 memcpy(s
->temp
.buf
+ s
->temp
.size
, b
->in
+ b
->in_pos
, tmp
);
863 if (s
->temp
.size
+ tmp
== s
->lzma2
.compressed
) {
864 memzero(s
->temp
.buf
+ s
->temp
.size
+ tmp
,
866 - s
->temp
.size
- tmp
);
867 s
->rc
.in_limit
= s
->temp
.size
+ tmp
;
868 } else if (s
->temp
.size
+ tmp
< LZMA_IN_REQUIRED
) {
873 s
->rc
.in_limit
= s
->temp
.size
+ tmp
- LZMA_IN_REQUIRED
;
876 s
->rc
.in
= s
->temp
.buf
;
879 if (!lzma_main(s
) || s
->rc
.in_pos
> s
->temp
.size
+ tmp
)
882 s
->lzma2
.compressed
-= s
->rc
.in_pos
;
884 if (s
->rc
.in_pos
< s
->temp
.size
) {
885 s
->temp
.size
-= s
->rc
.in_pos
;
886 memmove(s
->temp
.buf
, s
->temp
.buf
+ s
->rc
.in_pos
,
891 b
->in_pos
+= s
->rc
.in_pos
- s
->temp
.size
;
895 in_avail
= b
->in_size
- b
->in_pos
;
896 if (in_avail
>= LZMA_IN_REQUIRED
) {
898 s
->rc
.in_pos
= b
->in_pos
;
900 if (in_avail
>= s
->lzma2
.compressed
+ LZMA_IN_REQUIRED
)
901 s
->rc
.in_limit
= b
->in_pos
+ s
->lzma2
.compressed
;
903 s
->rc
.in_limit
= b
->in_size
- LZMA_IN_REQUIRED
;
908 in_avail
= s
->rc
.in_pos
- b
->in_pos
;
909 if (in_avail
> s
->lzma2
.compressed
)
912 s
->lzma2
.compressed
-= in_avail
;
913 b
->in_pos
= s
->rc
.in_pos
;
916 in_avail
= b
->in_size
- b
->in_pos
;
917 if (in_avail
< LZMA_IN_REQUIRED
) {
918 if (in_avail
> s
->lzma2
.compressed
)
919 in_avail
= s
->lzma2
.compressed
;
921 memcpy(s
->temp
.buf
, b
->in
+ b
->in_pos
, in_avail
);
922 s
->temp
.size
= in_avail
;
923 b
->in_pos
+= in_avail
;
930 * Take care of the LZMA2 control layer, and forward the job of actual LZMA
931 * decoding or copying of uncompressed chunks to other functions.
933 XZ_EXTERN NOINLINE
enum xz_ret XZ_FUNC
xz_dec_lzma2_run(
934 struct xz_dec_lzma2
*s
, struct xz_buf
*b
)
938 while (b
->in_pos
< b
->in_size
|| s
->lzma2
.sequence
== SEQ_LZMA_RUN
) {
939 switch (s
->lzma2
.sequence
) {
946 * 0x01 Dictionary reset followed by
947 * an uncompressed chunk
948 * 0x02 Uncompressed chunk (no dictionary reset)
950 * Highest three bits (s->control & 0xE0):
951 * 0xE0 Dictionary reset, new properties and state
952 * reset, followed by LZMA compressed chunk
953 * 0xC0 New properties and state reset, followed
954 * by LZMA compressed chunk (no dictionary
956 * 0xA0 State reset using old properties,
957 * followed by LZMA compressed chunk (no
959 * 0x80 LZMA chunk (no dictionary or state reset)
961 * For LZMA compressed chunks, the lowest five bits
962 * (s->control & 1F) are the highest bits of the
963 * uncompressed size (bits 16-20).
965 * A new LZMA2 stream must begin with a dictionary
966 * reset. The first LZMA chunk must set new
967 * properties and reset the LZMA state.
969 * Values that don't match anything described above
970 * are invalid and we return XZ_DATA_ERROR.
972 tmp
= b
->in
[b
->in_pos
++];
975 return XZ_STREAM_END
;
977 if (tmp
>= 0xE0 || tmp
== 0x01) {
978 s
->lzma2
.need_props
= true;
979 s
->lzma2
.need_dict_reset
= false;
980 dict_reset(&s
->dict
, b
);
981 } else if (s
->lzma2
.need_dict_reset
) {
982 return XZ_DATA_ERROR
;
986 s
->lzma2
.uncompressed
= (tmp
& 0x1F) << 16;
987 s
->lzma2
.sequence
= SEQ_UNCOMPRESSED_1
;
991 * When there are new properties,
992 * state reset is done at
995 s
->lzma2
.need_props
= false;
996 s
->lzma2
.next_sequence
998 } else if (s
->lzma2
.need_props
) {
999 return XZ_DATA_ERROR
;
1001 s
->lzma2
.next_sequence
1008 return XZ_DATA_ERROR
;
1010 s
->lzma2
.sequence
= SEQ_COMPRESSED_0
;
1011 s
->lzma2
.next_sequence
= SEQ_COPY
;
1016 case SEQ_UNCOMPRESSED_1
:
1017 s
->lzma2
.uncompressed
1018 += (uint32_t)b
->in
[b
->in_pos
++] << 8;
1019 s
->lzma2
.sequence
= SEQ_UNCOMPRESSED_2
;
1022 case SEQ_UNCOMPRESSED_2
:
1023 s
->lzma2
.uncompressed
1024 += (uint32_t)b
->in
[b
->in_pos
++] + 1;
1025 s
->lzma2
.sequence
= SEQ_COMPRESSED_0
;
1028 case SEQ_COMPRESSED_0
:
1030 = (uint32_t)b
->in
[b
->in_pos
++] << 8;
1031 s
->lzma2
.sequence
= SEQ_COMPRESSED_1
;
1034 case SEQ_COMPRESSED_1
:
1036 += (uint32_t)b
->in
[b
->in_pos
++] + 1;
1037 s
->lzma2
.sequence
= s
->lzma2
.next_sequence
;
1040 case SEQ_PROPERTIES
:
1041 if (!lzma_props(s
, b
->in
[b
->in_pos
++]))
1042 return XZ_DATA_ERROR
;
1044 s
->lzma2
.sequence
= SEQ_LZMA_PREPARE
;
1046 case SEQ_LZMA_PREPARE
:
1047 if (s
->lzma2
.compressed
< RC_INIT_BYTES
)
1048 return XZ_DATA_ERROR
;
1050 if (!rc_read_init(&s
->rc
, b
))
1053 s
->lzma2
.compressed
-= RC_INIT_BYTES
;
1054 s
->lzma2
.sequence
= SEQ_LZMA_RUN
;
1058 * Set dictionary limit to indicate how much we want
1059 * to be encoded at maximum. Decode new data into the
1060 * dictionary. Flush the new data from dictionary to
1061 * b->out. Check if we finished decoding this chunk.
1062 * In case the dictionary got full but we didn't fill
1063 * the output buffer yet, we may run this loop
1064 * multiple times without changing s->lzma2.sequence.
1066 dict_limit(&s
->dict
, min_t(size_t,
1067 b
->out_size
- b
->out_pos
,
1068 s
->lzma2
.uncompressed
));
1069 if (!lzma2_lzma(s
, b
))
1070 return XZ_DATA_ERROR
;
1072 s
->lzma2
.uncompressed
-= dict_flush(&s
->dict
, b
);
1074 if (s
->lzma2
.uncompressed
== 0) {
1075 if (s
->lzma2
.compressed
> 0 || s
->lzma
.len
> 0
1076 || !rc_is_finished(&s
->rc
))
1077 return XZ_DATA_ERROR
;
1080 s
->lzma2
.sequence
= SEQ_CONTROL
;
1081 } else if (b
->out_pos
== b
->out_size
1082 || (b
->in_pos
== b
->in_size
1084 < s
->lzma2
.compressed
)) {
1091 dict_uncompressed(&s
->dict
, b
, &s
->lzma2
.compressed
);
1092 if (s
->lzma2
.compressed
> 0)
1095 s
->lzma2
.sequence
= SEQ_CONTROL
;
1103 XZ_EXTERN
struct xz_dec_lzma2
* XZ_FUNC
xz_dec_lzma2_create(
1104 enum xz_mode mode
, uint32_t dict_max
)
1106 struct xz_dec_lzma2
*s
= kmalloc(sizeof(*s
), GFP_KERNEL
);
1110 s
->dict
.mode
= mode
;
1111 s
->dict
.size_max
= dict_max
;
1113 if (DEC_IS_PREALLOC(mode
)) {
1114 s
->dict
.buf
= vmalloc(dict_max
);
1115 if (s
->dict
.buf
== NULL
) {
1119 } else if (DEC_IS_DYNALLOC(mode
)) {
1121 s
->dict
.allocated
= 0;
1127 XZ_EXTERN
enum xz_ret XZ_FUNC
xz_dec_lzma2_reset(
1128 struct xz_dec_lzma2
*s
, uint8_t props
)
1130 /* This limits dictionary size to 3 GiB to keep parsing simpler. */
1132 return XZ_OPTIONS_ERROR
;
1134 s
->dict
.size
= 2 + (props
& 1);
1135 s
->dict
.size
<<= (props
>> 1) + 11;
1137 if (DEC_IS_MULTI(s
->dict
.mode
)) {
1138 if (s
->dict
.size
> s
->dict
.size_max
)
1139 return XZ_MEMLIMIT_ERROR
;
1141 s
->dict
.end
= s
->dict
.size
;
1143 if (DEC_IS_DYNALLOC(s
->dict
.mode
)) {
1144 if (s
->dict
.allocated
< s
->dict
.size
) {
1146 s
->dict
.buf
= vmalloc(s
->dict
.size
);
1147 if (s
->dict
.buf
== NULL
) {
1148 s
->dict
.allocated
= 0;
1149 return XZ_MEM_ERROR
;
1157 s
->lzma2
.sequence
= SEQ_CONTROL
;
1158 s
->lzma2
.need_dict_reset
= true;
1165 XZ_EXTERN
void XZ_FUNC
xz_dec_lzma2_end(struct xz_dec_lzma2
*s
)
1167 if (DEC_IS_MULTI(s
->dict
.mode
))