Lines Matching +full:codeword +full:- +full:by +full:- +full:codeword
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() -
17 * This takes as input the length of the codeword for each symbol in the
19 * decoding of prefix-encoded symbols using read_huffsym().
28 * reconstructed directly from the codeword lengths. A prefix code is
29 * canonical if and only if a longer codeword never lexicographically
30 * precedes a shorter codeword, and the lexicographic ordering of
33 * primarily by codeword length and secondarily by symbol value, then
34 * reconstruct the prefix code by generating codewords lexicographically
40 * in the input, we can look up the decoded symbol by indexing a table
41 * containing 2**max_codeword_len entries. A codeword with length
43 * a codeword shorter than 'max_codeword_len' will have multiple entries
44 * in this table. Precisely, a codeword of length n will be represented
45 * by 2**(max_codeword_len - n) entries in this table. The 0-based index
46 * of each such entry will contain the corresponding codeword as a prefix
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,
64 * used symbols are assigned the shortest codeword lengths.
66 * - When we decode a symbol using a direct lookup of the table, we still
67 * need to know its length so that the bitstream can be advanced by the
91 * An array of length @num_syms, indexable by symbol, that gives the
92 * length of the codeword, in bits, for that symbol. The length can
93 * be 0, which means that the symbol does not have a codeword
97 * The longest codeword length allowed in the compression format.
105 * Returns 0 on success, or -1 if the lengths do not form a valid prefix
126 /* Count how many symbols have each possible codeword length. in make_huffman_decode_table()
128 * used in the code and therefore does not have a codeword. in make_huffman_decode_table()
136 * cannot assume they form a valid prefix code. A codeword of in make_huffman_decode_table()
139 * exactly filled by the lengths, by this measure. in make_huffman_decode_table()
144 left -= len_counts[len]; in make_huffman_decode_table()
147 * is over-subscribed. in make_huffman_decode_table()
149 return -1; in make_huffman_decode_table()
160 * so we must allow it. By definition, no symbols can in make_huffman_decode_table()
172 return -1; in make_huffman_decode_table()
175 /* Sort the symbols primarily by length and secondarily by symbol order. in make_huffman_decode_table()
194 * --- that is, those short enough for a direct mapping. in make_huffman_decode_table()
196 * The table will start with entries for the shortest codeword(s), which in make_huffman_decode_table()
198 * codeword will decrease. 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()
252 /* Iterate through each codeword with length greater than in make_huffman_decode_table()
253 * 'table_bits', primarily in order of codeword length in make_huffman_decode_table()
262 /* 'sorted_sym' is the symbol represented by the in make_huffman_decode_table()
263 * codeword. in make_huffman_decode_table()
266 u32 extra_bits = codeword_len - table_bits; in make_huffman_decode_table()
269 /* Go through each bit of the current codeword in make_huffman_decode_table()
277 * identically to other internal (non-leaf) in make_huffman_decode_table()
288 * codeword, but the current node is an in make_huffman_decode_table()
300 * in the codeword is 0; otherwise go to in make_huffman_decode_table()
304 --extra_bits; in make_huffman_decode_table()
309 * codeword, and we're now at the entry where in make_huffman_decode_table()
311 * distinguished from internal nodes by not in make_huffman_decode_table()