Compressor e descompactador LZ77 em C++

Question

Eu escrevi a implementação do algoritmo LZ77 que usa listas vinculadas (elas ajudam a procurar substrings correspondentes mais rapidamente). Gostaria de obter algum feedback sobre a qualidade do meu código e também informações sobre erros e lugares duvidosos em meu programa (se houver).

#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

bem-vindo à revisão do código! Tenho várias observações em seu código e tento criar pequenos capítulos para cada uma abaixo. Minha impressão é que você já tem experiência em programação em C e agora está tentando mudar para C++. Embora a maior parte do código C possa ser compilado por um compilador C++, as linguagens são um pouco diferentes e tudo o que é idiomático para C é muito provavelmente diferente em C++ ;-) Dito isso, aqui estão minhas observações, se você tiver alguma dúvida, por favor, pergunte e eu vou elaborar:

---

using namespace std;

Não faça isso, isso é considerado um hábito muito ruim e, de fato, nenhum desenvolvedor C++ profissional que eu vi até agora escreve isso. Isso adicionará todos os identificadores do stdnamespace ao seu escopo e impedirá que você simplesmente use esses nomes de outra forma. Você também deve usar os nomes qualificados completos do tipo, por exemplo. std::fstreamem vez de fstream.

---

Se você definir uma variável para ser uma referência ou um ponteiro, coloque o asterisco ou o e comercial no tipo, não no identificador da variável. Então ao invés de escrever

, unsigned short &len,

Escreva

, unsigned short& len,

Esta é uma diferença para C simples, onde o asterisco é escrito ao lado do identificador.

---

Em C++, use std::coutpara gravar em stdout . Além disso, os erros devem ser impressos no stderr , que é std::cerr:

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

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

---

Ao passar uma estrutura para uma função, passe-a por referência. Dessa forma, você evita que o C++ copie o conteúdo da estrutura. Se você não modificar o conteúdo da estrutura, passe por constreferência:

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);

---

Você está escrevendo sua própria lista encadeada, mas recomendo usar std::listem seu lugar. A biblioteca padrão C++ oferece muitos contêineres para vários casos de uso e é sempre mais fácil usar um deles, ao mesmo tempo em que produz um código mais legível. Se você estiver interessado em escrever uma lista encadeada, sugiro fazer isso em um projeto minha própria lista encadeada para não se distrair com essas coisas de LZZ ;-)

Eu iria um pouco mais longe e sugeriria que você criasse uma classe de dicionário :

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>
};

---

Você não precisa incluir <cstring>.

---

Como dica: você não deve usar new. Há quase sempre uma maneira melhor. Para sua lista encadeada, já indiquei std::list, para o buffer retornado de readFile, você pode passar um vetor para a função e usá-lo para armazenar o 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;
}

Nota: existem maneiras melhores e mais compactas de ler um arquivo:https://stackoverflow.com/questions/2602013/read-whole-ascii-file-into-c-stdstring

---

Em vez de passar unsigned char* datae unsigned int filesizeusar um std::vector<unsigned char>e passá-lo por referência. Se você quiser manter o ponteiro e o tamanho, torne o ponteiro o primeiro parâmetro.

---

Em compressDatae uncompressDatavocê não precisa de um vectorbuffer para os dados. Como você está apenas anexando a ele, basta escrever no fluxo. Também prefiro usar um fluxo genérico, assim é mais fácil controlar de fora se você deseja gravar em um arquivo ou em um buffer.

---

Se eu compilar seu código com g++ -Wall lzz.cc -o lzz(gcc 8.3.0), recebo o seguinte aviso:

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));

Isso pode ser para mim usando um compilador mais novo, mas em qualquer caso, sempre tente compilar -Wallpara ver se há algum aviso e corrija-o.

---