dcodlzw.c

著名压缩算法的实现

/* Fichier: dcodlzw.c
   Auteur: David Bourgin
   Date de creation: 14/2/94
   Date de derniere mise a jour: 12/10/95
   Dessein: Exemple de decodage LZW avec comme donnees a decompresser le contenu d'un fichier.
*/

#include <stdio.h>
/* Pour les routines printf,fgetc,fputc. */
#include <stdlib.h>
/* Pour la routine 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
#define BAD_DATA_CODE        4
#define DICTIONARY_OVERFLOW  5

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

/* 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 long int val_a_ecrire=0,
                  val_a_lire=0;
unsigned char nb_bits_a_ecrire=0,
              nb_bits_a_lire=0;

typedef struct s_chainage_dic { unsigned int carac;
                                struct s_chainage_dic *precedent;
                              } t_chainage_dic,*p_chainage_dic;
#define CARAC_CHAINAGE(dic)  ((*(dic)).carac)
#define PREC_CHAINAGE(dic)  ((*(dic)).precedent)

#define CODAGE_TYPE_GIF
/* Implique l'inclusion des codes des marqueurs code_initialisation et code_fin_information.
   Pour invalider cette option, mettre la ligne #define... en commentaire. */
#ifdef CODAGE_TYPE_GIF
#define AUTO_DIC_REINIT
/* Si cette macro est definie, le dictionnaire est toujours augmente
   (quitte a creer une erreur de debordement!).
   Si au contraire, cette macro est indefinie, le dictionnaire n'est plus mis a jour
   des que celui-ci atteint sa capacite maximale. C'est la reception du code
   'code_initialisation' qui forcera le dictionnaire a etre vide.
   Pour invalider cette option, mettre la ligne #define... en commentaire.
   Cette macro est observee que si CODAGE_TYPE_GIF est defini,
   ce qui explique la presence des lignes #ifdef... et #endif... */
#endif

unsigned int index_dic;
/* Nombre de mots deja reconnus dans le dictionnaire. */
unsigned char nb_bits_decodage;
/* Nombre de bits en decodage. */

#define EXP2_DIC_MAX  12
/* 2^EXP2_DIC_MAX donne le nombre maximum de mots dans le dictionnaire durant *toutes* les compressions.
   Valeurs possibles: 3 a 25.
   Attention: Au-dela de 12, vous pouvez avoir des erreurs d'allocations de memoire
   selon votre compilateur et votre ordinateur. */
unsigned int index_dic_max;
/* index_dic_max donne le nombre maximum de mots dans le dictionnaire durant *une* compression.
   Cette constante est limitee entre code_fin_information et 2^EXP2_DIC_MAX */
unsigned char nb_bits_sortie,
/* Nombre de bits pour chaque donnee en sortie.
   Avec nb_bits_sortie=1, on peut compresser/decompresser des images monochromes
   et avec nb_bits_sortie=8, on peut coder des images en 256 couleurs ou des fichiers quelconques. */
              nb_bits_decodage_min;
/* Nombre de bits pour coder code_initialisation. */
unsigned int code_initialisation;
unsigned int code_fin_information;
/* code_initialisation et code_fin_information sont deux codes consecutifs
   qui arrivent juste apres le dernier mot connu du dictionnaire initial. */

p_chainage_dic dictionnaire[1<<EXP2_DIC_MAX];

void init_dictionnaire1()
/* Parametres en sortie: Aucun.
   Action: Initialise le dictionnaire qui va servir au chainage LZW.
   Erreurs: Aucune s'il y a assez de place memoire.
*/
{ register unsigned int i;

  index_dic_max=1<<12;       /* Attention: Valeurs possibles: 2^3 a 2^EXP2_DIC_MAX */
  nb_bits_sortie=8;          /* Attention: Valeurs possibles 1 a EXP2_DIC_MAX-1
                                (en general, pour des images a fixer a 1 ou 4 ou 8 si on a
                                une image monochrome ou en 16 couleurs ou en 256 couleurs). */
  if (nb_bits_sortie==1)
     nb_bits_decodage_min=3;
  else nb_bits_decodage_min=nb_bits_sortie+1;
  code_initialisation=1<<(nb_bits_decodage_min-1);
#ifdef CODAGE_TYPE_GIF
  code_fin_information=code_initialisation+1;
#else
  code_fin_information=code_initialisation-1;
#endif
  for (i=0;i<index_dic_max;i++)
      { if ((dictionnaire[i]=(p_chainage_dic)malloc(sizeof(t_chainage_dic)))==NULL)
           { while (i)
             { i--;
               free(dictionnaire[i]);
             }
             fclose(f_source);
             fclose(f_dest);
             exit(BAD_MEM_ALLOC);
           }
        if (i<code_initialisation)
           CARAC_CHAINAGE(dictionnaire[i])=i;
        PREC_CHAINAGE(dictionnaire[i])=NULL;
      }
  index_dic=code_fin_information+1;
  nb_bits_decodage=nb_bits_decodage_min;
}

void init_dictionnaire2()
/* Parametres en sortie: Aucun.
   Action: Reinitialise le dictionnaire qui va servir au chainage LZW.
   Ce dictionnaire doit deja avoir ete initialise par 'init_dictionnaire1'.
   Erreurs: Aucune.
*/
{ register unsigned int i;

  for (i=code_initialisation;(i<index_dic_max)&&(dictionnaire[i]!=NULL);i++)
      PREC_CHAINAGE(dictionnaire[i])=NULL;
  index_dic=code_fin_information+1;
  nb_bits_decodage=nb_bits_decodage_min;
}

void supprimer_dictionnaire()
/* Parametres en sortie: Aucun.
   Action: Supprime le dictionnaire qui a servi au chainage LZW.
   Erreurs: Aucune si le dictionnaire a ete initialise par 'init_dictionnaire1'.
*/
{ register unsigned int i;

  for (i=0;(i<index_dic_max)&&(dictionnaire[i]!=NULL);i++)
      free(dictionnaire[i]);
}

void ecrire_sortie(valeur)
/* Parametres en sortie: Aucune.
   Action: Ecrit nb_bits_sortie via la fonction ecrire_octet.
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
*/
unsigned int valeur;
{ val_a_ecrire=(val_a_ecrire << nb_bits_sortie) | valeur;
  nb_bits_a_ecrire += nb_bits_sortie;
  while (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);
        }
}

void completer_sortie()
/* Parametres en sortie: Aucune.
   Action: Complete le dernier octet a ecrire par des bits a 0, si necessaire.
   Cette procedure est a considerer avec la procedure ecrire_sortie.
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
*/
{ if (nb_bits_a_ecrire>0)
     ecrire_octet((unsigned char)(val_a_ecrire << (8-nb_bits_a_ecrire)));
  val_a_ecrire=nb_bits_a_ecrire=0;
}

void ecrire_chainage(chainage,carac)
/* Parametres en sortie: 'carac' peut avoir ete modifie.
   Action: Envoie la chane dans le flux de sortie donne par le 'chainage' du dictionnaire LZW.
   'carac' contient en fin de routine le premier caractere de la chaine.
   Erreurs: Aucune (sauf debordement possible de la pile operationnelle allouee par
   le programme qui doit permettre au moins 8*INDEX_DIC_MAX octets, ce qui correspond
   a un cas de figure exceptionnel.
*/
p_chainage_dic chainage;
unsigned int *carac;
{ if (PREC_CHAINAGE(chainage)!=NULL)
     { ecrire_chainage(PREC_CHAINAGE(chainage),carac);
       ecrire_sortie(CARAC_CHAINAGE(chainage));
     }
  else { ecrire_sortie(CARAC_CHAINAGE(chainage));
         *carac=CARAC_CHAINAGE(chainage);
       }
}

unsigned int ecrire_chaine(code_prec,code_actuel,premier_carac)
/* Parametres en sortie: Renvoie un octet.
   Action: Ecrit la chaine d'octets associee a 'code_actuel' et renvoie
   le premier caractere de cette chaine.
   Erreurs: Aucune.
*/
unsigned int code_prec,code_actuel;
unsigned int premier_carac;
{ unsigned int carac;

  if (code_actuel<index_dic)
     ecrire_chainage(dictionnaire[code_actuel],&carac);
  else { ecrire_chainage(dictionnaire[code_prec],&carac);
         ecrire_sortie(premier_carac);
       }
  return carac;
}

void ajouter_chaine(code,premier_carac)
/* Parametres en sortie: Aucun.
   Action: Ajoute au dictionnaire la chaine avec le 'code' donne.
   Erreurs: Aucune.
*/
unsigned int code;
unsigned int premier_carac;
{ CARAC_CHAINAGE(dictionnaire[index_dic])=premier_carac;
  PREC_CHAINAGE(dictionnaire[index_dic])=dictionnaire[code];
  index_dic++;
  if (index_dic+1==(1<<nb_bits_decodage))
     nb_bits_decodage++;
}

unsigned int lire_code_gd()
/* Parametres en sortie: Renvoie la valeur d'un code.
   Action: Renvoie la valeur codee sur 'nb_bits_decodage' bits dans le flux de codes d'entree.
   Les bits sont inscrits de gauche a droite. Exemple: aaabbbbcccc est ecrit:
   Bits     7 6 5 4 3 2 1 0
   Octet 1  a a a b b b b c
   Octet 2  c c c ? ? ? ? ?
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
*/
{ unsigned int code_lu;

  while (nb_bits_a_lire<nb_bits_decodage)
        { val_a_lire=(val_a_lire<<8)|lire_octet();
          nb_bits_a_lire += 8;
        }
  nb_bits_a_lire -= nb_bits_decodage;
  code_lu=val_a_lire>>nb_bits_a_lire;
  val_a_lire &= ((1<<nb_bits_a_lire)-1);
  return code_lu;
}

unsigned int lire_code_dg()
/* Parametres en sortie: Renvoie la valeur d'un code.
   Action: Renvoie la valeur codee sur 'nb_bits_decodage' bits dans le flux de codes d'entree.
   Les bits sont inscrits de droite a gauche. Exemple: aaabbbbcccc est ecrit:
   Bits     7 6 5 4 3 2 1 0
   Octet 1  c b b b b a a a
   Octet 2  ? ? ? ? ? c c c
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
*/
{ unsigned int code_lu;

  while (nb_bits_a_lire<nb_bits_decodage)
        { val_a_lire |= ((unsigned long int)lire_octet())<<nb_bits_a_lire;
          nb_bits_a_lire += 8;
        }
  nb_bits_a_lire -= nb_bits_decodage;
  code_lu=val_a_lire & ((1<<nb_bits_decodage)-1);
  val_a_lire >>= nb_bits_decodage;
  return code_lu;
}

void decodagelzw()
/* Parametres en sortie: Aucun.
   Action: Decompresse suivant la methode de LZW tous les octets lus par les fonctions 'lire_code_??'.
   (ou '??' est 'gd' ou 'dg' selon la facon dont vous stockiez les bits dans le flux compresse.
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
*/
{ unsigned int code_prec,code_actuel;
  unsigned int premier_carac;

  if (!fin_des_donnees())
     { init_dictionnaire1();
       code_actuel=lire_code_gd();
#ifdef CODAGE_TYPE_GIF
       if (code_actuel!=code_initialisation)
          { fprintf(stderr,"Fichier de codes invalide!\n");
            supprimer_dictionnaire();
            fclose(f_source);
            fclose(f_dest);
            exit(BAD_DATA_CODE);
          }
       if ((code_actuel=lire_code_gd())<code_initialisation)
          { premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
            code_prec=code_actuel;
            code_actuel=lire_code_gd();
          }
       while (code_actuel!=code_fin_information)
             { if (code_actuel==code_initialisation)
                  { init_dictionnaire2();
                    code_actuel=lire_code_gd();
                    if (code_actuel<code_initialisation)
                       { premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
                         code_prec=code_actuel;
                         code_actuel=lire_code_gd();
                       }
                  }
               else { if (code_actuel>index_dic)
                       { fprintf(stderr,"Fichier de codes invalide!\n");
                         fclose(f_source);
                         fclose(f_dest);
                         exit(BAD_DATA_CODE);
                       }
#ifdef AUTO_DIC_REINIT
                      if (index_dic==index_dic_max)
                         { fprintf(stderr,"Depassement de capacite du dictionnaire!\n");
                           fclose(f_source);
                           fclose(f_dest);
                           exit(DICTIONARY_OVERFLOW);
                         }
                      premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
                      ajouter_chaine(code_prec,premier_carac);
                      code_prec=code_actuel;
                      code_actuel=lire_code_gd();
#else
                      premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
                      if (index_dic<index_dic_max)
                         ajouter_chaine(code_prec,premier_carac);
                      code_prec=code_actuel;
                      code_actuel=lire_code_gd();
#endif
                    }
          }
    supprimer_dictionnaire();
#else
       code_prec=code_actuel;
       premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
       while ((!fin_des_donnees())||(nb_bits_a_lire>=nb_bits_decodage))
             { code_actuel=lire_code_gd();
               if (code_actuel>index_dic)
                  { fprintf(stderr,"Fichier de codes invalide!\n");
                    fclose(f_source);
                    fclose(f_dest);
                    exit(BAD_DATA_CODE);
                  }
               premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
               if (index_dic==index_dic_max-2)
                  { init_dictionnaire2();
                    if ((!fin_des_donnees())||(nb_bits_a_lire>=nb_bits_decodage))
                       { code_prec=(code_actuel=lire_code_gd());
                         premier_carac=ecrire_chaine(code_prec,code_actuel,premier_carac);
                       }
                  }
               else ajouter_chaine(code_prec,premier_carac);
               code_prec=code_actuel;
             }
       supprimer_dictionnaire();
#endif
       completer_sortie();
     }
}

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 LZW\n");
  printf("telle qu'elle est exposee dans 'La Video et Les Imprimantes sur PC'\n");
  printf("\nUsage: dcodlzw 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 { decodagelzw();
                   fclose(f_source);
                   fclose(f_dest);
                 }
  printf("Execution de dcodlzw achevee.\n");
  return (NO_ERROR);
}