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