Huffman/arbre.c

#include "arbre.h"

int listeVersArbre(Liste *liste) {
    Cellule *curseur = *liste;
    int nombreLettresDansFichier = 0;
    while (curseur != NULL) { // parcours de la liste
        if (curseur->lettre != '\0') nombreLettresDansFichier++; // +1 au compteur si c'est bien une lettre
        if (curseur->suivant != NULL) { // on créer un mini-arbre qu'on colle au reste de l'arbre seulement si le suivant existe
            Cellule *nouvelleCellule;
            if ((nouvelleCellule = (Cellule*)malloc(sizeof(Cellule))) == NULL) { // on alloue de la mémoire pour notre nouvelle cellule (mini-racine)
                printf("Impossible d'allouer de la mémoire supplémentaire (listeVersArbre).\n"); // gestion de l'erreur
                exit(1);
            }

            nouvelleCellule->gauche = curseur; // membre gauche = curseur
            nouvelleCellule->droite = curseur->suivant; // membre droit = élément suivant dans la liste
            nouvelleCellule->lettre = '\0';
            nouvelleCellule->frequence = nouvelleCellule->gauche->frequence + nouvelleCellule->droite->frequence;

            if (curseur->suivant->lettre != '\0') nombreLettresDansFichier++; // +1 si le suivant est aussi une lettre (membre droit)

            curseur = curseur->suivant->suivant; // on va au suivant 2x car on a déjà ajouté le suivant en tant que membre droit

            *liste = curseur; // on change le point de départ de notre liste pour ne pas traiter en boucle les anciennes cellules
            ajouterRangee(liste, nouvelleCellule); // on ajoute à la liste notre nouvelle cellule
            curseur = *liste; // on met à jour le curseur
        } else { // cas du dernier élément
            *liste = curseur;
            curseur = curseur->suivant;
        }
    }

    return nombreLettresDansFichier;
}

void assignationCode(Arbre arbre, int codeActuel, int longueur, Entete *enteteListe, int *i, int *longueurTotale) {
    if (arbre->lettre != '\0') { // si c'est une lettre qu'on regarde
        enteteListe[*i].lettre = arbre->lettre; // ajout de la lettre
        enteteListe[*i].code = codeActuel; // assignation de son code
        enteteListe[*i].longueur = longueur; // longueur du code (ex: 1001 est de taille 4)

        *i += 1; // on incrémente de 1
        *longueurTotale += longueur * arbre->frequence; // incrémente la taille du code à la taille totale finale
    } else { // si c'est une "mini-racine"
        longueur++;
        codeActuel <<= 1; // décalage de bit vers la gauche
        assignationCode(arbre->gauche, codeActuel, longueur, enteteListe, i, longueurTotale); // appel récursif arbre de gauche
        codeActuel |= 1; // copie de bit si nécessaire (porte ou)
        assignationCode(arbre->droite, codeActuel, longueur, enteteListe, i, longueurTotale); // appel récursif arbre de droite
    }
}

void freeArbre(Arbre arbre) {
    if (arbre->lettre == '\0') { // free aussi les mini-racines
        freeArbre(arbre->gauche);
        freeArbre(arbre->droite);
    }

    free(arbre); // free du noeud courant
}

Entete *arbreVersListe(Arbre arbre, int taille, int *tailleTotale) {
    Entete *enteteListe;
    if ((enteteListe = (Entete*)malloc(taille * sizeof(Entete))) == NULL) { // on alloue la liste qui va contenir nos caractères
        printf("Impossible d'allouer de la mémoire supplémentaire (arbreVersListe).\n"); // gestion de l'erreur
        exit(1);
    }
    int i = 0; // initialisation de `i` au début car `assignationCode` est récursif
    assignationCode(arbre, '\0', 0, enteteListe, &i, tailleTotale); // on commence avec une racine nulle et une taille de 0
    freeArbre(arbre);

    return enteteListe;
}

Entete *fichierVersListe(FILE *fichier, int *nombreLettresDansFichier, int *tailleTotale) {
    char lettre = 'a'; // initalisation pour éviter un warning
    Liste liste = NULL;
    while (lettre != EOF) {
        lettre = fgetc(fichier);
        ajouterLettre(&liste, lettre);
    }
    rewind(fichier);

    trierListe(&liste);
    *nombreLettresDansFichier = listeVersArbre(&liste);

    return arbreVersListe(liste, *nombreLettresDansFichier, tailleTotale);
}

void compression(FILE *entree, FILE *sortie) {
    int nombreLettresDansFichier; // initialisé par `listeVersArbre`
    int tailleTotale = 0; // taille totale en bit du fichier en sortie
    Entete *enteteListe = fichierVersListe(entree, &nombreLettresDansFichier, &tailleTotale);

    // On écrit l'entête du fichier avec la table complète des correspondances
    enteteVersFichier(enteteListe, nombreLettresDansFichier, tailleTotale, sortie);

    // On écrit les données huffman-isée dans le fichier
    huffmanVersFichier(entree, sortie, enteteListe, nombreLettresDansFichier);

    free(enteteListe); // libération de la liste car utilisation du malloc dans `arbreVersListe`
}

void enteteVersFichier(Entete *enteteListe, int nombreLettresDansFichier, int longueurTotale, FILE *fichier) {
    fwrite(&nombreLettresDansFichier, sizeof(int), 1, fichier); // stockage du nombre de lettres dans le fichier
    fwrite(&longueurTotale, sizeof(int), 1, fichier); // stockage de la taille totale
    for (int i = 0; i < nombreLettresDansFichier; i++) { // on parcours l'entete et on y ajoute la table de huffman utilisé
        fwrite(&(enteteListe[i].lettre), sizeof(char), 1, fichier);
        fwrite(&(enteteListe[i].code), sizeof(int), 1, fichier);
        fwrite(&(enteteListe[i].longueur), sizeof(int), 1, fichier);
    }
}

void huffmanVersFichier(FILE *entree, FILE *sortie, Entete *enteteListe, int nombreLettresDansFichier) {
    int buffer = 0, tailleBufferActuelle = 0, sizeOfInt = sizeof(int) * 8; // *8 car quelque fois certains caractères sont mal encodés (en plus ça réduit la taille du fichier final)
    char lettre = 'a'; // initialisation pour éviter un warning
    while (lettre != EOF) { // on parcours le fichier
        lettre = fgetc(entree);
        Entete entete = recuperationLettre(lettre, enteteListe, nombreLettresDansFichier); // rappel: entete représente une liste de caractères
        if (tailleBufferActuelle + entete.longueur >= sizeOfInt) { // écriture dans le fichier
            // Modification du buffer
            int aAjouter = sizeOfInt - tailleBufferActuelle;
            if (aAjouter < 32)
                buffer <<= aAjouter; // décalage vers la gauche
            else { // évite un overflow (https://gcc.gnu.org/onlinedocs/gcc/Static-Analyzer-Options.html#index-Wanalyzer-shift-count-overflow)
                printf("Déplacement de bits trop important (aAjouter >=32 [=%d])", aAjouter);
                exit(1);
            }

            // Ajout de la lettre
            int tmp = entete.code >> (entete.longueur - aAjouter);
            entete.longueur -= aAjouter;

            // Écriture dans le fichier ici
            buffer |= tmp;
            fwrite(&buffer, sizeof(int), 1, sortie);

            buffer = 0, tailleBufferActuelle = 0; // reset du buffer
        }
        // Mise à jour du buffer
        tailleBufferActuelle += entete.longueur;
        buffer <<= entete.longueur; // décalage vers la gauche
        buffer |= entete.code;
    }
    if (tailleBufferActuelle > 0) {
        buffer <<= sizeOfInt - tailleBufferActuelle; // décalage vers la gauche
        fwrite(&buffer, sizeof(int), 1, sortie);
    }
}

Entete recuperationLettre(char lettre, Entete *enteteListe, int nombreLettresDansFichier) {
    for (int i = 0; i < nombreLettresDansFichier; i++)
        if (enteteListe[i].lettre == lettre)
            return enteteListe[i];

    exit(1);
}

Arbre lectureDonnees(FILE *fichier, int *tailleTotale) {
    int nombreLettresDansFichier, lecture = 0; // bytes lues
    lecture += fread(&nombreLettresDansFichier, sizeof(int), 1, fichier);
    lecture += fread(tailleTotale, sizeof(int), 1, fichier);

    Entete *entete;
    if ((entete = (Entete*)malloc(nombreLettresDansFichier * sizeof(Entete))) == NULL) { // on alloue de la mémoire pour l'entête
        printf("Impossible d'allouer de la mémoire supplémentaire (lectureDonnees).\n"); // gestion de l'erreur
        exit(1);
    }

    Arbre arbre = allouerCellule('\0');
    for (int i = 0; i < nombreLettresDansFichier; i++) {
        // Lecture de l'entête
        lecture += fread(&(entete[i].lettre), sizeof(char), 1, fichier);
        lecture += fread(&(entete[i].code), sizeof(int), 1, fichier);
        lecture += fread(&(entete[i].longueur), sizeof(int), 1, fichier);

        // Ajout de la lettre à l'arbre
        Cellule *curseur = arbre;
        int mask = 1; // mask est le masque de bit appliqué pour savoir si on doit aller a la gauche ou a la droite de l'arbre
        mask <<= entete[i].longueur - 1; // décalage vers la gauche de la longueur de la lettre - 1

        for (int j = 0; j < entete[i].longueur; j++) {
            int gaucheOuDroite = entete[i].code & mask;

            entete[i].code <<= 1; // décalage de 1 vers la gauche pour éviter la segfault
            if (gaucheOuDroite) { // droite
                if (curseur->droite == NULL) curseur->droite = allouerCellule('\0'); // on remplace NULL par le caractère correspondant
                curseur = curseur->droite;
            } else { // gauche
                if (curseur->gauche == NULL) curseur->gauche = allouerCellule('\0'); // on remplace NULL par le caractère correspondant
                curseur = curseur->gauche;
            }
        }
        curseur->lettre = entete[i].lettre; // on assigne la bonne lettre correspondante
    }

    free(entete); // on libère l'entête car on en a plus besoin

    printf("%d bytes lus pour reconstruire l'arbre.\n", lecture);
    return arbre;
}

void huffmanDepuisFichier(FILE *entree, FILE *sortie, Arbre arbre, int tailleTotale) {
    int mask = 1, buffer, bitsLus = 0, lecture = 0, sizeOfInt = sizeof(int) * 8;
    int bitsMax = tailleTotale / sizeOfInt;

    if(tailleTotale % sizeOfInt != 0) bitsMax++; // parce que c'est un arbre binaire

    mask <<= sizeOfInt - 1; // on récupère le bon bit

    Cellule * curseur = arbre;
    for (int i = 0; i < bitsMax; i++) { // on parcours le fichier
        lecture += fread(&buffer, sizeof(int), 1, entree);

        for (int j = 0; bitsLus < tailleTotale && j < sizeOfInt; j++) {
            if (curseur->lettre != '\0') { // update de l'arbre si on est sur une 'mini-racine'
                fprintf(sortie, "%c", curseur->lettre); // on ajoute le caractères dans le fichier de sortie
                curseur = arbre;
            }

            if(mask & buffer) curseur = curseur->droite; // droite
            else curseur = curseur->gauche; // gauche
            bitsLus++; // on incrémente bitsLus de 1
            buffer <<= 1; // update du buffer
        }
    }

    printf("%d bytes lus pour reconstruire le fichier.\n", lecture);
}

void decompression(FILE *entree, FILE *sortie) {
    int tailleTotale; // taille totale en bit du fichier en entrée
    Arbre arbre = lectureDonnees(entree, &tailleTotale);
    huffmanDepuisFichier(entree, sortie, arbre, tailleTotale);

    freeArbre(arbre); // on libère l'arbre
}