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

#include <huffman.hh>

Inheritance diagram for gem5::compression::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 gem5::compression::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 56 of file huffman.hh.

Constructor & Destructor Documentation

◆ Huffman()

gem5::compression::encoder::Huffman::Huffman ( uint64_t max_code_length )

Definition at line 45 of file huffman.cc.

References fatal_if, and maxCodeLength.

◆ ~Huffman()

gem5::compression::encoder::Huffman::~Huffman ( )

default

Member Function Documentation

◆ buildTree()

std::unique_ptr< Huffman::Node > gem5::compression::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 61 of file huffman.cc.

References trees.

Referenced by generateCodeMaps().

◆ decode()

uint64_t gem5::compression::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 gem5::compression::encoder::Base.

Definition at line 132 of file huffman.cc.

References codeToValue.

◆ encode()

Code gem5::compression::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 gem5::compression::encoder::Base.

Definition at line 116 of file huffman.cc.

References gem5::compression::encoder::Code::code, gem5::compression::encoder::Code::length, gem5::X86ISA::val, and valueToCode.

Referenced by gem5::compression::FrequentValues::compress(), and gem5::compression::FrequentValues::decompress().

◆ generateCodeMaps()

void gem5::compression::encoder::Huffman::generateCodeMaps ( )

Generation of the code maps.

This automatically builds the tree.

Definition at line 84 of file huffman.cc.

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

Referenced by gem5::compression::FrequentValues::generateCodes().

◆ generateCodes()

void gem5::compression::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 92 of file huffman.cc.

References gem5::compression::encoder::Code::code, codeToValue, gem5::compression::encoder::Huffman::Node::getLeftSubTree(), gem5::compression::encoder::Huffman::Node::getRightSubTree(), gem5::compression::encoder::Huffman::Node::getValue(), gem5::compression::encoder::Huffman::Node::isLeaf(), gem5::compression::encoder::Code::length, maxCodeLength, and valueToCode.

Referenced by generateCodeMaps().

◆ sample()

void gem5::compression::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 53 of file huffman.cc.

References trees.

Referenced by gem5::compression::FrequentValues::generateCodes().

Member Data Documentation

◆ codeToValue

std::map<uint64_t, uint64_t> gem5::compression::encoder::Huffman::codeToValue

private

Definition at line 149 of file huffman.hh.

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

◆ maxCodeLength

const unsigned gem5::compression::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 142 of file huffman.hh.

Referenced by generateCodes(), and Huffman().

◆ trees

std::priority_queue<Node*, std::vector<Node*>, NodeComparator> gem5::compression::encoder::Huffman::trees

private

Definition at line 163 of file huffman.hh.

Referenced by buildTree(), and sample().

◆ valueToCode

std::map<uint64_t, Code> gem5::compression::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 148 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