TP3 du morse
Description
Le code Morse fut pendant un temps le codage standard de l’information textuelle sur le réseau. De nos jours, le codage est pratiquement tombé en désuétude est n’est plus utilisé que dans des reconstituions historiques, des compétitions informatiques et des travaux pratiques d’étudiants.
Toutefois, en ces temps où la population ressent un réel besoin de protection de sa vie privée et de la sécurité de sa communication, le code morse pourrait revenir une option valide (en fait, c’est peu probable).
L’objectif de ce TP est de concevoir une bibliothèque de décodage Morse qui convertit un texte en code morse des un texte en clair. La particularité est que le code Morse utilisé est personnel et peut être modifié ou étendu afin d’augmenter de respect de la vie privée des utilisateurs.
Structure morse
Pour permette à l’utilisateur d’utiliser un codage morse personnel, une structure arborescente est utilisée pour représenter un code morse spécifique qui associe des séquences de .
et de -
vers des caractères ASCII en clair.
Chaque nœud de la structure fait 24 octets doit respecter la forme suivante :
mCar
: le caractère en clair codé par ce maillon, ou'\0'
s’il n’y en a pas (un octets) ;- 7 octets à 0 (réservés pour un usage futur très hypothétique) ;
mPoint
: l’adresse du nœud suivant pour un point.
, ou 0 si absent (8 octets) ;mTiret
: l’adresse du nœud suivant pour un tiret-
, ou 0 si absent (8 octets) ;- la structure est aligné à 8 octets.
Un codage morse est identifié par un nœud racine, ensuite, les séquences de .
et de -
du code morse à déchiffrer sont utilisés pour naviguer dans l’arborescence (via respectivement mPoint
et mTiret
), le nœud sur lequel on termine contient le caractère en clair décodé dans mCar
.
Si mPoint
ou mTiret
valent 0, ou si le mCar
du nœud d’arrêt est '\0'
, alors le code est invalide et ne correspond à aucun caractère en clair (toutes les séquence de points et de tiret ne signifie pas forcément quelque chose).
Exemple ESTO
Soit le code morse ESTO minimal restreint aux 4 lettres en clair :
E
codé par.
T
codé par-
S
codé par...
O
codé par---
Celui-ci correspond à l’arborescence suivante composé de 7 nœuds :
racine--> +--------(1)-+
| mCar: '\0' |
/-------mPoint |
| | mTiret---------\
| +------------+ |
V V
+--------(2)-+ +--------(3)-+
| mCar: 'E' | | mCar: 'T' |
| mPoint--------\ | mPoint: 0 |
| mTiret: 0 | | | mTiret---------\
+------------+ | +------------+ |
V V
+--------(4)-+ +--------(5)-+
| mCar: '\0' | | mCar: '\0' |
/-------mPoint | | mPoint: 0 |
| | mTiret: 0 | /----mTiret |
| +------------+ | +------------+
V V
+--------(6)-+ +--------(7)-+
| mCar: 'S' | | mCar: 'O' |
| mPoint: 0 | | mPoint: 0 |
| mTiret: 0 | | mTiret: 0 |
+------------+ +------------+
Cette représentation arborescente permet de décoder très rapidement tout caractère en clair codé par une séquence morse même si le code morse est immense.
- La séquence
...
donne le chemin 1→2→4→6, le nœud 6 est associé à la lettre en clair'S'
, donc...
correspond à cette lettre. - La séquence
-
donne le chemin 1→3, le nœud 3 est associé à la lettre en clair'T'
, donc-
correspond à cette lettre. - La séquence
--
donne le chemin 1→3→5, le nœud 5 est associé à'\0'
, donc--
ne correspond aucune lettre en clair dans le code morse ESTO. - La séquence
-.
ne donne aucun chemin 1→3→X, vu qu’il n’y a pas de sortie pour un point dans le nœud 3 ; donc-.
correspond non plus à aucune lettre en clair. - Note: la séquence vide donne un chemin qui reste sur le nœud racine (1). Ce nœud est associé ici à
'\0'
donc ne correspond à rien. Toutefois, en toute généralité, la chaîne vide pourrait être associée à une lettre en clair, même si ce n’est vraisemblablement pas très utile en pratique.
Bibliothèque du morse
Votre travail est de développer une bibliothèque morse.s
qui expose des routines (et une variable globale) pour gérer des codes morse représentés par une arborescence telle que présenté à la section précédente.
L’ordre de description des fonctionnalités est pensé pour vous en faciliter le développement.
Symbole miniMorse
miniMorse
est une étiquette associé au code morse ESTO présenté ci-dessus.
Cette étiquette correspond à l’adresse du nœud 1 (le nœud racine) ESTO et tous les 7 nœuds sont pré-alloués par la bibliothèque dans la section data.
la s1, miniMorse # noeud 1 (racine)
lbu a0, 0(s1) # doit être '\0'
ld s2, 8(s1) # noeud 2
lbu a0, 0(s2) # doit être 'E'
ld a0, 16(s2) # doit être 0 (null)
miniMorse
permet d’avoir un code morse simple et fonctionnel pour tester les routines de la bibliothèque.
Il est également suffisant pour décoder "SOS"
et "TEST"
, ce qui est clairement très utile.
Important : Assurez-vous d’avoir une versions récente du fork de RARS. Pensez aussi aux alignements.
Routine decMorse
decMorse
permet de décoder une séquence morse.
a0
: l’adresse d’un code morse. par exempleminiMorse
.a1
: l’adresse d’une chaîne de caractère composée de.
et de-
. par exemple"..."
Note : poura1
, le caractère'\0'
termine la chaîne, ainsi que tout caractère différent de'-'
et de'.'
.- résultat
a0
: le code ASCII du caractère en clair ; par exemple'S'
. si la chaîne de caractère correspond à rien, alors le caractère'?'
est retourné (attention à ne pas retourner'\0'
).
la s0, miniMorse
mv a0, s0
la a1, s
call decMorse
li a7, PrintChar
ecall # Affiche 'S'
.data
s: .string "..."
Routine printMorse
printMorse
affiche l’ensemble des caractères en clair disponibles dans un code morse.
Les caractères sont affichés dans l’ordre de leur codage morse (avec .
avant -
) : on parcours les nœuds de l’arborescence en profondeur, en commençant via mPoint
et ensuite via mTiret
.
Note: c’est le parcours d’arborescence le plus simple à coder.
a0
: l’adresse d’un code morse. par exempleminiMorse
.
Note : printMorse
affiche les caractères en clair tels quels, sans ajouter de séparateur ou de saut de ligne. Attention à ne pas afficher de '\0'
.
la a0, miniMorse
call printMorse # affiche "ESTO"
Routine newMorse
newMorse
alloue dans le tas un nouveau nœud associé à aucun caractère en clair (donc '\0'
pour mCar
) et sans suivant pour point et pour tiret (donc 0 pour mPoint
et mTiret
).
- retour
a0
: l’adresse d’un nœud morse vide alloué dans le tas
Note : utilisez l’appel système RARS Sbrk
pour l’allocation dans le tas.
newMorse
peut être utilisé par le client pour fabriquer une nouvelle racine d’un code morse.
Cette routine peut être aussi utilisée par la bibliothèque pour créer des nouveaux nœuds dans une arborescences existante.
call newMorse
mv s0, a0 # Noeud morse vide
mv a0, s0
la a1, s
call decMorse # trouve rien, car le noeud est vide
li a7, PrintChar
ecall # Donc affiche '?'
mv a0, s0
call printMorse # affiche rien, car le noeud est vide
.data
s: .string "..."
Routine addMorse
addMorse
ajoute un nouveau caractère en clair à un code morse existant.
a0
: l’adresse d’un code morse.a1
: l’adresse d’une chaîne de caractère composée de.
et de-
.a2
: le caractère en clair à associer à cette chaîne.
Pour ce faire, addMorse
parcours l’arborescence et ajoute de nouveaux nœuds sur son parcours si c’est nécessaire (vous pouvez réutilisez newMorse
).
Les anciens nœuds intermédiaires gardent leurs caractères en clairs.
Les nouveaux nœuds intermédiaires sont associé à '\0'
.
Le nœud final est associé au caractère a2
fourni par le client.
Si le nœud final avait déjà un caractère, celui-ci est remplacé (écrasé).
Si a2
vaut '\0'
, cela correspond en pratique à invalider un caractère existant.
Note: c’est la routine difficile du TP (sauf partie ultra), allez-y doucement.
call newMorse
mv s0, a0 # nouveau noeud vide
mv a0, s0
la a1, s
li a2, 'S'
call addMorse # ajoute S
mv a0, s0
la a1, s
call decMorse # trouve S
li a7, PrintChar
ecall # affiche S
.data
s: .string "..."
Ultra : Routine printMorseLong
Important : Cette partie est avancée et ne vaut que 2 points. Ne la faire que si tout le reste fonctionne et est d’excellente qualité et si vous recherchez un défi supplémentaire.
printMorseLong
fonctionne comme printMorse
mais pour chaque caractère en clair la routine affiche : ce caractère, un espace, le code morse associé (composé de .
et de -
) et en fin un saut de ligne.
Contrainte: printMorseLong
doit fonctionner pour des code morses arbitrairement grands (dont évitez de pré-allouer des tampons de tailles fixes).
Note: il est possible de s’en sortir sans rien allouer de plus dans le tas, ni dans la section data, ni en modifiant la structure d’un nœud morse.
la a0, miniMorse
call printMorseLong
doit afficher
E .
S ...
T -
O ---
Réalisation
Développez la bibliothèque morse.s
qui doit exporter (avec la directive .global
) les étiquettes demandés: miniMorse
, decMorse
, printMorse
, newMorse
, addMorse
et éventuellement printMorseLong
.
La réalisation de cette bibliothèque se fera par groupes d’au plus deux personnes. Chaque membre de l’équipe devra maîtriser tous les aspects du code.
Contraintes d’implémentation :
- Votre code doit fonctionner avec le fork de RARS de Jean Privat en mode 64 bits (voir site du cours).
- Vous pouvez utiliser les appels systèmes RARS ou les fonctions équivalentes de
libs.s
pour les entrées-sorties. - Vous devez organiser votre programme en utilisant des routines.
Pour information, ma solution (sans trop de documentation) prend moins de 300 lignes (partie ultime comprise avec un peu de code de débogage restant).
Évaluation
Aptitude fonctionnelle
-
49% : 10 tests publics (4.9 points par test).
Les tests sont des programmes indépendants qui utilisent la bibliothèque et s’attendent au bon comportement. -
49% : plusieurs tests privés évalués par le correcteur après la remise.
Il est donc de votre responsabilité de vous assurer que votre programme fonctionne correctement au-delà des tests publics fournis. -
2% : partie ultra.
Pour vous aider, le script de correction qui sera utilisé est disponible à https://gitlab.info.uqam.ca/inf2171/20241/tp3-corrige. Tous les tests publics sont également disponibles à https://gitlab.info.uqam.ca/inf2171/20241/tp3-corrige/-/tree/master/tests?ref_type=heads.
Important : si le code remis ne s’assemble pas (erreur de syntaxe, fichier corrompu, etc.) ou si aucun test ne passe avec l’outil (échec systématique), la note zéro sera automatiquement attribuée au TP, et ce, indépendamment de la qualité du code, du temps de développement passé ou des affichages de RARS sur l’ordinateur de l’étudiant.
Qualité et lisibilité du code source
Des points bonus et malus seront attribués en fonction de la qualité du code.
- Indentation et aération.
- Nommage adéquat des symboles.
- Présence et pertinence des commentaires.
- Organisation du code, simplicité, modularité.
Les critères sont plus détaillés dans le guide de style.
Modalités de remise et dates
- Date de remise : dimanche 21 avril à 23h55.
- La remise se fait via moodle.
- Remettez un seul fichier appelé
morse.s
(pas d’archive, juste ce fichier) - Mettez les noms, prénoms et codes permanents des étudiants du groupe en commentaire au début du fichier.
- Dans un groupe de deux étudiants, un seul étudiant doit remettre.
- Seule la remise la plus récente est considérée. Vous pouvez remettre autant de fois que vous le voulez avant l’échéance.
- Remettez un seul fichier appelé
- Si vous ne voulez pas perdre de points, assurez-vous de respecter le guide de style