1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  * xpress_decompress.c - A decompressor for the XPRESS compression format
4  * (Huffman variant), which can be used in "System Compressed" files.  This is
5  * based on the code from wimlib.
6  *
7  * Copyright (C) 2015 Eric Biggers
8  */
9 
10 #include "decompress_common.h"
11 #include "lib.h"
12 
13 #define XPRESS_NUM_SYMBOLS	512
14 #define XPRESS_MAX_CODEWORD_LEN	15
15 #define XPRESS_MIN_MATCH_LEN	3
16 
17 /* This value is chosen for fast decompression.  */
18 #define XPRESS_TABLEBITS 12
19 
20 /* Reusable heap-allocated memory for XPRESS decompression  */
21 struct xpress_decompressor {
22 
23 	/* The Huffman decoding table  */
24 	u16 decode_table[(1 << XPRESS_TABLEBITS) + 2 * XPRESS_NUM_SYMBOLS];
25 
26 	/* An array that maps symbols to codeword lengths  */
27 	u8 lens[XPRESS_NUM_SYMBOLS];
28 
29 	/* Temporary space for make_huffman_decode_table()  */
30 	u16 working_space[2 * (1 + XPRESS_MAX_CODEWORD_LEN) +
31 			  XPRESS_NUM_SYMBOLS];
32 };
33 
34 /*
35  * xpress_allocate_decompressor - Allocate an XPRESS decompressor
36  *
37  * Return the pointer to the decompressor on success, or return NULL and set
38  * errno on failure.
39  */
xpress_allocate_decompressor(void)40 struct xpress_decompressor *xpress_allocate_decompressor(void)
41 {
42 	return kmalloc(sizeof(struct xpress_decompressor), GFP_NOFS);
43 }
44 
45 /*
46  * xpress_decompress - Decompress a buffer of XPRESS-compressed data
47  *
48  * @decompressor:       A decompressor that was allocated with
49  *			xpress_allocate_decompressor()
50  * @compressed_data:	The buffer of data to decompress
51  * @compressed_size:	Number of bytes of compressed data
52  * @uncompressed_data:	The buffer in which to store the decompressed data
53  * @uncompressed_size:	The number of bytes the data decompresses into
54  *
55  * Return 0 on success, or return -1 and set errno on failure.
56  */
xpress_decompress(struct xpress_decompressor * decompressor,const void * compressed_data,size_t compressed_size,void * uncompressed_data,size_t uncompressed_size)57 int xpress_decompress(struct xpress_decompressor *decompressor,
58 		      const void *compressed_data, size_t compressed_size,
59 		      void *uncompressed_data, size_t uncompressed_size)
60 {
61 	struct xpress_decompressor *d = decompressor;
62 	const u8 * const in_begin = compressed_data;
63 	u8 * const out_begin = uncompressed_data;
64 	u8 *out_next = out_begin;
65 	u8 * const out_end = out_begin + uncompressed_size;
66 	struct input_bitstream is;
67 	u32 i;
68 
69 	/* Read the Huffman codeword lengths.  */
70 	if (compressed_size < XPRESS_NUM_SYMBOLS / 2)
71 		goto invalid;
72 	for (i = 0; i < XPRESS_NUM_SYMBOLS / 2; i++) {
73 		d->lens[i*2 + 0] = in_begin[i] & 0xF;
74 		d->lens[i*2 + 1] = in_begin[i] >> 4;
75 	}
76 
77 	/* Build a decoding table for the Huffman code.  */
78 	if (make_huffman_decode_table(d->decode_table, XPRESS_NUM_SYMBOLS,
79 				      XPRESS_TABLEBITS, d->lens,
80 				      XPRESS_MAX_CODEWORD_LEN,
81 				      d->working_space))
82 		goto invalid;
83 
84 	/* Decode the matches and literals.  */
85 
86 	init_input_bitstream(&is, in_begin + XPRESS_NUM_SYMBOLS / 2,
87 			     compressed_size - XPRESS_NUM_SYMBOLS / 2);
88 
89 	while (out_next != out_end) {
90 		u32 sym;
91 		u32 log2_offset;
92 		u32 length;
93 		u32 offset;
94 
95 		sym = read_huffsym(&is, d->decode_table,
96 				   XPRESS_TABLEBITS, XPRESS_MAX_CODEWORD_LEN);
97 		if (sym < 256) {
98 			/* Literal  */
99 			*out_next++ = sym;
100 		} else {
101 			/* Match  */
102 			length = sym & 0xf;
103 			log2_offset = (sym >> 4) & 0xf;
104 
105 			bitstream_ensure_bits(&is, 16);
106 
107 			offset = ((u32)1 << log2_offset) |
108 				 bitstream_pop_bits(&is, log2_offset);
109 
110 			if (length == 0xf) {
111 				length += bitstream_read_byte(&is);
112 				if (length == 0xf + 0xff)
113 					length = bitstream_read_u16(&is);
114 			}
115 			length += XPRESS_MIN_MATCH_LEN;
116 
117 			if (offset > (size_t)(out_next - out_begin))
118 				goto invalid;
119 
120 			if (length > (size_t)(out_end - out_next))
121 				goto invalid;
122 
123 			out_next = lz_copy(out_next, length, offset, out_end,
124 					   XPRESS_MIN_MATCH_LEN);
125 		}
126 	}
127 	return 0;
128 
129 invalid:
130 	return -1;
131 }
132 
133 /*
134  * xpress_free_decompressor - Free an XPRESS decompressor
135  *
136  * @decompressor:       A decompressor that was allocated with
137  *			xpress_allocate_decompressor(), or NULL.
138  */
xpress_free_decompressor(struct xpress_decompressor * decompressor)139 void xpress_free_decompressor(struct xpress_decompressor *decompressor)
140 {
141 	kfree(decompressor);
142 }
143