gem5::compression::encoder::Huffman Class Reference

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.
void	generateCodeMaps ()
	Generation of the code maps.
Code	encode (const uint64_t val) const override
	The function responsible for the generation of the alternative value.
uint64_t	decode (const uint64_t code) const override
	Decode a value.
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.
void	generateCodes (const Node *node, const Code &current_code)
	Recursive function that generates the huffman codes based on the tree provided.

Private Attributes
const unsigned	maxCodeLength
	Maximum number of bits in a codeword.
std::map< uint64_t, Code >	valueToCode
	Table containing the codewords and their respective lengths.
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 54 of file huffman.hh.

Constructor & Destructor Documentation

Huffman()

gem5::compression::encoder::Huffman::Huffman

(

uint64_t

max_code_length

)

Definition at line 43 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 59 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 130 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 114 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 82 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 90 of file huffman.cc.

References gem5::compression::encoder::Code::code, codeToValue, generateCodes(), 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(), and generateCodes().

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 51 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 147 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 140 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 161 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 146 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