gem5  v22.1.0.0
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__
Base class for encoders.
Definition: base.hh:60
Node for the Huffman tree.
Definition: huffman.hh:79
uint64_t getFrequency() const
Getter for the frequency counter.
Definition: huffman.hh:108
const uint64_t _value
Value represented by this node, if this is a leaf node.
Definition: huffman.hh:85
bool isLeaf() const
Determine if the node is a leaf node by checking if it does not have sub-trees.
Definition: huffman.hh:117
uint64_t getValue() const
Get the leaf's value.
Definition: huffman.hh:128
const Node * getRightSubTree() const
Definition: huffman.hh:135
Node(Node *left, Node *right)
Initialize node as an internal node.
Definition: huffman.hh:101
std::unique_ptr< Node > _right
The right tree.
Definition: huffman.hh:91
Node(uint64_t value, uint64_t frequency)
Initialize node as a leaf node.
Definition: huffman.hh:95
std::unique_ptr< Node > _left
The left tree.
Definition: huffman.hh:88
const uint64_t _frequency
Frequency of the value represented by this node.
Definition: huffman.hh:82
This encoder builds a Huffman tree using the frequency of each value to be encoded.
Definition: huffman.hh:57
std::map< uint64_t, Code > valueToCode
Table containing the codewords and their respective lengths.
Definition: huffman.hh:148
void sample(uint64_t value, uint64_t frequency)
Inserts the value-frequency pair in the tree.
Definition: huffman.cc:53
Code encode(const uint64_t val) const override
The function responsible for the generation of the alternative value.
Definition: huffman.cc:116
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
void generateCodeMaps()
Generation of the code maps.
Definition: huffman.cc:84
const unsigned maxCodeLength
Maximum number of bits in a codeword.
Definition: huffman.hh:142
uint64_t decode(const uint64_t code) const override
Decode a value.
Definition: huffman.cc:132
std::map< uint64_t, uint64_t > codeToValue
Definition: huffman.hh:149
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
Huffman(uint64_t max_code_length)
Definition: huffman.cc:45
std::priority_queue< Node *, std::vector< Node * >, NodeComparator > trees
Definition: huffman.hh:163
Bitfield< 63 > val
Definition: misc.hh:776
GEM5_DEPRECATED_NAMESPACE(Encoder, encoder)
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
GEM5_DEPRECATED_NAMESPACE(GuestABI, guest_abi)
Entries are not inserted directly into the tree.
Definition: huffman.hh:156
bool operator()(const Node *lhs, const Node *rhs) const
Definition: huffman.hh:158

Generated on Wed Dec 21 2022 10:22:36 for gem5 by doxygen 1.9.1