Introduction

Le rendu du TP noté doit se faire sur arche

Il est conseillé de traiter la question 3, elle pourrait être utile le jour de l'examen final (pas du TP)

Les fichiers nécessaires à la résolution des questions se trouvent ici.

Voici le rendu attendu pour chacune des questions:

Q1	Un fichier .c
Q2		Le résultat de la décompression des 4 fichiers
Q3	Un fichier .c	Trois fichiers png
Q4	Un fichier .c
Q5	Un fichier .c	Le résultat de la compression du fichier lucky
Q6	Un fichier .c	Le résultat de la compression du fichier lucky
Q7		Un fichier .txt répondant à la question

Le but du TP noté est d'implémenter un compresseur/décompresseur LZ77/LZSS.

Pour avoir une note correcte, il est attendu a minima une réponse aux question 1,2,3 et 7, ou 2,3,4 et 7.

Le travail doit être effectué seul. Il est possible de récupérer des fichiers venant des TPs précédents. L'usage d'internet est restreint à l'accès aux pages concernant le cours.

Tout non-respect des consignes sera sanctionné. En particulier, si le travail n'a pas été effectué seul, une pénalité d'un minimum de 20 points sera appliquée.

• Le fichier est constitué de blocs: chaque block contient d'abord des littéraux (éventuellement 0) puis des paires (éventuellement 0).
• Chaque block commence par le nombre de littéraux qu'il contient (codé sur 3 bits) et le nombre de paires qu'il contient (codé sur 5 bits). Si les deux nombres sont nuls, c'est que la fin du fichier est atteinte.
• Suivent ensuite les littéraux, codés sur 8 bits.
• Suivent ensuite les paires:
  • La position est codée sur 12 bits. Pour trouver la position dans le fichier, il faut ajouter 1 au résultat.
  • Le nombre de lettres à recopier est j+3, où j est codé par un code de Huffman
    • 0 est codé par 00
    • 1 est codé par 01
    • 2 est codé par 10
    • 3 est codé par 110
    • Si j est plus grand que 4, il est codé par 111, suivi de la valeur de j - 4, codée sur 5 bits

Prenons l'exemple de la représentation de ab(2,3)d(6,8)(5,4). Il y aura trois blocs:

• Le block correspondant à ab(2,3) (2 littéraux, une paire)
• Le block d(6,8)(5,4) (1 littéral, 2 paires)
• Le block de fin
  Le premier block sera codé par

  010 00001 01100001 01100010 000000000001  00
   2     1        a      b        1 (+1)    0(+3)
  

  Le second block sera codé par

  001 00010   01100100  000000000101  11100001  000000000100  01
   1     3     d          5 (+1)      1(+4+3)    4 (+1)      1(+3)
  

  et le troisième block sera codé par

  000 00000
   0    0 
  

Q1. Ecrire l'algorithme de décompression. On supposera pour simplifier que la taille du résultat est plus petite que 100000 octets, de sorte qu'on pourra la mettre dans un tableau char text[100000]; déclaré en variable globale

Q2. Tester le résultat du programme sur les fichiers lucky.lzo, texte.lzo (un texte), logo.pgm.lzo (un logo) et photo.ppm.lzo (une photo).

Q3. Pour chacun des 3 fichiers, calculer, pour chaque position p, combien de fois elle apparaît dans le fichier. Pour avoir un graphique plus facile à lire, on groupera ensemble les positions par paquets de 10: de 0 à 9, de 10 à 19, etc.. On affichera le résultat sous la forme d'un fichier png. On pourra commencer par regarder le fichier toto.dat et lancer la commande gnuplot toto.plot.

Q4. Ecrire, dans le fichier tests.c, la fonction communs(char* x, char* y, int n) qui indique le nombre de caractères en commun au début des chaînes de caractères x et y (avec un maximum de n)

Q5. Utiliser la fonction précédente pour créer un logiciel de compression. Pour cette question, on ne cherchera pas à "regrouper" ensemble les blocs.

Q6. Changer le programme de la question précédente pour qu'il regroupe les littéraux et les paires par blocs.

Q7. On se donne un fichier de départ, dont la taille est exactement 1000 octets. Montrer qu'il est possible de le compresser en un fichier .lzo dont la taille est exactement 1126 octets, par un programme qui n'utilise PAS bits.h et bits.c. (Il n'est pas demandé de réaliser le programme).