Compresor y descompresor LZ77 en C++
He escrito una implementación del algoritmo LZ77 funcional que usa listas enlazadas (ayudan a buscar subcadenas coincidentes más rápido). Me gustaría recibir comentarios sobre la calidad de mi código y también información sobre errores y lugares dudosos en mi programa (si tengo alguno).
#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;
}
Respuestas
¡Bienvenido a la revisión del código! Tengo varios comentarios a su código y trato de construir pequeños capítulos para cada uno a continuación. Mi impresión es que ya tiene experiencia en programación en C y ahora está tratando de pasarse a C++. Si bien la mayoría del código C puede ser compilado por un compilador de C++, los lenguajes son algo diferentes y todo lo que es idiomático para C es muy probable que sea diferente en C++ ;-) Dicho esto, aquí están mis comentarios, si tiene alguna pregunta sobre algo, por favor pregunte y voy a elaborar:
using namespace std;
No hagas esto, se considera un hábito muy malo y, de hecho, ningún desarrollador profesional de C++ que haya visto hasta ahora escribe esto. Esto agregará todos los identificadores del stdespacio de nombres a su alcance y evitará que simplemente use esos nombres de otra manera. También debe usar los nombres calificados completos del tipo, por ejemplo. std::fstreamen lugar fstreamde
Si define una variable para que sea una referencia o un puntero, pegue el asterisco o el ampersand al tipo, no al identificador de la variable. Así que en lugar de escribir
, unsigned short &len,
escribe
, unsigned short& len,
Esta es una diferencia con la C simple, donde el asterisco se escribe al lado del identificador.
En C++, use std::coutpara escribir en stdout . Además, los errores deben imprimirse en stderr , que es std::cerr:
std::cout << "Output file size: " << target_size << " bytes\n";
if(file_size==0) {
std::cerr << "Error! Input file is empty\n");
return;
}
Al pasar una estructura a una función, pásela por referencia. De esa manera evita que C++ copie el contenido de la estructura. Si no modifica el contenido de la estructura, páselo por constreferencia:
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);
Estás escribiendo tu propia lista enlazada, pero recomiendo usarla std::listen su lugar. La biblioteca estándar de C++ ofrece muchos contenedores para varios casos de uso y siempre es más fácil usar uno de esos mientras se produce un código más legible. Si está interesado en escribir una lista enlazada, le sugiero que haga esto en un proyecto, mi propia lista enlazada, de esa manera no se distraerá con esas cosas de LZZ ;-)
Incluso iría un poco más allá y sugeriría que cree una clase de diccionario :
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>
};
No es necesario incluir <cstring>.
Como pista: no debes usar new. Casi siempre hay una mejor manera. Para su lista vinculada, ya le señalé std::list, para el búfer devuelto readFile, podría pasar un vector a la función y usarlo para almacenar el búfer:
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: hay formas mejores y más compactas de leer un archivo:https://stackoverflow.com/questions/2602013/read-whole-ascii-file-into-c-stdstring
En lugar de pasar unsigned char* datay unsigned int filesizeusar un std::vector<unsigned char>y pasarlo por referencia. Si desea ceñirse al puntero y el tamaño, haga que el puntero sea el primer parámetro.
In compressDatay uncompressDatano necesita un vectorpara almacenar en búfer los datos. Como solo lo está agregando, simplemente puede escribir en la transmisión. También prefiero usar una secuencia genérica, de esa manera es más fácil controlar desde el exterior si desea escribir en un archivo o en un búfer.
Si compilo su código con g++ -Wall lzz.cc -o lzz(gcc 8.3.0) recibo la siguiente advertencia:
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));
Esto podría ser para mí usando un compilador más nuevo, pero en cualquier caso, siempre intente compilar -Wallpara ver si hay advertencias y corregirlas.