LZ77 compressor and decompressor in C++

Question

I've written working LZ77 algorithm implementation which uses linked lists (they help to look for matching substrings faster). I'd like to get some feedback on my code's quality and also information about mistakes and dubious places in my program (if I have any).

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

unsigned int max_buf_length=0;
unsigned int max_dict_length=0;
unsigned int cur_dict_length=0;
unsigned int cur_buf_length=0;

struct link {
    unsigned short length;
    unsigned short offset;
    unsigned char next;
};

struct Node
{
    Node* prev;
    unsigned int index;
};

class LinkedList
{
    public: Node* lastNode;

    LinkedList()
    {
        lastNode=nullptr;
    }

    ~LinkedList()
    {
        Node* temp;
        while(lastNode!=nullptr)
        {
            temp=lastNode;
            lastNode = lastNode->prev;
            delete temp;
        }
    }

    void PushBack(unsigned int val)
    {
        Node* myNode = new Node;
        myNode->index=val;
        myNode->prev=lastNode;
        lastNode=myNode;
    }
};

unsigned int readFile(unsigned char* &raw, fstream &inp)
{
    inp.seekg(0, ios::beg);
    unsigned int file_start = inp.tellg();
    inp.seekg(0, ios::end);
    unsigned int file_end = inp.tellg();
    unsigned int file_size = file_end - file_start;
    inp.seekg(0, ios::beg);
    raw = new unsigned char[file_size];
    inp.read((char*)raw, file_size);
    return file_size;
}

void FindLongestMatch(unsigned char* s, unsigned int buf_start, unsigned short &len, unsigned short &off, LinkedList dict[])
{
    Node* current = dict[s[buf_start]].lastNode;
    unsigned int max_offset = buf_start - cur_dict_length;
    unsigned int j = 0;
    unsigned int k = 0;
    if(current!=nullptr && (current->index)>=max_offset) { len=1; off=buf_start-(current->index); }
    while(current!=nullptr && (current->index)>=max_offset)
    {
       j=1;
       k=1;
       while(k<cur_buf_length && s[(current->index)+j]==s[buf_start+k])
       {
            if((current->index)+j==buf_start-1) { j=0; }
            else j++;
            k++;
       }
       if(k>len)
       {
            len = k;
            off = buf_start-(current->index);
            if(len==cur_buf_length) break;
       }
       else
       {
            current=current->prev;
       }
    }
}

int UpdateDictionary(unsigned char* s, unsigned int shift_start, unsigned short Length, LinkedList dict[])
{
    for(unsigned int i=shift_start; i<(shift_start+Length+1); i++)
    {
         dict[s[i]].PushBack(i);
    }
    return Length;
}

void compactAndWriteLink(link inp, vector<unsigned char> &out)
{
        if(inp.length!=0)
        {
            out.push_back((unsigned char)((inp.length << 4) | (inp.offset >> 8)));
            out.push_back((unsigned char)(inp.offset));
        }
        else
        {
            out.push_back((unsigned char)((inp.length << 4)));
        }
        out.push_back(inp.next);
}

void compressData(unsigned int file_size, unsigned char* data, fstream &file_out)
{
    LinkedList dict[256];
    link myLink;
    vector<unsigned char> lz77_coded;
    lz77_coded.reserve(2*file_size);
    bool hasOddSymbol=false;
    unsigned int target_size = 0;
    file_out.seekp(0, ios_base::beg);
    cur_dict_length = 0;
    cur_buf_length = max_buf_length;
    for(unsigned int i=0; i<file_size; i++)
    {
        if((i+max_buf_length)>=file_size)
        {
            cur_buf_length = file_size-i;
        }
        myLink.length=0;myLink.offset=0;
        FindLongestMatch(data,i,myLink.length,myLink.offset, dict);
        i=i+UpdateDictionary(data, i, myLink.length, dict);
        if(i<file_size) {
            myLink.next=data[i]; }
            else { myLink.next='_'; hasOddSymbol=true; }
        compactAndWriteLink(myLink, lz77_coded);
        if(cur_dict_length<max_dict_length) {
        while((cur_dict_length < max_dict_length) && cur_dict_length < (i+1)) cur_dict_length++;
        }
   }
   if(hasOddSymbol==true) { lz77_coded.push_back((unsigned char)0x1); }
   else lz77_coded.push_back((unsigned char)0x0);
   target_size=lz77_coded.size();
   file_out.write((char*)lz77_coded.data(), target_size);
   lz77_coded.clear();
   printf("Output file size: %d bytes\n", target_size);
   printf("Compression ratio: %.3Lf:1\n", ((double)file_size/(double)target_size));
}

void uncompressData(unsigned int file_size, unsigned char* data, fstream &file_out)
{
    if(file_size==0) { printf("Error! Input file is empty\n"); return; }
    link myLink;
    vector<unsigned char> lz77_decoded;
    lz77_decoded.reserve(4*file_size);
    unsigned int target_size = 0;
    unsigned int i=0;
    int k=0;
    file_out.seekg(0, ios::beg);
    while(i<(file_size-1))
    {
        if(i!=0) { lz77_decoded.push_back(myLink.next); }
        myLink.length = (unsigned short)(data[i] >> 4);
        if(myLink.length!=0)
        {
            myLink.offset = (unsigned short)(data[i] & 0xF);
            myLink.offset = myLink.offset << 8;
            myLink.offset = myLink.offset | (unsigned short)data[i+1];
            myLink.next = (unsigned char)data[i+2];
            if(myLink.offset>lz77_decoded.size()) {
             printf("Error! Offset is out of range!");
             lz77_decoded.clear();
             return;
             }
            if(myLink.length>myLink.offset)
            {
            k = myLink.length;
            while(k>0)
            {
                if(k>=myLink.offset)
                {
                lz77_decoded.insert(lz77_decoded.end(), lz77_decoded.end()-myLink.offset, lz77_decoded.end());
                k=k-myLink.offset;
                }
                else
                {
                lz77_decoded.insert(lz77_decoded.end(), lz77_decoded.end()-myLink.offset, lz77_decoded.end()-myLink.offset+k);
                k=0;
                }
            }
            }
            else lz77_decoded.insert(lz77_decoded.end(), lz77_decoded.end()-myLink.offset, lz77_decoded.end()-myLink.offset+myLink.length);
            i++;
        }
        else {
            myLink.offset = 0;
            myLink.next = (unsigned char)data[i+1];
        }
        i=i+2;
    }
    unsigned char hasOddSymbol = data[file_size-1];
    if(hasOddSymbol==0x0 && file_size>1) { lz77_decoded.push_back(myLink.next); }
    target_size = lz77_decoded.size();
    file_out.write((char*)lz77_decoded.data(), target_size);
    lz77_decoded.clear();
    printf("Output file size: %d bytes\n", target_size);
    printf("Unpacking finished!");
}

int main(int argc, char* argv[])
{
    max_buf_length=15; //16-1;
    max_dict_length=4095; //4096-1
    string filename_in ="";
    string filename_out="";
    fstream file_in;
    fstream file_out;
    unsigned int raw_size = 0;
    unsigned char* raw = nullptr;
    int mode = 0;
    printf("Simple LZ77 compression/decompression program\n");
    printf("Coded by MVoloshin, TSU, 2020\n");
    if(argc==4) {
        if(strcmp(argv[1], "-u")==0) mode = 0;
        else if(strcmp(argv[1], "-c")==0) mode = 1;
        else { printf("Unknown parameter, use -c or -u\n"); return 0; }
        filename_in=std::string(argv[2]);
        filename_out=std::string(argv[3]);
    }
    else
    {
        printf("Usage: [-c | -u] [input_file] [output_file]\n");
        return 0;
    }
    file_in.open(filename_in, ios::in | ios::binary);
    file_in.unsetf(ios_base::skipws);
    file_out.open(filename_out, ios::out);
    file_out.close();
    file_out.open(filename_out, ios::in | ios::out | ios::binary);
    file_out.unsetf(ios_base::skipws);
   if(file_in && file_out) {
   raw_size=readFile(raw, file_in);
   printf("Input file size: %d bytes\n", raw_size);
   }
   else
   {
        if(!file_in) printf("Error! Couldn't open input file!\n");
        if(!file_out) printf("Error! Couldn't open output file!\n");
        mode = -1;
   }
   file_in.close();
   if(mode==0)
   {
        uncompressData(raw_size, raw, file_out);
   }
   else if(mode==1)
   {
        compressData(raw_size, raw, file_out);
   }
   if(raw!=nullptr) delete[] raw;
   file_out.close();
    return 0;
}

Answer 1

welcome to code review! I have multiple remarks to your code and I try to build little chapters for each below. My impression is, that you already have programming experience in C and you're now trying to move to C++. While most C code can be compiled by a C++ compiler, the languages are somewhat different and everything that is idiomatic to C is very likely different in C++ ;-) That being said, here are my remarks, if you have a question on anything, please ask and I'll elaborate:

---

using namespace std;

Don't do this, this is considered a very bad habit and in fact, no professional C++-developer I've seen so far writes this. This will add all identifiers from the std namespace to your scope and will prevent you from simply using those names otherwise. You should also use the full qualified names of the type, eg. std::fstream instead of fstream.

---

If you define a variable to be a reference or a pointer, stick the asterisk or the ampersand to the type, not the variable's identifier. So instead of writing

, unsigned short &len,

write

, unsigned short& len,

This is a difference to plain C, where the asterisk is written next to the identifier.

---

In C++, use std::cout to write to stdout. Also, errors should be printed to stderr which is std::cerr:

std::cout << "Output file size: " << target_size << " bytes\n";

if(file_size==0) { 
    std::cerr << "Error! Input file is empty\n");
    return;
}

---

When passing a structure to a function, pass it by reference. That way you save C++ from copying the structure's content. If you don't modify the structure's content, pass it by const reference:

int UpdateDictionary(unsigned char* s, unsigned int shift_start, unsigned short Length, std::list<unsigned>& dict);

void compactAndWriteLink(const link& inp, vector<unsigned char> &out);

---

You're writing your own linked list, but I recommend using std::list instead. C++ standard library offers lots of containers for several use cases and it's always easier to use one of those while also producing more readable code. If you're interested in writing a linked list, I suggest doing this in a project my own linked list that way you don't get distracted with that LZZ stuff ;-)

I'd even go a bit further and suggest that you create a dictionary class:

class dictionary
{
public:
    unsigned short update(unsigned char* s, unsigned int shift_start, unsigned short length);
    void longest_match(unsigned char* s, unsigned int buf_start, unsigned short& len, unsigned short& off);

private:
    std::list<unsigned int> dict[256]; // or even better, use std::array<std::list<unsigned int>, 256>
};

---

You don't need to include <cstring>.

---

As a hint: you should not use new. There's almost always a better way. For your linked list, I already pointed you to std::list, for the buffer returned from readFile, you could pass a vector to the function and use it to store the buffer:

unsigned int readFile(std::vector<char>& buffer, std::fstream& inp)
{
    inp.seekg(0, ios::beg);
    unsigned int file_start = inp.tellg();
    inp.seekg(0, ios::end);
    unsigned int file_end = inp.tellg();
    unsigned int file_size = file_end - file_start;
    inp.seekg(0, ios::beg);

    buffer.reserve(file_size);
    inp.read(&buffer[0], file_size);
    return file_size;
}

Note: there are better and more compact ways to read a file: https://stackoverflow.com/questions/2602013/read-whole-ascii-file-into-c-stdstring

---

Instead of passing around unsigned char* data and unsigned int filesize use an std::vector<unsigned char> and pass it by reference. If you want to stick to pointer and size, make the pointer the first parameter.

---

In compressData and uncompressData you don't need a vector to buffer the data. As you're only appending to it, you can simply write to the stream. I'd also rather use a generic stream, that way it's easier to control from the outside whether you want to write to a file or a buffer.

---

If I compile your code with g++ -Wall lzz.cc -o lzz (gcc 8.3.0) I receive following warning:

lzz.cc: In function ‘void compressData(unsigned int, unsigned char*, std::fstream&)’:
lzz.cc:154:11: warning: format ‘%Lf’ expects argument of type ‘long double’, but argument 2 has type ‘double’ [-Wformat=]
    printf("Compression ratio: %.3Lf:1\n", ((double)file_size/(double)target_size));

This might be to me using a newer compiler, but in any case, always try to compile with -Wall to see if there are any warnings and fix those.

---