home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / CODECS.ZIP / codecs / francais / codlzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-10-13  |  13.1 KB  |  357 lines
  1. /* Fichier: codlzw.c
  2.    Auteur: David Bourgin
  3.    Date de creation: 25/2/94
  4.    Date de derniere mise a jour: 12/10/95
  5.    Dessein: Exemple de codage LZW avec comme donnees a compresser le contenu d'un fichier.
  6. */
  7.  
  8. #include <stdio.h>
  9. /* Pour les routines printf,fgetc,fputc. */
  10. #include <malloc.h>
  11. /* Pour les routines malloc et free. */
  12. #include <stdlib.h>
  13. /* Pour la routine exit. */
  14.  
  15. /* Codes d'erreur renvoyes a l'appelant. */
  16. #define NO_ERROR       0
  17. #define BAD_FILE_NAME  1
  18. #define BAD_ARGUMENT   2
  19. #define BAD_MEM_ALLOC  3
  20.  
  21. /* Constantes pratiques. */
  22. #define FALSE 0
  23. #define TRUE  1
  24.  
  25. /* Variables globales. */
  26. FILE *f_source,*f_dest;
  27.  
  28.                              /* Puisque fgetc=EOF uniquement apres un acces
  29.                                 alors statut_octet_stocke vaut TRUE si un octet a ete engrange par fgetc
  30.                                 ou FALSE s'il n'y aucun octet valide, deja lu et non traite dans val_octet_stocke */
  31. int statut_octet_stocke=FALSE;
  32. int val_octet_stocke;
  33.  
  34. /* Pseudo procedures. */
  35. #define fin_des_donnees() (statut_octet_stocke?FALSE:!(statut_octet_stocke=((val_octet_stocke=fgetc(f_source))!=EOF)))
  36. #define lire_octet()  (statut_octet_stocke?statut_octet_stocke=FALSE,(unsigned char)val_octet_stocke:(unsigned char)fgetc(f_source))
  37. #define ecrire_octet(octet)  ((void)fputc((octet),f_dest))
  38.  
  39. unsigned long int val_a_lire=0,
  40.                   val_a_ecrire=0;
  41. unsigned char nb_bits_a_lire=0,
  42.               nb_bits_a_ecrire=0;
  43.  
  44. typedef struct s_val_dic { unsigned int carac;
  45.                            unsigned int code;
  46.                            struct s_val_dic *ptr_gauche,
  47.                                             *ptr_droit;
  48.                          } t_val_dic,*p_val_dic;
  49. #define CARAC_VAL_DIC(ptr_dic)  ((*(ptr_dic)).carac)
  50. #define CODE_VAL_DIC(ptr_dic)  ((*(ptr_dic)).code)
  51. #define PGAUCHE_VAL_DIC(ptr_dic)  ((*(ptr_dic)).ptr_gauche)
  52. #define PDROIT_VAL_DIC(ptr_dic)  ((*(ptr_dic)).ptr_droit)
  53.  
  54. #define CODAGE_TYPE_GIF
  55. /* Implique l'inclusion des codes des marqueurs code_initialisation et code_fin_information.
  56.    Pour invalider cette option, mettez la ligne #define... en commentaire. */
  57.  
  58. unsigned int index_dic;
  59. /* Nombre de mots deja reconnus dans le dictionnaire. */
  60. unsigned char nb_bits_codage;
  61. /* Nombre de bits en codage. */
  62.  
  63. #define EXP2_DIC_MAX  12
  64. /* 2^EXP2_DIC_MAX donne le nombre maximum de mots dans le dictionnaire durant *toutes* les compressions.
  65.    Valeurs possibles: 3 a 25.
  66.    Attention: Au-dela de 12, vous pouvez avoir des erreurs d'allocations de memoire
  67.    selon votre compilateur et votre ordinateur. */
  68. unsigned int index_dic_max;
  69. /* index_dic_max donne le nombre maximum de mots dans le dictionnaire durant *une* compression.
  70.    Cette constante est limitee entre code_fin_information et 2^EXP2_DIC_MAX. */
  71. unsigned char nb_bits_entree,
  72. /* Nombre de bits pour chaque donnee en entree.
  73.    Avec nb_bits_entree=1, on peut compresser/decompresser des images monochromes
  74.    et avec nb_bits_entree=8, on peut coder des images en 256 couleurs ou des fichiers quelconques. */
  75.               nb_bits_codage_min;
  76. /* Nombre de bits pour coder code_initialisation. */
  77. unsigned int code_initialisation;
  78. unsigned int code_fin_information;
  79. /* code_initialisation et code_fin_information sont deux codes consecutifs
  80.    qui arrivent juste apres le dernier mot connu du dictionnaire initial. */
  81.  
  82. p_val_dic dictionnaire[1<<EXP2_DIC_MAX];
  83.  
  84. void init_dictionnaire1()
  85. /* Parametres en sortie: Aucun.
  86.    Action: Initialisation premiere du dictionnaire au debut d'un codage.
  87.    Erreurs: Aucune s'il y a assez de place memoire.
  88. */
  89. { register unsigned int i;
  90.  
  91.   index_dic_max=1<<12;       /* Attention: Valeurs possibles: 2^3 a 2^EXP2_DIC_MAX. */
  92.   nb_bits_entree=8;          /* Attention: Valeurs possibles 1 a EXP2_DIC_MAX-1
  93.                                 (en general, pour des images a fixer a 1 ou 4 ou 8 si on a
  94.                                 une image monochrome ou en 16 couleurs ou en 256 couleurs). */
  95.   if (nb_bits_entree==1)
  96.      nb_bits_codage_min=3;
  97.   else nb_bits_codage_min=nb_bits_entree+1;
  98.   code_initialisation=1<<(nb_bits_codage_min-1);
  99. #ifdef CODAGE_TYPE_GIF
  100.   code_fin_information=code_initialisation+1;
  101. #else
  102.   code_fin_information=code_initialisation-1;
  103. #endif
  104.   for (i=0;i<=code_fin_information;i++)
  105.       { if ((dictionnaire[i]=(p_val_dic)malloc(sizeof(t_val_dic)))==NULL)
  106.            { while (i)
  107.              { i--;
  108.                free(dictionnaire[i]);
  109.              }
  110.              exit(BAD_MEM_ALLOC);
  111.            }
  112.         CARAC_VAL_DIC(dictionnaire[i])=i;
  113.         CODE_VAL_DIC(dictionnaire[i])=i;
  114.         PGAUCHE_VAL_DIC(dictionnaire[i])=NULL;
  115.         PDROIT_VAL_DIC(dictionnaire[i])=NULL;
  116.       }
  117.   for (;i<index_dic_max;i++)
  118.       dictionnaire[i]=NULL;
  119.   index_dic=code_fin_information+1;
  120.   nb_bits_codage=nb_bits_codage_min;
  121. }
  122.  
  123. void init_dictionnaire2()
  124. /* Parametres en sortie: Aucun.
  125.    Action: Initialisation du dictionnaire en cours de codage.
  126.    Erreurs: Aucune.
  127. */
  128. { register unsigned int i;
  129.  
  130.   for (i=0;i<index_dic_max;i++)
  131.       { PGAUCHE_VAL_DIC(dictionnaire[i])=NULL;
  132.         PDROIT_VAL_DIC(dictionnaire[i])=NULL;
  133.       }
  134.   index_dic=code_fin_information+1;
  135.   nb_bits_codage=nb_bits_codage_min;
  136. }
  137.  
  138. void supprimer_dictionnaire()
  139. /* Parametres en sortie: Aucun.
  140.    Action: Supprime le dictionnaire de codage de la memoire dynamique.
  141.    Erreurs: Aucune.
  142. */
  143. { register unsigned int i;
  144.  
  145.   for (i=0;(i<index_dic_max)&&(dictionnaire[i]!=NULL);i++)
  146.       free(dictionnaire[i]);
  147. }
  148.  
  149. p_val_dic trouver_noeud(noeud_courant,symbole)
  150. /* Parametres en sortie: Renvoie un noeud de l'arborescence du dictionnaire.
  151.    Action: Recherche 'symbole' a partir de 'noeud_courant'.
  152.    Cette recherche se fait a partir du pointeur gauche du 'noeud_courant'
  153.    (si le pointeur gauche ne valait pas NULL) puis se deplace
  154.    sur tous les pointeurs droits jusqu'a atteindre le noeud contenant 'symbole'
  155.    ou le dernier noeud dont le pointeur droit est NULL.
  156.    Erreurs: Si le symbole n'a pas ete trouve, (noeud_courant=noeud retourne) ou (CHAR_DIC_VAL(noeud retourne)#symbole).
  157.    Le 'noeud_courant' passe a cette routine ne doit jamais valoir NULL.
  158. */
  159. p_val_dic noeud_courant;
  160. unsigned int symbole;
  161. { p_val_dic nouveau_noeud;
  162.  
  163.   if (PGAUCHE_VAL_DIC(noeud_courant)==NULL)
  164.      return noeud_courant;
  165.   else { nouveau_noeud=PGAUCHE_VAL_DIC(noeud_courant);
  166.          while ((CARAC_VAL_DIC(nouveau_noeud)!=symbole)&&(PDROIT_VAL_DIC(nouveau_noeud)!=NULL))
  167.                nouveau_noeud=PDROIT_VAL_DIC(nouveau_noeud);
  168.          return nouveau_noeud;
  169.        }
  170. }
  171.  
  172. void ajouter_noeud(noeud_courant,nouveau_noeud,symbole)
  173. /* Parametres en sortie: Aucun.
  174.    Action: Cree un nouveau_noeud dans l'arborescence du dictionnaire.
  175.    L'appel a cette routine intervient normalement apres un appel a trouver_noeud.
  176.    Erreurs: Aucune.
  177. */
  178. p_val_dic noeud_courant,nouveau_noeud;
  179. unsigned int symbole;
  180. { if (dictionnaire[index_dic]==NULL)
  181.      { if ((dictionnaire[index_dic]=(p_val_dic)malloc(sizeof(t_val_dic)))==NULL)
  182.           { supprimer_dictionnaire();
  183.             exit(BAD_MEM_ALLOC);
  184.           }
  185.        CODE_VAL_DIC(dictionnaire[index_dic])=index_dic;
  186.        PGAUCHE_VAL_DIC(dictionnaire[index_dic])=NULL;
  187.        PDROIT_VAL_DIC(dictionnaire[index_dic])=NULL;
  188.      }
  189.   CARAC_VAL_DIC(dictionnaire[index_dic])=symbole;
  190.   if (noeud_courant==nouveau_noeud)
  191.      PGAUCHE_VAL_DIC(nouveau_noeud)=dictionnaire[index_dic];
  192.   else PDROIT_VAL_DIC(nouveau_noeud)=dictionnaire[index_dic];
  193.   index_dic++;
  194.   if (index_dic==(1 << nb_bits_codage))
  195.      nb_bits_codage++;
  196. }
  197.  
  198. #define dictionnaire_sature()  (index_dic==index_dic_max)
  199.  
  200. void ecrire_code_gd(valeur)
  201. /* Parametres en sortie: Aucun.
  202.    Action: Envoie la 'valeur' codee sur 'nb_bits_codage' bits dans le flux de codes de sortie.
  203.    Les bits sont inscrits de gauche a droite. Exemple: aaabbbbcccc est ecrit:
  204.    Bits     7 6 5 4 3 2 1 0
  205.    Octet 1  a a a b b b b c
  206.    Octet 2  c c c ? ? ? ? ?
  207.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  208. */
  209. unsigned int valeur;
  210. { val_a_ecrire=(val_a_ecrire << nb_bits_codage) | valeur;
  211.   nb_bits_a_ecrire += nb_bits_codage;
  212.   while (nb_bits_a_ecrire>=8)
  213.         { nb_bits_a_ecrire -= 8;
  214.           ecrire_octet((unsigned char)(val_a_ecrire >> nb_bits_a_ecrire));
  215.           val_a_ecrire &= ((1<< nb_bits_a_ecrire)-1);
  216.         }
  217. }
  218.  
  219. void completer_codage_gd()
  220. /* Parametres en sortie: Aucune.
  221.    Action: Complete le dernier octet a ecrire par des bits a 0, si necessaire.
  222.    Cette procedure est a considerer avec la procedure ecrire_code_gd.
  223.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  224. */
  225. { if (nb_bits_a_ecrire>0)
  226.      ecrire_octet((unsigned char)(val_a_ecrire << (8-nb_bits_a_ecrire)));
  227.   val_a_ecrire=nb_bits_a_ecrire=0;
  228. }
  229.  
  230. void ecrire_code_dg(valeur)
  231. /* Parametres en sortie: Aucun.
  232.    Action: Envoie la 'valeur' codee sur 'nb_bits_codage' bits dans le flux de codes de sortie
  233.    Les bits sont inscrits de droite a gauche. Exemple: aaabbbbcccc est ecrit:
  234.    Bits     7 6 5 4 3 2 1 0
  235.    Octet 1  c b b b b a a a
  236.    Octet 2  ? ? ? ? ? c c c
  237.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  238. */
  239. unsigned int valeur;
  240. { val_a_ecrire |= ((unsigned long int)valeur) << nb_bits_a_ecrire;
  241.   nb_bits_a_ecrire += nb_bits_codage;
  242.   while (nb_bits_a_ecrire>=8)
  243.         { nb_bits_a_ecrire -= 8;
  244.           ecrire_octet((unsigned char)(val_a_ecrire&0xFF));
  245.           val_a_ecrire = (val_a_ecrire>>8)&((1<< nb_bits_a_ecrire)-1);
  246.         }
  247. }
  248.  
  249. void completer_codage_dg()
  250. /* Parametres en sortie: Aucune.
  251.    Action: Complete le dernier octet a ecrire par des bits a 0, si necessaire.
  252.    Cette procedure est a considerer avec la procedure ecrire_code_dg.
  253.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  254. */
  255. { if (nb_bits_a_ecrire>0)
  256.      ecrire_octet((unsigned char)val_a_ecrire);
  257.   val_a_ecrire=nb_bits_a_ecrire=0;
  258. }
  259.  
  260. unsigned int lire_entree()
  261. /* Parametres en sortie: Aucune.
  262.    Action: Lit nb_bits_entree via la fonction lire_octet.
  263.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  264. */
  265. { unsigned int code_lu;
  266.  
  267.   while (nb_bits_a_lire<nb_bits_entree)
  268.         { val_a_lire=(val_a_lire<<8)|lire_octet();
  269.           nb_bits_a_lire += 8;
  270.         }
  271.   nb_bits_a_lire -= nb_bits_entree;
  272.   code_lu=val_a_lire>>nb_bits_a_lire;
  273.   val_a_lire &= ((1<<nb_bits_a_lire)-1);
  274.   return code_lu;
  275. }
  276.  
  277. #define fin_entree()  ((nb_bits_a_lire<nb_bits_entree)&&fin_des_donnees())
  278.  
  279. void codagelzw()
  280. /* Parametres en sortie: Aucun.
  281.    Action: Compresse suivant la methode de LZW tous les octets lus par la fonction lire_entree.
  282.    Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme.
  283. */
  284. { p_val_dic noeud_courant,nouveau_noeud;
  285.   unsigned int symbole;
  286.  
  287.   if (!fin_entree())
  288.      { init_dictionnaire1();
  289. #ifdef CODAGE_TYPE_GIF
  290.        ecrire_code_gd(code_initialisation);
  291. #endif
  292.        noeud_courant=dictionnaire[lire_entree()];
  293.        while (!fin_entree())
  294.              { symbole=lire_entree();
  295.                nouveau_noeud=trouver_noeud(noeud_courant,symbole);
  296.                if ((nouveau_noeud!=noeud_courant)&&(CARAC_VAL_DIC(nouveau_noeud)==symbole))
  297.                   noeud_courant=nouveau_noeud;
  298.                else { ecrire_code_gd(CODE_VAL_DIC(noeud_courant));
  299.                       ajouter_noeud(noeud_courant,nouveau_noeud,symbole);
  300.                       if dictionnaire_sature()
  301.                          {
  302. #ifdef CODAGE_TYPE_GIF
  303.                            ecrire_code_gd(code_initialisation);
  304. #endif
  305.                            init_dictionnaire2();
  306.                          }
  307.                       noeud_courant=dictionnaire[symbole];
  308.                     }
  309.              }
  310.        ecrire_code_gd(CODE_VAL_DIC(noeud_courant));
  311. #ifdef CODAGE_TYPE_GIF
  312.        ecrire_code_gd(code_fin_information);
  313. #endif
  314.        completer_codage_gd();
  315.        supprimer_dictionnaire();
  316.      }
  317. }
  318.  
  319. void aide()
  320. /* Parametres en sortie: Aucun.
  321.    Action: Affiche l'aide du programme et termine son execution.
  322.    Erreurs: Aucune.
  323. */
  324. { printf("Cet utilitaire permet de compresser un fichier par la methode de LZW\n");
  325.   printf("telle qu'elle est exposee dans 'La Video et Les Imprimantes sur PC'\n");
  326.   printf("\nUsage: codlzw source destination\n");
  327.   printf("source: Nom du fichier a compresser\n");
  328.   printf("destination: Nom du fichier compresse\n");
  329. }
  330.  
  331. int main(argc,argv)
  332. /* Parametres en sortie: Renvoie un code d'erreur (0=Aucune).
  333.    Action: Procedure principale.
  334.    Erreurs: Detectee, traitee et un code d'erreur est renvoye si necessaire.
  335. */
  336. int argc;
  337. char *argv[];
  338. { if (argc!=3)
  339.      { aide();
  340.        exit(BAD_ARGUMENT);
  341.      }
  342.   else if ((f_source=fopen(argv[1],"rb"))==NULL)
  343.           { aide();
  344.             exit(BAD_FILE_NAME);
  345.           }
  346.        else if ((f_dest=fopen(argv[2],"wb"))==NULL)
  347.                { aide();
  348.                  exit(BAD_FILE_NAME);
  349.                }
  350.             else { codagelzw();
  351.                    fclose(f_source);
  352.                    fclose(f_dest);
  353.                  }
  354.   printf("Execution de codlzw achevee.\n");
  355.   return (NO_ERROR);
  356. }
  357.