gem5  v22.0.0.2
huffman.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2019, 2020 Inria
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met: redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer;
9  * redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution;
12  * neither the name of the copyright holders nor the names of its
13  * contributors may be used to endorse or promote products derived from
14  * this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #ifndef __MEM_CACHE_COMPRESSORS_ENCODERS_HUFFMAN_HH__
30 #define __MEM_CACHE_COMPRESSORS_ENCODERS_HUFFMAN_HH__
31 
32 #include <cassert>
33 #include <cstdint>
34 #include <map>
35 #include <memory>
36 #include <queue>
37 #include <vector>
38 
39 #include "base/compiler.hh"
41 
42 namespace gem5
43 {
44 
45 GEM5_DEPRECATED_NAMESPACE(Compressor, compression);
46 namespace compression
47 {
48 GEM5_DEPRECATED_NAMESPACE(Encoder, encoder);
49 namespace encoder
50 {
51 
56 class Huffman : public Base
57 {
58  public:
59  Huffman(uint64_t max_code_length);
60  ~Huffman() = default;
61 
68  void sample(uint64_t value, uint64_t frequency);
69 
71  void generateCodeMaps();
72 
73  Code encode(const uint64_t val) const override;
74  uint64_t decode(const uint64_t code) const override;
75 
76  private:
78  class Node
79  {
80  private:
82  const uint64_t _frequency;
83 
85  const uint64_t _value;
86 
88  std::unique_ptr<Node> _left;
89 
91  std::unique_ptr<Node> _right;
92 
93  public:
95  Node(uint64_t value, uint64_t frequency)
96  : _frequency(frequency), _value(value), _left(), _right()
97  {
98  }
99 
101  Node(Node* left, Node* right)
102  : _frequency(left->getFrequency() + right->getFrequency()),
103  _value(0), _left(left), _right(right)
104  {
105  }
106 
108  uint64_t getFrequency() const { return _frequency; }
109 
116  bool
117  isLeaf() const
118  {
119  return (_left == nullptr) && (_right == nullptr);
120  }
121 
127  uint64_t
128  getValue() const
129  {
130  assert(isLeaf());
131  return _value;
132  }
133 
134  const Node* getLeftSubTree() const { return _left.get(); }
135  const Node* getRightSubTree() const { return _right.get(); }
136  };
137 
142  const unsigned maxCodeLength;
143 
148  std::map<uint64_t, Code> valueToCode;
149  std::map<uint64_t, uint64_t> codeToValue;
150 
156  {
157  bool
158  operator()(const Node* lhs, const Node* rhs) const
159  {
160  return lhs->getFrequency() > rhs->getFrequency();
161  }
162  };
163  std::priority_queue<Node*, std::vector<Node*>, NodeComparator> trees;
164 
172  std::unique_ptr<Node> buildTree();
173 
182  void generateCodes(const Node* node, const Code& current_code);
183 };
184 
185 } // namespace encoder
186 } // namespace compression
187 } // namespace gem5
188 
189 #endif //__MEM_CACHE_COMPRESSORS_ENCODERS_HUFFMAN_HH__
gem5::compression::encoder::Huffman::Node::Node
Node(Node *left, Node *right)
Initialize node as an internal node.
Definition: huffman.hh:101
gem5::compression::encoder::Huffman::Node::isLeaf
bool isLeaf() const
Determine if the node is a leaf node by checking if it does not have sub-trees.
Definition: huffman.hh:117
gem5::compression::encoder::Huffman::Huffman
Huffman(uint64_t max_code_length)
Definition: huffman.cc:45
gem5::compression::encoder::Base
Base class for encoders.
Definition: base.hh:59
base.hh
gem5::X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:769
gem5::compression::encoder::Huffman::NodeComparator
Entries are not inserted directly into the tree.
Definition: huffman.hh:155
gem5::compression::encoder::Huffman::decode
uint64_t decode(const uint64_t code) const override
Decode a value.
Definition: huffman.cc:132
gem5::compression::encoder::Huffman::Node::Node
Node(uint64_t value, uint64_t frequency)
Initialize node as a leaf node.
Definition: huffman.hh:95
gem5::compression::encoder::Huffman::Node::_left
std::unique_ptr< Node > _left
The left tree.
Definition: huffman.hh:88
gem5::compression::encoder::Huffman::Node::_frequency
const uint64_t _frequency
Frequency of the value represented by this node.
Definition: huffman.hh:82
gem5::compression::encoder::Huffman::trees
std::priority_queue< Node *, std::vector< Node * >, NodeComparator > trees
Definition: huffman.hh:163
gem5::compression::encoder::Huffman::buildTree
std::unique_ptr< Node > buildTree()
Build a Huffman tree using the values and their respective frequencies, which have been informed thro...
Definition: huffman.cc:61
gem5::compression::encoder::Huffman
This encoder builds a Huffman tree using the frequency of each value to be encoded.
Definition: huffman.hh:56
gem5::compression::encoder::Code
Definition: base.hh:46
gem5::compression::encoder::Huffman::codeToValue
std::map< uint64_t, uint64_t > codeToValue
Definition: huffman.hh:149
gem5::compression::encoder::Huffman::encode
Code encode(const uint64_t val) const override
The function responsible for the generation of the alternative value.
Definition: huffman.cc:116
compiler.hh
gem5::compression::encoder::Huffman::valueToCode
std::map< uint64_t, Code > valueToCode
Table containing the codewords and their respective lengths.
Definition: huffman.hh:148
gem5::compression::encoder::Huffman::Node::getRightSubTree
const Node * getRightSubTree() const
Definition: huffman.hh:135
gem5::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(GuestABI, guest_abi)
gem5::compression::encoder::Huffman::maxCodeLength
const unsigned maxCodeLength
Maximum number of bits in a codeword.
Definition: huffman.hh:142
gem5::compression::encoder::Huffman::generateCodes
void generateCodes(const Node *node, const Code &current_code)
Recursive function that generates the huffman codes based on the tree provided.
Definition: huffman.cc:92
gem5::compression::encoder::Huffman::sample
void sample(uint64_t value, uint64_t frequency)
Inserts the value-frequency pair in the tree.
Definition: huffman.cc:53
gem5::compression::encoder::Huffman::Node::getLeftSubTree
const Node * getLeftSubTree() const
Definition: huffman.hh:134
gem5::compression::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(Encoder, encoder)
gem5::compression::encoder::Huffman::~Huffman
~Huffman()=default
gem5::compression::encoder::Huffman::Node::getFrequency
uint64_t getFrequency() const
Getter for the frequency counter.
Definition: huffman.hh:108
gem5::compression::encoder::Huffman::Node::_value
const uint64_t _value
Value represented by this node, if this is a leaf node.
Definition: huffman.hh:85
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: gpu_translation_state.hh:37
gem5::compression::encoder::Huffman::generateCodeMaps
void generateCodeMaps()
Generation of the code maps.
Definition: huffman.cc:84
gem5::compression::encoder::Huffman::Node::_right
std::unique_ptr< Node > _right
The right tree.
Definition: huffman.hh:91
gem5::compression::encoder::Huffman::Node
Node for the Huffman tree.
Definition: huffman.hh:78
gem5::compression::encoder::Huffman::NodeComparator::operator()
bool operator()(const Node *lhs, const Node *rhs) const
Definition: huffman.hh:158
gem5::compression::encoder::Huffman::Node::getValue
uint64_t getValue() const
Get the leaf's value.
Definition: huffman.hh:128

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