Table of Contents
QccENTHuffmanEncode, QccENTHuffmanDecode - Huffman encoding and
decoding
#include "libQccPack.h"
int QccENTHuffmanEncode(QccBitBuffer
*output_buffer, const int *symbols, int num_symbols, const QccENTHuffmanTable
*table);
int QccENTHuffmanDecode(QccBitBuffer *input_buffer, int *symbols,
int num_symbols, const QccENTHuffmanTable *table);
QccENTHuffmanEncode()
performs Huffman coding of the symbol stream in symbols, outputting the
binary codewords to output_buffer. num_symbols indicates how many symbols
are in the symbol stream (which can be as short as one symbol). output_buffer
must be a QccBitBuffer that has been opened for writing prior to calling
QccENTHuffmanEncode(). Finally, table gives the table of Huffman codewords
for the alphabet of possible symbols. QccENTHuffmanDesign(3)
can be used
to design this table from a probability distribution of the symbols. table
must be an encoding table; i.e., table->table_type must be QCCENTHUFFMAN_ENCODETABLE.
After calling QccENTHuffmanEncode(), QccBitBufferFlush(3)
must be called
to ensure that the last few bits of the bitstream are actually written
to the output file.
QccENTHuffmanDecode() performs Huffman decoding of
the bits in the bitstream input_buffer, producing a output stream of symbols
that are stored in symbols . The symbols array must be allocated with
space sufficient for holding num_symbols integers; this allocation must
be done prior to calling QccENTHuffmanDecode(). Additionally, input_buffer
must be opened for reading prior to calling QccENTHuffmanDecode().
Multiple successive calls to QccENTHuffmanEncode() are possible; in this
case, the individual bitstreams produced by each encoding appear concatenated
in the final output bitstream. QccBitBufferFlush(3)
must be called after
the final call to QccENTHuffmanEncode() (but not after any of the preceeding
calls to QccENTHuffmanEncode()) to ensure that the last few bits of the
concatenated bitstream are actually written to the output file. Multiple
calls to QccENTHuffmanDecode() can be used to decode the concatenated
bitstream produced in this fashion, or a single call (with an appropriately
larger num_symbols value) will work too.
These routines are based upon
the implementations of Huffman encoding and decoding suggested in Annexes
C & F of the JPEG standard, ISO/IEC 10918.
These routines
return 0 on success, and 1 on failure.
QccENTHuffmanEncode() will fail
if it encounters an invalid symbol (a symbol that is outside of the permissible
range of 0 to QCCENTHUFFMAN_MAXSYMBOL, or a symbol that does not have
a valid codeword assigned to it in the Huffman table).
QccENTHuffmanDecode()
will fail if it encounters a bit pattern in the bitstream that does not
correspond to a valid codeword in the Huffman table.
QccENTHuffmanDesign(3)
,
QccENTHuffmanTable(3)
, QccPackENT(3)
, QccPack(3)
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.
Copyright (C)
1997-2021 James E. Fowler
Table of Contents
