1
2
3
4
5
6
7
8
9
10#include "xz_private.h"
11#include "xz_stream.h"
12
13
14struct xz_dec_hash {
15 vli_type unpadded;
16 vli_type uncompressed;
17 uint32_t crc32;
18};
19
20struct xz_dec {
21
22 enum {
23 SEQ_STREAM_HEADER,
24 SEQ_BLOCK_START,
25 SEQ_BLOCK_HEADER,
26 SEQ_BLOCK_UNCOMPRESS,
27 SEQ_BLOCK_PADDING,
28 SEQ_BLOCK_CHECK,
29 SEQ_INDEX,
30 SEQ_INDEX_PADDING,
31 SEQ_INDEX_CRC32,
32 SEQ_STREAM_FOOTER
33 } sequence;
34
35
36 uint32_t pos;
37
38
39 vli_type vli;
40
41
42 size_t in_start;
43 size_t out_start;
44
45
46 uint32_t crc32;
47
48
49 enum xz_check check_type;
50
51
52 enum xz_mode mode;
53
54
55
56
57
58 bool allow_buf_error;
59
60
61 struct {
62
63
64
65
66 vli_type compressed;
67
68
69
70
71
72 vli_type uncompressed;
73
74
75 uint32_t size;
76 } block_header;
77
78
79 struct {
80
81 vli_type compressed;
82
83
84 vli_type uncompressed;
85
86
87 vli_type count;
88
89
90
91
92
93 struct xz_dec_hash hash;
94 } block;
95
96
97 struct {
98
99 enum {
100 SEQ_INDEX_COUNT,
101 SEQ_INDEX_UNPADDED,
102 SEQ_INDEX_UNCOMPRESSED
103 } sequence;
104
105
106 vli_type size;
107
108
109 vli_type count;
110
111
112
113
114
115 struct xz_dec_hash hash;
116 } index;
117
118
119
120
121
122
123
124
125 struct {
126 size_t pos;
127 size_t size;
128 uint8_t buf[1024];
129 } temp;
130
131 struct xz_dec_lzma2 *lzma2;
132
133#ifdef XZ_DEC_BCJ
134 struct xz_dec_bcj *bcj;
135 bool bcj_active;
136#endif
137};
138
139#ifdef XZ_DEC_ANY_CHECK
140
141static const uint8_t check_sizes[16] = {
142 0,
143 4, 4, 4,
144 8, 8, 8,
145 16, 16, 16,
146 32, 32, 32,
147 64, 64, 64
148};
149#endif
150
151
152
153
154
155
156
157static bool fill_temp(struct xz_dec *s, struct xz_buf *b)
158{
159 size_t copy_size = min_t(size_t,
160 b->in_size - b->in_pos, s->temp.size - s->temp.pos);
161
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;
165
166 if (s->temp.pos == s->temp.size) {
167 s->temp.pos = 0;
168 return true;
169 }
170
171 return false;
172}
173
174
175static enum xz_ret dec_vli(struct xz_dec *s, const uint8_t *in,
176 size_t *in_pos, size_t in_size)
177{
178 uint8_t byte;
179
180 if (s->pos == 0)
181 s->vli = 0;
182
183 while (*in_pos < in_size) {
184 byte = in[*in_pos];
185 ++*in_pos;
186
187 s->vli |= (vli_type)(byte & 0x7F) << s->pos;
188
189 if ((byte & 0x80) == 0) {
190
191 if (byte == 0 && s->pos != 0)
192 return XZ_DATA_ERROR;
193
194 s->pos = 0;
195 return XZ_STREAM_END;
196 }
197
198 s->pos += 7;
199 if (s->pos == 7 * VLI_BYTES_MAX)
200 return XZ_DATA_ERROR;
201 }
202
203 return XZ_OK;
204}
205
206
207
208
209
210
211
212
213
214
215
216
217
218static enum xz_ret dec_block(struct xz_dec *s, struct xz_buf *b)
219{
220 enum xz_ret ret;
221
222 s->in_start = b->in_pos;
223 s->out_start = b->out_pos;
224
225#ifdef XZ_DEC_BCJ
226 if (s->bcj_active)
227 ret = xz_dec_bcj_run(s->bcj, s->lzma2, b);
228 else
229#endif
230 ret = xz_dec_lzma2_run(s->lzma2, b);
231
232 s->block.compressed += b->in_pos - s->in_start;
233 s->block.uncompressed += b->out_pos - s->out_start;
234
235
236
237
238
239 if (s->block.compressed > s->block_header.compressed
240 || s->block.uncompressed
241 > s->block_header.uncompressed)
242 return XZ_DATA_ERROR;
243
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);
247
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;
253
254 if (s->block_header.uncompressed != VLI_UNKNOWN
255 && s->block_header.uncompressed
256 != s->block.uncompressed)
257 return XZ_DATA_ERROR;
258
259 s->block.hash.unpadded += s->block_header.size
260 + s->block.compressed;
261
262#ifdef XZ_DEC_ANY_CHECK
263 s->block.hash.unpadded += check_sizes[s->check_type];
264#else
265 if (s->check_type == XZ_CHECK_CRC32)
266 s->block.hash.unpadded += 4;
267#endif
268
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);
273
274 ++s->block.count;
275 }
276
277 return ret;
278}
279
280
281static void index_update(struct xz_dec *s, const struct xz_buf *b)
282{
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);
286}
287
288
289
290
291
292
293
294
295
296static enum xz_ret dec_index(struct xz_dec *s, struct xz_buf *b)
297{
298 enum xz_ret ret;
299
300 do {
301 ret = dec_vli(s, b->in, &b->in_pos, b->in_size);
302 if (ret != XZ_STREAM_END) {
303 index_update(s, b);
304 return ret;
305 }
306
307 switch (s->index.sequence) {
308 case SEQ_INDEX_COUNT:
309 s->index.count = s->vli;
310
311
312
313
314
315
316 if (s->index.count != s->block.count)
317 return XZ_DATA_ERROR;
318
319 s->index.sequence = SEQ_INDEX_UNPADDED;
320 break;
321
322 case SEQ_INDEX_UNPADDED:
323 s->index.hash.unpadded += s->vli;
324 s->index.sequence = SEQ_INDEX_UNCOMPRESSED;
325 break;
326
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);
333 --s->index.count;
334 s->index.sequence = SEQ_INDEX_UNPADDED;
335 break;
336 }
337 } while (s->index.count > 0);
338
339 return XZ_STREAM_END;
340}
341
342
343
344
345
346static enum xz_ret crc32_validate(struct xz_dec *s, struct xz_buf *b)
347{
348 do {
349 if (b->in_pos == b->in_size)
350 return XZ_OK;
351
352 if (((s->crc32 >> s->pos) & 0xFF) != b->in[b->in_pos++])
353 return XZ_DATA_ERROR;
354
355 s->pos += 8;
356
357 } while (s->pos < 32);
358
359 s->crc32 = 0;
360 s->pos = 0;
361
362 return XZ_STREAM_END;
363}
364
365#ifdef XZ_DEC_ANY_CHECK
366
367
368
369
370static bool check_skip(struct xz_dec *s, struct xz_buf *b)
371{
372 while (s->pos < check_sizes[s->check_type]) {
373 if (b->in_pos == b->in_size)
374 return false;
375
376 ++b->in_pos;
377 ++s->pos;
378 }
379
380 s->pos = 0;
381
382 return true;
383}
384#endif
385
386
387static enum xz_ret dec_stream_header(struct xz_dec *s)
388{
389 if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE))
390 return XZ_FORMAT_ERROR;
391
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;
395
396 if (s->temp.buf[HEADER_MAGIC_SIZE] != 0)
397 return XZ_OPTIONS_ERROR;
398
399
400
401
402
403
404
405 s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1];
406
407#ifdef XZ_DEC_ANY_CHECK
408 if (s->check_type > XZ_CHECK_MAX)
409 return XZ_OPTIONS_ERROR;
410
411 if (s->check_type > XZ_CHECK_CRC32)
412 return XZ_UNSUPPORTED_CHECK;
413#else
414 if (s->check_type > XZ_CHECK_CRC32)
415 return XZ_OPTIONS_ERROR;
416#endif
417
418 return XZ_OK;
419}
420
421
422static enum xz_ret dec_stream_footer(struct xz_dec *s)
423{
424 if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE))
425 return XZ_DATA_ERROR;
426
427 if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf))
428 return XZ_DATA_ERROR;
429
430
431
432
433
434
435 if ((s->index.size >> 2) != get_le32(s->temp.buf + 4))
436 return XZ_DATA_ERROR;
437
438 if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type)
439 return XZ_DATA_ERROR;
440
441
442
443
444
445 return XZ_STREAM_END;
446}
447
448
449static enum xz_ret dec_block_header(struct xz_dec *s)
450{
451 enum xz_ret ret;
452
453
454
455
456
457 s->temp.size -= 4;
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;
461
462 s->temp.pos = 2;
463
464
465
466
467
468#ifdef XZ_DEC_BCJ
469 if (s->temp.buf[1] & 0x3E)
470#else
471 if (s->temp.buf[1] & 0x3F)
472#endif
473 return XZ_OPTIONS_ERROR;
474
475
476 if (s->temp.buf[1] & 0x40) {
477 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
478 != XZ_STREAM_END)
479 return XZ_DATA_ERROR;
480
481 s->block_header.compressed = s->vli;
482 } else {
483 s->block_header.compressed = VLI_UNKNOWN;
484 }
485
486
487 if (s->temp.buf[1] & 0x80) {
488 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
489 != XZ_STREAM_END)
490 return XZ_DATA_ERROR;
491
492 s->block_header.uncompressed = s->vli;
493 } else {
494 s->block_header.uncompressed = VLI_UNKNOWN;
495 }
496
497#ifdef XZ_DEC_BCJ
498
499 s->bcj_active = s->temp.buf[1] & 0x01;
500 if (s->bcj_active) {
501 if (s->temp.size - s->temp.pos < 2)
502 return XZ_OPTIONS_ERROR;
503
504 ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]);
505 if (ret != XZ_OK)
506 return ret;
507
508
509
510
511
512 if (s->temp.buf[s->temp.pos++] != 0x00)
513 return XZ_OPTIONS_ERROR;
514 }
515#endif
516
517
518 if (s->temp.size - s->temp.pos < 2)
519 return XZ_DATA_ERROR;
520
521
522 if (s->temp.buf[s->temp.pos++] != 0x21)
523 return XZ_OPTIONS_ERROR;
524
525
526 if (s->temp.buf[s->temp.pos++] != 0x01)
527 return XZ_OPTIONS_ERROR;
528
529
530 if (s->temp.size - s->temp.pos < 1)
531 return XZ_DATA_ERROR;
532
533 ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]);
534 if (ret != XZ_OK)
535 return ret;
536
537
538 while (s->temp.pos < s->temp.size)
539 if (s->temp.buf[s->temp.pos++] != 0x00)
540 return XZ_OPTIONS_ERROR;
541
542 s->temp.pos = 0;
543 s->block.compressed = 0;
544 s->block.uncompressed = 0;
545
546 return XZ_OK;
547}
548
549static enum xz_ret dec_main(struct xz_dec *s, struct xz_buf *b)
550{
551 enum xz_ret ret;
552
553
554
555
556
557 s->in_start = b->in_pos;
558
559 while (true) {
560 switch (s->sequence) {
561 case SEQ_STREAM_HEADER:
562
563
564
565
566
567
568
569
570 if (!fill_temp(s, b))
571 return XZ_OK;
572
573
574
575
576
577
578
579
580 s->sequence = SEQ_BLOCK_START;
581
582 ret = dec_stream_header(s);
583 if (ret != XZ_OK)
584 return ret;
585
586
587
588 case SEQ_BLOCK_START:
589
590 if (b->in_pos == b->in_size)
591 return XZ_OK;
592
593
594 if (b->in[b->in_pos] == 0) {
595 s->in_start = b->in_pos++;
596 s->sequence = SEQ_INDEX;
597 break;
598 }
599
600
601
602
603
604 s->block_header.size
605 = ((uint32_t)b->in[b->in_pos] + 1) * 4;
606
607 s->temp.size = s->block_header.size;
608 s->temp.pos = 0;
609 s->sequence = SEQ_BLOCK_HEADER;
610
611
612
613 case SEQ_BLOCK_HEADER:
614 if (!fill_temp(s, b))
615 return XZ_OK;
616
617 ret = dec_block_header(s);
618 if (ret != XZ_OK)
619 return ret;
620
621 s->sequence = SEQ_BLOCK_UNCOMPRESS;
622
623
624
625 case SEQ_BLOCK_UNCOMPRESS:
626 ret = dec_block(s, b);
627 if (ret != XZ_STREAM_END)
628 return ret;
629
630 s->sequence = SEQ_BLOCK_PADDING;
631
632
633
634 case SEQ_BLOCK_PADDING:
635
636
637
638
639
640
641
642 while (s->block.compressed & 3) {
643 if (b->in_pos == b->in_size)
644 return XZ_OK;
645
646 if (b->in[b->in_pos++] != 0)
647 return XZ_DATA_ERROR;
648
649 ++s->block.compressed;
650 }
651
652 s->sequence = SEQ_BLOCK_CHECK;
653
654
655
656 case SEQ_BLOCK_CHECK:
657 if (s->check_type == XZ_CHECK_CRC32) {
658 ret = crc32_validate(s, b);
659 if (ret != XZ_STREAM_END)
660 return ret;
661 }
662#ifdef XZ_DEC_ANY_CHECK
663 else if (!check_skip(s, b)) {
664 return XZ_OK;
665 }
666#endif
667
668 s->sequence = SEQ_BLOCK_START;
669 break;
670
671 case SEQ_INDEX:
672 ret = dec_index(s, b);
673 if (ret != XZ_STREAM_END)
674 return ret;
675
676 s->sequence = SEQ_INDEX_PADDING;
677
678
679
680 case SEQ_INDEX_PADDING:
681 while ((s->index.size + (b->in_pos - s->in_start))
682 & 3) {
683 if (b->in_pos == b->in_size) {
684 index_update(s, b);
685 return XZ_OK;
686 }
687
688 if (b->in[b->in_pos++] != 0)
689 return XZ_DATA_ERROR;
690 }
691
692
693 index_update(s, b);
694
695
696 if (!memeq(&s->block.hash, &s->index.hash,
697 sizeof(s->block.hash)))
698 return XZ_DATA_ERROR;
699
700 s->sequence = SEQ_INDEX_CRC32;
701
702
703
704 case SEQ_INDEX_CRC32:
705 ret = crc32_validate(s, b);
706 if (ret != XZ_STREAM_END)
707 return ret;
708
709 s->temp.size = STREAM_HEADER_SIZE;
710 s->sequence = SEQ_STREAM_FOOTER;
711
712
713
714 case SEQ_STREAM_FOOTER:
715 if (!fill_temp(s, b))
716 return XZ_OK;
717
718 return dec_stream_footer(s);
719 }
720 }
721
722
723}
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750XZ_EXTERN enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b)
751{
752 size_t in_start;
753 size_t out_start;
754 enum xz_ret ret;
755
756 if (DEC_IS_SINGLE(s->mode))
757 xz_dec_reset(s);
758
759 in_start = b->in_pos;
760 out_start = b->out_pos;
761 ret = dec_main(s, b);
762
763 if (DEC_IS_SINGLE(s->mode)) {
764 if (ret == XZ_OK)
765 ret = b->in_pos == b->in_size
766 ? XZ_DATA_ERROR : XZ_BUF_ERROR;
767
768 if (ret != XZ_STREAM_END) {
769 b->in_pos = in_start;
770 b->out_pos = out_start;
771 }
772
773 } else if (ret == XZ_OK && in_start == b->in_pos
774 && out_start == b->out_pos) {
775 if (s->allow_buf_error)
776 ret = XZ_BUF_ERROR;
777
778 s->allow_buf_error = true;
779 } else {
780 s->allow_buf_error = false;
781 }
782
783 return ret;
784}
785
786XZ_EXTERN struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max)
787{
788 struct xz_dec *s = kmalloc(sizeof(*s), GFP_KERNEL);
789 if (s == NULL)
790 return NULL;
791
792 s->mode = mode;
793
794#ifdef XZ_DEC_BCJ
795 s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode));
796 if (s->bcj == NULL)
797 goto error_bcj;
798#endif
799
800 s->lzma2 = xz_dec_lzma2_create(mode, dict_max);
801 if (s->lzma2 == NULL)
802 goto error_lzma2;
803
804 xz_dec_reset(s);
805 return s;
806
807error_lzma2:
808#ifdef XZ_DEC_BCJ
809 xz_dec_bcj_end(s->bcj);
810error_bcj:
811#endif
812 kfree(s);
813 return NULL;
814}
815
816XZ_EXTERN void xz_dec_reset(struct xz_dec *s)
817{
818 s->sequence = SEQ_STREAM_HEADER;
819 s->allow_buf_error = false;
820 s->pos = 0;
821 s->crc32 = 0;
822 memzero(&s->block, sizeof(s->block));
823 memzero(&s->index, sizeof(s->index));
824 s->temp.pos = 0;
825 s->temp.size = STREAM_HEADER_SIZE;
826}
827
828XZ_EXTERN void xz_dec_end(struct xz_dec *s)
829{
830 if (s != NULL) {
831 xz_dec_lzma2_end(s->lzma2);
832#ifdef XZ_DEC_BCJ
833 xz_dec_bcj_end(s->bcj);
834#endif
835 kfree(s);
836 }
837}
838