Initial commit

1 files changed, 357 insertions, 0 deletions

diff --git a/sem_3/SYSTEME/TP3/HUFFMAN/distrib.c b/sem_3/SYSTEME/TP3/HUFFMAN/distrib.c
new file mode 100644
index 0000000..3ae45b1
--- /dev/null
+++ b/sem_3/SYSTEME/TP3/HUFFMAN/distrib.c
@@ -0,0 +1,357 @@
+#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;
+}