:: Enseignements :: Licence :: L2 :: 2008-2009 :: Programmation Avancée en C ::

Encodage des entiers

Nous souhaitons développer une bibliothèque de codage d'entiers. Tout d'abord nous utilisons une méthode de codage des entiers sur un nombre variable d'octets (avec 7 bits utiles de codage par octet et un bit indiquant la terminaison de l'entier). Ensuite nous développons un module de lecture et d'écriture bit-à-bit pour coder des entiers sur un nombre variable de bits. Les entiers considérés sont toujours non signés.

Exercice 1 - Octet par octet

Pour la première méthode on découpe l'écriture binaire d'un entier en paquets de 7 bits. A chaque paquet on ajoute un bit de poids fort indiquant si l'écriture se poursuit sur l'octet suivant. Par exemple,

5 s'écrit (101)₂ donc on codera par l'octet 00000101,
707 s'écrit (1011000011)₂ donc on codera par 2 octets, 10000101 et 01000011.

Exercice 2 - Bit par bit

On peut écrire chaque entier sur un nombre variable de bits, si on indique d'abord le nombre de bits à considérer. Ceci peut se faire en unaire, avec une suite de 1 de longueur égale aux nombre de bits utilisés, suivis d'un 0 pour séparer. Par exemple, 5 s'écrira 1110101 : 111 pour dire 3 bits, 0 pour séparer, 101 pour le nombre proprement dit.

On peut faire mieux, en remarquant que les nombres commencent par 1 sauf 0, et qu'il faut donc toujours au moins un bit. On peut donc améliorer (légèrement) la méthode en encodant n+1 à la place de n, et en omettant le premier bit à chaque fois. Donc pour écrire 5, on écrit d'abord 6, donc 1110110, puis on omet les bits en gras, ce qui donne 11010.

En C, on ne peut écrire dans un fichier que par octet. Ecrire les fonctions de bas niveau pour écrire un bit, finir d'écrire dans le fichier, lire un bit. Ensuite, écrire le compresseur lui-même.

Mise en forme

Pour chaque méthode, il devra y avoir un compresseur et un décompresseur. Le premier prend en argument des nombres et crée un fichier output. Le deuxième lit le fichier en question. Par exemple,

$ ./octet_comp 398 3098 21 1 938220
$ ./octet_decomp output
398 
3098 
21 
1 
938220