huffman.cc

Go to the documentation of this file.

/*
 * Copyright (c) 2019, 2020 Inria
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
#include "mem/cache/compressors/encoders/huffman.hh"
 
#include <cassert>
 
#include "base/logging.hh"
 
namespace Compressor {
namespace Encoder {
 
Huffman::Huffman(uint64_t max_code_length)
  : Base(), maxCodeLength(max_code_length)
{
    fatal_if(maxCodeLength > 64,
        "Code length cannot surpass its underlying container");
}
 
void
Huffman::sample(uint64_t value, uint64_t frequency)
{
    if (frequency != 0) {
        trees.push(new Node(value, frequency));
    }
}
 
std::unique_ptr<Huffman::Node>
Huffman::buildTree()
{
    // Construct tree by assigning left and right nodes. The left path leads
    // to the most frequent values
    while (trees.size() > 1) {
        Node* left = trees.top();
        trees.pop();
 
        Node* right = trees.top();
        trees.pop();
 
        Node* parent = new Node(left, right);
        trees.push(parent);
    }
 
    // All queue entries have been merged into a single entry containing
    // the tree
    Node* root = trees.top();
    trees.pop();
    return std::unique_ptr<Node>(root);
}
 
void
Huffman::generateCodeMaps()
{
    valueToCode.clear();
    codeToValue.clear();
    generateCodes(buildTree().get(), Code());
}
 
void
Huffman::generateCodes(const Node* node, const Code& current_code)
{
    // Drop all entries with length greater than maxCodeLength
    if (current_code.length > maxCodeLength) {
        return;
    }
 
    if (node->isLeaf()) {
        valueToCode[node->getValue()] = current_code;
        codeToValue[current_code.code] = node->getValue();
    } else {
        Code right_code = current_code;
        right_code.code = (right_code.code << 1) + 1;
        right_code.length++;
        generateCodes(node->getRightSubTree(), right_code);
 
        Code left_code = current_code;
        left_code.code = left_code.code << 1;
        left_code.length++;
        generateCodes(node->getLeftSubTree(), left_code);
    }
}
 
Code
Huffman::encode(const uint64_t val) const
{
    auto it = valueToCode.find(val);
    if (it == valueToCode.end()) {
        // If the value is unknown, generate a dummy code with invalid
        // length to let the caller know the encoding is invalid
        Code dummy_code;
        dummy_code.code = 0;
        dummy_code.length = 65;
        return dummy_code;
    } else {
        return it->second;
    }
}
 
uint64_t
Huffman::decode(const uint64_t code) const
{
    // A code that does not exist cannot be decoded
    auto it = codeToValue.find(code);
    assert(it != codeToValue.end());
    return it->second;
}
 
} // namespace Encoder
} // namespace Compressor