C++11 implementation of Huffman-encoding

Question

This is a c++11 implementation of Huffman-encoding that I wrote as a hobby. My main goal in writing it was to get more accustomed to c++11 and STL in general, as well as stuff like bit-manipulation.

Here are the classes bifstream and bofstream (binary ifstream/ofstream). I wrote these so that I could read in/write out a single bit at a time to a file.

bifstream.h

#pragma once

#include <fstream>
#include <vector>

class bifstream
{
public:
    bifstream();
    ~bifstream();

public:
    void open(const char *filePath);
    void close();
    bool good();
    bool eof();
    void clear();
    bool fail();

    bool get();
    std::vector<bool> get(int bytes);
    unsigned char getByte();

private:
    std::ifstream file;
    unsigned char lastByteRead;
    short bitPosition;
};

bifstream.cpp

#include "bifstream.h"
#include <iostream>

bifstream::bifstream()
{
    lastByteRead = 0;
    bitPosition = -1;
}

bifstream::~bifstream()
{
    this->close();
}

void bifstream::open(const char *filePath)
{
    file.open(filePath, std::ios_base::in | std::ios_base::binary);
}

void bifstream::close()
{
    file.close();
}

bool bifstream::good()
{
    return file.good();
}

bool bifstream::eof()
{
    return file.eof();
}

void bifstream::clear()
{
    file.clear();
}

bool bifstream::fail()
{
    return file.fail();
}

bool bifstream::get()
{
    if (bitPosition < 0)
    {
        bool b = file.fail();
        lastByteRead = file.get();
        bitPosition = 7;
    }

    unsigned char shiftedByte = lastByteRead >> bitPosition;
    bitPosition--;
    return (shiftedByte & 0x01) == 1;
}

std::vector<bool> bifstream::get(int bytes)
{
    std::vector<bool> bitset;
    for (int i = 0; i < bytes; i++)
    {
        bitset.push_back(get());
    }

    return bitset;
}

unsigned char bifstream::getByte()
{
    unsigned char c = 0x00;
    for (int i = 0; i < 8; i++)
    {
        if (get())
        {
            c |= (0x80 >> i);
        }
    }

    return c;
}

bofstream.h

#pragma once

#include <fstream>
#include <vector>

class bofstream
{
public:
    bofstream();
    ~bofstream();

public:
    void open(const char *filePath);
    void close();
    bool good();
    bool fail();
    bool eof();
    void clear();

    void put(bool);
    void put(std::vector<bool>);

private:
    void flushBufferToFile();

private:
    std::ofstream file;
    unsigned char buffer;
    short bitPosition;
};

bofstream.cpp

#include "bofstream.h"

bofstream::bofstream()
{
    buffer = 0x00;
    bitPosition = 7;
}

bofstream::~bofstream()
{
    file.close();
}

void bofstream::open(const char *filePath)
{
    file.open(filePath, std::ios_base::out | std::ios_base::binary);
}

void bofstream::close()
{
    if (bitPosition != 7)
        flushBufferToFile();
}

bool bofstream::good()
{
    return file.good();
}

bool bofstream::fail()
{
    return file.fail();
}

bool bofstream::eof()
{
    return file.eof();
}

void bofstream::clear()
{
    file.clear();
}

void bofstream::flushBufferToFile()
{
    file.put(buffer);
    buffer = 0x00;
    bitPosition = 7;
}

void bofstream::put(bool bit)
{
    buffer |= (bit << bitPosition);
    bitPosition--;
    if (bitPosition < 0)
        flushBufferToFile();
}

void bofstream::put(std::vector<bool> bitset)
{
    for (auto i = bitset.begin(); i != bitset.end(); i++)
        put(*i);
}

---

Here is the class Byte. This class just holds an unsigned char and a bool. A decoded message will be a string of bytes, and the last byte will have the bool true to represent that the message is over.

Byte.h

#pragma once

#include <string>

class Byte
{
public:
    Byte(unsigned char c, bool isTerminator = false);
    Byte();
    ~Byte();

    unsigned char getChar() const;
    bool getIsTerminator() const;
    std::string getPrintable() const;
    std::string getHexPrintable() const;

    bool operator == (unsigned char c);

private:
    unsigned char c;
    bool isTerminator;
};

bool operator < (const Byte &lhs, const Byte &rhs);

Byte.cpp

#include "Byte.h"

Byte::Byte(unsigned char c, bool isTerminator)
{
    this->c = c;
    this->isTerminator = isTerminator;
}

Byte::Byte()
{
}

Byte::~Byte()
{
}

unsigned char Byte::getChar() const
{
    return c;

}

bool Byte::getIsTerminator() const
{
    return isTerminator;
}

bool operator < (const Byte &lhs, const Byte &rhs)
{
    if (lhs.getChar() == rhs.getChar())
        return (lhs.getIsTerminator() > rhs.getIsTerminator()); //So that the terminator (0x00, true) is first

    return (lhs.getChar() < rhs.getChar());
}

bool Byte::operator == (unsigned char c)
{
    return (this->c == c);
}

std::string Byte::getPrintable() const
{
    if (c == '\n')
        return "\\n ";
    if (c == '\t')
        return "\\t ";

    std::string s = "   ";
    s[0] = char(c);
    return s;
}

std::string Byte::getHexPrintable() const
{
    char hexOutput[10];
    if (!isTerminator)
        sprintf_s(hexOutput, " (0x%02x):\t", c);
    else
        sprintf_s(hexOutput, " (Term):\t");

    return std::string(hexOutput);
}

---

Here is the struct charCountNode. This class is used in constructing a tree of Bytes, so it holds a byte and 2 pointers to other charCountNodes. It also has count for how many times that byte occurs in the original message, as well as adding two nodes together.

charCountNode.h

#pragma once
#include "Byte.h"

struct CharCountNode
{
    Byte byte;
    int count;

    CharCountNode *left;
    CharCountNode *right;

    CharCountNode(Byte b, int i);
    void print();
};

bool isEmptyNode(CharCountNode node);

bool operator < (const CharCountNode &lhs, const CharCountNode &rhs);
bool operator > (const CharCountNode &lhs, const CharCountNode &rhs);

charCountNode.cpp

#include <iostream>
#include "charCountNode.h"

CharCountNode::CharCountNode(Byte b, int i) : byte(b.getChar(), b.getIsTerminator())
{
    count = i;
    left = nullptr;
    right = nullptr;
}

void CharCountNode::print()
{
    std::cout << "Char:\t" << byte.getPrintable() << "\n";
    std::cout << "Count:\t" << count << "\n";
    std::cout << "Left:\t" << left << "\n";
    std::cout << "Right:\t" << right << "\n";
}

bool operator < (const CharCountNode &lhs, const CharCountNode &rhs)
{
    return (lhs.count < rhs.count);
}

bool operator > (const CharCountNode &lhs, const CharCountNode &rhs)
{
    return (lhs.count > rhs.count);
}

bool isEmptyNode(CharCountNode node)
{
    return (node.count == 0);
}

---

And last but not least, here is main.cpp. This has all of the encoding/logic in it, as well as opening/handling files.

main.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include "bifstream.h"
#include "bofstream.h"
#include "Byte.h"
#include "charCountNode.h"

typedef std::vector<bool> Bitset;
typedef std::map<Byte, Bitset> CharMap;

const bool LEFT = true;
const bool RIGHT = false;

CharMap getCharMap(std::vector<unsigned char> &dataString);
std::vector<CharCountNode> getCharFreqs(std::vector<unsigned char> &dataString);
void traverseTree(CharCountNode *currentNode, CharMap &charMap, Bitset &path);
std::vector<unsigned char> getString(std::string inputFilePath, bool &worked);

bool writeKeyToFile(bofstream &outputFile, CharMap &map);
bool writeHumanReadableKeyToFile(std::ofstream &outputFile, CharMap &map);
bool writeMessageToFile(std::vector<unsigned char> &dataString, bofstream &outputFile, CharMap &map);

void printBitset(Bitset bits);
Bitset charToBitset(char c);

CharMap readKeyFromFile(bifstream &input);
std::string readMessageFromFile(bifstream &input, CharMap &charMap);

void writeKeyAndMessage();
void decodeMessage();

int main()
{
    writeKeyAndMessage();
    decodeMessage();
}

void writeKeyAndMessage()
{
    bool worked;
    std::string originalTextPath = "Huffman\\original.txt";
    std::vector<unsigned char> dataString = getString(originalTextPath, worked);

    if (!worked)
    {
        std::cout << "Failed opening the file at '" << originalTextPath.c_str() << "'. Aborting\n";
        return;
    }

    CharMap map = getCharMap(dataString);

    bofstream keyOutput;
    std::string keyOutputPath = "Huffman\\keyOutput.key";
    keyOutput.open(keyOutputPath.c_str());
    if (keyOutput.fail())
    {
        std::cout << "Failed opening the file at '" << keyOutputPath.c_str() << "'. Aborting\n";
        return;
    }

    writeKeyToFile(keyOutput, map);

    bofstream messageOutput;
    std::string messageOutputPath = "Huffman\\messageOutput.huff";
    messageOutput.open(messageOutputPath.c_str());
    if (messageOutput.fail())
    {
        std::cout << "Failed opening the file at '" << messageOutputPath.c_str() << "'. Aborting\n";
        return;
    }

    std::ofstream humanReadableOutput;
    std::string humanReadableOutputPath = "Huffman\\humanReadableKey.txt";
    humanReadableOutput.open(humanReadableOutputPath.c_str());
    if (humanReadableOutput.fail())
    {
        std::cout << "Failed opening the file at '" << humanReadableOutputPath.c_str() << "'. Aborting\n";
        return;
    }

    writeHumanReadableKeyToFile(humanReadableOutput, map);
    writeMessageToFile(dataString, messageOutput, map);

    keyOutput.close();
    messageOutput.close();
}

void decodeMessage()
{
    bifstream keyInput;
    std::string keyInputPath = "Huffman\\keyOutput.key";
    keyInput.open(keyInputPath.c_str());
    if (keyInput.fail())
    {
        std::cout << "Failed opening the file at '" << keyInputPath.c_str() << "'. Aborting\n";
        return;
    }

    CharMap mapFromFile = readKeyFromFile(keyInput);

    bifstream messageInput;
    std::string messageInputPath = "Huffman\\messageOutput.huff";
    messageInput.open(keyInputPath.c_str());
    if (messageInput.fail())
    {
        std::cout << "Failed opening the file at '" << messageInputPath.c_str() << "'. Aborting\n";
        return;
    }

    std::string message = readMessageFromFile(messageInput, mapFromFile);

    std::ofstream outputOriginal;
    std::string outputOriginalPath = "Huffman\\decodedMessage.txt";
    outputOriginal.open(outputOriginalPath.c_str());
    if (outputOriginal.fail())
    {
        std::cout << "Failed opening the file at '" << outputOriginalPath.c_str() << "'. Aborting";
        return;
    }

    outputOriginal << message.c_str();

    std::ofstream humanReadableOutput;
    std::string humanReadableOutputPath = "Huffman\\humanReadableKeyDecoded.txt";
    humanReadableOutput.open(humanReadableOutputPath.c_str());
    if (humanReadableOutput.fail())
    {
        std::cout << "Failed opening the file at '" << humanReadableOutputPath.c_str() << "'. Aborting\n";
        return;
    }

    writeHumanReadableKeyToFile(humanReadableOutput, mapFromFile);

    outputOriginal.close();
    keyInput.close();
    messageInput.close();
}

std::string readMessageFromFile(bifstream &NOTinput, CharMap &charMap)
{
    //Construct a map of <Bitset, Byte> rather than <Byte, Bitset>
    std::map<Bitset, Byte> bitMap;
    for (auto iter = charMap.begin(); iter != charMap.end(); iter++)
        bitMap[iter->second] = iter->first;

    std::string result;

    Bitset currentBits;

    bifstream input;
    input.open("Huffman\\messageOutput.huff");
    if (input.fail())
        return "";

    while (!input.eof())
    {
        currentBits.push_back(input.get());
        if (bitMap.find(currentBits) != bitMap.end())
        {
            if (bitMap[currentBits].getIsTerminator())  
                break;

            result += bitMap[currentBits].getChar();
            currentBits = {};
        }
    }

    return result;
}

std::vector<unsigned char> getString(std::string inputFilePath, bool &worked)
{
    std::vector<unsigned char> string;
    std::ifstream inputFile;
    inputFile.open(inputFilePath.c_str(), std::ios::in | std::ios::binary);
    worked = inputFile.good();

    if (worked)
    {
        while (true)
        {
            unsigned char c = inputFile.get();
            if (inputFile.fail())
                break;
            string.push_back(c);
        }
    }

    inputFile.close();
    return string;
}

CharMap readKeyFromFile(bifstream &input)
{
    CharMap map;

    bool firstByte = true;

    while (true)
    {
        unsigned char c = input.getByte();
        Bitset key;
        Bitset nextBitPair = input.get(2);
        while (nextBitPair[0])
        {
            key.push_back(nextBitPair[1]);

            nextBitPair = input.get(2);
            if (input.fail())
                break;
        }

        map.insert(std::pair<Byte, Bitset>(Byte(c, firstByte), key));
        if (nextBitPair[1] == 1)
            break;

        firstByte = false;
    }
    return map;
}

bool writeKeyToFile(bofstream &outputFile, CharMap &map)
{
    for (auto iter = map.begin(); iter != map.end(); iter++)
    {
        unsigned char c = iter->first.getChar();
        Bitset key = iter->second;
        outputFile.put(charToBitset(c));
        for (auto bit: key)
        {
            outputFile.put(true);
            outputFile.put(bit);
        }

        outputFile.put(false);
        if (std::next(iter) == map.end())
            outputFile.put(true);
        else
            outputFile.put(false);
    }

    return true;
}

bool writeHumanReadableKeyToFile(std::ofstream &outputFile, CharMap &map)
{
    auto i = map.find(Byte(0x00, false));
    if (i != map.end())
        int i = 7;

    for (auto iter = map.begin(); iter != map.end(); iter++)
    {
        outputFile << iter->first.getPrintable() << iter->first.getHexPrintable();
        for (auto i: iter->second)
            outputFile << int(i);
        outputFile << "\n";
    }

    return true;
}

bool writeMessageToFile(std::vector<unsigned char> &dataString, bofstream &outputFile, CharMap &map)
{
    for (auto c: dataString)
    {
        outputFile.put(map[c]);
    }

    outputFile.put(map.begin()->second);    //The first value in the map is always the terminator
    outputFile.close();

    return true; 
}

CharMap getCharMap(std::vector<unsigned char> &dataString)
{
    CharMap map;
    std::vector<CharCountNode> freqs = getCharFreqs(dataString);

    freqs.push_back(CharCountNode(Byte(0x00, true), 1));        //The terminator

    if (freqs.size() == 1)      //In case the program is given an empty file. Otherwise, we wouuld get an error dereferencing the top of an empty heap.
    {
        map[freqs[0].byte] = std::vector<bool> {true};
        return map;
    }

    std::priority_queue<CharCountNode, std::vector<CharCountNode>, std::greater<CharCountNode>> heap(freqs.begin(), freqs.end());

    while (heap.size() > 2)
    {
        CharCountNode *left = new CharCountNode(heap.top());
        std::ifstream originalInputFile;
        heap.pop();
        CharCountNode *right = new CharCountNode(heap.top());
        heap.pop();

        CharCountNode newNode(0, right->count + left->count);   //The "char" value (0) is irrelevant since we will traverse through this node without looking at the char.
        newNode.left = left;
        newNode.right = right;

        heap.push(newNode);
    }

    CharCountNode *left = new CharCountNode(heap.top());
    heap.pop();
    CharCountNode *right = new CharCountNode(heap.top());
    heap.pop();

    CharCountNode *head = new CharCountNode(0, right->count + left->count);
    head->left = left;
    head->right = right;

    Bitset path = {};
    traverseTree(head, map, path);

    return map;
}

std::vector<CharCountNode> getCharFreqs(std::vector<unsigned char> &dataString)
{
    std::vector<CharCountNode> freqs;
    for (unsigned int i = 0; i < 256; i++)
        freqs.push_back(CharCountNode((unsigned char) i, 0));

    std::string data = "";

    for (auto byte: dataString)
    {
        freqs[byte].count++;
    }

    freqs.erase(std::remove_if(freqs.begin(), freqs.end(), isEmptyNode), freqs.end());
    return freqs;
}

void traverseTree(CharCountNode *currentNode, CharMap &map, Bitset &path)
{
    if (currentNode->left != nullptr && currentNode->right != nullptr)  //Not to the bottom yet, recurse again.
    {
        path.push_back(LEFT);
        traverseTree(currentNode->left, map, path);
        path.pop_back();

        path.push_back(RIGHT);
        traverseTree(currentNode->right, map, path);
        path.pop_back();
    }

    else    //Hit the buttom, add this value to the map
    {
        auto iter = map.begin();
        map.insert(iter, std::pair<Byte, Bitset>(currentNode->byte, path));
    }

    delete currentNode;
}

void printBitset(Bitset bits)
{
    for (auto i : bits)
        std::cout << (i) ? "1" : "0";
}

Bitset charToBitset(char c)
{
    Bitset bits = {};
    for (int i = 7; i >= 0; i--)
    {
        bits.push_back((c >> i) & 0x01);
    }
    return bits;
}

I'd love to hear any tips/thoughts you have on the code. I'd specifically like to know:

• Am I taking advantage of the c++ STL well, rather than reinventing the wheel?

• Is the code logically easy to follow and easy to understand?

• Is it DRY or are there redundancies?

• Are there any high-level decisions that you would have made differently if you were writing it?

Answer 1

Looks well written overall. Good job. I'll just give a few quick remarks about the code. Compression is not really my field.

• Unnecessary destructors in bofstream and bifstream. They already hold Standard streams that automatically close the underlaying file handles in their own destructors, so you're just replicating work by calling close() explicitly. Once you remove that, you'll end up with empty destructors that should be removed. Let the compiler supply a default when you have no manual cleanup to perform in your classes. Actually, bofstream might need to flushBufferToFile(), so that one might need a destructor after all...

• Mark methods that aren't changing member data with const. E.g.: eof, good, fail, etc. Take a look into what const member functions mean in C++. This is an important thing to use and I see that you are not being consistent with it.

• bofstream::put(std::vector<bool>) is taking the vector parameter by value, thus making its own copy of it just to iterate the array. You don't need that copy if you're just inspecting the collection. Pass by const reference instead:

  void put(const std::vector<bool> & v) { ... }
           ^^^^^                   ^
  

  In general you should pass objects by reference if you're only looking at the object without wanting to store an actual copy of it somewhere. Native types like integers are of course still passed by value, since copying those is free and implemented in the hardware.

• Use range based for loops when you're iterating a standard collection from back-to-back. Instead of this:

  for (auto i = bitset.begin(); i != bitset.end(); i++)
  

  You can do this:

  for (auto b : bitset) {
      // use b
  }
  

• Prefixing member variables or methods with this-> is generally not a good practice. Not only it is unnecessary and verbose, but it can also hide names that shadow each other, which can be a serious problem.

• Byte's default constructor doesn't initialize its member data. Always initialize data to some known value to make your code deterministic.

• Byte's destructor is empty, so should be removed. Same as mentioned in the fist point.

• Why didn't you initialize all members of CharCountNode in the initializer list?

  CharCountNode::CharCountNode(Byte b, int i) : byte(b.getChar(), b.getIsTerminator())
  {
      count = i;
      left = nullptr;
      right = nullptr;
   }
  

• Use std::snprintf over sprintf_s or sprintf. It takes a count parameter to prevent buffer overruns.