codrle4.c

著名压缩算法的实现

/* Fichier: codrle4.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 4 avec comme donnees a compresser le contenu d'un fichier.
*/

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

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

unsigned int index=0,
             taille_tmp_lec=0;
unsigned char tmp_lec[8224+2*65];

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 charger_bloc()  { taille_tmp_lec=fread(tmp_lec,1,sizeof(tmp_lec),f_source); index=0; }
#define repositionner_index(i)  (index=(i))
#define taille_restante_a_lire()  (taille_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_mot(x)  { ecrire_octet((x) >> 8); ecrire_octet((x) & 0xFF); }
#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_occurrle4(index_basic,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 a partir de la position index_basic 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
*/
unsigned int index_basic,*nb_trames,*taille_trame;
int *repetition_ok;
{ int egalite_des_tableaux;
  t_tab tableau1,tableau2;

  *taille_trame=1;
  *repetition_ok=FALSE;
  repositionner_index(index_basic);
  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<16449)&&(*taille_trame==1))||((*nb_trames<257)&&(*taille_trame>1)))
                      &&(egalite_des_tableaux))
                     { if ((*taille_trame>2)||(*nb_trames>2))
                          { if (*repetition_ok)
                               repositionner_index(*taille_trame);
                            else { *repetition_ok=TRUE;
                                   if (index_basic)
                                      return;
                                   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 ((*taille_trame>2)||(*nb_trames>2))
                  { if (index_basic)
                       { *repetition_ok=TRUE;
                         return;
                       }
                    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(index_basic);
        }
}

void codagerle4()
/* Parametres en sortie: Aucun
   Action: Compresse suivant la methode RLE type 4 tous les octets lus par la fonction lire_octet
   Erreurs: Une erreur d'entree/sortie peut perturber le deroulement de l'algorithme
*/
{ t_tab trame;
  unsigned int nb_trames1,taille_trame1,nb_trames2,taille_trame2;
  int repetition_valide;

  charger_bloc();
  while (taille_restante_a_lire())
        { chercher_occurrle4(0,&nb_trames1,&taille_trame1,&repetition_valide);
          if (repetition_valide)
                             /* Il y a eu repetition? */
             { if (taille_trame1==1)
                             /* Trame a 1 octet? */
                  { if (nb_trames1<66)
                             /* Trame a 1 octet mais moins de 66 fois? */
                       ecrire_octet(nb_trames1-2);
                    else ecrire_mot(nb_trames1+16318);
                  }
               else {        /* Trame a plusieurs octets */
                      ecrire_octet(taille_trame1+126);
                      ecrire_octet(nb_trames1-2);
                    }
             }
          else { taille_trame1=0;
                 do {        /* Teste jusqu'ou il n'y a pas repetition */
                      taille_trame1++;
                      chercher_occurrle4(taille_trame1,&nb_trames2,&taille_trame2,&repetition_valide);
                    }
                 while ((taille_restante_a_lire())&&(taille_trame1<8224)&&(!repetition_valide));
                 if (taille_trame1<33)
                             /* Non repetition de trame avec moins de 33 octets */
                    ecrire_octet(taille_trame1+191);
                 else ecrire_mot(taille_trame1+57311);
               }
          repositionner_index(0);
          lire_tableau(trame,taille_trame1);
          ecrire_tableau(trame);
          completer_bloc();  /* Toute nouvelle analyse doit debuter dans le tampon en 0 */
        }
}

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