Figure 1 - Exemple d'écriture bit à bit avec un tampon de 1 octet
En C, il n'existe pas d'opérateur permettant de changer la valeur d'un bit particulier dans une variable (de toutes façons, ce genre d'instruction n'existe pas forcément dans le langage machine cible). Cependant, en utilisant judicieusement les opérateurs de décalage (<< et >>), la négation bit à bit (~) et les opérateurs logiques bit à bit (| et &), il est possible de manipuler chacun des bits d'une variable indépendamment. A titre d'exemple, l'expression suivante à la même valeur que le bit 4 de la variable toto (le bit 0 étant le bit de poids faible) :
(toto >> 4) & 1Exercice :
La bibliothèque C standard offre de nombreuses fonctions d'accès à un fichier. Ce sont, entre autres, les fonctions fopen, fscanf, fprintf, ... dont les prototypes sont fournis dans stdio.h. Ces fonctions permettent d'ouvrir un ficher en lecture ou écriture puis d'y écrire ou lire des caractères, des entiers, des flottants, etc. Malheureusement, la bibliothèque standard n'offre pas de moyen de lire ou d'écrire un seul bit à la fois dans un fichier.
Le but de ce TD est d'écrire une bibliothèque permettant d'effectuer des entrées/sorties bit à bit dans un fichier. Une telle bibliothèque se révélera particulièrement utile pour implémenter des algorithmes de compression (par exemple). Le problème qui se pose lors de la réalisation de fonctions d'accès bit à bit aux fichiers est que nous devons les réaliser en nous servant des fonctions standard pour lesquelles la taille minimale d'un accès est l'octet (8 bits).
Une réalisation possible pour les fonctions d'écriture de cette bibliothèque consisterait à maintenir un ensemble de bits en attente d'écriture (dans une variable, qui nous servirait ainsi de mémoire tampon) et, dès que ces bits sont au nombre de huit, de réaliser l'écriture de l'octet correspondant à l'aide d'une des fonctions de la bibliothèque standard. Pour les fonctions de lecture, nous pouvons utiliser la même idée en maintenant un octet lu à l'avance dans le fichier duquel nous extrayons les bits les uns après les autres au fur et à mesure des demandes. La figure ci-dessous illustre cela pour l'exemple d'une écriture bit à bit avec un tampon de 1 octet :
/*
bstart
description : démarre un accès bit à bit au fichier dont le descripteur est
passé en paramètre (le fichier doit avoir été préalablement
ouvert).
Pour conserver la cohérence des données, aucun accès non bit à
bit au même descripteur ne doit être fait jusqu'au prochain
bstop.
paramètres : descripteur du fichier, le mode dans lequel le descripteur est
ouvert.
valeur de retour : pointeur vers une structure BFILE allouée par bstart
ou NULL si une erreur est survenue
effets de bord : aucun (outre l'allocation)
*/
BFILE *bstart(FILE *fichier, const char *mode);
/*
bstop
description : termine un accès bit à bit à un fichier préalablement démarré
par bstart (termine les E/S en attente et libère la structure
BFILE).
paramètres : pointeur vers une structure BFILE renvoyée par bstart
valeur de retour : 0 si aucune erreur n'est survenue
effets de bord : écrit potentiellement dans le fichier
*/
int bstop(BFILE *fichier);
/*
bitread
description : lit un bit dans un fichier sur lequel un accès bit à bit
a été préalablement démarré a l'aide de bstart.
paramètres : pointeur vers une structure BFILE renvoyée par bstart
valeur de retour : bit lu ou -1 si une erreur s'est produite ou si la
fin de fichier a été atteinte
effets de bord : la valeur de retour dépend du contenu du fichier
lit potentiellement dans le fichier
*/
char bitread(BFILE *fichier);
/*
bitwrite
description : écrit un bit dans un fichier sur lequel un accès bit à bit
a été préalablement démarré à l'aide de bstart.
paramètres : pointeur vers une structure BFILE renvoyée par bstart, bit à
écrire
valeur de retour : -1 si une erreur s'est produite
effets de bord : écrit potentiellement dans le fichier
*/
int bitwrite(BFILE *fichier, char bit);
/*
beof
description : retourne 1 si un accès en lecture préalable a échoué pour
cause d'atteinte de la fin d'une séquence de bits (fin de
fichier ou fin de séquence codée dans le fichier), 0 sinon.
L'accès bit à bit doit avoir été préalablement démarré à
l'aide de bstart.
paramètres : pointeur vers une structure BFILE renvoyée par bstart
valeur de retour : 1 ou 0
effets de bord : aucun.
*/
int beof(BFILE *fichier);
La spécification précédente n'est pas très satisfaisante en ce qui concerne la fin d'un accès bit à bit. Théoriquement, nous devrions pouvoir insérer un nombre quelconque de bits (pas forcément multiple de 8) à n'importe quelle position lors de l'accès à un fichier. Le problème vient de la relecture : comment déterminer à quel moment la séquence de bits se termine alors qu'on ne peut lire que des octets, c'est-à-dire des groupes de 8 bits ?
Une première solution, un peu naïve, serait d'écrire le nombre de bits contenus dans la séquence au tout début de celle-ci. Le désavantage de cette méthode est que, pour compter la séquence de bits, elle oblige à conserver en mémoire une séquence qui peut être arbitrairement longue avant de réaliser l'écriture proprement dite dans le fichier. On peut limiter l'effet néfaste du problème en découpant la séquence en tranches (de 1024 bits par exemple). Autrement dit une séquence de bits serait alors constituée d'une séquence de tranches, chacune constituée de sa taille (entre 0 et 1024) en suivie des bits eux même.
Une autre idée serait de s'inspirer des techniques utilisées dans les réseaux (au niveau de la couche liaison de données) afin de délimiter nos séquences. L'idée est de réquisitionner une séquence de données particulière pour indiquer la présence de directives destinées à la bibliothèque de gestion d'accès bit à bit. Par exemple, nous pouvons réquisitionner l'octet 0xFF pour coder nos directives. Cet octet sera toujours suivi d'un second octet codant la directive proprement dite. Un exemple de contenu possible pour ce second octet peut être :
il convient alors, lors de l'écriture des données dans le fichier, de remplacer tout octet de valeur 0xFF par une séquence de deux octets successifs de valeur 0xFF (on recode la donnée réquisitionnée en son équivalent sous forme de directive) et lors de la lecture de traiter le cas particulier des directives.
Exercice :Bien entendu, une fois que vous aurez proposé une implémentation complète des accès bit à bit à un fichier, il sera nécessaire de la tester. Des tests manuels rapides permettent souvent de mettre au point une première implémentation et de repérer les plus gros bugs, mais ils sont souvent insuffisants. Pour les compléter, il faudrait idéalement tester tous les cas de séquence de bits possibles aussi bien en écriture qu'en lecture. Malheureusement, ceci n'est généralement pas possible en raison du nombre trop grand (éventuellement infini) de cas différents. A défaut, le test d'un programme repose généralement sur une ou plusieurs des techniques suivantes :