4
* Author: Lasse Collin <lasse.collin@tukaani.org>
6
* This file has been put into the public domain.
7
* You can do whatever you want with this file.
10
#include "xz_private.h"
11
#include "xz_stream.h"
13
/* Hash used to validate the Index field */
16
vli_type uncompressed;
21
/* Position in dec_main() */
35
/* Position in variable-length integers and Check fields */
38
/* Variable-length integer decoded by dec_vli() */
41
/* Saved in_pos and out_pos */
45
/* CRC32 value in Block or Index */
48
/* Type of the integrity check calculated from uncompressed data */
49
enum xz_check check_type;
55
* True if the next call to xz_dec_run() is allowed to return
60
/* Information stored in Block Header */
63
* Value stored in the Compressed Size field, or
64
* VLI_UNKNOWN if Compressed Size is not present.
69
* Value stored in the Uncompressed Size field, or
70
* VLI_UNKNOWN if Uncompressed Size is not present.
72
vli_type uncompressed;
74
/* Size of the Block Header field */
78
/* Information collected when decoding Blocks */
80
/* Observed compressed size of the current Block */
83
/* Observed uncompressed size of the current Block */
84
vli_type uncompressed;
86
/* Number of Blocks decoded so far */
90
* Hash calculated from the Block sizes. This is used to
91
* validate the Index field.
93
struct xz_dec_hash hash;
96
/* Variables needed when verifying the Index field */
98
/* Position in dec_index() */
102
SEQ_INDEX_UNCOMPRESSED
105
/* Size of the Index in bytes */
108
/* Number of Records (matches block.count in valid files) */
112
* Hash calculated from the Records (matches block.hash in
115
struct xz_dec_hash hash;
119
* Temporary buffer needed to hold Stream Header, Block Header,
120
* and Stream Footer. The Block Header is the biggest (1 KiB)
121
* so we reserve space according to that. buf[] has to be aligned
122
* to a multiple of four bytes; the size_t variables before it
123
* should guarantee this.
131
struct xz_dec_lzma2 *lzma2;
134
struct xz_dec_bcj *bcj;
139
#ifdef XZ_DEC_ANY_CHECK
140
/* Sizes of the Check field with different Check IDs */
141
static const uint8_t check_sizes[16] = {
152
* Fill s->temp by copying data starting from b->in[b->in_pos]. Caller
153
* must have set s->temp.pos to indicate how much data we are supposed
154
* to copy into s->temp.buf. Return true once s->temp.pos has reached
157
static bool fill_temp(struct xz_dec *s, struct xz_buf *b)
159
size_t copy_size = min_t(size_t,
160
b->in_size - b->in_pos, s->temp.size - s->temp.pos);
162
memcpy(s->temp.buf + s->temp.pos, b->in + b->in_pos, copy_size);
163
b->in_pos += copy_size;
164
s->temp.pos += copy_size;
166
if (s->temp.pos == s->temp.size) {
174
/* Decode a variable-length integer (little-endian base-128 encoding) */
175
static enum xz_ret dec_vli(struct xz_dec *s, const uint8_t *in,
176
size_t *in_pos, size_t in_size)
183
while (*in_pos < in_size) {
187
s->vli |= (vli_type)(byte & 0x7F) << s->pos;
189
if ((byte & 0x80) == 0) {
190
/* Don't allow non-minimal encodings. */
191
if (byte == 0 && s->pos != 0)
192
return XZ_DATA_ERROR;
195
return XZ_STREAM_END;
199
if (s->pos == 7 * VLI_BYTES_MAX)
200
return XZ_DATA_ERROR;
207
* Decode the Compressed Data field from a Block. Update and validate
208
* the observed compressed and uncompressed sizes of the Block so that
209
* they don't exceed the values possibly stored in the Block Header
210
* (validation assumes that no integer overflow occurs, since vli_type
211
* is normally uint64_t). Update the CRC32 if presence of the CRC32
212
* field was indicated in Stream Header.
214
* Once the decoding is finished, validate that the observed sizes match
215
* the sizes possibly stored in the Block Header. Update the hash and
216
* Block count, which are later used to validate the Index field.
218
static enum xz_ret dec_block(struct xz_dec *s, struct xz_buf *b)
222
s->in_start = b->in_pos;
223
s->out_start = b->out_pos;
227
ret = xz_dec_bcj_run(s->bcj, s->lzma2, b);
230
ret = xz_dec_lzma2_run(s->lzma2, b);
232
s->block.compressed += b->in_pos - s->in_start;
233
s->block.uncompressed += b->out_pos - s->out_start;
236
* There is no need to separately check for VLI_UNKNOWN, since
237
* the observed sizes are always smaller than VLI_UNKNOWN.
239
if (s->block.compressed > s->block_header.compressed
240
|| s->block.uncompressed
241
> s->block_header.uncompressed)
242
return XZ_DATA_ERROR;
244
if (s->check_type == XZ_CHECK_CRC32)
245
s->crc32 = xz_crc32(b->out + s->out_start,
246
b->out_pos - s->out_start, s->crc32);
248
if (ret == XZ_STREAM_END) {
249
if (s->block_header.compressed != VLI_UNKNOWN
250
&& s->block_header.compressed
251
!= s->block.compressed)
252
return XZ_DATA_ERROR;
254
if (s->block_header.uncompressed != VLI_UNKNOWN
255
&& s->block_header.uncompressed
256
!= s->block.uncompressed)
257
return XZ_DATA_ERROR;
259
s->block.hash.unpadded += s->block_header.size
260
+ s->block.compressed;
262
#ifdef XZ_DEC_ANY_CHECK
263
s->block.hash.unpadded += check_sizes[s->check_type];
265
if (s->check_type == XZ_CHECK_CRC32)
266
s->block.hash.unpadded += 4;
269
s->block.hash.uncompressed += s->block.uncompressed;
270
s->block.hash.crc32 = xz_crc32(
271
(const uint8_t *)&s->block.hash,
272
sizeof(s->block.hash), s->block.hash.crc32);
280
/* Update the Index size and the CRC32 value. */
281
static void index_update(struct xz_dec *s, const struct xz_buf *b)
283
size_t in_used = b->in_pos - s->in_start;
284
s->index.size += in_used;
285
s->crc32 = xz_crc32(b->in + s->in_start, in_used, s->crc32);
289
* Decode the Number of Records, Unpadded Size, and Uncompressed Size
290
* fields from the Index field. That is, Index Padding and CRC32 are not
291
* decoded by this function.
293
* This can return XZ_OK (more input needed), XZ_STREAM_END (everything
294
* successfully decoded), or XZ_DATA_ERROR (input is corrupt).
296
static enum xz_ret dec_index(struct xz_dec *s, struct xz_buf *b)
301
ret = dec_vli(s, b->in, &b->in_pos, b->in_size);
302
if (ret != XZ_STREAM_END) {
307
switch (s->index.sequence) {
308
case SEQ_INDEX_COUNT:
309
s->index.count = s->vli;
312
* Validate that the Number of Records field
313
* indicates the same number of Records as
314
* there were Blocks in the Stream.
316
if (s->index.count != s->block.count)
317
return XZ_DATA_ERROR;
319
s->index.sequence = SEQ_INDEX_UNPADDED;
322
case SEQ_INDEX_UNPADDED:
323
s->index.hash.unpadded += s->vli;
324
s->index.sequence = SEQ_INDEX_UNCOMPRESSED;
327
case SEQ_INDEX_UNCOMPRESSED:
328
s->index.hash.uncompressed += s->vli;
329
s->index.hash.crc32 = xz_crc32(
330
(const uint8_t *)&s->index.hash,
331
sizeof(s->index.hash),
332
s->index.hash.crc32);
334
s->index.sequence = SEQ_INDEX_UNPADDED;
337
} while (s->index.count > 0);
339
return XZ_STREAM_END;
343
* Validate that the next four input bytes match the value of s->crc32.
344
* s->pos must be zero when starting to validate the first byte.
346
static enum xz_ret crc32_validate(struct xz_dec *s, struct xz_buf *b)
349
if (b->in_pos == b->in_size)
352
if (((s->crc32 >> s->pos) & 0xFF) != b->in[b->in_pos++])
353
return XZ_DATA_ERROR;
357
} while (s->pos < 32);
362
return XZ_STREAM_END;
365
#ifdef XZ_DEC_ANY_CHECK
367
* Skip over the Check field when the Check ID is not supported.
368
* Returns true once the whole Check field has been skipped over.
370
static bool check_skip(struct xz_dec *s, struct xz_buf *b)
372
while (s->pos < check_sizes[s->check_type]) {
373
if (b->in_pos == b->in_size)
386
/* Decode the Stream Header field (the first 12 bytes of the .xz Stream). */
387
static enum xz_ret dec_stream_header(struct xz_dec *s)
389
if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE))
390
return XZ_FORMAT_ERROR;
392
if (xz_crc32(s->temp.buf + HEADER_MAGIC_SIZE, 2, 0)
393
!= get_le32(s->temp.buf + HEADER_MAGIC_SIZE + 2))
394
return XZ_DATA_ERROR;
396
if (s->temp.buf[HEADER_MAGIC_SIZE] != 0)
397
return XZ_OPTIONS_ERROR;
400
* Of integrity checks, we support only none (Check ID = 0) and
401
* CRC32 (Check ID = 1). However, if XZ_DEC_ANY_CHECK is defined,
402
* we will accept other check types too, but then the check won't
403
* be verified and a warning (XZ_UNSUPPORTED_CHECK) will be given.
405
s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1];
407
#ifdef XZ_DEC_ANY_CHECK
408
if (s->check_type > XZ_CHECK_MAX)
409
return XZ_OPTIONS_ERROR;
411
if (s->check_type > XZ_CHECK_CRC32)
412
return XZ_UNSUPPORTED_CHECK;
414
if (s->check_type > XZ_CHECK_CRC32)
415
return XZ_OPTIONS_ERROR;
421
/* Decode the Stream Footer field (the last 12 bytes of the .xz Stream) */
422
static enum xz_ret dec_stream_footer(struct xz_dec *s)
424
if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE))
425
return XZ_DATA_ERROR;
427
if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf))
428
return XZ_DATA_ERROR;
431
* Validate Backward Size. Note that we never added the size of the
432
* Index CRC32 field to s->index.size, thus we use s->index.size / 4
433
* instead of s->index.size / 4 - 1.
435
if ((s->index.size >> 2) != get_le32(s->temp.buf + 4))
436
return XZ_DATA_ERROR;
438
if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type)
439
return XZ_DATA_ERROR;
442
* Use XZ_STREAM_END instead of XZ_OK to be more convenient
445
return XZ_STREAM_END;
448
/* Decode the Block Header and initialize the filter chain. */
449
static enum xz_ret dec_block_header(struct xz_dec *s)
454
* Validate the CRC32. We know that the temp buffer is at least
455
* eight bytes so this is safe.
458
if (xz_crc32(s->temp.buf, s->temp.size, 0)
459
!= get_le32(s->temp.buf + s->temp.size))
460
return XZ_DATA_ERROR;
465
* Catch unsupported Block Flags. We support only one or two filters
466
* in the chain, so we catch that with the same test.
469
if (s->temp.buf[1] & 0x3E)
471
if (s->temp.buf[1] & 0x3F)
473
return XZ_OPTIONS_ERROR;
475
/* Compressed Size */
476
if (s->temp.buf[1] & 0x40) {
477
if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
479
return XZ_DATA_ERROR;
481
s->block_header.compressed = s->vli;
483
s->block_header.compressed = VLI_UNKNOWN;
486
/* Uncompressed Size */
487
if (s->temp.buf[1] & 0x80) {
488
if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
490
return XZ_DATA_ERROR;
492
s->block_header.uncompressed = s->vli;
494
s->block_header.uncompressed = VLI_UNKNOWN;
498
/* If there are two filters, the first one must be a BCJ filter. */
499
s->bcj_active = s->temp.buf[1] & 0x01;
501
if (s->temp.size - s->temp.pos < 2)
502
return XZ_OPTIONS_ERROR;
504
ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]);
509
* We don't support custom start offset,
510
* so Size of Properties must be zero.
512
if (s->temp.buf[s->temp.pos++] != 0x00)
513
return XZ_OPTIONS_ERROR;
517
/* Valid Filter Flags always take at least two bytes. */
518
if (s->temp.size - s->temp.pos < 2)
519
return XZ_DATA_ERROR;
521
/* Filter ID = LZMA2 */
522
if (s->temp.buf[s->temp.pos++] != 0x21)
523
return XZ_OPTIONS_ERROR;
525
/* Size of Properties = 1-byte Filter Properties */
526
if (s->temp.buf[s->temp.pos++] != 0x01)
527
return XZ_OPTIONS_ERROR;
529
/* Filter Properties contains LZMA2 dictionary size. */
530
if (s->temp.size - s->temp.pos < 1)
531
return XZ_DATA_ERROR;
533
ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]);
537
/* The rest must be Header Padding. */
538
while (s->temp.pos < s->temp.size)
539
if (s->temp.buf[s->temp.pos++] != 0x00)
540
return XZ_OPTIONS_ERROR;
543
s->block.compressed = 0;
544
s->block.uncompressed = 0;
549
static enum xz_ret dec_main(struct xz_dec *s, struct xz_buf *b)
554
* Store the start position for the case when we are in the middle
555
* of the Index field.
557
s->in_start = b->in_pos;
560
switch (s->sequence) {
561
case SEQ_STREAM_HEADER:
563
* Stream Header is copied to s->temp, and then
564
* decoded from there. This way if the caller
565
* gives us only little input at a time, we can
566
* still keep the Stream Header decoding code
567
* simple. Similar approach is used in many places
570
if (!fill_temp(s, b))
574
* If dec_stream_header() returns
575
* XZ_UNSUPPORTED_CHECK, it is still possible
576
* to continue decoding if working in multi-call
577
* mode. Thus, update s->sequence before calling
578
* dec_stream_header().
580
s->sequence = SEQ_BLOCK_START;
582
ret = dec_stream_header(s);
586
case SEQ_BLOCK_START:
587
/* We need one byte of input to continue. */
588
if (b->in_pos == b->in_size)
591
/* See if this is the beginning of the Index field. */
592
if (b->in[b->in_pos] == 0) {
593
s->in_start = b->in_pos++;
594
s->sequence = SEQ_INDEX;
599
* Calculate the size of the Block Header and
600
* prepare to decode it.
603
= ((uint32_t)b->in[b->in_pos] + 1) * 4;
605
s->temp.size = s->block_header.size;
607
s->sequence = SEQ_BLOCK_HEADER;
609
case SEQ_BLOCK_HEADER:
610
if (!fill_temp(s, b))
613
ret = dec_block_header(s);
617
s->sequence = SEQ_BLOCK_UNCOMPRESS;
619
case SEQ_BLOCK_UNCOMPRESS:
620
ret = dec_block(s, b);
621
if (ret != XZ_STREAM_END)
624
s->sequence = SEQ_BLOCK_PADDING;
626
case SEQ_BLOCK_PADDING:
628
* Size of Compressed Data + Block Padding
629
* must be a multiple of four. We don't need
630
* s->block.compressed for anything else
631
* anymore, so we use it here to test the size
632
* of the Block Padding field.
634
while (s->block.compressed & 3) {
635
if (b->in_pos == b->in_size)
638
if (b->in[b->in_pos++] != 0)
639
return XZ_DATA_ERROR;
641
++s->block.compressed;
644
s->sequence = SEQ_BLOCK_CHECK;
646
case SEQ_BLOCK_CHECK:
647
if (s->check_type == XZ_CHECK_CRC32) {
648
ret = crc32_validate(s, b);
649
if (ret != XZ_STREAM_END)
652
#ifdef XZ_DEC_ANY_CHECK
653
else if (!check_skip(s, b)) {
658
s->sequence = SEQ_BLOCK_START;
662
ret = dec_index(s, b);
663
if (ret != XZ_STREAM_END)
666
s->sequence = SEQ_INDEX_PADDING;
668
case SEQ_INDEX_PADDING:
669
while ((s->index.size + (b->in_pos - s->in_start))
671
if (b->in_pos == b->in_size) {
676
if (b->in[b->in_pos++] != 0)
677
return XZ_DATA_ERROR;
680
/* Finish the CRC32 value and Index size. */
683
/* Compare the hashes to validate the Index field. */
684
if (!memeq(&s->block.hash, &s->index.hash,
685
sizeof(s->block.hash)))
686
return XZ_DATA_ERROR;
688
s->sequence = SEQ_INDEX_CRC32;
690
case SEQ_INDEX_CRC32:
691
ret = crc32_validate(s, b);
692
if (ret != XZ_STREAM_END)
695
s->temp.size = STREAM_HEADER_SIZE;
696
s->sequence = SEQ_STREAM_FOOTER;
698
case SEQ_STREAM_FOOTER:
699
if (!fill_temp(s, b))
702
return dec_stream_footer(s);
710
* xz_dec_run() is a wrapper for dec_main() to handle some special cases in
711
* multi-call and single-call decoding.
713
* In multi-call mode, we must return XZ_BUF_ERROR when it seems clear that we
714
* are not going to make any progress anymore. This is to prevent the caller
715
* from calling us infinitely when the input file is truncated or otherwise
716
* corrupt. Since zlib-style API allows that the caller fills the input buffer
717
* only when the decoder doesn't produce any new output, we have to be careful
718
* to avoid returning XZ_BUF_ERROR too easily: XZ_BUF_ERROR is returned only
719
* after the second consecutive call to xz_dec_run() that makes no progress.
721
* In single-call mode, if we couldn't decode everything and no error
722
* occurred, either the input is truncated or the output buffer is too small.
723
* Since we know that the last input byte never produces any output, we know
724
* that if all the input was consumed and decoding wasn't finished, the file
725
* must be corrupt. Otherwise the output buffer has to be too small or the
726
* file is corrupt in a way that decoding it produces too big output.
728
* If single-call decoding fails, we reset b->in_pos and b->out_pos back to
729
* their original values. This is because with some filter chains there won't
730
* be any valid uncompressed data in the output buffer unless the decoding
731
* actually succeeds (that's the price to pay of using the output buffer as
734
XZ_EXTERN enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b)
740
if (DEC_IS_SINGLE(s->mode))
743
in_start = b->in_pos;
744
out_start = b->out_pos;
745
ret = dec_main(s, b);
747
if (DEC_IS_SINGLE(s->mode)) {
749
ret = b->in_pos == b->in_size
750
? XZ_DATA_ERROR : XZ_BUF_ERROR;
752
if (ret != XZ_STREAM_END) {
753
b->in_pos = in_start;
754
b->out_pos = out_start;
757
} else if (ret == XZ_OK && in_start == b->in_pos
758
&& out_start == b->out_pos) {
759
if (s->allow_buf_error)
762
s->allow_buf_error = true;
764
s->allow_buf_error = false;
770
XZ_EXTERN struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max)
772
struct xz_dec *s = kmalloc(sizeof(*s), GFP_KERNEL);
779
s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode));
784
s->lzma2 = xz_dec_lzma2_create(mode, dict_max);
785
if (s->lzma2 == NULL)
793
xz_dec_bcj_end(s->bcj);
800
XZ_EXTERN void xz_dec_reset(struct xz_dec *s)
802
s->sequence = SEQ_STREAM_HEADER;
803
s->allow_buf_error = false;
806
memzero(&s->block, sizeof(s->block));
807
memzero(&s->index, sizeof(s->index));
809
s->temp.size = STREAM_HEADER_SIZE;
812
XZ_EXTERN void xz_dec_end(struct xz_dec *s)
815
xz_dec_lzma2_end(s->lzma2);
817
xz_dec_bcj_end(s->bcj);