CODAGE HUFFMAN

/*
 * 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);
}