int QccENTHuffmanTableCreateDecodeTable(QccENTHuffmanTable
*table);
int QccENTHuffmanTableCreateEncodeTable(QccENTHuffmanTable *table);
A number of arrays and array lengths internal to table must be set before calling these routines. table->num_codewords_list is a list of the number of codewords of each length. The first entry in the list, table->num_codewords_list[0], gives the number of codewords with length equal to one bit; the second entry in the list, table->num_codewords_list[1], gives the number of codewords with length equal to two bits; etc. A zero indicates that there are no codewords of a particular length. table->num_codewords_list_length is the number of entries in table->num_codewords_list; table->num_codewords_list_length must be greater than zero, but less than or equal to QCCENTHUFFMAN_MAXCODEWORDLEN (defined to be 31 bits). If table->num_codewords_list_length is less than QCCENTHUFFMAN_MAXCODEWORDLEN, it is assumed that the number of codewords of lengths between table->num_codewords_list_length and QCCENTHUFFMAN_MAXCODEWORDLEN is zero.
table->symbol_list lists the symbols, in order, corresponding to the codewords implied by table->num_codewords_list. table->symbol_list_length gives the length of the table->symbol_list list. table->symbol_list_length must be exactly equal to the sum of all the lengths in table->num_codewords_list for table->num_codewords_list and table->symbol_list to be consistent with each other; QccENTHuffmanTableCreateDecodeTable() checks for this and returns an error if the two tables are not consistent in this way.
QccENTHuffmanTableCreateDecodeTable() returns a Huffman table with table->table_type set to QCCENTHUFFMAN_DECODETABLE, which means that table is suitable for Huffman decoding with QccENTHuffmanDecode(3) .
QccENTHuffmanTableCreateEncodeTable() returns a Huffman table with table->table_type set to QCCENTHUFFMAN_ENCODETABLE, which means that table is suitable for Huffman encoding with QccENTHuffmanEncode(3) . QccENTHuffmanTableCreateEncodeTable() first calls QccENTHuffmanTableCreateDecodeTable() to generate a decoding table, then reorganizes the decoding table so as to provide a lookup table indexed by the symbol value for quick encoding. Typically, this encoding-table format occupies much more memory than the corresponding decoding table.
Both QccENTHuffmanTableCreateEncodeTable() and QccENTHuffmanTableCreateDecodeTable() allocate space for table->table via a call to QccENTHuffmanTableAlloc(3) , so this should not be done prior to calling these routines.
Then QccENTHuffmanTableCreateDecodeTable() will assign the following Huffman codewords to the symbols:QccENTHuffmanTable table;
int num_codewords_list[] = { 0, 2, 1, 2 };
int symbol_list[] = { 'a', 'b', 'c', 'd', 'e' };
table.num_codewords_list_length = 4;
table.symbol_list_length = 5;
table.num_codewords_list = num_codewords_list;
table.symbol_list = symbol_list;
Note that num_codewords_list specifies zero length-1 codewords, two length-2 codewords, one length-3 codeword, and two length-4 codewords, and that the symbol_list symbols are given in the order corresponding to the lengths; i.e., both symbols 'a' and 'b' are to be assigned length-2 codewords.Symbol Codeword Length Codeword
-------------------------------------------
'a' 2 00
'b' 2 01
'c' 3 100
'd' 4 1010
'e' 4 1011
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes," Proceedings of the IRE, vol. 40, pp. 1098-1101, September 1952.
ISO/IEC 10918, Digital compression and coding of continuous-tone still images, 1994.