Obligement - L'Amiga au maximum

Jeudi 06 août 2020 - 21:57  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Quizz
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Trucs et astuces
 · Articles divers

 · Articles in english


Twitter

Suivez-nous sur Twitter




Liste des jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z,
ALL


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Galeries

 · Menu des galeries

 · BD d'Amiga Spécial
 · Caricatures Dudai
 · Caricatures Jet d'ail
 · Diagrammes de Jay Miner
 · Images insolites
 · Fin de jeux (de A à E)
 · Fin de Jeux (de F à O)
 · Fin de jeux (de P à Z)
 · Galerie de Mike Dafunk
 · Logos d'Obligement
 · Pubs pour matériels
 · Systèmes d'exploitation
 · Trombinoscope Alchimie 7
 · Vidéos


Téléchargement

 · Documents
 · Jeux
 · Logiciels
 · Magazines
 · Divers


Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Logiciels
 · Jeux
 · Scène démo
 · Divers


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


A Propos

A propos d'Obligement

A Propos


Contact

David Brunet

Courriel

 


Dossier : La compression de données avec l'algorithme de Huffman
(Article écrit par Emmanuel Hocdet et extrait d'Amiga News Tech - mai 1992)


Un des deux plus puissants algorithmes de compactage, avec LZW, n'est autre que celui de Huffman que nous nous proposons d'étudier aujourd'hui.

Cet algorithme porte le nom du mathématicien qui l'a mis au point, vous l'aurez deviné : l'honorable monsieur Huffman. Attendez-vous donc à trouver un peu de mathématiques dans le principe même de l'algorithme. Celui-ci risque de paraître peu clair au premier abord, mais le jeu en vaut la chandelle. Pour preuve, tous les logiciels d'archivage, à ma connaissance, l'utilisent. Et pour cause : il apparaît comme un complément très intéressant à LZW puisqu'il permet de gagner en moyenne entre 20 et 30% sur n'importe quel fichier, même déjà compacté avec cette méthode. Tout cela bien sûr au détriment de la vitesse.

Nous verrons les raisons de ces performances par la suite, avec l'explication détaillée de l'algorithme d'Huffman. Son implémentation sera aussi largement abordée ici.

Prise de contact

Avec Huffman, nous avons affaire à une méthode de compression statistique au niveau des octets (aïe, voilà les maths qui rappliquent à fond la caisse...).

Le but de l'algorithme est de coder chaque caractère par le plus petit nombre de bits possible. Je m'explique : chaque fichier est composé d'une série d'octets de taille fixe (8 bits en l'occurrence). Si l'on pouvait attribuer une taille variable de bits pour chaque octet en fonction du nombre de fois qu'il se répète dans le fichier (deux ou trois bits pour un caractère possédant une fréquence élevée, plus de huit si la fréquence est faible), le gain serait théoriquement optimal. L'algorithme de Huffman tente d'obtenir ce résultat à partir de la composition propre des données à traiter, quelle qu'elle soit.

La fréquence des 256 octets répartis dans un fichier est obtenue en parcourant les données caractère par caractère, la somme de toutes les fréquences devant donc correspondre à la taille en octets du fichier. Il est aussi possible de travailler avec les probabilités d'apparition de chaque caractère, de telle sorte que pour un octet "i" quelconque, Probabilité(i)=Fréquence(i)/Taille. En multipliant le résultat par 100, on obtient un pourcentage certainement plus parlant.

Pour en finir avec les maths, sachez qu'à ce stade du traitement, il est possible de connaître approximativement le nombre de bits minimum que prendra le fichier compacté grâce à l'entropie (fig. 1), le logarithme étant en base deux. Si l'entropie est supérieure à la taille du fichier à traiter, ce n'est pas la peine de le compresser.

compression des données
Figure 1

Les nouveaux codes des 256 caractères, une fois déterminés, doivent être rangés dans une table stockée dans le fichier destination. Il faut donc tenir compte de celle-ci dans la taille finale du fichier. La nécessité de parcourir la totalité des données avant de commencer la compression ne permet pas de coder les caractères à la volée comme avec LZW, ce qui implique une relative raideur de traitement.

Notion d'arbre binaire

Une fois les fréquences de chaque caractère déterminées, on peut se demander, à juste titre, comment il est possible de modifier le code d'un caractère et comment l'ordinateur peut s'y retrouver si ces codes possèdent une taille de bits variable. C'est là qu'intervient l'arbre binaire.

Pour bien assimiler le principe, prenons un exemple simple de construction d'un arbre. Un fichier comporte huit caractères différents de fréquence identique : il apparaît alors judicieux de leur attribuer un code sur 3 bits, puisque 21*3=8. Par exemple : 0=000, 0=001, M=010, P=011, A=100, R=101, S=110, E=111. Ce codage peut aussi être présenté sous la forme d'un arbre binaire (fig. 2). Les branches allant vers la gauche sont étiquetées à 0 et celles allant vers la droite à 1.

compression des données
Figure 2

Pour déterminer le code d'un caractère, il suffit de parcourir l'arbre depuis la racine jusqu'au caractère considéré et de prendre en compte chaque étiquette rencontrée. Le compactage d'une chaîne de caractères s'effectue alors comme dans l'exemple ci-dessous :

P	A	S	M	A	P	O	M	M	E
011	100	110	010	100	011	001	010	010	111

L'arbre est plus difficile à mettre en place lorsque les fréquences relatives à chaque caractère varient.

Dans un fichier, il est rare qu'un caractère ne se distingue pas des autres par sa fréquence d'apparition. La longueur de son code de compactage pourrait alors être judicieusement choisie entre 1 et 3 bits. Au second de la liste on affecte alors un code sur 2 ou 3 bits par exemple, et ainsi de suite. L'arbre construit à partir de ces codes se décompose en branches de longueurs inégales (fig. 3). Bien sûr, ce choix est complètement arbitraire, et ne peut donner un résultat optimal. Il reste cependant correct. Le problème est donc de créer, à partir de toutes les fréquences, l'arbre le mieux adapté aux données. Les codes ainsi obtenus doivent théoriquement être les meilleures réductions d'octets du contexte. C'est ce que tente de faire l'arbre de Huffman.

compression des données
Figure 3

L'arbre de Huffman

L'algorithme de Huffman utilise à la base la fréquence de chaque caractère, puis la somme de deux fréquences, et ainsi de suite pour arriver à une fréquence égale à la taille du fichier à compresser. Pour mieux comprendre la suite de l'explication, il est conseillé de se reporter au tableau explicatif de la figure 4.

compression des données
Figure 4

La recherche s'effectue en premier lieu sur les fréquences les moins élevées afin de déterminer les caractères, ou les groupes de caractères les moins courants. Les deux fréquences ainsi trouvées sont additionnées. Les caractères auxquels ils correspondent sont associés afin de rivaliser avec la fréquence des autres caractères. Un nouveau noeud de l'arbre, regroupant deux branches, est créé. Il a pour code la nouvelle fréquence, et représente une série de sous-branches aboutissant à un caractère. Ceux-ci n'apparaissent évidemment plus que de manière implicite. L'opération est ainsi répétée jusqu'à ce qu'il n'y est plus qu'une fréquence (égale à la taille du fichier).

A partir de là, il est aisé d'obtenir le code compressé de chaque caractère. En se positionnant à la racine de l'arbre, on remonte petit à petit vers le caractère afin de stocker la direction de chaque noeud rencontré. Par exemple, bit à 0 pour la gauche et bit à 1 pour la droite.

Compression et décompression

Le code de chaque caractère étant déterminé par l'arbre, il devient aisé de compresser le fichier précédemment traité. Par une lecture linéaire, on remplace chaque donnée composée de 8 bits par son code de taille variable et on le stocke dans la destination. Il ne faut pas oublier d'y inclure l'arbre, ou bien uniquement la table de conversion, moins encombrante.

Une remarque importante : chaque code est unique, sinon la décompression ne pourrait pas s'effectuer correctement. La raison se situe dans la base même de l'arbre. Il n'existe qu'un et un seul chemin pour arriver à une terminaison (le caractère). La décompression passe donc obligatoirement par la reconstitution de l'arbre à partir de la table de conversion.

La source à décompacter est traitée bit à bit. On se positionne à la racine de l'arbre. Suivant la valeur du bit en entrée, on remonte noeud par noeud dans l'arbre jusqu'à la terminaison correspondante. Le caractère ainsi trouvé est sauvegardé dans la destination et l'opération est répétée jusqu'à la reconstitution du fichier d'origine.

Mise en oeuvre

L'utilisation des listes chaînées est, à mon avis, l'unique moyen valable permettant la construction de l'arbre d'Huffman. La mise en place de cet arbre n'intervenant qu'une seule fois dans le programme, il serait judicieux de programmer cette partie en C, beaucoup plus simple à mettre en oeuvre. Dans cette optique, il me semble nécessaire de différencier les fréquences et les caractères associés à leur code.

Les fréquences, triées au fur et à mesure, sont le premier maillon d'une liste de caractères associés à leur codes. Ces derniers pourront ainsi, après la création d'un noeud, être directement complétés. Les deux fréquences considérées sont alors additionnées et leurs chaînes concaténées.

La mise en oeuvre de l'algorithme de substitution caractère-code ressemble à celle de LZW pour les chaînes de caractères, sauf qu'ici le nombre de bits à insérer dans le fichier de destination varie constamment. De sa rapidité dépendra directement celle de l'algorithme de compression.

La décompression est, quant à elle, beaucoup plus délicate. En effet, après avoir reconstitué l'arbre d'origine, il faut prendre les données bit à bit et remonter l'arbre d'Huffman noeud par noeud, ce qui créée une quantité importante d'instructions et d'accès mémoire pour décompresser un caractère. Le programme doit donc être particulièrement soigné et rapide : l'assembleur est de rigueur.

Pour les heureux possesseurs d'un 68030, la mémoire cache fera office de turbo en stockant l'arbre, sans cesse sollicité.

Il existe aussi un dérivé de cet algorithme : Huffman à la volée, qui comme son nom l'indique, permet une compression à la volée. Nous le verrons peut-être dans un prochain article.

Le programme suivant en lui-même est composé de cinq fichiers :
  • global.h, contenant les définitions communes.
  • main.c, le fichier principal.
  • compression.c, la routine de compression.
  • decompression.c, la routine de décompression.
  • huffasm.s, deux routines assembleur.
Pour la compilation, l'assemblage et l'édition de liens, il est fortement conseillé d'utiliser le makefile proposé ici. Sinon, effectuez les commandes suivantes :

lc -0 main.c
lc -0 compression.c
lc -0 decompression.c
genim2 -L -o huffasm   (si vous avez Devpac 2)
blink LIB:c.o main.o compression.o decompression.o huffasm.o
          TO Huffman
          LIBRARY LIB:lc.lib,LIB:amiga.lib

Listing 1 : main.c

/*-------------------------------------------------------------*/
/*      Algorithme de compression de type Huffman              */
/*      Amiga-News-Tech 1992                                   */
/*      Par Emmanuel Hocdet, Mai 1992                          */
/*-------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include "global.h"

extern UBYTE Compression (char**)   ;
extern UBYTE Decompression (char**) ;

char     *Header = {"HUF"}	;

int main(int argc, char **argv)
{
   FILE  *fp	;
   char  *HeaderTest = {"   "}   ;
   char  *Messages[] = {
                  "Well done.\n",
                  "Usage: HUFFMAN <source> <desination>\n",
                  "Pas assez de mémoire.\n",
                  "Impossible d'ouvrir le fichier source.\n",
                  "Impossible d'ouvrir le fichier destination.\n" };

   if (argc < 3)
   {
      printf ("%s", Messages[1]) ;
      exit(0)	;
   }

   if (! (fp = fopen(argv[1], "r")) )
   {
       printf ("%s", Messages[3]) ;
       exit(0) ;
   }
   fread (HeaderTest, sizeof(char), 3, fp)	;
   fclose (fp)	;
   if (strcmp (Header, HeaderTest)  )
      printf ("%s", Messages[Compression (argv)]   )  ;
   else
       printf ("%s", Messages[Decompression (argv)]   )  ;
}

Listing 2 : compression.c

/*----------------------------------------------------------*/
/*       Routine de compression Huffman : compression.c     */
/*----------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "global.h"

typedef  struct Tronc   TRONC	;
typedef  struct Branche BRANCHE	;

struct Tronc
{
   ULONG    NbrFeuilles	;        /* fréquence */
   BRANCHE  *Noeud	;
   TRONC    *Suivant	;
}  ;

struct Branche
{
   UBYTE    Feuille	;           /* octet */
   UBYTE    LongBourgeon	;     /* Longueur du code */
   ULONG    Bourgeon	;           /* Nouveau code */
   BRANCHE  *Noeud	;
}	;

extern UBYTE * __asm CompressASM (
	            register __a4 UBYTE *,
               register __a5 UBYTE *,
               register __a6 BRANCHE *,
               register __d7 ULONG )   ;

extern   char * Header;

UBYTE Compression(char **argv)
{
   FILE     *fp;
   TRONC    *Foret, *PtForet, *StartForet, *TempStart	;
   BRANCHE  *Arbre, *PtArbre	;
   UBYTE    *Buffer, *PtSource, *PtDestination, NbrBourgeon	;
   ULONG    TailleSource, Temp, *PtLong	;
   int      i, j	;

   if (! (fp = fopen(argv[1], "r")) )
       return(3) ;
   fseek (fp, 0, 2)	;
   TailleSource = ftell (fp)	;
   fseek (fp, 0, 0)	;
   Buffer = malloc (TailleSource + AddBuf  * sizeof(char) )	;
   if (!Buffer)
      return (2);
   PtSource = Buffer + AddBuf	;
   fread (PtSource, sizeof(UBYTE), TailleSource, fp)	;
   fclose (fp)	;

   Foret = (TRONC *) malloc ( 256 * sizeof(TRONC) )	;
   if (!Foret)
      return (2);
   Arbre = (BRANCHE *) malloc ( 256 * sizeof(BRANCHE) )	;
   if (!Arbre)
      return (2);

/*----------------------------------------------------------*/
/*                   Création de l'arbre                    */
/*----------------------------------------------------------*/

/* Initialisation de la liste des troncs composant la foret */
/*    avec création des liens entre chaque élément          */
/*    (liste simplement chainée)                            */
/*    et création d'un lien avec la branche correspondante  */
/* En même temps initialisation de la liste des branches    */
/*    la créations des liens entre chaque élément se fera   */
/*    par la suite.                                         */

   PtArbre = Arbre	;
   for (i = 0; i < 256; i++)
   {
      Foret[i].NbrFeuilles = 0	;
      Foret[i].Noeud = PtArbre++	;
      Foret[i].Suivant = &Foret[i+1]	;
      Arbre[i].Feuille = i	;
      Arbre[i].LongBourgeon = 0	;
      Arbre[i].Bourgeon = 0	;
      Arbre[i].Noeud = NULL	;
   }
   Foret[255].Suivant = NULL	;

/*  Scaning des données à compresser pour déterminer la     */
/*  fréquence de chaque octet.                              */

   for (PtSource = Buffer + AddBuf	;
        PtSource < Buffer + AddBuf + TailleSource	;
        PtSource++   )
      (Foret[*PtSource]).NbrFeuilles += 1	;

/*  Trie à bulles sur la liste des tronc sans utiliser la   */
/*   liste chainée pour des questions de facilités et de    */
/*   rapididés. Seuls les valeurs spécifiques des éléments  */
/*   de type tronc sont échangés.                           */

   for (i =0; i < 255; i++)
      for (j = 255; j > i; j--)
         if (Foret[j].NbrFeuilles < Foret[j-1].NbrFeuilles)
         {
            Swap (Foret[j].NbrFeuilles,
                  Foret[j-1].NbrFeuilles, Temp)	;
            Swap (Foret[j].Noeud,
                  Foret[j-1].Noeud, PtArbre)	;
         }

/*  Pointer au premier élément dont la fréquence est        */
/*  différante de zéro.                                     */

   for (StartForet = Foret, NbrBourgeon = 255	;
        !StartForet -> NbrFeuilles	;
        StartForet++, NbrBourgeon-- )	;

/*----------------------------------------------------------*/
/*                Construction de l'arbre                   */
/*----------------------------------------------------------*/

   while (StartForet -> Suivant)
   {
      for (PtArbre = StartForet->Noeud	;
           PtArbre	;
           PtArbre = PtArbre->Noeud )
      {
         PtArbre -> LongBourgeon += 1	;
         PtArbre -> Bourgeon = (PtArbre -> Bourgeon << 1) + 1	;
      }

      for (PtArbre = StartForet->Suivant->Noeud	;
           PtArbre->Noeud	;
           PtArbre = PtArbre->Noeud )
      {
         PtArbre -> LongBourgeon += 1	;
         PtArbre -> Bourgeon = (PtArbre -> Bourgeon << 1)	;
      }
      PtArbre -> LongBourgeon += 1	;
      PtArbre -> Bourgeon = (PtArbre -> Bourgeon << 1)	;
      PtArbre -> Noeud  = StartForet -> Noeud	;
      StartForet->Suivant->NbrFeuilles += StartForet->NbrFeuilles;
      StartForet = StartForet -> Suivant	;

/*  Trie par sélection échange du nouvel élément            */

      if (TempStart = StartForet -> Suivant)
         if (StartForet->NbrFeuilles > TempStart->NbrFeuilles)
         {
            for (PtForet = TempStart	;
                 (PtForet -> Suivant) &&
                 (StartForet -> NbrFeuilles >
                     PtForet -> Suivant -> NbrFeuilles)	;
                 PtForet = PtForet -> Suivant   )	;

            StartForet -> Suivant = PtForet -> Suivant	;
            PtForet -> Suivant = StartForet	;
            StartForet = TempStart	;
         }
   }

/*-------------------------------------------------------------*/
/* Affichage des caractères rencontrés avec leur nouveau code  */
/* ainsi que la longueur de ces nouveaux codes  (optionnel)    */
/*-------------------------------------------------------------*/

   for (PtArbre = StartForet -> Noeud  ;
        PtArbre	;
        PtArbre = PtArbre -> Noeud  )
   {
      printf("octet %3d :   long = %2d   code = ",
              PtArbre -> Feuille,
              PtArbre -> LongBourgeon)	;
      Temp = PtArbre -> Bourgeon	;
      for (i = 0; i < PtArbre -> LongBourgeon; i++, Temp >>= 1)
         printf("%d", Temp & 1)	;
      printf("\n")	;
   }

/*----------------------------------------------------------*/
/*                 Sauvegarde de l'arbre                    */
/*----------------------------------------------------------*/

   PtDestination = Buffer	;
   strcpy (PtDestination, Header)	;
   PtDestination += strlen(PtDestination)	;
   *PtDestination++ = NbrBourgeon	;
   PtLong = (ULONG *) PtDestination ;
   *PtLong++ = TailleSource   ;
   PtDestination = (UBYTE *) PtLong ;


   for (PtArbre = StartForet -> Noeud	;
        PtArbre	;
        PtArbre = PtArbre -> Noeud  )
   {
      Temp = PtArbre -> Bourgeon	;
      *PtDestination++ = PtArbre -> Feuille  ;
      *PtDestination++ = PtArbre -> LongBourgeon   ;
      switch (PtArbre -> LongBourgeon >> 3)
      {
         case 3 : *PtDestination++ = (UBYTE) (Temp >> 24);
         case 2 : *PtDestination++ = (UBYTE) (Temp >> 16);
         case 1 : *PtDestination++ = (UBYTE) (Temp >> 8) ;
         case 0 : *PtDestination++ = (UBYTE) Temp  ;
      }
   }

/*----------------------------------------------------------*/
/*                Compression des données                   */
/*----------------------------------------------------------*/

   PtSource = Buffer + AddBuf	;
   PtDestination = CompressASM ( PtDestination,
                                 PtSource,
                                 Arbre,
                                 TailleSource)	;

/*----------------------------------------------------------*/
/*             Sauvegarde des données compressées           */
/*----------------------------------------------------------*/

   if (! (fp = fopen(argv[2], "w")) )
       return(4) ;
   fwrite ( Buffer, sizeof(UBYTE), PtDestination - Buffer, fp)	;
   fclose(fp)	;

   free(Foret)	;
   free(Arbre)	;
   free(Buffer);

   return (0)  ;
}

Listing 3 : décompression.c

/*----------------------------------------------------------*/
/*     Routine de décompression Huffman : décompression.c   */
/*----------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "global.h"

typedef  struct Noeud   NOEUD ;

struct Noeud
{
   NOEUD  *droite ;
   NOEUD  *gauche ;
}  ;

extern __asm DecompressASM (
			register __a4 UBYTE *,
			register __a5 UBYTE *,
			register __a6 NOEUD *,
         register __d7 ULONG )   ;

extern  char * Header;

UBYTE Decompression (char **argv)
{
   FILE     *fp;
   NOEUD    *Arbre, *PtArbre, *Racine  ;
   UBYTE    NbrBourgeon, LongBourgeon, Feuille  ;
   UBYTE    *Buffer, *PtSource, *PtDestination ;
   ULONG    TailleDestination, TailleSource, Bourgeon;
   int      i, j  ;

   if (! (fp = fopen(argv[1], "r")) )
       return(3) ;
   fseek (fp, 0, 2)  ;
   TailleSource = ftell (fp)	;

   fseek (fp, 3, 0)  ;
   fread ( &NbrBourgeon, sizeof(UBYTE), 1, fp)   ;
   fseek (fp, 0, 1)  ;
   fread ( (UBYTE *) &TailleDestination, sizeof(ULONG), 1, fp)   ;
   fseek (fp, 0, 1)  ;
   TailleSource -= ftell (fp) ;
   Buffer = malloc (TailleDestination + AddBuf  * sizeof(char) )	;
   if (!Buffer)
      return (2);
   PtSource = Buffer + TailleDestination + AddBuf - TailleSource;
   fread (PtSource, sizeof(UBYTE), TailleSource, fp)	;
   fseek (fp, 0, 0)  ;
   fclose (fp) ;

   Arbre = (NOEUD *) calloc (NbrBourgeon * 2 + 1, sizeof(NOEUD));
   if (!Arbre)
      return (2);
   PtArbre = Arbre + 1;

/*----------------------------------------------------------*/
/*                 Reconstitution de l'arbre                */
/*----------------------------------------------------------*/

   for (i = 0; i <= NbrBourgeon; i++)
   {
      Racine = Arbre;
      Bourgeon = 0   ;
      Feuille = *PtSource++  ;
      LongBourgeon = *PtSource++  ;
      switch (LongBourgeon >> 3)
      {
         case 3 : Bourgeon |= ((ULONG) *PtSource++) << 24 ;
         case 2 : Bourgeon |= ((ULONG) *PtSource++) << 16 ;
         case 1 : Bourgeon |= ((ULONG) *PtSource++) << 8  ;
         case 0 : Bourgeon |= (ULONG) *PtSource++ ;
      }

      for (j = 0; j < LongBourgeon; j++)
      {
         if (Bourgeon & 1)
         {
            if (Racine -> droite == NULL)
               Racine -> droite = PtArbre++  ;
            Racine = Racine -> droite  ;
         }
         else
         {
            if (Racine -> gauche == NULL)
               Racine -> gauche = PtArbre++  ;
            Racine = Racine -> gauche ;
         }
         Bourgeon >>= 1 ;     /* bit suivant */
      }
      Racine -> droite = 0   ;
      Racine -> gauche = Feuille ;

/*  Le compilateur effectue un Warning sur la commande      */
/*  précédente. Pour éviter de perdre de la place en créant */
/*  une structure intermédiaire, la valeur de l'octet       */
/*  (Feuille) est strockée directement dans le pointeur     */
/*  gauche, le pointeur droite étant dans ce cas null       */

   }

/*----------------------------------------------------------*/
/*                Decompression des données                 */
/*----------------------------------------------------------*/

   PtDestination = Buffer;
   DecompressASM ( PtDestination,
                   PtSource,
                   Arbre,
                   TailleDestination)	;

/*----------------------------------------------------------*/
/*             Sauvegarde des données décompressées         */
/*----------------------------------------------------------*/

   if (! (fp = fopen(argv[2], "w")) )
       return(4) ;
   fwrite ( Buffer, sizeof(UBYTE), TailleDestination, fp)   ;
   fclose(fp)	;

   free(Arbre);
   free(Buffer);
   return (0)  ;
}

Listing 4 : global.h

typedef  unsigned long int  ULONG	;
typedef  unsigned char  UBYTE	;

#define AddBuf  1024*8

/* invercer deux valeurs */
#define Swap(a, b, c)  { (c) = (a);  (a) = (b);  (b) = (c); }

Listing 5 : huffman.asm

* structure Branche	(pour la compression)
	RSRESET
Feuille		rs.b  1
LongBourgeon	rs.b  1
Bourgeon		rs.l  1
Branche		rs.l  1
Struct_Branche	rs.l  0

	
* structure Noeud		(pour la décompression)
	RSRESET
droite		rs.l  1
gauche		rs.b  3
feuille		rs.b  1


		SECTION     Huffman,CODE

	XDEF  _CompressASM
	XDEF  _DecompressASM

***
*** Routine de compression Huffman
***

_CompressASM
	* a4 = Destination
	* a5 = Source
	* a6 = Arbre
	* d7 = Nbrs d'octets à traiter

CompRegs	REG     d2-d7/a3

	movem.l CompRegs,-(a7)

	move.l  a4,d4
	addq.l  #1,d4
	and.l   #-2,d4
	move.l  d4,a4

	lea     Mul(pc),a3
	moveq   #1,d4
suivant
	moveq   #0,d5
	moveq   #0,d6
	move.b  (a5)+,d5
	add     d5,d5
	move    (a3,d5),d5
	move.l  Bourgeon(a6,d5),d2
	move.b  LongBourgeon(a6,d5),d6
	subq    #1,d6

code	lsr.l   #1,d2
	addx    d3,d3
	add     d4,d4
	bne.s   pasplein
	addx    d4,d4
	move    d3,(a4)+
pasplein	dbf     d6,code
	
	subq.l  #1,d7
	bne.s   suivant

	cmp     #1,d4
	beq.s   sort
fincompteur add     d3,d3
	add     d4,d4
	bne.s   fincompteur
	move    d3,(a4)+
sort
	move.l  a4,d0		* valeur à retourner
	movem.l (a7)+,CompRegs
	rts

***
*** Routine de décompression Huffman
***

_DecompressASM
	* a4 = Destination
	* a5 = Source
	* a6 = Arbre
	* d7 = Nbrs d'octets à traiter

DecompRegs REG     d5-d7/a3

	movem.l  DecompRegs,-(a7)

	move.l  a5,d6
	addq.l  #1,d6
	and.l   #-2,d6
	move.l  d6,a5

	lea	(a6),a3
	move	(a5)+,d5
	moveq	#15,d6
decode	
	add	d5,d5
	bcc.s	Agauche
Adroite
	move.l	droite(a3),a3
	tst.l	droite(a3)
	beq.s	Terminaison
	dbf	d6,decode
	move	(a5)+,d5
	moveq	#15,d6
	bra.s	decode
Agauche
	move.l	gauche(a3),a3
	tst.l	droite(a3)
	beq.s	Terminaison
	dbf	d6,decode
	move	(a5)+,d5
	moveq	#15,d6
	bra.s	decode
Terminaison
	move.b	feuille(a3),(a4)+
	lea	(a6),a3
	subq.l  #1,d7
	beq.s	fin
	dbf	d6,decode
	move	(a5)+,d5
	moveq	#15,d6
	bra.s	decode

fin	movem.l  (a7)+,DecompRegs	
	rts

***
*** Table permettant de pointer sur le bon élément de l'arbre
***

Mul
A set 0
	rept 256
	dc.w  A*Struct_Branche
A set A+1
	endr

	end

Listing 6 : makefile

#----- Makefile pour le comp./decomp. Huffman

CompilC = lc
Linker  = Blink lib:c.o
Linker_Flags =  lib lib:lc.lib lib:amiga.lib BUFSIZE 1024 VERBOSE

# Transformation Rules
.c.o:
   lc  -O $*

.s.o:
   genim2 -L -o $*

# File dependencies

programme : huffman

main.o : main.c global.h
compression.o : compression.c global.h
decompression.o : decompression.c global.h
huffASM.o : huffASM.s

huffman : main.o compression.o decompression.o huffASM.o
        $(Linker) main.o \
                  compression.o \
                  decompression.o \
                  huffASM.o \
                  TO huffman $(Linker_Flags)


[Retour en haut] / [Retour aux articles]