dcodhuff.c

著名压缩算法的实现

/* Fichier: dcodhuff.c
   Auteur: David Bourgin
   Date de creation: 15/2/94
   Date de derniere mise a jour: 24/7/95
   Dessein: Exemple de decodage Huffman avec comme donnees a decompresser le contenu d'un fichier.
*/

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

/* 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

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 */
                         struct s_arbre *ptr_gauche,
                                        *ptr_droit;
                       } t_arbre,*p_arbre;
#define OCTET_ARBRE(ptr_arbre)  ((*(ptr_arbre)).octet)
#define PGAUCHE_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_gauche)
#define PDROIT_ARBRE(ptr_arbre)  ((*(ptr_arbre)).ptr_droit)

typedef struct { unsigned char bits[32],
                               nb_bits,
                               presence;
               } t_val_bin;
#define BITS_VAL_BIN(x)  ((x).bits)
#define NB_BITS_VAL_BIN(x)  ((x).nb_bits)
#define PRESENCE_VAL_BIN(x)  ((x).presence)

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

                             /* 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 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_lire=0;
unsigned int val_a_lire=0;

unsigned char lire_code_1_bit()
/* Parametres en sortie: Renvoie un entier non signe sur 1 bit valide (a droite de l'entier)
   Action: Lit dans le fichier des donnees en entree le prochain bit
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
   La source des donnees doit disposer de suffisamment de bits restants a lire
*/
{ unsigned int resultat;

  if (nb_bits_a_lire)
     { nb_bits_a_lire--;
       resultat=(val_a_lire >> nb_bits_a_lire) & 1;
     }
  else { val_a_lire=lire_octet();
         nb_bits_a_lire=7;
         resultat=(val_a_lire >> 7) & 1;
       }
  val_a_lire &= 127;
  return resultat;
}

unsigned int lire_code_n_bits(n)
/* Parametres en sortie: Renvoie un entier non signe sur 'n' bits valides (a droite de l'entier)
   Action: Lit dans le fichier des donnees en entree les n prochains bits
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
   La source des donnees doit disposer de suffisamment de bits restants a lire
*/
unsigned char n;
{ unsigned int resultat;

  while ((nb_bits_a_lire<n)&&(!fin_des_donnees()))
        { val_a_lire = (val_a_lire << 8)+lire_octet();
          nb_bits_a_lire += 8;
        }
  nb_bits_a_lire -= n;
  resultat=val_a_lire >> nb_bits_a_lire;
  val_a_lire &= ((1<<nb_bits_a_lire)-1);
  return resultat;
}

void lire_en_tete(table_codes)
/* Parametres en sortie: Le contenu de 'table_codes' est modifie
   Action: Reconstruit le tableau de codage binaire a partir de l'en-tete
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
t_val_bin table_codes[257];
{ register unsigned int i,j;
  char num_octet;

  (void)memset((char *)table_codes,0,257*sizeof(*table_codes));
                             /* == Decodage de la premiere partie de l'en-tete == */
  if (lire_code_1_bit())
                             /* Premier bit=0 => Octets presents codes sur n*8 bits
                                           =1 => Octets presents codes sur 256 bits */
     for (i=0;i<=255;i++)
         PRESENCE_VAL_BIN(table_codes[i])=lire_code_1_bit();
  else { i=lire_code_n_bits(5)+1;
         while (i)
               { PRESENCE_VAL_BIN(table_codes[lire_code_n_bits(8)])=1;
                 i--;
               }
       }
  PRESENCE_VAL_BIN(table_codes[256])=1;
                             /* La presence de l'octet fictif 256 est forcee! */

                             /* == Decodage de la seconde partie de l'en-tete == */
  for (i=0;i<=256;i++)
      if PRESENCE_VAL_BIN(table_codes[i])
         { if (lire_code_1_bit())
                             /* Premier bit=0 => 5 bits de longueur binaire-1 suivi du mot binaire
                                           =1 => 8 bits de longueur binaire-1 suivi du mot binaire */
              j=lire_code_n_bits(8)+1;
           else j=lire_code_n_bits(5)+1;
           NB_BITS_VAL_BIN(table_codes[i])=j;
                             /* Lecture du mot binaire */
           num_octet=(j+7) >> 3;
           if (j & 7)
              {              /* Lire les bits ne formant pas un octet */
                num_octet--;
                BITS_VAL_BIN(table_codes[i])[num_octet]=(unsigned char)lire_code_n_bits(j & 7);
              }
           while (num_octet)
                 {           /* Lire les bits format un octet */
                   num_octet--;
                   BITS_VAL_BIN(table_codes[i])[num_octet]=(unsigned char)lire_code_n_bits(8);
                 }
         }
}

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 coder_arbre(table_codes)
/* Parametres en sortie: Un arbre binaire est renvoye
   Action: Renvoie l'arbre binaire de decodage de 'table_codes'
   Erreurs: Aucune
*/
t_val_bin table_codes[257];
{ register unsigned int i;
  unsigned int j;
  p_arbre ptr_arbre,noeud_courant;

  if ((ptr_arbre=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
     exit(BAD_MEM_ALLOC);
  OCTET_ARBRE(ptr_arbre)=257;
  PGAUCHE_ARBRE(ptr_arbre)=NULL;
  PDROIT_ARBRE(ptr_arbre)=NULL;
  for (i=0;i<=256;i++)
      { for (noeud_courant=ptr_arbre,j=NB_BITS_VAL_BIN(table_codes[i]);j;j--)
          { if (BITS_VAL_BIN(table_codes[i])[(j-1) >> 3] & (1 << ((j-1) & 7)))
               if (PGAUCHE_ARBRE(noeud_courant)==NULL)
                  { if ((PGAUCHE_ARBRE(noeud_courant)=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
                       { supprimer_arbre(ptr_arbre);
                         exit(BAD_MEM_ALLOC);
                       }
                    noeud_courant=PGAUCHE_ARBRE(noeud_courant);
                    PGAUCHE_ARBRE(noeud_courant)=NULL;
                    PDROIT_ARBRE(noeud_courant)=NULL;
                  }
               else noeud_courant=PGAUCHE_ARBRE(noeud_courant);
            else if (PDROIT_ARBRE(noeud_courant)==NULL)
                    { if ((PDROIT_ARBRE(noeud_courant)=(p_arbre)malloc(sizeof(t_arbre)))==NULL)
                         { supprimer_arbre(ptr_arbre);
                           exit(BAD_MEM_ALLOC);
                         }
                      noeud_courant=PDROIT_ARBRE(noeud_courant);
                      PGAUCHE_ARBRE(noeud_courant)=NULL;
                      PDROIT_ARBRE(noeud_courant)=NULL;
                    }
                 else noeud_courant=PDROIT_ARBRE(noeud_courant);
            if (j==1)
               OCTET_ARBRE(noeud_courant)=i;
            else OCTET_ARBRE(noeud_courant)=257;
          }
      }
  return (ptr_arbre);
}

void decodagehuff()
/* Parametres en sortie: Aucun
   Action: Decompresse suivant la methode de Huffman tous les octets lus par les fonctions lire_code_1_bit et lire_code_n_bits
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
{ t_val_bin table_codage[257];
  p_arbre ptr_arbre,noeud_courant;

  if (!fin_des_donnees())    /* Y a-t-il des donnees a compresser? */
     { lire_en_tete(table_codage);
       ptr_arbre=coder_arbre(table_codage);
       do { noeud_courant=ptr_arbre;
            while (OCTET_ARBRE(noeud_courant)==257)
                  if (lire_code_1_bit())
                             /* Bit=1 => Aller a gauche dans le noeud courant de l'arbre
                                   =0 => Aller a droite dans le noeud courant de l'arbre */
                     noeud_courant=PGAUCHE_ARBRE(noeud_courant);
                  else noeud_courant=PDROIT_ARBRE(noeud_courant);
            if (OCTET_ARBRE(noeud_courant)<=255)
               ecrire_octet(OCTET_ARBRE(noeud_courant));
          }
       while (OCTET_ARBRE(noeud_courant)!=256);
       supprimer_arbre(ptr_arbre);
     }
}

void aide()
/* Parametres en sortie: Aucun
   Action: Affiche l'aide du programme et termine son execution
   Erreurs: Aucune
*/
{ printf("Cet utilitaire permet de decompresser 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: dcodhuff source destination\n");
  printf("source: Nom du fichier a decompresser\n");
  printf("destination: Nom du fichier decompresse\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 { decodagehuff();
                   fclose(f_source);
                   fclose(f_dest);
                 }
  printf("Execution de dcodhuff achevee.\n");
  return (NO_ERROR);
}