Aller au contenu

TP05 - La tour de Hanoï en assembleur – avec solutions

Ce TP a pour objectif la conception et la réalisation, en langage assembleur, du jeu de la tour de Hanoï sur l’écran LCD.

Hanoi

Objectifs du TP

Ce TP a pour but de vous familiariser avec le langage assembleur ARM.

À la fin de ce TP, les étudiants :

  • réutiliseront le codeur rotatif dans un autre contexte;
  • réutiliseront l’écran LCD;
  • sauront réaliser un module en assembleur et l’interfacer avec du code C/C++;
  • sauront remplacer un module en C par un en assembleur;
  • auront mis en œuvre le concept de programmation orientée objet;
  • réutiliseront les concepts appris dans les TPs précédents;
  • réutiliseront du code précédent pour faire des applications plus complexes;
  • auront réalisé un nouveau mini-projet sur la cible;
  • auront appliqué les bonnes pratiques en utilisant des assertions, en écrivant des tests unitaires et en validant systématiquement leur code avec le CI/CD;
  • sauront configurer le CI/CD pour faire tourner des tests unitaires sur une cible.

Les livrables sont :

  • un projet git (tp05) dans votre groupe sur gitlab.forge.hefr.ch avec le code du TP et le code du programme de test;
  • une configuration CI/CD de gitlab comprenant des vérifications de code statique et au moins un test unitaire qui tourne sur la cible;
  • un journal de travail déposé sur gitlab.

Temps accordé : 4 périodes de 45 minutes en classe + travail personnel à la maison

Délai

Le rapport et le code doivent être rendus au plus tard 6 jours après la séance en classe. Ce rapport doit comporter tous les chapitres demandés ainsi que la version finale du code en assembleur (fonctionnel et testé).

La tour de Hanoï

La tour est constituée de plusieurs disques de grandeurs et couleurs différentes affichés à l’écran. On choisit la cheville (peg) vers laquelle on souhaite déplacer la tour avec le codeur rotatif ou le joystick. La cheville de destination est affichée sur l’écran 7-segments et sur les LEDs qui entourent le codeur rotatif - il n’y a que trois positions possibles: gauche, centre et droite. Une pression sur le bouton-poussoir du codeur rotatif active le déplacement de la tour.

Le joystick permet également de choisir la destination et permet, en plus, de choisir le nombre de disques de la tour avec les touches up/down.

La vidéo ci-dessous illustre le résultat final :

Explications de l’algorithme récursif

Supposons que nous souhaitons déplacer une tour de hauteur 3, de la cheville A vers la cheville C en passant par la cheville B :

MoveTower of height 3 from A to C by B {
   MoveTower of height 2 from A to B by C {
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
      MoveDisc 1 from A to B
      MoveTower of height 1 from C to B by A {
         MoveTower of height 0 from C to A by B {}
         MoveDisc 0 from C to B
         MoveTower of height 0 from A to B by C {}
      }
   }
   MoveDisc 2 from A to C
   MoveTower of height 2 from B to C by A {
      MoveTower of height 1 from B to A by C {
         MoveTower of height 0 from B to C by A {}
         MoveDisc 0 from B to A
         MoveTower of height 0 from C to A by B {}
      }
      MoveDisc 1 from B to C
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
   }
}

On ne sait pas déplacer une tour de hauteur 3, donc on entre dans la récursivité et on déplace tout d’abord une tour de hauteur 2 de A vers B en passant par C. On a maintenant dégagé le disque 2 et on peut le déplacer de A vers C. Pour terminer, on déplace la tour de hauteur 2 que nous avons déplacé de de la cheville B vers C en passant par A :

MoveTower of height 3 from A to C by B {
   MoveTower of height 2 from A to B by C {
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
      MoveDisc 1 from A to B
      MoveTower of height 1 from C to B by A {
         MoveTower of height 0 from C to A by B {}
         MoveDisc 0 from C to B
         MoveTower of height 0 from A to B by C {}
      }
   }
   MoveDisc 2 from A to C
   MoveTower of height 2 from B to C by A {
      MoveTower of height 1 from B to A by C {
         MoveTower of height 0 from B to C by A {}
         MoveDisc 0 from B to A
         MoveTower of height 0 from C to A by B {}
      }
      MoveDisc 1 from B to C
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
   }
}

Mais on ne sait toujours pas déplacer une tour de hauteur 2, donc on descend encore dans la récursivité et on déplace une tour de hauteur 1 de A vers C en passant par B; on déplace le disque 1 de A vers B; et on réplace la toure de hauteur 1 de C vers B en passant par A : 

MoveTower of height 3 from A to C by B {
   MoveTower of height 2 from A to B by C {
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
      MoveDisc 1 from A to B
      MoveTower of height 1 from C to B by A {
         MoveTower of height 0 from C to A by B {}
         MoveDisc 0 from C to B
         MoveTower of height 0 from A to B by C {}
      }
   }
   MoveDisc 2 from A to C
   MoveTower of height 2 from B to C by A {
      MoveTower of height 1 from B to A by C {
         MoveTower of height 0 from B to C by A {}
         MoveDisc 0 from B to A
         MoveTower of height 0 from C to A by B {}
      }
      MoveDisc 1 from B to C
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
   }
}

On ne sait pas déplacer une tour de hauteur 1, donc on descend dans la récursivité et on déplace la toure de hauteur 0 de A vers C en passant par B; on déplace le disque 0 de A vers C; et on déplace la tour de hauteur 0 de B vers C en passant par A :

MoveTower of height 3 from A to C by B {
   MoveTower of height 2 from A to B by C {
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
      MoveDisc 1 from A to B
      MoveTower of height 1 from C to B by A {
         MoveTower of height 0 from C to A by B {}
         MoveDisc 0 from C to B
         MoveTower of height 0 from A to B by C {}
      }
   }
   MoveDisc 2 from A to C
   MoveTower of height 2 from B to C by A {
      MoveTower of height 1 from B to A by C {
         MoveTower of height 0 from B to C by A {}
         MoveDisc 0 from B to A
         MoveTower of height 0 from C to A by B {}
      }
      MoveDisc 1 from B to C
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
   }
}

On sait maintenant déplacer une tour de hauteur 0 car il ne faut rien faire du tout. On remonte donc la récursivité et après avoir déplacé le disque de A vers B, on revient au point où on doit déplacer une tour de hauteur 1 de C vers B par A. Comme on ne sait pas le faire, on descend dans la récursivité et on déplace la toure de hauteur 0 de A vers A en passant par B; on déplace le disque 0 de C vers B; et on déplace la tour de hauteur 0 de A vers B en passant par C :

MoveTower of height 3 from A to C by B {
   MoveTower of height 2 from A to B by C {
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
      MoveDisc 1 from A to B
      MoveTower of height 1 from C to B by A {
         MoveTower of height 0 from C to A by B {}
         MoveDisc 0 from C to B
         MoveTower of height 0 from A to B by C {}
      }
   }
   MoveDisc 2 from A to C
   MoveTower of height 2 from B to C by A {
      MoveTower of height 1 from B to A by C {
         MoveTower of height 0 from B to C by A {}
         MoveDisc 0 from B to A
         MoveTower of height 0 from C to A by B {}
      }
      MoveDisc 1 from B to C
      MoveTower of height 1 from A to C by B {
         MoveTower of height 0 from A to B by C {}
         MoveDisc 0 from A to C
         MoveTower of height 0 from B to C by A {}
      }
   }
}

Aspects pratiques

Le code en C/C++ vous est déjà fourni dans le projet tp-05-starter. Ce code est presque fonctionnel. La seule chose que vous devez implémenter (pour vous échauffer pour la suite ;-)) est la fonction récursive tower_of_hanoi_move :

int tower_of_hanoi_move(int from, int to, int by, int height) {
    ...
}

Pour déplacer un disque, vous pouvez appeler la fonction move_disk fournie.

Tout le reste est déjà implémenté pour vous :

  • Le code pour button
  • Le code pour shift_reg
  • Le code pour seg7
  • Le code pour pwm
  • Le code pour rotary
  • Le code pour joystick
  • Le code pour poller

Dès que le code C/C++ fonctionne correctement, vous pourrez passer à l’implémentation en assembleur (youpi !!!) en remplaçant hanoi.c avec votre version en assembleur à coder dans hanoi_asm.S.

Interface C pour accéder à l’écran LCD

Interfacer du code assembleur avec du code C++ est complexe. On préfère donc choisir une interface C. La librairie “canvas” fournit les 3 méthodes nécessaires (canvas_init, canvas_text_center et canvas_rectangle) pour la réalisation de la tour de Hanoï en assembleur. C’est pourquoi nous mettons à disposition un wrapper avec la librairie canvas.

Programmation en assembleur

Écrivez le code assembleur dans le fichier hanoi_asm.S (avec un S majuscule ). Notez que le suffixe _asm est nécessaire; vous ne pouvez pas simplement faire un fichier hanoi.S car le compilateur ne peut pas avoir deux fichiers sources pour produire le même fichier objet.

Pour permettre les deux variantes (C et Assembleur) dans le même projet, nous utilisons deux environnements dans le fichier platformio.ini :

[env:disco_f412zg_c]
build_flags =
    -DVARIANT_C


[env:disco_f412zg_asm]
build_flags =
    -DVARIANT_ASM

Chaque environnement définit un symbole : VARIANT_C pour la variante C et VARIANT_ASM pour la variante assembleur. Étudiez le début des fichiers hanoi.c et hanoi.h pour voir comment ces symboles sont utilisés. Vous avez déjà une squelette du fichier hanoi_asm.S utilisant la variable VARIANT_ASM pour votre implémentation en assembleur.

Pour sélectionner un environnement donné, cliquez sur l’icône en forme de dossier dans la barre au bas de la fenêtre (1) et choisissez l’environnement souhaité (2)

Le code source de lib/color/color.h est aussi intéressant. Étudiez comment les symboles __ASSEMBLER__ et __cplusplus sont utilisés pour rendre ce fichier utilisable en C, en C++ et en assembleur

Tests unitaires et CI/CD

Écrivez un test unitaire pour valider le nombre de mouvements nécessaires pour déplacer une tour de \(n\) disques. Voici à quoi pourrait ressembler une telle procédure de test :

void test_hanoi(void)
{
    tower_of_hanoi_init(0, 3);
    int moves = tower_of_hanoi_move(0, 2, 1, 3);
    TEST_ASSERT_EQUAL(7, moves);

    // TODO : add at least 2 more tests with different arguments
}

N’hésitez pas à compléter si vous avez d’autres idées.

Important

Pour que vous puissiez utiliser du code se trouvant dans le dossier src de votre projet dans des tests unitaires (ce qui est le cas ici avec la librairie hanoi), il vous faudra :

  • rajouter test_build_src = true dans votre fichier platform.ini (dans la section [env])
  • utiliser #ifndef PIO_UNIT_TESTING et #endif afin d’exclure le code
    du dossier src qui n’est pas pertinent pour les test (p.ex. main() du fichier main.cpp). Si vous ne faites pas cela, il y aura potentiellement deux implémentations d’une même fonction (et donc une erreur).

Voir https://docs.platformio.org/en/stable/advanced/unit-testing/structure/shared-code.html pour plus de détails.

Faites en sorte que vos tests unitaires tournent sur le runners spécifiques à ce cours (les Raspberry Pi avec une connexion aux cibles).

À ne pas oublier

Gardez toujours en têtes les bonnes pratiques ainsi que les dix commandements du bon programmeur.

  • Prenez du temps pour la conception sur papier avant de coder.
  • Gérez votre temps. Vous devrez probablement faire du travail à la maison pour arriver à terminer le TP.
  • Choisissez de bons noms pour les classes, les méthodes et les variables.
  • Implémentez les bibliothèques avec un haut niveau d’abstraction pour pouvoir réutiliser les méthodes dans d’autres projets.
  • Faites des “git commit” régulièrement avec de bons commentaires.
  • Configurez le CI/CD de gitlab et testez automatiquement le plus de choses possibles.
  • Implémentez beaucoup de tests unitaires.
  • Utilisez des assertions dans votre code pour le documenter et le rendre plus robuste.

Journal de travail

Rédigez un rapport (journal de travail) selon le même modèle que pour le premier TP. Déposez votre rapport dans un dossier /docs de votre dépôt git (tp05) avec le nom report.pdf (le chemin complet vers votre rapport est donc /docs/report.pdf)