path: root/sem_3/SYSTEME/TP3/HUFFMAN/distrib.c

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef struct proba proba;
struct proba {
  char * carac;
  int * nb_carac;
  float * proba;
  int taille;
  int somme;
};
typedef struct branche branche;
struct branche {
  char noeud;
  branche * filsg;
  branche * filsd;
};
typedef struct doublet doublet;
struct doublet{
  int a;
  int b;
};
typedef struct table table;
struct table {
  unsigned int taille;
  unsigned int * taillecode;
  char * carac;
  char ** code;
  unsigned int indice[256];
};
typedef struct buffer buffer;
struct buffer {
  unsigned int taille;
  char contenu;
};

void loading(int, FILE *,float *);
void forceprintbuffer(buffer *,FILE *);
void supprimerTable(table *);
void ecrirecomp(FILE *,FILE *,table *,buffer *,int );
void videbuffer(buffer *);
void ajouterbuffer(buffer*, char,FILE *);
void printcaraccode(table *,char,FILE *, buffer*);
void printchemin (char *, int, FILE *, buffer *);
void parcoursarbre ( branche *, char *, int, FILE *, table *, buffer *);
table * ecrireArbre(FILE *, branche*, int,buffer *);
void afficheTab(proba *);
void supprimerArbre(branche *);
branche* creerArbre(char , branche * , branche * );
int estdanstab (char *,int,char);
void creertab (proba *, FILE *);
branche* creerHuff(proba*);
doublet deuxpluspetits(proba *);
void aff(branche *, int );
void printinfofinales(table *, FILE *, FILE *);


int main (int argc, char ** argv) {
  if (argc != 3) {
    printf("Erreur, la syntaxe est la suivante : ./huffhuff [source] [destination]");
    return -1;
  }
  FILE * fichier = fopen(argv[1], "r");
  if (fichier == NULL) {
    printf("Erreur, l'ouverture du fichier source à rencontré une erreur, verifiez que vous avez les droits en lecture sur le fichier.");
  }
  FILE * fichierdest = fopen(argv[2],"wb");
  if (fichierdest == NULL) {
    printf("Erreur, l'ouverture du fichier de destination à rencontré une erreur.");
    return -2;
  }
  fseek(fichier,0,SEEK_END);
  int size = ftell(fichier);
  rewind(fichier);
  proba tab;
  printf("Le fichier %s fait %d octets.\n",argv[1],size);
  creertab (&tab, fichier);
  afficheTab(&tab);
  branche * Arbre = creerHuff(&tab);
  free(tab.carac);
  free(tab.nb_carac);
  free(tab.proba);
  buffer * buf = malloc(sizeof(buffer));
  videbuffer(buf);
  table * tablecodage = ecrireArbre(fichierdest, Arbre, tab.taille,buf);
  ecrirecomp(fichier,fichierdest,tablecodage,buf,size);
  printinfofinales(tablecodage,fichier,fichierdest);
  supprimerArbre(Arbre);
  supprimerTable(tablecodage);
  free(buf);
  fclose(fichierdest);
  fclose( fichier);
  return 0;
}


void printinfofinales(table * tablecode, FILE * source, FILE * destination){
  int somme=0;
  for (int i = 0; i < tablecode->taille;i++){
    somme+=tablecode->taillecode[i];
  }
  float moy = (float)somme/(float)tablecode->taille;
  printf("Fini ! \n");
  printf("Longueur moyenne du codage : %2.2f bits;", moy);
  fseek(source,0,SEEK_END);
  fseek(destination,0,SEEK_END);
  int taillesource = ftell(source);
  int taillecible = ftell(destination);
  printf (" Taille d'origine : %d; Taille compressée : %d; Soit un gain de %3.2f %%\n", taillesource,taillecible,100-(float)taillecible*100/(float)taillesource);
}
void supprimerTable(table * tablecod){
  for (unsigned int i = 0; i < tablecod->taille; i ++){
    free(tablecod->code[i]);
  }
  free(tablecod->taillecode);
  free(tablecod->carac);
  free(tablecod);
}
void loading(int taille, FILE * fichier, float * anciennevaleur){
  int current = ftell(fichier)-1;
  float avancement = current*100/taille;
  if (current == 0){
    *anciennevaleur=0;
    printf("[");
    fflush(stdout);
  }
  if (*anciennevaleur+10 <= avancement){
    printf("##");
    fflush(stdout);
    *anciennevaleur=avancement;
  }
  if (current == taille-2){
    printf("##]");
    fflush(stdout);
  }

}
void ecrirecomp(FILE * fichier,FILE * fichierdest,table * tablecodage, buffer * buf, int size){
  fseek(fichier,0,SEEK_SET);
  int current=fgetc(fichier);
  float * anciennevaleur=malloc(sizeof(float));
  *anciennevaleur=0;
  while(current!=EOF){
    printcaraccode(tablecodage,(char)current,fichierdest,buf);
    loading(size,fichier,anciennevaleur);
    current =fgetc(fichier);
  }
  char remplissage = (char) 8-buf->taille;
  forceprintbuffer(buf,fichierdest);
  fwrite(&remplissage,sizeof(char),1,fichierdest);
  free(buf);
}
void videbuffer(buffer * buf){
  buf->taille=0;
  buf->contenu = 0;
}
void ajouterbuffer(buffer* buf, char carac,FILE * destination){
  char tmp='1';
  if ( buf->taille < 8){
    if (  carac == tmp)buf->contenu+=pow(2,7-buf->taille);
    buf->taille++;
  }
  if (buf->taille == 8) {
    fwrite(&buf->contenu,sizeof(char),1,destination);
    videbuffer(buf);
    fflush(destination);
  }
}
void forceprintbuffer(buffer * buf,FILE * destination){
  if ( buf->taille>0){
    fwrite(&buf->contenu,sizeof(char),1,destination);
    videbuffer(buf);
  }
}
void printcaraccode(table* tablecodage,char carac,FILE * fichierdest, buffer * buf){
  unsigned int i =0;
  i=tablecodage->indice[(unsigned char)carac];
  for (unsigned int j=0; j < tablecodage->taillecode[i];j++){
    ajouterbuffer(buf,tablecodage->code[i][j],fichierdest);
  }
}
void printchemin (char * chemin, int taille, FILE *destination,buffer * buf){
  char taillechar = (char)taille;
  fwrite(&taillechar, sizeof(char),1,destination);
  for (int i =0; i < taille; i ++){
    ajouterbuffer(buf,chemin[i],destination);
  };
  forceprintbuffer(buf, destination);
}
branche* creerHuff(proba*prob){
  branche * arbrehuf[prob->taille];
  for ( int i =0; i <= prob->taille; i ++){
    arbrehuf[i]= creerArbre(prob->carac[i], NULL, NULL);
  }
  doublet indices = deuxpluspetits(prob);
  while (indices.b!=-1) {
    arbrehuf[indices.a] = creerArbre (0, arbrehuf[indices.a],arbrehuf[indices.b]);
    prob->proba[indices.a]+=prob->proba[indices.b];
    prob->proba[indices.b]=0;
    indices = deuxpluspetits(prob);
  }
  return arbrehuf[indices.a];
}
void parcoursarbre ( branche * Arbre, char * chemin, int taille, FILE * destination, table * tabcode, buffer * buf){
  if ( Arbre->filsd == NULL && Arbre->filsg==NULL ){
    printchemin(chemin, taille, destination, buf);
    fwrite(&Arbre->noeud,sizeof(char),1,destination);
    char * code = malloc(taille*sizeof(char));
    tabcode->taille+=1;
    tabcode->code= realloc(tabcode->code,tabcode->taille*sizeof(char*));
    tabcode->carac=realloc(tabcode->carac,tabcode->taille*sizeof(char));
    tabcode->taillecode=realloc(tabcode->taillecode,tabcode->taille*sizeof(unsigned int));
    tabcode->carac[tabcode->taille-1]=Arbre->noeud;
    tabcode->taillecode[tabcode->taille-1]=taille;
    tabcode->indice[(unsigned char)Arbre->noeud]=tabcode->taille-1;
    for (int i =0; i < taille; i ++){
      code[i]=chemin[i];
    }
    tabcode->code[tabcode->taille-1]=code;
    if (Arbre->noeud==(char)10) {
      printf("Carac = LF");
    }
    else if (Arbre->noeud==(char)13) {
      printf("Carac = CR");
    }
    else printf("Carac = %c", Arbre->noeud);
    printf(", taille chemin = %d, chemin = ", taille);
    for (int i =0; i < taille; i ++){
      printf("%c",chemin[i]);
    }
    printf("\n");
  }
  else{
    int newtaille= taille + 1;
    chemin = realloc(chemin, newtaille*sizeof(char));
    if (Arbre->filsg!=NULL){
      chemin[newtaille-1]='0';
      parcoursarbre ( Arbre->filsg, chemin, newtaille, destination, tabcode,buf );
    }
    if (Arbre->filsd!=NULL){
      chemin[newtaille-1]='1';
      parcoursarbre ( Arbre->filsd, chemin, newtaille, destination, tabcode,buf);
    }
  }
}
table * ecrireArbre(FILE * destination, branche* arbre, int taille,buffer * buf){
  char taille2 = (char)taille;
  table * tabcode = malloc(sizeof(table));
  tabcode->taille = 0;
  tabcode->taillecode= malloc(0);
  tabcode->code=malloc(0);
  tabcode->carac=malloc(0);
  fwrite(&taille2,sizeof(char),1,destination);
  char * chemin = malloc(0);
  parcoursarbre(arbre, chemin, 0, destination, tabcode,buf);
  free(chemin);
  fflush(destination);
  return tabcode;
}
branche* creerArbre(char carac, branche * ssag, branche * ssad){
  branche * tmp = malloc(sizeof(branche));
  tmp->noeud= carac;
  tmp->filsd= ssad;
  tmp->filsg=ssag;
  return tmp;
}
void supprimerArbre(branche * arbre){
  branche * gauche = arbre->filsg;
  branche * droite = arbre->filsd;
  if ( gauche != NULL){
    supprimerArbre(gauche);
  }
  if (droite!=NULL){
    supprimerArbre(droite);
  }
  if (droite==NULL && gauche == NULL) {
    free(arbre);
  }
}
void creertab (proba * tab, FILE * fichier){
  tab->carac = malloc(0);
  tab->nb_carac = malloc (0);
  tab->taille = 0;
  tab->somme=0;
  int caracint = 0;
  char caracchar = 0;
  int indice = -1;
  caracint= fgetc(fichier);
  while (caracint != EOF ) {
    caracchar = (char)caracint;
    tab->somme ++;
    indice = estdanstab(tab->carac, tab->taille, caracchar);
    if ( indice != -1) {
      tab->nb_carac[indice]++;
    }
    else {
      tab->taille ++;
      tab->carac=realloc(tab->carac,tab->taille*(sizeof(char)));
      tab->nb_carac=realloc(tab->nb_carac,tab->taille*(sizeof(int)));
      tab->carac[tab->taille-1]= caracchar;
      tab->nb_carac[tab->taille-1]= 1;
    }
    caracint = fgetc(fichier);
  }
  tab->proba=malloc(tab->taille*(sizeof(float)));
  for (int i =0; i<tab->taille;i++){
    tab->proba[i]= (float)tab->nb_carac[i]/(float)tab->somme;
  }
}
int estdanstab(char * tab, int n, char x) {
  int i=0;
  int ret=0;
  while (i<n && !ret) {
    if (tab[i]==x) ret = 1;
    i ++;
  }
  return ret ? i-1 : -1;
}
void afficheTab(proba * prob){
  for (int i =0; i < prob->taille; i ++) {
    if (prob->carac[i]==(char)10) {
      printf("LF | %1.3f \n", prob->proba[i]);
    }
    if (prob->carac[i]==(char)13) {
      printf("CR | %1.3f \n", prob->proba[i]);
    }
    else {
      printf("%c | %1.3f \n", prob->carac[i], prob->proba[i]);
    }

  }
  printf("Le fichier comporte %d caracteres differents\n", prob->taille);
}
doublet deuxpluspetits(proba * prob) { //renvoie les indices des deux plus petits float du tableau
  doublet ret;
  ret.a= -1;
  ret.b=-1;
  float aval,bval;
  aval = 2;
  bval = 2;
  for (int i =0; i< prob->taille; i ++){
    if ( prob->proba[i]!=0){
      if ( prob->proba[i]< aval){
        ret.b= ret.a;
        bval=aval;
        ret.a=i;
        aval=prob->proba[i];
      }
      else if (prob->proba[i]<bval){
        ret.b=i;
        bval=prob->proba[i];
      }
    }
  }
  return ret;
}