Manuale di riferimento

(1)

Progetto di Marco Mandrioli matricola 210298

Generato da Doxygen 1.5.2-20070506 e modificato da Marco Mandrioli

Thu Jun 7 20:56:56 2007

(2)

(3)

1 Algoritmo di compressione con codici di Huffman 1

1.1 Introduzione. . . 1

1.2 Costruzione del codice . . . 1

1.3 Decodifica. . . 1

2 Indice dei composti 3 2.1 Lista dei composti. . . 3

3 Indice dei file 5 3.1 Lista dei file . . . 5

4 Documentazione delle classi 7 4.1 Riferimenti per la struct cod_letter . . . 7

4.2 Riferimenti per la struct node . . . 8

5 Documentazione dei file 9 5.1 Riferimenti per il file compress.c . . . 9

5.2 Riferimenti per il file compress.h . . . 14

5.3 Riferimenti per il file decompress.c. . . 15

5.4 Riferimenti per il file decompress.h. . . 17

5.5 Riferimenti per il file free.c . . . 18

5.6 Riferimenti per il file free.h . . . 19

5.7 Riferimenti per il file huffman.h . . . 20

5.8 Riferimenti per il file main.c . . . 23

6 Ottimizzazioni 25 6.1 Ottimizzazioni riguardanti la velocità di esecuzione . . . 25

6.2 Ottimizzazioni riguardanti la dimensione del file compresso. . . 25

7 Lista dei bug e delle cose da fare 27

(4)

ii INDICE

7.1 Lista dei bug noti . . . 27 7.2 Lista delle cose da fare . . . 27

(5)

Algoritmo di compressione con codici di Huffman

Autore:

Marco Mandrioli, matricola 210298

1.1 Introduzione

La codifica di Huffman è un algoritmo utilizzato per la compressione di dati, basato sulla frequenza di ogni carattere nel file da comprimere. Questa codifica prende il nome dal suo ideatore, David A. Huffman, che nel 1952 la sviluppò come tesi durante il dottorato, e che è risultata essere la codifica binaria più efficiente.

Questo tipo di codifica (o delle sue varianti) è oggi utilizzata in svariati ambiti, benchè il suo utilizzo principale sia come complemento ad altri metodi di compressione, tra i quali DEFLATE, l’algoritmo di PKZIP e dei suoi successori ZIP e WinRar, e codec multimediali quali JPEG ed MP3.

1.2 Costruzione del codice

Il codice viene costruito in base alla frequenza di ogni carattere nel file da comprimere. Viene associato ad ogni carattere un albero binario, questi alberi vengono poi ordinati in base alla frequenza della lettera che rappresenta, e i due di peso minimo diventano i figli di un altro nodo che avrà come peso la somma dei pesi dei due sottoalberi. Ripetendo questo procedimento finchè è presente più di un albero, si ottiene un albero binario le cui foglie sono i caratteri da codificare. Il codice viene ora costruito in base al percorso dalla radice alle foglie, ogni volta che si procede verso il figlio sinistro viene codificato uno zero, ogni volta che si procede verso il figlio destro viene codificato un uno. E’ interessante notare che con questo metodo si ottiene un codice a lunghezza variabile non ambiguo, in quanto è impossibile che il codice di un carattere corrisponda alla prima parte del codice di un altro carattere.

1.3 Decodifica

La codifica di Huffman, essendo differente a seconda del file che si va a comprimere, deve essere in qualche modo salvata all’inizio del file compresso stesso. Esistono diversi metodi per salvare questi dati,

(6)

2 Algoritmo di compressione con codici di Huffman

ovviamente si cerca di ridurre lo spazio necessario. Un metodo può essere ad esempio scrivere per ogni carattere la lunghezza del suo codice, il codice, e il carattere stesso, soluzione ovviamente non molto efficiente dal punto di vista dello spazio occupato.

La decodifica del codice avviene a tempo di esecuzione, leggendo la parte iniziale del file e (nel caso del- l’esempio) salvando il codice in una tabella. Questo porta alcuni vantaggi ed alcuni svantaggi, si ha infatti il vantaggio di avere il codice salvato in una struttura dati statica, e di non dover quindi dereferenziare dei puntatori, però bisogna notare che per decomprimere il file potrebbe capitare di dover fare molti confronti per ogni lettera che si deve decodificare, anche nel caso che il codice sia salvato in una tabella hash ben costruita.

La soluzione in un certo senso "opposta" è memorizzare all’inizio del file compresso l’albero di codifica, ed è la soluzione utilizzata in questa implementazione. Il vantaggio principale è di poter decodificare ogni lettera "a colpo sicuro", perchè ogni volta che viene letto un bit ci si sposta o sul figlio sinistro (zero) o sul figlio destro (uno), finchè non si raggiunge una foglia, la quale conterrà il carattere cercato.

(7)

Indice dei composti

2.1 Lista dei composti

Queste sono le classi, structs, unions e interfacce con una loro breve descrizione:

cod_letter(Struttura di un elemento della tabella di codifica ) . . . 7 node(Struttura di un nodo della lista-albero ) . . . 8

(8)

4 Indice dei composti

(9)

Indice dei file

3.1 Lista dei file

Questa è una lista dei file documentati con una loro breve descrizione:

compress.c(Compressione di un file di testo ) . . . 9

compress.h(Header del filecompress.c) . . . 14

decompress.c(Decompressione di un file di testo ) . . . 15

decompress.h(Header del filedecompress.c) . . . 17

free.c(Deallocazione delle strutture dati dinamiche ) . . . 18

free.h(Header del filefree.c) . . . 19

huffman.h(Header principale ) . . . 20

main.c(File contenente la funzione main ) . . . 23

(10)

6 Indice dei file

(11)

Documentazione delle classi

4.1 Riferimenti per la struct cod_letter

Struttura di un elemento della tabella di codifica.

#include <huffman.h>

Attributi pubblici

• intlen

lunghezza del codice

• char ∗bit

array di "bit" contenenti il codice

4.1.1 Descrizione Dettagliata

Ogni elemento della tabella di codifica contiene la lunghezza del codice e il codice stesso della lettera che rappresenta. La relazione tra un elemento della tabella e la rispettiva lettera è creata secondo la regola a=1, b=2, ..., z=25 , TERM_CHAR=26.

La documentazione per questa struct è stata generata a partire dal seguente file:

• huffman.h

(12)

8 Documentazione delle classi

4.2 Riferimenti per la struct node

Struttura di un nodo della lista-albero.

#include <huffman.h>

Attributi pubblici

• charletter lettera

• unsigned intnum

numero di occorrenze della lettera nel file da comprimere (o dei due sottoalberi del nodo)

• node∗next

puntatore all’elemento successivo (lista)

• node∗dx

puntatore al figlio destro (albero)

• node∗sx

puntatore al figlio sinistro (albero)

4.2.1 Descrizione Dettagliata

Per creare l’albero di codifica a partire da una lista ordinata è conveniente utilizzare una struttura che possa essere considerata sia come lista sia come albero binario a seconda dei casi, in modo da poter reinserire ogni nuovo nodo nella lista stessa. A questo scopo la struttura definita contiene sia un puntatore all’elemento successivo della lista sia i puntatori a figlio destro e sinistro dell’albero.

La documentazione per questa struct è stata generata a partire dal seguente file:

• huffman.h

(13)

Documentazione dei file

5.1 Riferimenti per il file compress.c

Compressione di un file di testo.

#include "huffman.h"

#include "compress.h"

#include "free.h"

Funzioni

• voidcompress_file(char ∗input_file_name, char ∗output_file_name)

Funzione che comprime il file di testo in input, richiamando le varie funzioni dedite a questo compito.

Si occupa anche di aprire e chiudere i file in input ed in output, nonchè di riportare all’inizio del file il puntatore dopo aver scorso tutto il file per creare il codice.

• unsigned int ∗letters_count(FILE ∗file_in)

Funzione che conta quante volte ogni lettera è ripetuta all’interno del file da comprimere.

• tree_ptr tree_create(FILE ∗file_in)

Funzione che inserisce quelle che dovranno poi diventare le foglie dell’albero di decodifica in una lista ordinata (in ordine crescente), richiamando primaletters_count(), poi inserendo gli elementi ordinatamente nella lista in base alla frequenza con cui sono contenute nel file da comprimere, e infine richiama la funzione list_to_tree_create(), che trasforma la lista ordinata nell’albero di codifica.

• tree_ptr list_to_tree_create(tree_ptr∗list)

Funzione che trasforma la lista ordinata in input nell’albero di codifica.

• table∗table_create(tree_ptrtree)

Funzione che crea la tabella di codifica richiamandotable_create_recursive(), che visita ricorsivamente l’albero.

• voidtable_create_recursive(tree_ptrtree, int height, int ∗code,table∗tbl)

Funzione ricorsiva per la visita dell’albero e la creazione della tabella di codifica. Quando arriva ad una foglia dell’albero salva il codice e l’altezza della foglia nella struttura corrispondente alla lettera rappresentata dalla foglia nella tabella di codifica.

(14)

10 Documentazione dei file

• voidcompress_file_text(FILE ∗file_in, FILE ∗file_out,tree_ptrtree,table∗tbl)

Funzione che richiamacreate_file_header_recursive()e poi comprime il testo del file in input e lo scrive sul file in output.

• voidcreate_file_header_recursive(FILE ∗file_out,tree_ptrtree, unsigned char ∗byte_out, unsigned char ∗mul, unsigned int ∗i)

Funzione che crea l’header del file compresso. L’header contiene i dati necessari per poter ricreare l’albero di codifica in fase di decompressione.

5.1.1 Descrizione Dettagliata

Compressione di un file di testo.

Il filecompress.ccontiene le funzioni che si occupano della creazione del codice di codifica, della creazione della tabella di codifica e della compressione del file dato in input al programma.

5.1.2 Documentazione delle funzioni

5.1.2.1 void compress_file (char ∗ input_file_name, char ∗ output_file_name)

Parametri:

input_file_name puntatore alla stringa contenente il nome del file in input output_file_name puntatore alla stringa contenente il nome del file di output

5.1.2.2 void compress_file_text (FILE ∗ file_in, FILE ∗ file_out, tree_ptr tree, table ∗ tbl)

Funzione che richiamacreate_file_header_recursive()e poi comprime il testo del file in input e lo scrive

(15)

Funzione che crea l’header del file compresso. L’header contiene i dati necessari per poter ricreare l’albero di codifica in fase di decompressione.

L’albero di codifica, per come viene costruito, non contiene nodi con un figlio solo, e le uniche foglie sono i caratteri codificati. E’ perciò possibile salvare l’albero "da sinistra verso destra", scrivendo uno zero per ogni discesa verso sinistra (per discesa si intende il passaggio dal nodo attuale ad uno dei suoi figli), e un uno ogni volta che raggiungo una foglia. Questo implica che tutto l’albero possa essere memorizzato in 2n − 1 bit (n è il numero di foglie). Infatti, per induzione, un albero con una foglia viene codificato con un bit (un uno) in quanto senza discese si arriva subito ad una foglia. Assumendo poi vero il risultato per n, si osserva che, dato un albero con n foglie, trasformando una di queste nel padre di 2 foglie, si ottiene un albero con n + 1 foglie. Per codificare questo nuovo albero sono necessari 2 bit in più di rispetto a quello precedente, infatti sono presenti:

1. uno zero in più (una discesa in più per arrivare alla foglia sinistra) 2. un uno in più (una foglia in più)

utilizzando quindi un totale di (2n − 1) + 2 = 2n + 1 bit, che è uguale ai 2(n + 1) − 1 bit ricavabili dall’ipotesi induttiva.

Di conseguenza in quest’implementazione dove i caratteri da codificare possono essere al massimo 27 (26 lettere minuscole più il carattere terminatore), l’albero avrà al più 27 foglie, ed è quindi salvabile in (al più) 53 bit.

A questo si devono ovviamente aggiungere i bit necessari per salvare il contenuto delle foglie, in questo caso quindi 27 simboli, che possono essere salvati in 5 bit ciascuno (2⁵ = 32), per un totale di 135 bit.

Sommati ai 53 necessari per l’albero fanno sì che l’header del file compresso sia salvabile al massimo in (2n − 1) + 5n = 7n − 1 = 188 bit.

Parametri:

file_out puntatore al file su cui scrivere il risultato della decompressione tree albero da utilizzare per la decodifica

byte_out puntatore al buffer di scrittura

mul puntatore alla variabile contenente il valore corrispondente al bit da scrivere i puntatore alla variabile contenente l’indice del byte del buffer di scrittura da processare

5.1.2.4 unsigned int∗ letters_count (FILE ∗ file_in)

Ritorna il puntatore ad un vettore di 27 interi senza segno. Questi interi rappresentano le volte che ogni lettera è ripetuta all’interno del file in input. Le lettere sono associate alle posizioni nell’array secondo la regola a=0, b=1, ..., z=25, TERM_CHAR=26, sfruttando anche il fatto che il codice ASCII associa alle lettere dell’alfabeto valori consecutivi (da questo risulta anche che il carattere successivo alla ’z’, ed utilizzato come carattere terminatore, sia ’{’).

Parametri:

file_in puntatore al file da comprimere

Generato il Thu Jun 7 20:56:56 2007 da Doxygen e modificato da Marco Mandrioli

(16)

Valori di ritorno:

letter puntatore ad un array di interi senza segno contenente la frequenza con cui ogni lettera è ripetuta

5.1.2.5 tree_ptr list_to_tree_create (tree_ptr ∗ list)

Funzione che si occupa di trasformare la lista ordinata in input nell’albero di codifica. Essendo la lista ordinata in modo crescente, ad ogni iterazione crea un nuovo nodo e gli associa i primi due elementi della lista come figli, dopodichè inserisce questo nuovo nodo, la cui frequenza è data dalla somma delle frequenze dei figli, nella lista (mantenendola ordinata). Ripetendo questo procedimento finchè la lista non contiene un unico elemento si ottiene l’albero.

Parametri:

list puntatore di puntatore alla testa della lista da trasformare Valori di ritorno:

∗list puntatore alla radice dell’albero di codifica

5.1.2.6 table∗ table_create (tree_ptr tree)

Utilizzare l’albero per comprimere tutto il file risulterebbe ovviamente molto costoso, in quanto nel caso pessimo sarebbe necessaria una visita completa prima di giungere alla foglia contenente la lettera cercata, perciò conviene salvare i codici in una tabella.

Parametri:

tree puntatore alla radice dell’albero di codifica Valori di ritorno:

tbl puntatore alla tabella di codifica, un array di strutture di tipocod_letterdove ogni struttura contiene il codice (e la sua lunghezza) di una lettera

(17)

code puntatore ad un vettore di byte contenente il percorso per giungere al nodo che stiamo attualmente visitando

tbl puntatore alla tabella di codifica da modificare

5.1.2.8 tree_ptr tree_create (FILE ∗ file_in)

Per quanto concerne la creazione dell’albero di codifica l’algoritmo si divide in due parti, la creazione di una lista ordinata a partire dal vettore elaborato inletters_count(), e la trasformazione della stessa in un albero. La struttura dati utilizzata è una lista-albero, di tipo structnode.

La funzionetree_create()si occupa di creare la lista ordinata scorrendo il vettore, se un elemento è maggiore di zero (ovvero se era presente almeno una volta nel file in input) crea un nuovo elemento e lo inserisce nella posizione corretta in lista. Una volta creata la lista richiamalist_to_tree_create(), che si occupa di trasformare la lista ordinata nell’albero di codifica.

Parametri:

file_in puntatore al file da comprimere Valori di ritorno:

list_to_tree_create(&list) funzione che crea l’albero di codifica a partire dalla lista ordinata

(18)

5.2 Riferimenti per il file compress.h

Header del filecompress.c.

Funzioni

• voidcompress_file(char ∗input_file_name, char ∗output_file_name)

• unsigned int ∗letters_count(FILE ∗file_in)

• tree_ptr tree_create(FILE ∗file_in)

• tree_ptr list_to_tree_create(tree_ptr∗list)

• table∗table_create(tree_ptrtree)

• voidtable_create_recursive(tree_ptrtree, int height, int ∗code,table∗tbl)

Funzione ricorsiva per la visita dell’albero e la creazione della tabella di codifica. Quando arriva ad una foglia dell’albero salva il codice e l’altezza della foglia nella struttura corrispondente alla lettera rappresentata dalla foglia nella tabella di codifica.

• voidcompress_file_text(FILE ∗file_in, FILE ∗file_out,tree_ptrtree,table∗tbl)

Funzione che richiamacreate_file_header_recursive()e poi comprime il testo del file in input e lo scrive sul file in output.

• voidcreate_file_header_recursive(FILE ∗file_out,tree_ptrtree, unsigned char ∗byte, unsigned char

(19)

Decompressione di un file di testo.

#include "decompress.h"

#include "free.h"

Funzioni

• voiddecompress_file(char ∗input_file_name, char ∗output_file_name)

Funzione che decomprime un file compresso, richiamando le varie funzioni dedite a questo compito. Si occupa anche di aprire e chiudere i file in input ed in output.

• tree_ptr decode_header(FILE ∗file_in,tree_ptr∗tree, unsigned char ∗byte_in, unsigned char ∗mul, int ∗i, int ∗j)

Funzione che decodifica l’header del file da decomprimere, e lo trasforma nell’albero necessario per la decompressione.

• void decompress_file_text(FILE ∗file_in, FILE ∗file_out, tree_ptr tree, unsigned char ∗byte_in, unsigned char ∗mul, int i, int j)

Funzione che decomprime il testo del file compresso in input e scrive sul file in output il file decompresso.

5.3.1 Descrizione Dettagliata

Decompressione di un file di testo.

Il filedecompress.ccontiene le funzioni che si occupano della decodifica dell’header, della ricostruzione dell’albero di codifica e ovviamente della decompressione del file compresso in input.

5.3.2 Documentazione delle funzioni

5.3.2.1 tree_ptr decode_header (FILE ∗ file_in, tree_ptr ∗ tree, unsigned char ∗ byte_in, unsigned char ∗ mul, int ∗ i, int ∗ j)

Questa funzione prende in input la radice dell’albero e scorrendo l’header del file da decomprimere man mano che trova uno zero alloca un nuovo nodo come figlio sinistro. Quando legge un uno, trasforma i 5 bit successivi nella lettera corrispondente e, al ritorno dalla ricorsione sul sottoalbero sinistro, ripete la stessa per ogni nodo anche sul sottoalbero destro.

Osservazioni:

Non può accadere che il file da decomprimere sia vuoto perchè, per costruzione, il file compresso contiene almeno il terminatore, e in questo caso l’header sarà formato da un solo bit, un uno. La funzione in questo caso ritornerà un albero formato da un nodo senza figli.

Parametri:

file_in puntatore al file da decomprimere

(20)

tree puntatore di puntatore alla radice dell’albero da creare byte_in puntatore al buffer di lettura

mul puntatore alla variabile contenente il valore corrispondente al bit da leggere i puntatore alla variabile contenente l’indice del byte del buffer di lettura da processare j puntatore alla variabile contenente il numero di byte letti dall’ultima fread

Valori di ritorno:

∗tree puntatore alla radice dell’albero

5.3.2.2 void decompress_file (char ∗ input_file_name, char ∗ output_file_name)

Osservazioni:

Se la funzionedecode_header()ritorna un albero formato da un solo nodo, senza figli, significa che il file che è stato compresso era vuoto, e che quindi l’header del file da decomprimere inizia con un bit impostato ad uno. In questo caso non viene quindi richiamata la funzionedecompress_file_text().

Parametri:

input_file_name puntatore alla stringa contenente il nome del file in input output_file_name puntatore alla stringa contenente il nome del file di output

5.3.2.3 void decompress_file_text (FILE ∗ file_in, FILE ∗ file_out, tree_ptr tree, unsigned char ∗ byte_in, unsigned char ∗ mul, int i, int j)

Se la radice non è anche una foglia (che significherebbe che il file di origine era vuoto) il programma comincia a decomprimere il file compresso. La decompressione avviene scorrendo il file bit a bit e proce- dendo nella visita dell’albero in base al bit che si legge: se è uno zero procede verso sinistra, se è un uno procede verso destra, e quando arriva ad una foglia stampa il valore contenuto nel campo letter della foglia

(21)

Header del filedecompress.c.

Funzioni

• voiddecompress_file(char ∗input_file_name, char ∗output_file_name)

• tree_ptr decode_header(FILE ∗file_in,tree_ptr∗tree, unsigned char ∗byte, unsigned char ∗mul, int

∗i, int ∗j)

• void decompress_file_text(FILE ∗file_in, FILE ∗file_out, tree_ptr tree, unsigned char ∗byte_in, unsigned char ∗mul, int i, int j)

5.4.1 Descrizione Dettagliata

Header del filedecompress.c.

Il filedecompress.ccontiene le funzioni che si occupano della decodifica dell’header, della ricostruzione dell’albero di codifica e ovviamente della decompressione del file compresso in input.

(22)

5.5 Riferimenti per il file free.c

Deallocazione delle strutture dati dinamiche.

#include "free.h"

Funzioni

• voidtree_free(tree_ptr∗tree)

Funzione che dealloca l’albero binario utilizzato durante la compressione e la decompressione.

• voidtable_free(table∗tbl)

Funzione che dealloca la tabella utilizzata durante la compressione.

5.5.1 Descrizione Dettagliata

Deallocazione delle strutture dati dinamiche.

Il file free.c contiene le funzioni dedite alla deallocazione della memoria occupata dalle strutture dati utilizzate, una per la deallocazione dell’albero e una per la deallocazione della tabella.

5.5.2 Documentazione delle funzioni

5.5.2.1 void table_free (table ∗ tbl)

Parametri:

tbl puntatore all’array di strutture da deallocare

5.5.2.2 void tree_free (tree_ptr ∗ tree)

(23)

Header del filefree.c.

Funzioni

• voidtree_free(tree_ptr∗tree)

Funzione che dealloca l’albero binario utilizzato durante la compressione e la decompressione.

• voidtable_free(table∗tbl)

5.6.1 Descrizione Dettagliata

Header del filefree.c.

Il filefree.ccontiene le funzioni dedite alla deallocazione della memoria delle strutture utilizzate, una per la deallocazione dell’albero e una per la deallocazione della tabella.

(24)

5.7 Riferimenti per il file huffman.h

Header principale.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <assert.h>

Composti

• structcod_letter

• structnode

Definizioni

• #defineASSERT(_cond, _errtype, _situation)

Macro che stampa un messaggio di errore e termina il programma se _cond risulta falso.

• #defineERROR_MEM_ALLOC("Allocazione della memoria non riuscita") Messaggio che appare se avviene un errore durante l’allocazione della memoria.

• #defineERROR_FILE_CREATE("Creazione del file di output non riuscita") Messaggio che appare se avviene un errore durante la creazione del file di output.

• #defineERROR_FILE_READ("Apertura del file di input non riuscita") Messaggio che appare se avviene un errore durante l’apertura del file di input.

• #defineERROR_WHILE_COMP("Si è verificato un errore durante la compressione del file:") Messaggio che appare se avviene un errore durante il processo di compressione di un file.

(25)

Dimensione (in byte) di un byte.

• #defineBIT_50x10

Valore del quinto bit in un byte (2⁵⁻¹).

• #defineBIT_80x80

Valore del quinto bit in un byte (2⁸⁻¹).

• #defineBUF_SIZEBUFSIZ

Dimensione dei buffer di input e output.

Ridefinizioni di tipo (typedefs)

• typedefcod_letter table

ridefinizione di tipo per migliorare la leggibilità del codice

• typedefnode tree_node

ridefinizione di tipo per migliorare la leggibilità del codice

• typedeftree_node∗tree_ptr

definizione del tipo puntatore ad un nodo della lista-albero

5.7.1 Descrizione Dettagliata

Header principale.

Questo header contiene le define delle macro, delle costanti e dei messaggi di errore, e le definizioni delle strutture, ed include a sua volta gli header delle librerie di sistema necessarie al programma.

5.7.2 Documentazione delle definizioni

5.7.2.1 #define ASSERT(_cond, _errtype, _situation) Valore:

{ \

if ( !(_cond) ) { \

printf _situation; \

printf("\n"); \

printf _errtype; \

printf("\n"); \

assert( _cond ); \

} \

}

Macro che stampa un messaggio di errore e termina il programma se _cond risulta falso.

(26)

Parametri:

_cond se è falso la macro viene eseguita

_errtype descrizione dell’errore che si è verificato

_situation descrizione della situazione in cui è avvenuto l’errore

(27)

File contenente la funzione main.

#include "compress.h"

#include "decompress.h"

Funzioni

• intmain(int argc, char ∗argv[ ]) Funzione main.

5.8.1 Descrizione Dettagliata

File contenente la funzione main.

5.8.2 Documentazione delle funzioni

5.8.2.1 int main (int argc, char ∗ argv[ ]) Funzione main.

Il main si occupa di processare l’input dato dall’utente, se non è stato specificato nessun file stampa un messaggio di errore e termina il programma, se è stato dato un file in input verifica che operazione deve eseguire sul file:

• compressione se il file non ha estensione ".huff", richiama la funzionecompress_file()

• decompressione se il file ha estensione ".huff", richiama la funzionedecompress_file() Parametri:

argc numero di parametri passati alla funzione

argv array di stringhe contenente i parametri passati alla funzione Valori di ritorno:

EXIT_SUCCESS (che corrisponde al valore 0 ) in caso la compressione/decompressione sia andata a buon fine

EXIT_FAILURE (che corrisponde al valore 1 ) se non viene specificato nessun file in input Osservazioni:

Gli altri errori che possono avvenire durante l’esecuzione del programma sono gestiti dalla macro ASSERT(), che termina il programma subito dopo aver visualizzato un messaggio di errore. Non è quindi il main che li gestisce e che deve controllare i valori di ritorno delle funzioni, anche se il programma in caso di errore ritorna comunque EXIT_FAILURE .

(28)

(29)

Ottimizzazioni

6.1 Ottimizzazioni riguardanti la velocità di esecuzione

• la lettura e scrittura dei singoli bit all’interno dei byte avviene mediante un contatore che viene progressivamente diviso per due, che il compilatore trasforma in uno shift verso destra di un bit (SAR r/m8, 1), operazione quindi di basso costo.

• lettura e scrittura su file avvengono in modo bufferizzato. La dimensione del buffer è impostata ad 8192 byte, che è la dimensione standard del buffer di input/output, definita in stdio.h (BUFSIZ).

Questa scelta è stata effettuata per ottenere una maggiore compatibilità, dopo avere effettuato innu- merevoli test su un file di input contenente 100 milioni di caratteri, ed avendo osservato che buffer di dimensioni comprese tra 4096 ( 2¹²) e 262144 ( 2¹⁸) byte non comportavano differenze significative nel tempo di esecuzione (differenze tra l’altro difficilmente quantificabili perchè dello stesso ordine di grandezza, qualche decimo di secondo, delle fluttuazioni dovute ad interrupt di sistema). Inoltre la dimensione ideale del buffer dipende anche dall’architettura stessa della macchina su cui è eseguito il programma, ad esempio dalla dimensione della cache e, soprattutto, dalle specifiche dell’hard disk.

• modificati alcuni cicli in modo che risultino più facilmente ottimizzabili dal compilatore (più simili al costrutto assembler LOOP ).

• rimossi alcuni confronti inutili per via della costruzione dell’albero di codifica, il quale non può avere nodi con un figlio solo (ogni nodo o ha due figli o è una foglia).

• effettuati vari test riguardanti il passaggio di parametri alle funzioni. Nel caso della funzione decompress_file_text()passando per indirizzo mul si ottiene un guadagno del 13% circa nella ve- locità di decompressione sia compilando con gcc4.2.0 che con gcc3.4.6 (il file decompress.c, se compilato con gcc3.4.6, risulta però sempre più veloce di un 25% abbondante che compilato con gcc4.2.0).

6.2 Ottimizzazioni riguardanti la dimensione del file compresso

• ridotto da 3n − 2 a 2n − 1 il numero di bit necessari a memorizzare l’albero binario, sfruttando il fatto che, per costruzione, ogni nodo o ha due figli o è una foglia, quindi se esiste il nodo sinistro deve esistere anche quello destro.

• non è necessario alcun bit aggiuntivo per determinare la fine dell’header.

(30)

26 Ottimizzazioni

• nessun byte del file compresso (escluso l’ultimo) contiene bit "inutili", come potrebbe capitare ad esempio scrivendo un byte non completamente utilizzato alla fine dell’header e cominciando la scrittura del testo compresso dal byte successivo.

(31)

Lista dei bug e delle cose da fare

7.1 Lista dei bug noti

• non sono presenti bug noti.

7.2 Lista delle cose da fare

• eliminare la limitazione relativa alle 26 lettere dell’alfabeto.

(32)

Indice analitico

ASSERT

huffman.h,21 cod_letter,7 compress.c,9

compress_file,10 compress_file_text,10

create_file_header_recursive,10 letters_count,11

list_to_tree_create,12 table_create,12

table_create_recursive,12 tree_create,13

compress.h,14 compress_file

compress.c,10 compress_file_text

compress.c,10

create_file_header_recursive compress.c,10

decode_header decompress.c,15 decompress.c,15

decode_header,15 decompress_file,16 decompress_file_text,16 decompress.h,17

decompress_file decompress.c,16

main

main.c,23 main.c,23

main,23 node,8 table_create

compress.c,12 table_create_recursive

compress.c,12 table_free

free.c,18 tree_create

compress.c,13 tree_free

free.c,18