1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#define FOR_xzcat
21#include "toys.h"
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62enum xz_ret {
63 XZ_OK,
64 XZ_STREAM_END,
65 XZ_UNSUPPORTED_CHECK,
66 XZ_MEM_ERROR,
67 XZ_MEMLIMIT_ERROR,
68 XZ_FORMAT_ERROR,
69 XZ_OPTIONS_ERROR,
70 XZ_DATA_ERROR,
71 XZ_BUF_ERROR
72};
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90struct xz_buf {
91 const uint8_t *in;
92 size_t in_pos;
93 size_t in_size;
94
95 uint8_t *out;
96 size_t out_pos;
97 size_t out_size;
98};
99
100
101
102
103struct xz_dec;
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127struct xz_dec *xz_dec_init(uint32_t dict_max);
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b);
148
149
150
151
152
153
154
155
156
157
158
159
160void xz_dec_reset(struct xz_dec *s);
161
162
163
164
165
166
167void xz_dec_end(struct xz_dec *s);
168
169
170
171
172
173
174static uint32_t xz_crc32_table[256];
175
176uint32_t xz_crc32(const uint8_t *buf, size_t size, uint32_t crc)
177{
178 crc = ~crc;
179
180 while (size != 0) {
181 crc = xz_crc32_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8);
182 --size;
183 }
184
185 return ~crc;
186}
187
188static uint64_t xz_crc64_table[256];
189
190
191
192
193static uint8_t in[BUFSIZ];
194static uint8_t out[BUFSIZ];
195
196void do_xzcat(int fd, char *name)
197{
198 struct xz_buf b;
199 struct xz_dec *s;
200 enum xz_ret ret;
201 const char *msg;
202
203 crc_init(xz_crc32_table, 1);
204 const uint64_t poly = 0xC96C5795D7870F42ULL;
205 uint32_t i;
206 uint32_t j;
207 uint64_t r;
208
209
210 for (i = 0; i < 256; ++i) {
211 r = i;
212 for (j = 0; j < 8; ++j)
213 r = (r >> 1) ^ (poly & ~((r & 1) - 1));
214
215 xz_crc64_table[i] = r;
216 }
217
218
219
220
221
222 s = xz_dec_init(1 << 26);
223 if (s == NULL) {
224 msg = "Memory allocation failed\n";
225 goto error;
226 }
227
228 b.in = in;
229 b.in_pos = 0;
230 b.in_size = 0;
231 b.out = out;
232 b.out_pos = 0;
233 b.out_size = BUFSIZ;
234
235 for (;;) {
236 if (b.in_pos == b.in_size) {
237 b.in_size = read(fd, in, sizeof(in));
238 b.in_pos = 0;
239 }
240
241 ret = xz_dec_run(s, &b);
242
243 if (b.out_pos == sizeof(out)) {
244 if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos) {
245 msg = "Write error\n";
246 goto error;
247 }
248
249 b.out_pos = 0;
250 }
251
252 if (ret == XZ_OK)
253 continue;
254
255 if (ret == XZ_UNSUPPORTED_CHECK)
256 continue;
257
258 if (fwrite(out, 1, b.out_pos, stdout) != b.out_pos) {
259 msg = "Write error\n";
260 goto error;
261 }
262
263 switch (ret) {
264 case XZ_STREAM_END:
265 xz_dec_end(s);
266 return;
267
268 case XZ_MEM_ERROR:
269 msg = "Memory allocation failed\n";
270 goto error;
271
272 case XZ_MEMLIMIT_ERROR:
273 msg = "Memory usage limit reached\n";
274 goto error;
275
276 case XZ_FORMAT_ERROR:
277 msg = "Not a .xz file\n";
278 goto error;
279
280 case XZ_OPTIONS_ERROR:
281 msg = "Unsupported options in the .xz headers\n";
282 goto error;
283
284 case XZ_DATA_ERROR:
285 case XZ_BUF_ERROR:
286 msg = "File is corrupt\n";
287 goto error;
288
289 default:
290 msg = "Bug!\n";
291 goto error;
292 }
293 }
294
295error:
296 xz_dec_end(s);
297 error_exit("%s", msg);
298}
299
300void xzcat_main(void)
301{
302 loopfiles(toys.optargs, do_xzcat);
303}
304
305
306
307
308
309
310
311
312#define XZ_DEC_X86
313#define XZ_DEC_POWERPC
314#define XZ_DEC_IA64
315#define XZ_DEC_ARM
316#define XZ_DEC_ARMTHUMB
317#define XZ_DEC_SPARC
318
319
320#define memeq(a, b, size) (memcmp(a, b, size) == 0)
321
322
323#ifndef get_unaligned_le32
324static inline uint32_t get_unaligned_le32(const uint8_t *buf)
325{
326 return (uint32_t)buf[0]
327 | ((uint32_t)buf[1] << 8)
328 | ((uint32_t)buf[2] << 16)
329 | ((uint32_t)buf[3] << 24);
330}
331#endif
332
333#ifndef get_unaligned_be32
334static inline uint32_t get_unaligned_be32(const uint8_t *buf)
335{
336 return (uint32_t)(buf[0] << 24)
337 | ((uint32_t)buf[1] << 16)
338 | ((uint32_t)buf[2] << 8)
339 | (uint32_t)buf[3];
340}
341#endif
342
343#ifndef put_unaligned_le32
344static inline void put_unaligned_le32(uint32_t val, uint8_t *buf)
345{
346 buf[0] = (uint8_t)val;
347 buf[1] = (uint8_t)(val >> 8);
348 buf[2] = (uint8_t)(val >> 16);
349 buf[3] = (uint8_t)(val >> 24);
350}
351#endif
352
353#ifndef put_unaligned_be32
354static inline void put_unaligned_be32(uint32_t val, uint8_t *buf)
355{
356 buf[0] = (uint8_t)(val >> 24);
357 buf[1] = (uint8_t)(val >> 16);
358 buf[2] = (uint8_t)(val >> 8);
359 buf[3] = (uint8_t)val;
360}
361#endif
362
363
364
365
366
367
368#ifndef get_le32
369# define get_le32 get_unaligned_le32
370#endif
371
372
373
374
375
376#ifndef XZ_DEC_BCJ
377# if defined(XZ_DEC_X86) || defined(XZ_DEC_POWERPC) \
378 || defined(XZ_DEC_IA64) || defined(XZ_DEC_ARM) \
379 || defined(XZ_DEC_ARM) || defined(XZ_DEC_ARMTHUMB) \
380 || defined(XZ_DEC_SPARC)
381# define XZ_DEC_BCJ
382# endif
383#endif
384
385
386
387
388
389struct xz_dec_lzma2 *xz_dec_lzma2_create(uint32_t dict_max);
390
391
392
393
394
395
396
397enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s,
398 uint8_t props);
399
400
401enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
402 struct xz_buf *b);
403
404
405
406
407
408
409
410
411
412
413
414#ifdef XZ_DEC_BCJ
415
416struct xz_dec_bcj {
417
418 enum {
419 BCJ_X86 = 4,
420 BCJ_POWERPC = 5,
421 BCJ_IA64 = 6,
422 BCJ_ARM = 7,
423 BCJ_ARMTHUMB = 8,
424 BCJ_SPARC = 9
425 } type;
426
427
428
429
430
431
432 enum xz_ret ret;
433
434
435
436
437
438
439 uint32_t pos;
440
441
442 uint32_t x86_prev_mask;
443
444
445 uint8_t *out;
446 size_t out_pos;
447 size_t out_size;
448
449 struct {
450
451 size_t filtered;
452
453
454 size_t size;
455
456
457
458
459
460
461
462
463
464
465
466
467
468 uint8_t buf[16];
469 } temp;
470};
471
472
473
474
475
476
477
478enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id);
479
480
481
482
483
484
485enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s,
486 struct xz_dec_lzma2 *lzma2,
487 struct xz_buf *b);
488
489#ifdef XZ_DEC_X86
490
491
492
493
494static inline int bcj_x86_test_msbyte(uint8_t b)
495{
496 return b == 0x00 || b == 0xFF;
497}
498
499static size_t bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
500{
501 static const int mask_to_allowed_status[8]
502 = { 1,1,1,0,1,0,0,0 };
503
504 static const uint8_t mask_to_bit_num[8] = { 0, 1, 2, 2, 3, 3, 3, 3 };
505
506 size_t i;
507 size_t prev_pos = (size_t)-1;
508 uint32_t prev_mask = s->x86_prev_mask;
509 uint32_t src;
510 uint32_t dest;
511 uint32_t j;
512 uint8_t b;
513
514 if (size <= 4)
515 return 0;
516
517 size -= 4;
518 for (i = 0; i < size; ++i) {
519 if ((buf[i] & 0xFE) != 0xE8)
520 continue;
521
522 prev_pos = i - prev_pos;
523 if (prev_pos > 3) {
524 prev_mask = 0;
525 } else {
526 prev_mask = (prev_mask << (prev_pos - 1)) & 7;
527 if (prev_mask != 0) {
528 b = buf[i + 4 - mask_to_bit_num[prev_mask]];
529 if (!mask_to_allowed_status[prev_mask]
530 || bcj_x86_test_msbyte(b)) {
531 prev_pos = i;
532 prev_mask = (prev_mask << 1) | 1;
533 continue;
534 }
535 }
536 }
537
538 prev_pos = i;
539
540 if (bcj_x86_test_msbyte(buf[i + 4])) {
541 src = get_unaligned_le32(buf + i + 1);
542 for (;;) {
543 dest = src - (s->pos + (uint32_t)i + 5);
544 if (prev_mask == 0)
545 break;
546
547 j = mask_to_bit_num[prev_mask] * 8;
548 b = (uint8_t)(dest >> (24 - j));
549 if (!bcj_x86_test_msbyte(b))
550 break;
551
552 src = dest ^ (((uint32_t)1 << (32 - j)) - 1);
553 }
554
555 dest &= 0x01FFFFFF;
556 dest |= (uint32_t)0 - (dest & 0x01000000);
557 put_unaligned_le32(dest, buf + i + 1);
558 i += 4;
559 } else {
560 prev_mask = (prev_mask << 1) | 1;
561 }
562 }
563
564 prev_pos = i - prev_pos;
565 s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1);
566 return i;
567}
568#endif
569
570#ifdef XZ_DEC_POWERPC
571static size_t bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
572{
573 size_t i;
574 uint32_t instr;
575
576 for (i = 0; i + 4 <= size; i += 4) {
577 instr = get_unaligned_be32(buf + i);
578 if ((instr & 0xFC000003) == 0x48000001) {
579 instr &= 0x03FFFFFC;
580 instr -= s->pos + (uint32_t)i;
581 instr &= 0x03FFFFFC;
582 instr |= 0x48000001;
583 put_unaligned_be32(instr, buf + i);
584 }
585 }
586
587 return i;
588}
589#endif
590
591#ifdef XZ_DEC_IA64
592static size_t bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
593{
594 static const uint8_t branch_table[32] = {
595 0, 0, 0, 0, 0, 0, 0, 0,
596 0, 0, 0, 0, 0, 0, 0, 0,
597 4, 4, 6, 6, 0, 0, 7, 7,
598 4, 4, 0, 0, 4, 4, 0, 0
599 };
600
601
602
603
604
605
606
607
608 size_t i;
609 size_t j;
610
611
612 uint32_t slot;
613
614
615 uint32_t bit_pos;
616
617
618 uint32_t byte_pos;
619 uint32_t bit_res;
620
621
622 uint32_t addr;
623
624
625 uint32_t mask;
626
627
628 uint64_t instr;
629
630
631 uint64_t norm;
632
633 for (i = 0; i + 16 <= size; i += 16) {
634 mask = branch_table[buf[i] & 0x1F];
635 for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) {
636 if (((mask >> slot) & 1) == 0)
637 continue;
638
639 byte_pos = bit_pos >> 3;
640 bit_res = bit_pos & 7;
641 instr = 0;
642 for (j = 0; j < 6; ++j)
643 instr |= (uint64_t)(buf[i + j + byte_pos])
644 << (8 * j);
645
646 norm = instr >> bit_res;
647
648 if (((norm >> 37) & 0x0F) == 0x05
649 && ((norm >> 9) & 0x07) == 0) {
650 addr = (norm >> 13) & 0x0FFFFF;
651 addr |= ((uint32_t)(norm >> 36) & 1) << 20;
652 addr <<= 4;
653 addr -= s->pos + (uint32_t)i;
654 addr >>= 4;
655
656 norm &= ~((uint64_t)0x8FFFFF << 13);
657 norm |= (uint64_t)(addr & 0x0FFFFF) << 13;
658 norm |= (uint64_t)(addr & 0x100000)
659 << (36 - 20);
660
661 instr &= (1 << bit_res) - 1;
662 instr |= norm << bit_res;
663
664 for (j = 0; j < 6; j++)
665 buf[i + j + byte_pos]
666 = (uint8_t)(instr >> (8 * j));
667 }
668 }
669 }
670
671 return i;
672}
673#endif
674
675#ifdef XZ_DEC_ARM
676static size_t bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
677{
678 size_t i;
679 uint32_t addr;
680
681 for (i = 0; i + 4 <= size; i += 4) {
682 if (buf[i + 3] == 0xEB) {
683 addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8)
684 | ((uint32_t)buf[i + 2] << 16);
685 addr <<= 2;
686 addr -= s->pos + (uint32_t)i + 8;
687 addr >>= 2;
688 buf[i] = (uint8_t)addr;
689 buf[i + 1] = (uint8_t)(addr >> 8);
690 buf[i + 2] = (uint8_t)(addr >> 16);
691 }
692 }
693
694 return i;
695}
696#endif
697
698#ifdef XZ_DEC_ARMTHUMB
699static size_t bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
700{
701 size_t i;
702 uint32_t addr;
703
704 for (i = 0; i + 4 <= size; i += 2) {
705 if ((buf[i + 1] & 0xF8) == 0xF0
706 && (buf[i + 3] & 0xF8) == 0xF8) {
707 addr = (((uint32_t)buf[i + 1] & 0x07) << 19)
708 | ((uint32_t)buf[i] << 11)
709 | (((uint32_t)buf[i + 3] & 0x07) << 8)
710 | (uint32_t)buf[i + 2];
711 addr <<= 1;
712 addr -= s->pos + (uint32_t)i + 4;
713 addr >>= 1;
714 buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07));
715 buf[i] = (uint8_t)(addr >> 11);
716 buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07));
717 buf[i + 2] = (uint8_t)addr;
718 i += 2;
719 }
720 }
721
722 return i;
723}
724#endif
725
726#ifdef XZ_DEC_SPARC
727static size_t bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
728{
729 size_t i;
730 uint32_t instr;
731
732 for (i = 0; i + 4 <= size; i += 4) {
733 instr = get_unaligned_be32(buf + i);
734 if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) {
735 instr <<= 2;
736 instr -= s->pos + (uint32_t)i;
737 instr >>= 2;
738 instr = ((uint32_t)0x40000000 - (instr & 0x400000))
739 | 0x40000000 | (instr & 0x3FFFFF);
740 put_unaligned_be32(instr, buf + i);
741 }
742 }
743
744 return i;
745}
746#endif
747
748
749
750
751
752
753
754
755
756static void bcj_apply(struct xz_dec_bcj *s,
757 uint8_t *buf, size_t *pos, size_t size)
758{
759 size_t filtered;
760
761 buf += *pos;
762 size -= *pos;
763
764 switch (s->type) {
765#ifdef XZ_DEC_X86
766 case BCJ_X86:
767 filtered = bcj_x86(s, buf, size);
768 break;
769#endif
770#ifdef XZ_DEC_POWERPC
771 case BCJ_POWERPC:
772 filtered = bcj_powerpc(s, buf, size);
773 break;
774#endif
775#ifdef XZ_DEC_IA64
776 case BCJ_IA64:
777 filtered = bcj_ia64(s, buf, size);
778 break;
779#endif
780#ifdef XZ_DEC_ARM
781 case BCJ_ARM:
782 filtered = bcj_arm(s, buf, size);
783 break;
784#endif
785#ifdef XZ_DEC_ARMTHUMB
786 case BCJ_ARMTHUMB:
787 filtered = bcj_armthumb(s, buf, size);
788 break;
789#endif
790#ifdef XZ_DEC_SPARC
791 case BCJ_SPARC:
792 filtered = bcj_sparc(s, buf, size);
793 break;
794#endif
795 default:
796
797 filtered = 0;
798 break;
799 }
800
801 *pos += filtered;
802 s->pos += filtered;
803}
804
805
806
807
808
809
810static void bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b)
811{
812 size_t copy_size;
813
814 copy_size = minof(s->temp.filtered, b->out_size - b->out_pos);
815 memcpy(b->out + b->out_pos, s->temp.buf, copy_size);
816 b->out_pos += copy_size;
817
818 s->temp.filtered -= copy_size;
819 s->temp.size -= copy_size;
820 memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size);
821}
822
823
824
825
826
827
828enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s,
829 struct xz_dec_lzma2 *lzma2,
830 struct xz_buf *b)
831{
832 size_t out_start;
833
834
835
836
837
838
839 if (s->temp.filtered > 0) {
840 bcj_flush(s, b);
841 if (s->temp.filtered > 0)
842 return XZ_OK;
843
844 if (s->ret == XZ_STREAM_END)
845 return XZ_STREAM_END;
846 }
847
848
849
850
851
852
853
854
855
856
857
858
859
860 if (s->temp.size < b->out_size - b->out_pos || s->temp.size == 0) {
861 out_start = b->out_pos;
862 memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size);
863 b->out_pos += s->temp.size;
864
865 s->ret = xz_dec_lzma2_run(lzma2, b);
866 if (s->ret != XZ_STREAM_END
867 && (s->ret != XZ_OK ))
868 return s->ret;
869
870 bcj_apply(s, b->out, &out_start, b->out_pos);
871
872
873
874
875
876
877 if (s->ret == XZ_STREAM_END)
878 return XZ_STREAM_END;
879
880 s->temp.size = b->out_pos - out_start;
881 b->out_pos -= s->temp.size;
882 memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size);
883
884
885
886
887
888
889 if (b->out_pos + s->temp.size < b->out_size)
890 return XZ_OK;
891 }
892
893
894
895
896
897
898
899
900
901 if (b->out_pos < b->out_size) {
902
903 s->out = b->out;
904 s->out_pos = b->out_pos;
905 s->out_size = b->out_size;
906 b->out = s->temp.buf;
907 b->out_pos = s->temp.size;
908 b->out_size = sizeof(s->temp.buf);
909
910 s->ret = xz_dec_lzma2_run(lzma2, b);
911
912 s->temp.size = b->out_pos;
913 b->out = s->out;
914 b->out_pos = s->out_pos;
915 b->out_size = s->out_size;
916
917 if (s->ret != XZ_OK && s->ret != XZ_STREAM_END)
918 return s->ret;
919
920 bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size);
921
922
923
924
925
926
927 if (s->ret == XZ_STREAM_END)
928 s->temp.filtered = s->temp.size;
929
930 bcj_flush(s, b);
931 if (s->temp.filtered > 0)
932 return XZ_OK;
933 }
934
935 return s->ret;
936}
937
938enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id)
939{
940 switch (id) {
941#ifdef XZ_DEC_X86
942 case BCJ_X86:
943#endif
944#ifdef XZ_DEC_POWERPC
945 case BCJ_POWERPC:
946#endif
947#ifdef XZ_DEC_IA64
948 case BCJ_IA64:
949#endif
950#ifdef XZ_DEC_ARM
951 case BCJ_ARM:
952#endif
953#ifdef XZ_DEC_ARMTHUMB
954 case BCJ_ARMTHUMB:
955#endif
956#ifdef XZ_DEC_SPARC
957 case BCJ_SPARC:
958#endif
959 break;
960
961 default:
962
963 return XZ_OPTIONS_ERROR;
964 }
965
966 s->type = id;
967 s->ret = XZ_OK;
968 s->pos = 0;
969 s->x86_prev_mask = 0;
970 s->temp.filtered = 0;
971 s->temp.size = 0;
972
973 return XZ_OK;
974}
975
976#endif
977
978
979
980
981
982
983
984
985
986
987
988
989
990#define RC_SHIFT_BITS 8
991#define RC_TOP_BITS 24
992#define RC_TOP_VALUE (1 << RC_TOP_BITS)
993#define RC_BIT_MODEL_TOTAL_BITS 11
994#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
995#define RC_MOVE_BITS 5
996
997
998
999
1000
1001
1002#define POS_STATES_MAX (1 << 4)
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017enum lzma_state {
1018 STATE_LIT_LIT,
1019 STATE_MATCH_LIT_LIT,
1020 STATE_REP_LIT_LIT,
1021 STATE_SHORTREP_LIT_LIT,
1022 STATE_MATCH_LIT,
1023 STATE_REP_LIT,
1024 STATE_SHORTREP_LIT,
1025 STATE_LIT_MATCH,
1026 STATE_LIT_LONGREP,
1027 STATE_LIT_SHORTREP,
1028 STATE_NONLIT_MATCH,
1029 STATE_NONLIT_REP
1030};
1031
1032
1033#define STATES 12
1034
1035
1036#define LIT_STATES 7
1037
1038
1039static inline void lzma_state_literal(enum lzma_state *state)
1040{
1041 if (*state <= STATE_SHORTREP_LIT_LIT)
1042 *state = STATE_LIT_LIT;
1043 else if (*state <= STATE_LIT_SHORTREP)
1044 *state -= 3;
1045 else
1046 *state -= 6;
1047}
1048
1049
1050static inline void lzma_state_match(enum lzma_state *state)
1051{
1052 *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
1053}
1054
1055
1056static inline void lzma_state_long_rep(enum lzma_state *state)
1057{
1058 *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
1059}
1060
1061
1062static inline void lzma_state_short_rep(enum lzma_state *state)
1063{
1064 *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
1065}
1066
1067
1068static inline int lzma_state_is_literal(enum lzma_state state)
1069{
1070 return state < LIT_STATES;
1071}
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081#define LITERAL_CODER_SIZE 0x300
1082
1083
1084#define LITERAL_CODERS_MAX (1 << 4)
1085
1086
1087#define MATCH_LEN_MIN 2
1088
1089
1090
1091
1092
1093
1094
1095
1096#define LEN_LOW_BITS 3
1097#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
1098#define LEN_MID_BITS 3
1099#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
1100#define LEN_HIGH_BITS 8
1101#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
1102#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
1103
1104
1105
1106
1107
1108#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
1109
1110
1111
1112
1113
1114
1115
1116#define DIST_STATES 4
1117
1118
1119
1120
1121
1122static inline uint32_t lzma_get_dist_state(uint32_t len)
1123{
1124 return len < DIST_STATES + MATCH_LEN_MIN
1125 ? len - MATCH_LEN_MIN : DIST_STATES - 1;
1126}
1127
1128
1129
1130
1131
1132
1133#define DIST_SLOT_BITS 6
1134#define DIST_SLOTS (1 << DIST_SLOT_BITS)
1135
1136
1137
1138
1139
1140
1141
1142
1143#define DIST_MODEL_START 4
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155#define DIST_MODEL_END 14
1156
1157
1158#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
1159#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
1160
1161
1162
1163
1164
1165#define ALIGN_BITS 4
1166#define ALIGN_SIZE (1 << ALIGN_BITS)
1167#define ALIGN_MASK (ALIGN_SIZE - 1)
1168
1169
1170#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
1171
1172
1173
1174
1175
1176
1177#define REPS 4
1178
1179
1180
1181
1182
1183
1184
1185#define RC_INIT_BYTES 5
1186
1187
1188
1189
1190
1191
1192
1193
1194#define LZMA_IN_REQUIRED 21
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210struct dictionary {
1211
1212 uint8_t *buf;
1213
1214
1215 size_t start;
1216
1217
1218 size_t pos;
1219
1220
1221
1222
1223
1224 size_t full;
1225
1226
1227 size_t limit;
1228
1229
1230 size_t end;
1231
1232
1233
1234
1235
1236
1237 uint32_t size;
1238
1239
1240
1241
1242 uint32_t size_max;
1243
1244
1245
1246
1247 uint32_t allocated;
1248};
1249
1250
1251struct rc_dec {
1252 uint32_t range;
1253 uint32_t code;
1254
1255
1256
1257
1258
1259 uint32_t init_bytes_left;
1260
1261
1262
1263
1264
1265 const uint8_t *in;
1266 size_t in_pos;
1267 size_t in_limit;
1268};
1269
1270
1271struct lzma_len_dec {
1272
1273 uint16_t choice;
1274
1275
1276 uint16_t choice2;
1277
1278
1279 uint16_t low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
1280
1281
1282 uint16_t mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
1283
1284
1285 uint16_t high[LEN_HIGH_SYMBOLS];
1286};
1287
1288struct lzma_dec {
1289
1290 uint32_t rep0;
1291 uint32_t rep1;
1292 uint32_t rep2;
1293 uint32_t rep3;
1294
1295
1296 enum lzma_state state;
1297
1298
1299
1300
1301
1302 uint32_t len;
1303
1304
1305
1306
1307
1308
1309
1310 uint32_t lc;
1311 uint32_t literal_pos_mask;
1312 uint32_t pos_mask;
1313
1314
1315 uint16_t is_match[STATES][POS_STATES_MAX];
1316
1317
1318 uint16_t is_rep[STATES];
1319
1320
1321
1322
1323
1324 uint16_t is_rep0[STATES];
1325
1326
1327
1328
1329
1330 uint16_t is_rep1[STATES];
1331
1332
1333 uint16_t is_rep2[STATES];
1334
1335
1336
1337
1338
1339 uint16_t is_rep0_long[STATES][POS_STATES_MAX];
1340
1341
1342
1343
1344
1345
1346 uint16_t dist_slot[DIST_STATES][DIST_SLOTS];
1347
1348
1349
1350
1351
1352 uint16_t dist_special[FULL_DISTANCES - DIST_MODEL_END];
1353
1354
1355
1356
1357
1358 uint16_t dist_align[ALIGN_SIZE];
1359
1360
1361 struct lzma_len_dec match_len_dec;
1362
1363
1364 struct lzma_len_dec rep_len_dec;
1365
1366
1367 uint16_t literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE];
1368};
1369
1370struct lzma2_dec {
1371
1372 enum lzma2_seq {
1373 SEQ_CONTROL,
1374 SEQ_UNCOMPRESSED_1,
1375 SEQ_UNCOMPRESSED_2,
1376 SEQ_COMPRESSED_0,
1377 SEQ_COMPRESSED_1,
1378 SEQ_PROPERTIES,
1379 SEQ_LZMA_PREPARE,
1380 SEQ_LZMA_RUN,
1381 SEQ_COPY
1382 } sequence;
1383
1384
1385 enum lzma2_seq next_sequence;
1386
1387
1388 uint32_t uncompressed;
1389
1390
1391
1392
1393
1394 uint32_t compressed;
1395
1396
1397
1398
1399
1400 int need_dict_reset;
1401
1402
1403
1404
1405
1406 int need_props;
1407};
1408
1409struct xz_dec_lzma2 {
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419 struct rc_dec rc;
1420 struct dictionary dict;
1421 struct lzma2_dec lzma2;
1422 struct lzma_dec lzma;
1423
1424
1425
1426
1427
1428 struct {
1429 uint32_t size;
1430 uint8_t buf[3 * LZMA_IN_REQUIRED];
1431 } temp;
1432};
1433
1434
1435
1436
1437
1438
1439static void dict_reset(struct dictionary *dict)
1440{
1441 dict->start = 0;
1442 dict->pos = 0;
1443 dict->limit = 0;
1444 dict->full = 0;
1445}
1446
1447
1448static void dict_limit(struct dictionary *dict, size_t out_max)
1449{
1450 if (dict->end - dict->pos <= out_max)
1451 dict->limit = dict->end;
1452 else
1453 dict->limit = dict->pos + out_max;
1454}
1455
1456
1457static inline int dict_has_space(const struct dictionary *dict)
1458{
1459 return dict->pos < dict->limit;
1460}
1461
1462
1463
1464
1465
1466
1467
1468static inline uint32_t dict_get(const struct dictionary *dict, uint32_t dist)
1469{
1470 size_t offset = dict->pos - dist - 1;
1471
1472 if (dist >= dict->pos)
1473 offset += dict->end;
1474
1475 return dict->full > 0 ? dict->buf[offset] : 0;
1476}
1477
1478
1479
1480
1481static inline void dict_put(struct dictionary *dict, uint8_t byte)
1482{
1483 dict->buf[dict->pos++] = byte;
1484
1485 if (dict->full < dict->pos)
1486 dict->full = dict->pos;
1487}
1488
1489
1490
1491
1492
1493
1494static int dict_repeat(struct dictionary *dict, uint32_t *len, uint32_t dist)
1495{
1496 size_t back;
1497 uint32_t left;
1498
1499 if (dist >= dict->full || dist >= dict->size) return 0;
1500
1501 left = minof(dict->limit - dict->pos, *len);
1502 *len -= left;
1503
1504 back = dict->pos - dist - 1;
1505 if (dist >= dict->pos)
1506 back += dict->end;
1507
1508 do {
1509 dict->buf[dict->pos++] = dict->buf[back++];
1510 if (back == dict->end)
1511 back = 0;
1512 } while (--left > 0);
1513
1514 if (dict->full < dict->pos)
1515 dict->full = dict->pos;
1516
1517 return 1;
1518}
1519
1520
1521static void dict_uncompressed(struct dictionary *dict, struct xz_buf *b,
1522 uint32_t *left)
1523{
1524 size_t copy_size;
1525
1526 while (*left > 0 && b->in_pos < b->in_size
1527 && b->out_pos < b->out_size) {
1528 copy_size = minof(b->in_size - b->in_pos,
1529 b->out_size - b->out_pos);
1530 if (copy_size > dict->end - dict->pos)
1531 copy_size = dict->end - dict->pos;
1532 if (copy_size > *left)
1533 copy_size = *left;
1534
1535 *left -= copy_size;
1536
1537 memcpy(dict->buf + dict->pos, b->in + b->in_pos, copy_size);
1538 dict->pos += copy_size;
1539
1540 if (dict->full < dict->pos)
1541 dict->full = dict->pos;
1542
1543 if (dict->pos == dict->end)
1544 dict->pos = 0;
1545
1546 memcpy(b->out + b->out_pos, b->in + b->in_pos,
1547 copy_size);
1548
1549 dict->start = dict->pos;
1550
1551 b->out_pos += copy_size;
1552 b->in_pos += copy_size;
1553 }
1554}
1555
1556
1557
1558
1559
1560
1561static uint32_t dict_flush(struct dictionary *dict, struct xz_buf *b)
1562{
1563 size_t copy_size = dict->pos - dict->start;
1564
1565 if (dict->pos == dict->end)
1566 dict->pos = 0;
1567
1568 memcpy(b->out + b->out_pos, dict->buf + dict->start,
1569 copy_size);
1570
1571 dict->start = dict->pos;
1572 b->out_pos += copy_size;
1573 return copy_size;
1574}
1575
1576
1577
1578
1579
1580
1581static void rc_reset(struct rc_dec *rc)
1582{
1583 rc->range = (uint32_t)-1;
1584 rc->code = 0;
1585 rc->init_bytes_left = RC_INIT_BYTES;
1586}
1587
1588
1589
1590
1591
1592static int rc_read_init(struct rc_dec *rc, struct xz_buf *b)
1593{
1594 while (rc->init_bytes_left > 0) {
1595 if (b->in_pos == b->in_size) return 0;
1596
1597 rc->code = (rc->code << 8) + b->in[b->in_pos++];
1598 --rc->init_bytes_left;
1599 }
1600
1601 return 1;
1602}
1603
1604
1605static inline int rc_limit_exceeded(const struct rc_dec *rc)
1606{
1607 return rc->in_pos > rc->in_limit;
1608}
1609
1610
1611
1612
1613
1614static inline int rc_is_finished(const struct rc_dec *rc)
1615{
1616 return rc->code == 0;
1617}
1618
1619
1620static inline void rc_normalize(struct rc_dec *rc)
1621{
1622 if (rc->range < RC_TOP_VALUE) {
1623 rc->range <<= RC_SHIFT_BITS;
1624 rc->code = (rc->code << RC_SHIFT_BITS) + rc->in[rc->in_pos++];
1625 }
1626}
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639static inline int rc_bit(struct rc_dec *rc, uint16_t *prob)
1640{
1641 uint32_t bound;
1642 int bit;
1643
1644 rc_normalize(rc);
1645 bound = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) * *prob;
1646 if (rc->code < bound) {
1647 rc->range = bound;
1648 *prob += (RC_BIT_MODEL_TOTAL - *prob) >> RC_MOVE_BITS;
1649 bit = 0;
1650 } else {
1651 rc->range -= bound;
1652 rc->code -= bound;
1653 *prob -= *prob >> RC_MOVE_BITS;
1654 bit = 1;
1655 }
1656
1657 return bit;
1658}
1659
1660
1661static inline uint32_t rc_bittree(struct rc_dec *rc,
1662 uint16_t *probs, uint32_t limit)
1663{
1664 uint32_t symbol = 1;
1665
1666 do {
1667 if (rc_bit(rc, &probs[symbol]))
1668 symbol = (symbol << 1) + 1;
1669 else
1670 symbol <<= 1;
1671 } while (symbol < limit);
1672
1673 return symbol;
1674}
1675
1676
1677static inline void rc_bittree_reverse(struct rc_dec *rc,
1678 uint16_t *probs,
1679 uint32_t *dest, uint32_t limit)
1680{
1681 uint32_t symbol = 1;
1682 uint32_t i = 0;
1683
1684 do {
1685 if (rc_bit(rc, &probs[symbol])) {
1686 symbol = (symbol << 1) + 1;
1687 *dest += 1 << i;
1688 } else {
1689 symbol <<= 1;
1690 }
1691 } while (++i < limit);
1692}
1693
1694
1695static inline void rc_direct(struct rc_dec *rc, uint32_t *dest, uint32_t limit)
1696{
1697 uint32_t mask;
1698
1699 do {
1700 rc_normalize(rc);
1701 rc->range >>= 1;
1702 rc->code -= rc->range;
1703 mask = (uint32_t)0 - (rc->code >> 31);
1704 rc->code += rc->range & mask;
1705 *dest = (*dest << 1) + (mask + 1);
1706 } while (--limit > 0);
1707}
1708
1709
1710
1711
1712
1713
1714static uint16_t *lzma_literal_probs(struct xz_dec_lzma2 *s)
1715{
1716 uint32_t prev_byte = dict_get(&s->dict, 0);
1717 uint32_t low = prev_byte >> (8 - s->lzma.lc);
1718 uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc;
1719 return s->lzma.literal[low + high];
1720}
1721
1722
1723static void lzma_literal(struct xz_dec_lzma2 *s)
1724{
1725 uint16_t *probs;
1726 uint32_t symbol;
1727 uint32_t match_byte;
1728 uint32_t match_bit;
1729 uint32_t offset;
1730 uint32_t i;
1731
1732 probs = lzma_literal_probs(s);
1733
1734 if (lzma_state_is_literal(s->lzma.state)) {
1735 symbol = rc_bittree(&s->rc, probs, 0x100);
1736 } else {
1737 symbol = 1;
1738 match_byte = dict_get(&s->dict, s->lzma.rep0) << 1;
1739 offset = 0x100;
1740
1741 do {
1742 match_bit = match_byte & offset;
1743 match_byte <<= 1;
1744 i = offset + match_bit + symbol;
1745
1746 if (rc_bit(&s->rc, &probs[i])) {
1747 symbol = (symbol << 1) + 1;
1748 offset &= match_bit;
1749 } else {
1750 symbol <<= 1;
1751 offset &= ~match_bit;
1752 }
1753 } while (symbol < 0x100);
1754 }
1755
1756 dict_put(&s->dict, (uint8_t)symbol);
1757 lzma_state_literal(&s->lzma.state);
1758}
1759
1760
1761static void lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l,
1762 uint32_t pos_state)
1763{
1764 uint16_t *probs;
1765 uint32_t limit;
1766
1767 if (!rc_bit(&s->rc, &l->choice)) {
1768 probs = l->low[pos_state];
1769 limit = LEN_LOW_SYMBOLS;
1770 s->lzma.len = MATCH_LEN_MIN;
1771 } else {
1772 if (!rc_bit(&s->rc, &l->choice2)) {
1773 probs = l->mid[pos_state];
1774 limit = LEN_MID_SYMBOLS;
1775 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS;
1776 } else {
1777 probs = l->high;
1778 limit = LEN_HIGH_SYMBOLS;
1779 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS
1780 + LEN_MID_SYMBOLS;
1781 }
1782 }
1783
1784 s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit;
1785}
1786
1787
1788static void lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
1789{
1790 uint16_t *probs;
1791 uint32_t dist_slot;
1792 uint32_t limit;
1793
1794 lzma_state_match(&s->lzma.state);
1795
1796 s->lzma.rep3 = s->lzma.rep2;
1797 s->lzma.rep2 = s->lzma.rep1;
1798 s->lzma.rep1 = s->lzma.rep0;
1799
1800 lzma_len(s, &s->lzma.match_len_dec, pos_state);
1801
1802 probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)];
1803 dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS;
1804
1805 if (dist_slot < DIST_MODEL_START) {
1806 s->lzma.rep0 = dist_slot;
1807 } else {
1808 limit = (dist_slot >> 1) - 1;
1809 s->lzma.rep0 = 2 + (dist_slot & 1);
1810
1811 if (dist_slot < DIST_MODEL_END) {
1812 s->lzma.rep0 <<= limit;
1813 probs = s->lzma.dist_special + s->lzma.rep0
1814 - dist_slot - 1;
1815 rc_bittree_reverse(&s->rc, probs,
1816 &s->lzma.rep0, limit);
1817 } else {
1818 rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS);
1819 s->lzma.rep0 <<= ALIGN_BITS;
1820 rc_bittree_reverse(&s->rc, s->lzma.dist_align,
1821 &s->lzma.rep0, ALIGN_BITS);
1822 }
1823 }
1824}
1825
1826
1827
1828
1829
1830static void lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
1831{
1832 uint32_t tmp;
1833
1834 if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) {
1835 if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[
1836 s->lzma.state][pos_state])) {
1837 lzma_state_short_rep(&s->lzma.state);
1838 s->lzma.len = 1;
1839 return;
1840 }
1841 } else {
1842 if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) {
1843 tmp = s->lzma.rep1;
1844 } else {
1845 if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) {
1846 tmp = s->lzma.rep2;
1847 } else {
1848 tmp = s->lzma.rep3;
1849 s->lzma.rep3 = s->lzma.rep2;
1850 }
1851
1852 s->lzma.rep2 = s->lzma.rep1;
1853 }
1854
1855 s->lzma.rep1 = s->lzma.rep0;
1856 s->lzma.rep0 = tmp;
1857 }
1858
1859 lzma_state_long_rep(&s->lzma.state);
1860 lzma_len(s, &s->lzma.rep_len_dec, pos_state);
1861}
1862
1863
1864static int lzma_main(struct xz_dec_lzma2 *s)
1865{
1866 uint32_t pos_state;
1867
1868
1869
1870
1871
1872 if (dict_has_space(&s->dict) && s->lzma.len > 0)
1873 dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0);
1874
1875
1876
1877
1878
1879 while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) {
1880 pos_state = s->dict.pos & s->lzma.pos_mask;
1881
1882 if (!rc_bit(&s->rc, &s->lzma.is_match[
1883 s->lzma.state][pos_state])) {
1884 lzma_literal(s);
1885 } else {
1886 if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state]))
1887 lzma_rep_match(s, pos_state);
1888 else
1889 lzma_match(s, pos_state);
1890
1891 if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0))
1892 return 0;
1893 }
1894 }
1895
1896
1897
1898
1899
1900 rc_normalize(&s->rc);
1901
1902 return 1;
1903}
1904
1905
1906
1907
1908
1909static void lzma_reset(struct xz_dec_lzma2 *s)
1910{
1911 uint16_t *probs;
1912 size_t i;
1913
1914 s->lzma.state = STATE_LIT_LIT;
1915 s->lzma.rep0 = 0;
1916 s->lzma.rep1 = 0;
1917 s->lzma.rep2 = 0;
1918 s->lzma.rep3 = 0;
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929 probs = s->lzma.is_match[0];
1930 for (i = 0; i < PROBS_TOTAL; ++i)
1931 probs[i] = RC_BIT_MODEL_TOTAL / 2;
1932
1933 rc_reset(&s->rc);
1934}
1935
1936
1937
1938
1939
1940
1941static int lzma_props(struct xz_dec_lzma2 *s, uint8_t props)
1942{
1943 if (props > (4 * 5 + 4) * 9 + 8)
1944 return 0;
1945
1946 s->lzma.pos_mask = 0;
1947 while (props >= 9 * 5) {
1948 props -= 9 * 5;
1949 ++s->lzma.pos_mask;
1950 }
1951
1952 s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1;
1953
1954 s->lzma.literal_pos_mask = 0;
1955 while (props >= 9) {
1956 props -= 9;
1957 ++s->lzma.literal_pos_mask;
1958 }
1959
1960 s->lzma.lc = props;
1961
1962 if (s->lzma.lc + s->lzma.literal_pos_mask > 4)
1963 return 0;
1964
1965 s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1;
1966
1967 lzma_reset(s);
1968
1969 return 1;
1970}
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988static int lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b)
1989{
1990 size_t in_avail;
1991 uint32_t tmp;
1992
1993 in_avail = b->in_size - b->in_pos;
1994 if (s->temp.size > 0 || s->lzma2.compressed == 0) {
1995 tmp = 2 * LZMA_IN_REQUIRED - s->temp.size;
1996 if (tmp > s->lzma2.compressed - s->temp.size)
1997 tmp = s->lzma2.compressed - s->temp.size;
1998 if (tmp > in_avail)
1999 tmp = in_avail;
2000
2001 memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp);
2002
2003 if (s->temp.size + tmp == s->lzma2.compressed) {
2004 memset(s->temp.buf + s->temp.size + tmp, 0,
2005 sizeof(s->temp.buf)
2006 - s->temp.size - tmp);
2007 s->rc.in_limit = s->temp.size + tmp;
2008 } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) {
2009 s->temp.size += tmp;
2010 b->in_pos += tmp;
2011 return 1;
2012 } else {
2013 s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED;
2014 }
2015
2016 s->rc.in = s->temp.buf;
2017 s->rc.in_pos = 0;
2018
2019 if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp)
2020 return 0;
2021
2022 s->lzma2.compressed -= s->rc.in_pos;
2023
2024 if (s->rc.in_pos < s->temp.size) {
2025 s->temp.size -= s->rc.in_pos;
2026 memmove(s->temp.buf, s->temp.buf + s->rc.in_pos,
2027 s->temp.size);
2028 return 1;
2029 }
2030
2031 b->in_pos += s->rc.in_pos - s->temp.size;
2032 s->temp.size = 0;
2033 }
2034
2035 in_avail = b->in_size - b->in_pos;
2036 if (in_avail >= LZMA_IN_REQUIRED) {
2037 s->rc.in = b->in;
2038 s->rc.in_pos = b->in_pos;
2039
2040 if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED)
2041 s->rc.in_limit = b->in_pos + s->lzma2.compressed;
2042 else
2043 s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED;
2044
2045 if (!lzma_main(s))
2046 return 0;
2047
2048 in_avail = s->rc.in_pos - b->in_pos;
2049 if (in_avail > s->lzma2.compressed) return 0;
2050
2051 s->lzma2.compressed -= in_avail;
2052 b->in_pos = s->rc.in_pos;
2053 }
2054
2055 in_avail = b->in_size - b->in_pos;
2056 if (in_avail < LZMA_IN_REQUIRED) {
2057 if (in_avail > s->lzma2.compressed)
2058 in_avail = s->lzma2.compressed;
2059
2060 memcpy(s->temp.buf, b->in + b->in_pos, in_avail);
2061 s->temp.size = in_avail;
2062 b->in_pos += in_avail;
2063 }
2064
2065 return 1;
2066}
2067
2068
2069
2070
2071
2072enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
2073 struct xz_buf *b)
2074{
2075 uint32_t tmp;
2076
2077 while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) {
2078 switch (s->lzma2.sequence) {
2079 case SEQ_CONTROL:
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111 tmp = b->in[b->in_pos++];
2112
2113 if (tmp == 0x00)
2114 return XZ_STREAM_END;
2115
2116 if (tmp >= 0xE0 || tmp == 0x01) {
2117 s->lzma2.need_props = 1;
2118 s->lzma2.need_dict_reset = 0;
2119 dict_reset(&s->dict);
2120 } else if (s->lzma2.need_dict_reset) {
2121 return XZ_DATA_ERROR;
2122 }
2123
2124 if (tmp >= 0x80) {
2125 s->lzma2.uncompressed = (tmp & 0x1F) << 16;
2126 s->lzma2.sequence = SEQ_UNCOMPRESSED_1;
2127
2128 if (tmp >= 0xC0) {
2129
2130
2131
2132
2133
2134 s->lzma2.need_props = 0;
2135 s->lzma2.next_sequence
2136 = SEQ_PROPERTIES;
2137
2138 } else if (s->lzma2.need_props) {
2139 return XZ_DATA_ERROR;
2140
2141 } else {
2142 s->lzma2.next_sequence
2143 = SEQ_LZMA_PREPARE;
2144 if (tmp >= 0xA0)
2145 lzma_reset(s);
2146 }
2147 } else {
2148 if (tmp > 0x02)
2149 return XZ_DATA_ERROR;
2150
2151 s->lzma2.sequence = SEQ_COMPRESSED_0;
2152 s->lzma2.next_sequence = SEQ_COPY;
2153 }
2154
2155 break;
2156
2157 case SEQ_UNCOMPRESSED_1:
2158 s->lzma2.uncompressed
2159 += (uint32_t)b->in[b->in_pos++] << 8;
2160 s->lzma2.sequence = SEQ_UNCOMPRESSED_2;
2161 break;
2162
2163 case SEQ_UNCOMPRESSED_2:
2164 s->lzma2.uncompressed
2165 += (uint32_t)b->in[b->in_pos++] + 1;
2166 s->lzma2.sequence = SEQ_COMPRESSED_0;
2167 break;
2168
2169 case SEQ_COMPRESSED_0:
2170 s->lzma2.compressed
2171 = (uint32_t)b->in[b->in_pos++] << 8;
2172 s->lzma2.sequence = SEQ_COMPRESSED_1;
2173 break;
2174
2175 case SEQ_COMPRESSED_1:
2176 s->lzma2.compressed
2177 += (uint32_t)b->in[b->in_pos++] + 1;
2178 s->lzma2.sequence = s->lzma2.next_sequence;
2179 break;
2180
2181 case SEQ_PROPERTIES:
2182 if (!lzma_props(s, b->in[b->in_pos++]))
2183 return XZ_DATA_ERROR;
2184
2185 s->lzma2.sequence = SEQ_LZMA_PREPARE;
2186
2187 case SEQ_LZMA_PREPARE:
2188 if (s->lzma2.compressed < RC_INIT_BYTES)
2189 return XZ_DATA_ERROR;
2190
2191 if (!rc_read_init(&s->rc, b))
2192 return XZ_OK;
2193
2194 s->lzma2.compressed -= RC_INIT_BYTES;
2195 s->lzma2.sequence = SEQ_LZMA_RUN;
2196
2197 case SEQ_LZMA_RUN:
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207 dict_limit(&s->dict, minof(b->out_size - b->out_pos,
2208 s->lzma2.uncompressed));
2209 if (!lzma2_lzma(s, b))
2210 return XZ_DATA_ERROR;
2211
2212 s->lzma2.uncompressed -= dict_flush(&s->dict, b);
2213
2214 if (s->lzma2.uncompressed == 0) {
2215 if (s->lzma2.compressed > 0 || s->lzma.len > 0
2216 || !rc_is_finished(&s->rc))
2217 return XZ_DATA_ERROR;
2218
2219 rc_reset(&s->rc);
2220 s->lzma2.sequence = SEQ_CONTROL;
2221
2222 } else if (b->out_pos == b->out_size
2223 || (b->in_pos == b->in_size
2224 && s->temp.size
2225 < s->lzma2.compressed)) {
2226 return XZ_OK;
2227 }
2228
2229 break;
2230
2231 case SEQ_COPY:
2232 dict_uncompressed(&s->dict, b, &s->lzma2.compressed);
2233 if (s->lzma2.compressed > 0)
2234 return XZ_OK;
2235
2236 s->lzma2.sequence = SEQ_CONTROL;
2237 break;
2238 }
2239 }
2240
2241 return XZ_OK;
2242}
2243
2244struct xz_dec_lzma2 *xz_dec_lzma2_create(uint32_t dict_max)
2245{
2246 struct xz_dec_lzma2 *s = malloc(sizeof(*s));
2247 if (s == NULL)
2248 return NULL;
2249
2250 s->dict.size_max = dict_max;
2251 s->dict.buf = NULL;
2252 s->dict.allocated = 0;
2253
2254 return s;
2255}
2256
2257enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props)
2258{
2259
2260 if (props > 39)
2261 return XZ_OPTIONS_ERROR;
2262
2263 s->dict.size = 2 + (props & 1);
2264 s->dict.size <<= (props >> 1) + 11;
2265
2266 if (s->dict.size > s->dict.size_max)
2267 return XZ_MEMLIMIT_ERROR;
2268
2269 s->dict.end = s->dict.size;
2270
2271 if (s->dict.allocated < s->dict.size) {
2272 free(s->dict.buf);
2273 s->dict.buf = malloc(s->dict.size);
2274 if (s->dict.buf == NULL) {
2275 s->dict.allocated = 0;
2276 return XZ_MEM_ERROR;
2277 }
2278 }
2279
2280 s->lzma.len = 0;
2281
2282 s->lzma2.sequence = SEQ_CONTROL;
2283 s->lzma2.need_dict_reset = 1;
2284
2285 s->temp.size = 0;
2286
2287 return XZ_OK;
2288}
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306#define STREAM_HEADER_SIZE 12
2307
2308#define HEADER_MAGIC "\3757zXZ"
2309#define HEADER_MAGIC_SIZE 6
2310
2311#define FOOTER_MAGIC "YZ"
2312#define FOOTER_MAGIC_SIZE 2
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323typedef uint64_t vli_type;
2324
2325#define VLI_MAX ((vli_type)-1 / 2)
2326#define VLI_UNKNOWN ((vli_type)-1)
2327
2328
2329#define VLI_BYTES_MAX (sizeof(vli_type) * 8 / 7)
2330
2331
2332enum xz_check {
2333 XZ_CHECK_NONE = 0,
2334 XZ_CHECK_CRC32 = 1,
2335 XZ_CHECK_CRC64 = 4,
2336 XZ_CHECK_SHA256 = 10
2337};
2338
2339
2340#define XZ_CHECK_MAX 15
2341
2342
2343#define IS_CRC64(check_type) ((check_type) == XZ_CHECK_CRC64)
2344
2345
2346struct xz_dec_hash {
2347 vli_type unpadded;
2348 vli_type uncompressed;
2349 uint32_t crc32;
2350};
2351
2352struct xz_dec {
2353
2354 enum {
2355 SEQ_STREAM_HEADER,
2356 SEQ_BLOCK_START,
2357 SEQ_BLOCK_HEADER,
2358 SEQ_BLOCK_UNCOMPRESS,
2359 SEQ_BLOCK_PADDING,
2360 SEQ_BLOCK_CHECK,
2361 SEQ_INDEX,
2362 SEQ_INDEX_PADDING,
2363 SEQ_INDEX_CRC32,
2364 SEQ_STREAM_FOOTER
2365 } sequence;
2366
2367
2368 uint32_t pos;
2369
2370
2371 vli_type vli;
2372
2373
2374 size_t in_start;
2375 size_t out_start;
2376
2377
2378 uint64_t crc;
2379
2380
2381 enum xz_check check_type;
2382
2383
2384
2385
2386
2387 int allow_buf_error;
2388
2389
2390 struct {
2391
2392
2393
2394
2395 vli_type compressed;
2396
2397
2398
2399
2400
2401 vli_type uncompressed;
2402
2403
2404 uint32_t size;
2405 } block_header;
2406
2407
2408 struct {
2409
2410 vli_type compressed;
2411
2412
2413 vli_type uncompressed;
2414
2415
2416 vli_type count;
2417
2418
2419
2420
2421
2422 struct xz_dec_hash hash;
2423 } block;
2424
2425
2426 struct {
2427
2428 enum {
2429 SEQ_INDEX_COUNT,
2430 SEQ_INDEX_UNPADDED,
2431 SEQ_INDEX_UNCOMPRESSED
2432 } sequence;
2433
2434
2435 vli_type size;
2436
2437
2438 vli_type count;
2439
2440
2441
2442
2443
2444 struct xz_dec_hash hash;
2445 } index;
2446
2447
2448
2449
2450
2451
2452
2453
2454 struct {
2455 size_t pos;
2456 size_t size;
2457 uint8_t buf[1024];
2458 } temp;
2459
2460 struct xz_dec_lzma2 *lzma2;
2461
2462#ifdef XZ_DEC_BCJ
2463 struct xz_dec_bcj *bcj;
2464 int bcj_active;
2465#endif
2466};
2467
2468
2469static const uint8_t check_sizes[16] = {
2470 0,
2471 4, 4, 4,
2472 8, 8, 8,
2473 16, 16, 16,
2474 32, 32, 32,
2475 64, 64, 64
2476};
2477
2478
2479
2480
2481
2482
2483
2484static int fill_temp(struct xz_dec *s, struct xz_buf *b)
2485{
2486 size_t copy_size = minof(b->in_size - b->in_pos, s->temp.size - s->temp.pos);
2487
2488 memcpy(s->temp.buf + s->temp.pos, b->in + b->in_pos, copy_size);
2489 b->in_pos += copy_size;
2490 s->temp.pos += copy_size;
2491
2492 if (s->temp.pos == s->temp.size) {
2493 s->temp.pos = 0;
2494 return 1;
2495 }
2496
2497 return 0;
2498}
2499
2500
2501static enum xz_ret dec_vli(struct xz_dec *s, const uint8_t *in,
2502 size_t *in_pos, size_t in_size)
2503{
2504 uint8_t byte;
2505
2506 if (s->pos == 0)
2507 s->vli = 0;
2508
2509 while (*in_pos < in_size) {
2510 byte = in[*in_pos];
2511 ++*in_pos;
2512
2513 s->vli |= (vli_type)(byte & 0x7F) << s->pos;
2514
2515 if ((byte & 0x80) == 0) {
2516
2517 if (byte == 0 && s->pos != 0)
2518 return XZ_DATA_ERROR;
2519
2520 s->pos = 0;
2521 return XZ_STREAM_END;
2522 }
2523
2524 s->pos += 7;
2525 if (s->pos == 7 * VLI_BYTES_MAX)
2526 return XZ_DATA_ERROR;
2527 }
2528
2529 return XZ_OK;
2530}
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544static enum xz_ret dec_block(struct xz_dec *s, struct xz_buf *b)
2545{
2546 enum xz_ret ret;
2547
2548 s->in_start = b->in_pos;
2549 s->out_start = b->out_pos;
2550
2551#ifdef XZ_DEC_BCJ
2552 if (s->bcj_active)
2553 ret = xz_dec_bcj_run(s->bcj, s->lzma2, b);
2554 else
2555#endif
2556 ret = xz_dec_lzma2_run(s->lzma2, b);
2557
2558 s->block.compressed += b->in_pos - s->in_start;
2559 s->block.uncompressed += b->out_pos - s->out_start;
2560
2561
2562
2563
2564
2565 if (s->block.compressed > s->block_header.compressed
2566 || s->block.uncompressed
2567 > s->block_header.uncompressed)
2568 return XZ_DATA_ERROR;
2569
2570 if (s->check_type == XZ_CHECK_CRC32)
2571 s->crc = xz_crc32(b->out + s->out_start,
2572 b->out_pos - s->out_start, s->crc);
2573 else if (s->check_type == XZ_CHECK_CRC64) {
2574 s->crc = ~(s->crc);
2575 size_t size = b->out_pos - s->out_start;
2576 uint8_t *buf = b->out + s->out_start;
2577 while (size) {
2578 s->crc = xz_crc64_table[*buf++ ^ (s->crc & 0xFF)] ^ (s->crc >> 8);
2579 --size;
2580 }
2581 s->crc=~(s->crc);
2582 }
2583
2584 if (ret == XZ_STREAM_END) {
2585 if (s->block_header.compressed != VLI_UNKNOWN
2586 && s->block_header.compressed
2587 != s->block.compressed)
2588 return XZ_DATA_ERROR;
2589
2590 if (s->block_header.uncompressed != VLI_UNKNOWN
2591 && s->block_header.uncompressed
2592 != s->block.uncompressed)
2593 return XZ_DATA_ERROR;
2594
2595 s->block.hash.unpadded += s->block_header.size
2596 + s->block.compressed;
2597
2598 s->block.hash.unpadded += check_sizes[s->check_type];
2599
2600 s->block.hash.uncompressed += s->block.uncompressed;
2601 s->block.hash.crc32 = xz_crc32(
2602 (const uint8_t *)&s->block.hash,
2603 sizeof(s->block.hash), s->block.hash.crc32);
2604
2605 ++s->block.count;
2606 }
2607
2608 return ret;
2609}
2610
2611
2612static void index_update(struct xz_dec *s, const struct xz_buf *b)
2613{
2614 size_t in_used = b->in_pos - s->in_start;
2615 s->index.size += in_used;
2616 s->crc = xz_crc32(b->in + s->in_start, in_used, s->crc);
2617}
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627static enum xz_ret dec_index(struct xz_dec *s, struct xz_buf *b)
2628{
2629 enum xz_ret ret;
2630
2631 do {
2632 ret = dec_vli(s, b->in, &b->in_pos, b->in_size);
2633 if (ret != XZ_STREAM_END) {
2634 index_update(s, b);
2635 return ret;
2636 }
2637
2638 switch (s->index.sequence) {
2639 case SEQ_INDEX_COUNT:
2640 s->index.count = s->vli;
2641
2642
2643
2644
2645
2646
2647 if (s->index.count != s->block.count)
2648 return XZ_DATA_ERROR;
2649
2650 s->index.sequence = SEQ_INDEX_UNPADDED;
2651 break;
2652
2653 case SEQ_INDEX_UNPADDED:
2654 s->index.hash.unpadded += s->vli;
2655 s->index.sequence = SEQ_INDEX_UNCOMPRESSED;
2656 break;
2657
2658 case SEQ_INDEX_UNCOMPRESSED:
2659 s->index.hash.uncompressed += s->vli;
2660 s->index.hash.crc32 = xz_crc32(
2661 (const uint8_t *)&s->index.hash,
2662 sizeof(s->index.hash),
2663 s->index.hash.crc32);
2664 --s->index.count;
2665 s->index.sequence = SEQ_INDEX_UNPADDED;
2666 break;
2667 }
2668 } while (s->index.count > 0);
2669
2670 return XZ_STREAM_END;
2671}
2672
2673
2674
2675
2676
2677
2678static enum xz_ret crc_validate(struct xz_dec *s, struct xz_buf *b,
2679 uint32_t bits)
2680{
2681 do {
2682 if (b->in_pos == b->in_size)
2683 return XZ_OK;
2684
2685 if (((s->crc >> s->pos) & 0xFF) != b->in[b->in_pos++])
2686 return XZ_DATA_ERROR;
2687
2688 s->pos += 8;
2689
2690 } while (s->pos < bits);
2691
2692 s->crc = 0;
2693 s->pos = 0;
2694
2695 return XZ_STREAM_END;
2696}
2697
2698
2699
2700
2701
2702static int check_skip(struct xz_dec *s, struct xz_buf *b)
2703{
2704 while (s->pos < check_sizes[s->check_type]) {
2705 if (b->in_pos == b->in_size) return 0;
2706
2707 ++b->in_pos;
2708 ++s->pos;
2709 }
2710
2711 s->pos = 0;
2712
2713 return 1;
2714}
2715
2716
2717static enum xz_ret dec_stream_header(struct xz_dec *s)
2718{
2719 if (!memeq(s->temp.buf, HEADER_MAGIC, HEADER_MAGIC_SIZE))
2720 return XZ_FORMAT_ERROR;
2721
2722 if (xz_crc32(s->temp.buf + HEADER_MAGIC_SIZE, 2, 0)
2723 != get_le32(s->temp.buf + HEADER_MAGIC_SIZE + 2))
2724 return XZ_DATA_ERROR;
2725
2726 if (s->temp.buf[HEADER_MAGIC_SIZE] != 0)
2727 return XZ_OPTIONS_ERROR;
2728
2729
2730
2731
2732
2733
2734
2735
2736 s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1];
2737
2738 if (s->check_type > XZ_CHECK_MAX)
2739 return XZ_OPTIONS_ERROR;
2740
2741 if (s->check_type > XZ_CHECK_CRC32 && !IS_CRC64(s->check_type))
2742 return XZ_UNSUPPORTED_CHECK;
2743
2744 return XZ_OK;
2745}
2746
2747
2748static enum xz_ret dec_stream_footer(struct xz_dec *s)
2749{
2750 if (!memeq(s->temp.buf + 10, FOOTER_MAGIC, FOOTER_MAGIC_SIZE))
2751 return XZ_DATA_ERROR;
2752
2753 if (xz_crc32(s->temp.buf + 4, 6, 0) != get_le32(s->temp.buf))
2754 return XZ_DATA_ERROR;
2755
2756
2757
2758
2759
2760
2761 if ((s->index.size >> 2) != get_le32(s->temp.buf + 4))
2762 return XZ_DATA_ERROR;
2763
2764 if (s->temp.buf[8] != 0 || s->temp.buf[9] != s->check_type)
2765 return XZ_DATA_ERROR;
2766
2767
2768
2769
2770
2771 return XZ_STREAM_END;
2772}
2773
2774
2775static enum xz_ret dec_block_header(struct xz_dec *s)
2776{
2777 enum xz_ret ret;
2778
2779
2780
2781
2782
2783 s->temp.size -= 4;
2784 if (xz_crc32(s->temp.buf, s->temp.size, 0)
2785 != get_le32(s->temp.buf + s->temp.size))
2786 return XZ_DATA_ERROR;
2787
2788 s->temp.pos = 2;
2789
2790
2791
2792
2793
2794#ifdef XZ_DEC_BCJ
2795 if (s->temp.buf[1] & 0x3E)
2796#else
2797 if (s->temp.buf[1] & 0x3F)
2798#endif
2799 return XZ_OPTIONS_ERROR;
2800
2801
2802 if (s->temp.buf[1] & 0x40) {
2803 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
2804 != XZ_STREAM_END)
2805 return XZ_DATA_ERROR;
2806
2807 s->block_header.compressed = s->vli;
2808 } else {
2809 s->block_header.compressed = VLI_UNKNOWN;
2810 }
2811
2812
2813 if (s->temp.buf[1] & 0x80) {
2814 if (dec_vli(s, s->temp.buf, &s->temp.pos, s->temp.size)
2815 != XZ_STREAM_END)
2816 return XZ_DATA_ERROR;
2817
2818 s->block_header.uncompressed = s->vli;
2819 } else {
2820 s->block_header.uncompressed = VLI_UNKNOWN;
2821 }
2822
2823#ifdef XZ_DEC_BCJ
2824
2825 s->bcj_active = s->temp.buf[1] & 0x01;
2826 if (s->bcj_active) {
2827 if (s->temp.size - s->temp.pos < 2)
2828 return XZ_OPTIONS_ERROR;
2829
2830 ret = xz_dec_bcj_reset(s->bcj, s->temp.buf[s->temp.pos++]);
2831 if (ret != XZ_OK)
2832 return ret;
2833
2834
2835
2836
2837
2838 if (s->temp.buf[s->temp.pos++] != 0x00)
2839 return XZ_OPTIONS_ERROR;
2840 }
2841#endif
2842
2843
2844 if (s->temp.size - s->temp.pos < 2)
2845 return XZ_DATA_ERROR;
2846
2847
2848 if (s->temp.buf[s->temp.pos++] != 0x21)
2849 return XZ_OPTIONS_ERROR;
2850
2851
2852 if (s->temp.buf[s->temp.pos++] != 0x01)
2853 return XZ_OPTIONS_ERROR;
2854
2855
2856 if (s->temp.size - s->temp.pos < 1)
2857 return XZ_DATA_ERROR;
2858
2859 ret = xz_dec_lzma2_reset(s->lzma2, s->temp.buf[s->temp.pos++]);
2860 if (ret != XZ_OK)
2861 return ret;
2862
2863
2864 while (s->temp.pos < s->temp.size)
2865 if (s->temp.buf[s->temp.pos++] != 0x00)
2866 return XZ_OPTIONS_ERROR;
2867
2868 s->temp.pos = 0;
2869 s->block.compressed = 0;
2870 s->block.uncompressed = 0;
2871
2872 return XZ_OK;
2873}
2874
2875static enum xz_ret dec_main(struct xz_dec *s, struct xz_buf *b)
2876{
2877 enum xz_ret ret;
2878
2879
2880
2881
2882
2883 s->in_start = b->in_pos;
2884
2885 for (;;) {
2886 switch (s->sequence) {
2887 case SEQ_STREAM_HEADER:
2888
2889
2890
2891
2892
2893
2894
2895
2896 if (!fill_temp(s, b))
2897 return XZ_OK;
2898
2899
2900
2901
2902
2903
2904
2905
2906 s->sequence = SEQ_BLOCK_START;
2907
2908 ret = dec_stream_header(s);
2909 if (ret != XZ_OK)
2910 return ret;
2911
2912 case SEQ_BLOCK_START:
2913
2914 if (b->in_pos == b->in_size)
2915 return XZ_OK;
2916
2917
2918 if (b->in[b->in_pos] == 0) {
2919 s->in_start = b->in_pos++;
2920 s->sequence = SEQ_INDEX;
2921 break;
2922 }
2923
2924
2925
2926
2927
2928 s->block_header.size
2929 = ((uint32_t)b->in[b->in_pos] + 1) * 4;
2930
2931 s->temp.size = s->block_header.size;
2932 s->temp.pos = 0;
2933 s->sequence = SEQ_BLOCK_HEADER;
2934
2935 case SEQ_BLOCK_HEADER:
2936 if (!fill_temp(s, b))
2937 return XZ_OK;
2938
2939 ret = dec_block_header(s);
2940 if (ret != XZ_OK)
2941 return ret;
2942
2943 s->sequence = SEQ_BLOCK_UNCOMPRESS;
2944
2945 case SEQ_BLOCK_UNCOMPRESS:
2946 ret = dec_block(s, b);
2947 if (ret != XZ_STREAM_END)
2948 return ret;
2949
2950 s->sequence = SEQ_BLOCK_PADDING;
2951
2952 case SEQ_BLOCK_PADDING:
2953
2954
2955
2956
2957
2958
2959
2960 while (s->block.compressed & 3) {
2961 if (b->in_pos == b->in_size)
2962 return XZ_OK;
2963
2964 if (b->in[b->in_pos++] != 0)
2965 return XZ_DATA_ERROR;
2966
2967 ++s->block.compressed;
2968 }
2969
2970 s->sequence = SEQ_BLOCK_CHECK;
2971
2972 case SEQ_BLOCK_CHECK:
2973 if (s->check_type == XZ_CHECK_CRC32) {
2974 ret = crc_validate(s, b, 32);
2975 if (ret != XZ_STREAM_END)
2976 return ret;
2977 }
2978 else if (IS_CRC64(s->check_type)) {
2979 ret = crc_validate(s, b, 64);
2980 if (ret != XZ_STREAM_END)
2981 return ret;
2982 }
2983 else if (!check_skip(s, b)) {
2984 return XZ_OK;
2985 }
2986
2987 s->sequence = SEQ_BLOCK_START;
2988 break;
2989
2990 case SEQ_INDEX:
2991 ret = dec_index(s, b);
2992 if (ret != XZ_STREAM_END)
2993 return ret;
2994
2995 s->sequence = SEQ_INDEX_PADDING;
2996
2997 case SEQ_INDEX_PADDING:
2998 while ((s->index.size + (b->in_pos - s->in_start))
2999 & 3) {
3000 if (b->in_pos == b->in_size) {
3001 index_update(s, b);
3002 return XZ_OK;
3003 }
3004
3005 if (b->in[b->in_pos++] != 0)
3006 return XZ_DATA_ERROR;
3007 }
3008
3009
3010 index_update(s, b);
3011
3012
3013 if (!memeq(&s->block.hash, &s->index.hash,
3014 sizeof(s->block.hash)))
3015 return XZ_DATA_ERROR;
3016
3017 s->sequence = SEQ_INDEX_CRC32;
3018
3019 case SEQ_INDEX_CRC32:
3020 ret = crc_validate(s, b, 32);
3021 if (ret != XZ_STREAM_END)
3022 return ret;
3023
3024 s->temp.size = STREAM_HEADER_SIZE;
3025 s->sequence = SEQ_STREAM_FOOTER;
3026
3027 case SEQ_STREAM_FOOTER:
3028 if (!fill_temp(s, b))
3029 return XZ_OK;
3030
3031 return dec_stream_footer(s);
3032 }
3033 }
3034
3035
3036}
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b)
3064{
3065 size_t in_start;
3066 size_t out_start;
3067 enum xz_ret ret;
3068
3069 in_start = b->in_pos;
3070 out_start = b->out_pos;
3071 ret = dec_main(s, b);
3072
3073 if (ret == XZ_OK && in_start == b->in_pos && out_start == b->out_pos) {
3074 if (s->allow_buf_error)
3075 ret = XZ_BUF_ERROR;
3076
3077 s->allow_buf_error = 1;
3078 } else {
3079 s->allow_buf_error = 0;
3080 }
3081
3082 return ret;
3083}
3084
3085struct xz_dec *xz_dec_init(uint32_t dict_max)
3086{
3087 struct xz_dec *s = malloc(sizeof(*s));
3088 if (!s)
3089 return NULL;
3090
3091#ifdef XZ_DEC_BCJ
3092 s->bcj = malloc(sizeof(*s->bcj));
3093 if (!s->bcj)
3094 goto error_bcj;
3095#endif
3096
3097 s->lzma2 = xz_dec_lzma2_create(dict_max);
3098 if (s->lzma2 == NULL)
3099 goto error_lzma2;
3100
3101 xz_dec_reset(s);
3102 return s;
3103
3104error_lzma2:
3105#ifdef XZ_DEC_BCJ
3106 free(s->bcj);
3107error_bcj:
3108#endif
3109 free(s);
3110 return NULL;
3111}
3112
3113void xz_dec_reset(struct xz_dec *s)
3114{
3115 s->sequence = SEQ_STREAM_HEADER;
3116 s->allow_buf_error = 0;
3117 s->pos = 0;
3118 s->crc = 0;
3119 memset(&s->block, 0, sizeof(s->block));
3120 memset(&s->index, 0, sizeof(s->index));
3121 s->temp.pos = 0;
3122 s->temp.size = STREAM_HEADER_SIZE;
3123}
3124
3125void xz_dec_end(struct xz_dec *s)
3126{
3127 if (s != NULL) {
3128 free((s->lzma2)->dict.buf);
3129 free(s->lzma2);
3130
3131#ifdef XZ_DEC_BCJ
3132 free(s->bcj);
3133#endif
3134 free(s);
3135 }
3136}
3137