Compression lz77 sous linux (ou windows)

Soyez le premier à donner votre avis sur cette source.

Vue 6 619 fois - Téléchargée 236 fois

Description

Voici ma première réalisation sous linux (facilement adaptable pour WINDOWS),
elle est inachevée et buggée (ca ne plante pas pour autant),
mais l'organisation générale des fonctions pourra inspirer
des débutants (comme moi).
Même certaines fonctions pourront etre réutilisées car pratique.

ATTENTION : la décompression n'est pas implémentée!

Il s'agit donc d'un compresseur utilisant l'algorithme LZ77
plutot efficace, mais soyez patient!!!
G testé sur un fichier de 1.5Mo facilement compressible:
-avec un dictionnaire de 4ko il faut 45secondes (option -1) pour un résultat de 260ko
-un dico de 64ko -> 5mn!!! (option -5) pour 170ko
-un dico de 1Mo -> 17mn!! (option-9) pour 96ko

En concurrence, Winrar 3.0 bien réglé :
176ko mais en 1 secondes....... :-(

Bref, il reste du chemin!!

Dans le zip il y a:
comp.c (et const.h)-> les sources (écrites avec Emacs)
comp -> l'éxécutable
makefile -> automate de compilation

Pour le compiler, il suffit de taper dans une console : 'make'
tout en étant dans le répertoir contenant les fichiers, si cela ne fonctionne pas
taper : 'gcc comp.c -o comp'
mais de toute facon, il y a l'éxécutable.

Si vous avez des remarques, questions ou conseils, n'hésitez pas!

Je mettrai à jour les sources au fil des évolutions.

Source / Exemple :


// Les librairies du compilateur
#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

// Mes librairies
#include "const.h"

// Variables Globales
int Error;
long Size_Scan;
int Bits_Scan;

// Structure
struct red
{
  long Pos;  // Position dans le dictionnaire du début de la suite de données redondante
  unsigned long Size;  // Taille de la suite de données redondante
};

// Déclaration de mes fonctions
void HelpMessage(void);
void DoError(int nError);

void Main_Compress(char* File_Name);

char* Compress(char* BufferIn, long SizeIn, long* SizeOut);

long ReadFile(int File_Handle, char* Buffer, long Size);
long WriteFile(int File_Handle, char* Buffer, long Size);
void InitBufferOut(int File_Handle, unsigned long* Buffer);
unsigned long CheckSum(char* Begin, char* End, unsigned long Checksum);
long WriteBufferOut(struct red Data, char* Buffer);
struct red Redondance(char* Buffer, char* Window, char* End_Window);
//struct red ExtractData(char** Pos_Buffer, int* N_Bit);
unsigned long ReadBits(int Nb_Bits, unsigned long* pValue, int N_Bit);
void WriteBits(unsigned long Value, int Nb_Bits, unsigned long* pOctet, int N_Bit);
long pow(long A, long B);
long min(long A, long B);
long max(long A, long B);
char* minc(char* A, char* B);
char* maxc(char* A, char* B);
void DispTime(time_t Sec);
void AddBits(char** Adr, int* Bit, int N_Bits);

int main(int argc, char* argv[])
{
  extern int Error;
  extern long Size_Scan;
  extern int Bits_Scan;
  int i = 0;
  time_t Time_Begin;
  time_t Time_End;
  char* lst_opt = "1:2:3:4:5:6:7:8:9:u:h";

  time(&Time_Begin);

  Error = 0;

  opterr = 0;

  switch(getopt(argc, argv, lst_opt)){

  case '1':
    Size_Scan = 4096;
    Bits_Scan = 12;
    Main_Compress(optarg);
    break;

  case '2':
    Size_Scan = 8192;
    Bits_Scan = 13;
    Main_Compress(optarg);
    break;

  case '3':
    Size_Scan = 16384;
    Bits_Scan = 14;
    Main_Compress(optarg);
    break;

  case '4':
    Size_Scan = 32768;
    Bits_Scan = 15;
    Main_Compress(optarg);
    break;

  case '5':
    Size_Scan = 65536;
    Bits_Scan = 16;
    Main_Compress(optarg);
    break;

  case '6':
    Size_Scan = 131072;
    Bits_Scan = 17;
    Main_Compress(optarg);
    break;

  case '7':
    Size_Scan = 262144;
    Bits_Scan = 18;
    Main_Compress(optarg);
    break;

  case '8':
    Size_Scan = 524288;
    Bits_Scan = 19;
    Main_Compress(optarg);
    break;

  case '9':
    Size_Scan = 1048576;
    Bits_Scan = 20;
    Main_Compress(optarg);
    break;

  case 'u':
    fprintf(stdout, "Non implémentée!!!\n");
    /*
    fprintf(stdout, "Décompression...\n");
    Main_UnCompress(optarg);*/
    break;

  case 'h':
    HelpMessage();
    break;

  default :
    DoError(ERR_ARGS);
  }

  time(&Time_End);

  DispTime(Time_End - Time_Begin);

  return 0;
}

void DoError(int nError)
{
  char* LstError[] = {"Erreur de Syntaxe : comp [-123456789uh] [fichier]",
		      "Erreur fonction ReadBits() : Nb_Bits > 24",
		      "Erreur fonction WriteBits() : Nb_Bits > 24"
		      "Erreur fonction WriteBits() : Value > ((2^nb_bits) - 1)",
		      "Erreur fonction WriteBits() : N_Bit > 7",
		      "Erreur fonction ReadBits() : N_Bit > 7",
		      "Erreur fonction (Un)Compress() : allocation de mémoire impossible",
		      "Erreur fonction (Un)Compress() : Impossible d'ouvrir le fichier",
		      "Erreur fonction (Un)Compress() : Impossible d'écrire le fichier"};

  fprintf(stderr, "%s\n", LstError[nError]);

  Error = 1;
}

void HelpMessage(void)
{
  fprintf(stdout, "**** Compress v0.1b par Wyttenbach Bruno 06/08/2002 ****\n\n");
  fprintf(stdout, "Attention!! Version de Test... Décompression inutilisable\n\n");
  fprintf(stdout, "Utilisation : comp [-123456789uh] [fichier]\n");
  fprintf(stdout, " -u      Décompression du fichier\n");
  fprintf(stdout, " -h      Aide\n");
  fprintf(stdout, " -1..9   Taille du dictionnaire\n");  
}

void Main_Compress(char* File_Name)
{
  int File_In;
  int File_Out;
  long Read;
  long Size_Resu;
  char* Buffer;
  char* Resu;

  fprintf(stdout, "Dictionnaire : %d octets\nCompression...\n", Size_Scan);

  if((Buffer = malloc(SIZE_BUFFER_IN)) == NULL){
    DoError(ERR_CMP_MALLOC);
    return;
  }

  if((File_In = open(File_Name, O_RDONLY)) == -1){
    DoError(ERR_CMP_FILE);
    return;
  }

  if((File_Out = open(strcat(File_Name, ".cpr"), O_WRONLY | O_CREAT | O_TRUNC, 0666)) == -1){
    DoError(ERR_CMP_FILE);
    close(File_In);
    return;
  }

  Read = ReadFile(File_In, Buffer, SIZE_BUFFER_IN);
  fprintf(stdout, "Taille fichier décompressé : %d octets\n", Read);
  Resu = Compress(Buffer, Read, &Size_Resu);
  fprintf(stdout, "Taille fichier compressé   : %d octets\n", Size_Resu);

  if(WriteFile(File_Out, Resu, Size_Resu) != Size_Resu){
    DoError(ERR_CMP_WFILE);
    close(File_In);
    close(File_Out);
    return;
  }

  close(File_In);
  close(File_Out);

}

// Routine de compression des données contenues à l'adr BufferIn
char* Compress(char* BufferIn, long SizeIn, long* SizeOut)
{
  char* BufferOut;  // Adresse de début du Buffer qui va recevoir les données compréssées
  char* Buffer_Scan;  // Adresse de début du dictionnaire
  char* Window_BufferIn;  // Adresse de début de la fenètre de parcour des données
  char* LimitIn;  // Adresse de fin du fichier dans le buffer
  char* End_Window;  // Adresse de fin de fenètre de parcour
  //  long size = SizeIn;
  struct red Find;  // Structure contenant les coordonnées des redondances trouvées

  if((BufferOut = malloc(SizeIn)) == NULL){
    DoError(ERR_CMP_MALLOC);
    return;
  }

  Window_BufferIn = BufferIn;
  LimitIn = Window_BufferIn + SizeIn;
  End_Window = minc(LimitIn, Window_BufferIn + SIZE_WINDOW);
  Buffer_Scan = BufferIn;

  while(Window_BufferIn <= LimitIn){

    Find = Redondance(Buffer_Scan, Window_BufferIn, End_Window);

    //printf("WBI : %d, End\n", Window_BufferIn);

    //printf("%d    \r", (LimitIn - Window_BufferIn));

    WriteBufferOut(Find, BufferOut);
    Window_BufferIn += Find.Size;
    End_Window = minc(LimitIn, (Window_BufferIn + SIZE_WINDOW));
    Buffer_Scan = maxc((Window_BufferIn - Size_Scan), BufferIn);
  }

  • SizeOut = WriteBufferOut(Find, 0);
return BufferOut; } // Lecture du fichier dans un buffer long ReadFile(int File_Handle, char* Buffer, long Size) { unsigned int Read; unsigned int Rest = min(65534, Size); char* Begin_Buffer = Buffer; while(((Read = read(File_Handle, Buffer, Rest)) == Rest) || (Size == 0)){ Buffer += Read; Size -= Read; Rest = min(65534, Size); } if(Read != 65535) Buffer += Read; return (Buffer - Begin_Buffer); } // Ecriture dans un fichier à partir d'un buffer long WriteFile(int File_Handle, char* Buffer, long Size) { unsigned int Write, Rest = min(65534, Size); char* Begin_Buffer = Buffer; while(((Write = write(File_Handle, Buffer, Rest)) == Rest) && (Size > 0)){ Buffer += Write; Size -= Write; Rest = min(65534, Size); } Buffer += Write; return (Buffer - Begin_Buffer); } // (Future) En-tête d'un fichier compressé void InitBufferOut(int File_Handle, unsigned long* Buffer) {
  • Buffer = 0x42573438;
Buffer++;
  • Buffer = 0;
} // Calcul de la somme de controle unsigned long CheckSum(char* Begin, char* End, unsigned long Checksum) { for(Begin; Begin <= End; Begin++) Checksum += *Begin; return Checksum; } // Code au bit près l'emplacement, la longueur (dans le dictionnaire) définissant les données redondantes // ou bien, code juste 1 octet si aucune redondance n'a été trouvée (par la fction Redondance) long WriteBufferOut(struct red Data, char* Buffer) { static long Pos_Buffer = 0; static int N_Bit = 0; static long* Zero = NULL; long Value; char* pPos_Buffer = Buffer + Pos_Buffer; if(Buffer != 0) { if(Data.Size == 1){ Value = *pPos_Buffer; WriteBits(Value, 9, (unsigned long*)pPos_Buffer, N_Bit); AddBits(&pPos_Buffer, &N_Bit, 9); } else{ Data.Size += 0x1000; WriteBits(Data.Size, 13, (unsigned long*)pPos_Buffer, N_Bit); AddBits(&pPos_Buffer, &N_Bit, 13); WriteBits(Data.Pos, Bits_Scan, (unsigned long*)pPos_Buffer, N_Bit); AddBits(&pPos_Buffer, &N_Bit, Bits_Scan); } } else return Pos_Buffer+1; Zero = (long*)pPos_Buffer+1;
  • Zero = 0;
Pos_Buffer = pPos_Buffer - Buffer; return 0; } // Parcour le dictionnaire (Buffer), compare au contenu de la fenetre de parcour (Window), jusqu'à trouver la plus grande redondance struct red Redondance(char* Buffer, char* Window, char* End_Window) { struct red Result; long Size = 1; char* Deb_Buffer = Buffer; char* Stop; char* pZone1; char* pZone2; Result.Pos = 0; Result.Size = 1; Stop = Window; for(Buffer; Buffer < Stop; Buffer++){ pZone1 = Buffer; pZone2 = Window; while((pZone1 < Window) && (*pZone1 == *pZone2) && (pZone2 < End_Window)){ pZone1++; pZone2++; } Size = pZone1 - Buffer; if(Size > Result.Size){ Result.Pos = Buffer - Deb_Buffer; Result.Size = Size; Stop = Window - Size; } } if(Result.Size < 4){ Result.Size = 1; Result.Pos = 0; } return Result; } /* // Extrait des données compressée pour le renvoyer dans une structure 'red' pour pouvoir etre interprété struct red ExtractData(char** Pos_Buffer, int* N_Bit) { struct red Data; unsigned long Value; Value = ReadBits(1, (unsigned long*)*Pos_Buffer, *N_Bit); if(Value == 0){ Data.Size = ReadBits(9, (unsigned long*)*Pos_Buffer, *N_Bit); Data.Pos = NULL;
  • Pos_Buffer++;
if(*N_Bit == 7){
  • N_Bit = 0;
  • Pos_Bufer++;
} else
  • N_Bit++;
} else{ Data.Size = Read_Bits(13, (unsigned long*)*Pos_Buffer, *N_Bit); Data.Size -= 0x1000;
  • Pos_Buffer++;
if(N_Bit > 2){
  • Pos_Buffer++;
  • N_Bit -= 3;
} else
  • N_Bit += 5;
} return Data; }
  • /
// Lit 'Nb_Bits' à l'adresse 'pValue' et commencant au bit numéro 'N_Bit' unsigned long ReadBits(int Nb_Bits, unsigned long* pValue, int N_Bit) { unsigned long Value = *pValue; if(Nb_Bits > 24){ DoError(ERR_RB_OVERFLOW_NB_BITS); return 0; } if(N_Bit > 7){ DoError(ERR_RB_OVERFLOW_N_BIT); return 0; } if(N_Bit != 0) Value = Value << N_Bit; Value = Value >> (32 - Nb_Bits); return Value; } // Ecrit 'Value' à l'adresse 'pOctet', au numéro de bit 'N_Bit', sur une longueur de 'Nb_Bit' void WriteBits(unsigned long Value, int Nb_Bits, unsigned long* pOctet, int N_Bit) { // ATTENTION : Les bits suivant doivent etre à 0; if(Nb_Bits > 24){ DoError(ERR_WB_OVERFLOW_NB_BITS); return; } if(Value > (pow(2,Nb_Bits) - 1)){ DoError(ERR_WB_OVERFLOW_VALUE); return; } if(N_Bit > 7){ DoError(ERR_WB_OVERFLOW_N_BIT); return; } Value = Value << N_Bit;
  • pOctet = *pOctet | Value;
} long pow(long A, long B) { long Result = A; for(B; B > 1; B--) Result *= A; return Result; } long min(long A, long B) { return A<B ? A:B; } long max(long A, long B) { return A>B ? A:B; } char* minc(char* A, char* B) { return A<B ? A:B; } char* maxc(char* A, char* B) { return A>B ? A:B; } void DispTime(time_t Sec) { int Hour; int Minute; Hour = Sec / 3600; Sec -= Hour * 3600; Minute = Sec / 60; Sec -= Minute * 60; printf("%dh %dmn %ds\n",Hour, Minute, Sec); } // Calcule l'adresse 'Adr' et le numéro de bit 'Bit', en y ajoutant un déplacement de 'N_Bit' void AddBits(char** Adr, int* Bit, int N_Bits) { int temp; temp = N_Bits / 8;
  • Adr += temp;
N_Bits -= (temp * 8); temp = N_Bits + *Bit; if(temp > 7) { (*Adr)++;
  • Bit = temp - 8;
} else
  • Bit += N_Bits;
}

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
9
Date d'inscription
lundi 20 mai 2002
Statut
Membre
Dernière intervention
27 septembre 2003

Pour optimiser ton prog tu peux :
* remplacer les laVar++ par des ++laVar
* transformer max, min en macros
* limiter les controles lors de la compression, quite à faire une seconde passe de contrôle après une première de compression

* restreindre les entrés/sorties en stockant tout en mémoire (heu là faut voir)
* transformer ton dico en AVL, ou déja eb ABR
Messages postés
4
Date d'inscription
lundi 5 août 2002
Statut
Membre
Dernière intervention
7 août 2002

Je n'ai pas encore fait de routine de décompression, mais ca ne saurai tarder..
Je serai fixé sur son (bon?) fonctionnement...

Ok pour les utilitaires de profilage, je ne savais pas que cela existait, merci du
conseil, ca pourra m'ètre utile car j'ai l'impression que certaines routines
bouffent plus de temps que prévu...
Si jamais tu sais ou je peux trouver ces progs...

Le problème de temps vient en (grosse) partie du fait que le dictionnaire est
parcouru en entier afin de trouver la + grande redondance.
Pour améliorer un peu, il faudrai arréter la recherche dès qu'une
suite de données en double trouvée soit suffisament grande, pour que sa
compression soit considérée comme 'rentable'.

...un peu d'ASM ca ferai du bien aussi....
Messages postés
269
Date d'inscription
mercredi 24 avril 2002
Statut
Membre
Dernière intervention
9 juin 2003

t'a essayé de décompresser ce que tu compresses avec ton prog ?
pour optimiser tu as des utilitaires de profilage sous linux (te permettant de voir quelles fonctions prennent le plus de temps, etc..)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.