Unité arithmétique et logique
GameBoj – Étape 2

Une unité arithmétique et logique ou UAL (arithmetic logic unit ou ALU en anglais) est une partie d'un processeur chargée d'effectuer des calculs sur des « entiers » de taille fixe.

Le processeur du Game Boy possède une UAL capable d'effectuer des calculs sur des « entiers » de 8 bits¹. Parmi les opérations qu'elle offre figurent :

• l'addition et la soustraction,
• les opérations bit à bit usuelles (et, ou, ou exclusif, etc.),
• le décalage et la rotation dans chacune des deux directions, mais d'une distance limitée à un seul bit,
• le test et la modification d'un bit individuel d'un « entier » de 8 bits.

En plus de ces opérations sur des « entiers » de 8 bits, elle offre également l'addition sur les « entiers » de 16 bits.

Il faut noter que cette UAL ne permet pas d'effectuer des multiplications ou des divisions ! Cela implique que le processeur du Game Boy n'offre pas non plus d'instruction de multiplication ou de division, ce qui ne facilite pas la vie des programmeurs.

En plus de produire un « entier » de taille fixe comme résultat, les différentes opérations de l'UAL produisent également un certain nombre de valeurs booléennes, nommées fanions ou parfois drapeaux (flags), qui donnent des informations sur le résultat. Ces fanions permettent de facilement déterminer si le résultat d'une opération a une caractéristique donnée — p.ex. s'il est nul —, simplement en consultant le fanion correspondant.

Les fanions sont généralement nommés au moyen d'une seule lettre et, dans le cas de l'UAL du Game Boy, sont au nombre de quatre : Z, N, H et C. Leur signification est la suivante :

• Z (zero) est vrai ssi le résultat de l'opération vaut zéro,
• N est vrai ssi l'opération effectuée était une soustraction,
• H (half carry) est vrai ssi une retenue (resp. un emprunt) a été produite par l'addition (resp. la soustraction) des 4 bits de poids faible,
• C (carry) est vrai ssi une retenue (resp. un emprunt) a été produite par l'addition (resp. la soustraction) de la totalité des 8 bits.

Les notions de retenue et d'emprunt sont décrites plus en détail à la section suivante. Le fonctionnement des fanions peut néanmoins être illustré au moyen de l'exemple suivant : admettons que l'on demande à l'UAL du Game Boy de calculer la somme des deux « entiers » de 8 bits valant 91₁₆ et 83₁₆. Elle produit :

• un résultat de 8 bits valant 14₁₆ (qui est différent du résultat mathématique, 114₁₆, car celui-ci n'est pas représentable avec 8 bits),
• un fanion Z faux, car le résultat n'est pas égal à 0,
• un fanion N faux, car l'opération n'était pas une soustraction,
• un fanion H faux, car l'addition des 4 bits de poids faible (1₁₆ et 3₁₆) n'a pas produit de retenue — en d'autres termes, son résultat (4₁₆) est représentable avec 4 bits uniquement,
• un fanion C vrai, car l'addition des 8 bits a produit une retenue — en d'autres termes, son résultat (114₁₆) n'est pas représentable avec 8 bits et a été tronqué en 14₁₆.

Il faut noter que certains fanions n'ont pas de sens clair pour chacune des opérations de l'UAL. Par exemple, la notion de retenue/emprunt n'a de sens que pour l'addition et la soustraction, et dès lors la signification des fanions H et C n'est claire que pour ces deux opérations. La valeur d'un fanion à la suite d'une opération pour lequel il n'a pas de sens évident a donc été choisie plus ou moins arbitrairement par les concepteurs du processeur du Game Boy, et ne répond généralement à aucune logique.

La signification des deux fanions de retenue (H et C) n'est pas la même pour les additions que pour les soustractions. Quelques explications à leur sujet s'imposent donc.

Dans la section précédente, nous avons affirmé que dans le cas d'une addition, le premier bit de la retenue — c[0] — valait toujours 0. De même, dans le cas d'une soustraction, le premier bit de l'emprunt — b[0] — valait toujours 0.

Dans certaines situations, il est pourtant intéressant de pouvoir spécifier, lors d'une addition, la valeur de c[0] et, lors d'une soustraction, la valeur de b[0].

Par exemple, admettons que l'on désire effecuter une soustraction de deux valeurs 16 bits alors qu'on ne dispose que d'une UAL capable d'additioner des valeurs 8 bits. Intuitivement, cela peut se faire en enchaînant deux additions de 8 bits : la première pour les 8 bits de poids faible, la seconde pour les 8 bits de poids fort. Toutefois, il faut bien prendre garde à une chose : si la première addition produit une retenue, celle-ci doit être utilisée comme retenue initiale de la seconde addition ! En d'autres termes, la valeur de c[8] de la première addition doit être utilisée comme valeur de c[0] de la seconde addition.

Pour cette raison, l'UAL du Game Boy offre la possibilité de spécifier la valeur de c[0] (resp. b[0]) lors d'une addition (resp. une soustraction). On appelle ces variantes de l'addition et de la soustraction : addition avec retenue (add with carry) et soustraction avec emprunt (subtract with borrow).

L'UAL du Game Boy peut également effectuer des additions de valeurs 16 bits, ce qu'elle fait en chaînant deux additions de 8 bits comme décrit ci-dessus.

Lorsqu'une telle addition est effectuée, la question se pose de savoir ce que valent les fanions de retenue, H et C. En gros, deux possibilités sensées existent :

1. ces fanions sont ceux de la première addition de 8 bits, celle qui somme les 8 bits de poids faible de chacune des deux valeurs,
2. ces fanions sont ceux de la seconde addition de 8 bits, celle qui somme les 8 bits de poids fort de chacune des deux valeurs et l'éventuelle retenue produite par la première addition.

Visiblement, les concepteurs du processeur du Game Boy n'ont pas réussi à se décider pour l'une de ces deux possibilités, et on retrouve donc les deux dans différentes situations. Pour cette raison, notre UAL simulée offre deux variantes de l'addition 16 bits, qui produisent la même valeur 16 bits mais des fanions H et C calculés différemment.

Comme d'autres UAL, celle du Game Boy offre une opération dite de rotation à travers la retenue (rotate through carry).

Conceptuellement, cette opération consiste à obtenir une valeur de 9 bits en combinant les 8 bits de la valeur et le bit de retenue, qui devient le bit de poids le plus fort de la valeur combinée. Cette valeur de 9 bits subit une rotation, et les 9 bits du résultat sont à nouveau séparés en le bit de poids le plus fort, qui devient le fanion de retenue du résultat, et les 8 bits de poids faible, qui constituent la valeur du résultat.

Par exemple, admettons que l'on désire effectuer une rotation d'un bit vers la gauche de la valeur 8 bits stuvwxyz (chaque lettre représente un bit) et du fanion C. On procède comme décrit plus haut en :

1. formant la valeur 9 bits combinée, Cstuvwxyz,
2. tournant cette valeur d'un bit vers la gauche, ce qui donne stuvwxyzC,
3. séparant cette valeur en son bit de poids le plus fort, s, qui devient la retenue du résultat, et ses 8 bits de poids faible, tuvwxyzC, qui deviennent la valeur du résultat.

Les ordinateurs représentent en interne les nombres en base 2, tandis que les humains ont l'habitude de travailler en base 10.

Cette différence de base pose parfois problème, par exemple lorsqu'on désire afficher, en base 10, un nombre stocké dans l'ordinateur. En effet, cet affichage implique de déterminer la représentation en base 10 d'un nombre dont on ne connaît que la représentation en base 2.

La solution la plus naturelle pour passer d'une représentation à l'autre consiste à calculer le reste de la division du nombre par 10, ce qui donne le chiffre de poids faible. Le chiffre suivant (depuis la droite) peut ensuite être obtenu en appliquant la même technique au nombre divisé entièrement par 10, et ainsi de suite.

Cette solution fonctionne, mais sa mise en œuvre est problématique (et coûteuse) sur un système comme le Game Boy dont l'UAL n'offre pas d'opération de division.

Pour cette raison, et d'autres, certains nombres sont parfois stockés dans une représentation particulière nommée le décimal codé binaire, abrégé DCB (binary coded decimal, BCD). L'idée est de représenter chaque chiffre décimal par un groupe de 4 bits, selon la correspondance (évidente) suivante :

Par exemple, 73 est représenté en DCB par un groupe de huit bits, les quatre de poids fort valant 0111 (7), les quatre de poids faible valant 0011 (3), soit 01110011. Notez que cette représentation n'a rien à voir avec la représentation de 73 en binaire, qui vaut 01001001.

Bien entendu, le décimal codé binaire gaspille beaucoup de place, car il n'utilise que 10 des 16 valeurs représentables au moyen d'un groupe de 4 bits. Ainsi, en DCB, un groupe de 8 bits ne permet que de représenter les entiers allant de 0 à 99, alors qu'en binaire, ces mêmes 8 bits permettent de représenter les entiers allant de 0 à 255. L'intérêt du DCB est que la conversion en base 10 est triviale car il y a une correspondance directe entre un groupe de 4 bits et un chiffre décimal.

Pour faciliter la manipulation de nombres décimaux codés binaire, l'UAL du Game Boy permet d'ajuster le résultat d'une opération arithmétique (addition ou soustraction) effectuée sur deux nombres DCB afin que le résultat soit lui aussi au format DCB.

Par exemple, admettons que l'on désire calculer la somme de 35 et de 38, représentés en DCB, et obtenir un résultat qui soit lui aussi en DCB. En DCB, 35 est représenté par les 8 bits valant 0011 0101, tandis que 38 l'est par les 8 bits valant 0011 1000. En calculant « bêtement » la somme de ces deux valeurs 8 bits, on obtient 0110 1101. Ces 8 bits ne constituent pas une valeur DCB valide, car les 4 bits de poids faible valent 1101, ce qui ne correspond pas à un chiffre décimal. Dans ce cas particulier, il suffit d'ajouter 6 au résultat pour obtenir 0111 0011, qui est bien la représentation DCB de 73, la somme de 35 et de 38.

De manière générale, lorsqu'on effectue une addition ou une soustraction « normale » (c-à-d sans savoir qu'on manipule des valeurs DCB) sur deux valeurs DCB, le résultat obtenu n'est pas forcément une valeur DCB valide. Pour la rendre valide, il faut soit ajouter (dans le cas d'une addition), soit soustraire (dans le cas d'une soustraction) 6 à l'un ou l'autre, ou les deux, groupes de 4 bits. Ainsi, dans l'exemple ci-dessus, il a été nécessaire d'ajouter 6 au groupe de bits de poids faible².

La manière dont on détermine le sous-ensemble des deux groupes de 4 bits nécessitant une correction n'est pas totalement triviale. Dès lors, nous vous la décrivons sous la forme de l'algorithme d'ajustement ci-dessous, donné en pseudo-code. Cet algorithme prend quatre paramètres : la valeur 8 bits V à ajuster et les fanions N, H et C décrits plus haut. Cinq valeurs sont produites en résultat par la dernière ligne, sous la forme d'un quintuplet dont les composantes sont données entre parenthèses et sont, dans l'ordre : la valeur ajustée (Va) et les 4 fanions Z, N, H et C.

fixL := H ∨ (¬N ∧ V[3:0] > 9)
fixH := C ∨ (¬N ∧ V > 99₁₆)
fix := 60₁₆ × fixH + 06₁₆ × fixL
Va := V - fix si N, V + fix sinon
(Va, Va = 0, N, faux, fixH)

On fait ci-dessus l'hypothèse que les fanions sont utilisables comme des entiers valant 0 si faux, 1 si vrai. D'autre part, les symboles usuels sont utilisés pour la conjonction (∨), disjonction (∧) et négation (¬) logiques. Finalement, V[3:0] dénote l'entier représenté par les 4 bits de poids faible de V.

Pour illustrer le fonctionnement de cet algorithme on peut l'appliquer à l'exemple donné plus haut, l'addition des valeurs DCB 0011 0101 (35₁₆) et 0011 1000 (38₁₆). Dans ce cas, V vaut 0110 1101 (6D₁₆), le fanion N est faux car l'opération effectuée était une addition et pas une soustraction, le fanion H est faux car l'addition des 4 bits de poids faible (0101 et 1000) n'a pas produit de retenue, et le fanion C est faux car l'addition des deux valeurs 8 bits n'a pas produit de retenue non plus.

Les paramètres de l'algorithme étant connus, on peut l'exécuter et on obtient alors :

fixL := faux ∨ (¬faux ∧ D₁₆ > 9₁₆) = vrai
fixH := faux ∨ (¬faux ∧ 6D₁₆ > 99₁₆) = faux
fix := 60₁₆ × 0 + 06₁₆ × 1 = 06₁₆
Va := 6D₁₆ + 06₁₆ = 73₁₆
(73₁₆, faux, faux, faux, faux)

En d'autres termes, la valeur ajustée vaut 73₁₆ (comme attendu) et les fanions Z, N, H et C sont tous faux.

Comme cela a été expliqué plus haut, les opérations de l'UAL produisent non seulement un « entier » 8 (ou 16) bits, mais aussi quatre fanions, soit cinq valeurs au total.

Malheureusement, une méthode Java ne peut retourner qu'une seule valeur en résultat. La solution généralement adoptée lorsqu'on désire écrire une méthode retournant plus d'une valeur consiste à définir une classe dont les instances peuvent contenir ces valeurs, et à retourner ensuite une instance de cette classe.

Cette solution serait bien entendu utilisable ici, mais le coût de la création d'un nouvel objet à chaque appel d'une méthode de l'UAL serait prohibitif étant donné la simplicité des opérations effectuées par ces méthodes (additions, etc.).

Dans ce cas particulier, il existe toutefois une solution plus simple et nettement moins coûteuse : l'empaquetage des valeurs dans un seul « entier » Java de type int. Etant donné que les méthodes de l'UAL retournent une valeur de 8 (ou 16) bits plus 4 fanions de 1 bit chacun, seul 12 (ou 20) bits sont nécessaires pour représenter ces 5 valeurs, et il est donc tout à fait possible de les empaqueter dans un « entier » Java de type int.

Les différentes méthodes de l'UAL retournent donc un entier int dont les 32 bits ont le contenu suivant :

Par exemple, lorsqu'on demande à l'UAL de calculer la somme des deux entiers 91₁₆ et 83₁₆ déjà utilisés à la §2.2, elle retourne un « entier » int valant 00001410₁₆. Cet entier contient, dans ses différents bits et selon la convention décrite plus haut, à la fois le résultat (14₁₆) et les fanions (0001₂).

Il peut paraître étrange de stocker les fanions dans les bits 4 à 7 et de laisser les bits 3 à 0 inutilisés. Ce choix a été fait simplement car, comme nous le verrons à l'étape suivante, le processeur stocke les fanions sous la forme d'une valeur de 8 bits qui correspond directement aux 8 bits de poids faible d'une valeur encodée comme décrit ci-dessus.

L'UAL du Game Boy effectue les opérations d'addition et de soustraction comme décrit plus haut, en procédant bit à bit, de droite à gauche. Ce faisant, elle détermine individuellement chacun des bits de retenue (dans le cas d'une addition) et d'emprunt (dans le cas d'une soustraction) et n'a donc aucune peine à connaître la valeur des fanions H et C.

Pour simuler cette UAL en Java, il serait bien entendu possible d'effectuer également les additions et soustractions bit à bit, mais cela serait à la fois pénible à écrire et lent à exécuter. Il est beaucoup plus simple et efficace d'utiliser les opérations d'addition et de soustraction offertes par Java. La question se pose néanmoins de savoir comment déterminer la valeur des fanions H et C.

Dans le cas d'une addition, la réponse est simple : une addition sur n bits produit une retenue si et seulement si le résultat est plus grand que la plus grande valeur représentable au moyen de n bits. Dès lors, en Java, on peut déterminer la valeur du fanion C suite à l'addition de deux valeurs 8 bits stockés dans les variables x et y ainsi :

boolean c = (x + y) > 0xFF;

Notez qu'il est fondamental que l'addition soit faite sur des entiers comportant au moins n + 1 bits pour que le fanion C soit calculé correctement ! C'est une des raisons pour lesquelles nous avons décidé de représenter les valeurs 8 et 16 bits au moyen du type Java int (32 bits) dans ce projet.

Dans le cas d'une soustraction, la réponse n'est pas beaucoup plus compliquée : une soustraction sur n bits produit un emprunt si et seulement si la seconde opérande de la soustraction est strictement plus grande que la première. Dès lors, en Java, on peut déterminer la valeur du fanion C suite à la soustraction de deux valeurs 8 bits stockées dans les variables x et y ainsi :

boolean c = x < y;

La classe Alu du paquetage ch.epfl.gameboj.component.cpu, publique, finale et non instanciable, contient principalement des méthodes statiques permettant d'effectuer des opérations sur des valeurs 8 ou 16 bits et d'obtenir à la fois le résultat et la valeur des fanions.

En plus de la classe Alu, une seconde classe nommée GameBoy est à commencer pour cette étape. Comme son nom l'indique, cette classe modélise un Game Boy et a pour but d'instancier les différents composants de la console et de les attacher à un bus commun.

Cette classe sera augmentée au cours des étapes, mais pour l'instant elle contient déjà :

• un bus, auquel tous les composants sont connectés,
• une mémoire vive, appelée la mémoire de travail (work RAM) d'une taille de 8192 octets et accessible depuis l'adresse C000₁₆,
• une copie des 7680 premiers octets de cette mémoire de travail, accessible depuis l'adresse E000₁₆.

Ce que l'on entend par « copie » est que les mêmes données sont accessibles au moyen de deux adresses différentes. Ainsi, aussi bien l'adresse C000₁₆ que l'adresse E000₁₆ désignent le premier octet de la mémoire de travail, et une valeur écrite à l'une ou l'autre de ces adresses peut être relue par la suite à travers l'autre adresse.

La mémoire de travail et sa copie sont mentionnées dans la carte des adresses du Game Boy, présentée à l'étape précédente. Pour faciliter votre travail, nous mettons à votre disposition une archive Zip à importer dans votre projet et contenant une interface nommée AddressMap décrivant cette carte des adresses. Les constantes utiles pour cette étape sont :

• WORK_RAM_START, WORK_RAM_END et WORK_RAM_SIZE qui caractérisent la mémoire de travail,
• ECHO_RAM_START, ECHO_RAM_END et ECHO_RAM_SIZE qui caractérisent sa copie partielle (généralement désignée par echo en anglais).

Il faut noter que dans la documentation officielle du Game Boy, la zone echo est décrite comme inutilisable. En pratique, elle se comporte comme décrit ci-dessus, et comme certains programmes font usage de ce comportement non documenté, nous devons le simuler.

La version initiale de la classe GameBoy est très simple et ne comporte qu'un constructeur et une méthode d'accès. Le constructeur a le profil suivant :

• GameBoy(Object cartridge), qui construit un Game Boy en créant les composants nécessaires (actuellement, seule la mémoire de travail et sa copie) et en les attachant à un bus commun ; l'argument cartridge est à ignorer totalement dans la version actuelle, mais sera utilisé plus tard pour représenter la cartouche attachée au Game Boy ; son type sera alors changé.

L'unique méthode publique de la version actuelle de la classe GameBoy est un accesseur :

• Bus bus(), qui retourne le bus du Game Boy.

A ce bus doivent être attachés les deux contrôleurs pour la mémoire de travail, qui y donnent accès via les deux plages d'adresses susmentionnées.

À partir de cette étape, nous ne vous fournissons plus de tests unitaires. Il vous faut donc les écrire vous-même si vous désirez en avoir, ce qui est fortement conseillé.

Si nous ne vous fournissons pas de tests JUnit, nous vous fournissons néanmoins une archive Zip à importer dans votre projet et contenant un fichier nommé SignatureChecks_2.java. La classe qu'il contient fait référence à la totalité des classes, interfaces et méthodes de cette étape, ce qui vous permet de vérifier que leurs noms et types sont corrects. Cela est capital, car la moindre faute à ce niveau empêcherait l'exécution de nos tests unitaires.

Nous vous fournirons de tels fichiers pour toutes les étapes jusqu'à la mi-semestre, et il vous faudra penser à vérifier systématiquement qu'Eclipse ne signale aucune erreur à leur sujet. Faute de cela, votre rendu se verra refusé par notre système.