/*************************************************************************************************************************************/
/* */
/* C O D A G E D E H U F F M A N ' HUF ' E T I N V E R S E : */
/* */
/* */
/* Nota : */
/* */
/* Ce module est inspire de 'v $xtc/HuffmanCoding.01$I' */
/* qui a servi a sa mise au point... */
/* */
/* */
/* Author of '$xrC/CompressionDeCompression_HuffmanCoding.01$vv$I' : */
/* */
/* Jean-Francois Colonna (LACTAMME, 20151227143815). */
/* */
/*************************************************************************************************************************************/
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N G E N E R A L E S : */
/* */
/*************************************************************************************************************************************/
Logical HUF_Utiliser=VRAI;
Logical HUF_EditerFrequences=FAUX;
Logical HUF_EditerArbre=FAUX;
Logical HUF_EditerCodesDeHuffman=FAUX;
/* Indicateurs de controle des editions... */
#define PREMIER_CARACTERE \
INDEX0
#define DERNIER_CARACTERE \
MASKO
#define NOMBRE_DE_CARACTERES \
((DERNIER_CARACTERE-PREMIER_CARACTERE)+1)
/*************************************************************************************************************************************/
/* */
/* S T R U C T U R E S F R E Q U E N T I E L L E S D E S C A R A C T E R E S : */
/* */
/*************************************************************************************************************************************/
Entier HUF_FrequencesDOccurenceDesCaracteres[NOMBRE_DE_CARACTERES];
Entier HUF_DefinitionRedondanteDesCodesDesCaracteres[NOMBRE_DE_CARACTERES];
Entier HUF_NumerosDesNoeudsDeRangementDesCaracteres[NOMBRE_DE_CARACTERES];
Entier HUF_PremierCaractere=PREMIER_CARACTERE;
Entier HUF_DernierCaractere=DERNIER_CARACTERE;
/* On notera que tout est defini en 'int' afin d'eviter des debordements et des problemes */
/* de signe. On notera de plus que la definition des codes de caracteres n'est pas */
/* redondante avec les index d'acces a cause des permutations qui sont effectuees sur */
/* ces tableaux... */
#define HUF_TYPE_CaractereAssociesAuCodeBinaire \
CHAR
#define HUF_TYPE_LongueurDuCodeBinaire \
CHAR
#define HUF_TYPE_CodeBinaire \
Entier
#define HUF_SIZE_CodeBinaire \
(HUF_NombreDeCodes \
*(SIZEOF(HUF_TYPE_CaractereAssociesAuCodeBinaire) \
+SIZEOF(HUF_TYPE_LongueurDuCodeBinaire) \
+SIZEOF(HUF_TYPE_CodeBinaire) \
) \
+SIZEOF(HUF_NombreDeCodes) \
)
HUF_TYPE_CaractereAssociesAuCodeBinaire HUF_CaractereAssociesAuCodeBinaire[NOMBRE_DE_CARACTERES];
HUF_TYPE_LongueurDuCodeBinaire HUF_LongueurDuCodeBinaire[NOMBRE_DE_CARACTERES];
HUF_TYPE_CodeBinaire HUF_CodeBinaire[NOMBRE_DE_CARACTERES];
/* Definition des codes entropiques de Huffman. */
Entier HUF_NombreDeCodes;
HUF_TYPE_CaractereAssociesAuCodeBinaire HUF_CaractereAssociesAuCodeBinaireCompacte[NOMBRE_DE_CARACTERES];
HUF_TYPE_LongueurDuCodeBinaire HUF_LongueurDuCodeBinaireCompacte[NOMBRE_DE_CARACTERES];
HUF_TYPE_CodeBinaire HUF_CodeBinaireCompacte[NOMBRE_DE_CARACTERES];
/* Definition des codes entropiques de Huffman apres compactage. */
Entier HUF_NombreDeBitsApresCodage;
Entier HUF_NombreDOctetsApresDecodage;
/* Afin de faciliter l'exploitation des resultats... */
Entier HUF_Codage_LongueurAvant;
Entier HUF_Codage_LongueurApres;
Entier HUF_Decodage_LongueurAvant;
Entier HUF_Decodage_LongueurApres;
/* Afin de faciliter des verifications de coherence... */
#define NOEUD_INEXISTANT \
(INDEX0-1)
#define CARACTERE_INUTILISE \
0
#define CODE_DE_HUFFMAN_INUTILISE \
0
/*************************************************************************************************************************************/
/* */
/* A N A L Y S E F R E Q U E N T I E L L E D E S C A R A C T E R E S : */
/* */
/*************************************************************************************************************************************/
void F_HUF_GenerationFrequences(CHAR chaine[],Entier longueur)
{
Entier index;
HUF_Codage_LongueurAvant = longueur;
for (index=INDEX0 ; index<=NombreVersIndex(longueur) ; index++)
{
HUF_FrequencesDOccurenceDesCaracteres[chaine[index]]++;
/* La "frequence" est obtenu par un simple comptage des caracteres... */
}
}
#define D_HUF_Permutation(tableau,index1,index2) \
{ \
Entier SauvegardeTemporaire=tableau[index1]; \
tableau[index1] = tableau[index2]; \
tableau[index2] = SauvegardeTemporaire; \
}
void F_HUF_TriCroissantDesFrequencesDesCaracteres()
{
Entier index_de_fin;
for (index_de_fin=(HUF_DernierCaractere-1) ; index_de_fin>=HUF_PremierCaractere ; index_de_fin--)
{
Entier index_de_debut;
for (index_de_debut=HUF_PremierCaractere ; index_de_debut<=index_de_fin ; index_de_debut++)
{
if (HUF_FrequencesDOccurenceDesCaracteres[index_de_debut]
> HUF_FrequencesDOccurenceDesCaracteres[index_de_debut+1]
)
{
D_HUF_Permutation(HUF_FrequencesDOccurenceDesCaracteres
,index_de_debut
,index_de_debut+1
);
D_HUF_Permutation(HUF_DefinitionRedondanteDesCodesDesCaracteres
,index_de_debut
,index_de_debut+1
);
D_HUF_Permutation(HUF_NumerosDesNoeudsDeRangementDesCaracteres
,index_de_debut
,index_de_debut+1
);
/* Cette echange conserve l'ordre des elements possedant la meme "clef"... */
}
else
{
}
}
}
for (index_de_fin=HUF_PremierCaractere ; index_de_fin<=HUF_DernierCaractere ; index_de_fin++)
{
if (HUF_FrequencesDOccurenceDesCaracteres[index_de_fin] == CARACTERE_INUTILISE)
{
HUF_PremierCaractere = index_de_fin+1;
/* Afin de ne parcourir que les entrees utiles (dont les frequences sont donc differentes */
/* de 'CARACTERE_INUTILISE'...). On notera que 'DernierCaractere' ne bouge pas ; il vaut */
/* en effet toujours 'DERNIER_CARACTERE'... */
}
else
{
}
}
}
#define CARACTERE_INEXISTANT \
(PREMIER_CARACTERE-1)
#define PREMIER_CARACTERE_EDITABLE \
0x20
#define DERNIER_CARACTERE_EDITABLE \
0x7e
void F_HUF_EditionDesFrequencesDesCaracteres()
{
Entier index;
if (HUF_EditerFrequences == VRAI)
{
printf("HUF/Frequences :\n");
for (index=HUF_PremierCaractere ; index<=HUF_DernierCaractere ; index++)
{
if (HUF_FrequencesDOccurenceDesCaracteres[index] != CARACTERE_INUTILISE)
{
if (HUF_DefinitionRedondanteDesCodesDesCaracteres[index] > CARACTERE_INEXISTANT)
{
if ( ((CHAR)HUF_DefinitionRedondanteDesCodesDesCaracteres[index]
>= PREMIER_CARACTERE_EDITABLE
)
&& ((CHAR)HUF_DefinitionRedondanteDesCodesDesCaracteres[index]
<= DERNIER_CARACTERE_EDITABLE
)
)
{
printf("caractere='%c' (0x%02"For16") frequence=%"For10" noeud=%"For10"\n"
,(CHAR)HUF_DefinitionRedondanteDesCodesDesCaracteres[index]
,HUF_DefinitionRedondanteDesCodesDesCaracteres[index]
,HUF_FrequencesDOccurenceDesCaracteres[index]
,HUF_NumerosDesNoeudsDeRangementDesCaracteres[index]
);
}
else
{
printf("caractere= (0x%02"For16") frequence=%"For10" noeud=%"For10"\n"
,HUF_DefinitionRedondanteDesCodesDesCaracteres[index]
,HUF_FrequencesDOccurenceDesCaracteres[index]
,HUF_NumerosDesNoeudsDeRangementDesCaracteres[index]
);
}
/* Cas des "vrais" caracteres... */
}
else
{
printf("* frequence=%"For10" noeud=%"For10"\n"
,HUF_FrequencesDOccurenceDesCaracteres[index]
,HUF_NumerosDesNoeudsDeRangementDesCaracteres[index]
);
/* Cas des caracteres de type "cumul"... */
}
}
else
{
}
}
}
else
{
}
}
/*************************************************************************************************************************************/
/* */
/* G E S T I O N D E L ' A R B R E D E S C O D E S D E H U F F M A N : */
/* */
/*************************************************************************************************************************************/
#define NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE \
(2*NOMBRE_DE_CARACTERES)
#define PREMIER_NOEUD_DE_L_ARBRE \
INDEX0
#define DERNIER_NOEUD_DE_L_ARBRE \
NombreVersIndex(HUF_IdentiteDuNoeudCourantDeLArbre)
#define SUIVANT_INEXISTANT \
(PREMIER_NOEUD_DE_L_ARBRE-1)
#define HUF_TYPE_ArbreCaracteresEnChaqueNoeud \
Entier
#define HUF_TYPE_ArbreChainageAGauche \
Entier
#define HUF_TYPE_ArbreChainageADroite \
Entier
/* On notera qu'en theorie le nombre d'octets necessaires devrait etre au plus : */
/* */
/* ArbreCaracteresEnChaqueNoeud 1 */
/* ArbreChainageAGauche 2 */
/* ArbreChainageADroite 2 */
/* */
/* mais qu'a cause des fonctions de mesure c'est actuellement (le 20160103103543) */
/* difficile a mettre en place... */
#define HUF_SIZE_Arbre \
(HUF_IdentiteDuNoeudCourantDeLArbre \
*(SIZEOF(HUF_TYPE_ArbreCaracteresEnChaqueNoeud) \
+SIZEOF(HUF_TYPE_ArbreChainageAGauche) \
+SIZEOF(HUF_TYPE_ArbreChainageADroite) \
) \
) \
/* On notera que 'ArbreFrequenceDesNoeuds' est inutile pour la mesure de 'K'... */
Entier HUF_ArbreFrequenceDesNoeuds[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
HUF_TYPE_ArbreCaracteresEnChaqueNoeud HUF_ArbreCaracteresEnChaqueNoeud[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
HUF_TYPE_ArbreChainageAGauche HUF_ArbreChainageAGauche[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
HUF_TYPE_ArbreChainageADroite HUF_ArbreChainageADroite[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
#define HUF_SIZE_IdentiteDuNoeudCourantDeLArbre \
SIZEOF(HUF_IdentiteDuNoeudCourantDeLArbre)
Entier HUF_IdentiteDuNoeudCourantDeLArbre=PREMIER_NOEUD_DE_L_ARBRE;
Entier HUF_RacineDeLArbre;
/* Definition de l'arbre de codage... */
#define D_HUF_MiseAJourArbre(frequence,caractere,ChainageAGauche,ChainageADroite) \
/* On notera qu'a GAUCHE se trouve la FREQUENCE MINIMALE... */ \
{ \
HUF_ArbreFrequenceDesNoeuds[HUF_IdentiteDuNoeudCourantDeLArbre] = frequence; \
HUF_ArbreCaracteresEnChaqueNoeud[HUF_IdentiteDuNoeudCourantDeLArbre] = caractere; \
HUF_ArbreChainageAGauche[HUF_IdentiteDuNoeudCourantDeLArbre] = ChainageAGauche; \
HUF_ArbreChainageADroite[HUF_IdentiteDuNoeudCourantDeLArbre] = ChainageADroite; \
\
if (HUF_IdentiteDuNoeudCourantDeLArbre < NombreVersIndex(NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE)) \
{ \
HUF_IdentiteDuNoeudCourantDeLArbre++; \
} \
else \
{ \
fprintf(stderr,"ERREUR(HUF) : Debordement de l'arbre.\n"); \
} \
}
void F_HUF_GenerationDeLArbre()
{
Logical ItererLaGenerationDeLArbre=VRAI;
while (ItererLaGenerationDeLArbre == VRAI)
{
Entier index;
Entier IndexFrequenceMinimaleGauche,FrequenceMinimaleGauche,CaractereGauche,NoeudFilsGauche;
Entier IndexFrequenceMinimaleDroite,FrequenceMinimaleDroite,CaractereDroite,NoeudFilsDroite;
Entier SommeDesFrequencesEnUnNoeud=0;
F_HUF_TriCroissantDesFrequencesDesCaracteres();
F_HUF_EditionDesFrequencesDesCaracteres();
/* Tri destine a garantir l'ordre des frequences... */
index=HUF_PremierCaractere;
while ( (HUF_FrequencesDOccurenceDesCaracteres[index] == CARACTERE_INUTILISE)
&& (index < HUF_DernierCaractere)
)
{
index++;
}
IndexFrequenceMinimaleGauche = index;
FrequenceMinimaleGauche= HUF_FrequencesDOccurenceDesCaracteres[IndexFrequenceMinimaleGauche];
CaractereGauche = HUF_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleGauche];
if (CaractereGauche != CARACTERE_INEXISTANT)
{
NoeudFilsGauche = HUF_IdentiteDuNoeudCourantDeLArbre;
HUF_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleGauche]
= NoeudFilsGauche;
D_HUF_MiseAJourArbre(FrequenceMinimaleGauche
,CaractereGauche
,SUIVANT_INEXISTANT
,SUIVANT_INEXISTANT
);
/* Creation d'une feuille de l'arbre (noeud donnant donc un caractere). */
}
else
{
NoeudFilsGauche = HUF_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleGauche];
/* Cas d'un noeud de cumul de l'arbre deja genere. */
}
SommeDesFrequencesEnUnNoeud = SommeDesFrequencesEnUnNoeud + FrequenceMinimaleGauche;
HUF_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleGauche] = CARACTERE_INEXISTANT;
HUF_FrequencesDOccurenceDesCaracteres[IndexFrequenceMinimaleGauche] = CARACTERE_INUTILISE;
/* Ainsi, ce caractere dont la frequence va etre cumule un peu plus loin disparait en */
/* quelque sorte de la liste des caracteres a traiter (via donc une frequence nulle). */
index=HUF_PremierCaractere;
while ( (HUF_FrequencesDOccurenceDesCaracteres[index] == CARACTERE_INUTILISE)
&& (index < HUF_DernierCaractere)
)
{
index++;
}
IndexFrequenceMinimaleDroite = index;
if (IndexFrequenceMinimaleGauche != IndexFrequenceMinimaleDroite)
{
FrequenceMinimaleDroite = HUF_FrequencesDOccurenceDesCaracteres[IndexFrequenceMinimaleDroite];
CaractereDroite = HUF_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleDroite];
if (FrequenceMinimaleGauche > FrequenceMinimaleDroite)
{
fprintf(stderr
,"ERREUR(HUF) : FreqMinGauche=%"For10" > FreqMinDroite=%"For10"\n"
,FrequenceMinimaleGauche
,FrequenceMinimaleDroite
);
}
else
{
}
if (CaractereDroite != CARACTERE_INEXISTANT)
{
NoeudFilsDroite = HUF_IdentiteDuNoeudCourantDeLArbre;
HUF_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleDroite]
= NoeudFilsDroite;
D_HUF_MiseAJourArbre(FrequenceMinimaleDroite
,CaractereDroite
,SUIVANT_INEXISTANT
,SUIVANT_INEXISTANT
);
/* Creation d'une feuille de l'arbre (noeud donnant donc un caractere). */
}
else
{
NoeudFilsDroite = HUF_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleDroite];
/* Cas d'un noeud de cumul de l'arbre deja genere. */
}
SommeDesFrequencesEnUnNoeud = SommeDesFrequencesEnUnNoeud + FrequenceMinimaleDroite;
HUF_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleDroite] = CARACTERE_INEXISTANT;
HUF_FrequencesDOccurenceDesCaracteres[IndexFrequenceMinimaleDroite] = SommeDesFrequencesEnUnNoeud;
/* Ainsi, ce caractere dont la frequence vient d'etre cumule est remplace par ce cumul... */
HUF_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleDroite]
= HUF_IdentiteDuNoeudCourantDeLArbre;
D_HUF_MiseAJourArbre(SommeDesFrequencesEnUnNoeud
,CARACTERE_INEXISTANT
,NoeudFilsGauche
,NoeudFilsDroite
);
/* Creation d'un noeud de cumul de l'arbre. */
}
else
{
ItererLaGenerationDeLArbre = FAUX;
}
}
HUF_RacineDeLArbre = HUF_IdentiteDuNoeudCourantDeLArbre-1;
}
void F_HUF_EditionDeLArbre()
{
if (HUF_EditerArbre == VRAI)
{
Entier index;
printf("HUF/EditionDeLArbre :\n");
for (index=PREMIER_NOEUD_DE_L_ARBRE ; index<=DERNIER_NOEUD_DE_L_ARBRE ; index++)
{
printf("noeud=%04"For10" frequence=%08"For10""
,index
,HUF_ArbreFrequenceDesNoeuds[index]
);
if (HUF_ArbreCaracteresEnChaqueNoeud[index] != CARACTERE_INEXISTANT)
{
printf(" caractere=0x%02"For16""
,HUF_ArbreCaracteresEnChaqueNoeud[index]
);
}
else
{
printf(" * ");
}
if (HUF_ArbreChainageAGauche[index] != NOEUD_INEXISTANT)
{
printf(" ChainageAGauche=%04"For10""
,HUF_ArbreChainageAGauche[index]
);
}
else
{
}
if (HUF_ArbreChainageADroite[index] != NOEUD_INEXISTANT)
{
printf(" ChainageADroite=%04"For10""
,HUF_ArbreChainageADroite[index]
);
}
else
{
}
printf("\n");
}
}
else
{
}
}
#define GAUCHE \
1
#define DROITE \
0
#define BASE2 \
2
void F_HUF_ParcoursRecursifDeLArbre(Entier racine,Entier CodeBinaire,Entier LongueurCodeBinaire)
{
if (racine != NOEUD_INEXISTANT)
{
if ( (HUF_ArbreChainageAGauche[racine] != NOEUD_INEXISTANT)
&& (HUF_ArbreChainageADroite[racine] != NOEUD_INEXISTANT)
)
{
if (LongueurCodeBinaire < (NBITMO-1))
{
F_HUF_ParcoursRecursifDeLArbre(HUF_ArbreChainageAGauche[racine]
,(BASE2*CodeBinaire)+GAUCHE
,LongueurCodeBinaire+1
);
F_HUF_ParcoursRecursifDeLArbre(HUF_ArbreChainageADroite[racine]
,(BASE2*CodeBinaire)+DROITE
,LongueurCodeBinaire+1
);
}
else
{
fprintf(stderr,"ERREUR(HUF) : Un code binaire est trop long.\n");
}
}
else
{
Entier caractere=HUF_ArbreCaracteresEnChaqueNoeud[racine];
Entier longueur=COND((LongueurCodeBinaire == 0),1,LongueurCodeBinaire);
/* Le forcage de la longueur 1 est destine au cas ou l'arbre se reduit a sa racine, ce qui */
/* signifie que la chaine de caracteres ne possede qu'une suite de caracteres identiques. */
HUF_LongueurDuCodeBinaire[caractere] = longueur;
HUF_CodeBinaire[caractere] = CodeBinaire;
if (caractere != HUF_CaractereAssociesAuCodeBinaire[caractere])
{
fprintf(stderr,"ERREUR(HUF) : Les tables de Huffman sont incoherentes.\n");
}
else
{
}
}
}
else
{
}
}
void F_HUF_CompactageDesCodesDeHuffman()
{
Entier index_1;
HUF_NombreDeCodes = 0;
for (index_1=PREMIER_CARACTERE ; index_1<=DERNIER_CARACTERE ; index_1++)
{
Entier LongueurCodeBinaire=HUF_LongueurDuCodeBinaire[index_1];
if (LongueurCodeBinaire != CODE_DE_HUFFMAN_INUTILISE)
{
Entier index_2;
HUF_NombreDeCodes++;
index_2=NombreVersIndex(HUF_NombreDeCodes);
HUF_CaractereAssociesAuCodeBinaireCompacte[index_2] = HUF_CaractereAssociesAuCodeBinaire[index_1];
HUF_LongueurDuCodeBinaireCompacte[index_2] = HUF_LongueurDuCodeBinaire[index_1];
HUF_CodeBinaireCompacte[index_2] = HUF_CodeBinaire[index_1];
}
else
{
}
}
}
void F_HUF_DeCompactageDesCodesDeHuffman()
{
Entier index_1;
DoIn(index_1,PREMIER_CARACTERE,DERNIER_CARACTERE)
{
mEGAL(ACCES_CHAINE(HUF_CaractereAssociesAuCodeBinaire,index_1),index_1);
mEGAL(ACCES_CHAINE(HUF_LongueurDuCodeBinaire,index_1),CODE_DE_HUFFMAN_INUTILISE);
mEGAL(HUF_CodeBinaire[index_1],CODE_DE_HUFFMAN_INUTILISE);
}
EDoI
DoIn(index_1,INDEX0,NombreVersIndex(HUF_NombreDeCodes))
{
Entier index_2;
mEGAL(index_2,HUF_CaractereAssociesAuCodeBinaireCompacte[index_1]);
mEGAL(ACCES_CHAINE(HUF_CaractereAssociesAuCodeBinaire,index_2),index_2);
mEGAL(ACCES_CHAINE(HUF_LongueurDuCodeBinaire,index_2),HUF_LongueurDuCodeBinaireCompacte[index_1]);
mEGAL(HUF_CodeBinaire[index_2],HUF_CodeBinaireCompacte[index_1]);
}
EDoI
}
/*************************************************************************************************************************************/
/* */
/* I N T I A L I S A T I O N S D I V E R S E S : */
/* */
/*************************************************************************************************************************************/
void F_HUF_Initialisations()
{
Entier index;
HUF_PremierCaractere=PREMIER_CARACTERE;
HUF_DernierCaractere=DERNIER_CARACTERE;
HUF_IdentiteDuNoeudCourantDeLArbre=PREMIER_NOEUD_DE_L_ARBRE;
for (index=HUF_PremierCaractere ; index<=HUF_DernierCaractere ; index++)
{
HUF_FrequencesDOccurenceDesCaracteres[index] = 0;
HUF_DefinitionRedondanteDesCodesDesCaracteres[index] = index;
HUF_NumerosDesNoeudsDeRangementDesCaracteres[index] = NOEUD_INEXISTANT;
HUF_CaractereAssociesAuCodeBinaire[index] = index;
HUF_LongueurDuCodeBinaire[index] = CODE_DE_HUFFMAN_INUTILISE;
HUF_CodeBinaire[index] = CODE_DE_HUFFMAN_INUTILISE;
}
}
/*************************************************************************************************************************************/
/* */
/* E D I T I O N D E S C O D E S D E H U F F M A N : */
/* */
/*************************************************************************************************************************************/
void F_HUF_EditionDesCodesDeHuffman()
{
if (HUF_EditerCodesDeHuffman == VRAI)
{
Entier index_1;
printf("HUF/EditionDesCodesDeHuffman :\n");
for (index_1=PREMIER_CARACTERE ; index_1<=DERNIER_CARACTERE ; index_1++)
{
Entier LongueurCodeBinaire=HUF_LongueurDuCodeBinaire[index_1];
if (LongueurCodeBinaire != CODE_DE_HUFFMAN_INUTILISE)
{
CHAR caractere=HUF_CaractereAssociesAuCodeBinaire[index_1];
Entier reste=HUF_CodeBinaire[index_1];
Entier PuissanceDe2=1;
Entier index_2;
if ( (caractere >= PREMIER_CARACTERE_EDITABLE)
&& (caractere <= DERNIER_CARACTERE_EDITABLE)
)
{
printf("'%c' (0x%02x) --> "
,caractere
,caractere
);
}
else
{
printf(" (0x%02x) --> "
,caractere
);
}
for (index_2=1 ; index_2<=LongueurCodeBinaire ; index_2++)
{
PuissanceDe2 = BASE2*PuissanceDe2;
}
for (index_2=1 ; index_2<=LongueurCodeBinaire ; index_2++)
{
PuissanceDe2 = PuissanceDe2/BASE2;
printf("%1"For10,reste/PuissanceDe2);
reste = reste%PuissanceDe2;
}
printf("\n");
}
else
{
}
}
}
else
{
}
}
/*************************************************************************************************************************************/
/* */
/* C O M P A C T A G E D ' U N E C H A I N E D E C A R A C T E R E S : */
/* */
/*************************************************************************************************************************************/
#define D_HUF_StoreBit(Bit,IndexBit,Chaine) \
{ \
Entier IndexBitDansChaine; \
CHAR Octet; \
CHAR MasqueRangementBit; \
Entier IndexBitDansOctet; \
\
IndexBitDansChaine = IndexBit/NBITOC; \
IndexBitDansOctet = IndexBit%NBITOC; \
\
Octet = Chaine[IndexBitDansChaine]; \
MasqueRangementBit = Bit << ((NBITOC-IndexBitDansOctet)-1); \
Chaine[IndexBitDansChaine] = Octet | MasqueRangementBit; \
}
void F_HUF_Directe(CHAR ChaineB[],CHAR ChaineA[],Entier longueurA)
{
Entier NombreDeBitsDansChaineB=0;
Entier IndexBitCourant=0;
Entier IndexDeChaineA;
for (IndexDeChaineA=INDEX0 ; IndexDeChaineA<=NombreVersIndex(longueurA) ; IndexDeChaineA++)
{
CHAR CaractereCourant=ChaineA[IndexDeChaineA];
Entier IndexHUF=PREMIER_CARACTERE;
Logical iterer=VRAI;
while (iterer == VRAI)
{
if (IndexHUF <= DERNIER_CARACTERE)
{
if (CaractereCourant == HUF_CaractereAssociesAuCodeBinaire[IndexHUF])
{
/* Le caractere courant a ete retrouve dans les tables de codage entropique de Huffman : */
Entier LongueurCodeBinaire=HUF_LongueurDuCodeBinaire[IndexHUF];
Entier reste=HUF_CodeBinaire[IndexHUF];
Entier IndexCodeBinaire;
Entier PuissanceDe2=1;
for (IndexCodeBinaire=1
; IndexCodeBinaire<=LongueurCodeBinaire
; IndexCodeBinaire++
)
{
PuissanceDe2 = BASE2*PuissanceDe2;
}
for (IndexCodeBinaire=1
; IndexCodeBinaire<=LongueurCodeBinaire
; IndexCodeBinaire++
)
{
Entier BitCourant;
PuissanceDe2 = PuissanceDe2/BASE2;
BitCourant = reste/PuissanceDe2;
reste = reste%PuissanceDe2;
D_HUF_StoreBit(BitCourant,IndexBitCourant,ChaineB);
/* Mise en place des bits codant le caractere courant 'CaractereCourant'... */
IndexBitCourant++;
NombreDeBitsDansChaineB++;
}
iterer=FAUX;
}
else
{
IndexHUF++;
/* Il faut poursuivre la recherche du caractere courant dans le code de Huffman... */
}
}
else
{
fprintf(stderr,"ERREUR(HUF) : Le caractere '0x02x' n'est pas dans l'arbre.\n");
iterer=FAUX;
}
}
}
HUF_NombreDeBitsApresCodage = NombreDeBitsDansChaineB;
HUF_Codage_LongueurApres = DIVISION_PAR_EXCES(HUF_NombreDeBitsApresCodage,NBITOC);
}
/*************************************************************************************************************************************/
/* */
/* D E C O M P A C T A G E D ' U N E C H A I N E D E C A R A C T E R E S : */
/* */
/*************************************************************************************************************************************/
#define D_HUF_LoadBit(Bit,IndexBit,Chaine) \
{ \
Entier IndexBitDansChaine; \
Entier IndexBitDansOctet; \
Entier decalage; \
CHAR Octet; \
Entier MasqueExtractionBit; \
\
mEGAL(IndexBitDansChaine,mDIVI(IndexBit,NBITOC)); \
mEGAL(IndexBitDansOctet,mREST(IndexBit,NBITOC)); \
\
mEGAL(decalage,mSOUS(mSOUS(NBITOC,IndexBitDansOctet),1)); \
\
mEGAL(Octet,ACCES_CHAINE(Chaine,IndexBitDansChaine)); \
mEGAL(MasqueExtractionBit,mDECG(BIT,decalage)); \
mEGAL(Bit,(Entier)mDECD(mETLO(Octet,MasqueExtractionBit),decalage)); \
}
void F_HUF_Inverse(CHAR ChaineR[],CHAR ChaineB[],Entier NombreDeBitsDansChaineB)
{
Entier NombreDOctetssDansChaineR;
Entier IndexBitCourant;
Entier IndexChaineR;
Entier NoeudCourantDeLArbre;
HUF_Decodage_LongueurAvant = DIVISION_PAR_EXCES(NombreDeBitsDansChaineB,NBITOC);
mEGAL(NombreDOctetssDansChaineR,0);
mEGAL(IndexChaineR,INDEX0);
mEGAL(NoeudCourantDeLArbre,HUF_RacineDeLArbre);
DoIn(IndexBitCourant,INDEX0,NombreVersIndex(NombreDeBitsDansChaineB))
{
Entier BitCourant;
D_HUF_LoadBit(BitCourant,IndexBitCourant,ChaineB);
Test ( mIFEQ(HUF_ArbreChainageAGauche[NoeudCourantDeLArbre],NOEUD_INEXISTANT)
&& mIFEQ(HUF_ArbreChainageADroite[NoeudCourantDeLArbre],NOEUD_INEXISTANT)
)
{
/* Cas ou l'arbre n'a qu'un noeud (sa racine est une feuille), ce qui se rencontre dans */
/* le cas ou la chaine 'A' contient des caracteres tous identiques... */
}
ATes
{
Choi(BitCourant)
/* La valeur du bit courant indique si l'on doit tourner a GAUCHE ou bien a DROITE... */
{
Case(GAUCHE)
{
mEGAL(NoeudCourantDeLArbre,HUF_ArbreChainageAGauche[NoeudCourantDeLArbre]);
break;
}
ECas
Case(DROITE)
{
mEGAL(NoeudCourantDeLArbre,HUF_ArbreChainageADroite[NoeudCourantDeLArbre]);
break;
}
ECas
Defo
{
fprintf(stderr,"ERREUR(HUF) : un bit vaut %"For10".\n",BitCourant);
}
EDef
}
ECho
}
ETes
Test ( mIFEQ(HUF_ArbreChainageAGauche[NoeudCourantDeLArbre],NOEUD_INEXISTANT)
&& mIFEQ(HUF_ArbreChainageADroite[NoeudCourantDeLArbre],NOEUD_INEXISTANT)
)
{
mEGAL(ACCES_CHAINE(ChaineR,IndexChaineR),HUF_ArbreCaracteresEnChaqueNoeud[NoeudCourantDeLArbre]);
/* Cas ou l'on est tombe sur une feuille de l'arbre : elle donne le caractere qui etait */
/* code par la suite courante de bits... */
mINCR(IndexChaineR);
mINCR(NombreDOctetssDansChaineR);
mEGAL(NoeudCourantDeLArbre,HUF_RacineDeLArbre);
/* Et on repart de la racine de l'arbre... */
}
ATes
{
}
ETes
}
EDoI
mEGAL(HUF_NombreDOctetsApresDecodage,NombreDOctetssDansChaineR);
HUF_Decodage_LongueurApres = HUF_NombreDOctetsApresDecodage;
}
/*************************************************************************************************************************************/
/* */
/* V A L I D A T I O N D U C O M P A C T A G E / D E C O M P A C T A G E */
/* D ' U N E C H A I N E D E C A R A C T E R E S : */
/* */
/*************************************************************************************************************************************/
void F_HUF_Verifications(CHAR Chaine1[],Entier LongueurChaine1,CHAR Chaine2[],Entier LongueurChaine2)
{
Entier index;
if (LongueurChaine1 == LongueurChaine2)
{
for (index=INDEX0 ; index<=NombreVersIndex(MIN2(LongueurChaine1,LongueurChaine2)) ; index++)
{
if (Chaine1[index] != Chaine2[index])
{
fprintf(stderr,"ERREUR(HUF) : '0x%02x' et '0x%02x' de rang %"For10" different.\n"
,Chaine1[index]
,Chaine2[index]
,index
);
}
else
{
}
}
}
else
{
fprintf(stderr
,"ERREUR(HUF) : Les deux chaines n'ont pas la meme longueur (%"For10"#%"For10").\n"
,LongueurChaine1
,LongueurChaine2
);
}
}
/*************************************************************************************************************************************/
/* */
/* I N I T I A L I S A T I O N S A S S O C I E E S A C H A Q U E C H A I N E D E T E S T : */
/* */
/*************************************************************************************************************************************/
#ifndef HUF_FIN_DE_CHAINE
# define HUF_FIN_DE_CHAINE \
1 \
/* Le '+1' est destine a pouvoir introduire, si besoin est, une "fin de chaine"... */
#else
#endif
#define D_HUF________Debut(ChaineB,ChaineR,ChaineA,LongueurChaineA) \
{ \
Entier index_1; \
Entier longueur=LongueurChaineA+HUF_FIN_DE_CHAINE; \
/* Le '+1' est destine a pouvoir introduire, si besoin est, une "fin de chaine"... */ \
\
ChaineB = MALLOC(longueur*sizeof(CHAR)); \
ChaineR = MALLOC(longueur*sizeof(CHAR)); \
\
for (index_1=1 ; index_1<=longueur ; index_1++) \
{ \
Entier index_2=NombreVersIndex(index_1); \
\
ChaineB[index_2] = 0; \
ChaineR[index_2] = 0; \
/* On notera que cela met donc implicitement une "fin de chaine" (0)... */ \
} \
}
#define D_HUF________Fin__(ChaineA1,ChaineA2) \
{ \
CALLs(free(ChaineA1)); \
CALLs(free(ChaineA2)); \
}