gem5  v22.0.0.2
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
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:
gem5::compression::encoder::Base

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< NodebuildTree ()
 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, CodevalueToCode
 Table containing the codewords and their respective lengths. More...
 
std::map< uint64_t, uint64_t > codeToValue
 
std::priority_queue< Node *, std::vector< Node * >, NodeComparatortrees
 

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
codeThe 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
Thevalue 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
nodeThe node being analyzed.
current_codeThe 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
valueThe value.
frequencyThe 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:

Generated on Thu Jul 28 2022 13:33:28 for gem5 by doxygen 1.8.17