1 // SPDX-License-Identifier: GPL-2.0-or-later
3  * decompress_common.c - Code shared by the XPRESS and LZX decompressors
11  * make_huffman_decode_table() -
19  * decoding of prefix-encoded symbols using read_huffsym().
45  * by 2**(max_codeword_len - n) entries in this table.  The 0-based index
47  * when zero-padded on the left to 'max_codeword_len' binary digits.
52  * - For many compression formats, the maximum codeword length is too
60  *   bit-by-bit decoding of the remainder of the codeword.  Child nodes
62  *   contain symbols.  Note that the long-codeword case is, in general,
63  *   not performance critical, since in Huffman codes the most frequently
66  * - When we decode a symbol using a direct lookup of the table, we still
105  * Returns 0 on success, or -1 if the lengths do not form a valid prefix
117 	int left;  in make_huffman_decode_table()  local
141 	left = 1;  in make_huffman_decode_table()
143 		left <<= 1;  in make_huffman_decode_table()
144 		left -= len_counts[len];  in make_huffman_decode_table()
145 		if (left < 0) {  in make_huffman_decode_table()
147 			 * is over-subscribed.  in make_huffman_decode_table()
149 			return -1;  in make_huffman_decode_table()
153 	if (left) {  in make_huffman_decode_table()
157 		if (left == (1 << max_codeword_len)) {  in make_huffman_decode_table()
172 		return -1;  in make_huffman_decode_table()
194 	 * --- that is, those short enough for a direct mapping.  in make_huffman_decode_table()
197 	 * have the most entries.  From there, the number of entries per  in make_huffman_decode_table()
203 	stores_per_loop = (1 << (table_bits - codeword_len));  in make_huffman_decode_table()
218 			} while (--n);  in make_huffman_decode_table()
228 	decode_table_pos = (u16 *)decode_table_ptr - decode_table;  in make_huffman_decode_table()
266 				u32 extra_bits = codeword_len - table_bits;  in make_huffman_decode_table()
277 				 * identically to other internal (non-leaf)  in make_huffman_decode_table()
281 				 * simply the index of the left child combined  in make_huffman_decode_table()
299 					/* Go to the left child if the next bit  in make_huffman_decode_table()
304 					--extra_bits;  in make_huffman_decode_table()