0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 #include "xz_private.h"
0011 #include "xz_stream.h"
0012
0013
0014 struct xz_dec_hash {
0015 vli_type unpadded;
0016 vli_type uncompressed;
0017 uint32_t crc32;
0018 };
0019
0020 struct xz_dec {
0021
0022 enum {
0023 SEQ_STREAM_HEADER,
0024 SEQ_BLOCK_START,
0025 SEQ_BLOCK_HEADER,
0026 SEQ_BLOCK_UNCOMPRESS,
0027 SEQ_BLOCK_PADDING,
0028 SEQ_BLOCK_CHECK,
0029 SEQ_INDEX,
0030 SEQ_INDEX_PADDING,
0031 SEQ_INDEX_CRC32,
0032 SEQ_STREAM_FOOTER
0033 } sequence;
0034
0035
0036 uint32_t pos;
0037
0038
0039 vli_type vli;
0040
0041
0042 size_t in_start;
0043 size_t out_start;
0044
0045
0046 uint32_t crc32;
0047
0048
0049 enum xz_check check_type;
0050
0051
0052 enum xz_mode mode;
0053
0054
0055
0056
0057
0058 bool allow_buf_error;
0059
0060
0061 struct {
0062
0063
0064
0065
0066 vli_type compressed;
0067
0068
0069
0070
0071
0072 vli_type uncompressed;
0073
0074
0075 uint32_t size;
0076 } block_header;
0077
0078
0079 struct {
0080
0081 vli_type compressed;
0082
0083
0084 vli_type uncompressed;
0085
0086
0087 vli_type count;
0088
0089
0090
0091
0092
0093 struct xz_dec_hash hash;
0094 } block;
0095
0096
0097 struct {
0098
0099 enum {
0100 SEQ_INDEX_COUNT,
0101 SEQ_INDEX_UNPADDED,
0102 SEQ_INDEX_UNCOMPRESSED
0103 } sequence;
0104
0105
0106 vli_type size;
0107
0108
0109 vli_type count;
0110
0111
0112
0113
0114
0115 struct xz_dec_hash hash;
0116 } index;
0117
0118
0119
0120
0121
0122
0123
0124
0125 struct {
0126 size_t pos;
0127 size_t size;
0128 uint8_t buf[1024];
0129 } temp;
0130
0131 struct xz_dec_lzma2 *lzma2;
0132
0133 #ifdef XZ_DEC_BCJ
0134 struct xz_dec_bcj *bcj;
0135 bool bcj_active;
0136 #endif
0137 };
0138
0139 #ifdef XZ_DEC_ANY_CHECK
0140
0141 static const uint8_t check_sizes[16] = {
0142 0,
0143 4, 4, 4,
0144 8, 8, 8,
0145 16, 16, 16,
0146 32, 32, 32,
0147 64, 64, 64
0148 };
0149 #endif
0150
0151
0152
0153
0154
0155
0156
0157 static bool fill_temp(struct xz_dec *s, struct xz_buf *b)
0158 {
0159 size_t copy_size = min_t(size_t,
0160 b->in_size - b->in_pos, s->temp.size - s->temp.pos);
0161
0162 memcpy(s->temp.buf + s->temp.pos, b->in + b->in_pos, copy_size);
0163 b->in_pos += copy_size;
0164 s->temp.pos += copy_size;
0165
0166 if (s->temp.pos == s->temp.size) {
0167 s->temp.pos = 0;
0168 return true;
0169 }
0170
0171 return false;
0172 }
0173
0174
0175 static enum xz_ret dec_vli(struct xz_dec *s, const uint8_t *in,
0176 size_t *in_pos, size_t in_size)
0177 {
0178 uint8_t byte;
0179
0180 if (s->pos == 0)
0181 s->vli = 0;
0182
0183 while (*in_pos < in_size) {
0184 byte = in[*in_pos];
0185 ++*in_pos;
0186
0187 s->vli |= (vli_type)(byte & 0x7F) << s->pos;
0188
0189 if ((byte & 0x80) == 0) {
0190
0191 if (byte == 0 && s->pos != 0)
0192 return XZ_DATA_ERROR;
0193
0194 s->pos = 0;
0195 return XZ_STREAM_END;
0196 }
0197
0198 s->pos += 7;
0199 if (s->pos == 7 * VLI_BYTES_MAX)
0200 return XZ_DATA_ERROR;
0201 }
0202
0203 return XZ_OK;
0204 }
0205
0206
0207
0208
0209
0210
0211
0212
0213
0214
0215
0216
0217
0218 static enum xz_ret dec_block(struct xz_dec *s, struct xz_buf *b)
0219 {
0220 enum xz_ret ret;
0221
0222 s->in_start = b->in_pos;
0223 s->out_start = b->out_pos;
0224
0225 #ifdef XZ_DEC_BCJ
0226 if (s->bcj_active)
0227 ret = xz_dec_bcj_run(s->bcj, s->lzma2, b);
0228 else
0229 #endif
0230 ret = xz_dec_lzma2_run(s->lzma2, b);
0231
0232 s->block.compressed += b->in_pos - s->in_start;
0233 s->block.uncompressed += b->out_pos - s->out_start;
0234
0235
0236
0237
0238
0239 if (s->block.compressed > s->block_header.compressed
0240 || s->block.uncompressed
0241 > s->block_header.uncompressed)
0242 return XZ_DATA_ERROR;
0243
0244 if (s->check_type == XZ_CHECK_CRC32)
0245 s->crc32 = xz_crc32(b->out + s->out_start,
0246 b->out_pos - s->out_start, s->crc32);
0247
0248 if (ret == XZ_STREAM_END) {
0249 if (s->block_header.compressed != VLI_UNKNOWN
0250 && s->block_header.compressed
0251 != s->block.compressed)
0252 return XZ_DATA_ERROR;
0253
0254 if (s->block_header.uncompressed != VLI_UNKNOWN
0255 && s->block_header.uncompressed
0256 != s->block.uncompressed)
0257 return XZ_DATA_ERROR;
0258
0259 s->block.hash.unpadded += s->block_header.size
0260 + s->block.compressed;
0261
0262 #ifdef XZ_DEC_ANY_CHECK
0263 s->block.hash.unpadded += check_sizes[s->check_type];
0264 #else
0265 if (s->check_type == XZ_CHECK_CRC32)
0266 s->block.hash.unpadded += 4;
0267 #endif
0268
0269 s->block.hash.uncompressed += s->block.uncompressed;
0270 s->block.hash.crc32 = xz_crc32(
0271 (const uint8_t *)&s->block.hash,
0272 sizeof(s->block.hash), s->block.hash.crc32);
0273
0274 ++s->block.count;
0275 }
0276
0277 return ret;
0278 }
0279
0280
0281 static void index_update(struct xz_dec *s, const struct xz_buf *b)
0282 {
0283 size_t in_used = b->in_pos - s->in_start;
0284 s->index.size += in_used;
0285 s->crc32 = xz_crc32(b->in + s->in_start, in_used, s->crc32);
0286 }
0287
0288
0289
0290
0291
0292
0293
0294
0295
0296 static enum xz_ret dec_index(struct xz_dec *s, struct xz_buf *b)
0297 {
0298 enum xz_ret ret;
0299
0300 do {
0301 ret = dec_vli(s, b->in, &b->in_pos, b->in_size);
0302 if (ret != XZ_STREAM_END) {
0303 index_update(s, b);
0304 return ret;
0305 }
0306
0307 switch (s->index.sequence) {
0308 case SEQ_INDEX_COUNT:
0309 s->index.count = s->vli;
0310
0311
0312
0313
0314
0315
0316 if (s->index.count != s->block.count)
0317 return XZ_DATA_ERROR;
0318
0319 s->index.sequence = SEQ_INDEX_UNPADDED;
0320 break;
0321
0322 case SEQ_INDEX_UNPADDED:
0323 s->index.hash.unpadded += s->vli;
0324 s->index.sequence = SEQ_INDEX_UNCOMPRESSED;
0325 break;
0326
0327 case SEQ_INDEX_UNCOMPRESSED:
0328 s->index.hash.uncompressed += s->vli;
0329 s->index.hash.crc32 = xz_crc32(
0330 (const uint8_t *)&s->index.hash,
0331 sizeof(s->index.hash),
0332 s->index.hash.crc32);
0333 --s->index.count;
0334 s->index.sequence = SEQ_INDEX_UNPADDED;
0335 break;
0336 }
0337 } while (s->index.count > 0);
0338
0339 return XZ_STREAM_END;
0340 }
0341
0342
0343
0344
0345
0346 static enum xz_ret crc32_validate(struct xz_dec *s, struct xz_buf *b)
0347 {
0348 do {
0349 if (b->in_pos == b->in_size)
0350 return XZ_OK;
0351
0352 if (((s->crc32 >> s->pos) & 0xFF) != b->in[b->in_pos++])
0353 return XZ_DATA_ERROR;
0354
0355 s->pos += 8;
0356
0357 } while (s->pos < 32);
0358
0359 s->crc32 = 0;
0360 s->pos = 0;
0361
0362 return XZ_STREAM_END;
0363 }
0364
0365 #ifdef XZ_DEC_ANY_CHECK
0366
0367
0368
0369
0370 static bool check_skip(struct xz_dec *s, struct xz_buf *b)
0371 {
0372 while (s->pos < check_sizes[s->check_type]) {
0373 if (b->in_pos == b->in_size)
0374 return false;
0375
0376 ++b->in_pos;
0377 ++s->pos;
0378 }
0379
0380 s->pos = 0;
0381
0382 return true;
0383 }
0384 #endif
0385
0386
0387 static enum xz_ret dec_stream_header(struct xz_dec *s)
0388 {
0389 if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE))
0390 return XZ_FORMAT_ERROR;
0391
0392 if (xz_crc32(s->temp.buf + HEADER_MAGIC_SIZE, 2, 0)
0393 != get_le32(s->temp.buf + HEADER_MAGIC_SIZE + 2))
0394 return XZ_DATA_ERROR;
0395
0396 if (s->temp.buf[HEADER_MAGIC_SIZE] != 0)
0397 return XZ_OPTIONS_ERROR;
0398
0399
0400
0401
0402
0403
0404
0405 if (s->temp.buf[HEADER_MAGIC_SIZE + 1] > XZ_CHECK_MAX)
0406 return XZ_OPTIONS_ERROR;
0407
0408 s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1];
0409
0410 #ifdef XZ_DEC_ANY_CHECK
0411 if (s->check_type > XZ_CHECK_CRC32)
0412 return XZ_UNSUPPORTED_CHECK;
0413 #else
0414 if (s->check_type > XZ_CHECK_CRC32)
0415 return XZ_OPTIONS_ERROR;
0416 #endif
0417
0418 return XZ_OK;
0419 }
0420
0421
0422 static enum xz_ret dec_stream_footer(struct xz_dec *s)
0423 {
0424 if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE))
0425 return XZ_DATA_ERROR;
0426
0427 if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf))
0428 return XZ_DATA_ERROR;
0429
0430
0431
0432
0433
0434
0435 if ((s->index.size >> 2) != get_le32(s->temp.buf + 4))
0436 return XZ_DATA_ERROR;
0437
0438 if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type)
0439 return XZ_DATA_ERROR;
0440
0441
0442
0443
0444
0445 return XZ_STREAM_END;
0446 }
0447
0448
0449 static enum xz_ret dec_block_header(struct xz_dec *s)
0450 {
0451 enum xz_ret ret;
0452
0453
0454
0455
0456
0457 s->temp.size -= 4;
0458 if (xz_crc32(s->temp.buf, s->temp.size, 0)
0459 != get_le32(s->temp.buf + s->temp.size))
0460 return XZ_DATA_ERROR;
0461
0462 s->temp.pos = 2;
0463
0464
0465
0466
0467
0468 #ifdef XZ_DEC_BCJ
0469 if (s->temp.buf[1] & 0x3E)
0470 #else
0471 if (s->temp.buf[1] & 0x3F)
0472 #endif
0473 return XZ_OPTIONS_ERROR;
0474
0475
0476 if (s->temp.buf[1] & 0x40) {
0477 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
0478 != XZ_STREAM_END)
0479 return XZ_DATA_ERROR;
0480
0481 s->block_header.compressed = s->vli;
0482 } else {
0483 s->block_header.compressed = VLI_UNKNOWN;
0484 }
0485
0486
0487 if (s->temp.buf[1] & 0x80) {
0488 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
0489 != XZ_STREAM_END)
0490 return XZ_DATA_ERROR;
0491
0492 s->block_header.uncompressed = s->vli;
0493 } else {
0494 s->block_header.uncompressed = VLI_UNKNOWN;
0495 }
0496
0497 #ifdef XZ_DEC_BCJ
0498
0499 s->bcj_active = s->temp.buf[1] & 0x01;
0500 if (s->bcj_active) {
0501 if (s->temp.size - s->temp.pos < 2)
0502 return XZ_OPTIONS_ERROR;
0503
0504 ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]);
0505 if (ret != XZ_OK)
0506 return ret;
0507
0508
0509
0510
0511
0512 if (s->temp.buf[s->temp.pos++] != 0x00)
0513 return XZ_OPTIONS_ERROR;
0514 }
0515 #endif
0516
0517
0518 if (s->temp.size - s->temp.pos < 2)
0519 return XZ_DATA_ERROR;
0520
0521
0522 if (s->temp.buf[s->temp.pos++] != 0x21)
0523 return XZ_OPTIONS_ERROR;
0524
0525
0526 if (s->temp.buf[s->temp.pos++] != 0x01)
0527 return XZ_OPTIONS_ERROR;
0528
0529
0530 if (s->temp.size - s->temp.pos < 1)
0531 return XZ_DATA_ERROR;
0532
0533 ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]);
0534 if (ret != XZ_OK)
0535 return ret;
0536
0537
0538 while (s->temp.pos < s->temp.size)
0539 if (s->temp.buf[s->temp.pos++] != 0x00)
0540 return XZ_OPTIONS_ERROR;
0541
0542 s->temp.pos = 0;
0543 s->block.compressed = 0;
0544 s->block.uncompressed = 0;
0545
0546 return XZ_OK;
0547 }
0548
0549 static enum xz_ret dec_main(struct xz_dec *s, struct xz_buf *b)
0550 {
0551 enum xz_ret ret;
0552
0553
0554
0555
0556
0557 s->in_start = b->in_pos;
0558
0559 while (true) {
0560 switch (s->sequence) {
0561 case SEQ_STREAM_HEADER:
0562
0563
0564
0565
0566
0567
0568
0569
0570 if (!fill_temp(s, b))
0571 return XZ_OK;
0572
0573
0574
0575
0576
0577
0578
0579
0580 s->sequence = SEQ_BLOCK_START;
0581
0582 ret = dec_stream_header(s);
0583 if (ret != XZ_OK)
0584 return ret;
0585
0586 fallthrough;
0587
0588 case SEQ_BLOCK_START:
0589
0590 if (b->in_pos == b->in_size)
0591 return XZ_OK;
0592
0593
0594 if (b->in[b->in_pos] == 0) {
0595 s->in_start = b->in_pos++;
0596 s->sequence = SEQ_INDEX;
0597 break;
0598 }
0599
0600
0601
0602
0603
0604 s->block_header.size
0605 = ((uint32_t)b->in[b->in_pos] + 1) * 4;
0606
0607 s->temp.size = s->block_header.size;
0608 s->temp.pos = 0;
0609 s->sequence = SEQ_BLOCK_HEADER;
0610
0611 fallthrough;
0612
0613 case SEQ_BLOCK_HEADER:
0614 if (!fill_temp(s, b))
0615 return XZ_OK;
0616
0617 ret = dec_block_header(s);
0618 if (ret != XZ_OK)
0619 return ret;
0620
0621 s->sequence = SEQ_BLOCK_UNCOMPRESS;
0622
0623 fallthrough;
0624
0625 case SEQ_BLOCK_UNCOMPRESS:
0626 ret = dec_block(s, b);
0627 if (ret != XZ_STREAM_END)
0628 return ret;
0629
0630 s->sequence = SEQ_BLOCK_PADDING;
0631
0632 fallthrough;
0633
0634 case SEQ_BLOCK_PADDING:
0635
0636
0637
0638
0639
0640
0641
0642 while (s->block.compressed & 3) {
0643 if (b->in_pos == b->in_size)
0644 return XZ_OK;
0645
0646 if (b->in[b->in_pos++] != 0)
0647 return XZ_DATA_ERROR;
0648
0649 ++s->block.compressed;
0650 }
0651
0652 s->sequence = SEQ_BLOCK_CHECK;
0653
0654 fallthrough;
0655
0656 case SEQ_BLOCK_CHECK:
0657 if (s->check_type == XZ_CHECK_CRC32) {
0658 ret = crc32_validate(s, b);
0659 if (ret != XZ_STREAM_END)
0660 return ret;
0661 }
0662 #ifdef XZ_DEC_ANY_CHECK
0663 else if (!check_skip(s, b)) {
0664 return XZ_OK;
0665 }
0666 #endif
0667
0668 s->sequence = SEQ_BLOCK_START;
0669 break;
0670
0671 case SEQ_INDEX:
0672 ret = dec_index(s, b);
0673 if (ret != XZ_STREAM_END)
0674 return ret;
0675
0676 s->sequence = SEQ_INDEX_PADDING;
0677
0678 fallthrough;
0679
0680 case SEQ_INDEX_PADDING:
0681 while ((s->index.size + (b->in_pos - s->in_start))
0682 & 3) {
0683 if (b->in_pos == b->in_size) {
0684 index_update(s, b);
0685 return XZ_OK;
0686 }
0687
0688 if (b->in[b->in_pos++] != 0)
0689 return XZ_DATA_ERROR;
0690 }
0691
0692
0693 index_update(s, b);
0694
0695
0696 if (!memeq(&s->block.hash, &s->index.hash,
0697 sizeof(s->block.hash)))
0698 return XZ_DATA_ERROR;
0699
0700 s->sequence = SEQ_INDEX_CRC32;
0701
0702 fallthrough;
0703
0704 case SEQ_INDEX_CRC32:
0705 ret = crc32_validate(s, b);
0706 if (ret != XZ_STREAM_END)
0707 return ret;
0708
0709 s->temp.size = STREAM_HEADER_SIZE;
0710 s->sequence = SEQ_STREAM_FOOTER;
0711
0712 fallthrough;
0713
0714 case SEQ_STREAM_FOOTER:
0715 if (!fill_temp(s, b))
0716 return XZ_OK;
0717
0718 return dec_stream_footer(s);
0719 }
0720 }
0721
0722
0723 }
0724
0725
0726
0727
0728
0729
0730
0731
0732
0733
0734
0735
0736
0737
0738
0739
0740
0741
0742
0743
0744
0745
0746
0747
0748
0749
0750 XZ_EXTERN enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b)
0751 {
0752 size_t in_start;
0753 size_t out_start;
0754 enum xz_ret ret;
0755
0756 if (DEC_IS_SINGLE(s->mode))
0757 xz_dec_reset(s);
0758
0759 in_start = b->in_pos;
0760 out_start = b->out_pos;
0761 ret = dec_main(s, b);
0762
0763 if (DEC_IS_SINGLE(s->mode)) {
0764 if (ret == XZ_OK)
0765 ret = b->in_pos == b->in_size
0766 ? XZ_DATA_ERROR : XZ_BUF_ERROR;
0767
0768 if (ret != XZ_STREAM_END) {
0769 b->in_pos = in_start;
0770 b->out_pos = out_start;
0771 }
0772
0773 } else if (ret == XZ_OK && in_start == b->in_pos
0774 && out_start == b->out_pos) {
0775 if (s->allow_buf_error)
0776 ret = XZ_BUF_ERROR;
0777
0778 s->allow_buf_error = true;
0779 } else {
0780 s->allow_buf_error = false;
0781 }
0782
0783 return ret;
0784 }
0785
0786 XZ_EXTERN struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max)
0787 {
0788 struct xz_dec *s = kmalloc(sizeof(*s), GFP_KERNEL);
0789 if (s == NULL)
0790 return NULL;
0791
0792 s->mode = mode;
0793
0794 #ifdef XZ_DEC_BCJ
0795 s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode));
0796 if (s->bcj == NULL)
0797 goto error_bcj;
0798 #endif
0799
0800 s->lzma2 = xz_dec_lzma2_create(mode, dict_max);
0801 if (s->lzma2 == NULL)
0802 goto error_lzma2;
0803
0804 xz_dec_reset(s);
0805 return s;
0806
0807 error_lzma2:
0808 #ifdef XZ_DEC_BCJ
0809 xz_dec_bcj_end(s->bcj);
0810 error_bcj:
0811 #endif
0812 kfree(s);
0813 return NULL;
0814 }
0815
0816 XZ_EXTERN void xz_dec_reset(struct xz_dec *s)
0817 {
0818 s->sequence = SEQ_STREAM_HEADER;
0819 s->allow_buf_error = false;
0820 s->pos = 0;
0821 s->crc32 = 0;
0822 memzero(&s->block, sizeof(s->block));
0823 memzero(&s->index, sizeof(s->index));
0824 s->temp.pos = 0;
0825 s->temp.size = STREAM_HEADER_SIZE;
0826 }
0827
0828 XZ_EXTERN void xz_dec_end(struct xz_dec *s)
0829 {
0830 if (s != NULL) {
0831 xz_dec_lzma2_end(s->lzma2);
0832 #ifdef XZ_DEC_BCJ
0833 xz_dec_bcj_end(s->bcj);
0834 #endif
0835 kfree(s);
0836 }
0837 }