CSI2531 Gestion de Fichiers -- Hiver 2003 Devoir #1 Valeur: 8% -- 80 points A remettre: Mardi 11 Février 03 10h30 du matin PREMIERE PARTIE: PROGRAMATION (70 points) ========================================= Généralité ---------- Ce devoir sera pour vous l'occasion d'appliquer vos connaissances sur les opérations de base de gestion de fichiers en C++ et de compression de données en écrivant deux programmes simpleo de compression et décompression d'images. Le programme de compression d'images aura comme entrée un fichier texte contenant une "image" et sortira un nouveau fichier qui est une version comprimée du fichier d'entrée. Le programme de décompression d'images aura comme entrée le fichier texte comprimée et reproduira l'image originale. Encodage à plage ("Run-Length Encoding") ---------------------------------------- L'encodage à plage (RLE) est une simple technique pour comprimer les fichiers qui fonctionne de la manière suivante. Tout d'abord, l'on choisit une valeur d'octet comme indicateur de répétition. Ensuite l'on cherche des répétitions de plages d'une seule valeur dans un fichier d'entrée pour les remplacer par un triplet composé de l'indicateur de répétition, de la valeur répétée, ainsi que du nombre de répétitions. La section 6.1.2 de notre manuel de cours vous donnera un algorithme de compression. Pour décomprimer un fichier, il est suffisant de d'abord chercher les occurrences de l'indicateur de répétition. Chaque fois que cet indicateur est trouvé, la valeur répétée est copiée autant de fois que le nombre de répétitions l'indique. Pour ce devoir, utilisez "*" comme indicateur de répétition. Matériel de lecture (pour plus de détails, mais non requis pour votre tâche) ---------------------------------------------------------------------------- http://www.rasip.fer.hr/research/compress/algorithms/fund/rl/index.html Représentation de l'image ------------------------- Les fichiers d'images que vous utiliserez sont en fait des fichiers ASCII. Voici un exemple d'une telle image": ooooooxxoooooooooooooaaooooooooooooooooo ooooooxxxxooooooooooaaaaaooooooooooooooo ooooooxxxxxxxoooooooooaaoooooxxxoooooooo oooooooooxxxoooooooooooaoxxxxxxxxooooooo ooooooooooooooxxooooooooooxxxxxooooooooo oooooooooooxxxxxxoooooooooooxxoooooooooo ooooooooxxxxxxxxxoooooooooaaoooooooooooo ooooooooooooxxxxxoooooooooaaaooooooooooo ooooooaaaoooooxxxooooooooaaaaooooooooooo ooooaaaaaoooooooooooooooooaaoooooooooooo oooooooaaoooooooooooooooxxxxxxxxoooooooo ooooooooooooooxxooooooooooxxxxxooooooooo aoooooooooooxxxxxxoooooooooooxxooooooooo aaaaooooooooxxxxxxxxxooooooooooooooooooo oaaoooooooooooxxxxxooooooooooaaaaooooooo ooooooooooooooxxxoooooooooaaaaaaaooooooo Cette image contient 3 sortes de formes, à savoir les "a", les "o" et les "x". Imaginez que c'est là une image de l'espace dans laquelle les "o" représentent une couleur d'arrière-plan, les "a" représentent une couleur plus claire que les "o" et les "x" sont la couleur la plus claire à notre disposition. En fait, l'on pourrait utiliser les espaces ("blanks") pour représenter la couleur d'arrière-plan. A la fin de chaque ligne il y a un caractère représentant une nouvelle ligne (en Windows/DOS la nouvelle ligne est représentée par deux caractères). Vous pouvez créer une telle image en utilisant un simple éditeur comme "notepad". Essayez de créer tant des images denses que dispersées afin de tester les programmes que vous aurez à écrire et de vérifierl'indice de compression. Arguments de la ligne de Commandes ---------------------------------- Le nom du fichier d'entrée de vos programmes sera donné à la ligne de commandes. Cela signifie que après avoir écrit votre programme et après l'avoir compilé et obtenu un code de commande exécutable, vous pouvez exécuter ce dernier sur l'invite DOS et y spécifier les arguments représentant les options et noms qui seront utilisés par votre programme. Les détails sur l'accès aux arguments donnés à la ligne de commandes seront donnés sur la page web du cours. En résumé, le méchanisme principal pour l'accès aux arguments de la ligne de commandes utilise les arguments "argc" et "argv" dans la fonction "main" du programme en C++ comme suit: int main (int argc, char* argv[]) { ... } Le livre de Lipman et Lajoie, les informations sur le web ou un autre livre vous en diront plus. Programme à créer ----------------- 1) "compress" Créez un projet "compress" avec un seul programme ("compress.cpp"); le code de commande exécutable sera appelé "compress.exe" par défaut, puisque "compress" est le nom du projet. Le programme "compress.exe" sera exécuté à la ligne de commandes DOS où l'utilisateur pourra spécifier ses commandes en utilisant le format suivant: compress.exe [-v] ou alternativement (en se délestant de l'extension ".exe"): compress [-v] Ici, est un fichier d'entrée existant et "-v" ("verbose") est un drapeau optionel. Si l'option "-v" est sélectionée, votre programme doit imprimer un message à l'erreur standard pour informer l'usager de l'indice de compression atteint. Cet indice est calculé en divisant la taille du fichier comprimé par celle du fichier original non-comprimé. Les données comprimées doivent être écrites dans un fichier de sortie avec le même nom que le fichier d'entrée, mais allongé du suffixe ".rle". Ainsi par exemple, si vous exécutez la commande compress.exe galaxyNGC891 le fichier de sortie comprimé devrait être "galaxyNGC891.rle". Si vous exécutez compress.exe galaxyNGC891.txt le fichier de sortie comprimé devrait être "galaxyNGC891.txt.rle". 2) "uncompress" De manière similaire à "compress", vous devez créer un projet "uncompress" avec un seul programme dedans ("uncompress.cpp") créant un code exécutable "uncompress.exe". Ce programme prendra comme entrée un fichier créé par "compress" et reproduira le fichier original non-comprimé. Le format suivant est à utiliser: uncompress Ici, est un fichier d'entrée existant devant être décomprimé. Le programme devrait tester si le nom du fichier contient l'extension ".rle" et, si ce n'est pas le cas, il devrait lui adjoindre une telle extension. De cette manière l'utilisateur devrait avoir l'option de donner le suffixe ".rle" ou pas. Ainsi donc, une commande telle que "uncompress galaxyNGC891" devrait être comprise par le programme comme "uncompress galaxyNGC891.rle". La sortie qui en résultera doit être écrite dans un fichier avec le même nom que le fichier d'entrée, cependant sans l'extension ".rle". Par exemple, si votre fichier d'entrée est "galaxyNGC891.rle", le fichier de sortie doit avoir le nom "galaxyNGC891". Traitement des erreurs d'entrée ------------------------------- Votre programme doit traiter les erreurs suivantes: - Utilisation incorrecte des arguments de la ligne de commande - Compression ou décompression de fichiers inexistants - Création d'un fichier à comprimer ou à décompresser ayant le même nom qu'un fichier existant Veuillez garder le programme simple et surtout ne demandez pas à l'utilisateur des entrées alternatives. Style de documentation ---------------------- Votre programme doit être bien documenté et écrit dans un bon style. Une partie de vos points proviendront du style et de la documentation. Afin de documenter vos programmes, écrivez des commentaires expliquant les lignes de code qui suivent le commentaire. Vous pouvez aussi ajouter des commentaires à la fin d'une ligne afin d'expliquer ce qui est fait dans cette ligne. Ajoutez une explication claire pour chaque fonction utilisée avant de donner le code de ladite fonction. Votre exlication doit contenir le but de la fonction et le sens de ses arguments. Ajoutez une explication pour chaque classe créée avant de la définir. Chosissez des noms de variable, classes, fonctions, etc. qui sont claires et intuitifs. Suivez une bonne organisation pour votre programme en créant des fonctions qui couvrent des parties appropriées de votre design et introduisez les classes de manière judicieuse. Il est à noter que, en général, on sépare les grandes classes d'un large programme en les mettant dans des fichiers différents. Cependant, pour ce devoir vous mettrez toutes vos classes relatives à chacun des projets dans un fichier unique. Précaution à prendre -------------------- Testez votre programme avec beaucoup d'arguments de ligne de commandes tenant compte des types d'erreurs mentionnées plus haut. Nous vous donnerons une ou plusieurs images afin de tester vos programmes. Ces images seront disponibles sur le web. Vous devriez créer diverses images pour test, et veuillez soumettre une d'elles. Votre programme sera testé avec l'image que vous soumettrez ainsi qu'avec d'autres de notre choix. Que soumettre? -------------- Veuillez soumettre les fichiers suivants: - "compress.cpp": (programme de compression) - "uncompress.cpp": (programme de décompression) - "image1.txt": (fichier avec une image ASCII de taille 20x20 ASCII) - "image1.txt.rle": (fichier obtenu en exécutant "compress" sur "image1.txt") - "written.txt" (fichier texte avec les réponses aux question ci-bas) CHAQUE FICHIER DOIT CONTENIR UNE BANNIERE AVEC VOTRE NOM, NUMERO D'ETUDIANT ET COURS. Tout programme ne remplissant pas les critères évoqués ci-haut sera sanctionné. Créez un directoire comme expliqué au devoir#0, copiez les cinq fichiers à soumettre dedans, "zipez" ce directoire et soumettez le comme devoir#2. En plus des spécifications données ici, votre programme doit remplir tout critère supplémentaire donné plutard sur le web our sur WebCT. IMPORTANT: La section francophone doit aussi soumettre une version imprimée de la soumission en ligne. DEUXIEME PARTIE: QUESTIONS ECRITES (10 points) ============================================== Répondez aux questions suivantes sur papier et entrez les réponses dans un fichier appelé "written.txt". -------------------------------------------------------------------------- I. Disques magnétiques (6 points) --------------------------------- Supposez que vous avez un fichier avec les caractéristiques: longueur: 1,000,000 octets organisation: 2,000 enregistrements avec 500 octets par enregistrement ainsi qu'un disque avec les caractéristiques: Nombre d'octets par secteurs = 600 Nombre de Secteurs par piste = 100 Nombre de pistes par cylindre = 4 Temp d'accès moyen (seek time) = 2 msec Délai moyen de rotation = .5 msec Temps de transfert = .01 msec/secteur = 1 msec/piste En plus de cela, assumez que le disque a l'organisation suivante: 1-a) Configuration 1: .Les enregistrements peuvent couvrir deux secteurs. .Des enregistrements consécutifs sont stockés dans des secteurs consécutifs sur une piste. .Les pistes s'étendent au hasard à travers le disque. 1-b) Configuration 2: .Seulement un enregistrement est permis par secteur. .Des enregistrements consécutifs sont stockés dans des secteurs consécutifs sur une piste et sur des pistes consécutives dans chaque cylindre. .Les pistes s'étendent au hasard à travers le disque. .Il n'y a pas de délai rotationnel entre les pistes d'un même cylindre lors d'accès séquentiels. .Les cylindres s'étendent au hasard à travers le disque. Pour chacune des configurations ci-dessus, calculez: A) Le temps que prendrait une lecture SEQUENTIELLE complète du fichier. B) Le temps que prendrait une lecture complète en accès aléatoire ("RANDOM ACCES"); c'est-à-dire, le temps pris en traversant chaque enregistrement une fois en ordre aléatoire. C) La fragmentation interne présente dans le fichier à cause de l'espace inutilisé. Montrez les détails de vos calculs. -------------------------------------------------------------------------- II. Bandes magnétiques (4 points) --------------------------------- Supposez que nous ayions la description suivante d'une bande magnétique: Densité = 3,000 bpi Espace interblock = 0.2 inch Vitesse = 200 ips ainsi que les caractéristiques suivantes: nombre d'enregistrements = 1,000 taille de l'enregistrement = 30 Utilisant un facteur de block de 50 et 100, calculez les quantités suivantes: A) Longueur (en pieds) de la bande requise pour stocker le fichier (1 pieds = 12 pouces). B) Densité d'enregistrement effectif. C) Taux de transmission effectif. Montrez les détails de vos calculs.