#include <huffman_decoder.hpp>

Inheritance diagram for fly::coders::HuffmanDecoder:

Collaboration diagram for fly::coders::HuffmanDecoder:

Public Member Functions
	HuffmanDecoder () noexcept

code_type	compute_kraft_mcmillan_constant () const

Public Member Functions inherited from fly::coders::Decoder
virtual	~Decoder ()=default

bool	decode_string (const std::string &encoded, std::string &decoded)

bool	decode_file (const std::filesystem::path &encoded, const std::filesystem::path &decoded)

Protected Member Functions
bool	decode_binary (fly::BitStreamReader &encoded, std::ostream &decoded) override

Protected Member Functions inherited from fly::coders::BinaryDecoder
bool	decode_internal (std::istream &encoded, std::ostream &decoded) final

Detailed Description

Implementation of the Decoder interface for Huffman coding.

Author: Timothy Flynn (trfly.nosp@m.nn89.nosp@m.@pm.m.nosp@m.e)

Version: July 7, 2019

Constructor & Destructor Documentation

◆ HuffmanDecoder()

fly::coders::HuffmanDecoder::HuffmanDecoder ( )

noexcept

Constructor.

Member Function Documentation

◆ compute_kraft_mcmillan_constant()

code_type fly::coders::HuffmanDecoder::compute_kraft_mcmillan_constant ( ) const

Compute the Kraft-McMillan constant of the decoded Huffman codes. Primarily meant for unit testing.

Returns: The Kraft-McMillan constant.

◆ decode_binary()

bool fly::coders::HuffmanDecoder::decode_binary	(	fly::BitStreamReader &	encoded,
		std::ostream &	decoded
	)

overrideprotectedvirtual

Huffman decode a stream.

Because large input streams are encoded in chunks, they must also be decoded in chunks. The input stream is decoded until either the end of the stream or the chunk size is reached. The decoding sequence is then repeated for each chunk.

The sequence to decode a stream is:

1. Decode the canonical Huffman codes from the stream.
2. Convert the canonical codes to a prefix table.
3. Decode the input stream using the table.

Prefix tables (step 2) function via the property that no Huffman code is a prefix of any other code. Thus, a table can be formed as an array, whose indices are integers where the most-significant bits are Huffman codes.

Decoding a symbol from the input stream (step 3) consists of peeking N bits from the input stream, where N is maximum length of the decoded Huffman codes. These bits are the index into the prefix table; a single lookup is performed to find the corresponding Huffman code. The actual length of the code is then discarded from the input stream.

Parameters

encoded	Stream holding the contents to decode.
decoded	Stream to store the decoded contents.

Returns: True if the input stream was successfully decoded.

Implements fly::coders::BinaryDecoder.

The documentation for this class was generated from the following files:

fly/coders/huffman/huffman_decoder.hpp
fly/coders/huffman/huffman_decoder.cpp