gem5  v21.1.0.2
huffman.cc
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 
30 
31 #include <cassert>
32 
33 #include "base/logging.hh"
34 
35 namespace gem5
36 {
37 
38 GEM5_DEPRECATED_NAMESPACE(Compressor, compression);
39 namespace compression
40 {
41 GEM5_DEPRECATED_NAMESPACE(Encoder, encoder);
42 namespace encoder
43 {
44 
45 Huffman::Huffman(uint64_t max_code_length)
46  : Base(), maxCodeLength(max_code_length)
47 {
49  "Code length cannot surpass its underlying container");
50 }
51 
52 void
53 Huffman::sample(uint64_t value, uint64_t frequency)
54 {
55  if (frequency != 0) {
56  trees.push(new Node(value, frequency));
57  }
58 }
59 
60 std::unique_ptr<Huffman::Node>
62 {
63  // Construct tree by assigning left and right nodes. The left path leads
64  // to the most frequent values
65  while (trees.size() > 1) {
66  Node* left = trees.top();
67  trees.pop();
68 
69  Node* right = trees.top();
70  trees.pop();
71 
72  Node* parent = new Node(left, right);
73  trees.push(parent);
74  }
75 
76  // All queue entries have been merged into a single entry containing
77  // the tree
78  Node* root = trees.top();
79  trees.pop();
80  return std::unique_ptr<Node>(root);
81 }
82 
83 void
85 {
86  valueToCode.clear();
87  codeToValue.clear();
88  generateCodes(buildTree().get(), Code());
89 }
90 
91 void
92 Huffman::generateCodes(const Node* node, const Code& current_code)
93 {
94  // Drop all entries with length greater than maxCodeLength
95  if (current_code.length > maxCodeLength) {
96  return;
97  }
98 
99  if (node->isLeaf()) {
100  valueToCode[node->getValue()] = current_code;
101  codeToValue[current_code.code] = node->getValue();
102  } else {
103  Code right_code = current_code;
104  right_code.code = (right_code.code << 1) + 1;
105  right_code.length++;
106  generateCodes(node->getRightSubTree(), right_code);
107 
108  Code left_code = current_code;
109  left_code.code = left_code.code << 1;
110  left_code.length++;
111  generateCodes(node->getLeftSubTree(), left_code);
112  }
113 }
114 
115 Code
116 Huffman::encode(const uint64_t val) const
117 {
118  auto it = valueToCode.find(val);
119  if (it == valueToCode.end()) {
120  // If the value is unknown, generate a dummy code with invalid
121  // length to let the caller know the encoding is invalid
122  Code dummy_code;
123  dummy_code.code = 0;
124  dummy_code.length = 65;
125  return dummy_code;
126  } else {
127  return it->second;
128  }
129 }
130 
131 uint64_t
132 Huffman::decode(const uint64_t code) const
133 {
134  // A code that does not exist cannot be decoded
135  auto it = codeToValue.find(code);
136  assert(it != codeToValue.end());
137  return it->second;
138 }
139 
140 } // namespace encoder
141 } // namespace compression
142 } // namespace gem5
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
gem5::X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:775
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::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::Code::code
uint64_t code
Only the LSB of the code are relevant.
Definition: base.hh:49
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
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::Code::length
unsigned length
Number of bits in the code.
Definition: base.hh:51
gem5::compression::encoder::Huffman::Node::getLeftSubTree
const Node * getLeftSubTree() const
Definition: huffman.hh:134
gem5::compression::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(Encoder, encoder)
logging.hh
huffman.hh
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:225
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::compression::encoder::Huffman::generateCodeMaps
void generateCodeMaps()
Generation of the code maps.
Definition: huffman.cc:84
gem5::compression::encoder::Huffman::Node
Node for the Huffman tree.
Definition: huffman.hh:78
gem5::compression::encoder::Huffman::Node::getValue
uint64_t getValue() const
Get the leaf's value.
Definition: huffman.hh:128

Generated on Tue Sep 21 2021 12:25:29 for gem5 by doxygen 1.8.17