codhuff.c

著名压缩算法的实现

/* Fichier: codhuff.c
   Auteur: David Bourgin
   Date de creation: 7/2/94
   Date de derniere mise a jour: 24/7/95
   Dessein: Exemple de codage Huffman avec comme donnees a compresser le contenu d'un fichier.
   Attention: Le compilateur doit etre configure pour une pile d'au moins 20 ko.
*/

#include <stdio.h>
/* Pour les routines fgetc,fputc,fwrite et rewind */
#include <memory.h>
/* Pour les routines memset,memcpy */
#include <malloc.h>
/* Pour la routine malloc et free */
#include <stdlib.h>
/* Pour les routines qsort et exit */

/* Codes d'erreur renvoyes a l'appelant */
#define NO_ERROR      0
#define BAD_FILE_NAME 1
#define BAD_ARGUMENT  2
#define BAD_MEM_ALLOC 3

/* Constantes pratiques */
#define FALSE 0
#define TRUE  1

/* Variables globales */
FILE *f_source,*f_dest;

typedef struct s_arbre { unsigned int octet;
                             /* Un octet est volontairement code comme un entier non signe pour qu'un noeud fictif puisse depasser la valeur 255 */
                         unsigned long int poids;
                         struct s_arbre *ptr_gauche,
                                        *ptr_droit;
                       } t_arbre,*p_arbre;
#define OCTET_ARBRE(ptr_arbre)  ((*(ptr_arbre)).octet)
#define POIDS_ARBRE(ptr_arbre)  ((*(ptr_arbre)).poids)
#define PGAUCHE_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_gauche)
#define PDROIT_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_droit)

typedef struct { unsigned char bits[32];
                 unsigned int nb_bits;
               } t_val_bin;
#define BITS_VAL_BIN(val_bin)  ((val_bin).bits)
#define NB_BITS_VAL_BIN(val_bin)  ((val_bin).nb_bits)

                             /* Puisque fgetc=EOF uniquement apres un acces
                                alors statut_octet_stocke vaut TRUE si un octet a ete engrange par fgetc
                                ou FALSE s'il n'y aucun octet valide, deja lu et non traite dans val_octet_stocke */
int statut_octet_stocke=FALSE;
int val_octet_stocke;

/* Pseudo procedures */
#define debut_des_donnees()  { (void)rewind(f_source); statut_octet_stocke=FALSE; }
#define fin_des_donnees() (statut_octet_stocke?FALSE:!(statut_octet_stocke=((val_octet_stocke=fgetc(f_source))!=EOF)))
#define lire_octet()  (statut_octet_stocke?statut_octet_stocke=FALSE,(unsigned char)val_octet_stocke:(unsigned char)fgetc(f_source))
#define ecrire_octet(octet)  ((void)fputc((octet),f_dest))

unsigned char nb_bits_a_ecrire=0;
unsigned int val_a_ecrire=0;

void ecrire_val_bin(val_bin)
/* Parametres en sortie: Aucun
   Action: Ecrit dans le fichier de sortie la valeur codee en binaire dans 'val_bin'
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
t_val_bin val_bin;
{ unsigned char pos_bin,
                pos_octet;

  pos_octet=(NB_BITS_VAL_BIN(val_bin)+7) >> 3;
  pos_bin=NB_BITS_VAL_BIN(val_bin) & 7;
  if (pos_bin)
     { pos_octet--;
       val_a_ecrire=(val_a_ecrire<<pos_bin)|BITS_VAL_BIN(val_bin)[pos_octet];
       nb_bits_a_ecrire += pos_bin;
       if (nb_bits_a_ecrire>=8)
          { nb_bits_a_ecrire -= 8;
            ecrire_octet((unsigned char)(val_a_ecrire>>nb_bits_a_ecrire));
            val_a_ecrire &= ((1<<nb_bits_a_ecrire)-1);
          }
     }
  while (pos_octet)
        { pos_octet--;
          val_a_ecrire=(val_a_ecrire<<8)|BITS_VAL_BIN(val_bin)[pos_octet];
          ecrire_octet((unsigned char)(val_a_ecrire>>nb_bits_a_ecrire));
          val_a_ecrire &= ((1<<nb_bits_a_ecrire)-1);
        }
}

void completer_codage()
/* Parametres en sortie: Aucun
   Action: Complete le dernier octet a inscrire dans le fichier de codes
   par une serie de bits a 0.
   Erreurs: Aucune
*/
{ if (nb_bits_a_ecrire)
     ecrire_octet(val_a_ecrire << (8-nb_bits_a_ecrire));
}

void ecrire_en_tete(table_codes)
/* Parametres en sortie: Aucun
   Action: Ecrit l'en-tete dans le flux de codes
   Erreurs: Aucune
*/
t_val_bin table_codes[257];
{ register unsigned int i,j;
  t_val_bin val_bin_a_0,
            val_bin_a_1,
            val_bin;         /* Sert a l'envoi en mode binaire via ecrire_val_bin */

  *BITS_VAL_BIN(val_bin_a_0)=0;
  NB_BITS_VAL_BIN(val_bin_a_0)=1;
  *BITS_VAL_BIN(val_bin_a_1)=1;
  NB_BITS_VAL_BIN(val_bin_a_1)=1;
  for (i=0,j=0;j<=255;j++)
      if NB_BITS_VAL_BIN(table_codes[j])
         i++;
                             /* A partir d'ici i contient  le nombre d'octets differents d'occurrences non nulles a coder */
                             /* Premiere partie de l'en-tete: Specifier les octets qui apparaissent dans la source de codage */
  if (i<32)
     {                       /* Codage des octets apparus par une serie d'octets */
       ecrire_val_bin(val_bin_a_0);
       NB_BITS_VAL_BIN(val_bin)=5;
       *BITS_VAL_BIN(val_bin)=(unsigned char)(i-1);
       ecrire_val_bin(val_bin);
       NB_BITS_VAL_BIN(val_bin)=8;
       for (j=0;j<=255;j++)
           if NB_BITS_VAL_BIN(table_codes[j])
              { *BITS_VAL_BIN(val_bin)=(unsigned char)j;
                ecrire_val_bin(val_bin);
              }
     }
  else {                     /* Codage des octets apparus par une serie de bits */
         ecrire_val_bin(val_bin_a_1);
         for (j=0;j<=255;j++)
             if NB_BITS_VAL_BIN(table_codes[j])
                ecrire_val_bin(val_bin_a_1);
             else ecrire_val_bin(val_bin_a_0);
     }
                             /* Seconde partie de l'en-tete: Specifier le codage des octets (fictifs ou non) qui apparaissent dans la source de codage */
  for (i=0;i<=256;i++)
      if (j=NB_BITS_VAL_BIN(table_codes[i]))
         { if (j<33)
              { ecrire_val_bin(val_bin_a_0);
                NB_BITS_VAL_BIN(val_bin)=5;
              }
           else { ecrire_val_bin(val_bin_a_1);
                  NB_BITS_VAL_BIN(val_bin)=8;
                }
           *BITS_VAL_BIN(val_bin)=(unsigned char)(j-1);
           ecrire_val_bin(val_bin);
           ecrire_val_bin(table_codes[i]);
         }
}

int comp_poids_arbre(arbre1,arbre2)
/* Parametres en sortie: Renvoie un statut de comparaison
   Action: Renvoie un nombre negatif, nul ou positif selon que le poids
   de 'arbre2' est inferieur, egal ou superieur au poids de 'arbre1'
   Erreurs: Aucune
*/
p_arbre *arbre1,*arbre2;
{ return (POIDS_ARBRE(*arbre2) ^ POIDS_ARBRE(*arbre1))?((POIDS_ARBRE(*arbre2)<POIDS_ARBRE(*arbre1))?-1:1):0;
}

void supprimer_arbre(arbre)
/* Parametres en sortie: Aucun
   Action: Supprime la memoire allouee a un arbre
   Erreurs: Aucune si l'arbre a ete construit par allocations dynamiques!
*/
p_arbre arbre;
{ if (arbre!=NULL)
     { supprimer_arbre(PGAUCHE_ARBRE(arbre));
       supprimer_arbre(PDROIT_ARBRE(arbre));
       free(arbre);
     }
}

p_arbre creer_arbre_codage()
/* Parametres en sortie: Renvoie un arbre de codage
   Action: Genere un arbre de codage de Huffman suivant les donnees issues du flux a compresser
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
{ register unsigned int i;
  p_arbre table_occurrences[257],
          ptr_arbre_fictif;

                             /* Initialiser le nombre d'occurrences de tous les octets a 0 */
  for (i=0;i<=256;i++)
      { if ((table_occurrences[i]=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
           { for (;i;i--)
                 free(table_occurrences[i-1]);
             exit(BAD_MEM_ALLOC);
           }
        OCTET_ARBRE(table_occurrences[i])=i;
        POIDS_ARBRE(table_occurrences[i])=0;
        PGAUCHE_ARBRE(table_occurrences[i])=NULL;
        PDROIT_ARBRE(table_occurrences[i])=NULL;
      }
                             /* Valider les occurrences de table_occurrences en fonction des donnees a compresser */
  if (!fin_des_donnees())
     { while (!fin_des_donnees())
             { i=lire_octet();
               POIDS_ARBRE(table_occurrences[i])++;
             }
       POIDS_ARBRE(table_occurrences[256])=1;
                             /* Tri de la table des occurrences selon le poids de chaque caractere */
       (void)qsort(table_occurrences,257,sizeof(p_arbre),comp_poids_arbre);
       for (i=256;(i!=0)&&(!POIDS_ARBRE(table_occurrences[i]));i--)
           free(table_occurrences[i]);
       i++;
                             /* A partir d'ici i donne le nombre d'octets differents d'occurrence non nulle dans le flux a compresser */
       while (i>0)           /* Parcourir (i+1)/2 fois la table des occurrences pour relier les noeuds en un unique arbre */
             { if ((ptr_arbre_fictif=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
                  { for (i=0;i<=256;i++)
                        supprimer_arbre(table_occurrences[i]);
                    exit(BAD_MEM_ALLOC);
                  }
               OCTET_ARBRE(ptr_arbre_fictif)=257;
               POIDS_ARBRE(ptr_arbre_fictif)=POIDS_ARBRE(table_occurrences[--i]);
               PGAUCHE_ARBRE(ptr_arbre_fictif)=table_occurrences[i];
               if (i)
                  { i--;
                    POIDS_ARBRE(ptr_arbre_fictif) += POIDS_ARBRE(table_occurrences[i]);
                    PDROIT_ARBRE(ptr_arbre_fictif)=table_occurrences[i];
                  }
               else PDROIT_ARBRE(ptr_arbre_fictif)=NULL;
               table_occurrences[i]=ptr_arbre_fictif;
               (void)qsort((char *)table_occurrences,i+1,sizeof(p_arbre),comp_poids_arbre);
               if (i)        /* Reste-t-il un noeud dans la table des occurrences? */
                  i++;       /* Oui, alors tenir compte du noeud fictif */
             }
     }
  return (*table_occurrences);
}

void coder_table_codes(arbre,table_codes,val_code)
/* Parametres en sortie: Les donnees de 'table_codes' peuvent avoir ete modifiees
   Action: Enregistre l'arbre de codage sous forme d'une table de codages binaires plus rapides d'acces
   'val_code' fournit le codage au noeud courant de l'arbre
   Erreurs: Aucune
*/
p_arbre arbre;
t_val_bin table_codes[257],
          *val_code;
{ register unsigned int i;
  t_val_bin tmp_val_code;

  if (OCTET_ARBRE(arbre)==257)
     { if (PGAUCHE_ARBRE(arbre)!=NULL)
                             /* Les sous-arbres a gauche debutent par un bit a 1 */
          { tmp_val_code = *val_code;
            for (i=31;i>0;i--)
                BITS_VAL_BIN(*val_code)[i]=(BITS_VAL_BIN(*val_code)[i] << 1)|(BITS_VAL_BIN(*val_code)[i-1] >> 7);
            *BITS_VAL_BIN(*val_code)=(*BITS_VAL_BIN(*val_code) << 1) | 1;
            NB_BITS_VAL_BIN(*val_code)++;
            coder_table_codes(PGAUCHE_ARBRE(arbre),table_codes,val_code);
            *val_code = tmp_val_code;
          }
       if (PDROIT_ARBRE(arbre)!=NULL)
                             /* Les sous-arbres a droite debutent par un bit a 0 */
          { tmp_val_code = *val_code;
            for (i=31;i>0;i--)
                BITS_VAL_BIN(*val_code)[i]=(BITS_VAL_BIN(*val_code)[i] << 1)|(BITS_VAL_BIN(*val_code)[i-1] >> 7);
            *BITS_VAL_BIN(*val_code) <<= 1;
            NB_BITS_VAL_BIN(*val_code)++;
            coder_table_codes(PDROIT_ARBRE(arbre),table_codes,val_code);
            *val_code = tmp_val_code;
          }
     }
  else table_codes[OCTET_ARBRE(arbre)] = *val_code;
}

void creer_table_codes(arbre,table_codes)
/* Parametres en sortie: Les donnees de 'table_codes' peuvent avoir ete modifiees
   Action: Enregistre l'arbre de codage sous forme d'une table de codages binaires plus rapide d'acces
   Erreurs: Aucune
*/
p_arbre arbre;
t_val_bin table_codes[257];
{ t_val_bin val_code;

  (void)memset((char *)&val_code,0,sizeof(val_code));
  (void)memset((char *)table_codes,0,257*sizeof(*table_codes));
  coder_table_codes(arbre,table_codes,&val_code);
}

void codagehuffman()
/* Parametres en sortie: Aucun
   Action: Compresse suivant la methode de Huffman tous les octets lus par la fonction lire_octet
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
{ p_arbre arbre;
  t_val_bin table_codage[257];
  unsigned char octet_lu;

  if (!fin_des_donnees())    /* Generer un codage uniquement s'il y a des donnees */
     { arbre=creer_arbre_codage();
                             /* Creation de l'arbre binaire le mieux adapte */
       creer_table_codes(arbre,table_codage);
       supprimer_arbre(arbre);
                             /* En deduire les codages binaires dans un tableau pour un acces plus rapide */
       ecrire_en_tete(table_codage);
                             /* Inscrire la definition du codage */
       debut_des_donnees();  /* Compression a propremement parlee des donnees */
       while (!fin_des_donnees())
             { octet_lu=lire_octet();
               ecrire_val_bin(table_codage[octet_lu]);
             }
       ecrire_val_bin(table_codage[256]);
                             /* Code de fin de codage */
       completer_codage();   /* Completer ce dernier octet avant fermeture du fichier, si necessaire */
     }
}

void aide()
/* Parametres en sortie: Aucun
   Action: Affiche l'aide du programme et termine son execution
   Erreurs: Aucune
*/
{ printf("Cet utilitaire permet de compresser un fichier par la methode de Huffman\n");
  printf("telle qu'elle est exposee dans 'La Video et Les Imprimantes sur PC'\n");
  printf("\nUsage: codhuff source destination\n");
  printf("source: Nom du fichier a compresser\n");
  printf("destination: Nom du fichier compresse\n");
}

int main(argc,argv)
/* Parametres en sortie: Renvoie un code d'erreur (0=Aucune)
   Action: Procedure principale
   Erreurs: Detectee, traitee et un code d'erreur est renvoye si necessaire
*/
int argc;
char *argv[];
{ if (argc!=3)
     { aide();
       exit(BAD_ARGUMENT);
     }
  else if ((f_source=fopen(argv[1],"rb"))==NULL)
          { aide();
            exit(BAD_FILE_NAME);
          }
       else if ((f_dest=fopen(argv[2],"wb"))==NULL)
               { aide();
                 exit(BAD_FILE_NAME);
               }
            else { codagehuffman();
                   fclose(f_source);
                   fclose(f_dest);
                 }
  printf("Execution de codhuff achevee.\n");
  return (NO_ERROR);
}