/*************************************************************************************************************************************/
/* */
/* C O D A G E D E H U F F M A N E T I N V E R S E : */
/* */
/* */
/* Author of '$xtc/HuffmanCoding.01$vv$I' : */
/* */
/* Jean-Francois Colonna (LACTAMME, 20151223080449). */
/* */
/*************************************************************************************************************************************/
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N G E N E R A L E S : */
/* */
/*************************************************************************************************************************************/
int HuffmanCoding_EditerFrequences=FAUX;
int HuffmanCoding_EditerArbre=FAUX;
int HuffmanCoding_EditerCodesDeHuffman=VRAI;
/* Indicateurs de controle des editions... */
#ifndef CHAR
# define CHAR \
unsigned char
#else
#endif
#define EntierCourt \
1
#define EntierLong \
2
#define Precision \
EntierLong
/* La Precision est soit 'EntierCourt' soit 'EntierLong'... */
/* */
/* ATTENTION : on notera que 'EntierCourt' et 'EntierLong' doivent etre defines a l'aide */
/* de valeurs entieres si l'on veut que le '#if' qui suit fonctionne correctement... */
#if (Precision==EntierCourt)
# define Entier \
int
# define For10 \
"d"
# define For16 \
"x"
#else
# define Entier \
long int
# define For10 \
"ld"
# define For16 \
"lx"
#endif
/* Types de donnees et Formats utiles... */
#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 CodageDeHuffman_FrequencesDOccurenceDesCaracteres[NOMBRE_DE_CARACTERES];
Entier CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[NOMBRE_DE_CARACTERES];
Entier CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[NOMBRE_DE_CARACTERES];
Entier CodageDeHuffman_PremierCaractere=PREMIER_CARACTERE;
Entier CodageDeHuffman_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 SIZE_CodageDeHuffman_CodeBinaire \
((NOMBRE_DE_CARACTERES*(sizeof(CHAR)+sizeof(CHAR)+sizeof(Entier)))*NBITOC)
CHAR CodageDeHuffman_CaractereAssociesAuCodeBinaire[NOMBRE_DE_CARACTERES];
CHAR CodageDeHuffman_LongueurDuCodeBinaire[NOMBRE_DE_CARACTERES];
Entier CodageDeHuffman_CodeBinaire[NOMBRE_DE_CARACTERES];
/* Definition des codes entropiques de Huffman. */
Entier CodageDeHuffman_NombreDeBitsApresCodage;
Entier CodageDeHuffman_NombreDOctetsApresDecodage;
/* Afin de faciliter l'exploitation des resultats... */
#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 CodageDeHuffman_GenerationFrequences(CHAR chaine[],Entier longueur)
{
Entier index;
for (index=INDEX0 ; index<=NombreVersIndex(longueur) ; index++)
{
CodageDeHuffman_FrequencesDOccurenceDesCaracteres[chaine[index]]++;
/* La "frequence" est obtenu par un simple comptage des caracteres... */
}
}
#define PERMUTATION(tableau,index1,index2) \
{ \
Entier SauvegardeTemporaire=tableau[index1]; \
tableau[index1] = tableau[index2]; \
tableau[index2] = SauvegardeTemporaire; \
}
void CodageDeHuffman_TriCroissantDesFrequencesDesCaracteres()
{
Entier index_de_fin;
for (index_de_fin=(CodageDeHuffman_DernierCaractere-1)
; index_de_fin>=CodageDeHuffman_PremierCaractere
; index_de_fin--
)
{
Entier index_de_debut;
for (index_de_debut=CodageDeHuffman_PremierCaractere ; index_de_debut<=index_de_fin ; index_de_debut++)
{
if (CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index_de_debut]
> CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index_de_debut+1]
)
{
PERMUTATION(CodageDeHuffman_FrequencesDOccurenceDesCaracteres
,index_de_debut
,index_de_debut+1
);
PERMUTATION(CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres
,index_de_debut
,index_de_debut+1
);
PERMUTATION(CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres
,index_de_debut
,index_de_debut+1
);
/* Cette echange conserve l'ordre des elements possedant la meme "clef"... */
}
else
{
}
}
}
for (index_de_fin=CodageDeHuffman_PremierCaractere ; index_de_fin<=CodageDeHuffman_DernierCaractere ; index_de_fin++)
{
if (CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index_de_fin] == CARACTERE_INUTILISE)
{
CodageDeHuffman_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 CodageDeHuffman_EditionDesFrequencesDesCaracteres()
{
Entier index;
if (HuffmanCoding_EditerFrequences == VRAI)
{
printf("========================================\n");
for (index=CodageDeHuffman_PremierCaractere ; index<=CodageDeHuffman_DernierCaractere ; index++)
{
if (CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index] != CARACTERE_INUTILISE)
{
if (CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[index]
> CARACTERE_INEXISTANT
)
{
if ( ((CHAR)CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[index]
>= PREMIER_CARACTERE_EDITABLE
)
&& ((CHAR)CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[index]
<= DERNIER_CARACTERE_EDITABLE
)
)
{
printf("caractere='%c' (0x%02"For16") frequence=%"For10" noeud=%"For10"\n"
,(CHAR)CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[index]
,CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[index]
,CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index]
,CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[index]
);
}
else
{
printf("caractere= (0x%02"For16") frequence=%"For10" noeud=%"For10"\n"
,CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[index]
,CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index]
,CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[index]
);
}
/* Cas des "vrais" caracteres... */
}
else
{
printf("* frequence=%"For10" noeud=%"For10"\n"
,CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index]
,CodageDeHuffman_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(CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre)
#define SUIVANT_INEXISTANT \
(PREMIER_NOEUD_DE_L_ARBRE-1)
#define SIZE_CodageDeHuffman_Arbre \
((CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre*(sizeof(Entier)+sizeof(Entier)+sizeof(Entier)))*NBITOC) \
/* On notera que 'ArbreFrequenceDesNoeuds' est inutile pour la mesure de 'K'... */
Entier CodageDeHuffman_ArbreFrequenceDesNoeuds[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
Entier CodageDeHuffman_ArbreCaracteresEnChaqueNoeud[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
Entier CodageDeHuffman_ArbreChainageAGauche[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
Entier CodageDeHuffman_ArbreChainageADroite[NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE];
#define SIZE_IdentiteDuNoeudCourantDeLArbre \
(sizeof(CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre)*NBITOC)
Entier CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre=PREMIER_NOEUD_DE_L_ARBRE;
Entier CodageDeHuffman_RacineDeLArbre;
/* Definition de l'arbre de codage... */
#define MISE_A_JOUR_ARBRE(frequence,caractere,ChainageAGauche,ChainageADroite) \
/* On notera qu'a GAUCHE se trouve la FREQUENCE MINIMALE... */ \
{ \
CodageDeHuffman_ArbreFrequenceDesNoeuds[CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre] = frequence; \
CodageDeHuffman_ArbreCaracteresEnChaqueNoeud[CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre] = caractere; \
CodageDeHuffman_ArbreChainageAGauche[CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre] = ChainageAGauche; \
CodageDeHuffman_ArbreChainageADroite[CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre] = ChainageADroite; \
\
if (CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre < NombreVersIndex(NOMBRE_MAXIMAL_DE_NOEUDS_DE_L_ARBRE)) \
{ \
CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre++; \
} \
else \
{ \
fprintf(stderr,"ERREUR(HuffmanCoding) : Debordement de l'arbre.\n"); \
} \
}
void CodageDeHuffman_GenerationDeLArbre()
{
Entier ItererLaGenerationDeLArbre=VRAI;
while (ItererLaGenerationDeLArbre == VRAI)
{
Entier index;
Entier IndexFrequenceMinimaleGauche,FrequenceMinimaleGauche,CaractereGauche,NoeudFilsGauche;
Entier IndexFrequenceMinimaleDroite,FrequenceMinimaleDroite,CaractereDroite,NoeudFilsDroite;
Entier SommeDesFrequencesEnUnNoeud=0;
CodageDeHuffman_TriCroissantDesFrequencesDesCaracteres();
CodageDeHuffman_EditionDesFrequencesDesCaracteres();
/* Tri destine a garantir l'ordre des frequences... */
index=CodageDeHuffman_PremierCaractere;
while ( (CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index] == CARACTERE_INUTILISE)
&& (index < CodageDeHuffman_DernierCaractere)
)
{
index++;
}
IndexFrequenceMinimaleGauche = index;
FrequenceMinimaleGauche= CodageDeHuffman_FrequencesDOccurenceDesCaracteres[IndexFrequenceMinimaleGauche];
CaractereGauche = CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleGauche];
if (CaractereGauche != CARACTERE_INEXISTANT)
{
NoeudFilsGauche = CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre;
CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleGauche]
= NoeudFilsGauche;
MISE_A_JOUR_ARBRE(FrequenceMinimaleGauche
,CaractereGauche
,SUIVANT_INEXISTANT
,SUIVANT_INEXISTANT
);
/* Creation d'une feuille de l'arbre (noeud donnant donc un caractere). */
}
else
{
NoeudFilsGauche
= CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleGauche];
/* Cas d'un noeud de cumul de l'arbre deja genere. */
}
SommeDesFrequencesEnUnNoeud = SommeDesFrequencesEnUnNoeud + FrequenceMinimaleGauche;
CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleGauche] = CARACTERE_INEXISTANT;
CodageDeHuffman_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=CodageDeHuffman_PremierCaractere;
while ( (CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index] == CARACTERE_INUTILISE)
&& (index < CodageDeHuffman_DernierCaractere)
)
{
index++;
}
IndexFrequenceMinimaleDroite = index;
if (IndexFrequenceMinimaleGauche != IndexFrequenceMinimaleDroite)
{
FrequenceMinimaleDroite
= CodageDeHuffman_FrequencesDOccurenceDesCaracteres[IndexFrequenceMinimaleDroite];
CaractereDroite
= CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleDroite];
if (FrequenceMinimaleGauche > FrequenceMinimaleDroite)
{
fprintf(stderr
,"ERREUR(HuffmanCoding) : FreqMinGauche=%"For10" > FreqMinDroite=%"For10"\n"
,FrequenceMinimaleGauche
,FrequenceMinimaleDroite
);
}
else
{
}
if (CaractereDroite != CARACTERE_INEXISTANT)
{
NoeudFilsDroite = CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre;
CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleDroite]
= NoeudFilsDroite;
MISE_A_JOUR_ARBRE(FrequenceMinimaleDroite
,CaractereDroite
,SUIVANT_INEXISTANT
,SUIVANT_INEXISTANT
);
/* Creation d'une feuille de l'arbre (noeud donnant donc un caractere). */
}
else
{
NoeudFilsDroite
= CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleDroite];
/* Cas d'un noeud de cumul de l'arbre deja genere. */
}
SommeDesFrequencesEnUnNoeud = SommeDesFrequencesEnUnNoeud + FrequenceMinimaleDroite;
CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[IndexFrequenceMinimaleDroite]
= CARACTERE_INEXISTANT;
CodageDeHuffman_FrequencesDOccurenceDesCaracteres[IndexFrequenceMinimaleDroite]
= SommeDesFrequencesEnUnNoeud;
/* Ainsi, ce caractere dont la frequence vient d'etre cumule est remplace par ce cumul... */
CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[IndexFrequenceMinimaleDroite]
= CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre;
MISE_A_JOUR_ARBRE(SommeDesFrequencesEnUnNoeud
,CARACTERE_INEXISTANT
,NoeudFilsGauche
,NoeudFilsDroite
);
/* Creation d'un noeud de cumul de l'arbre. */
}
else
{
ItererLaGenerationDeLArbre = FAUX;
}
}
CodageDeHuffman_RacineDeLArbre = CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre-1;
}
void CodageDeHuffman_EditionDeLArbre()
{
if (HuffmanCoding_EditerArbre == VRAI)
{
Entier index;
for (index=PREMIER_NOEUD_DE_L_ARBRE ; index<=DERNIER_NOEUD_DE_L_ARBRE ; index++)
{
printf("noeud=%04"For10" frequence=%08"For10""
,index
,CodageDeHuffman_ArbreFrequenceDesNoeuds[index]
);
if (CodageDeHuffman_ArbreCaracteresEnChaqueNoeud[index] != CARACTERE_INEXISTANT)
{
printf(" caractere=0x%02"For16""
,CodageDeHuffman_ArbreCaracteresEnChaqueNoeud[index]
);
}
else
{
printf(" * ");
}
if (CodageDeHuffman_ArbreChainageAGauche[index] != NOEUD_INEXISTANT)
{
printf(" ChainageAGauche=%04"For10""
,CodageDeHuffman_ArbreChainageAGauche[index]
);
}
else
{
}
if (CodageDeHuffman_ArbreChainageADroite[index] != NOEUD_INEXISTANT)
{
printf(" ChainageADroite=%04"For10""
,CodageDeHuffman_ArbreChainageADroite[index]
);
}
else
{
}
printf("\n");
}
}
else
{
}
}
#define GAUCHE \
1
#define DROITE \
0
#define BASE2 \
2
void CodageDeHuffman_ParcoursRecursifDeLArbre(Entier racine,Entier CodeBinaire,Entier LongueurCodeBinaire)
{
if (racine != NOEUD_INEXISTANT)
{
if ( (CodageDeHuffman_ArbreChainageAGauche[racine] != NOEUD_INEXISTANT)
&& (CodageDeHuffman_ArbreChainageADroite[racine] != NOEUD_INEXISTANT)
)
{
if (LongueurCodeBinaire < (NBITMO-1))
{
CodageDeHuffman_ParcoursRecursifDeLArbre(CodageDeHuffman_ArbreChainageAGauche[racine]
,(BASE2*CodeBinaire)+GAUCHE
,LongueurCodeBinaire+1
);
CodageDeHuffman_ParcoursRecursifDeLArbre(CodageDeHuffman_ArbreChainageADroite[racine]
,(BASE2*CodeBinaire)+DROITE
,LongueurCodeBinaire+1
);
}
else
{
fprintf(stderr,"ERREUR(HuffmanCoding) : Un code binaire est trop long.\n");
}
}
else
{
Entier caractere=CodageDeHuffman_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. */
CodageDeHuffman_LongueurDuCodeBinaire[caractere] = longueur;
CodageDeHuffman_CodeBinaire[caractere] = CodeBinaire;
if (caractere != CodageDeHuffman_CaractereAssociesAuCodeBinaire[caractere])
{
fprintf(stderr,"ERREUR(HuffmanCoding) : Les tables de Huffman sont incoherentes.\n");
}
else
{
}
}
}
else
{
}
}
/*************************************************************************************************************************************/
/* */
/* I N T I A L I S A T I O N S D I V E R S E S : */
/* */
/*************************************************************************************************************************************/
void CodageDeHuffman_Initialisations()
{
Entier index;
CodageDeHuffman_PremierCaractere=PREMIER_CARACTERE;
CodageDeHuffman_DernierCaractere=DERNIER_CARACTERE;
CodageDeHuffman_IdentiteDuNoeudCourantDeLArbre=PREMIER_NOEUD_DE_L_ARBRE;
for (index=CodageDeHuffman_PremierCaractere ; index<=CodageDeHuffman_DernierCaractere ; index++)
{
CodageDeHuffman_FrequencesDOccurenceDesCaracteres[index] = CARACTERE_INUTILISE;
CodageDeHuffman_DefinitionRedondanteDesCodesDesCaracteres[index] = index;
CodageDeHuffman_NumerosDesNoeudsDeRangementDesCaracteres[index] = NOEUD_INEXISTANT;
CodageDeHuffman_CaractereAssociesAuCodeBinaire[index] = index;
CodageDeHuffman_LongueurDuCodeBinaire[index] = CODE_DE_HUFFMAN_INUTILISE;
CodageDeHuffman_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 CodageDeHuffman_EditionDesCodesDeHuffman()
{
if (HuffmanCoding_EditerCodesDeHuffman == VRAI)
{
Entier index_1;
printf("\n");
for (index_1=PREMIER_CARACTERE ; index_1<=DERNIER_CARACTERE ; index_1++)
{
Entier LongueurCodeBinaire=CodageDeHuffman_LongueurDuCodeBinaire[index_1];
if (LongueurCodeBinaire != CODE_DE_HUFFMAN_INUTILISE)
{
CHAR caractere=CodageDeHuffman_CaractereAssociesAuCodeBinaire[index_1];
Entier reste=CodageDeHuffman_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 STORE_BIT(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; \
}
Entier CodageDeHuffman_CompactageChaine(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 IndexCodageDeHuffman=PREMIER_CARACTERE;
Entier iterer=VRAI;
while (iterer == VRAI)
{
if (IndexCodageDeHuffman <= DERNIER_CARACTERE)
{
if (CaractereCourant
== CodageDeHuffman_CaractereAssociesAuCodeBinaire[IndexCodageDeHuffman]
)
{
/* Le caractere courant a ete retrouve dans les tables de codage entropique de Huffman : */
Entier LongueurCodeBinaire
=CodageDeHuffman_LongueurDuCodeBinaire[IndexCodageDeHuffman];
Entier reste=CodageDeHuffman_CodeBinaire[IndexCodageDeHuffman];
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;
STORE_BIT(BitCourant,IndexBitCourant,ChaineB);
/* Mise en place des bits codant le caractere courant 'CaractereCourant'... */
IndexBitCourant++;
NombreDeBitsDansChaineB++;
}
iterer=FAUX;
}
else
{
IndexCodageDeHuffman++;
/* Il faut poursuivre la recherche du caractere courant dans le code de Huffman... */
}
}
else
{
fprintf(stderr,"ERREUR(HuffmanCoding) : Le caractere '0x02x' n'est pas dans l'arbre.\n");
iterer=FAUX;
}
}
}
CodageDeHuffman_NombreDeBitsApresCodage = NombreDeBitsDansChaineB;
return(NombreDeBitsDansChaineB);
}
/*************************************************************************************************************************************/
/* */
/* 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 LOAD_BIT(Bit,IndexBit,Chaine) \
{ \
Entier IndexBitDansChaine = IndexBit/NBITOC; \
Entier IndexBitDansOctet = IndexBit%NBITOC; \
Entier decalage; \
CHAR Octet; \
Entier MasqueExtractionBit; \
\
decalage = ((NBITOC-IndexBitDansOctet)-1); \
\
Octet = Chaine[IndexBitDansChaine]; \
MasqueExtractionBit = BIT << decalage; \
Bit = (Octet & MasqueExtractionBit) >> decalage; \
}
Entier CodageDeHuffman_DeCompactageChaine(CHAR ChaineR[],CHAR ChaineB[],Entier NombreDeBitsDansChaineB)
{
Entier NombreDOctetssDansChaineR=0;
Entier IndexBitCourant;
Entier IndexChaineR=INDEX0;
Entier NoeudCourantDeLArbre=CodageDeHuffman_RacineDeLArbre;
for (IndexBitCourant=INDEX0 ; IndexBitCourant<=NombreVersIndex(NombreDeBitsDansChaineB) ; IndexBitCourant++)
{
Entier BitCourant;
LOAD_BIT(BitCourant,IndexBitCourant,ChaineB);
if ( (CodageDeHuffman_ArbreChainageAGauche[NoeudCourantDeLArbre] == NOEUD_INEXISTANT)
&& (CodageDeHuffman_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... */
}
else
{
switch (BitCourant)
/* La valeur du bit courant indique si l'on doit tourner a GAUCHE ou bien a DROITE... */
{
case GAUCHE:
{
NoeudCourantDeLArbre = CodageDeHuffman_ArbreChainageAGauche[NoeudCourantDeLArbre];
break;
}
case DROITE:
{
NoeudCourantDeLArbre = CodageDeHuffman_ArbreChainageADroite[NoeudCourantDeLArbre];
break;
}
default:
{
fprintf(stderr,"ERREUR(HuffmanCoding) : un bit vaut %"For10".\n",BitCourant);
}
}
}
if ( (CodageDeHuffman_ArbreChainageAGauche[NoeudCourantDeLArbre] == NOEUD_INEXISTANT)
&& (CodageDeHuffman_ArbreChainageADroite[NoeudCourantDeLArbre] == NOEUD_INEXISTANT)
)
{
ChaineR[IndexChaineR] = CodageDeHuffman_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... */
IndexChaineR++;
NombreDOctetssDansChaineR++;
NoeudCourantDeLArbre = CodageDeHuffman_RacineDeLArbre;
/* Et on repart de la racine de l'arbre... */
}
else
{
}
}
CodageDeHuffman_NombreDOctetsApresDecodage = NombreDOctetssDansChaineR;
return(NombreDOctetssDansChaineR);
}
/*************************************************************************************************************************************/
/* */
/* V A L I D A T I O N D U D E 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 CodageDeHuffman_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(HuffmanCoding) : '0x%02x' et '0x%02x' de rang %"For10" different.\n"
,Chaine1[index]
,Chaine2[index]
,index
);
}
else
{
}
}
}
else
{
fprintf(stderr
,"ERREUR(HuffmanCoding) : 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 CodageDeHuffman_FIN_DE_CHAINE
# define CodageDeHuffman_FIN_DE_CHAINE \
1 \
/* Le '+1' est destine a pouvoir introduire, si besoin est, une "fin de chaine"... */
#else
#endif
#define CodageDeHuffman_InitialisationChaines(ChaineB,ChaineR,ChaineA,LongueurChaineA) \
{ \
Entier index_1; \
Entier longueur=LongueurChaineA+CodageDeHuffman_FIN_DE_CHAINE; \
/* Le '+1' est destine a pouvoir introduire, si besoin est, une "fin de chaine"... */ \
\
ChaineB = malloc(longueur); \
ChaineR = malloc(longueur); \
\
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 CodageDeHuffman_DesinitialisationChaines(ChaineA1,ChaineA2) \
{ \
free(ChaineA1); \
free(ChaineA2); \
}