c' est le codage huffman
Source / Exemple :
/*
- Devoir : Compression de Huffman
- /
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
*
typedef unsigned char byte;
typedef unsigned int uint;
/* */
typedef struct _arbre* ptr_arbre;
typedef struct _arbre
{
/* données */
byte c;
uint freq;
uint code_huff;
byte nbr_bits;
/* les fils */
ptr_arbre fils_d;
ptr_arbre fils_g;
}h_arbre;
/* */
typedef struct _list* ptr_list;
typedef struct _list
{
ptr_arbre noeud;
ptr_list suiv;
}list;
/* */
typedef struct _ch_context
{
FILE *fin;
FILE *fout;
uint fsize;
uint nbr_elem;
ptr_arbre r_arbre;
ptr_arbre car_table;
}ch_context;
/*
*
typedef struct _dh_context
{
FILE *fin;
FILE *fout;
uint fsize;
uint nbr_elem;
ptr_arbre r_arbre;
}dh_context;
/* compression */
int comp_huffman(const char*, const char*);
/* decompression */
int decomp_huffman(const char*, const char*);
/*******************************************************
- main**********************************
int main(int argc, char **argv)
{
int get_file_size(const char*);
if ((argc != 4) || (argv[1][0] != '-')
|| ((argv[1][1] != 'c') && (argv[1][1] != 'd')))
{
printf("Utilisation:\n");
printf(" Huffman {-c, -d} src dest\n");
printf(" -c : pour la compression\n");
printf(" -d : pour la decompression\n");
printf(" src : fichier source\n");
printf(" dest : fichier destination\n");
}
else
{
char *fsrc, *fdest;
char comp = argv[1][1];
/* les deux fichiers */
fsrc = argv[2];
fdest = argv[3];
if (comp == 'c')
{
/* compression */
if (comp_huffman(fsrc, fdest))
{
int insize = get_file_size(fsrc);
int outsize = get_file_size(fdest);
printf("Compression reussie\n");
printf("Taile du fichier non compressee : %d (octets)\n", insize);
printf("Taile du fichier compressee : %d (octets)\n", outsize);
printf("Taux de compression : %d%%\n",
((outsize - insize)*100)/outsize);
}
else
printf("Erreur de compression\n");
}
else
{
/* decompression */
if (decomp_huffman(fsrc, fdest))
printf("Decompression OK\n");
else
printf("Erreur de decompression\n");
}
}
return (0);
}
int get_file_size(const char *file)
{
int size;
FILE *fp = fopen(file, "rb");
if (!fp)
return (-1);
fseek(fp, 0, 2);
size = (int)ftell(fp);
fclose(fp);
return (size);
}
void ch_free_arbre(ptr_arbre arbre)
{
/* on libere tous les noeud sauf les feuille */
if (arbre)
{
if (arbre->fils_g && arbre->fils_d)
{
ch_free_arbre(arbre->fils_g);
ch_free_arbre(arbre->fils_d);
free(arbre);
}
}
}
/* */
void ch_free_context(ch_context* ct)
{
ch_free_arbre(ct->r_arbre);
if (ct->car_table)
{
free(ct->car_table);
}
if (ct->fin)
fclose(ct->fin);
if (ct->fout)
fclose(ct->fout);
}
/* */
void ch_inserer(ptr_list* lst, ptr_arbre arbre)
{
if (*lst == 0)
{
(*lst) = (ptr_list)malloc(sizeof(list));
(*lst)->noeud = arbre;
(*lst)->suiv = 0;
}
else
{
ptr_list p = (*lst);
if (p->noeud->freq > arbre->freq)
{
ptr_list l = (ptr_list)malloc(sizeof(list));
l->noeud = arbre;
l->suiv = (*lst);
(*lst) = l;
}
else
{
ptr_list q, l;
while (p)
{
if (p->noeud->freq > arbre->freq)
break;
q = p;
p = p->suiv;
}
l = (ptr_list)malloc(sizeof(list));
l->noeud = arbre;
l->suiv = p;
q->suiv = l;
}
}
}
/* */
int ch_calc_freq(ch_context* ct)
{
uint *car_freq;
int i, j;
car_freq = (uint*)malloc(256*sizeof(uint));
memset(car_freq, 0, 256*sizeof(uint));
rewind(ct->fin);
/* etude statistique */
while (!feof(ct->fin))
{
byte c;
fread(&c, 1, 1, ct->fin);
if (car_freq[c] == 0)
(ct->nbr_elem)++;
car_freq[c] = car_freq[c] + 1;
}
/* création de la table des caracteres du fichier */
ct->car_table = (ptr_arbre)malloc((ct->nbr_elem)*sizeof(h_arbre));
for (i = 0, j = 0; i < 256 ; i++)
{
if (car_freq[i] != 0)
{
ct->car_table[j].c = (byte)i;
ct->car_table[j].freq = car_freq[i];
ct->car_table[j].code_huff = 0;
ct->car_table[j].nbr_bits = 0;
ct->car_table[j].fils_d = 0;
ct->car_table[j].fils_g = 0;
j++;
}
}
free(car_freq);
return (1);
}
/* */
void ch_set_bits(ptr_arbre arbre, uint code_huff, uint nbr_bits)
{
if (arbre)
{
if (arbre->fils_d && arbre->fils_g)
{
ch_set_bits(arbre->fils_d, code_huff, nbr_bits + 1);
ch_set_bits(arbre->fils_g,
code_huff | (0x1 << nbr_bits), nbr_bits + 1);
}
else
{
arbre->code_huff = code_huff;
arbre->nbr_bits = nbr_bits;
}
}
}
/* */
int ch_creation_arbre(ch_context* ct)
{
ptr_list lst = 0;
uint i, nbr_elem = ct->nbr_elem;
for (i = 0; i < nbr_elem; i++)
ch_inserer(&lst, &(ct->car_table[i]));
/* c'est bien, les elements sont classés par ordre croissant */
/* maintenat on va grouper les deux premier */
while (nbr_elem > 1)
{
ptr_arbre a, a1, a2;
ptr_list p;
p = lst;
a1 = p->noeud;
a2 = p->suiv->noeud;
lst = p->suiv->suiv;
free(p->suiv);
free(p);
a = (ptr_arbre)malloc(sizeof(h_arbre));
a->c = -1;
a->freq = a1->freq + a2->freq;
a->code_huff = 0;
a->fils_d = a1;
a->fils_g = a2;
ch_inserer(&lst, a);
nbr_elem--;
}
ct->r_arbre = lst->noeud;
free(lst);
/* calcul du codage pour chaque caractere */
ch_set_bits(ct->r_arbre, 0, 0);
return (1);
}
/* */
int ch_ecriture_table(ch_context* ct)
{
uint i, nbr_elem = ct->nbr_elem;
/* nombre de caracteres */
if (!fwrite(&nbr_elem, sizeof(uint), 1, ct->fout))
return (0);
/* la taille du fichier */
if (!fwrite(&(ct->fsize), sizeof(uint), 1, ct->fout))
return (0);
/* ecriture de la table */
for (i = 0; i < nbr_elem; i++)
{
byte c, nbr_bits;
uint code_huff;
/* le caractere */
c = ct->car_table[i].c;
if (!fwrite(&c, 1, 1, ct->fout))
return (0);
/* le nombre de bit necessaire */
nbr_bits = ct->car_table[i].nbr_bits;
if (!fwrite(&nbr_bits, 1, 1, ct->fout))
return (0);
/* le code huffman */
code_huff = ct->car_table[i].code_huff;
if (nbr_bits <= 8)
{
if (!fwrite(&code_huff, 1, 1, ct->fout))
return (0);
}
else if (nbr_bits <= 16)
{
if (!fwrite(&code_huff, 2, 1, ct->fout))
return (0);
}
else
{
if (!fwrite(&code_huff, 4, 1, ct->fout))
return (0);
}
}
return (1);
}
/* */
ptr_arbre ch_get_arbre(ch_context* ct, byte c)
{
ptr_arbre a;
uint i;
a = ct->car_table;
i = ct->nbr_elem;
while (i--)
{
if (a->c == c)
return (a);
a++;
}
return (0);
}
/* */
int ch_compression(ch_context* ct)
{
ptr_arbre a;
byte ucar = 0, c, nbr_bits;
uint code_huff, pc = 0, i;
rewind(ct->fin);
while (!feof(ct->fin))
{
fread(&c, 1, 1, ct->fin);
a = ch_get_arbre(ct, c);
code_huff = a->code_huff;
nbr_bits = a->nbr_bits;
for (i = 0; i < nbr_bits; i++)
{
ucar = ucar << 1;
if (code_huff & 0x1)
ucar = ucar | 0x1;
code_huff = code_huff >> 1;
pc++;
if (pc == 8)
{
fwrite(&ucar, 1, 1, ct->fout);
pc = 0;
ucar = 0;
}
}
}
if (pc != 0)
{
/* ecriture du dernier caractere */
while (pc != 8)
{
ucar = ucar << 1;
pc++;
}
fwrite(&ucar, 1, 1, ct->fout);
}
return (1);
}
/* */
int comp_huffman(const char* fsrc, const char* fdest)
{
ch_context ct;
memset(&ct, 0, sizeof(ch_context));
ct.fin = fopen(fsrc, "rb");
if (!(ct.fin))
return (0);
fseek(ct.fin, 0, 2);
ct.fsize = ftell(ct.fin);
/* calcule de la fréquence */
if (!ch_calc_freq(&ct))
{
ch_free_context(&ct);
return (0);
}
/* création de l'arbre de huffman */
if (!ch_creation_arbre(&ct))
{
ch_free_context(&ct);
return (0);
}
/* on est prés à la compression */
ct.fout = fopen(fdest, "wb");
if (!(ct.fin))
{
ch_free_context(&ct);
return (0);
}
/* ecriture de la table */
if (!ch_ecriture_table(&ct))
{
ch_free_context(&ct);
return (0);
}
/* compression des données */
if (!ch_compression(&ct))
{
ch_free_context(&ct);
return (0);
}
ch_free_context(&ct);
return (1);
}
void dh_free_arbre(ptr_arbre arbre)
{
/* on libere tous les noeud sauf les feuille */
if (arbre)
{
dh_free_arbre(arbre->fils_g);
dh_free_arbre(arbre->fils_d);
free(arbre);
}
}
/* */
void dh_free_context(dh_context* ct)
{
dh_free_arbre(ct->r_arbre);
if (ct->fin)
fclose(ct->fin);
if (ct->fout)
fclose(ct->fout);
}
/* */
int dh_creation_arbre(dh_context* ct)
{
uint i, nbr_elem;
/* nombre d'element */
if (!fread(&nbr_elem, sizeof(uint), 1, ct->fin))
return (0);
/* la taille du fichier */
if (!fread(&(ct->fsize), sizeof(uint), 1, ct->fin))
return (0);
/* allocation de la mémoire */
ct->nbr_elem = nbr_elem;
ct->r_arbre = (ptr_arbre)malloc(sizeof(h_arbre));
ct->r_arbre->c = 0xFF;
ct->r_arbre->fils_d = 0;
ct->r_arbre->fils_g = 0;
for (i = 0; i < nbr_elem; i++)
{
byte c, nbr_bits, j;
uint code_huff = 0;
ptr_arbre a;
/* le caractere */
if (!fread(&c, 1, 1, ct->fin))
return (0);
/* le nombre de bit necessaire */
if (!fread(&nbr_bits, 1, 1, ct->fin))
return (0);
/* le code huffman */
if (nbr_bits <= 8)
{
if (!fread(&code_huff, 1, 1, ct->fin))
return (0);
}
else if (nbr_bits <= 16)
{
if (!fread(&code_huff, 2, 1, ct->fin))
return (0);
}
else
{
if (!fread(&code_huff, 4, 1, ct->fin))
return (0);
}
/* ajout à l'arbre de huffman */
a = ct->r_arbre;
for (j = 0; j < nbr_bits; j++, code_huff >>= 1)
{
if (code_huff & 0x1)
{
if (a->fils_g == 0)
{
a->fils_g = (ptr_arbre)malloc(sizeof(h_arbre));
a = a->fils_g;
a->c = -1;
a->fils_g = 0;
a->fils_d = 0;
}
else
a = a->fils_g;
}
else
{
if (a->fils_d == 0)
{
a->fils_d = (ptr_arbre)malloc(sizeof(h_arbre));
a = a->fils_d;
a->c = 0xFF;
a->fils_g = 0;
a->fils_d = 0;
}
else
a = a->fils_d;
}
}
a->c = c;
}
return (1);
}
/* Fonction de décompression */
int dh_decompression(dh_context* ct)
{
ptr_arbre a = ct->r_arbre;
uint j, i = 0, fsize = ct->fsize;
byte c;
while (!feof(ct->fin))
{
fread(&c, 1, 1, ct->fin);
for (j = 0; j < 8; j++)
{
if ((c & 0x80) == 0x80) /* 0x80 = 10000000b */
a = a->fils_g;
else
a = a->fils_d;
c = c << 1;
if ((a->fils_d == 0) && (a->fils_g == 0))
{
/* une feuille */
fwrite(&(a->c), 1, 1, ct->fout);
if (++i == fsize)
return (1);
a = ct->r_arbre;
}
}
}
return (0);
}
/* */
int decomp_huffman(const char* fsrc, const char* fdest)
{
dh_context ct;
memset(&ct, 0, sizeof(dh_context));
ct.fin = fopen(fsrc, "rb");
if (!(ct.fin))
return (0);
/* récréation de l'arbre */
if (!dh_creation_arbre(&ct))
{
dh_free_context(&ct);
return (0);
}
/* on est prés à la decompression */
ct.fout = fopen(fdest, "wb");
if (!(ct.fin))
{
dh_free_context(&ct);
return (0);
}
/* decompression des données */
if (!dh_decompression(&ct))
{
dh_free_context(&ct);
return (0);
}
dh_free_context(&ct);
return (1);
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.