TP3 du morse

Sommaire

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 exemple miniMorse.
  • a1: l’adresse d’une chaîne de caractère composée de . et de -. par exemple "..."
    Note : pour a1, 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 exemple miniMorse.

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.
  • Si vous ne voulez pas perdre de points, assurez-vous de respecter le guide de style