This encoder builds a Huffman tree using the frequency of each value to be encoded. More...

#include <huffman.hh>

Inheritance diagram for Compressor::Encoder::Huffman:

Classes
class	Node
	Node for the Huffman tree. More...

struct	NodeComparator
	Entries are not inserted directly into the tree. More...

Public Member Functions
	Huffman (uint64_t max_code_length)

	~Huffman ()=default

void	sample (uint64_t value, uint64_t frequency)
	Inserts the value-frequency pair in the tree. More...

void	generateCodeMaps ()
	Generation of the code maps. More...

Code	encode (const uint64_t val) const override
	The function responsible for the generation of the alternative value. More...

uint64_t	decode (const uint64_t code) const override
	Decode a value. More...

Public Member Functions inherited from Compressor::Encoder::Base
	Base ()

virtual	~Base ()=default

Private Member Functions
std::unique_ptr< Node >	buildTree ()
	Build a Huffman tree using the values and their respective frequencies, which have been informed through the insertion function. More...

void	generateCodes (const Node *node, const Code &current_code)
	Recursive function that generates the huffman codes based on the tree provided. More...

Private Attributes
const unsigned	maxCodeLength
	Maximum number of bits in a codeword. More...

std::map< uint64_t, Code >	valueToCode
	Table containing the codewords and their respective lengths. More...

std::map< uint64_t, uint64_t >	codeToValue

std::priority_queue< Node , std::vector< Node >, NodeComparator >	trees

Detailed Description

This encoder builds a Huffman tree using the frequency of each value to be encoded.

Definition at line 48 of file huffman.hh.

Constructor & Destructor Documentation

◆ Huffman()

Compressor::Encoder::Huffman::Huffman ( uint64_t max_code_length )

Definition at line 38 of file huffman.cc.

References fatal_if, and maxCodeLength.

◆ ~Huffman()

Compressor::Encoder::Huffman::~Huffman ( )

default

Member Function Documentation

◆ buildTree()

std::unique_ptr< Huffman::Node > Compressor::Encoder::Huffman::buildTree ( )

private

Build a Huffman tree using the values and their respective frequencies, which have been informed through the insertion function.

Returns: A pointer to the root of the tree.

Definition at line 54 of file huffman.cc.

References trees.

Referenced by generateCodeMaps().

◆ decode()

uint64_t Compressor::Encoder::Huffman::decode ( const uint64_t code ) const

overridevirtual

Decode a value.

See also: encode()

Parameters

code	The encoded value.

Returns: The original value.

Implements Compressor::Encoder::Base.

Definition at line 125 of file huffman.cc.

References codeToValue.

◆ encode()

Code Compressor::Encoder::Huffman::encode ( const uint64_t val ) const

overridevirtual

The function responsible for the generation of the alternative value.

If the size of the returning Code is greater than the maximum undelying type's size (e.g., 64 bits) the encoding results should be discarded.

Parameters

The	value to be encoded.

Returns: The encoded value.

Implements Compressor::Encoder::Base.

Definition at line 109 of file huffman.cc.

References Compressor::Encoder::Code::code, Compressor::Encoder::Code::length, X86ISA::val, and valueToCode.

Referenced by Compressor::FrequentValues::compress(), and Compressor::FrequentValues::decompress().

◆ generateCodeMaps()

void Compressor::Encoder::Huffman::generateCodeMaps ( )

Generation of the code maps.

This automatically builds the tree.

Definition at line 77 of file huffman.cc.

References buildTree(), codeToValue, generateCodes(), and valueToCode.

Referenced by Compressor::FrequentValues::generateCodes().

◆ generateCodes()

void Compressor::Encoder::Huffman::generateCodes	(	const Node *	node,
		const Code &	current_code
	)

private

Recursive function that generates the huffman codes based on the tree provided.

The generated codes are added to the code map structure.

Parameters

node	The node being analyzed.
current_code	The code so far.

Definition at line 85 of file huffman.cc.

References Compressor::Encoder::Code::code, codeToValue, Compressor::Encoder::Huffman::Node::getLeftSubTree(), Compressor::Encoder::Huffman::Node::getRightSubTree(), Compressor::Encoder::Huffman::Node::getValue(), Compressor::Encoder::Huffman::Node::isLeaf(), Compressor::Encoder::Code::length, maxCodeLength, and valueToCode.

Referenced by generateCodeMaps().

◆ sample()

void Compressor::Encoder::Huffman::sample	(	uint64_t	value,
		uint64_t	frequency
	)

Inserts the value-frequency pair in the tree.

Parameters

value	The value.
frequency	The value's frequency.

Definition at line 46 of file huffman.cc.

References trees.

Referenced by Compressor::FrequentValues::generateCodes().

Member Data Documentation

◆ codeToValue

std::map<uint64_t, uint64_t> Compressor::Encoder::Huffman::codeToValue

private

Definition at line 141 of file huffman.hh.

Referenced by decode(), generateCodeMaps(), and generateCodes().

◆ maxCodeLength

const unsigned Compressor::Encoder::Huffman::maxCodeLength

private

Maximum number of bits in a codeword.

If a codeword requires more than this amount of bits, its respective value is discarded.

Definition at line 134 of file huffman.hh.

Referenced by generateCodes(), and Huffman().

◆ trees

std::priority_queue<Node*, std::vector<Node*>, NodeComparator> Compressor::Encoder::Huffman::trees

private

Definition at line 155 of file huffman.hh.

Referenced by buildTree(), and sample().

◆ valueToCode

std::map<uint64_t, Code> Compressor::Encoder::Huffman::valueToCode

private

Table containing the codewords and their respective lengths.

Some entries are discarded due to their lengths being too big.

Definition at line 140 of file huffman.hh.

Referenced by encode(), generateCodeMaps(), and generateCodes().

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

mem/cache/compressors/encoders/huffman.hh
mem/cache/compressors/encoders/huffman.cc

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Huffman()

◆ ~Huffman()

Member Function Documentation

◆ buildTree()

◆ decode()

◆ encode()

◆ generateCodeMaps()

◆ generateCodes()

◆ sample()

Member Data Documentation

◆ codeToValue

◆ maxCodeLength

◆ trees

◆ valueToCode