1 // SPDX-License-Identifier: GPL-2.0-or-later
3  * lzx_decompress.c - A decompressor for the LZX compression format, which can
22 #define LZX_NUM_LENS			(LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1)
28 /* Valid values of the 3-bit block type field  */
41 #define LZX_LENCODE_NUM_SYMBOLS		(LZX_NUM_LENS - LZX_NUM_PRIMARY_LENS)
46 /* Number of bits in which each precode codeword length is represented  */
49 /* Number of low-order bits of each match offset that are entropy-encoded in
57 /* Mask for the match offset bits that are entropy-encoded in aligned offset
60 #define LZX_ALIGNED_OFFSET_BITMASK	((1 << LZX_NUM_ALIGNED_OFFSET_BITS) - 1)
62 /* Number of bits in which each aligned offset codeword length is represented  */
68 #define LZX_MAX_PRE_CODEWORD_LEN	((1 << LZX_PRECODE_ELEMENT_SIZE) - 1)
69 #define LZX_MAX_ALIGNED_CODEWORD_LEN	((1 << LZX_ALIGNEDCODE_ELEMENT_SIZE) - 1)
71 /* The default "filesize" value used in pre/post-processing.  In the LZX format
73  * in the LZX format used in WIM files and system-compressed files this value is
95 	0,	1,	2,	3,	4,	/* 0  --- 4  */
96 	6,	8,	12,	16,	24,	/* 5  --- 9  */
97 	32,	48,	64,	96,	128,	/* 10 --- 14 */
98 	192,	256,	384,	512,	768,	/* 15 --- 19 */
99 	1024,	1536,	2048,	3072,	4096,   /* 20 --- 24 */
100 	6144,	8192,	12288,	16384,	24576,	/* 25 --- 29 */
116 /* Reusable heap-allocated memory for LZX decompression  */
119 	/* Huffman decoding tables, and arrays that map symbols to codeword
154 			rel_offset = abs_offset - input_pos;  in undo_e8_translation()
158 		if (abs_offset >= -input_pos) {  in undo_e8_translation()
168  * uncompressed data was preprocessed by changing the targets of suspected x86
175 	 * A worthwhile optimization is to push the end-of-buffer check into the  in lzx_postprocess()
178 	 * before reaching end-of-buffer.  In addition, this scheme guarantees  in lzx_postprocess()
180 	 * bytes because a 4-byte offset containing E8 as its high byte is a  in lzx_postprocess()
191 	tail = &data[size - 6];  in lzx_postprocess()
200 		undo_e8_translation(p + 1, p - data);  in lzx_postprocess()
206 /* Read a Huffman-encoded symbol using the precode.  */
210 	return read_huffsym(is, d->precode_decode_table,  in read_presym()
214 /* Read a Huffman-encoded symbol using the main code.  */
218 	return read_huffsym(is, d->maincode_decode_table,  in read_mainsym()
222 /* Read a Huffman-encoded symbol using the length code.  */
226 	return read_huffsym(is, d->lencode_decode_table,  in read_lensym()
230 /* Read a Huffman-encoded symbol using the aligned offset code.  */
234 	return read_huffsym(is, d->alignedcode_decode_table,  in read_alignedsym()
241  * @num_lens codeword length values.
246  *		the codeword lengths for this Huffman code were read, or all 0's
252  * Returns 0 on success, or -1 if the data was invalid.
266 		d->precode_lens[i] =  in lzx_read_codeword_lens()
271 	if (make_huffman_decode_table(d->precode_decode_table,  in lzx_read_codeword_lens()
274 				      d->precode_lens,  in lzx_read_codeword_lens()
276 				      d->working_space))  in lzx_read_codeword_lens()
277 		return -1;  in lzx_read_codeword_lens()
279 	/* Decode the codeword lengths.  */  in lzx_read_codeword_lens()
288 			len = *len_ptr - presym;  in lzx_read_codeword_lens()
310 					return -1;  in lzx_read_codeword_lens()
311 				len = *len_ptr - presym;  in lzx_read_codeword_lens()
318 			} while (--run_len);  in lzx_read_codeword_lens()
343  * Return 0 on success, or -1 if the data was invalid.
380 			d->alignedcode_lens[i] =  in lzx_read_block_header()
385 		if (make_huffman_decode_table(d->alignedcode_decode_table,  in lzx_read_block_header()
388 					      d->alignedcode_lens,  in lzx_read_block_header()
390 					      d->working_space))  in lzx_read_block_header()
391 			return -1;  in lzx_read_block_header()
402 		 * Note that the codeword lengths in the main code are encoded  in lzx_read_block_header()
407 		if (lzx_read_codeword_lens(d, is, d->maincode_lens,  in lzx_read_block_header()
409 			return -1;  in lzx_read_block_header()
412 					   d->maincode_lens + LZX_NUM_CHARS,  in lzx_read_block_header()
413 					   LZX_MAINCODE_NUM_SYMBOLS - LZX_NUM_CHARS))  in lzx_read_block_header()
414 			return -1;  in lzx_read_block_header()
416 		if (make_huffman_decode_table(d->maincode_decode_table,  in lzx_read_block_header()
419 					      d->maincode_lens,  in lzx_read_block_header()
421 					      d->working_space))  in lzx_read_block_header()
422 			return -1;  in lzx_read_block_header()
426 		if (lzx_read_codeword_lens(d, is, d->lencode_lens,  in lzx_read_block_header()
428 			return -1;  in lzx_read_block_header()
430 		if (make_huffman_decode_table(d->lencode_decode_table,  in lzx_read_block_header()
433 					      d->lencode_lens,  in lzx_read_block_header()
435 					      d->working_space))  in lzx_read_block_header()
436 			return -1;  in lzx_read_block_header()
443 		 * block header, the stream must be aligned on a 16-bit  in lzx_read_block_header()
457 			return -1;  in lzx_read_block_header()
462 		return -1;  in lzx_read_block_header()
470 /* Decompress a block of LZX-compressed data.  */
478 	u32 ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED);  in lzx_decompress_block()
497 		mainsym -= LZX_NUM_CHARS;  in lzx_decompress_block()
511 			 * quirk allows all 3 recent offsets to be handled by  in lzx_decompress_block()
512 			 * the same code.  (For R0, the swap is a no-op.)  in lzx_decompress_block()
527 			/* In aligned offset blocks, the low-order 3 bits of  in lzx_decompress_block()
534 					bitstream_read_bits(is, num_extra_bits -  in lzx_decompress_block()
543 			match_offset -= (LZX_NUM_RECENT_OFFSETS - 1);  in lzx_decompress_block()
553 		if (match_len > (size_t)(block_end - out_next))  in lzx_decompress_block()
554 			return -1;  in lzx_decompress_block()
556 		if (match_offset > (size_t)(out_next - out_begin))  in lzx_decompress_block()
557 			return -1;  in lzx_decompress_block()
568  * lzx_allocate_decompressor - Allocate an LZX decompressor
579  * lzx_decompress - Decompress a buffer of LZX-compressed data
587  * Return 0 on success, or return -1 and set errno on failure.
603 	/* Codeword lengths begin as all 0's for delta encoding purposes.  */  in lzx_decompress()
604 	memset(d->maincode_lens, 0, LZX_MAINCODE_NUM_SYMBOLS);  in lzx_decompress()
605 	memset(d->lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS);  in lzx_decompress()
617 		if (block_size < 1 || block_size > (size_t)(out_end - out_next))  in lzx_decompress()
633 			e8_status |= d->maincode_lens[0xe8];  in lzx_decompress()
657 	return -1;  in lzx_decompress()
661  * lzx_free_decompressor - Free an LZX decompressor