This section describes
functions implementing the Huffman coding algorithm. This algorithm
performs so called entropy encoding. The main idea of this method
is to substitute the code words (Huffman codes) instead of symbols.
The least length codes correspond to the most often occurring symbols
allowing to perform compression. For example, the sequence “aaaaaaaa”
contains only one symbol ‘a' that corresponds to the Huffman code
with size 1 bit; after encoding the output sequence will have size
1 byte - thus compression ratio will be 8.
Limitations and conventions.
Intel IPP functions implement the Huffman static encoding. This
means that encoding is a two-passes operation. In the first pass
the probability structure of the source data is determined, then
in the second pass the encoding itself is performed. The table of
Huffman Code lengths must be passed to decoder (this table can be
effectively compressed).
Maximum length of the Huffman codes in the Intel IPP functions
for Huffman coding is 32 bits.
The functions for Huffman encoding/decoding initialize a correspondent
specification structure and perform the encoding and decoding operations.
To use the functions for encoding,
follow this general scheme:
- Call the function ippsEncodeHuffInitAlloc to allocate memory and initialize the Huffman structure for encoding
with specified frequency table.
Or call the function ippsEncodeHuffInit to initialize the Huffman structure for encoding in the previously
created external buffer. The size of this buffer can be computed
by calling the function ippsHuffGetSize.
- If encoding is performed by blocks,
call the function ippsHuffGetDstBuffSize to compute the size of the destination buffer.
- Call ippsEncodeHuffOne
to encode a single element, or call ippsEncodeHuff
to encode the source sequence (vector). (Alternatively the sequence
of N element can be encoded by calling ippsEncodeHuffOne N times.) Then call ippsEncodeHuffFinal to finalize the encoding procedure. Note that the size of the input
sequence (vector) must be passed to the decoding functions.
- Call ippsHuffGetLenCodeTable
to receive the table containing the lengths of Huffman codes.
This table must be passed to the decoding functions. To increase
the effectiveness of encoding it may be compressed by calling the
function ippsHuffLenCodeTablePack.
- Call ippsHuffFree
to free dynamic memory allocated with the Huffman structure for
encoding by the function ippsEncodeHuffInitAlloc.
To use these functions for decoding,
follow this general scheme:
- Call the function ippsDecodeHuffInitAlloc
to allocate memory and initialize the Huffman structure for decoding
with specified table containing lengths of Huffman codes.
Or call the function ippsDecodeHuffInit
to initialize the Huffman structure for encoding in the previously
created external buffer. The size of this buffer can be computed
by calling the function ippsHuffGetSize.
- If decoding is performed by blocks,
call the function ippsHuffGetDstBuffSize
to compute the size of the destination buffer.
- Call ippsDecodeHuffOne
to encode a single element, or call ippsDecodeHuff
to encode the source sequence (vector). The size of the source
non-encoded sequence (vector) must be passed from the encoding
functions as well as the table containing the lengths of Huffman
codes. If this table is in the packed form, it may be restored by calling
the function ippsHuffLenCodeTableUnpack.
- Call ippsHuffFree
to free dynamic memory allocated with the Huffman structure for
decoding by the function ippsDecodeHuffInitAlloc.