How to fix a bug in the Huffman algorithm?

Question

C++ / C#

Hello. I can't figure out what's wrong.

#include <iostream>
#include <fstream>
#include <map>
#include <vector>
using namespace std;

int main()
{
  int weight[0x100];
  for (auto &i : weight)
    i = 0;
  {
    ifstream f("ex.txt");
    while (!f.eof())
    {
      unsigned char ch;
      f.read((char *)&ch, sizeof(ch));
      ++weight[ch];
    }
  }
  multimap<int, int> sortedWeight;
  struct Node
  {
    char ch;
    int parent;
    int zero;
    int one;
    bool branch;
  };
  vector<Node> tree;
  map<char, int> charMap;
  for (size_t i = 0; i < 0x100; ++i)
  {
    if (weight[i] > 0)
    {
      tree.push_back(Node{ (char)i, -1, -1, -1, false });
      charMap[i] = tree.size() - 1;
      sortedWeight.insert(make_pair(weight[i], tree.size() - 1));
    }
  }
  while (sortedWeight.size() > 1)
  {
    int w0 = begin(sortedWeight)->first;
    int n0 = begin(sortedWeight)->second;
    sortedWeight.erase(begin(sortedWeight));
    int w1 = begin(sortedWeight)->first;
    int n1 = begin(sortedWeight)->second;
    sortedWeight.erase(begin(sortedWeight));
    tree.push_back(Node{ '\0', -1, n0, n1, false });
    tree[n0].parent = tree.size() - 1;
    tree[n0].branch = false;
    tree[n1].parent = tree.size() - 1;
    tree[n1].branch = true;
    sortedWeight.insert(make_pair(w0 + w1, tree.size() - 1));
  }
  vector<bool> data;
  {
    ifstream f("ex.txt");
    while (!f.eof())
    {
      unsigned char ch;
      f.read((char *)&ch, sizeof(ch));
      auto n = tree[charMap[ch]];
      vector<bool> compressedChar;
      while (n.parent != -1)
      {
        compressedChar.push_back(n.branch);
        n = tree[n.parent];
      }
      data.insert(end(data), compressedChar.rbegin(), compressedChar.rend());
    }
  }
  ofstream f("ex.huff");
  int treeSize = tree.size();
  f.write((char *)&treeSize, sizeof(treeSize));
  for (auto i : tree)
    f.write((char *)&i, sizeof(i));
  for (size_t i = 0; i <= data.size() / 8; ++i)
  {
    unsigned char ch = 0;
    for (int j = 0; j < 8; ++j)
      if (data[i * 8 + j])
        ch |= (1 << j);
    f.write((char *)&ch, sizeof(ch));
  }
}

output log:

Huffman.exe (Win32). "C:\Users\Ilya\Documents\Visual Studio 2015\Projects\Huffman\Debug\Huffman.exe" loaded. Symbols loaded.
Huffman.exe (Win32). "C:\Windows\SysWOW64\ntdll.dll" was loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\kernel32.dll" was loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\KernelBase.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\msvcp140d.dll" was loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\vcruntime140d.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\advapi32.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\msvcrt.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\sechost.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\rpcrt4.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\sspicli.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\cryptbase.dll" loaded. The .pdb file cannot be found or opened.
"huffman.exe" (Win32). "C:\Windows\SysWOW64\bcryptprimitives.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\ucrtbased.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\kernel.appcore.dll" loaded. The .pdb file cannot be found or opened.
Debug Assertion Failed!
Program: C:\WINDOWS\SYSTEM32\MSVCP140D.dll
File: c:\program files (x86)\microsoft visual studio 14.0\vc\include\vector
Line: 1985
Expression: vector iterator not dereferencable
For information on how your program can cause an assertion
failure, see the Visual C++ documentation on assertions.
(Press Retry to debug the application)
"Huffman.exe" (Win32). "C:\Windows\SysWOW64\user32.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\gdi32.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\imm32.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\msctf.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\uxtheme.dll" loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\combase.dll" was loaded. The .pdb file cannot be found or opened.
Huffman.exe (Win32). "C:\Windows\SysWOW64\dwmapi.dll" loaded. The .pdb file cannot be found or opened.
"huffman.exe" (Win32). "C:\Windows\SysWOW64\ole32.dll" was loaded. The .pdb file cannot be found or opened.
Thread 0x2a4c exited with code 3 (0x3).
Thread 0x2a2c exited with code 3 (0x3).
The program "[4712] Huffman.exe" exited with code 3 (0x3).

Answer 1

for (size_t i = 0; i <= data.size() / 8; ++i)
  {
    ...
    for (int j = 0; j < 8; ++j)
      if (data[i * 8 + j])
    ...
  }

Got out of the border data. If I understood the logic correctly, then there should be something like this:

for (size_t i = 0; i < (data.size() + 7) / 8; ++i)
  {
    ...
    for (int j = 0; j < std::min(8, data.size() - i * 8); ++j)
      if (data[i * 8 + j])
    ...
  }

Answer 2

How to fix a bug in the Huffman algorithm?

Just do not call the topic "How to fix a mistake in the Huffman algorithm?".
It's better to call it something more neutral ... like: "How to fix a mistake in my eccentricities?".

Answer 3

Press the "Abort" button, watch the call stack and dive into the interesting world of debugging.