huffman/src/compress.c

#include "common.h"
#include "compress.h"
#include "buffer.h"
#include "huftree.h"
#include "display.h"

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdint.h>

/**
 * Effectuer un comptage des caractères dans le fichier d'entrée
 * (résultat à libérer avec `free`)
 */
bytecount* _countCharacters(FILE*, bytecount* total);

/**
 * Encoder le fichier d'entrée vers le fichier de sortie
 * en suivant les étiquettes passées. Les étiquettes
 * peuvent être calculées avec labelTree()
 */
static void _encodeFromTable(char**, FILE*, WriteBuffer*);

bytecount* _countCharacters(FILE* file, bytecount* total) {
    bytecount* counts = malloc(NUM_CHARS * sizeof(*counts));
    *total = 0;

    for (size_t i = 0; i < NUM_CHARS; i++) {
        counts[i] = 0;
    }

    // Lecture du fichier caractère par caractère et comptage
    int current;

    while ((current = fgetc(file)) != EOF) {
        assert(current >= 0 && current < NUM_CHARS);
        counts[current]++;
        (*total)++;
    }

    return counts;
}

void _encodeFromTable(char** labels, FILE* source, WriteBuffer* output) {
    int current;

    // Lecture du fichier d'entrée caractère par caractère
    while ((current = fgetc(source)) != EOF) {
        assert(current >= 0 && current < NUM_CHARS);
        char* label = labels[current];
        assert(label != NULL);

        // Ajout du label dans le buffer, caractère par caractère
        // vidant progressivement le buffer
        while (*label != '\0') {
            putBuffer(*label == '1', output);
            label++;
        }
    }
}

void compress(FILE* source, FILE* dest) {
    // ÉTAPE 1 : calcul des effectifs de chaque caractère dans le fichier
    // source. Ce programme prend le terme caractère au sens restreint
    // d'octet. Dans le cas où l'on compresse des fichiers Unicode
    // utilisant des caractères sur plusieurs octets, on aura donc une
    // compression moins optimale.
    printVerbose("Calcul des fréquences d'apparition des caractères.\n");
    bytecount original_count = 0;
    bytecount* counts = _countCharacters(source, &original_count);

    if (isVerbose()) {
        printCountsTable(counts, original_count, NUM_CHARS);
    }

    // ÉTAPE 2 : construction d'un arbre de Huffman correspondant aux
    // fréquences d'apparition des caractères
    printVerbose("\nConstruction de l'arbre de Huffman.\n");
    HufTree tree = createTree(counts);

    free(counts);
    counts = NULL;

    if (isVerbose()) {
        printTree(tree);
    }

    // ÉTAPE 3 : calcul de la clef de codage en étiquettant les chaque feuille
    // de l'arbre. Pour chaque sommet traversé, s'il est le fils gauche de son
    // parent, l'étiquette est augmentée d'un '0', sinon elle l'est d'un '1'
    printVerbose("\nÉtiquetage des feuilles de l'arbre.\n");
    char** labels = createTreeLabels(tree);

    if (isVerbose()) {
        printLabelsTable(labels, NUM_CHARS);
    }

    // ÉTAPE 4 : écriture des données compressées vers la sortie. Les données
    // écrites permettent de restituer le fichier originel : nombre de
    // caractères stockés, arbre de Huffman et données compressées brutes
    WriteBuffer output = createWriteBuffer(dest);
    printVerbose("\nÉcriture des données compressées.\n");

    // - Entier 64 bits : nombre d'octets dans le fichier originel
    fwrite(&original_count, sizeof(uint64_t), 1, dest);

    // - Arbre linéarisé : arbre de Huffman permettant le calcul de la clef
    writeTree(tree, &output);

    // - Données compressées brutes (caractères originels traduits dans
    //   la clef de codage calculée avant)
    rewind(source);
    _encodeFromTable(labels, source, &output);
    flushBuffer(&output);

    // ÉTAPE 5 : affichage des statistiques de compression et fin
    bytecount final_count = sizeof(uint64_t) + getFlushedCount(&output);
    double gain = ((double) original_count - final_count) /
        original_count * 100;

    printVerbose("Taille originelle : %llu octets.\n", original_count);
    printVerbose("Taille compressée : %llu octets.\n", final_count);
    printVerbose("Gain : %.2f %% !\n", gain);

    freeTree(tree);
    freeTreeLabels(labels);
    labels = NULL;
}