Compressore e decompressore LZ77 in C++
Ho scritto un'implementazione funzionante dell'algoritmo LZ77 che utilizza elenchi collegati (aiutano a cercare le sottostringhe corrispondenti più velocemente). Vorrei ricevere un feedback sulla qualità del mio codice e anche informazioni su errori e punti dubbi nel mio programma (se ne ho).
#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;
}
Risposte
benvenuto alla revisione del codice! Ho più osservazioni sul tuo codice e cerco di costruire piccoli capitoli per ciascuno di seguito. La mia impressione è che tu abbia già esperienza di programmazione in C e ora stai provando a passare a C++. Mentre la maggior parte del codice C può essere compilato da un compilatore C++, i linguaggi sono in qualche modo diversi e tutto ciò che è idiomatico in C è molto probabilmente diverso in C++ ;-) Detto questo, ecco le mie osservazioni, se hai una domanda su qualcosa, chiedi pure e approfondisco:
using namespace std;
Non farlo, questa è considerata una pessima abitudine e in effetti nessuno sviluppatore C++ professionista che ho visto finora lo scrive. Ciò aggiungerà tutti gli identificatori dallo spazio dei stdnomi al tuo ambito e ti impedirà di utilizzare semplicemente quei nomi altrimenti. Dovresti anche usare i nomi completi completi del tipo, ad es. std::fstreaminvece di fstream.
Se definisci una variabile come riferimento o puntatore, attacca l'asterisco o la e commerciale al tipo, non all'identificatore della variabile. Quindi, invece di scrivere
, unsigned short &len,
scrivere
, unsigned short& len,
Questa è una differenza rispetto al semplice C, dove l'asterisco è scritto accanto all'identificatore.
In C++, usa std::coutper scrivere su stdout . Inoltre, gli errori dovrebbero essere stampati su stderr che è std::cerr:
std::cout << "Output file size: " << target_size << " bytes\n";
if(file_size==0) {
std::cerr << "Error! Input file is empty\n");
return;
}
Quando passi una struttura a una funzione, passala per riferimento. In questo modo risparmi C++ dalla copia del contenuto della struttura. Se non modifichi il contenuto della struttura, passalo per constriferimento:
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);
Stai scrivendo il tuo elenco di collegamenti, ma ti consiglio di utilizzare std::listinvece. La libreria standard C++ offre molti contenitori per diversi casi d'uso ed è sempre più facile usarne uno producendo anche codice più leggibile. Se sei interessato a scrivere un elenco collegato, ti suggerisco di farlo in un progetto il mio elenco collegato in modo da non farti distrarre da quella roba LZZ ;-)
Andrei anche un po' oltre e suggerirei di creare una classe di dizionario :
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>
};
Non è necessario includere <cstring>.
Come suggerimento: non dovresti usare new. C'è quasi sempre un modo migliore. Per il tuo elenco collegato, ti ho già indicato std::list, per il buffer restituito da readFile, potresti passare un vettore alla funzione e usarlo per memorizzare il 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: ci sono modi migliori e più compatti per leggere un file:https://stackoverflow.com/questions/2602013/read-whole-ascii-file-into-c-stdstring
Invece di passare in giro unsigned char* datae unsigned int filesizeusare an std::vector<unsigned char>e passarlo per riferimento. Se vuoi attenersi al puntatore e alla dimensione, imposta il puntatore come primo parametro.
In compressDatae uncompressDatanon hai bisogno di un vectorbuffer per i dati. Dato che stai solo aggiungendo ad esso, puoi semplicemente scrivere nello stream. Preferirei anche usare un flusso generico, in questo modo è più facile controllare dall'esterno se vuoi scrivere su un file o su un buffer.
Se compilo il tuo codice con g++ -Wall lzz.cc -o lzz(gcc 8.3.0) ricevo il seguente avviso:
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));
Questo potrebbe essere per me usando un compilatore più recente, ma in ogni caso, prova sempre a compilare con -Wallper vedere se ci sono avvisi e correggerli.