codrle3.c

著名压缩算法的实现

/* Fichier: codrle3.c
   Auteur: David Bourgin
   Date de creation: 1/2/94
   Date de derniere mise a jour: 24/7/95
   Dessein: Exemple de codage RLE type 3 avec comme donnees a compresser le contenu d'un fichier.
*/

#include <stdio.h>
/* Pour les routines printf,fputc,fread,fwrite et rewind */
#include <memory.h>
/* Pour les routines memset,memcpy */
#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

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

#define TAILLE_TRAME_MAX  256

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

unsigned int index=0,
             taille_tmp_lec=0;
unsigned char tmp_lec[3*256];

typedef struct { unsigned int taille_tab;
                 unsigned char *val_tab;
               } t_tab;
#define TAILLE_TAB(tableau)  ((tableau).taille_tab)
#define VAL_TAB(tableau)  ((tableau).val_tab)
#define SONT_EGAUX(tableau1,tableau2)  ((TAILLE_TAB(tableau1)==TAILLE_TAB(tableau2))&&(!memcmp(VAL_TAB(tableau1),VAL_TAB(tableau2),TAILLE_TAB(tableau1))))

/* Pseudo procedures */
#define taille_restante_a_lire()  (taille_tmp_lec-index)
#define charger_bloc()  { if (!taille_restante_a_lire())\
                             { taille_tmp_lec=fread(tmp_lec,1,sizeof(tmp_lec),f_source);\
                               index=0;\
                             }\
                        }
#define repositionner_index(i)  (index=(i))
#define debut_des_donnees()  { (void)rewind(f_source); taille_tmp_lec=0; index=0; }
#define fin_des_donnees()  (taille_restante_a_lire()?FALSE:(index=0,!(taille_tmp_lec=fread(tmp_lec,1,sizeof(tmp_lec),f_source))))
#define lire_octet()  ((unsigned char)(fin_des_donnees()?EOF:tmp_lec[index++]))
#define lire_tableau(tableau,nb_a_lire)  { TAILLE_TAB(tableau)=(nb_a_lire);\
                                           VAL_TAB(tableau)= &(tmp_lec[index]);\
                                           index += (nb_a_lire);\
                                         }
#define ecrire_octet(x)  ((void)fputc((unsigned char)(x),f_dest))
#define ecrire_tableau(tableau)  ((void)fwrite(VAL_TAB(tableau),1,TAILLE_TAB(tableau),f_dest))
#define completer_bloc()  { (void)memcpy(tmp_lec,&(tmp_lec[index]),taille_restante_a_lire());\
                            taille_tmp_lec=fread(&(tmp_lec[taille_restante_a_lire()]),1,sizeof(tmp_lec)-taille_restante_a_lire(),f_source)+taille_restante_a_lire();\
                            index=0;\
                          }

void chercher_occurrle3(nb_trames,taille_trame,
                        repetition_ok)
/* Parametres en sortie: nb_trames, taille_trame et repetition_ok sont modifies
   Action: Recherche dans le tampon d'octets une repetition de trame
   dont la taille et la repetition seront respectivement dans taille_trame et nb_trames.
   Si une repetition est rencontree, repetition_ok renvoie TRUE sinon repetition_ok renvoie FALSE
   Erreurs: S'il n'y a pas de trames multiples alors nb_trames ne sera pas modifie
   S'il y a repetition, telle que (nb_trames-1)*taille_trame>3, le tampon est complete
   pour ne contenir qu'une occurrence de la trame au debut
   (les repetitions ont ete videes par appel a 'completer_bloc').
*/
unsigned int *nb_trames,*taille_trame;
int *repetition_ok;
{ int egalite_des_tableaux;
  t_tab tableau1,tableau2;

  *taille_trame=1;
  *repetition_ok=FALSE;
  while ((*taille_trame<=TAILLE_TRAME_MAX)&&(taille_restante_a_lire()>=(*taille_trame << 1))&&(!*repetition_ok))
        { lire_tableau(tableau1,*taille_trame);
          lire_tableau(tableau2,*taille_trame);
          if (egalite_des_tableaux=SONT_EGAUX(tableau1,tableau2))
             { *nb_trames=2;
               while ((taille_restante_a_lire()>=*taille_trame)&&(*nb_trames<=255)&&(egalite_des_tableaux))
                     { if ((*nb_trames-1)*(*taille_trame)>3)
                          { if (*repetition_ok)
                               repositionner_index(*taille_trame);
                            else { *repetition_ok=TRUE;
                                   repositionner_index((*nb_trames-1)*(*taille_trame));
                                 }
                            completer_bloc();
                            repositionner_index(*taille_trame);
                          }
                       lire_tableau(tableau2,*taille_trame);
                       if (egalite_des_tableaux=SONT_EGAUX(tableau1,tableau2))
                          (*nb_trames)++;
                     }
               if ((*nb_trames-1)*(*taille_trame)>3)
                  { if (*repetition_ok)
                       { if (egalite_des_tableaux)
                            { repositionner_index(*taille_trame);
                              completer_bloc();
                            }
                       }
                    else { *repetition_ok=TRUE;
                           repositionner_index((*nb_trames-1)*(*taille_trame));
                           completer_bloc();
                         }
                    (*taille_trame)--;
                  }
                             /* Specifier a l'appelant qu'il y a eu repetition */
             }
          (*taille_trame)++;
          repositionner_index(0);
        }
}

void ecrire_non_reprle3(octet_repere,octet_non_repete)
/* Parametres en sortie: Aucun
   Action: Ecrit dans le flux de sortie de compression l'octet_non_repete
   octet_repere fait office de marqueur comme defini par la methode RLE 2
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
unsigned char octet_repere,octet_non_repete;
{ if (octet_non_repete==octet_repere)
     { ecrire_octet(octet_repere);
       ecrire_octet(0);
       ecrire_octet(0);
     }
  else ecrire_octet(octet_non_repete);
}

void ecrire_reprle3(octet_repere,trame,repetition)
/* Parametres en sortie: Aucun
   Action: Ecrit dans le flux de sortie de compression un nombre 'repetition' fois 'trame' de taille 'taille_trame'
   octet_repere fait office de marqueur comme defini par la methode RLE 3
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
unsigned char octet_repere;
t_tab trame;
unsigned int repetition;
{ ecrire_octet(octet_repere);
  ecrire_octet(repetition-1);
  ecrire_octet(TAILLE_TAB(trame)-1);
  ecrire_tableau(trame);
}


void codagerle3()
/* Parametres en sortie: Aucun
   Action: Compresse suivant la methode RLE type 3 tous les octets lus par la fonction lire_octet
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
{ register unsigned int i;
  unsigned long int table_occurrences[256];
  unsigned char octet_repere;
  t_tab trame;
  unsigned int nb_trames,taille_trame;
  int repetition_valide;

  if (!fin_des_donnees())    /* Y a-t-il au moins un octet a analyser? */
     {                       /* Initialiser le nombre d'occurrences de tous les octets a 0 */
       (void)memset((char *)table_occurrences,0,sizeof(table_occurrences));
                             /* Ceci equivaut a remplir table_occurrences de 0.
                                C'est plus rapide que boucler 256 fois */
                             /* Valider les occurrences de table_occurrences en fonction des donnees a compresser */
       while (!fin_des_donnees())
             { octet_repere=lire_octet();
               table_occurrences[octet_repere]++;
             }
       octet_repere=0;
       for (i=1;i<=255;i++)
           if (table_occurrences[i]<table_occurrences[octet_repere])
              octet_repere=i;
       ecrire_octet(octet_repere);
       debut_des_donnees();
       charger_bloc();
       while (taille_restante_a_lire())
             { chercher_occurrle3(&nb_trames,&taille_trame,&repetition_valide);
               if (repetition_valide)
                             /* Il y a eu repetition? */
                  { lire_tableau(trame,taille_trame);
                    ecrire_reprle3(octet_repere,trame,nb_trames);
                  }
               else          /* Pas de repetition de motif */
                    ecrire_non_reprle3(octet_repere,lire_octet());
               completer_bloc();
             }
     }
}

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