aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig6
-rw-r--r--lib/Kconfig.debug8
-rw-r--r--lib/Makefile6
-rw-r--r--lib/decompress.c5
-rw-r--r--lib/decompress_bunzip2.c8
-rw-r--r--lib/decompress_inflate.c23
-rw-r--r--lib/decompress_unlzma.c85
-rw-r--r--lib/decompress_unlzo.c105
-rw-r--r--lib/decompress_unxz.c397
-rw-r--r--lib/dynamic_debug.c9
-rw-r--r--lib/flex_array.c10
-rw-r--r--lib/hexdump.c18
-rw-r--r--lib/ioremap.c2
-rw-r--r--lib/kref.c30
-rw-r--r--lib/list_debug.c39
-rw-r--r--lib/nlattr.c2
-rw-r--r--lib/radix-tree.c7
-rw-r--r--lib/rbtree.c3
-rw-r--r--lib/swiotlb.c2
-rw-r--r--lib/textsearch.c10
-rw-r--r--lib/vsprintf.c38
-rw-r--r--lib/xz/Kconfig59
-rw-r--r--lib/xz/Makefile5
-rw-r--r--lib/xz/xz_crc32.c59
-rw-r--r--lib/xz/xz_dec_bcj.c561
-rw-r--r--lib/xz/xz_dec_lzma2.c1171
-rw-r--r--lib/xz/xz_dec_stream.c821
-rw-r--r--lib/xz/xz_dec_syms.c26
-rw-r--r--lib/xz/xz_dec_test.c220
-rw-r--r--lib/xz/xz_lzma2.h204
-rw-r--r--lib/xz/xz_private.h156
-rw-r--r--lib/xz/xz_stream.h62
32 files changed, 4050 insertions, 107 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index 3116aa631af6..0ee67e08ad3e 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -106,6 +106,8 @@ config LZO_COMPRESS
106config LZO_DECOMPRESS 106config LZO_DECOMPRESS
107 tristate 107 tristate
108 108
109source "lib/xz/Kconfig"
110
109# 111#
110# These all provide a common interface (hence the apparent duplication with 112# These all provide a common interface (hence the apparent duplication with
111# ZLIB_INFLATE; DECOMPRESS_GZIP is just a wrapper.) 113# ZLIB_INFLATE; DECOMPRESS_GZIP is just a wrapper.)
@@ -120,6 +122,10 @@ config DECOMPRESS_BZIP2
120config DECOMPRESS_LZMA 122config DECOMPRESS_LZMA
121 tristate 123 tristate
122 124
125config DECOMPRESS_XZ
126 select XZ_DEC
127 tristate
128
123config DECOMPRESS_LZO 129config DECOMPRESS_LZO
124 select LZO_DECOMPRESS 130 select LZO_DECOMPRESS
125 tristate 131 tristate
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 2d05adb98401..2b97418c67e2 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -657,7 +657,7 @@ config DEBUG_HIGHMEM
657 Disable for production systems. 657 Disable for production systems.
658 658
659config DEBUG_BUGVERBOSE 659config DEBUG_BUGVERBOSE
660 bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EMBEDDED 660 bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EXPERT
661 depends on BUG 661 depends on BUG
662 depends on ARM || AVR32 || M32R || M68K || SPARC32 || SPARC64 || \ 662 depends on ARM || AVR32 || M32R || M68K || SPARC32 || SPARC64 || \
663 FRV || SUPERH || GENERIC_BUG || BLACKFIN || MN10300 663 FRV || SUPERH || GENERIC_BUG || BLACKFIN || MN10300
@@ -729,8 +729,8 @@ config DEBUG_WRITECOUNT
729 If unsure, say N. 729 If unsure, say N.
730 730
731config DEBUG_MEMORY_INIT 731config DEBUG_MEMORY_INIT
732 bool "Debug memory initialisation" if EMBEDDED 732 bool "Debug memory initialisation" if EXPERT
733 default !EMBEDDED 733 default !EXPERT
734 help 734 help
735 Enable this for additional checks during memory initialisation. 735 Enable this for additional checks during memory initialisation.
736 The sanity checks verify aspects of the VM such as the memory model 736 The sanity checks verify aspects of the VM such as the memory model
@@ -805,7 +805,7 @@ config ARCH_WANT_FRAME_POINTERS
805config FRAME_POINTER 805config FRAME_POINTER
806 bool "Compile the kernel with frame pointers" 806 bool "Compile the kernel with frame pointers"
807 depends on DEBUG_KERNEL && \ 807 depends on DEBUG_KERNEL && \
808 (CRIS || M68K || M68KNOMMU || FRV || UML || \ 808 (CRIS || M68K || FRV || UML || \
809 AVR32 || SUPERH || BLACKFIN || MN10300) || \ 809 AVR32 || SUPERH || BLACKFIN || MN10300) || \
810 ARCH_WANT_FRAME_POINTERS 810 ARCH_WANT_FRAME_POINTERS
811 default y if (DEBUG_INFO && UML) || ARCH_WANT_FRAME_POINTERS 811 default y if (DEBUG_INFO && UML) || ARCH_WANT_FRAME_POINTERS
diff --git a/lib/Makefile b/lib/Makefile
index d7b6e30a3a1e..cbb774f7d41d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
12 idr.o int_sqrt.o extable.o prio_tree.o \ 12 idr.o int_sqrt.o extable.o prio_tree.o \
13 sha1.o irq_regs.o reciprocal_div.o argv_split.o \ 13 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
14 proportions.o prio_heap.o ratelimit.o show_mem.o \ 14 proportions.o prio_heap.o ratelimit.o show_mem.o \
15 is_single_threaded.o plist.o decompress.o flex_array.o 15 is_single_threaded.o plist.o decompress.o
16 16
17lib-$(CONFIG_MMU) += ioremap.o 17lib-$(CONFIG_MMU) += ioremap.o
18lib-$(CONFIG_SMP) += cpumask.o 18lib-$(CONFIG_SMP) += cpumask.o
@@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o
21 21
22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ 22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ 23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
24 string_helpers.o gcd.o lcm.o list_sort.o uuid.o 24 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o
25 25
26ifeq ($(CONFIG_DEBUG_KOBJECT),y) 26ifeq ($(CONFIG_DEBUG_KOBJECT),y)
27CFLAGS_kobject.o += -DDEBUG 27CFLAGS_kobject.o += -DDEBUG
@@ -69,11 +69,13 @@ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
69obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ 69obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
70obj-$(CONFIG_LZO_COMPRESS) += lzo/ 70obj-$(CONFIG_LZO_COMPRESS) += lzo/
71obj-$(CONFIG_LZO_DECOMPRESS) += lzo/ 71obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
72obj-$(CONFIG_XZ_DEC) += xz/
72obj-$(CONFIG_RAID6_PQ) += raid6/ 73obj-$(CONFIG_RAID6_PQ) += raid6/
73 74
74lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o 75lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o
75lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o 76lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o
76lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o 77lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o
78lib-$(CONFIG_DECOMPRESS_XZ) += decompress_unxz.o
77lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o 79lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o
78 80
79obj-$(CONFIG_TEXTSEARCH) += textsearch.o 81obj-$(CONFIG_TEXTSEARCH) += textsearch.o
diff --git a/lib/decompress.c b/lib/decompress.c
index a7606815541f..3d766b7f60ab 100644
--- a/lib/decompress.c
+++ b/lib/decompress.c
@@ -8,6 +8,7 @@
8 8
9#include <linux/decompress/bunzip2.h> 9#include <linux/decompress/bunzip2.h>
10#include <linux/decompress/unlzma.h> 10#include <linux/decompress/unlzma.h>
11#include <linux/decompress/unxz.h>
11#include <linux/decompress/inflate.h> 12#include <linux/decompress/inflate.h>
12#include <linux/decompress/unlzo.h> 13#include <linux/decompress/unlzo.h>
13 14
@@ -23,6 +24,9 @@
23#ifndef CONFIG_DECOMPRESS_LZMA 24#ifndef CONFIG_DECOMPRESS_LZMA
24# define unlzma NULL 25# define unlzma NULL
25#endif 26#endif
27#ifndef CONFIG_DECOMPRESS_XZ
28# define unxz NULL
29#endif
26#ifndef CONFIG_DECOMPRESS_LZO 30#ifndef CONFIG_DECOMPRESS_LZO
27# define unlzo NULL 31# define unlzo NULL
28#endif 32#endif
@@ -36,6 +40,7 @@ static const struct compress_format {
36 { {037, 0236}, "gzip", gunzip }, 40 { {037, 0236}, "gzip", gunzip },
37 { {0x42, 0x5a}, "bzip2", bunzip2 }, 41 { {0x42, 0x5a}, "bzip2", bunzip2 },
38 { {0x5d, 0x00}, "lzma", unlzma }, 42 { {0x5d, 0x00}, "lzma", unlzma },
43 { {0xfd, 0x37}, "xz", unxz },
39 { {0x89, 0x4c}, "lzo", unlzo }, 44 { {0x89, 0x4c}, "lzo", unlzo },
40 { {0, 0}, NULL, NULL } 45 { {0, 0}, NULL, NULL }
41}; 46};
diff --git a/lib/decompress_bunzip2.c b/lib/decompress_bunzip2.c
index 81c8bb1cc6aa..a7b80c1d6a0d 100644
--- a/lib/decompress_bunzip2.c
+++ b/lib/decompress_bunzip2.c
@@ -49,7 +49,6 @@
49#define PREBOOT 49#define PREBOOT
50#else 50#else
51#include <linux/decompress/bunzip2.h> 51#include <linux/decompress/bunzip2.h>
52#include <linux/slab.h>
53#endif /* STATIC */ 52#endif /* STATIC */
54 53
55#include <linux/decompress/mm.h> 54#include <linux/decompress/mm.h>
@@ -682,13 +681,12 @@ STATIC int INIT bunzip2(unsigned char *buf, int len,
682 int(*flush)(void*, unsigned int), 681 int(*flush)(void*, unsigned int),
683 unsigned char *outbuf, 682 unsigned char *outbuf,
684 int *pos, 683 int *pos,
685 void(*error_fn)(char *x)) 684 void(*error)(char *x))
686{ 685{
687 struct bunzip_data *bd; 686 struct bunzip_data *bd;
688 int i = -1; 687 int i = -1;
689 unsigned char *inbuf; 688 unsigned char *inbuf;
690 689
691 set_error_fn(error_fn);
692 if (flush) 690 if (flush)
693 outbuf = malloc(BZIP2_IOBUF_SIZE); 691 outbuf = malloc(BZIP2_IOBUF_SIZE);
694 692
@@ -751,8 +749,8 @@ STATIC int INIT decompress(unsigned char *buf, int len,
751 int(*flush)(void*, unsigned int), 749 int(*flush)(void*, unsigned int),
752 unsigned char *outbuf, 750 unsigned char *outbuf,
753 int *pos, 751 int *pos,
754 void(*error_fn)(char *x)) 752 void(*error)(char *x))
755{ 753{
756 return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error_fn); 754 return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error);
757} 755}
758#endif 756#endif
diff --git a/lib/decompress_inflate.c b/lib/decompress_inflate.c
index fc686c7a0a0d..19ff89e34eec 100644
--- a/lib/decompress_inflate.c
+++ b/lib/decompress_inflate.c
@@ -19,7 +19,6 @@
19#include "zlib_inflate/inflate.h" 19#include "zlib_inflate/inflate.h"
20 20
21#include "zlib_inflate/infutil.h" 21#include "zlib_inflate/infutil.h"
22#include <linux/slab.h>
23 22
24#endif /* STATIC */ 23#endif /* STATIC */
25 24
@@ -27,7 +26,7 @@
27 26
28#define GZIP_IOBUF_SIZE (16*1024) 27#define GZIP_IOBUF_SIZE (16*1024)
29 28
30static int nofill(void *buffer, unsigned int len) 29static int INIT nofill(void *buffer, unsigned int len)
31{ 30{
32 return -1; 31 return -1;
33} 32}
@@ -38,13 +37,12 @@ STATIC int INIT gunzip(unsigned char *buf, int len,
38 int(*flush)(void*, unsigned int), 37 int(*flush)(void*, unsigned int),
39 unsigned char *out_buf, 38 unsigned char *out_buf,
40 int *pos, 39 int *pos,
41 void(*error_fn)(char *x)) { 40 void(*error)(char *x)) {
42 u8 *zbuf; 41 u8 *zbuf;
43 struct z_stream_s *strm; 42 struct z_stream_s *strm;
44 int rc; 43 int rc;
45 size_t out_len; 44 size_t out_len;
46 45
47 set_error_fn(error_fn);
48 rc = -1; 46 rc = -1;
49 if (flush) { 47 if (flush) {
50 out_len = 0x8000; /* 32 K */ 48 out_len = 0x8000; /* 32 K */
@@ -100,13 +98,22 @@ STATIC int INIT gunzip(unsigned char *buf, int len,
100 * possible asciz filename) 98 * possible asciz filename)
101 */ 99 */
102 strm->next_in = zbuf + 10; 100 strm->next_in = zbuf + 10;
101 strm->avail_in = len - 10;
103 /* skip over asciz filename */ 102 /* skip over asciz filename */
104 if (zbuf[3] & 0x8) { 103 if (zbuf[3] & 0x8) {
105 while (strm->next_in[0]) 104 do {
106 strm->next_in++; 105 /*
107 strm->next_in++; 106 * If the filename doesn't fit into the buffer,
107 * the file is very probably corrupt. Don't try
108 * to read more data.
109 */
110 if (strm->avail_in == 0) {
111 error("header error");
112 goto gunzip_5;
113 }
114 --strm->avail_in;
115 } while (*strm->next_in++);
108 } 116 }
109 strm->avail_in = len - (strm->next_in - zbuf);
110 117
111 strm->next_out = out_buf; 118 strm->next_out = out_buf;
112 strm->avail_out = out_len; 119 strm->avail_out = out_len;
diff --git a/lib/decompress_unlzma.c b/lib/decompress_unlzma.c
index ca82fde81c8f..476c65af9709 100644
--- a/lib/decompress_unlzma.c
+++ b/lib/decompress_unlzma.c
@@ -33,7 +33,6 @@
33#define PREBOOT 33#define PREBOOT
34#else 34#else
35#include <linux/decompress/unlzma.h> 35#include <linux/decompress/unlzma.h>
36#include <linux/slab.h>
37#endif /* STATIC */ 36#endif /* STATIC */
38 37
39#include <linux/decompress/mm.h> 38#include <linux/decompress/mm.h>
@@ -74,6 +73,7 @@ struct rc {
74 uint32_t code; 73 uint32_t code;
75 uint32_t range; 74 uint32_t range;
76 uint32_t bound; 75 uint32_t bound;
76 void (*error)(char *);
77}; 77};
78 78
79 79
@@ -82,7 +82,7 @@ struct rc {
82#define RC_MODEL_TOTAL_BITS 11 82#define RC_MODEL_TOTAL_BITS 11
83 83
84 84
85static int nofill(void *buffer, unsigned int len) 85static int INIT nofill(void *buffer, unsigned int len)
86{ 86{
87 return -1; 87 return -1;
88} 88}
@@ -92,7 +92,7 @@ static void INIT rc_read(struct rc *rc)
92{ 92{
93 rc->buffer_size = rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE); 93 rc->buffer_size = rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE);
94 if (rc->buffer_size <= 0) 94 if (rc->buffer_size <= 0)
95 error("unexpected EOF"); 95 rc->error("unexpected EOF");
96 rc->ptr = rc->buffer; 96 rc->ptr = rc->buffer;
97 rc->buffer_end = rc->buffer + rc->buffer_size; 97 rc->buffer_end = rc->buffer + rc->buffer_size;
98} 98}
@@ -127,12 +127,6 @@ static inline void INIT rc_init_code(struct rc *rc)
127} 127}
128 128
129 129
130/* Called once. TODO: bb_maybe_free() */
131static inline void INIT rc_free(struct rc *rc)
132{
133 free(rc->buffer);
134}
135
136/* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */ 130/* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */
137static void INIT rc_do_normalize(struct rc *rc) 131static void INIT rc_do_normalize(struct rc *rc)
138{ 132{
@@ -169,7 +163,7 @@ static inline void INIT rc_update_bit_0(struct rc *rc, uint16_t *p)
169 rc->range = rc->bound; 163 rc->range = rc->bound;
170 *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS; 164 *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
171} 165}
172static inline void rc_update_bit_1(struct rc *rc, uint16_t *p) 166static inline void INIT rc_update_bit_1(struct rc *rc, uint16_t *p)
173{ 167{
174 rc->range -= rc->bound; 168 rc->range -= rc->bound;
175 rc->code -= rc->bound; 169 rc->code -= rc->bound;
@@ -319,32 +313,38 @@ static inline uint8_t INIT peek_old_byte(struct writer *wr,
319 313
320} 314}
321 315
322static inline void INIT write_byte(struct writer *wr, uint8_t byte) 316static inline int INIT write_byte(struct writer *wr, uint8_t byte)
323{ 317{
324 wr->buffer[wr->buffer_pos++] = wr->previous_byte = byte; 318 wr->buffer[wr->buffer_pos++] = wr->previous_byte = byte;
325 if (wr->flush && wr->buffer_pos == wr->header->dict_size) { 319 if (wr->flush && wr->buffer_pos == wr->header->dict_size) {
326 wr->buffer_pos = 0; 320 wr->buffer_pos = 0;
327 wr->global_pos += wr->header->dict_size; 321 wr->global_pos += wr->header->dict_size;
328 wr->flush((char *)wr->buffer, wr->header->dict_size); 322 if (wr->flush((char *)wr->buffer, wr->header->dict_size)
323 != wr->header->dict_size)
324 return -1;
329 } 325 }
326 return 0;
330} 327}
331 328
332 329
333static inline void INIT copy_byte(struct writer *wr, uint32_t offs) 330static inline int INIT copy_byte(struct writer *wr, uint32_t offs)
334{ 331{
335 write_byte(wr, peek_old_byte(wr, offs)); 332 return write_byte(wr, peek_old_byte(wr, offs));
336} 333}
337 334
338static inline void INIT copy_bytes(struct writer *wr, 335static inline int INIT copy_bytes(struct writer *wr,
339 uint32_t rep0, int len) 336 uint32_t rep0, int len)
340{ 337{
341 do { 338 do {
342 copy_byte(wr, rep0); 339 if (copy_byte(wr, rep0))
340 return -1;
343 len--; 341 len--;
344 } while (len != 0 && wr->buffer_pos < wr->header->dst_size); 342 } while (len != 0 && wr->buffer_pos < wr->header->dst_size);
343
344 return len;
345} 345}
346 346
347static inline void INIT process_bit0(struct writer *wr, struct rc *rc, 347static inline int INIT process_bit0(struct writer *wr, struct rc *rc,
348 struct cstate *cst, uint16_t *p, 348 struct cstate *cst, uint16_t *p,
349 int pos_state, uint16_t *prob, 349 int pos_state, uint16_t *prob,
350 int lc, uint32_t literal_pos_mask) { 350 int lc, uint32_t literal_pos_mask) {
@@ -378,16 +378,17 @@ static inline void INIT process_bit0(struct writer *wr, struct rc *rc,
378 uint16_t *prob_lit = prob + mi; 378 uint16_t *prob_lit = prob + mi;
379 rc_get_bit(rc, prob_lit, &mi); 379 rc_get_bit(rc, prob_lit, &mi);
380 } 380 }
381 write_byte(wr, mi);
382 if (cst->state < 4) 381 if (cst->state < 4)
383 cst->state = 0; 382 cst->state = 0;
384 else if (cst->state < 10) 383 else if (cst->state < 10)
385 cst->state -= 3; 384 cst->state -= 3;
386 else 385 else
387 cst->state -= 6; 386 cst->state -= 6;
387
388 return write_byte(wr, mi);
388} 389}
389 390
390static inline void INIT process_bit1(struct writer *wr, struct rc *rc, 391static inline int INIT process_bit1(struct writer *wr, struct rc *rc,
391 struct cstate *cst, uint16_t *p, 392 struct cstate *cst, uint16_t *p,
392 int pos_state, uint16_t *prob) { 393 int pos_state, uint16_t *prob) {
393 int offset; 394 int offset;
@@ -418,8 +419,7 @@ static inline void INIT process_bit1(struct writer *wr, struct rc *rc,
418 419
419 cst->state = cst->state < LZMA_NUM_LIT_STATES ? 420 cst->state = cst->state < LZMA_NUM_LIT_STATES ?
420 9 : 11; 421 9 : 11;
421 copy_byte(wr, cst->rep0); 422 return copy_byte(wr, cst->rep0);
422 return;
423 } else { 423 } else {
424 rc_update_bit_1(rc, prob); 424 rc_update_bit_1(rc, prob);
425 } 425 }
@@ -521,12 +521,15 @@ static inline void INIT process_bit1(struct writer *wr, struct rc *rc,
521 } else 521 } else
522 cst->rep0 = pos_slot; 522 cst->rep0 = pos_slot;
523 if (++(cst->rep0) == 0) 523 if (++(cst->rep0) == 0)
524 return; 524 return 0;
525 if (cst->rep0 > wr->header->dict_size
526 || cst->rep0 > get_pos(wr))
527 return -1;
525 } 528 }
526 529
527 len += LZMA_MATCH_MIN_LEN; 530 len += LZMA_MATCH_MIN_LEN;
528 531
529 copy_bytes(wr, cst->rep0, len); 532 return copy_bytes(wr, cst->rep0, len);
530} 533}
531 534
532 535
@@ -536,7 +539,7 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
536 int(*flush)(void*, unsigned int), 539 int(*flush)(void*, unsigned int),
537 unsigned char *output, 540 unsigned char *output,
538 int *posp, 541 int *posp,
539 void(*error_fn)(char *x) 542 void(*error)(char *x)
540 ) 543 )
541{ 544{
542 struct lzma_header header; 545 struct lzma_header header;
@@ -552,7 +555,7 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
552 unsigned char *inbuf; 555 unsigned char *inbuf;
553 int ret = -1; 556 int ret = -1;
554 557
555 set_error_fn(error_fn); 558 rc.error = error;
556 559
557 if (buf) 560 if (buf)
558 inbuf = buf; 561 inbuf = buf;
@@ -580,8 +583,10 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
580 ((unsigned char *)&header)[i] = *rc.ptr++; 583 ((unsigned char *)&header)[i] = *rc.ptr++;
581 } 584 }
582 585
583 if (header.pos >= (9 * 5 * 5)) 586 if (header.pos >= (9 * 5 * 5)) {
584 error("bad header"); 587 error("bad header");
588 goto exit_1;
589 }
585 590
586 mi = 0; 591 mi = 0;
587 lc = header.pos; 592 lc = header.pos;
@@ -627,21 +632,29 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
627 int pos_state = get_pos(&wr) & pos_state_mask; 632 int pos_state = get_pos(&wr) & pos_state_mask;
628 uint16_t *prob = p + LZMA_IS_MATCH + 633 uint16_t *prob = p + LZMA_IS_MATCH +
629 (cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state; 634 (cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state;
630 if (rc_is_bit_0(&rc, prob)) 635 if (rc_is_bit_0(&rc, prob)) {
631 process_bit0(&wr, &rc, &cst, p, pos_state, prob, 636 if (process_bit0(&wr, &rc, &cst, p, pos_state, prob,
632 lc, literal_pos_mask); 637 lc, literal_pos_mask)) {
633 else { 638 error("LZMA data is corrupt");
634 process_bit1(&wr, &rc, &cst, p, pos_state, prob); 639 goto exit_3;
640 }
641 } else {
642 if (process_bit1(&wr, &rc, &cst, p, pos_state, prob)) {
643 error("LZMA data is corrupt");
644 goto exit_3;
645 }
635 if (cst.rep0 == 0) 646 if (cst.rep0 == 0)
636 break; 647 break;
637 } 648 }
649 if (rc.buffer_size <= 0)
650 goto exit_3;
638 } 651 }
639 652
640 if (posp) 653 if (posp)
641 *posp = rc.ptr-rc.buffer; 654 *posp = rc.ptr-rc.buffer;
642 if (wr.flush) 655 if (!wr.flush || wr.flush(wr.buffer, wr.buffer_pos) == wr.buffer_pos)
643 wr.flush(wr.buffer, wr.buffer_pos); 656 ret = 0;
644 ret = 0; 657exit_3:
645 large_free(p); 658 large_free(p);
646exit_2: 659exit_2:
647 if (!output) 660 if (!output)
@@ -659,9 +672,9 @@ STATIC int INIT decompress(unsigned char *buf, int in_len,
659 int(*flush)(void*, unsigned int), 672 int(*flush)(void*, unsigned int),
660 unsigned char *output, 673 unsigned char *output,
661 int *posp, 674 int *posp,
662 void(*error_fn)(char *x) 675 void(*error)(char *x)
663 ) 676 )
664{ 677{
665 return unlzma(buf, in_len - 4, fill, flush, output, posp, error_fn); 678 return unlzma(buf, in_len - 4, fill, flush, output, posp, error);
666} 679}
667#endif 680#endif
diff --git a/lib/decompress_unlzo.c b/lib/decompress_unlzo.c
index bcb3a4bd68ff..5a7a2adf4c4c 100644
--- a/lib/decompress_unlzo.c
+++ b/lib/decompress_unlzo.c
@@ -33,7 +33,6 @@
33#ifdef STATIC 33#ifdef STATIC
34#include "lzo/lzo1x_decompress.c" 34#include "lzo/lzo1x_decompress.c"
35#else 35#else
36#include <linux/slab.h>
37#include <linux/decompress/unlzo.h> 36#include <linux/decompress/unlzo.h>
38#endif 37#endif
39 38
@@ -49,14 +48,25 @@ static const unsigned char lzop_magic[] = {
49 48
50#define LZO_BLOCK_SIZE (256*1024l) 49#define LZO_BLOCK_SIZE (256*1024l)
51#define HEADER_HAS_FILTER 0x00000800L 50#define HEADER_HAS_FILTER 0x00000800L
51#define HEADER_SIZE_MIN (9 + 7 + 4 + 8 + 1 + 4)
52#define HEADER_SIZE_MAX (9 + 7 + 1 + 8 + 8 + 4 + 1 + 255 + 4)
52 53
53STATIC inline int INIT parse_header(u8 *input, u8 *skip) 54STATIC inline int INIT parse_header(u8 *input, int *skip, int in_len)
54{ 55{
55 int l; 56 int l;
56 u8 *parse = input; 57 u8 *parse = input;
58 u8 *end = input + in_len;
57 u8 level = 0; 59 u8 level = 0;
58 u16 version; 60 u16 version;
59 61
62 /*
63 * Check that there's enough input to possibly have a valid header.
64 * Then it is possible to parse several fields until the minimum
65 * size may have been used.
66 */
67 if (in_len < HEADER_SIZE_MIN)
68 return 0;
69
60 /* read magic: 9 first bits */ 70 /* read magic: 9 first bits */
61 for (l = 0; l < 9; l++) { 71 for (l = 0; l < 9; l++) {
62 if (*parse++ != lzop_magic[l]) 72 if (*parse++ != lzop_magic[l])
@@ -74,6 +84,15 @@ STATIC inline int INIT parse_header(u8 *input, u8 *skip)
74 else 84 else
75 parse += 4; /* flags */ 85 parse += 4; /* flags */
76 86
87 /*
88 * At least mode, mtime_low, filename length, and checksum must
89 * be left to be parsed. If also mtime_high is present, it's OK
90 * because the next input buffer check is after reading the
91 * filename length.
92 */
93 if (end - parse < 8 + 1 + 4)
94 return 0;
95
77 /* skip mode and mtime_low */ 96 /* skip mode and mtime_low */
78 parse += 8; 97 parse += 8;
79 if (version >= 0x0940) 98 if (version >= 0x0940)
@@ -81,6 +100,8 @@ STATIC inline int INIT parse_header(u8 *input, u8 *skip)
81 100
82 l = *parse++; 101 l = *parse++;
83 /* don't care about the file name, and skip checksum */ 102 /* don't care about the file name, and skip checksum */
103 if (end - parse < l + 4)
104 return 0;
84 parse += l + 4; 105 parse += l + 4;
85 106
86 *skip = parse - input; 107 *skip = parse - input;
@@ -91,16 +112,15 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
91 int (*fill) (void *, unsigned int), 112 int (*fill) (void *, unsigned int),
92 int (*flush) (void *, unsigned int), 113 int (*flush) (void *, unsigned int),
93 u8 *output, int *posp, 114 u8 *output, int *posp,
94 void (*error_fn) (char *x)) 115 void (*error) (char *x))
95{ 116{
96 u8 skip = 0, r = 0; 117 u8 r = 0;
118 int skip = 0;
97 u32 src_len, dst_len; 119 u32 src_len, dst_len;
98 size_t tmp; 120 size_t tmp;
99 u8 *in_buf, *in_buf_save, *out_buf; 121 u8 *in_buf, *in_buf_save, *out_buf;
100 int ret = -1; 122 int ret = -1;
101 123
102 set_error_fn(error_fn);
103
104 if (output) { 124 if (output) {
105 out_buf = output; 125 out_buf = output;
106 } else if (!flush) { 126 } else if (!flush) {
@@ -119,8 +139,8 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
119 goto exit_1; 139 goto exit_1;
120 } else if (input) { 140 } else if (input) {
121 in_buf = input; 141 in_buf = input;
122 } else if (!fill || !posp) { 142 } else if (!fill) {
123 error("NULL input pointer and missing position pointer or fill function"); 143 error("NULL input pointer and missing fill function");
124 goto exit_1; 144 goto exit_1;
125 } else { 145 } else {
126 in_buf = malloc(lzo1x_worst_compress(LZO_BLOCK_SIZE)); 146 in_buf = malloc(lzo1x_worst_compress(LZO_BLOCK_SIZE));
@@ -134,22 +154,47 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
134 if (posp) 154 if (posp)
135 *posp = 0; 155 *posp = 0;
136 156
137 if (fill) 157 if (fill) {
138 fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE)); 158 /*
159 * Start from in_buf + HEADER_SIZE_MAX to make it possible
160 * to use memcpy() to copy the unused data to the beginning
161 * of the buffer. This way memmove() isn't needed which
162 * is missing from pre-boot environments of most archs.
163 */
164 in_buf += HEADER_SIZE_MAX;
165 in_len = fill(in_buf, HEADER_SIZE_MAX);
166 }
139 167
140 if (!parse_header(input, &skip)) { 168 if (!parse_header(in_buf, &skip, in_len)) {
141 error("invalid header"); 169 error("invalid header");
142 goto exit_2; 170 goto exit_2;
143 } 171 }
144 in_buf += skip; 172 in_buf += skip;
173 in_len -= skip;
174
175 if (fill) {
176 /* Move the unused data to the beginning of the buffer. */
177 memcpy(in_buf_save, in_buf, in_len);
178 in_buf = in_buf_save;
179 }
145 180
146 if (posp) 181 if (posp)
147 *posp = skip; 182 *posp = skip;
148 183
149 for (;;) { 184 for (;;) {
150 /* read uncompressed block size */ 185 /* read uncompressed block size */
186 if (fill && in_len < 4) {
187 skip = fill(in_buf + in_len, 4 - in_len);
188 if (skip > 0)
189 in_len += skip;
190 }
191 if (in_len < 4) {
192 error("file corrupted");
193 goto exit_2;
194 }
151 dst_len = get_unaligned_be32(in_buf); 195 dst_len = get_unaligned_be32(in_buf);
152 in_buf += 4; 196 in_buf += 4;
197 in_len -= 4;
153 198
154 /* exit if last block */ 199 /* exit if last block */
155 if (dst_len == 0) { 200 if (dst_len == 0) {
@@ -164,8 +209,18 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
164 } 209 }
165 210
166 /* read compressed block size, and skip block checksum info */ 211 /* read compressed block size, and skip block checksum info */
212 if (fill && in_len < 8) {
213 skip = fill(in_buf + in_len, 8 - in_len);
214 if (skip > 0)
215 in_len += skip;
216 }
217 if (in_len < 8) {
218 error("file corrupted");
219 goto exit_2;
220 }
167 src_len = get_unaligned_be32(in_buf); 221 src_len = get_unaligned_be32(in_buf);
168 in_buf += 8; 222 in_buf += 8;
223 in_len -= 8;
169 224
170 if (src_len <= 0 || src_len > dst_len) { 225 if (src_len <= 0 || src_len > dst_len) {
171 error("file corrupted"); 226 error("file corrupted");
@@ -173,6 +228,15 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
173 } 228 }
174 229
175 /* decompress */ 230 /* decompress */
231 if (fill && in_len < src_len) {
232 skip = fill(in_buf + in_len, src_len - in_len);
233 if (skip > 0)
234 in_len += skip;
235 }
236 if (in_len < src_len) {
237 error("file corrupted");
238 goto exit_2;
239 }
176 tmp = dst_len; 240 tmp = dst_len;
177 241
178 /* When the input data is not compressed at all, 242 /* When the input data is not compressed at all,
@@ -190,17 +254,26 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
190 } 254 }
191 } 255 }
192 256
193 if (flush) 257 if (flush && flush(out_buf, dst_len) != dst_len)
194 flush(out_buf, dst_len); 258 goto exit_2;
195 if (output) 259 if (output)
196 out_buf += dst_len; 260 out_buf += dst_len;
197 if (posp) 261 if (posp)
198 *posp += src_len + 12; 262 *posp += src_len + 12;
263
264 in_buf += src_len;
265 in_len -= src_len;
199 if (fill) { 266 if (fill) {
267 /*
268 * If there happens to still be unused data left in
269 * in_buf, move it to the beginning of the buffer.
270 * Use a loop to avoid memmove() dependency.
271 */
272 if (in_len > 0)
273 for (skip = 0; skip < in_len; ++skip)
274 in_buf_save[skip] = in_buf[skip];
200 in_buf = in_buf_save; 275 in_buf = in_buf_save;
201 fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE)); 276 }
202 } else
203 in_buf += src_len;
204 } 277 }
205 278
206 ret = 0; 279 ret = 0;
diff --git a/lib/decompress_unxz.c b/lib/decompress_unxz.c
new file mode 100644
index 000000000000..cecd23df2b9a
--- /dev/null
+++ b/lib/decompress_unxz.c
@@ -0,0 +1,397 @@
1/*
2 * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd
3 *
4 * Author: Lasse Collin <lasse.collin@tukaani.org>
5 *
6 * This file has been put into the public domain.
7 * You can do whatever you want with this file.
8 */
9
10/*
11 * Important notes about in-place decompression
12 *
13 * At least on x86, the kernel is decompressed in place: the compressed data
14 * is placed to the end of the output buffer, and the decompressor overwrites
15 * most of the compressed data. There must be enough safety margin to
16 * guarantee that the write position is always behind the read position.
17 *
18 * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below.
19 * Note that the margin with XZ is bigger than with Deflate (gzip)!
20 *
21 * The worst case for in-place decompression is that the beginning of
22 * the file is compressed extremely well, and the rest of the file is
23 * uncompressible. Thus, we must look for worst-case expansion when the
24 * compressor is encoding uncompressible data.
25 *
26 * The structure of the .xz file in case of a compresed kernel is as follows.
27 * Sizes (as bytes) of the fields are in parenthesis.
28 *
29 * Stream Header (12)
30 * Block Header:
31 * Block Header (8-12)
32 * Compressed Data (N)
33 * Block Padding (0-3)
34 * CRC32 (4)
35 * Index (8-20)
36 * Stream Footer (12)
37 *
38 * Normally there is exactly one Block, but let's assume that there are
39 * 2-4 Blocks just in case. Because Stream Header and also Block Header
40 * of the first Block don't make the decompressor produce any uncompressed
41 * data, we can ignore them from our calculations. Block Headers of possible
42 * additional Blocks have to be taken into account still. With these
43 * assumptions, it is safe to assume that the total header overhead is
44 * less than 128 bytes.
45 *
46 * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ
47 * doesn't change the size of the data, it is enough to calculate the
48 * safety margin for LZMA2.
49 *
50 * LZMA2 stores the data in chunks. Each chunk has a header whose size is
51 * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that
52 * the maximum chunk header size is 8 bytes. After the chunk header, there
53 * may be up to 64 KiB of actual payload in the chunk. Often the payload is
54 * quite a bit smaller though; to be safe, let's assume that an average
55 * chunk has only 32 KiB of payload.
56 *
57 * The maximum uncompressed size of the payload is 2 MiB. The minimum
58 * uncompressed size of the payload is in practice never less than the
59 * payload size itself. The LZMA2 format would allow uncompressed size
60 * to be less than the payload size, but no sane compressor creates such
61 * files. LZMA2 supports storing uncompressible data in uncompressed form,
62 * so there's never a need to create payloads whose uncompressed size is
63 * smaller than the compressed size.
64 *
65 * The assumption, that the uncompressed size of the payload is never
66 * smaller than the payload itself, is valid only when talking about
67 * the payload as a whole. It is possible that the payload has parts where
68 * the decompressor consumes more input than it produces output. Calculating
69 * the worst case for this would be tricky. Instead of trying to do that,
70 * let's simply make sure that the decompressor never overwrites any bytes
71 * of the payload which it is currently reading.
72 *
73 * Now we have enough information to calculate the safety margin. We need
74 * - 128 bytes for the .xz file format headers;
75 * - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header
76 * per chunk, each chunk having average payload size of 32 KiB); and
77 * - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that
78 * the decompressor never overwrites anything from the LZMA2 chunk
79 * payload it is currently reading.
80 *
81 * We get the following formula:
82 *
83 * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536
84 * = 128 + (uncompressed_size >> 12) + 65536
85 *
86 * For comparision, according to arch/x86/boot/compressed/misc.c, the
87 * equivalent formula for Deflate is this:
88 *
89 * safety_margin = 18 + (uncompressed_size >> 12) + 32768
90 *
91 * Thus, when updating Deflate-only in-place kernel decompressor to
92 * support XZ, the fixed overhead has to be increased from 18+32768 bytes
93 * to 128+65536 bytes.
94 */
95
96/*
97 * STATIC is defined to "static" if we are being built for kernel
98 * decompression (pre-boot code). <linux/decompress/mm.h> will define
99 * STATIC to empty if it wasn't already defined. Since we will need to
100 * know later if we are being used for kernel decompression, we define
101 * XZ_PREBOOT here.
102 */
103#ifdef STATIC
104# define XZ_PREBOOT
105#endif
106#ifdef __KERNEL__
107# include <linux/decompress/mm.h>
108#endif
109#define XZ_EXTERN STATIC
110
111#ifndef XZ_PREBOOT
112# include <linux/slab.h>
113# include <linux/xz.h>
114#else
115/*
116 * Use the internal CRC32 code instead of kernel's CRC32 module, which
117 * is not available in early phase of booting.
118 */
119#define XZ_INTERNAL_CRC32 1
120
121/*
122 * For boot time use, we enable only the BCJ filter of the current
123 * architecture or none if no BCJ filter is available for the architecture.
124 */
125#ifdef CONFIG_X86
126# define XZ_DEC_X86
127#endif
128#ifdef CONFIG_PPC
129# define XZ_DEC_POWERPC
130#endif
131#ifdef CONFIG_ARM
132# define XZ_DEC_ARM
133#endif
134#ifdef CONFIG_IA64
135# define XZ_DEC_IA64
136#endif
137#ifdef CONFIG_SPARC
138# define XZ_DEC_SPARC
139#endif
140
141/*
142 * This will get the basic headers so that memeq() and others
143 * can be defined.
144 */
145#include "xz/xz_private.h"
146
147/*
148 * Replace the normal allocation functions with the versions from
149 * <linux/decompress/mm.h>. vfree() needs to support vfree(NULL)
150 * when XZ_DYNALLOC is used, but the pre-boot free() doesn't support it.
151 * Workaround it here because the other decompressors don't need it.
152 */
153#undef kmalloc
154#undef kfree
155#undef vmalloc
156#undef vfree
157#define kmalloc(size, flags) malloc(size)
158#define kfree(ptr) free(ptr)
159#define vmalloc(size) malloc(size)
160#define vfree(ptr) do { if (ptr != NULL) free(ptr); } while (0)
161
162/*
163 * FIXME: Not all basic memory functions are provided in architecture-specific
164 * files (yet). We define our own versions here for now, but this should be
165 * only a temporary solution.
166 *
167 * memeq and memzero are not used much and any remotely sane implementation
168 * is fast enough. memcpy/memmove speed matters in multi-call mode, but
169 * the kernel image is decompressed in single-call mode, in which only
170 * memcpy speed can matter and only if there is a lot of uncompressible data
171 * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the
172 * functions below should just be kept small; it's probably not worth
173 * optimizing for speed.
174 */
175
176#ifndef memeq
177static bool memeq(const void *a, const void *b, size_t size)
178{
179 const uint8_t *x = a;
180 const uint8_t *y = b;
181 size_t i;
182
183 for (i = 0; i < size; ++i)
184 if (x[i] != y[i])
185 return false;
186
187 return true;
188}
189#endif
190
191#ifndef memzero
192static void memzero(void *buf, size_t size)
193{
194 uint8_t *b = buf;
195 uint8_t *e = b + size;
196
197 while (b != e)
198 *b++ = '\0';
199}
200#endif
201
202#ifndef memmove
203/* Not static to avoid a conflict with the prototype in the Linux headers. */
204void *memmove(void *dest, const void *src, size_t size)
205{
206 uint8_t *d = dest;
207 const uint8_t *s = src;
208 size_t i;
209
210 if (d < s) {
211 for (i = 0; i < size; ++i)
212 d[i] = s[i];
213 } else if (d > s) {
214 i = size;
215 while (i-- > 0)
216 d[i] = s[i];
217 }
218
219 return dest;
220}
221#endif
222
223/*
224 * Since we need memmove anyway, would use it as memcpy too.
225 * Commented out for now to avoid breaking things.
226 */
227/*
228#ifndef memcpy
229# define memcpy memmove
230#endif
231*/
232
233#include "xz/xz_crc32.c"
234#include "xz/xz_dec_stream.c"
235#include "xz/xz_dec_lzma2.c"
236#include "xz/xz_dec_bcj.c"
237
238#endif /* XZ_PREBOOT */
239
240/* Size of the input and output buffers in multi-call mode */
241#define XZ_IOBUF_SIZE 4096
242
243/*
244 * This function implements the API defined in <linux/decompress/generic.h>.
245 *
246 * This wrapper will automatically choose single-call or multi-call mode
247 * of the native XZ decoder API. The single-call mode can be used only when
248 * both input and output buffers are available as a single chunk, i.e. when
249 * fill() and flush() won't be used.
250 */
251STATIC int INIT unxz(unsigned char *in, int in_size,
252 int (*fill)(void *dest, unsigned int size),
253 int (*flush)(void *src, unsigned int size),
254 unsigned char *out, int *in_used,
255 void (*error)(char *x))
256{
257 struct xz_buf b;
258 struct xz_dec *s;
259 enum xz_ret ret;
260 bool must_free_in = false;
261
262#if XZ_INTERNAL_CRC32
263 xz_crc32_init();
264#endif
265
266 if (in_used != NULL)
267 *in_used = 0;
268
269 if (fill == NULL && flush == NULL)
270 s = xz_dec_init(XZ_SINGLE, 0);
271 else
272 s = xz_dec_init(XZ_DYNALLOC, (uint32_t)-1);
273
274 if (s == NULL)
275 goto error_alloc_state;
276
277 if (flush == NULL) {
278 b.out = out;
279 b.out_size = (size_t)-1;
280 } else {
281 b.out_size = XZ_IOBUF_SIZE;
282 b.out = malloc(XZ_IOBUF_SIZE);
283 if (b.out == NULL)
284 goto error_alloc_out;
285 }
286
287 if (in == NULL) {
288 must_free_in = true;
289 in = malloc(XZ_IOBUF_SIZE);
290 if (in == NULL)
291 goto error_alloc_in;
292 }
293
294 b.in = in;
295 b.in_pos = 0;
296 b.in_size = in_size;
297 b.out_pos = 0;
298
299 if (fill == NULL && flush == NULL) {
300 ret = xz_dec_run(s, &b);
301 } else {
302 do {
303 if (b.in_pos == b.in_size && fill != NULL) {
304 if (in_used != NULL)
305 *in_used += b.in_pos;
306
307 b.in_pos = 0;
308
309 in_size = fill(in, XZ_IOBUF_SIZE);
310 if (in_size < 0) {
311 /*
312 * This isn't an optimal error code
313 * but it probably isn't worth making
314 * a new one either.
315 */
316 ret = XZ_BUF_ERROR;
317 break;
318 }
319
320 b.in_size = in_size;
321 }
322
323 ret = xz_dec_run(s, &b);
324
325 if (flush != NULL && (b.out_pos == b.out_size
326 || (ret != XZ_OK && b.out_pos > 0))) {
327 /*
328 * Setting ret here may hide an error
329 * returned by xz_dec_run(), but probably
330 * it's not too bad.
331 */
332 if (flush(b.out, b.out_pos) != (int)b.out_pos)
333 ret = XZ_BUF_ERROR;
334
335 b.out_pos = 0;
336 }
337 } while (ret == XZ_OK);
338
339 if (must_free_in)
340 free(in);
341
342 if (flush != NULL)
343 free(b.out);
344 }
345
346 if (in_used != NULL)
347 *in_used += b.in_pos;
348
349 xz_dec_end(s);
350
351 switch (ret) {
352 case XZ_STREAM_END:
353 return 0;
354
355 case XZ_MEM_ERROR:
356 /* This can occur only in multi-call mode. */
357 error("XZ decompressor ran out of memory");
358 break;
359
360 case XZ_FORMAT_ERROR:
361 error("Input is not in the XZ format (wrong magic bytes)");
362 break;
363
364 case XZ_OPTIONS_ERROR:
365 error("Input was encoded with settings that are not "
366 "supported by this XZ decoder");
367 break;
368
369 case XZ_DATA_ERROR:
370 case XZ_BUF_ERROR:
371 error("XZ-compressed data is corrupt");
372 break;
373
374 default:
375 error("Bug in the XZ decompressor");
376 break;
377 }
378
379 return -1;
380
381error_alloc_in:
382 if (flush != NULL)
383 free(b.out);
384
385error_alloc_out:
386 xz_dec_end(s);
387
388error_alloc_state:
389 error("XZ decompressor ran out of memory");
390 return -1;
391}
392
393/*
394 * This macro is used by architecture-specific files to decompress
395 * the kernel image.
396 */
397#define decompress unxz
diff --git a/lib/dynamic_debug.c b/lib/dynamic_debug.c
index 3094318bfea7..b335acb43be2 100644
--- a/lib/dynamic_debug.c
+++ b/lib/dynamic_debug.c
@@ -141,11 +141,10 @@ static void ddebug_change(const struct ddebug_query *query,
141 else if (!dp->flags) 141 else if (!dp->flags)
142 dt->num_enabled++; 142 dt->num_enabled++;
143 dp->flags = newflags; 143 dp->flags = newflags;
144 if (newflags) { 144 if (newflags)
145 jump_label_enable(&dp->enabled); 145 dp->enabled = 1;
146 } else { 146 else
147 jump_label_disable(&dp->enabled); 147 dp->enabled = 0;
148 }
149 if (verbose) 148 if (verbose)
150 printk(KERN_INFO 149 printk(KERN_INFO
151 "ddebug: changed %s:%d [%s]%s %s\n", 150 "ddebug: changed %s:%d [%s]%s %s\n",
diff --git a/lib/flex_array.c b/lib/flex_array.c
index 77a6fea7481e..c0ea40ba2082 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -23,6 +23,7 @@
23#include <linux/flex_array.h> 23#include <linux/flex_array.h>
24#include <linux/slab.h> 24#include <linux/slab.h>
25#include <linux/stddef.h> 25#include <linux/stddef.h>
26#include <linux/module.h>
26 27
27struct flex_array_part { 28struct flex_array_part {
28 char elements[FLEX_ARRAY_PART_SIZE]; 29 char elements[FLEX_ARRAY_PART_SIZE];
@@ -103,6 +104,7 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
103 FLEX_ARRAY_BASE_BYTES_LEFT); 104 FLEX_ARRAY_BASE_BYTES_LEFT);
104 return ret; 105 return ret;
105} 106}
107EXPORT_SYMBOL(flex_array_alloc);
106 108
107static int fa_element_to_part_nr(struct flex_array *fa, 109static int fa_element_to_part_nr(struct flex_array *fa,
108 unsigned int element_nr) 110 unsigned int element_nr)
@@ -126,12 +128,14 @@ void flex_array_free_parts(struct flex_array *fa)
126 for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) 128 for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++)
127 kfree(fa->parts[part_nr]); 129 kfree(fa->parts[part_nr]);
128} 130}
131EXPORT_SYMBOL(flex_array_free_parts);
129 132
130void flex_array_free(struct flex_array *fa) 133void flex_array_free(struct flex_array *fa)
131{ 134{
132 flex_array_free_parts(fa); 135 flex_array_free_parts(fa);
133 kfree(fa); 136 kfree(fa);
134} 137}
138EXPORT_SYMBOL(flex_array_free);
135 139
136static unsigned int index_inside_part(struct flex_array *fa, 140static unsigned int index_inside_part(struct flex_array *fa,
137 unsigned int element_nr) 141 unsigned int element_nr)
@@ -196,6 +200,7 @@ int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
196 memcpy(dst, src, fa->element_size); 200 memcpy(dst, src, fa->element_size);
197 return 0; 201 return 0;
198} 202}
203EXPORT_SYMBOL(flex_array_put);
199 204
200/** 205/**
201 * flex_array_clear - clear element in array at @element_nr 206 * flex_array_clear - clear element in array at @element_nr
@@ -223,6 +228,7 @@ int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
223 memset(dst, FLEX_ARRAY_FREE, fa->element_size); 228 memset(dst, FLEX_ARRAY_FREE, fa->element_size);
224 return 0; 229 return 0;
225} 230}
231EXPORT_SYMBOL(flex_array_clear);
226 232
227/** 233/**
228 * flex_array_prealloc - guarantee that array space exists 234 * flex_array_prealloc - guarantee that array space exists
@@ -259,6 +265,7 @@ int flex_array_prealloc(struct flex_array *fa, unsigned int start,
259 } 265 }
260 return 0; 266 return 0;
261} 267}
268EXPORT_SYMBOL(flex_array_prealloc);
262 269
263/** 270/**
264 * flex_array_get - pull data back out of the array 271 * flex_array_get - pull data back out of the array
@@ -288,6 +295,7 @@ void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
288 } 295 }
289 return &part->elements[index_inside_part(fa, element_nr)]; 296 return &part->elements[index_inside_part(fa, element_nr)];
290} 297}
298EXPORT_SYMBOL(flex_array_get);
291 299
292/** 300/**
293 * flex_array_get_ptr - pull a ptr back out of the array 301 * flex_array_get_ptr - pull a ptr back out of the array
@@ -308,6 +316,7 @@ void *flex_array_get_ptr(struct flex_array *fa, unsigned int element_nr)
308 316
309 return *tmp; 317 return *tmp;
310} 318}
319EXPORT_SYMBOL(flex_array_get_ptr);
311 320
312static int part_is_free(struct flex_array_part *part) 321static int part_is_free(struct flex_array_part *part)
313{ 322{
@@ -348,3 +357,4 @@ int flex_array_shrink(struct flex_array *fa)
348 } 357 }
349 return ret; 358 return ret;
350} 359}
360EXPORT_SYMBOL(flex_array_shrink);
diff --git a/lib/hexdump.c b/lib/hexdump.c
index 5d7a4802c562..f5fe6ba7a3ab 100644
--- a/lib/hexdump.c
+++ b/lib/hexdump.c
@@ -34,6 +34,22 @@ int hex_to_bin(char ch)
34EXPORT_SYMBOL(hex_to_bin); 34EXPORT_SYMBOL(hex_to_bin);
35 35
36/** 36/**
37 * hex2bin - convert an ascii hexadecimal string to its binary representation
38 * @dst: binary result
39 * @src: ascii hexadecimal string
40 * @count: result length
41 */
42void hex2bin(u8 *dst, const char *src, size_t count)
43{
44 while (count--) {
45 *dst = hex_to_bin(*src++) << 4;
46 *dst += hex_to_bin(*src++);
47 dst++;
48 }
49}
50EXPORT_SYMBOL(hex2bin);
51
52/**
37 * hex_dump_to_buffer - convert a blob of data to "hex ASCII" in memory 53 * hex_dump_to_buffer - convert a blob of data to "hex ASCII" in memory
38 * @buf: data blob to dump 54 * @buf: data blob to dump
39 * @len: number of bytes in the @buf 55 * @len: number of bytes in the @buf
@@ -138,6 +154,7 @@ nil:
138} 154}
139EXPORT_SYMBOL(hex_dump_to_buffer); 155EXPORT_SYMBOL(hex_dump_to_buffer);
140 156
157#ifdef CONFIG_PRINTK
141/** 158/**
142 * print_hex_dump - print a text hex dump to syslog for a binary blob of data 159 * print_hex_dump - print a text hex dump to syslog for a binary blob of data
143 * @level: kernel log level (e.g. KERN_DEBUG) 160 * @level: kernel log level (e.g. KERN_DEBUG)
@@ -222,3 +239,4 @@ void print_hex_dump_bytes(const char *prefix_str, int prefix_type,
222 buf, len, true); 239 buf, len, true);
223} 240}
224EXPORT_SYMBOL(print_hex_dump_bytes); 241EXPORT_SYMBOL(print_hex_dump_bytes);
242#endif
diff --git a/lib/ioremap.c b/lib/ioremap.c
index 5730ecd3eb66..da4e2ad74b68 100644
--- a/lib/ioremap.c
+++ b/lib/ioremap.c
@@ -9,6 +9,7 @@
9#include <linux/mm.h> 9#include <linux/mm.h>
10#include <linux/sched.h> 10#include <linux/sched.h>
11#include <linux/io.h> 11#include <linux/io.h>
12#include <linux/module.h>
12#include <asm/cacheflush.h> 13#include <asm/cacheflush.h>
13#include <asm/pgtable.h> 14#include <asm/pgtable.h>
14 15
@@ -90,3 +91,4 @@ int ioremap_page_range(unsigned long addr,
90 91
91 return err; 92 return err;
92} 93}
94EXPORT_SYMBOL_GPL(ioremap_page_range);
diff --git a/lib/kref.c b/lib/kref.c
index d3d227a08a4b..3efb882b11db 100644
--- a/lib/kref.c
+++ b/lib/kref.c
@@ -62,6 +62,36 @@ int kref_put(struct kref *kref, void (*release)(struct kref *kref))
62 return 0; 62 return 0;
63} 63}
64 64
65
66/**
67 * kref_sub - subtract a number of refcounts for object.
68 * @kref: object.
69 * @count: Number of recounts to subtract.
70 * @release: pointer to the function that will clean up the object when the
71 * last reference to the object is released.
72 * This pointer is required, and it is not acceptable to pass kfree
73 * in as this function.
74 *
75 * Subtract @count from the refcount, and if 0, call release().
76 * Return 1 if the object was removed, otherwise return 0. Beware, if this
77 * function returns 0, you still can not count on the kref from remaining in
78 * memory. Only use the return value if you want to see if the kref is now
79 * gone, not present.
80 */
81int kref_sub(struct kref *kref, unsigned int count,
82 void (*release)(struct kref *kref))
83{
84 WARN_ON(release == NULL);
85 WARN_ON(release == (void (*)(struct kref *))kfree);
86
87 if (atomic_sub_and_test((int) count, &kref->refcount)) {
88 release(kref);
89 return 1;
90 }
91 return 0;
92}
93
65EXPORT_SYMBOL(kref_init); 94EXPORT_SYMBOL(kref_init);
66EXPORT_SYMBOL(kref_get); 95EXPORT_SYMBOL(kref_get);
67EXPORT_SYMBOL(kref_put); 96EXPORT_SYMBOL(kref_put);
97EXPORT_SYMBOL(kref_sub);
diff --git a/lib/list_debug.c b/lib/list_debug.c
index 344c710d16ca..b8029a5583ff 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -35,6 +35,31 @@ void __list_add(struct list_head *new,
35} 35}
36EXPORT_SYMBOL(__list_add); 36EXPORT_SYMBOL(__list_add);
37 37
38void __list_del_entry(struct list_head *entry)
39{
40 struct list_head *prev, *next;
41
42 prev = entry->prev;
43 next = entry->next;
44
45 if (WARN(next == LIST_POISON1,
46 "list_del corruption, %p->next is LIST_POISON1 (%p)\n",
47 entry, LIST_POISON1) ||
48 WARN(prev == LIST_POISON2,
49 "list_del corruption, %p->prev is LIST_POISON2 (%p)\n",
50 entry, LIST_POISON2) ||
51 WARN(prev->next != entry,
52 "list_del corruption. prev->next should be %p, "
53 "but was %p\n", entry, prev->next) ||
54 WARN(next->prev != entry,
55 "list_del corruption. next->prev should be %p, "
56 "but was %p\n", entry, next->prev))
57 return;
58
59 __list_del(prev, next);
60}
61EXPORT_SYMBOL(__list_del_entry);
62
38/** 63/**
39 * list_del - deletes entry from list. 64 * list_del - deletes entry from list.
40 * @entry: the element to delete from the list. 65 * @entry: the element to delete from the list.
@@ -43,19 +68,7 @@ EXPORT_SYMBOL(__list_add);
43 */ 68 */
44void list_del(struct list_head *entry) 69void list_del(struct list_head *entry)
45{ 70{
46 WARN(entry->next == LIST_POISON1, 71 __list_del_entry(entry);
47 "list_del corruption, next is LIST_POISON1 (%p)\n",
48 LIST_POISON1);
49 WARN(entry->next != LIST_POISON1 && entry->prev == LIST_POISON2,
50 "list_del corruption, prev is LIST_POISON2 (%p)\n",
51 LIST_POISON2);
52 WARN(entry->prev->next != entry,
53 "list_del corruption. prev->next should be %p, "
54 "but was %p\n", entry, entry->prev->next);
55 WARN(entry->next->prev != entry,
56 "list_del corruption. next->prev should be %p, "
57 "but was %p\n", entry, entry->next->prev);
58 __list_del(entry->prev, entry->next);
59 entry->next = LIST_POISON1; 72 entry->next = LIST_POISON1;
60 entry->prev = LIST_POISON2; 73 entry->prev = LIST_POISON2;
61} 74}
diff --git a/lib/nlattr.c b/lib/nlattr.c
index 00e8a02681a6..5021cbc34411 100644
--- a/lib/nlattr.c
+++ b/lib/nlattr.c
@@ -167,7 +167,7 @@ nla_policy_len(const struct nla_policy *p, int n)
167 * @policy: validation policy 167 * @policy: validation policy
168 * 168 *
169 * Parses a stream of attributes and stores a pointer to each attribute in 169 * Parses a stream of attributes and stores a pointer to each attribute in
170 * the tb array accessable via the attribute type. Attributes with a type 170 * the tb array accessible via the attribute type. Attributes with a type
171 * exceeding maxtype will be silently ignored for backwards compatibility 171 * exceeding maxtype will be silently ignored for backwards compatibility
172 * reasons. policy may be set to NULL if no validation is required. 172 * reasons. policy may be set to NULL if no validation is required.
173 * 173 *
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 5086bb962b4d..7ea2e033d715 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -736,10 +736,11 @@ next:
736 } 736 }
737 } 737 }
738 /* 738 /*
739 * The iftag must have been set somewhere because otherwise 739 * We need not to tag the root tag if there is no tag which is set with
740 * we would return immediated at the beginning of the function 740 * settag within the range from *first_indexp to last_index.
741 */ 741 */
742 root_tag_set(root, settag); 742 if (tagged > 0)
743 root_tag_set(root, settag);
743 *first_indexp = index; 744 *first_indexp = index;
744 745
745 return tagged; 746 return tagged;
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 4693f79195d3..a16be19a1305 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -315,6 +315,7 @@ void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
315 315
316 rb_augment_path(node, func, data); 316 rb_augment_path(node, func, data);
317} 317}
318EXPORT_SYMBOL(rb_augment_insert);
318 319
319/* 320/*
320 * before removing the node, find the deepest node on the rebalance path 321 * before removing the node, find the deepest node on the rebalance path
@@ -340,6 +341,7 @@ struct rb_node *rb_augment_erase_begin(struct rb_node *node)
340 341
341 return deepest; 342 return deepest;
342} 343}
344EXPORT_SYMBOL(rb_augment_erase_begin);
343 345
344/* 346/*
345 * after removal, update the tree to account for the removed entry 347 * after removal, update the tree to account for the removed entry
@@ -350,6 +352,7 @@ void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
350 if (node) 352 if (node)
351 rb_augment_path(node, func, data); 353 rb_augment_path(node, func, data);
352} 354}
355EXPORT_SYMBOL(rb_augment_erase_end);
353 356
354/* 357/*
355 * This function returns the first node (in sort order) of the tree. 358 * This function returns the first node (in sort order) of the tree.
diff --git a/lib/swiotlb.c b/lib/swiotlb.c
index 7c06ee51a29a..c47bbe11b804 100644
--- a/lib/swiotlb.c
+++ b/lib/swiotlb.c
@@ -60,7 +60,7 @@ int swiotlb_force;
60static char *io_tlb_start, *io_tlb_end; 60static char *io_tlb_start, *io_tlb_end;
61 61
62/* 62/*
63 * The number of IO TLB blocks (in groups of 64) betweeen io_tlb_start and 63 * The number of IO TLB blocks (in groups of 64) between io_tlb_start and
64 * io_tlb_end. This is command line adjustable via setup_io_tlb_npages. 64 * io_tlb_end. This is command line adjustable via setup_io_tlb_npages.
65 */ 65 */
66static unsigned long io_tlb_nslabs; 66static unsigned long io_tlb_nslabs;
diff --git a/lib/textsearch.c b/lib/textsearch.c
index d608331b3e47..e0cc0146ae62 100644
--- a/lib/textsearch.c
+++ b/lib/textsearch.c
@@ -13,7 +13,7 @@
13 * 13 *
14 * INTRODUCTION 14 * INTRODUCTION
15 * 15 *
16 * The textsearch infrastructure provides text searching facitilies for 16 * The textsearch infrastructure provides text searching facilities for
17 * both linear and non-linear data. Individual search algorithms are 17 * both linear and non-linear data. Individual search algorithms are
18 * implemented in modules and chosen by the user. 18 * implemented in modules and chosen by the user.
19 * 19 *
@@ -43,7 +43,7 @@
43 * to the algorithm to store persistent variables. 43 * to the algorithm to store persistent variables.
44 * (4) Core eventually resets the search offset and forwards the find() 44 * (4) Core eventually resets the search offset and forwards the find()
45 * request to the algorithm. 45 * request to the algorithm.
46 * (5) Algorithm calls get_next_block() provided by the user continously 46 * (5) Algorithm calls get_next_block() provided by the user continuously
47 * to fetch the data to be searched in block by block. 47 * to fetch the data to be searched in block by block.
48 * (6) Algorithm invokes finish() after the last call to get_next_block 48 * (6) Algorithm invokes finish() after the last call to get_next_block
49 * to clean up any leftovers from get_next_block. (Optional) 49 * to clean up any leftovers from get_next_block. (Optional)
@@ -58,15 +58,15 @@
58 * the pattern to look for and flags. As a flag, you can set TS_IGNORECASE 58 * the pattern to look for and flags. As a flag, you can set TS_IGNORECASE
59 * to perform case insensitive matching. But it might slow down 59 * to perform case insensitive matching. But it might slow down
60 * performance of algorithm, so you should use it at own your risk. 60 * performance of algorithm, so you should use it at own your risk.
61 * The returned configuration may then be used for an arbitary 61 * The returned configuration may then be used for an arbitrary
62 * amount of times and even in parallel as long as a separate struct 62 * amount of times and even in parallel as long as a separate struct
63 * ts_state variable is provided to every instance. 63 * ts_state variable is provided to every instance.
64 * 64 *
65 * The actual search is performed by either calling textsearch_find_- 65 * The actual search is performed by either calling textsearch_find_-
66 * continuous() for linear data or by providing an own get_next_block() 66 * continuous() for linear data or by providing an own get_next_block()
67 * implementation and calling textsearch_find(). Both functions return 67 * implementation and calling textsearch_find(). Both functions return
68 * the position of the first occurrence of the patern or UINT_MAX if 68 * the position of the first occurrence of the pattern or UINT_MAX if
69 * no match was found. Subsequent occurences can be found by calling 69 * no match was found. Subsequent occurrences can be found by calling
70 * textsearch_next() regardless of the linearity of the data. 70 * textsearch_next() regardless of the linearity of the data.
71 * 71 *
72 * Once you're done using a configuration it must be given back via 72 * Once you're done using a configuration it must be given back via
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index c150d3dafff4..d3023df8477f 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -936,6 +936,8 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
936 return string(buf, end, uuid, spec); 936 return string(buf, end, uuid, spec);
937} 937}
938 938
939int kptr_restrict = 1;
940
939/* 941/*
940 * Show a '%p' thing. A kernel extension is that the '%p' is followed 942 * Show a '%p' thing. A kernel extension is that the '%p' is followed
941 * by an extra set of alphanumeric characters that are extended format 943 * by an extra set of alphanumeric characters that are extended format
@@ -979,6 +981,7 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
979 * Implements a "recursive vsnprintf". 981 * Implements a "recursive vsnprintf".
980 * Do not use this feature without some mechanism to verify the 982 * Do not use this feature without some mechanism to verify the
981 * correctness of the format string and va_list arguments. 983 * correctness of the format string and va_list arguments.
984 * - 'K' For a kernel pointer that should be hidden from unprivileged users
982 * 985 *
983 * Note: The difference between 'S' and 'F' is that on ia64 and ppc64 986 * Note: The difference between 'S' and 'F' is that on ia64 and ppc64
984 * function pointers are really function descriptors, which contain a 987 * function pointers are really function descriptors, which contain a
@@ -1035,6 +1038,25 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr,
1035 return buf + vsnprintf(buf, end - buf, 1038 return buf + vsnprintf(buf, end - buf,
1036 ((struct va_format *)ptr)->fmt, 1039 ((struct va_format *)ptr)->fmt,
1037 *(((struct va_format *)ptr)->va)); 1040 *(((struct va_format *)ptr)->va));
1041 case 'K':
1042 /*
1043 * %pK cannot be used in IRQ context because its test
1044 * for CAP_SYSLOG would be meaningless.
1045 */
1046 if (in_irq() || in_serving_softirq() || in_nmi()) {
1047 if (spec.field_width == -1)
1048 spec.field_width = 2 * sizeof(void *);
1049 return string(buf, end, "pK-error", spec);
1050 } else if ((kptr_restrict == 0) ||
1051 (kptr_restrict == 1 &&
1052 has_capability_noaudit(current, CAP_SYSLOG)))
1053 break;
1054
1055 if (spec.field_width == -1) {
1056 spec.field_width = 2 * sizeof(void *);
1057 spec.flags |= ZEROPAD;
1058 }
1059 return number(buf, end, 0, spec);
1038 } 1060 }
1039 spec.flags |= SMALL; 1061 spec.flags |= SMALL;
1040 if (spec.field_width == -1) { 1062 if (spec.field_width == -1) {
@@ -1451,7 +1473,7 @@ EXPORT_SYMBOL(vsnprintf);
1451 * @args: Arguments for the format string 1473 * @args: Arguments for the format string
1452 * 1474 *
1453 * The return value is the number of characters which have been written into 1475 * The return value is the number of characters which have been written into
1454 * the @buf not including the trailing '\0'. If @size is <= 0 the function 1476 * the @buf not including the trailing '\0'. If @size is == 0 the function
1455 * returns 0. 1477 * returns 0.
1456 * 1478 *
1457 * Call this function if you are already dealing with a va_list. 1479 * Call this function if you are already dealing with a va_list.
@@ -1465,7 +1487,11 @@ int vscnprintf(char *buf, size_t size, const char *fmt, va_list args)
1465 1487
1466 i = vsnprintf(buf, size, fmt, args); 1488 i = vsnprintf(buf, size, fmt, args);
1467 1489
1468 return (i >= size) ? (size - 1) : i; 1490 if (likely(i < size))
1491 return i;
1492 if (size != 0)
1493 return size - 1;
1494 return 0;
1469} 1495}
1470EXPORT_SYMBOL(vscnprintf); 1496EXPORT_SYMBOL(vscnprintf);
1471 1497
@@ -1513,14 +1539,10 @@ int scnprintf(char *buf, size_t size, const char *fmt, ...)
1513 int i; 1539 int i;
1514 1540
1515 va_start(args, fmt); 1541 va_start(args, fmt);
1516 i = vsnprintf(buf, size, fmt, args); 1542 i = vscnprintf(buf, size, fmt, args);
1517 va_end(args); 1543 va_end(args);
1518 1544
1519 if (likely(i < size)) 1545 return i;
1520 return i;
1521 if (size != 0)
1522 return size - 1;
1523 return 0;
1524} 1546}
1525EXPORT_SYMBOL(scnprintf); 1547EXPORT_SYMBOL(scnprintf);
1526 1548
diff --git a/lib/xz/Kconfig b/lib/xz/Kconfig
new file mode 100644
index 000000000000..60a6088d0e5e
--- /dev/null
+++ b/lib/xz/Kconfig
@@ -0,0 +1,59 @@
1config XZ_DEC
2 tristate "XZ decompression support"
3 select CRC32
4 help
5 LZMA2 compression algorithm and BCJ filters are supported using
6 the .xz file format as the container. For integrity checking,
7 CRC32 is supported. See Documentation/xz.txt for more information.
8
9config XZ_DEC_X86
10 bool "x86 BCJ filter decoder" if EXPERT
11 default y
12 depends on XZ_DEC
13 select XZ_DEC_BCJ
14
15config XZ_DEC_POWERPC
16 bool "PowerPC BCJ filter decoder" if EXPERT
17 default y
18 depends on XZ_DEC
19 select XZ_DEC_BCJ
20
21config XZ_DEC_IA64
22 bool "IA-64 BCJ filter decoder" if EXPERT
23 default y
24 depends on XZ_DEC
25 select XZ_DEC_BCJ
26
27config XZ_DEC_ARM
28 bool "ARM BCJ filter decoder" if EXPERT
29 default y
30 depends on XZ_DEC
31 select XZ_DEC_BCJ
32
33config XZ_DEC_ARMTHUMB
34 bool "ARM-Thumb BCJ filter decoder" if EXPERT
35 default y
36 depends on XZ_DEC
37 select XZ_DEC_BCJ
38
39config XZ_DEC_SPARC
40 bool "SPARC BCJ filter decoder" if EXPERT
41 default y
42 depends on XZ_DEC
43 select XZ_DEC_BCJ
44
45config XZ_DEC_BCJ
46 bool
47 default n
48
49config XZ_DEC_TEST
50 tristate "XZ decompressor tester"
51 default n
52 depends on XZ_DEC
53 help
54 This allows passing .xz files to the in-kernel XZ decoder via
55 a character special file. It calculates CRC32 of the decompressed
56 data and writes diagnostics to the system log.
57
58 Unless you are developing the XZ decoder, you don't need this
59 and should say N.
diff --git a/lib/xz/Makefile b/lib/xz/Makefile
new file mode 100644
index 000000000000..a7fa7693f0f3
--- /dev/null
+++ b/lib/xz/Makefile
@@ -0,0 +1,5 @@
1obj-$(CONFIG_XZ_DEC) += xz_dec.o
2xz_dec-y := xz_dec_syms.o xz_dec_stream.o xz_dec_lzma2.o
3xz_dec-$(CONFIG_XZ_DEC_BCJ) += xz_dec_bcj.o
4
5obj-$(CONFIG_XZ_DEC_TEST) += xz_dec_test.o
diff --git a/lib/xz/xz_crc32.c b/lib/xz/xz_crc32.c
new file mode 100644
index 000000000000..34532d14fd4c
--- /dev/null
+++ b/lib/xz/xz_crc32.c
@@ -0,0 +1,59 @@
1/*
2 * CRC32 using the polynomial from IEEE-802.3
3 *
4 * Authors: Lasse Collin <lasse.collin@tukaani.org>
5 * Igor Pavlov <http://7-zip.org/>
6 *
7 * This file has been put into the public domain.
8 * You can do whatever you want with this file.
9 */
10
11/*
12 * This is not the fastest implementation, but it is pretty compact.
13 * The fastest versions of xz_crc32() on modern CPUs without hardware
14 * accelerated CRC instruction are 3-5 times as fast as this version,
15 * but they are bigger and use more memory for the lookup table.
16 */
17
18#include "xz_private.h"
19
20/*
21 * STATIC_RW_DATA is used in the pre-boot environment on some architectures.
22 * See <linux/decompress/mm.h> for details.
23 */
24#ifndef STATIC_RW_DATA
25# define STATIC_RW_DATA static
26#endif
27
28STATIC_RW_DATA uint32_t xz_crc32_table[256];
29
30XZ_EXTERN void xz_crc32_init(void)
31{
32 const uint32_t poly = 0xEDB88320;
33
34 uint32_t i;
35 uint32_t j;
36 uint32_t r;
37
38 for (i = 0; i < 256; ++i) {
39 r = i;
40 for (j = 0; j < 8; ++j)
41 r = (r >> 1) ^ (poly & ~((r & 1) - 1));
42
43 xz_crc32_table[i] = r;
44 }
45
46 return;
47}
48
49XZ_EXTERN uint32_t xz_crc32(const uint8_t *buf, size_t size, uint32_t crc)
50{
51 crc = ~crc;
52
53 while (size != 0) {
54 crc = xz_crc32_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8);
55 --size;
56 }
57
58 return ~crc;
59}
diff --git a/lib/xz/xz_dec_bcj.c b/lib/xz/xz_dec_bcj.c
new file mode 100644
index 000000000000..e51e2558ca9d
--- /dev/null
+++ b/lib/xz/xz_dec_bcj.c
@@ -0,0 +1,561 @@
1/*
2 * Branch/Call/Jump (BCJ) filter decoders
3 *
4 * Authors: Lasse Collin <lasse.collin@tukaani.org>
5 * Igor Pavlov <http://7-zip.org/>
6 *
7 * This file has been put into the public domain.
8 * You can do whatever you want with this file.
9 */
10
11#include "xz_private.h"
12
13/*
14 * The rest of the file is inside this ifdef. It makes things a little more
15 * convenient when building without support for any BCJ filters.
16 */
17#ifdef XZ_DEC_BCJ
18
19struct xz_dec_bcj {
20 /* Type of the BCJ filter being used */
21 enum {
22 BCJ_X86 = 4, /* x86 or x86-64 */
23 BCJ_POWERPC = 5, /* Big endian only */
24 BCJ_IA64 = 6, /* Big or little endian */
25 BCJ_ARM = 7, /* Little endian only */
26 BCJ_ARMTHUMB = 8, /* Little endian only */
27 BCJ_SPARC = 9 /* Big or little endian */
28 } type;
29
30 /*
31 * Return value of the next filter in the chain. We need to preserve
32 * this information across calls, because we must not call the next
33 * filter anymore once it has returned XZ_STREAM_END.
34 */
35 enum xz_ret ret;
36
37 /* True if we are operating in single-call mode. */
38 bool single_call;
39
40 /*
41 * Absolute position relative to the beginning of the uncompressed
42 * data (in a single .xz Block). We care only about the lowest 32
43 * bits so this doesn't need to be uint64_t even with big files.
44 */
45 uint32_t pos;
46
47 /* x86 filter state */
48 uint32_t x86_prev_mask;
49
50 /* Temporary space to hold the variables from struct xz_buf */
51 uint8_t *out;
52 size_t out_pos;
53 size_t out_size;
54
55 struct {
56 /* Amount of already filtered data in the beginning of buf */
57 size_t filtered;
58
59 /* Total amount of data currently stored in buf */
60 size_t size;
61
62 /*
63 * Buffer to hold a mix of filtered and unfiltered data. This
64 * needs to be big enough to hold Alignment + 2 * Look-ahead:
65 *
66 * Type Alignment Look-ahead
67 * x86 1 4
68 * PowerPC 4 0
69 * IA-64 16 0
70 * ARM 4 0
71 * ARM-Thumb 2 2
72 * SPARC 4 0
73 */
74 uint8_t buf[16];
75 } temp;
76};
77
78#ifdef XZ_DEC_X86
79/*
80 * This is used to test the most significant byte of a memory address
81 * in an x86 instruction.
82 */
83static inline int bcj_x86_test_msbyte(uint8_t b)
84{
85 return b == 0x00 || b == 0xFF;
86}
87
88static size_t bcj_x86(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
89{
90 static const bool mask_to_allowed_status[8]
91 = { true, true, true, false, true, false, false, false };
92
93 static const uint8_t mask_to_bit_num[8] = { 0, 1, 2, 2, 3, 3, 3, 3 };
94
95 size_t i;
96 size_t prev_pos = (size_t)-1;
97 uint32_t prev_mask = s->x86_prev_mask;
98 uint32_t src;
99 uint32_t dest;
100 uint32_t j;
101 uint8_t b;
102
103 if (size <= 4)
104 return 0;
105
106 size -= 4;
107 for (i = 0; i < size; ++i) {
108 if ((buf[i] & 0xFE) != 0xE8)
109 continue;
110
111 prev_pos = i - prev_pos;
112 if (prev_pos > 3) {
113 prev_mask = 0;
114 } else {
115 prev_mask = (prev_mask << (prev_pos - 1)) & 7;
116 if (prev_mask != 0) {
117 b = buf[i + 4 - mask_to_bit_num[prev_mask]];
118 if (!mask_to_allowed_status[prev_mask]
119 || bcj_x86_test_msbyte(b)) {
120 prev_pos = i;
121 prev_mask = (prev_mask << 1) | 1;
122 continue;
123 }
124 }
125 }
126
127 prev_pos = i;
128
129 if (bcj_x86_test_msbyte(buf[i + 4])) {
130 src = get_unaligned_le32(buf + i + 1);
131 while (true) {
132 dest = src - (s->pos + (uint32_t)i + 5);
133 if (prev_mask == 0)
134 break;
135
136 j = mask_to_bit_num[prev_mask] * 8;
137 b = (uint8_t)(dest >> (24 - j));
138 if (!bcj_x86_test_msbyte(b))
139 break;
140
141 src = dest ^ (((uint32_t)1 << (32 - j)) - 1);
142 }
143
144 dest &= 0x01FFFFFF;
145 dest |= (uint32_t)0 - (dest & 0x01000000);
146 put_unaligned_le32(dest, buf + i + 1);
147 i += 4;
148 } else {
149 prev_mask = (prev_mask << 1) | 1;
150 }
151 }
152
153 prev_pos = i - prev_pos;
154 s->x86_prev_mask = prev_pos > 3 ? 0 : prev_mask << (prev_pos - 1);
155 return i;
156}
157#endif
158
159#ifdef XZ_DEC_POWERPC
160static size_t bcj_powerpc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
161{
162 size_t i;
163 uint32_t instr;
164
165 for (i = 0; i + 4 <= size; i += 4) {
166 instr = get_unaligned_be32(buf + i);
167 if ((instr & 0xFC000003) == 0x48000001) {
168 instr &= 0x03FFFFFC;
169 instr -= s->pos + (uint32_t)i;
170 instr &= 0x03FFFFFC;
171 instr |= 0x48000001;
172 put_unaligned_be32(instr, buf + i);
173 }
174 }
175
176 return i;
177}
178#endif
179
180#ifdef XZ_DEC_IA64
181static size_t bcj_ia64(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
182{
183 static const uint8_t branch_table[32] = {
184 0, 0, 0, 0, 0, 0, 0, 0,
185 0, 0, 0, 0, 0, 0, 0, 0,
186 4, 4, 6, 6, 0, 0, 7, 7,
187 4, 4, 0, 0, 4, 4, 0, 0
188 };
189
190 /*
191 * The local variables take a little bit stack space, but it's less
192 * than what LZMA2 decoder takes, so it doesn't make sense to reduce
193 * stack usage here without doing that for the LZMA2 decoder too.
194 */
195
196 /* Loop counters */
197 size_t i;
198 size_t j;
199
200 /* Instruction slot (0, 1, or 2) in the 128-bit instruction word */
201 uint32_t slot;
202
203 /* Bitwise offset of the instruction indicated by slot */
204 uint32_t bit_pos;
205
206 /* bit_pos split into byte and bit parts */
207 uint32_t byte_pos;
208 uint32_t bit_res;
209
210 /* Address part of an instruction */
211 uint32_t addr;
212
213 /* Mask used to detect which instructions to convert */
214 uint32_t mask;
215
216 /* 41-bit instruction stored somewhere in the lowest 48 bits */
217 uint64_t instr;
218
219 /* Instruction normalized with bit_res for easier manipulation */
220 uint64_t norm;
221
222 for (i = 0; i + 16 <= size; i += 16) {
223 mask = branch_table[buf[i] & 0x1F];
224 for (slot = 0, bit_pos = 5; slot < 3; ++slot, bit_pos += 41) {
225 if (((mask >> slot) & 1) == 0)
226 continue;
227
228 byte_pos = bit_pos >> 3;
229 bit_res = bit_pos & 7;
230 instr = 0;
231 for (j = 0; j < 6; ++j)
232 instr |= (uint64_t)(buf[i + j + byte_pos])
233 << (8 * j);
234
235 norm = instr >> bit_res;
236
237 if (((norm >> 37) & 0x0F) == 0x05
238 && ((norm >> 9) & 0x07) == 0) {
239 addr = (norm >> 13) & 0x0FFFFF;
240 addr |= ((uint32_t)(norm >> 36) & 1) << 20;
241 addr <<= 4;
242 addr -= s->pos + (uint32_t)i;
243 addr >>= 4;
244
245 norm &= ~((uint64_t)0x8FFFFF << 13);
246 norm |= (uint64_t)(addr & 0x0FFFFF) << 13;
247 norm |= (uint64_t)(addr & 0x100000)
248 << (36 - 20);
249
250 instr &= (1 << bit_res) - 1;
251 instr |= norm << bit_res;
252
253 for (j = 0; j < 6; j++)
254 buf[i + j + byte_pos]
255 = (uint8_t)(instr >> (8 * j));
256 }
257 }
258 }
259
260 return i;
261}
262#endif
263
264#ifdef XZ_DEC_ARM
265static size_t bcj_arm(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
266{
267 size_t i;
268 uint32_t addr;
269
270 for (i = 0; i + 4 <= size; i += 4) {
271 if (buf[i + 3] == 0xEB) {
272 addr = (uint32_t)buf[i] | ((uint32_t)buf[i + 1] << 8)
273 | ((uint32_t)buf[i + 2] << 16);
274 addr <<= 2;
275 addr -= s->pos + (uint32_t)i + 8;
276 addr >>= 2;
277 buf[i] = (uint8_t)addr;
278 buf[i + 1] = (uint8_t)(addr >> 8);
279 buf[i + 2] = (uint8_t)(addr >> 16);
280 }
281 }
282
283 return i;
284}
285#endif
286
287#ifdef XZ_DEC_ARMTHUMB
288static size_t bcj_armthumb(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
289{
290 size_t i;
291 uint32_t addr;
292
293 for (i = 0; i + 4 <= size; i += 2) {
294 if ((buf[i + 1] & 0xF8) == 0xF0
295 && (buf[i + 3] & 0xF8) == 0xF8) {
296 addr = (((uint32_t)buf[i + 1] & 0x07) << 19)
297 | ((uint32_t)buf[i] << 11)
298 | (((uint32_t)buf[i + 3] & 0x07) << 8)
299 | (uint32_t)buf[i + 2];
300 addr <<= 1;
301 addr -= s->pos + (uint32_t)i + 4;
302 addr >>= 1;
303 buf[i + 1] = (uint8_t)(0xF0 | ((addr >> 19) & 0x07));
304 buf[i] = (uint8_t)(addr >> 11);
305 buf[i + 3] = (uint8_t)(0xF8 | ((addr >> 8) & 0x07));
306 buf[i + 2] = (uint8_t)addr;
307 i += 2;
308 }
309 }
310
311 return i;
312}
313#endif
314
315#ifdef XZ_DEC_SPARC
316static size_t bcj_sparc(struct xz_dec_bcj *s, uint8_t *buf, size_t size)
317{
318 size_t i;
319 uint32_t instr;
320
321 for (i = 0; i + 4 <= size; i += 4) {
322 instr = get_unaligned_be32(buf + i);
323 if ((instr >> 22) == 0x100 || (instr >> 22) == 0x1FF) {
324 instr <<= 2;
325 instr -= s->pos + (uint32_t)i;
326 instr >>= 2;
327 instr = ((uint32_t)0x40000000 - (instr & 0x400000))
328 | 0x40000000 | (instr & 0x3FFFFF);
329 put_unaligned_be32(instr, buf + i);
330 }
331 }
332
333 return i;
334}
335#endif
336
337/*
338 * Apply the selected BCJ filter. Update *pos and s->pos to match the amount
339 * of data that got filtered.
340 *
341 * NOTE: This is implemented as a switch statement to avoid using function
342 * pointers, which could be problematic in the kernel boot code, which must
343 * avoid pointers to static data (at least on x86).
344 */
345static void bcj_apply(struct xz_dec_bcj *s,
346 uint8_t *buf, size_t *pos, size_t size)
347{
348 size_t filtered;
349
350 buf += *pos;
351 size -= *pos;
352
353 switch (s->type) {
354#ifdef XZ_DEC_X86
355 case BCJ_X86:
356 filtered = bcj_x86(s, buf, size);
357 break;
358#endif
359#ifdef XZ_DEC_POWERPC
360 case BCJ_POWERPC:
361 filtered = bcj_powerpc(s, buf, size);
362 break;
363#endif
364#ifdef XZ_DEC_IA64
365 case BCJ_IA64:
366 filtered = bcj_ia64(s, buf, size);
367 break;
368#endif
369#ifdef XZ_DEC_ARM
370 case BCJ_ARM:
371 filtered = bcj_arm(s, buf, size);
372 break;
373#endif
374#ifdef XZ_DEC_ARMTHUMB
375 case BCJ_ARMTHUMB:
376 filtered = bcj_armthumb(s, buf, size);
377 break;
378#endif
379#ifdef XZ_DEC_SPARC
380 case BCJ_SPARC:
381 filtered = bcj_sparc(s, buf, size);
382 break;
383#endif
384 default:
385 /* Never reached but silence compiler warnings. */
386 filtered = 0;
387 break;
388 }
389
390 *pos += filtered;
391 s->pos += filtered;
392}
393
394/*
395 * Flush pending filtered data from temp to the output buffer.
396 * Move the remaining mixture of possibly filtered and unfiltered
397 * data to the beginning of temp.
398 */
399static void bcj_flush(struct xz_dec_bcj *s, struct xz_buf *b)
400{
401 size_t copy_size;
402
403 copy_size = min_t(size_t, s->temp.filtered, b->out_size - b->out_pos);
404 memcpy(b->out + b->out_pos, s->temp.buf, copy_size);
405 b->out_pos += copy_size;
406
407 s->temp.filtered -= copy_size;
408 s->temp.size -= copy_size;
409 memmove(s->temp.buf, s->temp.buf + copy_size, s->temp.size);
410}
411
412/*
413 * The BCJ filter functions are primitive in sense that they process the
414 * data in chunks of 1-16 bytes. To hide this issue, this function does
415 * some buffering.
416 */
417XZ_EXTERN enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s,
418 struct xz_dec_lzma2 *lzma2,
419 struct xz_buf *b)
420{
421 size_t out_start;
422
423 /*
424 * Flush pending already filtered data to the output buffer. Return
425 * immediatelly if we couldn't flush everything, or if the next
426 * filter in the chain had already returned XZ_STREAM_END.
427 */
428 if (s->temp.filtered > 0) {
429 bcj_flush(s, b);
430 if (s->temp.filtered > 0)
431 return XZ_OK;
432
433 if (s->ret == XZ_STREAM_END)
434 return XZ_STREAM_END;
435 }
436
437 /*
438 * If we have more output space than what is currently pending in
439 * temp, copy the unfiltered data from temp to the output buffer
440 * and try to fill the output buffer by decoding more data from the
441 * next filter in the chain. Apply the BCJ filter on the new data
442 * in the output buffer. If everything cannot be filtered, copy it
443 * to temp and rewind the output buffer position accordingly.
444 */
445 if (s->temp.size < b->out_size - b->out_pos) {
446 out_start = b->out_pos;
447 memcpy(b->out + b->out_pos, s->temp.buf, s->temp.size);
448 b->out_pos += s->temp.size;
449
450 s->ret = xz_dec_lzma2_run(lzma2, b);
451 if (s->ret != XZ_STREAM_END
452 && (s->ret != XZ_OK || s->single_call))
453 return s->ret;
454
455 bcj_apply(s, b->out, &out_start, b->out_pos);
456
457 /*
458 * As an exception, if the next filter returned XZ_STREAM_END,
459 * we can do that too, since the last few bytes that remain
460 * unfiltered are meant to remain unfiltered.
461 */
462 if (s->ret == XZ_STREAM_END)
463 return XZ_STREAM_END;
464
465 s->temp.size = b->out_pos - out_start;
466 b->out_pos -= s->temp.size;
467 memcpy(s->temp.buf, b->out + b->out_pos, s->temp.size);
468 }
469
470 /*
471 * If we have unfiltered data in temp, try to fill by decoding more
472 * data from the next filter. Apply the BCJ filter on temp. Then we
473 * hopefully can fill the actual output buffer by copying filtered
474 * data from temp. A mix of filtered and unfiltered data may be left
475 * in temp; it will be taken care on the next call to this function.
476 */
477 if (s->temp.size > 0) {
478 /* Make b->out{,_pos,_size} temporarily point to s->temp. */
479 s->out = b->out;
480 s->out_pos = b->out_pos;
481 s->out_size = b->out_size;
482 b->out = s->temp.buf;
483 b->out_pos = s->temp.size;
484 b->out_size = sizeof(s->temp.buf);
485
486 s->ret = xz_dec_lzma2_run(lzma2, b);
487
488 s->temp.size = b->out_pos;
489 b->out = s->out;
490 b->out_pos = s->out_pos;
491 b->out_size = s->out_size;
492
493 if (s->ret != XZ_OK && s->ret != XZ_STREAM_END)
494 return s->ret;
495
496 bcj_apply(s, s->temp.buf, &s->temp.filtered, s->temp.size);
497
498 /*
499 * If the next filter returned XZ_STREAM_END, we mark that
500 * everything is filtered, since the last unfiltered bytes
501 * of the stream are meant to be left as is.
502 */
503 if (s->ret == XZ_STREAM_END)
504 s->temp.filtered = s->temp.size;
505
506 bcj_flush(s, b);
507 if (s->temp.filtered > 0)
508 return XZ_OK;
509 }
510
511 return s->ret;
512}
513
514XZ_EXTERN struct xz_dec_bcj *xz_dec_bcj_create(bool single_call)
515{
516 struct xz_dec_bcj *s = kmalloc(sizeof(*s), GFP_KERNEL);
517 if (s != NULL)
518 s->single_call = single_call;
519
520 return s;
521}
522
523XZ_EXTERN enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id)
524{
525 switch (id) {
526#ifdef XZ_DEC_X86
527 case BCJ_X86:
528#endif
529#ifdef XZ_DEC_POWERPC
530 case BCJ_POWERPC:
531#endif
532#ifdef XZ_DEC_IA64
533 case BCJ_IA64:
534#endif
535#ifdef XZ_DEC_ARM
536 case BCJ_ARM:
537#endif
538#ifdef XZ_DEC_ARMTHUMB
539 case BCJ_ARMTHUMB:
540#endif
541#ifdef XZ_DEC_SPARC
542 case BCJ_SPARC:
543#endif
544 break;
545
546 default:
547 /* Unsupported Filter ID */
548 return XZ_OPTIONS_ERROR;
549 }
550
551 s->type = id;
552 s->ret = XZ_OK;
553 s->pos = 0;
554 s->x86_prev_mask = 0;
555 s->temp.filtered = 0;
556 s->temp.size = 0;
557
558 return XZ_OK;
559}
560
561#endif
diff --git a/lib/xz/xz_dec_lzma2.c b/lib/xz/xz_dec_lzma2.c
new file mode 100644
index 000000000000..ea5fa4fe9d67
--- /dev/null
+++ b/lib/xz/xz_dec_lzma2.c
@@ -0,0 +1,1171 @@
1/*
2 * LZMA2 decoder
3 *
4 * Authors: Lasse Collin <lasse.collin@tukaani.org>
5 * Igor Pavlov <http://7-zip.org/>
6 *
7 * This file has been put into the public domain.
8 * You can do whatever you want with this file.
9 */
10
11#include "xz_private.h"
12#include "xz_lzma2.h"
13
14/*
15 * Range decoder initialization eats the first five bytes of each LZMA chunk.
16 */
17#define RC_INIT_BYTES 5
18
19/*
20 * Minimum number of usable input buffer to safely decode one LZMA symbol.
21 * The worst case is that we decode 22 bits using probabilities and 26
22 * direct bits. This may decode at maximum of 20 bytes of input. However,
23 * lzma_main() does an extra normalization before returning, thus we
24 * need to put 21 here.
25 */
26#define LZMA_IN_REQUIRED 21
27
28/*
29 * Dictionary (history buffer)
30 *
31 * These are always true:
32 * start <= pos <= full <= end
33 * pos <= limit <= end
34 *
35 * In multi-call mode, also these are true:
36 * end == size
37 * size <= size_max
38 * allocated <= size
39 *
40 * Most of these variables are size_t to support single-call mode,
41 * in which the dictionary variables address the actual output
42 * buffer directly.
43 */
44struct dictionary {
45 /* Beginning of the history buffer */
46 uint8_t *buf;
47
48 /* Old position in buf (before decoding more data) */
49 size_t start;
50
51 /* Position in buf */
52 size_t pos;
53
54 /*
55 * How full dictionary is. This is used to detect corrupt input that
56 * would read beyond the beginning of the uncompressed stream.
57 */
58 size_t full;
59
60 /* Write limit; we don't write to buf[limit] or later bytes. */
61 size_t limit;
62
63 /*
64 * End of the dictionary buffer. In multi-call mode, this is
65 * the same as the dictionary size. In single-call mode, this
66 * indicates the size of the output buffer.
67 */
68 size_t end;
69
70 /*
71 * Size of the dictionary as specified in Block Header. This is used
72 * together with "full" to detect corrupt input that would make us
73 * read beyond the beginning of the uncompressed stream.
74 */
75 uint32_t size;
76
77 /*
78 * Maximum allowed dictionary size in multi-call mode.
79 * This is ignored in single-call mode.
80 */
81 uint32_t size_max;
82
83 /*
84 * Amount of memory currently allocated for the dictionary.
85 * This is used only with XZ_DYNALLOC. (With XZ_PREALLOC,
86 * size_max is always the same as the allocated size.)
87 */
88 uint32_t allocated;
89
90 /* Operation mode */
91 enum xz_mode mode;
92};
93
94/* Range decoder */
95struct rc_dec {
96 uint32_t range;
97 uint32_t code;
98
99 /*
100 * Number of initializing bytes remaining to be read
101 * by rc_read_init().
102 */
103 uint32_t init_bytes_left;
104
105 /*
106 * Buffer from which we read our input. It can be either
107 * temp.buf or the caller-provided input buffer.
108 */
109 const uint8_t *in;
110 size_t in_pos;
111 size_t in_limit;
112};
113
114/* Probabilities for a length decoder. */
115struct lzma_len_dec {
116 /* Probability of match length being at least 10 */
117 uint16_t choice;
118
119 /* Probability of match length being at least 18 */
120 uint16_t choice2;
121
122 /* Probabilities for match lengths 2-9 */
123 uint16_t low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
124
125 /* Probabilities for match lengths 10-17 */
126 uint16_t mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
127
128 /* Probabilities for match lengths 18-273 */
129 uint16_t high[LEN_HIGH_SYMBOLS];
130};
131
132struct lzma_dec {
133 /* Distances of latest four matches */
134 uint32_t rep0;
135 uint32_t rep1;
136 uint32_t rep2;
137 uint32_t rep3;
138
139 /* Types of the most recently seen LZMA symbols */
140 enum lzma_state state;
141
142 /*
143 * Length of a match. This is updated so that dict_repeat can
144 * be called again to finish repeating the whole match.
145 */
146 uint32_t len;
147
148 /*
149 * LZMA properties or related bit masks (number of literal
150 * context bits, a mask dervied from the number of literal
151 * position bits, and a mask dervied from the number
152 * position bits)
153 */
154 uint32_t lc;
155 uint32_t literal_pos_mask; /* (1 << lp) - 1 */
156 uint32_t pos_mask; /* (1 << pb) - 1 */
157
158 /* If 1, it's a match. Otherwise it's a single 8-bit literal. */
159 uint16_t is_match[STATES][POS_STATES_MAX];
160
161 /* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */
162 uint16_t is_rep[STATES];
163
164 /*
165 * If 0, distance of a repeated match is rep0.
166 * Otherwise check is_rep1.
167 */
168 uint16_t is_rep0[STATES];
169
170 /*
171 * If 0, distance of a repeated match is rep1.
172 * Otherwise check is_rep2.
173 */
174 uint16_t is_rep1[STATES];
175
176 /* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */
177 uint16_t is_rep2[STATES];
178
179 /*
180 * If 1, the repeated match has length of one byte. Otherwise
181 * the length is decoded from rep_len_decoder.
182 */
183 uint16_t is_rep0_long[STATES][POS_STATES_MAX];
184
185 /*
186 * Probability tree for the highest two bits of the match
187 * distance. There is a separate probability tree for match
188 * lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
189 */
190 uint16_t dist_slot[DIST_STATES][DIST_SLOTS];
191
192 /*
193 * Probility trees for additional bits for match distance
194 * when the distance is in the range [4, 127].
195 */
196 uint16_t dist_special[FULL_DISTANCES - DIST_MODEL_END];
197
198 /*
199 * Probability tree for the lowest four bits of a match
200 * distance that is equal to or greater than 128.
201 */
202 uint16_t dist_align[ALIGN_SIZE];
203
204 /* Length of a normal match */
205 struct lzma_len_dec match_len_dec;
206
207 /* Length of a repeated match */
208 struct lzma_len_dec rep_len_dec;
209
210 /* Probabilities of literals */
211 uint16_t literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE];
212};
213
214struct lzma2_dec {
215 /* Position in xz_dec_lzma2_run(). */
216 enum lzma2_seq {
217 SEQ_CONTROL,
218 SEQ_UNCOMPRESSED_1,
219 SEQ_UNCOMPRESSED_2,
220 SEQ_COMPRESSED_0,
221 SEQ_COMPRESSED_1,
222 SEQ_PROPERTIES,
223 SEQ_LZMA_PREPARE,
224 SEQ_LZMA_RUN,
225 SEQ_COPY
226 } sequence;
227
228 /* Next position after decoding the compressed size of the chunk. */
229 enum lzma2_seq next_sequence;
230
231 /* Uncompressed size of LZMA chunk (2 MiB at maximum) */
232 uint32_t uncompressed;
233
234 /*
235 * Compressed size of LZMA chunk or compressed/uncompressed
236 * size of uncompressed chunk (64 KiB at maximum)
237 */
238 uint32_t compressed;
239
240 /*
241 * True if dictionary reset is needed. This is false before
242 * the first chunk (LZMA or uncompressed).
243 */
244 bool need_dict_reset;
245
246 /*
247 * True if new LZMA properties are needed. This is false
248 * before the first LZMA chunk.
249 */
250 bool need_props;
251};
252
253struct xz_dec_lzma2 {
254 /*
255 * The order below is important on x86 to reduce code size and
256 * it shouldn't hurt on other platforms. Everything up to and
257 * including lzma.pos_mask are in the first 128 bytes on x86-32,
258 * which allows using smaller instructions to access those
259 * variables. On x86-64, fewer variables fit into the first 128
260 * bytes, but this is still the best order without sacrificing
261 * the readability by splitting the structures.
262 */
263 struct rc_dec rc;
264 struct dictionary dict;
265 struct lzma2_dec lzma2;
266 struct lzma_dec lzma;
267
268 /*
269 * Temporary buffer which holds small number of input bytes between
270 * decoder calls. See lzma2_lzma() for details.
271 */
272 struct {
273 uint32_t size;
274 uint8_t buf[3 * LZMA_IN_REQUIRED];
275 } temp;
276};
277
278/**************
279 * Dictionary *
280 **************/
281
282/*
283 * Reset the dictionary state. When in single-call mode, set up the beginning
284 * of the dictionary to point to the actual output buffer.
285 */
286static void dict_reset(struct dictionary *dict, struct xz_buf *b)
287{
288 if (DEC_IS_SINGLE(dict->mode)) {
289 dict->buf = b->out + b->out_pos;
290 dict->end = b->out_size - b->out_pos;
291 }
292
293 dict->start = 0;
294 dict->pos = 0;
295 dict->limit = 0;
296 dict->full = 0;
297}
298
299/* Set dictionary write limit */
300static void dict_limit(struct dictionary *dict, size_t out_max)
301{
302 if (dict->end - dict->pos <= out_max)
303 dict->limit = dict->end;
304 else
305 dict->limit = dict->pos + out_max;
306}
307
308/* Return true if at least one byte can be written into the dictionary. */
309static inline bool dict_has_space(const struct dictionary *dict)
310{
311 return dict->pos < dict->limit;
312}
313
314/*
315 * Get a byte from the dictionary at the given distance. The distance is
316 * assumed to valid, or as a special case, zero when the dictionary is
317 * still empty. This special case is needed for single-call decoding to
318 * avoid writing a '\0' to the end of the destination buffer.
319 */
320static inline uint32_t dict_get(const struct dictionary *dict, uint32_t dist)
321{
322 size_t offset = dict->pos - dist - 1;
323
324 if (dist >= dict->pos)
325 offset += dict->end;
326
327 return dict->full > 0 ? dict->buf[offset] : 0;
328}
329
330/*
331 * Put one byte into the dictionary. It is assumed that there is space for it.
332 */
333static inline void dict_put(struct dictionary *dict, uint8_t byte)
334{
335 dict->buf[dict->pos++] = byte;
336
337 if (dict->full < dict->pos)
338 dict->full = dict->pos;
339}
340
341/*
342 * Repeat given number of bytes from the given distance. If the distance is
343 * invalid, false is returned. On success, true is returned and *len is
344 * updated to indicate how many bytes were left to be repeated.
345 */
346static bool dict_repeat(struct dictionary *dict, uint32_t *len, uint32_t dist)
347{
348 size_t back;
349 uint32_t left;
350
351 if (dist >= dict->full || dist >= dict->size)
352 return false;
353
354 left = min_t(size_t, dict->limit - dict->pos, *len);
355 *len -= left;
356
357 back = dict->pos - dist - 1;
358 if (dist >= dict->pos)
359 back += dict->end;
360
361 do {
362 dict->buf[dict->pos++] = dict->buf[back++];
363 if (back == dict->end)
364 back = 0;
365 } while (--left > 0);
366
367 if (dict->full < dict->pos)
368 dict->full = dict->pos;
369
370 return true;
371}
372
373/* Copy uncompressed data as is from input to dictionary and output buffers. */
374static void dict_uncompressed(struct dictionary *dict, struct xz_buf *b,
375 uint32_t *left)
376{
377 size_t copy_size;
378
379 while (*left > 0 && b->in_pos < b->in_size
380 && b->out_pos < b->out_size) {
381 copy_size = min(b->in_size - b->in_pos,
382 b->out_size - b->out_pos);
383 if (copy_size > dict->end - dict->pos)
384 copy_size = dict->end - dict->pos;
385 if (copy_size > *left)
386 copy_size = *left;
387
388 *left -= copy_size;
389
390 memcpy(dict->buf + dict->pos, b->in + b->in_pos, copy_size);
391 dict->pos += copy_size;
392
393 if (dict->full < dict->pos)
394 dict->full = dict->pos;
395
396 if (DEC_IS_MULTI(dict->mode)) {
397 if (dict->pos == dict->end)
398 dict->pos = 0;
399
400 memcpy(b->out + b->out_pos, b->in + b->in_pos,
401 copy_size);
402 }
403
404 dict->start = dict->pos;
405
406 b->out_pos += copy_size;
407 b->in_pos += copy_size;
408 }
409}
410
411/*
412 * Flush pending data from dictionary to b->out. It is assumed that there is
413 * enough space in b->out. This is guaranteed because caller uses dict_limit()
414 * before decoding data into the dictionary.
415 */
416static uint32_t dict_flush(struct dictionary *dict, struct xz_buf *b)
417{
418 size_t copy_size = dict->pos - dict->start;
419
420 if (DEC_IS_MULTI(dict->mode)) {
421 if (dict->pos == dict->end)
422 dict->pos = 0;
423
424 memcpy(b->out + b->out_pos, dict->buf + dict->start,
425 copy_size);
426 }
427
428 dict->start = dict->pos;
429 b->out_pos += copy_size;
430 return copy_size;
431}
432
433/*****************
434 * Range decoder *
435 *****************/
436
437/* Reset the range decoder. */
438static void rc_reset(struct rc_dec *rc)
439{
440 rc->range = (uint32_t)-1;
441 rc->code = 0;
442 rc->init_bytes_left = RC_INIT_BYTES;
443}
444
445/*
446 * Read the first five initial bytes into rc->code if they haven't been
447 * read already. (Yes, the first byte gets completely ignored.)
448 */
449static bool rc_read_init(struct rc_dec *rc, struct xz_buf *b)
450{
451 while (rc->init_bytes_left > 0) {
452 if (b->in_pos == b->in_size)
453 return false;
454
455 rc->code = (rc->code << 8) + b->in[b->in_pos++];
456 --rc->init_bytes_left;
457 }
458
459 return true;
460}
461
462/* Return true if there may not be enough input for the next decoding loop. */
463static inline bool rc_limit_exceeded(const struct rc_dec *rc)
464{
465 return rc->in_pos > rc->in_limit;
466}
467
468/*
469 * Return true if it is possible (from point of view of range decoder) that
470 * we have reached the end of the LZMA chunk.
471 */
472static inline bool rc_is_finished(const struct rc_dec *rc)
473{
474 return rc->code == 0;
475}
476
477/* Read the next input byte if needed. */
478static __always_inline void rc_normalize(struct rc_dec *rc)
479{
480 if (rc->range < RC_TOP_VALUE) {
481 rc->range <<= RC_SHIFT_BITS;
482 rc->code = (rc->code << RC_SHIFT_BITS) + rc->in[rc->in_pos++];
483 }
484}
485
486/*
487 * Decode one bit. In some versions, this function has been splitted in three
488 * functions so that the compiler is supposed to be able to more easily avoid
489 * an extra branch. In this particular version of the LZMA decoder, this
490 * doesn't seem to be a good idea (tested with GCC 3.3.6, 3.4.6, and 4.3.3
491 * on x86). Using a non-splitted version results in nicer looking code too.
492 *
493 * NOTE: This must return an int. Do not make it return a bool or the speed
494 * of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care,
495 * and it generates 10-20 % faster code than GCC 3.x from this file anyway.)
496 */
497static __always_inline int rc_bit(struct rc_dec *rc, uint16_t *prob)
498{
499 uint32_t bound;
500 int bit;
501
502 rc_normalize(rc);
503 bound = (rc->range >> RC_BIT_MODEL_TOTAL_BITS) * *prob;
504 if (rc->code < bound) {
505 rc->range = bound;
506 *prob += (RC_BIT_MODEL_TOTAL - *prob) >> RC_MOVE_BITS;
507 bit = 0;
508 } else {
509 rc->range -= bound;
510 rc->code -= bound;
511 *prob -= *prob >> RC_MOVE_BITS;
512 bit = 1;
513 }
514
515 return bit;
516}
517
518/* Decode a bittree starting from the most significant bit. */
519static __always_inline uint32_t rc_bittree(struct rc_dec *rc,
520 uint16_t *probs, uint32_t limit)
521{
522 uint32_t symbol = 1;
523
524 do {
525 if (rc_bit(rc, &probs[symbol]))
526 symbol = (symbol << 1) + 1;
527 else
528 symbol <<= 1;
529 } while (symbol < limit);
530
531 return symbol;
532}
533
534/* Decode a bittree starting from the least significant bit. */
535static __always_inline void rc_bittree_reverse(struct rc_dec *rc,
536 uint16_t *probs,
537 uint32_t *dest, uint32_t limit)
538{
539 uint32_t symbol = 1;
540 uint32_t i = 0;
541
542 do {
543 if (rc_bit(rc, &probs[symbol])) {
544 symbol = (symbol << 1) + 1;
545 *dest += 1 << i;
546 } else {
547 symbol <<= 1;
548 }
549 } while (++i < limit);
550}
551
552/* Decode direct bits (fixed fifty-fifty probability) */
553static inline void rc_direct(struct rc_dec *rc, uint32_t *dest, uint32_t limit)
554{
555 uint32_t mask;
556
557 do {
558 rc_normalize(rc);
559 rc->range >>= 1;
560 rc->code -= rc->range;
561 mask = (uint32_t)0 - (rc->code >> 31);
562 rc->code += rc->range & mask;
563 *dest = (*dest << 1) + (mask + 1);
564 } while (--limit > 0);
565}
566
567/********
568 * LZMA *
569 ********/
570
571/* Get pointer to literal coder probability array. */
572static uint16_t *lzma_literal_probs(struct xz_dec_lzma2 *s)
573{
574 uint32_t prev_byte = dict_get(&s->dict, 0);
575 uint32_t low = prev_byte >> (8 - s->lzma.lc);
576 uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc;
577 return s->lzma.literal[low + high];
578}
579
580/* Decode a literal (one 8-bit byte) */
581static void lzma_literal(struct xz_dec_lzma2 *s)
582{
583 uint16_t *probs;
584 uint32_t symbol;
585 uint32_t match_byte;
586 uint32_t match_bit;
587 uint32_t offset;
588 uint32_t i;
589
590 probs = lzma_literal_probs(s);
591
592 if (lzma_state_is_literal(s->lzma.state)) {
593 symbol = rc_bittree(&s->rc, probs, 0x100);
594 } else {
595 symbol = 1;
596 match_byte = dict_get(&s->dict, s->lzma.rep0) << 1;
597 offset = 0x100;
598
599 do {
600 match_bit = match_byte & offset;
601 match_byte <<= 1;
602 i = offset + match_bit + symbol;
603
604 if (rc_bit(&s->rc, &probs[i])) {
605 symbol = (symbol << 1) + 1;
606 offset &= match_bit;
607 } else {
608 symbol <<= 1;
609 offset &= ~match_bit;
610 }
611 } while (symbol < 0x100);
612 }
613
614 dict_put(&s->dict, (uint8_t)symbol);
615 lzma_state_literal(&s->lzma.state);
616}
617
618/* Decode the length of the match into s->lzma.len. */
619static void lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l,
620 uint32_t pos_state)
621{
622 uint16_t *probs;
623 uint32_t limit;
624
625 if (!rc_bit(&s->rc, &l->choice)) {
626 probs = l->low[pos_state];
627 limit = LEN_LOW_SYMBOLS;
628 s->lzma.len = MATCH_LEN_MIN;
629 } else {
630 if (!rc_bit(&s->rc, &l->choice2)) {
631 probs = l->mid[pos_state];
632 limit = LEN_MID_SYMBOLS;
633 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS;
634 } else {
635 probs = l->high;
636 limit = LEN_HIGH_SYMBOLS;
637 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS
638 + LEN_MID_SYMBOLS;
639 }
640 }
641
642 s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit;
643}
644
645/* Decode a match. The distance will be stored in s->lzma.rep0. */
646static void lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
647{
648 uint16_t *probs;
649 uint32_t dist_slot;
650 uint32_t limit;
651
652 lzma_state_match(&s->lzma.state);
653
654 s->lzma.rep3 = s->lzma.rep2;
655 s->lzma.rep2 = s->lzma.rep1;
656 s->lzma.rep1 = s->lzma.rep0;
657
658 lzma_len(s, &s->lzma.match_len_dec, pos_state);
659
660 probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)];
661 dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS;
662
663 if (dist_slot < DIST_MODEL_START) {
664 s->lzma.rep0 = dist_slot;
665 } else {
666 limit = (dist_slot >> 1) - 1;
667 s->lzma.rep0 = 2 + (dist_slot & 1);
668
669 if (dist_slot < DIST_MODEL_END) {
670 s->lzma.rep0 <<= limit;
671 probs = s->lzma.dist_special + s->lzma.rep0
672 - dist_slot - 1;
673 rc_bittree_reverse(&s->rc, probs,
674 &s->lzma.rep0, limit);
675 } else {
676 rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS);
677 s->lzma.rep0 <<= ALIGN_BITS;
678 rc_bittree_reverse(&s->rc, s->lzma.dist_align,
679 &s->lzma.rep0, ALIGN_BITS);
680 }
681 }
682}
683
684/*
685 * Decode a repeated match. The distance is one of the four most recently
686 * seen matches. The distance will be stored in s->lzma.rep0.
687 */
688static void lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
689{
690 uint32_t tmp;
691
692 if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) {
693 if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[
694 s->lzma.state][pos_state])) {
695 lzma_state_short_rep(&s->lzma.state);
696 s->lzma.len = 1;
697 return;
698 }
699 } else {
700 if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) {
701 tmp = s->lzma.rep1;
702 } else {
703 if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) {
704 tmp = s->lzma.rep2;
705 } else {
706 tmp = s->lzma.rep3;
707 s->lzma.rep3 = s->lzma.rep2;
708 }
709
710 s->lzma.rep2 = s->lzma.rep1;
711 }
712
713 s->lzma.rep1 = s->lzma.rep0;
714 s->lzma.rep0 = tmp;
715 }
716
717 lzma_state_long_rep(&s->lzma.state);
718 lzma_len(s, &s->lzma.rep_len_dec, pos_state);
719}
720
721/* LZMA decoder core */
722static bool lzma_main(struct xz_dec_lzma2 *s)
723{
724 uint32_t pos_state;
725
726 /*
727 * If the dictionary was reached during the previous call, try to
728 * finish the possibly pending repeat in the dictionary.
729 */
730 if (dict_has_space(&s->dict) && s->lzma.len > 0)
731 dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0);
732
733 /*
734 * Decode more LZMA symbols. One iteration may consume up to
735 * LZMA_IN_REQUIRED - 1 bytes.
736 */
737 while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) {
738 pos_state = s->dict.pos & s->lzma.pos_mask;
739
740 if (!rc_bit(&s->rc, &s->lzma.is_match[
741 s->lzma.state][pos_state])) {
742 lzma_literal(s);
743 } else {
744 if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state]))
745 lzma_rep_match(s, pos_state);
746 else
747 lzma_match(s, pos_state);
748
749 if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0))
750 return false;
751 }
752 }
753
754 /*
755 * Having the range decoder always normalized when we are outside
756 * this function makes it easier to correctly handle end of the chunk.
757 */
758 rc_normalize(&s->rc);
759
760 return true;
761}
762
763/*
764 * Reset the LZMA decoder and range decoder state. Dictionary is nore reset
765 * here, because LZMA state may be reset without resetting the dictionary.
766 */
767static void lzma_reset(struct xz_dec_lzma2 *s)
768{
769 uint16_t *probs;
770 size_t i;
771
772 s->lzma.state = STATE_LIT_LIT;
773 s->lzma.rep0 = 0;
774 s->lzma.rep1 = 0;
775 s->lzma.rep2 = 0;
776 s->lzma.rep3 = 0;
777
778 /*
779 * All probabilities are initialized to the same value. This hack
780 * makes the code smaller by avoiding a separate loop for each
781 * probability array.
782 *
783 * This could be optimized so that only that part of literal
784 * probabilities that are actually required. In the common case
785 * we would write 12 KiB less.
786 */
787 probs = s->lzma.is_match[0];
788 for (i = 0; i < PROBS_TOTAL; ++i)
789 probs[i] = RC_BIT_MODEL_TOTAL / 2;
790
791 rc_reset(&s->rc);
792}
793
794/*
795 * Decode and validate LZMA properties (lc/lp/pb) and calculate the bit masks
796 * from the decoded lp and pb values. On success, the LZMA decoder state is
797 * reset and true is returned.
798 */
799static bool lzma_props(struct xz_dec_lzma2 *s, uint8_t props)
800{
801 if (props > (4 * 5 + 4) * 9 + 8)
802 return false;
803
804 s->lzma.pos_mask = 0;
805 while (props >= 9 * 5) {
806 props -= 9 * 5;
807 ++s->lzma.pos_mask;
808 }
809
810 s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1;
811
812 s->lzma.literal_pos_mask = 0;
813 while (props >= 9) {
814 props -= 9;
815 ++s->lzma.literal_pos_mask;
816 }
817
818 s->lzma.lc = props;
819
820 if (s->lzma.lc + s->lzma.literal_pos_mask > 4)
821 return false;
822
823 s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1;
824
825 lzma_reset(s);
826
827 return true;
828}
829
830/*********
831 * LZMA2 *
832 *********/
833
834/*
835 * The LZMA decoder assumes that if the input limit (s->rc.in_limit) hasn't
836 * been exceeded, it is safe to read up to LZMA_IN_REQUIRED bytes. This
837 * wrapper function takes care of making the LZMA decoder's assumption safe.
838 *
839 * As long as there is plenty of input left to be decoded in the current LZMA
840 * chunk, we decode directly from the caller-supplied input buffer until
841 * there's LZMA_IN_REQUIRED bytes left. Those remaining bytes are copied into
842 * s->temp.buf, which (hopefully) gets filled on the next call to this
843 * function. We decode a few bytes from the temporary buffer so that we can
844 * continue decoding from the caller-supplied input buffer again.
845 */
846static bool lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b)
847{
848 size_t in_avail;
849 uint32_t tmp;
850
851 in_avail = b->in_size - b->in_pos;
852 if (s->temp.size > 0 || s->lzma2.compressed == 0) {
853 tmp = 2 * LZMA_IN_REQUIRED - s->temp.size;
854 if (tmp > s->lzma2.compressed - s->temp.size)
855 tmp = s->lzma2.compressed - s->temp.size;
856 if (tmp > in_avail)
857 tmp = in_avail;
858
859 memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp);
860
861 if (s->temp.size + tmp == s->lzma2.compressed) {
862 memzero(s->temp.buf + s->temp.size + tmp,
863 sizeof(s->temp.buf)
864 - s->temp.size - tmp);
865 s->rc.in_limit = s->temp.size + tmp;
866 } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) {
867 s->temp.size += tmp;
868 b->in_pos += tmp;
869 return true;
870 } else {
871 s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED;
872 }
873
874 s->rc.in = s->temp.buf;
875 s->rc.in_pos = 0;
876
877 if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp)
878 return false;
879
880 s->lzma2.compressed -= s->rc.in_pos;
881
882 if (s->rc.in_pos < s->temp.size) {
883 s->temp.size -= s->rc.in_pos;
884 memmove(s->temp.buf, s->temp.buf + s->rc.in_pos,
885 s->temp.size);
886 return true;
887 }
888
889 b->in_pos += s->rc.in_pos - s->temp.size;
890 s->temp.size = 0;
891 }
892
893 in_avail = b->in_size - b->in_pos;
894 if (in_avail >= LZMA_IN_REQUIRED) {
895 s->rc.in = b->in;
896 s->rc.in_pos = b->in_pos;
897
898 if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED)
899 s->rc.in_limit = b->in_pos + s->lzma2.compressed;
900 else
901 s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED;
902
903 if (!lzma_main(s))
904 return false;
905
906 in_avail = s->rc.in_pos - b->in_pos;
907 if (in_avail > s->lzma2.compressed)
908 return false;
909
910 s->lzma2.compressed -= in_avail;
911 b->in_pos = s->rc.in_pos;
912 }
913
914 in_avail = b->in_size - b->in_pos;
915 if (in_avail < LZMA_IN_REQUIRED) {
916 if (in_avail > s->lzma2.compressed)
917 in_avail = s->lzma2.compressed;
918
919 memcpy(s->temp.buf, b->in + b->in_pos, in_avail);
920 s->temp.size = in_avail;
921 b->in_pos += in_avail;
922 }
923
924 return true;
925}
926
927/*
928 * Take care of the LZMA2 control layer, and forward the job of actual LZMA
929 * decoding or copying of uncompressed chunks to other functions.
930 */
931XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
932 struct xz_buf *b)
933{
934 uint32_t tmp;
935
936 while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) {
937 switch (s->lzma2.sequence) {
938 case SEQ_CONTROL:
939 /*
940 * LZMA2 control byte
941 *
942 * Exact values:
943 * 0x00 End marker
944 * 0x01 Dictionary reset followed by
945 * an uncompressed chunk
946 * 0x02 Uncompressed chunk (no dictionary reset)
947 *
948 * Highest three bits (s->control & 0xE0):
949 * 0xE0 Dictionary reset, new properties and state
950 * reset, followed by LZMA compressed chunk
951 * 0xC0 New properties and state reset, followed
952 * by LZMA compressed chunk (no dictionary
953 * reset)
954 * 0xA0 State reset using old properties,
955 * followed by LZMA compressed chunk (no
956 * dictionary reset)
957 * 0x80 LZMA chunk (no dictionary or state reset)
958 *
959 * For LZMA compressed chunks, the lowest five bits
960 * (s->control & 1F) are the highest bits of the
961 * uncompressed size (bits 16-20).
962 *
963 * A new LZMA2 stream must begin with a dictionary
964 * reset. The first LZMA chunk must set new
965 * properties and reset the LZMA state.
966 *
967 * Values that don't match anything described above
968 * are invalid and we return XZ_DATA_ERROR.
969 */
970 tmp = b->in[b->in_pos++];
971
972 if (tmp >= 0xE0 || tmp == 0x01) {
973 s->lzma2.need_props = true;
974 s->lzma2.need_dict_reset = false;
975 dict_reset(&s->dict, b);
976 } else if (s->lzma2.need_dict_reset) {
977 return XZ_DATA_ERROR;
978 }
979
980 if (tmp >= 0x80) {
981 s->lzma2.uncompressed = (tmp & 0x1F) << 16;
982 s->lzma2.sequence = SEQ_UNCOMPRESSED_1;
983
984 if (tmp >= 0xC0) {
985 /*
986 * When there are new properties,
987 * state reset is done at
988 * SEQ_PROPERTIES.
989 */
990 s->lzma2.need_props = false;
991 s->lzma2.next_sequence
992 = SEQ_PROPERTIES;
993
994 } else if (s->lzma2.need_props) {
995 return XZ_DATA_ERROR;
996
997 } else {
998 s->lzma2.next_sequence
999 = SEQ_LZMA_PREPARE;
1000 if (tmp >= 0xA0)
1001 lzma_reset(s);
1002 }
1003 } else {
1004 if (tmp == 0x00)
1005 return XZ_STREAM_END;
1006
1007 if (tmp > 0x02)
1008 return XZ_DATA_ERROR;
1009
1010 s->lzma2.sequence = SEQ_COMPRESSED_0;
1011 s->lzma2.next_sequence = SEQ_COPY;
1012 }
1013
1014 break;
1015
1016 case SEQ_UNCOMPRESSED_1:
1017 s->lzma2.uncompressed
1018 += (uint32_t)b->in[b->in_pos++] << 8;
1019 s->lzma2.sequence = SEQ_UNCOMPRESSED_2;
1020 break;
1021
1022 case SEQ_UNCOMPRESSED_2:
1023 s->lzma2.uncompressed
1024 += (uint32_t)b->in[b->in_pos++] + 1;
1025 s->lzma2.sequence = SEQ_COMPRESSED_0;
1026 break;
1027
1028 case SEQ_COMPRESSED_0:
1029 s->lzma2.compressed
1030 = (uint32_t)b->in[b->in_pos++] << 8;
1031 s->lzma2.sequence = SEQ_COMPRESSED_1;
1032 break;
1033
1034 case SEQ_COMPRESSED_1:
1035 s->lzma2.compressed
1036 += (uint32_t)b->in[b->in_pos++] + 1;
1037 s->lzma2.sequence = s->lzma2.next_sequence;
1038 break;
1039
1040 case SEQ_PROPERTIES:
1041 if (!lzma_props(s, b->in[b->in_pos++]))
1042 return XZ_DATA_ERROR;
1043
1044 s->lzma2.sequence = SEQ_LZMA_PREPARE;
1045
1046 case SEQ_LZMA_PREPARE:
1047 if (s->lzma2.compressed < RC_INIT_BYTES)
1048 return XZ_DATA_ERROR;
1049
1050 if (!rc_read_init(&s->rc, b))
1051 return XZ_OK;
1052
1053 s->lzma2.compressed -= RC_INIT_BYTES;
1054 s->lzma2.sequence = SEQ_LZMA_RUN;
1055
1056 case SEQ_LZMA_RUN:
1057 /*
1058 * Set dictionary limit to indicate how much we want
1059 * to be encoded at maximum. Decode new data into the
1060 * dictionary. Flush the new data from dictionary to
1061 * b->out. Check if we finished decoding this chunk.
1062 * In case the dictionary got full but we didn't fill
1063 * the output buffer yet, we may run this loop
1064 * multiple times without changing s->lzma2.sequence.
1065 */
1066 dict_limit(&s->dict, min_t(size_t,
1067 b->out_size - b->out_pos,
1068 s->lzma2.uncompressed));
1069 if (!lzma2_lzma(s, b))
1070 return XZ_DATA_ERROR;
1071
1072 s->lzma2.uncompressed -= dict_flush(&s->dict, b);
1073
1074 if (s->lzma2.uncompressed == 0) {
1075 if (s->lzma2.compressed > 0 || s->lzma.len > 0
1076 || !rc_is_finished(&s->rc))
1077 return XZ_DATA_ERROR;
1078
1079 rc_reset(&s->rc);
1080 s->lzma2.sequence = SEQ_CONTROL;
1081
1082 } else if (b->out_pos == b->out_size
1083 || (b->in_pos == b->in_size
1084 && s->temp.size
1085 < s->lzma2.compressed)) {
1086 return XZ_OK;
1087 }
1088
1089 break;
1090
1091 case SEQ_COPY:
1092 dict_uncompressed(&s->dict, b, &s->lzma2.compressed);
1093 if (s->lzma2.compressed > 0)
1094 return XZ_OK;
1095
1096 s->lzma2.sequence = SEQ_CONTROL;
1097 break;
1098 }
1099 }
1100
1101 return XZ_OK;
1102}
1103
1104XZ_EXTERN struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode,
1105 uint32_t dict_max)
1106{
1107 struct xz_dec_lzma2 *s = kmalloc(sizeof(*s), GFP_KERNEL);
1108 if (s == NULL)
1109 return NULL;
1110
1111 s->dict.mode = mode;
1112 s->dict.size_max = dict_max;
1113
1114 if (DEC_IS_PREALLOC(mode)) {
1115 s->dict.buf = vmalloc(dict_max);
1116 if (s->dict.buf == NULL) {
1117 kfree(s);
1118 return NULL;
1119 }
1120 } else if (DEC_IS_DYNALLOC(mode)) {
1121 s->dict.buf = NULL;
1122 s->dict.allocated = 0;
1123 }
1124
1125 return s;
1126}
1127
1128XZ_EXTERN enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props)
1129{
1130 /* This limits dictionary size to 3 GiB to keep parsing simpler. */
1131 if (props > 39)
1132 return XZ_OPTIONS_ERROR;
1133
1134 s->dict.size = 2 + (props & 1);
1135 s->dict.size <<= (props >> 1) + 11;
1136
1137 if (DEC_IS_MULTI(s->dict.mode)) {
1138 if (s->dict.size > s->dict.size_max)
1139 return XZ_MEMLIMIT_ERROR;
1140
1141 s->dict.end = s->dict.size;
1142
1143 if (DEC_IS_DYNALLOC(s->dict.mode)) {
1144 if (s->dict.allocated < s->dict.size) {
1145 vfree(s->dict.buf);
1146 s->dict.buf = vmalloc(s->dict.size);
1147 if (s->dict.buf == NULL) {
1148 s->dict.allocated = 0;
1149 return XZ_MEM_ERROR;
1150 }
1151 }
1152 }
1153 }
1154
1155 s->lzma.len = 0;
1156
1157 s->lzma2.sequence = SEQ_CONTROL;
1158 s->lzma2.need_dict_reset = true;
1159
1160 s->temp.size = 0;
1161
1162 return XZ_OK;
1163}
1164
1165XZ_EXTERN void xz_dec_lzma2_end(struct xz_dec_lzma2 *s)
1166{
1167 if (DEC_IS_MULTI(s->dict.mode))
1168 vfree(s->dict.buf);
1169
1170 kfree(s);
1171}
diff --git a/lib/xz/xz_dec_stream.c b/lib/xz/xz_dec_stream.c
new file mode 100644
index 000000000000..ac809b1e64f7
--- /dev/null
+++ b/lib/xz/xz_dec_stream.c
@@ -0,0 +1,821 @@
1/*
2 * .xz Stream decoder
3 *
4 * Author: Lasse Collin <lasse.collin@tukaani.org>
5 *
6 * This file has been put into the public domain.
7 * You can do whatever you want with this file.
8 */
9
10#include "xz_private.h"
11#include "xz_stream.h"
12
13/* Hash used to validate the Index field */
14struct xz_dec_hash {
15 vli_type unpadded;
16 vli_type uncompressed;
17 uint32_t crc32;
18};
19
20struct xz_dec {
21 /* Position in dec_main() */
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 /* Position in variable-length integers and Check fields */
36 uint32_t pos;
37
38 /* Variable-length integer decoded by dec_vli() */
39 vli_type vli;
40
41 /* Saved in_pos and out_pos */
42 size_t in_start;
43 size_t out_start;
44
45 /* CRC32 value in Block or Index */
46 uint32_t crc32;
47
48 /* Type of the integrity check calculated from uncompressed data */
49 enum xz_check check_type;
50
51 /* Operation mode */
52 enum xz_mode mode;
53
54 /*
55 * True if the next call to xz_dec_run() is allowed to return
56 * XZ_BUF_ERROR.
57 */
58 bool allow_buf_error;
59
60 /* Information stored in Block Header */
61 struct {
62 /*
63 * Value stored in the Compressed Size field, or
64 * VLI_UNKNOWN if Compressed Size is not present.
65 */
66 vli_type compressed;
67
68 /*
69 * Value stored in the Uncompressed Size field, or
70 * VLI_UNKNOWN if Uncompressed Size is not present.
71 */
72 vli_type uncompressed;
73
74 /* Size of the Block Header field */
75 uint32_t size;
76 } block_header;
77
78 /* Information collected when decoding Blocks */
79 struct {
80 /* Observed compressed size of the current Block */
81 vli_type compressed;
82
83 /* Observed uncompressed size of the current Block */
84 vli_type uncompressed;
85
86 /* Number of Blocks decoded so far */
87 vli_type count;
88
89 /*
90 * Hash calculated from the Block sizes. This is used to
91 * validate the Index field.
92 */
93 struct xz_dec_hash hash;
94 } block;
95
96 /* Variables needed when verifying the Index field */
97 struct {
98 /* Position in dec_index() */
99 enum {
100 SEQ_INDEX_COUNT,
101 SEQ_INDEX_UNPADDED,
102 SEQ_INDEX_UNCOMPRESSED
103 } sequence;
104
105 /* Size of the Index in bytes */
106 vli_type size;
107
108 /* Number of Records (matches block.count in valid files) */
109 vli_type count;
110
111 /*
112 * Hash calculated from the Records (matches block.hash in
113 * valid files).
114 */
115 struct xz_dec_hash hash;
116 } index;
117
118 /*
119 * Temporary buffer needed to hold Stream Header, Block Header,
120 * and Stream Footer. The Block Header is the biggest (1 KiB)
121 * so we reserve space according to that. buf[] has to be aligned
122 * to a multiple of four bytes; the size_t variables before it
123 * should guarantee this.
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/* Sizes of the Check field with different Check IDs */
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 * Fill s->temp by copying data starting from b->in[b->in_pos]. Caller
153 * must have set s->temp.pos to indicate how much data we are supposed
154 * to copy into s->temp.buf. Return true once s->temp.pos has reached
155 * s->temp.size.
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/* Decode a variable-length integer (little-endian base-128 encoding) */
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 /* Don't allow non-minimal encodings. */
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 * Decode the Compressed Data field from a Block. Update and validate
208 * the observed compressed and uncompressed sizes of the Block so that
209 * they don't exceed the values possibly stored in the Block Header
210 * (validation assumes that no integer overflow occurs, since vli_type
211 * is normally uint64_t). Update the CRC32 if presence of the CRC32
212 * field was indicated in Stream Header.
213 *
214 * Once the decoding is finished, validate that the observed sizes match
215 * the sizes possibly stored in the Block Header. Update the hash and
216 * Block count, which are later used to validate the Index field.
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 * There is no need to separately check for VLI_UNKNOWN, since
237 * the observed sizes are always smaller than VLI_UNKNOWN.
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/* Update the Index size and the CRC32 value. */
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 * Decode the Number of Records, Unpadded Size, and Uncompressed Size
290 * fields from the Index field. That is, Index Padding and CRC32 are not
291 * decoded by this function.
292 *
293 * This can return XZ_OK (more input needed), XZ_STREAM_END (everything
294 * successfully decoded), or XZ_DATA_ERROR (input is corrupt).
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 * Validate that the Number of Records field
313 * indicates the same number of Records as
314 * there were Blocks in the Stream.
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 * Validate that the next four input bytes match the value of s->crc32.
344 * s->pos must be zero when starting to validate the first byte.
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 * Skip over the Check field when the Check ID is not supported.
368 * Returns true once the whole Check field has been skipped over.
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/* Decode the Stream Header field (the first 12 bytes of the .xz Stream). */
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 * Of integrity checks, we support only none (Check ID = 0) and
401 * CRC32 (Check ID = 1). However, if XZ_DEC_ANY_CHECK is defined,
402 * we will accept other check types too, but then the check won't
403 * be verified and a warning (XZ_UNSUPPORTED_CHECK) will be given.
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/* Decode the Stream Footer field (the last 12 bytes of the .xz Stream) */
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 * Validate Backward Size. Note that we never added the size of the
432 * Index CRC32 field to s->index.size, thus we use s->index.size / 4
433 * instead of s->index.size / 4 - 1.
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 * Use XZ_STREAM_END instead of XZ_OK to be more convenient
443 * for the caller.
444 */
445 return XZ_STREAM_END;
446}
447
448/* Decode the Block Header and initialize the filter chain. */
449static enum xz_ret dec_block_header(struct xz_dec *s)
450{
451 enum xz_ret ret;
452
453 /*
454 * Validate the CRC32. We know that the temp buffer is at least
455 * eight bytes so this is safe.
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 * Catch unsupported Block Flags. We support only one or two filters
466 * in the chain, so we catch that with the same test.
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 /* Compressed Size */
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 /* Uncompressed Size */
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 /* If there are two filters, the first one must be a BCJ filter. */
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 * We don't support custom start offset,
510 * so Size of Properties must be zero.
511 */
512 if (s->temp.buf[s->temp.pos++] != 0x00)
513 return XZ_OPTIONS_ERROR;
514 }
515#endif
516
517 /* Valid Filter Flags always take at least two bytes. */
518 if (s->temp.size - s->temp.pos < 2)
519 return XZ_DATA_ERROR;
520
521 /* Filter ID = LZMA2 */
522 if (s->temp.buf[s->temp.pos++] != 0x21)
523 return XZ_OPTIONS_ERROR;
524
525 /* Size of Properties = 1-byte Filter Properties */
526 if (s->temp.buf[s->temp.pos++] != 0x01)
527 return XZ_OPTIONS_ERROR;
528
529 /* Filter Properties contains LZMA2 dictionary size. */
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 /* The rest must be Header Padding. */
538 while (s->temp.pos < s->temp.size)
539 if (s->temp.buf[s->temp.pos++] != 0x00)
540 return XZ_OPTIONS_ERROR;
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 * Store the start position for the case when we are in the middle
555 * of the Index field.
556 */
557 s->in_start = b->in_pos;
558
559 while (true) {
560 switch (s->sequence) {
561 case SEQ_STREAM_HEADER:
562 /*
563 * Stream Header is copied to s->temp, and then
564 * decoded from there. This way if the caller
565 * gives us only little input at a time, we can
566 * still keep the Stream Header decoding code
567 * simple. Similar approach is used in many places
568 * in this file.
569 */
570 if (!fill_temp(s, b))
571 return XZ_OK;
572
573 /*
574 * If dec_stream_header() returns
575 * XZ_UNSUPPORTED_CHECK, it is still possible
576 * to continue decoding if working in multi-call
577 * mode. Thus, update s->sequence before calling
578 * dec_stream_header().
579 */
580 s->sequence = SEQ_BLOCK_START;
581
582 ret = dec_stream_header(s);
583 if (ret != XZ_OK)
584 return ret;
585
586 case SEQ_BLOCK_START:
587 /* We need one byte of input to continue. */
588 if (b->in_pos == b->in_size)
589 return XZ_OK;
590
591 /* See if this is the beginning of the Index field. */
592 if (b->in[b->in_pos] == 0) {
593 s->in_start = b->in_pos++;
594 s->sequence = SEQ_INDEX;
595 break;
596 }
597
598 /*
599 * Calculate the size of the Block Header and
600 * prepare to decode it.
601 */
602 s->block_header.size
603 = ((uint32_t)b->in[b->in_pos] + 1) * 4;
604
605 s->temp.size = s->block_header.size;
606 s->temp.pos = 0;
607 s->sequence = SEQ_BLOCK_HEADER;
608
609 case SEQ_BLOCK_HEADER:
610 if (!fill_temp(s, b))
611 return XZ_OK;
612
613 ret = dec_block_header(s);
614 if (ret != XZ_OK)
615 return ret;
616
617 s->sequence = SEQ_BLOCK_UNCOMPRESS;
618
619 case SEQ_BLOCK_UNCOMPRESS:
620 ret = dec_block(s, b);
621 if (ret != XZ_STREAM_END)
622 return ret;
623
624 s->sequence = SEQ_BLOCK_PADDING;
625
626 case SEQ_BLOCK_PADDING:
627 /*
628 * Size of Compressed Data + Block Padding
629 * must be a multiple of four. We don't need
630 * s->block.compressed for anything else
631 * anymore, so we use it here to test the size
632 * of the Block Padding field.
633 */
634 while (s->block.compressed & 3) {
635 if (b->in_pos == b->in_size)
636 return XZ_OK;
637
638 if (b->in[b->in_pos++] != 0)
639 return XZ_DATA_ERROR;
640
641 ++s->block.compressed;
642 }
643
644 s->sequence = SEQ_BLOCK_CHECK;
645
646 case SEQ_BLOCK_CHECK:
647 if (s->check_type == XZ_CHECK_CRC32) {
648 ret = crc32_validate(s, b);
649 if (ret != XZ_STREAM_END)
650 return ret;
651 }
652#ifdef XZ_DEC_ANY_CHECK
653 else if (!check_skip(s, b)) {
654 return XZ_OK;
655 }
656#endif
657
658 s->sequence = SEQ_BLOCK_START;
659 break;
660
661 case SEQ_INDEX:
662 ret = dec_index(s, b);
663 if (ret != XZ_STREAM_END)
664 return ret;
665
666 s->sequence = SEQ_INDEX_PADDING;
667
668 case SEQ_INDEX_PADDING:
669 while ((s->index.size + (b->in_pos - s->in_start))
670 & 3) {
671 if (b->in_pos == b->in_size) {
672 index_update(s, b);
673 return XZ_OK;
674 }
675
676 if (b->in[b->in_pos++] != 0)
677 return XZ_DATA_ERROR;
678 }
679
680 /* Finish the CRC32 value and Index size. */
681 index_update(s, b);
682
683 /* Compare the hashes to validate the Index field. */
684 if (!memeq(&s->block.hash, &s->index.hash,
685 sizeof(s->block.hash)))
686 return XZ_DATA_ERROR;
687
688 s->sequence = SEQ_INDEX_CRC32;
689
690 case SEQ_INDEX_CRC32:
691 ret = crc32_validate(s, b);
692 if (ret != XZ_STREAM_END)
693 return ret;
694
695 s->temp.size = STREAM_HEADER_SIZE;
696 s->sequence = SEQ_STREAM_FOOTER;
697
698 case SEQ_STREAM_FOOTER:
699 if (!fill_temp(s, b))
700 return XZ_OK;
701
702 return dec_stream_footer(s);
703 }
704 }
705
706 /* Never reached */
707}
708
709/*
710 * xz_dec_run() is a wrapper for dec_main() to handle some special cases in
711 * multi-call and single-call decoding.
712 *
713 * In multi-call mode, we must return XZ_BUF_ERROR when it seems clear that we
714 * are not going to make any progress anymore. This is to prevent the caller
715 * from calling us infinitely when the input file is truncated or otherwise
716 * corrupt. Since zlib-style API allows that the caller fills the input buffer
717 * only when the decoder doesn't produce any new output, we have to be careful
718 * to avoid returning XZ_BUF_ERROR too easily: XZ_BUF_ERROR is returned only
719 * after the second consecutive call to xz_dec_run() that makes no progress.
720 *
721 * In single-call mode, if we couldn't decode everything and no error
722 * occurred, either the input is truncated or the output buffer is too small.
723 * Since we know that the last input byte never produces any output, we know
724 * that if all the input was consumed and decoding wasn't finished, the file
725 * must be corrupt. Otherwise the output buffer has to be too small or the
726 * file is corrupt in a way that decoding it produces too big output.
727 *
728 * If single-call decoding fails, we reset b->in_pos and b->out_pos back to
729 * their original values. This is because with some filter chains there won't
730 * be any valid uncompressed data in the output buffer unless the decoding
731 * actually succeeds (that's the price to pay of using the output buffer as
732 * the workspace).
733 */
734XZ_EXTERN enum xz_ret xz_dec_run(struct xz_dec *s, struct xz_buf *b)
735{
736 size_t in_start;
737 size_t out_start;
738 enum xz_ret ret;
739
740 if (DEC_IS_SINGLE(s->mode))
741 xz_dec_reset(s);
742
743 in_start = b->in_pos;
744 out_start = b->out_pos;
745 ret = dec_main(s, b);
746
747 if (DEC_IS_SINGLE(s->mode)) {
748 if (ret == XZ_OK)
749 ret = b->in_pos == b->in_size
750 ? XZ_DATA_ERROR : XZ_BUF_ERROR;
751
752 if (ret != XZ_STREAM_END) {
753 b->in_pos = in_start;
754 b->out_pos = out_start;
755 }
756
757 } else if (ret == XZ_OK && in_start == b->in_pos
758 && out_start == b->out_pos) {
759 if (s->allow_buf_error)
760 ret = XZ_BUF_ERROR;
761
762 s->allow_buf_error = true;
763 } else {
764 s->allow_buf_error = false;
765 }
766
767 return ret;
768}
769
770XZ_EXTERN struct xz_dec *xz_dec_init(enum xz_mode mode, uint32_t dict_max)
771{
772 struct xz_dec *s = kmalloc(sizeof(*s), GFP_KERNEL);
773 if (s == NULL)
774 return NULL;
775
776 s->mode = mode;
777
778#ifdef XZ_DEC_BCJ
779 s->bcj = xz_dec_bcj_create(DEC_IS_SINGLE(mode));
780 if (s->bcj == NULL)
781 goto error_bcj;
782#endif
783
784 s->lzma2 = xz_dec_lzma2_create(mode, dict_max);
785 if (s->lzma2 == NULL)
786 goto error_lzma2;
787
788 xz_dec_reset(s);
789 return s;
790
791error_lzma2:
792#ifdef XZ_DEC_BCJ
793 xz_dec_bcj_end(s->bcj);
794error_bcj:
795#endif
796 kfree(s);
797 return NULL;
798}
799
800XZ_EXTERN void xz_dec_reset(struct xz_dec *s)
801{
802 s->sequence = SEQ_STREAM_HEADER;
803 s->allow_buf_error = false;
804 s->pos = 0;
805 s->crc32 = 0;
806 memzero(&s->block, sizeof(s->block));
807 memzero(&s->index, sizeof(s->index));
808 s->temp.pos = 0;
809 s->temp.size = STREAM_HEADER_SIZE;
810}
811
812XZ_EXTERN void xz_dec_end(struct xz_dec *s)
813{
814 if (s != NULL) {
815 xz_dec_lzma2_end(s->lzma2);
816#ifdef XZ_DEC_BCJ
817 xz_dec_bcj_end(s->bcj);
818#endif
819 kfree(s);
820 }
821}
diff --git a/lib/xz/xz_dec_syms.c b/lib/xz/xz_dec_syms.c
new file mode 100644
index 000000000000..32eb3c03aede
--- /dev/null
+++ b/lib/xz/xz_dec_syms.c
@@ -0,0 +1,26 @@
1/*
2 * XZ decoder module information
3 *
4 * Author: Lasse Collin <lasse.collin@tukaani.org>
5 *
6 * This file has been put into the public domain.
7 * You can do whatever you want with this file.
8 */
9
10#include <linux/module.h>
11#include <linux/xz.h>
12
13EXPORT_SYMBOL(xz_dec_init);
14EXPORT_SYMBOL(xz_dec_reset);
15EXPORT_SYMBOL(xz_dec_run);
16EXPORT_SYMBOL(xz_dec_end);
17
18MODULE_DESCRIPTION("XZ decompressor");
19MODULE_VERSION("1.0");
20MODULE_AUTHOR("Lasse Collin <lasse.collin@tukaani.org> and Igor Pavlov");
21
22/*
23 * This code is in the public domain, but in Linux it's simplest to just
24 * say it's GPL and consider the authors as the copyright holders.
25 */
26MODULE_LICENSE("GPL");
diff --git a/lib/xz/xz_dec_test.c b/lib/xz/xz_dec_test.c
new file mode 100644
index 000000000000..da28a19d6c98
--- /dev/null
+++ b/lib/xz/xz_dec_test.c
@@ -0,0 +1,220 @@
1/*
2 * XZ decoder tester
3 *
4 * Author: Lasse Collin <lasse.collin@tukaani.org>
5 *
6 * This file has been put into the public domain.
7 * You can do whatever you want with this file.
8 */
9
10#include <linux/kernel.h>
11#include <linux/module.h>
12#include <linux/fs.h>
13#include <linux/uaccess.h>
14#include <linux/crc32.h>
15#include <linux/xz.h>
16
17/* Maximum supported dictionary size */
18#define DICT_MAX (1 << 20)
19
20/* Device name to pass to register_chrdev(). */
21#define DEVICE_NAME "xz_dec_test"
22
23/* Dynamically allocated device major number */
24static int device_major;
25
26/*
27 * We reuse the same decoder state, and thus can decode only one
28 * file at a time.
29 */
30static bool device_is_open;
31
32/* XZ decoder state */
33static struct xz_dec *state;
34
35/*
36 * Return value of xz_dec_run(). We need to avoid calling xz_dec_run() after
37 * it has returned XZ_STREAM_END, so we make this static.
38 */
39static enum xz_ret ret;
40
41/*
42 * Input and output buffers. The input buffer is used as a temporary safe
43 * place for the data coming from the userspace.
44 */
45static uint8_t buffer_in[1024];
46static uint8_t buffer_out[1024];
47
48/*
49 * Structure to pass the input and output buffers to the XZ decoder.
50 * A few of the fields are never modified so we initialize them here.
51 */
52static struct xz_buf buffers = {
53 .in = buffer_in,
54 .out = buffer_out,
55 .out_size = sizeof(buffer_out)
56};
57
58/*
59 * CRC32 of uncompressed data. This is used to give the user a simple way
60 * to check that the decoder produces correct output.
61 */
62static uint32_t crc;
63
64static int xz_dec_test_open(struct inode *i, struct file *f)
65{
66 if (device_is_open)
67 return -EBUSY;
68
69 device_is_open = true;
70
71 xz_dec_reset(state);
72 ret = XZ_OK;
73 crc = 0xFFFFFFFF;
74
75 buffers.in_pos = 0;
76 buffers.in_size = 0;
77 buffers.out_pos = 0;
78
79 printk(KERN_INFO DEVICE_NAME ": opened\n");
80 return 0;
81}
82
83static int xz_dec_test_release(struct inode *i, struct file *f)
84{
85 device_is_open = false;
86
87 if (ret == XZ_OK)
88 printk(KERN_INFO DEVICE_NAME ": input was truncated\n");
89
90 printk(KERN_INFO DEVICE_NAME ": closed\n");
91 return 0;
92}
93
94/*
95 * Decode the data given to us from the userspace. CRC32 of the uncompressed
96 * data is calculated and is printed at the end of successful decoding. The
97 * uncompressed data isn't stored anywhere for further use.
98 *
99 * The .xz file must have exactly one Stream and no Stream Padding. The data
100 * after the first Stream is considered to be garbage.
101 */
102static ssize_t xz_dec_test_write(struct file *file, const char __user *buf,
103 size_t size, loff_t *pos)
104{
105 size_t remaining;
106
107 if (ret != XZ_OK) {
108 if (size > 0)
109 printk(KERN_INFO DEVICE_NAME ": %zu bytes of "
110 "garbage at the end of the file\n",
111 size);
112
113 return -ENOSPC;
114 }
115
116 printk(KERN_INFO DEVICE_NAME ": decoding %zu bytes of input\n",
117 size);
118
119 remaining = size;
120 while ((remaining > 0 || buffers.out_pos == buffers.out_size)
121 && ret == XZ_OK) {
122 if (buffers.in_pos == buffers.in_size) {
123 buffers.in_pos = 0;
124 buffers.in_size = min(remaining, sizeof(buffer_in));
125 if (copy_from_user(buffer_in, buf, buffers.in_size))
126 return -EFAULT;
127
128 buf += buffers.in_size;
129 remaining -= buffers.in_size;
130 }
131
132 buffers.out_pos = 0;
133 ret = xz_dec_run(state, &buffers);
134 crc = crc32(crc, buffer_out, buffers.out_pos);
135 }
136
137 switch (ret) {
138 case XZ_OK:
139 printk(KERN_INFO DEVICE_NAME ": XZ_OK\n");
140 return size;
141
142 case XZ_STREAM_END:
143 printk(KERN_INFO DEVICE_NAME ": XZ_STREAM_END, "
144 "CRC32 = 0x%08X\n", ~crc);
145 return size - remaining - (buffers.in_size - buffers.in_pos);
146
147 case XZ_MEMLIMIT_ERROR:
148 printk(KERN_INFO DEVICE_NAME ": XZ_MEMLIMIT_ERROR\n");
149 break;
150
151 case XZ_FORMAT_ERROR:
152 printk(KERN_INFO DEVICE_NAME ": XZ_FORMAT_ERROR\n");
153 break;
154
155 case XZ_OPTIONS_ERROR:
156 printk(KERN_INFO DEVICE_NAME ": XZ_OPTIONS_ERROR\n");
157 break;
158
159 case XZ_DATA_ERROR:
160 printk(KERN_INFO DEVICE_NAME ": XZ_DATA_ERROR\n");
161 break;
162
163 case XZ_BUF_ERROR:
164 printk(KERN_INFO DEVICE_NAME ": XZ_BUF_ERROR\n");
165 break;
166
167 default:
168 printk(KERN_INFO DEVICE_NAME ": Bug detected!\n");
169 break;
170 }
171
172 return -EIO;
173}
174
175/* Allocate the XZ decoder state and register the character device. */
176static int __init xz_dec_test_init(void)
177{
178 static const struct file_operations fileops = {
179 .owner = THIS_MODULE,
180 .open = &xz_dec_test_open,
181 .release = &xz_dec_test_release,
182 .write = &xz_dec_test_write
183 };
184
185 state = xz_dec_init(XZ_PREALLOC, DICT_MAX);
186 if (state == NULL)
187 return -ENOMEM;
188
189 device_major = register_chrdev(0, DEVICE_NAME, &fileops);
190 if (device_major < 0) {
191 xz_dec_end(state);
192 return device_major;
193 }
194
195 printk(KERN_INFO DEVICE_NAME ": module loaded\n");
196 printk(KERN_INFO DEVICE_NAME ": Create a device node with "
197 "'mknod " DEVICE_NAME " c %d 0' and write .xz files "
198 "to it.\n", device_major);
199 return 0;
200}
201
202static void __exit xz_dec_test_exit(void)
203{
204 unregister_chrdev(device_major, DEVICE_NAME);
205 xz_dec_end(state);
206 printk(KERN_INFO DEVICE_NAME ": module unloaded\n");
207}
208
209module_init(xz_dec_test_init);
210module_exit(xz_dec_test_exit);
211
212MODULE_DESCRIPTION("XZ decompressor tester");
213MODULE_VERSION("1.0");
214MODULE_AUTHOR("Lasse Collin <lasse.collin@tukaani.org>");
215
216/*
217 * This code is in the public domain, but in Linux it's simplest to just
218 * say it's GPL and consider the authors as the copyright holders.
219 */
220MODULE_LICENSE("GPL");
diff --git a/lib/xz/xz_lzma2.h b/lib/xz/xz_lzma2.h
new file mode 100644
index 000000000000..071d67bee9f5
--- /dev/null
+++ b/lib/xz/xz_lzma2.h
@@ -0,0 +1,204 @@
1/*
2 * LZMA2 definitions
3 *
4 * Authors: Lasse Collin <lasse.collin@tukaani.org>
5 * Igor Pavlov <http://7-zip.org/>
6 *
7 * This file has been put into the public domain.
8 * You can do whatever you want with this file.
9 */
10
11#ifndef XZ_LZMA2_H
12#define XZ_LZMA2_H
13
14/* Range coder constants */
15#define RC_SHIFT_BITS 8
16#define RC_TOP_BITS 24
17#define RC_TOP_VALUE (1 << RC_TOP_BITS)
18#define RC_BIT_MODEL_TOTAL_BITS 11
19#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
20#define RC_MOVE_BITS 5
21
22/*
23 * Maximum number of position states. A position state is the lowest pb
24 * number of bits of the current uncompressed offset. In some places there
25 * are different sets of probabilities for different position states.
26 */
27#define POS_STATES_MAX (1 << 4)
28
29/*
30 * This enum is used to track which LZMA symbols have occurred most recently
31 * and in which order. This information is used to predict the next symbol.
32 *
33 * Symbols:
34 * - Literal: One 8-bit byte
35 * - Match: Repeat a chunk of data at some distance
36 * - Long repeat: Multi-byte match at a recently seen distance
37 * - Short repeat: One-byte repeat at a recently seen distance
38 *
39 * The symbol names are in from STATE_oldest_older_previous. REP means
40 * either short or long repeated match, and NONLIT means any non-literal.
41 */
42enum lzma_state {
43 STATE_LIT_LIT,
44 STATE_MATCH_LIT_LIT,
45 STATE_REP_LIT_LIT,
46 STATE_SHORTREP_LIT_LIT,
47 STATE_MATCH_LIT,
48 STATE_REP_LIT,
49 STATE_SHORTREP_LIT,
50 STATE_LIT_MATCH,
51 STATE_LIT_LONGREP,
52 STATE_LIT_SHORTREP,
53 STATE_NONLIT_MATCH,
54 STATE_NONLIT_REP
55};
56
57/* Total number of states */
58#define STATES 12
59
60/* The lowest 7 states indicate that the previous state was a literal. */
61#define LIT_STATES 7
62
63/* Indicate that the latest symbol was a literal. */
64static inline void lzma_state_literal(enum lzma_state *state)
65{
66 if (*state <= STATE_SHORTREP_LIT_LIT)
67 *state = STATE_LIT_LIT;
68 else if (*state <= STATE_LIT_SHORTREP)
69 *state -= 3;
70 else
71 *state -= 6;
72}
73
74/* Indicate that the latest symbol was a match. */
75static inline void lzma_state_match(enum lzma_state *state)
76{
77 *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
78}
79
80/* Indicate that the latest state was a long repeated match. */
81static inline void lzma_state_long_rep(enum lzma_state *state)
82{
83 *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
84}
85
86/* Indicate that the latest symbol was a short match. */
87static inline void lzma_state_short_rep(enum lzma_state *state)
88{
89 *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
90}
91
92/* Test if the previous symbol was a literal. */
93static inline bool lzma_state_is_literal(enum lzma_state state)
94{
95 return state < LIT_STATES;
96}
97
98/* Each literal coder is divided in three sections:
99 * - 0x001-0x0FF: Without match byte
100 * - 0x101-0x1FF: With match byte; match bit is 0
101 * - 0x201-0x2FF: With match byte; match bit is 1
102 *
103 * Match byte is used when the previous LZMA symbol was something else than
104 * a literal (that is, it was some kind of match).
105 */
106#define LITERAL_CODER_SIZE 0x300
107
108/* Maximum number of literal coders */
109#define LITERAL_CODERS_MAX (1 << 4)
110
111/* Minimum length of a match is two bytes. */
112#define MATCH_LEN_MIN 2
113
114/* Match length is encoded with 4, 5, or 10 bits.
115 *
116 * Length Bits
117 * 2-9 4 = Choice=0 + 3 bits
118 * 10-17 5 = Choice=1 + Choice2=0 + 3 bits
119 * 18-273 10 = Choice=1 + Choice2=1 + 8 bits
120 */
121#define LEN_LOW_BITS 3
122#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
123#define LEN_MID_BITS 3
124#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
125#define LEN_HIGH_BITS 8
126#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
127#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
128
129/*
130 * Maximum length of a match is 273 which is a result of the encoding
131 * described above.
132 */
133#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
134
135/*
136 * Different sets of probabilities are used for match distances that have
137 * very short match length: Lengths of 2, 3, and 4 bytes have a separate
138 * set of probabilities for each length. The matches with longer length
139 * use a shared set of probabilities.
140 */
141#define DIST_STATES 4
142
143/*
144 * Get the index of the appropriate probability array for decoding
145 * the distance slot.
146 */
147static inline uint32_t lzma_get_dist_state(uint32_t len)
148{
149 return len < DIST_STATES + MATCH_LEN_MIN
150 ? len - MATCH_LEN_MIN : DIST_STATES - 1;
151}
152
153/*
154 * The highest two bits of a 32-bit match distance are encoded using six bits.
155 * This six-bit value is called a distance slot. This way encoding a 32-bit
156 * value takes 6-36 bits, larger values taking more bits.
157 */
158#define DIST_SLOT_BITS 6
159#define DIST_SLOTS (1 << DIST_SLOT_BITS)
160
161/* Match distances up to 127 are fully encoded using probabilities. Since
162 * the highest two bits (distance slot) are always encoded using six bits,
163 * the distances 0-3 don't need any additional bits to encode, since the
164 * distance slot itself is the same as the actual distance. DIST_MODEL_START
165 * indicates the first distance slot where at least one additional bit is
166 * needed.
167 */
168#define DIST_MODEL_START 4
169
170/*
171 * Match distances greater than 127 are encoded in three pieces:
172 * - distance slot: the highest two bits
173 * - direct bits: 2-26 bits below the highest two bits
174 * - alignment bits: four lowest bits
175 *
176 * Direct bits don't use any probabilities.
177 *
178 * The distance slot value of 14 is for distances 128-191.
179 */
180#define DIST_MODEL_END 14
181
182/* Distance slots that indicate a distance <= 127. */
183#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
184#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
185
186/*
187 * For match distances greater than 127, only the highest two bits and the
188 * lowest four bits (alignment) is encoded using probabilities.
189 */
190#define ALIGN_BITS 4
191#define ALIGN_SIZE (1 << ALIGN_BITS)
192#define ALIGN_MASK (ALIGN_SIZE - 1)
193
194/* Total number of all probability variables */
195#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
196
197/*
198 * LZMA remembers the four most recent match distances. Reusing these
199 * distances tends to take less space than re-encoding the actual
200 * distance value.
201 */
202#define REPS 4
203
204#endif
diff --git a/lib/xz/xz_private.h b/lib/xz/xz_private.h
new file mode 100644
index 000000000000..a65633e06962
--- /dev/null
+++ b/lib/xz/xz_private.h
@@ -0,0 +1,156 @@
1/*
2 * Private includes and definitions
3 *
4 * Author: Lasse Collin <lasse.collin@tukaani.org>
5 *
6 * This file has been put into the public domain.
7 * You can do whatever you want with this file.
8 */
9
10#ifndef XZ_PRIVATE_H
11#define XZ_PRIVATE_H
12
13#ifdef __KERNEL__
14# include <linux/xz.h>
15# include <asm/byteorder.h>
16# include <asm/unaligned.h>
17 /* XZ_PREBOOT may be defined only via decompress_unxz.c. */
18# ifndef XZ_PREBOOT
19# include <linux/slab.h>
20# include <linux/vmalloc.h>
21# include <linux/string.h>
22# ifdef CONFIG_XZ_DEC_X86
23# define XZ_DEC_X86
24# endif
25# ifdef CONFIG_XZ_DEC_POWERPC
26# define XZ_DEC_POWERPC
27# endif
28# ifdef CONFIG_XZ_DEC_IA64
29# define XZ_DEC_IA64
30# endif
31# ifdef CONFIG_XZ_DEC_ARM
32# define XZ_DEC_ARM
33# endif
34# ifdef CONFIG_XZ_DEC_ARMTHUMB
35# define XZ_DEC_ARMTHUMB
36# endif
37# ifdef CONFIG_XZ_DEC_SPARC
38# define XZ_DEC_SPARC
39# endif
40# define memeq(a, b, size) (memcmp(a, b, size) == 0)
41# define memzero(buf, size) memset(buf, 0, size)
42# endif
43# define get_le32(p) le32_to_cpup((const uint32_t *)(p))
44#else
45 /*
46 * For userspace builds, use a separate header to define the required
47 * macros and functions. This makes it easier to adapt the code into
48 * different environments and avoids clutter in the Linux kernel tree.
49 */
50# include "xz_config.h"
51#endif
52
53/* If no specific decoding mode is requested, enable support for all modes. */
54#if !defined(XZ_DEC_SINGLE) && !defined(XZ_DEC_PREALLOC) \
55 && !defined(XZ_DEC_DYNALLOC)
56# define XZ_DEC_SINGLE
57# define XZ_DEC_PREALLOC
58# define XZ_DEC_DYNALLOC
59#endif
60
61/*
62 * The DEC_IS_foo(mode) macros are used in "if" statements. If only some
63 * of the supported modes are enabled, these macros will evaluate to true or
64 * false at compile time and thus allow the compiler to omit unneeded code.
65 */
66#ifdef XZ_DEC_SINGLE
67# define DEC_IS_SINGLE(mode) ((mode) == XZ_SINGLE)
68#else
69# define DEC_IS_SINGLE(mode) (false)
70#endif
71
72#ifdef XZ_DEC_PREALLOC
73# define DEC_IS_PREALLOC(mode) ((mode) == XZ_PREALLOC)
74#else
75# define DEC_IS_PREALLOC(mode) (false)
76#endif
77
78#ifdef XZ_DEC_DYNALLOC
79# define DEC_IS_DYNALLOC(mode) ((mode) == XZ_DYNALLOC)
80#else
81# define DEC_IS_DYNALLOC(mode) (false)
82#endif
83
84#if !defined(XZ_DEC_SINGLE)
85# define DEC_IS_MULTI(mode) (true)
86#elif defined(XZ_DEC_PREALLOC) || defined(XZ_DEC_DYNALLOC)
87# define DEC_IS_MULTI(mode) ((mode) != XZ_SINGLE)
88#else
89# define DEC_IS_MULTI(mode) (false)
90#endif
91
92/*
93 * If any of the BCJ filter decoders are wanted, define XZ_DEC_BCJ.
94 * XZ_DEC_BCJ is used to enable generic support for BCJ decoders.
95 */
96#ifndef XZ_DEC_BCJ
97# if defined(XZ_DEC_X86) || defined(XZ_DEC_POWERPC) \
98 || defined(XZ_DEC_IA64) || defined(XZ_DEC_ARM) \
99 || defined(XZ_DEC_ARM) || defined(XZ_DEC_ARMTHUMB) \
100 || defined(XZ_DEC_SPARC)
101# define XZ_DEC_BCJ
102# endif
103#endif
104
105/*
106 * Allocate memory for LZMA2 decoder. xz_dec_lzma2_reset() must be used
107 * before calling xz_dec_lzma2_run().
108 */
109XZ_EXTERN struct xz_dec_lzma2 *xz_dec_lzma2_create(enum xz_mode mode,
110 uint32_t dict_max);
111
112/*
113 * Decode the LZMA2 properties (one byte) and reset the decoder. Return
114 * XZ_OK on success, XZ_MEMLIMIT_ERROR if the preallocated dictionary is not
115 * big enough, and XZ_OPTIONS_ERROR if props indicates something that this
116 * decoder doesn't support.
117 */
118XZ_EXTERN enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s,
119 uint8_t props);
120
121/* Decode raw LZMA2 stream from b->in to b->out. */
122XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
123 struct xz_buf *b);
124
125/* Free the memory allocated for the LZMA2 decoder. */
126XZ_EXTERN void xz_dec_lzma2_end(struct xz_dec_lzma2 *s);
127
128#ifdef XZ_DEC_BCJ
129/*
130 * Allocate memory for BCJ decoders. xz_dec_bcj_reset() must be used before
131 * calling xz_dec_bcj_run().
132 */
133XZ_EXTERN struct xz_dec_bcj *xz_dec_bcj_create(bool single_call);
134
135/*
136 * Decode the Filter ID of a BCJ filter. This implementation doesn't
137 * support custom start offsets, so no decoding of Filter Properties
138 * is needed. Returns XZ_OK if the given Filter ID is supported.
139 * Otherwise XZ_OPTIONS_ERROR is returned.
140 */
141XZ_EXTERN enum xz_ret xz_dec_bcj_reset(struct xz_dec_bcj *s, uint8_t id);
142
143/*
144 * Decode raw BCJ + LZMA2 stream. This must be used only if there actually is
145 * a BCJ filter in the chain. If the chain has only LZMA2, xz_dec_lzma2_run()
146 * must be called directly.
147 */
148XZ_EXTERN enum xz_ret xz_dec_bcj_run(struct xz_dec_bcj *s,
149 struct xz_dec_lzma2 *lzma2,
150 struct xz_buf *b);
151
152/* Free the memory allocated for the BCJ filters. */
153#define xz_dec_bcj_end(s) kfree(s)
154#endif
155
156#endif
diff --git a/lib/xz/xz_stream.h b/lib/xz/xz_stream.h
new file mode 100644
index 000000000000..66cb5a7055ec
--- /dev/null
+++ b/lib/xz/xz_stream.h
@@ -0,0 +1,62 @@
1/*
2 * Definitions for handling the .xz file format
3 *
4 * Author: Lasse Collin <lasse.collin@tukaani.org>
5 *
6 * This file has been put into the public domain.
7 * You can do whatever you want with this file.
8 */
9
10#ifndef XZ_STREAM_H
11#define XZ_STREAM_H
12
13#if defined(__KERNEL__) && !XZ_INTERNAL_CRC32
14# include <linux/crc32.h>
15# undef crc32
16# define xz_crc32(buf, size, crc) \
17 (~crc32_le(~(uint32_t)(crc), buf, size))
18#endif
19
20/*
21 * See the .xz file format specification at
22 * http://tukaani.org/xz/xz-file-format.txt
23 * to understand the container format.
24 */
25
26#define STREAM_HEADER_SIZE 12
27
28#define HEADER_MAGIC "\3757zXZ"
29#define HEADER_MAGIC_SIZE 6
30
31#define FOOTER_MAGIC "YZ"
32#define FOOTER_MAGIC_SIZE 2
33
34/*
35 * Variable-length integer can hold a 63-bit unsigned integer or a special
36 * value indicating that the value is unknown.
37 *
38 * Experimental: vli_type can be defined to uint32_t to save a few bytes
39 * in code size (no effect on speed). Doing so limits the uncompressed and
40 * compressed size of the file to less than 256 MiB and may also weaken
41 * error detection slightly.
42 */
43typedef uint64_t vli_type;
44
45#define VLI_MAX ((vli_type)-1 / 2)
46#define VLI_UNKNOWN ((vli_type)-1)
47
48/* Maximum encoded size of a VLI */
49#define VLI_BYTES_MAX (sizeof(vli_type) * 8 / 7)
50
51/* Integrity Check types */
52enum xz_check {
53 XZ_CHECK_NONE = 0,
54 XZ_CHECK_CRC32 = 1,
55 XZ_CHECK_CRC64 = 4,
56 XZ_CHECK_SHA256 = 10
57};
58
59/* Maximum possible Check ID */
60#define XZ_CHECK_MAX 15
61
62#endif
generated by cgit v1.2.2 (git 2.25.0) at 2025-12-30 02:09:59 -0500