/* 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... */#endifunsigned 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);}