Suivez-nous sur X
|
|
|
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
|
|
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
|
|
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
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
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.
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.
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.
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.
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)
|
|
