Compression lz77 sous linux (ou windows)

Télécharger le projet
Commenter

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;

}
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (bruno3006)