Dans ce didacticiel, je vais vous montrer comment écrire votre propre machine virtuelle (VM) qui peut exécuter des programmes d'assembleur tels que
2048 (mon ami) ou
Roguelike (le mien). Si vous savez programmer, mais que vous voulez mieux comprendre ce qui se passe à l'intérieur de l'ordinateur et comment fonctionnent les langages de programmation, alors ce projet est fait pour vous. Écrire votre propre machine virtuelle peut sembler un peu effrayant, mais je vous promets que le sujet est étonnamment simple et instructif.
Le code final est d'environ 250 lignes en C. Il suffit de connaître uniquement les bases du C ou du C ++, comme l'
arithmétique binaire . Tout système Unix (y compris macOS) convient à la construction et à l'exécution. Plusieurs API Unix sont utilisées pour configurer l'entrée et l'affichage de la console, mais elles ne sont pas essentielles au code principal. (La mise en œuvre du support Windows est appréciée).
Remarque: cette VM est un programme compétent . Autrement dit, vous lisez déjà son code source en ce moment! Chaque morceau de code sera affiché et expliqué en détail, de sorte que vous pouvez être sûr que rien ne manque. Le code final est créé par un plexus de blocs de code. Dépôt de projets ici .
1. Contenu
- Table des matières
- Présentation
- Architecture LC-3
- Exemples d'assembleurs
- Exécution du programme
- Mise en œuvre des instructions
- Instructions Triche
- Procédures de traitement des interruptions
- Aide-mémoire pour les routines d'interruption
- Téléchargez le logiciel
- Registres mappés en mémoire
- Fonctionnalités de la plateforme
- Démarrage de la machine virtuelle
- Méthode alternative en C ++
2. Introduction
Qu'est-ce qu'une machine virtuelle?
Une machine virtuelle est un programme qui agit comme un ordinateur. Il simule un processeur avec plusieurs autres composants matériels, vous permettant d'effectuer des opérations arithmétiques, de lire et d'écrire dans la mémoire et d'interagir avec des périphériques d'entrée / sortie comme un véritable ordinateur physique. Plus important encore, VM comprend un langage machine que vous pouvez utiliser pour la programmation.
La quantité de matériel simulée par une machine virtuelle particulière dépend de son objectif. Certaines machines virtuelles reproduisent le comportement d'un ordinateur particulier. Les gens n'ont plus NES, mais nous pouvons toujours jouer à des jeux pour NES en simulant du matériel au niveau logiciel. Ces émulateurs doivent
recréer avec précision chaque
détail et chaque composant matériel majeur de l'appareil d'origine.
Les autres VM ne correspondent à aucun ordinateur particulier, mais correspondent partiellement à plusieurs à la fois! Cela est principalement fait pour faciliter le développement de logiciels. Imaginez que vous souhaitez créer un programme qui s'exécute sur plusieurs architectures informatiques. La machine virtuelle fournit une plate-forme standard qui assure la portabilité. Pas besoin de réécrire le programme dans différents dialectes d'assembleur pour chaque architecture. Il suffit de ne faire qu'une petite VM dans chaque langue. Après cela, tout programme ne peut être écrit qu'une seule fois dans le langage d'assemblage d'une machine virtuelle.
Remarque: le compilateur résout ces problèmes en compilant un langage standard de haut niveau pour différentes architectures de processeur. VM crée une architecture CPU standard qui est simulée sur divers périphériques matériels. L'un des avantages du compilateur est qu'il n'y a pas de surcharge d'exécution comme le fait VM. Bien que les compilateurs fonctionnent bien, l'écriture d'un nouveau compilateur pour plusieurs plates-formes est très difficile, donc les machines virtuelles sont toujours utiles. En réalité, à différents niveaux, VM et compilateurs sont utilisés ensemble.
La machine virtuelle Java (JVM) est un exemple très réussi. La JVM elle-même est de taille relativement moyenne; elle est suffisamment petite pour qu'un programmeur puisse la comprendre. Cela vous permet d'écrire du code pour des milliers d'appareils différents, y compris les téléphones. Après avoir implémenté la JVM sur le nouveau périphérique, n'importe quel programme Java, Kotlin ou Clojure écrit peut fonctionner sans modifications. Les seuls coûts ne seront que les frais généraux de la machine virtuelle elle-même et
l'abstraction du niveau machine. C'est généralement un très bon compromis.
Une machine virtuelle n'a pas besoin d'être volumineuse ou omniprésente pour offrir des avantages similaires. Les
jeux vidéo plus anciens utilisaient souvent de petites machines virtuelles pour créer des
systèmes de script simples.
Les machines virtuelles sont également utiles pour isoler des programmes en toute sécurité. Une application est la collecte des ordures.
Il n'y a aucun moyen trivial d' implémenter le ramasse-miettes automatique au-dessus de C ou C ++, car le programme ne peut pas voir sa propre pile ou ses variables. Cependant, la machine virtuelle est «en dehors» du programme en cours d'exécution et peut observer toutes les
références aux cellules de mémoire sur la pile.
Un autre exemple de ce comportement est illustré par
les contrats intelligents Ethereum . Les contrats intelligents sont de petits programmes exécutés par chaque nœud de validation de la chaîne de blocs. Autrement dit, les opérateurs autorisent l'exécution sur leurs machines de tout programme écrit par des inconnus, sans aucune possibilité de les étudier à l'avance. Pour éviter les actions malveillantes, elles sont effectuées sur une
machine virtuelle qui n'a pas accès au système de fichiers, au réseau, au disque, etc. Ethereum est également un bon exemple de portabilité. Grâce à VM, vous pouvez écrire des contrats intelligents sans prendre en compte les fonctionnalités de nombreuses plateformes.
3. Architecture LC-3
Notre machine virtuelle simulera un ordinateur fictif appelé
LC-3 . Il est populaire pour enseigner aux étudiants monteurs. Ici, un ensemble de commandes simplifié
par rapport à x86 , mais conserve tous les concepts de base utilisés dans les processeurs modernes.
Tout d'abord, vous devez simuler les composants matériels nécessaires. Essayez de comprendre ce qu'est chaque composant, mais ne vous inquiétez pas si vous ne savez pas comment il s'intègre dans la vue d'ensemble. Commençons par créer un fichier en C. Chaque morceau de code de cette section doit être placé dans la portée globale de ce fichier.
La mémoire
Le LC-3 possède 65 536 cellules de mémoire (2
16 ), chacune contenant une valeur de 16 bits. Cela signifie qu'il ne peut stocker que 128 Ko - beaucoup moins que ce à quoi vous êtes habitué! Dans notre programme, cette mémoire est stockée dans un tableau simple:
uint16_t memory[UINT16_MAX];
Registres
Un registre est un emplacement pour stocker une valeur dans le CPU. Les registres sont comme un «établi» de CPU. Pour qu'il puisse fonctionner avec certaines données, il doit se trouver dans l'un des registres. Mais comme il n'y a que quelques registres, seule une quantité minimale de données peut être téléchargée à tout moment. Les programmes contournent ce problème en chargeant des valeurs de la mémoire dans des registres, en calculant des valeurs dans d'autres registres, puis en stockant les résultats finaux dans la mémoire.
Il n'y a que 10 registres dans le LC-3, chacun avec 16 bits. La plupart d'entre eux sont à usage général, mais certains ont des rôles assignés.
- 8 registres à usage général (
R0-R7 ) - 1 registre du comptoir des équipes (
PC ) - 1 registre des indicateurs de condition (
COND )
Les registres à usage général peuvent être utilisés pour effectuer des calculs logiciels. Le compteur d'instructions est un entier non signé qui est l'adresse mémoire de la prochaine instruction à exécuter. Les drapeaux de condition nous renseignent sur le calcul précédent.
enum { R_R0 = 0, R_R1, R_R2, R_R3, R_R4, R_R5, R_R6, R_R7, R_PC, R_COND, R_COUNT };
Comme la mémoire, nous allons stocker les registres dans un tableau:
uint16_t reg[R_COUNT];
Jeu d'instructions
Une instruction est une commande qui indique au processeur d'effectuer une sorte de tâche fondamentale, par exemple, ajouter deux nombres. L'instruction a un
opcode (code d'opération) indiquant le type de tâche en cours d'exécution, ainsi qu'un ensemble de
paramètres qui fournissent une entrée pour la tâche en cours d'exécution.
Chaque
opcode représente une tâche que le processeur «sait» comment effectuer. Il y a 16 opcodes dans LC-3. Un ordinateur ne peut calculer que la séquence de ces instructions simples. La longueur de chaque instruction est de 16 bits et les 4 bits de gauche stockent le code d'opération. Les autres sont utilisés pour stocker les paramètres.
Plus tard, nous discuterons en détail de ce que fait chaque instruction. Définissez les opcodes suivants pour le moment. Assurez-vous de conserver cette commande pour obtenir la valeur d'énumération correcte:
enum { OP_BR = 0, OP_ADD, OP_LD, OP_ST, OP_JSR, OP_AND, OP_LDR, OP_STR, OP_RTI, OP_NOT, OP_LDI, OP_STI, OP_JMP, OP_RES, OP_LEA, OP_TRAP };
Remarque: l' architecture Intel x86 contient des centaines d'instructions, tandis que d'autres architectures telles que ARM et LC-3 sont très peu nombreuses. Les petits jeux d'instructions sont appelés RISC , tandis que les plus grands sont appelés CISC . Les grands jeux d'instructions, en règle générale, ne fournissent pas de fonctionnalités fondamentalement nouvelles, mais simplifient souvent l'écriture du code assembleur . Une instruction CISC peut remplacer plusieurs instructions RISC. Cependant, les processeurs CISC sont plus complexes et coûteux à concevoir et à fabriquer. Ceci et d'autres compromis ne permettent pas d'appeler la conception «optimale» .
Indicateurs de condition
Le registre
R_COND stocke des indicateurs de condition qui fournissent des informations sur le dernier calcul effectué. Cela permet aux programmes de vérifier les conditions logiques, telles que
if (x > 0) { ... } .
Chaque processeur possède de nombreux drapeaux d'état pour signaler diverses situations. Le LC-3 utilise seulement trois drapeaux de condition qui montrent le signe du calcul précédent.
enum { FL_POS = 1 << 0, FL_ZRO = 1 << 1, FL_NEG = 1 << 2, };
Remarque: (Le caractère << est appelé l'opérateur de décalage vers la gauche . (n << k) décale les bits n gauche de k emplacements. Ainsi, 1 << 2 est égal à 4 Lisez ici si vous n'êtes pas familier avec le concept. Ce sera très important).
Nous avons terminé la configuration des composants matériels de notre machine virtuelle! Après avoir ajouté des inclusions standard (voir le lien ci-dessus), votre fichier devrait ressembler à ceci:
{Includes, 12} {Registers, 3} {Opcodes, 3} {Condition Flags, 3}
Voici des liens vers des sections numérotées de l'article, d'où proviennent les fragments de code correspondants. Pour une liste complète, voir le programme de travail - env. trans.4. Exemples d'assembleurs
Maintenant, regardons le programme d'assembleur LC-3 pour avoir une idée de ce que fait réellement la machine virtuelle. Vous n'avez pas besoin de savoir programmer en assembleur, ni de tout comprendre ici. Essayez juste d'avoir une idée générale de ce qui se passe. Voici un simple «Hello World»:
.ORIG x3000 ; this is the address in memory where the program will be loaded LEA R0, HELLO_STR ; load the address of the HELLO_STR string into R0 PUTs ; output the string pointed to by R0 to the console HALT ; halt the program HELLO_STR .STRINGZ "Hello World!" ; store this string here in the program .END ; mark the end of the file
Comme en C, le programme exécute une instruction de haut en bas. Mais contrairement à C, il n'y a pas de zones imbriquées
{} ou de structures de contrôle telles que
if ou
while ; juste une simple liste d'opérateurs. Par conséquent, il est beaucoup plus facile à réaliser.
Veuillez noter que les noms de certains opérateurs correspondent aux opcodes que nous avons définis précédemment. Nous savons que les instructions sont de 16 bits, mais chaque ligne ressemble à un nombre différent de caractères. Comment un tel décalage est-il possible?
En effet, le code que nous lisons est écrit en
langage assembleur - sous forme de texte brut, lisible et inscriptible. Un outil, appelé
assembleur , convertit chaque ligne de texte en une instruction binaire 16 bits qu'une machine virtuelle comprend. Cette forme binaire, qui est essentiellement un tableau d'instructions 16 bits, est appelée
code machine et est en fait exécutée par une machine virtuelle.
Remarque: bien que le compilateur et l'assembleur jouent un rôle similaire dans le développement, ils ne sont pas identiques. L'assembleur code simplement ce que le programmeur a écrit dans le texte, en remplaçant les caractères par leur représentation binaire et en les emballant dans des instructions.
Les
.STRINGZ .ORIG et
.STRINGZ ressemblent à des instructions, mais non. Ce sont des directives d'assembleur qui génèrent une partie du code ou des données. Par exemple,
.STRINGZ insère une chaîne de caractères à un emplacement spécifié dans un programme binaire.
Les boucles et les conditions sont exécutées à l'aide d'une instruction de type goto. Voici un autre exemple qui compte jusqu'à 10.
AND R0, R0, 0 ; clear R0 LOOP ; label at the top of our loop ADD R0, R0, 1 ; add 1 to R0 and store back in R0 ADD R1, R0, -10 ; subtract 10 from R0 and store back in R1 BRn LOOP ; go back to LOOP if the result was negative ... ; R0 is now 10!
Remarque: ce didacticiel n'a pas à apprendre l'assemblage. Mais si vous êtes intéressé, vous pouvez écrire et créer vos propres programmes LC-3 à l'aide des outils LC-3 .
5. Exécution du programme
Encore une fois, les exemples précédents donnent juste une idée de ce que fait la VM. Pour écrire une machine virtuelle, vous n'avez pas besoin d'une compréhension complète de l'assembleur. Tant que vous suivez la procédure appropriée pour lire et exécuter les instructions,
tout programme LC-3 fonctionnera correctement, quelle que soit sa complexité. En théorie, une VM peut même exécuter un navigateur ou un système d'exploitation comme Linux!
Si vous pensez profondément, alors c'est une idée philosophiquement merveilleuse. Les programmes eux-mêmes peuvent produire des actions arbitrairement complexes auxquelles nous ne nous attendions pas et que nous ne pouvons pas comprendre. Mais en même temps, toutes leurs fonctionnalités sont limitées à du code simple, que nous écrirons! En même temps, nous savons tout et rien sur le fonctionnement de chaque programme. Turing a mentionné cette merveilleuse idée:
«L'opinion selon laquelle les machines ne peuvent surprendre personne avec quoi que ce soit est basée, je crois, sur une erreur, à laquelle les mathématiciens et les philosophes sont particulièrement enclins. Je veux dire l'hypothèse que depuis qu'un fait est devenu la propriété de l'esprit, immédiatement toutes les conséquences de ce fait deviendront la propriété de l'esprit. » - Alan M. Turing
Procédure
Voici la description exacte de la procédure à écrire:
- Téléchargez une instruction de la mémoire à l'adresse du registre
PC . - Augmentez
PC registre PC . - Affichez l'opcode pour déterminer le type d'instruction à suivre.
- Suivez les instructions en utilisant ses paramètres.
- Revenez à l'étape 1.
Vous pouvez poser la question: "Mais si la boucle continue à incrémenter le compteur en l'absence de
if ou
while , les instructions ne se termineront-elles pas?" La réponse est non. Comme nous l'avons déjà mentionné, certaines instructions de type goto modifient le flux d'exécution en sautant autour du
PC .
Nous commençons l'étude de ce processus comme exemple du cycle principal:
int main(int argc, const char* argv[]) { {Load Arguments, 12} {Setup, 12} enum { PC_START = 0x3000 }; reg[R_PC] = PC_START; int running = 1; while (running) { uint16_t instr = mem_read(reg[R_PC]++); uint16_t op = instr >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; case OP_JMP: {JMP, 7} break; case OP_JSR: {JSR, 7} break; case OP_LD: {LD, 7} break; case OP_LDI: {LDI, 6} break; case OP_LDR: {LDR, 7} break; case OP_LEA: {LEA, 7} break; case OP_ST: {ST, 7} break; case OP_STI: {STI, 7} break; case OP_STR: {STR, 7} break; case OP_TRAP: {TRAP, 8} break; case OP_RES: case OP_RTI: default: {BAD OPCODE, 7} break; } } {Shutdown, 12} }
6. Mise en œuvre des instructions
Maintenant, votre tâche est de faire l'implémentation correcte pour chaque opcode. Une spécification détaillée de chaque instruction est contenue dans la
documentation du
projet . À partir de la spécification, vous devez savoir comment fonctionne chaque instruction et écrire une implémentation. C'est plus facile qu'il n'y paraît. Ici, je vais montrer comment mettre en œuvre deux d'entre eux. Le code pour le reste peut être trouvé dans la section suivante.
AJOUTER
L'instruction
ADD prend deux nombres, les ajoute et stocke le résultat dans un registre. La spécification se trouve dans la documentation à la page 526. Chaque instruction
ADD est la suivante:
Il y a deux lignes dans le diagramme, car il y a deux «modes» différents pour cette instruction. Avant d'expliquer les modes, essayons de trouver les similitudes entre eux. Les deux commencent par quatre bits identiques
0001 . Il s'agit de la valeur de l'opcode pour
OP_ADD . Les trois bits suivants sont marqués
DR pour le registre de sortie. Le registre de sortie est l'emplacement de stockage du montant. Les trois bits suivants sont:
SR1 . Il s'agit d'un registre contenant le premier numéro à ajouter.
Ainsi, nous savons où enregistrer le résultat et nous connaissons le premier nombre à ajouter. Il ne reste plus qu'à trouver le deuxième numéro à ajouter. Ici, les deux lignes commencent à différer. Notez que le 5ème bit est 0 en haut et 1. est en bas. Ce bit correspond soit
au mode direct soit
au mode registre . En mode registre, le deuxième numéro est enregistré dans le registre, comme le premier. Il est marqué comme
SR2 et est contenu dans les bits deux à zéro. Les bits 3 et 4 ne sont pas utilisés. En assembleur, il s'écrira comme ceci:
ADD R2 R0 R1 ; add the contents of R0 to R1 and store in R2.
En mode immédiat, au lieu d'ajouter le contenu du registre, la valeur immédiate est intégrée dans l'instruction elle-même. Ceci est pratique car le programme n'a pas besoin d'instructions supplémentaires pour charger ce numéro dans le registre à partir de la mémoire. Au lieu de cela, il est déjà dans l'instruction lorsque nous en avons besoin. Le compromis est que seuls de petits nombres peuvent y être stockés. Pour être précis, un maximum de 2
5 = 32. Ceci est très utile pour augmenter les compteurs ou les valeurs. Dans l'assembleur, vous pouvez écrire comme ceci:
ADD R0 R0 1 ; add 1 to R0 and store back in R0
Voici un extrait de la spécification:
Si le bit [5] est égal à 0, le deuxième opérande source est obtenu à partir de SR2. Si le bit [5] est égal à 1, le deuxième opérande source est obtenu en étendant imm5 à 16 bits. Dans les deux cas, le deuxième opérande source est ajouté au contenu de SR1 et le résultat est stocké dans DR. (p. 526)
Ceci est similaire à ce que nous avons discuté. Mais qu'est-ce qu'une «extension de sens»? Bien qu'en mode direct, la valeur ne dispose que de 5 bits, elle doit être ajoutée avec un nombre de 16 bits. Ces 5 bits doivent être étendus à 16 pour correspondre à un autre nombre. Pour les nombres positifs, nous pouvons remplir les bits manquants avec des zéros et obtenir la même valeur. Cependant, pour les nombres négatifs, cela ne fonctionne pas. Par exemple, −1 sur cinq bits est
1 1111 . Si vous le remplissez simplement de zéros, nous obtenons
0000 0000 0001 1111 , soit 32! Le développement de la valeur empêche ce problème en remplissant les bits avec des zéros pour les nombres positifs et des uns pour les nombres négatifs.
uint16_t sign_extend(uint16_t x, int bit_count) { if ((x >> (bit_count - 1)) & 1) { x |= (0xFFFF << bit_count); } return x; }
Remarque: si vous êtes intéressé par les nombres négatifs binaires, vous pouvez lire des informations supplémentaires sur le code . Mais ce n'est pas essentiel. Copiez simplement le code ci-dessus et utilisez-le lorsque la spécification indique d'augmenter la valeur.
La spécification a la dernière phrase:
Les codes de condition sont définis selon que le résultat est négatif, nul ou positif. (p. 526)
Plus tôt, nous avons défini la condition d'énumération des drapeaux, et maintenant il est temps d'utiliser ces drapeaux. Chaque fois qu'une valeur est écrite dans le registre, nous devons mettre à jour les drapeaux pour indiquer son signe. Nous écrivons une fonction à réutiliser:
void update_flags(uint16_t r) { if (reg[r] == 0) { reg[R_COND] = FL_ZRO; } else if (reg[r] >> 15) { reg[R_COND] = FL_NEG; } else { reg[R_COND] = FL_POS; } }
Nous sommes maintenant prêts à écrire le code pour
ADD :
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t imm_flag = (instr >> 5) & 0x1; if (imm_flag) { uint16_t imm5 = sign_extend(instr & 0x1F, 5); reg[r0] = reg[r1] + imm5; } else { uint16_t r2 = instr & 0x7; reg[r0] = reg[r1] + reg[r2]; } update_flags(r0); }
Cette section contient beaucoup d'informations, alors résumons.
ADD prend deux valeurs et les stocke dans un registre.- En mode registre, la deuxième valeur à ajouter est en registre.
- En mode direct, la deuxième valeur est intégrée dans les 5 bits de droite de l'instruction.
- Les valeurs inférieures à 16 bits doivent être développées.
- Chaque fois que l'instruction change de casse, les indicateurs de condition doivent être mis à jour.
Vous pourriez être dépassé en écrivant 15 autres instructions. Cependant, les informations obtenues ici peuvent être réutilisées. La plupart des instructions utilisent une combinaison d'extension de valeur, de divers modes et de mises à jour d'indicateurs.
LDI
LDI signifie chargement "indirect" ou "indirect" (chargement indirect). Cette instruction est utilisée pour charger une valeur d'un emplacement mémoire dans un registre. Spécifications à la page 532.
Voici à quoi ressemble la disposition binaire:
Contrairement à
ADD , il n'y a pas de modes et moins de paramètres. Cette fois, le code d'opération est
1010 , ce qui correspond à la valeur d'énumération
OP_LDI . Encore une fois, nous voyons un
DR (registre de sortie) à trois bits pour stocker la valeur chargée. Les bits restants sont marqués comme
PCoffset9 . Il s'agit de la valeur immédiate intégrée à l'instruction (similaire à
imm5 ). Étant donné que l'instruction est chargée à partir de la mémoire, nous pouvons deviner que ce nombre est une sorte d'adresse qui indique où charger la valeur. La spécification explique plus en détail:
L'adresse est calculée en étendant les bits de la valeur [8:0] à 16 bits et en ajoutant cette valeur au PC agrandi. Ce qui est stocké en mémoire à cette adresse est l'adresse des données qui seront chargées dans le DR . (p. 532)
Comme précédemment, vous devez étendre cette valeur 9 bits, mais cette fois-ci, ajoutez-la au
PC actuel. (Si vous regardez le cycle d'exécution, le
PC augmenté immédiatement après le chargement de cette instruction). La somme résultante est l'adresse d'emplacement en mémoire, et cette adresse
contient une autre valeur, qui est l'adresse de la valeur de chargement.
Cela peut sembler un moyen détourné de lire de mémoire, mais c'est nécessaire. L'instruction
LD est limitée à un décalage d'adresse de 9 bits, tandis que la mémoire nécessite une adresse de 16 bits.
LDI est utile pour charger des valeurs qui sont stockées quelque part en dehors de l'ordinateur actuel, mais pour les utiliser, l'adresse de l'emplacement final doit être stockée à proximité. Vous pouvez le considérer comme une variable locale en C, qui est un pointeur vers certaines données:
Comme précédemment, après avoir écrit la valeur dans
DR , les drapeaux doivent être mis à jour:
Les codes de condition sont définis selon que le résultat est négatif, nul ou positif. (p. 532)
Voici le code de ce cas: (
mem_read discuté dans la section suivante):
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset)); update_flags(r0); }
Comme je l'ai dit, pour cette instruction, nous avons utilisé une partie importante du code et des connaissances acquises plus tôt lors de l'écriture d'
ADD . La même chose avec le reste des instructions.
Vous devez maintenant implémenter le reste des instructions. Suivez les
spécifications et utilisez le code déjà écrit. Le code de toutes les instructions est donné à la fin de l'article. Deux des opcodes mentionnés précédemment ne seront pas nécessaires:
OP_RTI et
OP_RES . Vous pouvez les ignorer ou donner une erreur s'ils sont appelés. Une fois terminé, la majeure partie de votre machine virtuelle peut être considérée comme complète!
7. Lit d'enfant selon les instructions
Cette section contient des implémentations complètes des instructions restantes si vous êtes bloqué.
RTI & RES
(non utilisé)
abort();
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t imm_flag = (instr >> 5) & 0x1; if (imm_flag) { uint16_t imm5 = sign_extend(instr & 0x1F, 5); reg[r0] = reg[r1] & imm5; } else { uint16_t r2 = instr & 0x7; reg[r0] = reg[r1] & reg[r2]; } update_flags(r0); }
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; reg[r0] = ~reg[r1]; update_flags(r0); }
Succursale
{ uint16_t pc_offset = sign_extend((instr) & 0x1ff, 9); uint16_t cond_flag = (instr >> 9) & 0x7; if (cond_flag & reg[R_COND]) { reg[R_PC] += pc_offset; } }
Sauter
RET est indiqué comme une instruction distincte dans la spécification, car il s'agit d'une autre commande dans l'assembleur. Il s'agit en fait d'un cas particulier de
JMP .
RET se produit chaque fois que
R1 est 7.
{ uint16_t r1 = (instr >> 6) & 0x7; reg[R_PC] = reg[r1]; }
Registre de saut
{ uint16_t r1 = (instr >> 6) & 0x7; uint16_t long_pc_offset = sign_extend(instr & 0x7ff, 11); uint16_t long_flag = (instr >> 11) & 1; reg[R_R7] = reg[R_PC]; if (long_flag) { reg[R_PC] += long_pc_offset; } else { reg[R_PC] = reg[r1]; } break; }
Charge
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = mem_read(reg[R_PC] + pc_offset); update_flags(r0); }
Registre de charge
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t offset = sign_extend(instr & 0x3F, 6); reg[r0] = mem_read(reg[r1] + offset); update_flags(r0); }
Adresse de chargement effective
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = reg[R_PC] + pc_offset; update_flags(r0); }
Boutique
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); mem_write(reg[R_PC] + pc_offset, reg[r0]); }
Magasin indirect
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); mem_write(mem_read(reg[R_PC] + pc_offset), reg[r0]); }
Registre du magasin
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t offset = sign_extend(instr & 0x3F, 6); mem_write(reg[r1] + offset, reg[r0]); }
8. Procédures de traitement des interruptions
LC-3 fournit plusieurs routines prédéfinies pour effectuer des tâches courantes et interagir avec les périphériques d'E / S. Par exemple, il existe des procédures pour obtenir les lignes d'entrée et de sortie du clavier vers la console. Ils sont appelés routines d'interruption, que vous pouvez considérer comme le système d'exploitation ou l'API pour LC-3. Chaque sous-programme se voit attribuer un code d'interruption (code d'interruption) qui l'identifie (semblable à un opcode).
Pour l'exécuter, une instruction est appelée TRAPavec le code du sous-programme souhaité.Définissez une énumération pour chaque code d'interruption: enum { TRAP_GETC = 0x20, TRAP_OUT = 0x21, TRAP_PUTS = 0x22, TRAP_IN = 0x23, TRAP_PUTSP = 0x24, TRAP_HALT = 0x25 };
Vous vous demandez peut-être pourquoi les codes d'interruption ne sont pas inclus dans les instructions. En effet, ils n'ajoutent en fait aucune nouvelle fonctionnalité au LC-3, mais fournissent uniquement un moyen pratique de terminer la tâche (comme les fonctions système en C). Dans le simulateur officiel LC-3, les codes d'interruption sont écrits en assembleur . Lorsqu'un code d'interruption est appelé, l'ordinateur se déplace vers l'adresse de ce code. La CPU exécute les instructions de la procédure et, une fois terminée, est PCréinitialisée à l'emplacement à partir duquel l'interruption a été appelée.: 0x3000 0x0 . , .
Il n'y a aucune spécification sur la façon d' implémenter des routines d'interruption: juste ce qu'elles doivent faire. Dans notre VM, nous agirons un peu différemment en les écrivant en C. Lorsque le code d'interruption est appelé, la fonction C sera appelée. Après son fonctionnement, l'instruction continuera.Bien que les procédures puissent être écrites en assembleur et que l'ordinateur physique LC-3 le soit, ce n'est pas la meilleure option pour la machine virtuelle. Au lieu d'écrire vos propres procédures d'entrée-sortie primitives, vous pouvez utiliser celles qui sont disponibles sur notre système d'exploitation. Cela améliorera la machine virtuelle sur nos ordinateurs, simplifiera le code et fournira un niveau d'abstraction plus élevé pour la portabilité.Remarque: Un exemple spécifique est la saisie au clavier. La version assembleur utilise une boucle pour vérifier en continu la saisie au clavier. Mais tant de temps processeur est perdu! En utilisant la fonction OS appropriée, le programme peut dormir paisiblement avant le signal d'entrée.
Dans l'opérateur à choix multiple pour l'opcode, TRAPajoutez un autre commutateur: switch (instr & 0xFF) { case TRAP_GETC: {TRAP GETC, 9} break; case TRAP_OUT: {TRAP OUT, 9} break; case TRAP_PUTS: {TRAP PUTS, 8} break; case TRAP_IN: {TRAP IN, 9} break; case TRAP_PUTSP: {TRAP PUTSP, 9} break; case TRAP_HALT: {TRAP HALT, 9} break; }
Comme pour les instructions, je vais vous montrer comment mettre en œuvre une procédure et faire le reste vous-même.Putts
Le code d'interruption est PUTSutilisé pour renvoyer une chaîne avec un zéro de fin (de même printfen C). Spécifications à la page 543.Pour afficher une chaîne, nous devons donner à la routine d'interruption une chaîne à afficher. Cela se fait en stockant l'adresse du premier caractère R0avant le début du traitement.De la spécification:Affichez la chaîne de caractères ASCII sur l'écran de la console. Les caractères sont contenus dans des cellules de mémoire consécutives, un caractère par cellule, en commençant à l'adresse spécifiée dans R0. La sortie se termine lorsqu'une valeur est rencontrée dans la mémoire x0000. (p. 543)
Notez que contrairement aux chaînes C, ici, les caractères ne sont pas stockés dans un octet, mais dans un emplacement en mémoire . L'emplacement de mémoire du LC-3 est de 16 bits, donc chaque caractère de la chaîne est de 16 bits. Pour afficher cela dans la fonction C, vous devez convertir chaque valeur en caractère et les imprimer séparément. { uint16_t* c = memory + reg[R_R0]; while (*c) { putc((char)*c, stdout); ++c; } fflush(stdout); }
Rien de plus n'est requis pour cette procédure. Les routines d'interruption sont assez simples si vous connaissez C. Revenez maintenant aux spécifications et implémentez le reste. Comme pour les instructions, le code complet se trouve à la fin de ce guide.9. Aide-mémoire pour les routines d'interruption
Cette section contient des implémentations complètes des routines d'interruption restantes.Saisie de caractères
reg[R_R0] = (uint16_t)getchar();
Sortie de caractères
putc((char)reg[R_R0], stdout); fflush(stdout);
Demande de saisie de caractères
printf("Enter a character: "); reg[R_R0] = (uint16_t)getchar();
Sortie ligne
{ uint16_t* c = memory + reg[R_R0]; while (*c) { char char1 = (*c) & 0xFF; putc(char1, stdout); char char2 = (*c) >> 8; if (char2) putc(char2, stdout); ++c; } fflush(stdout); }
Fin du programme
puts("HALT"); fflush(stdout); running = 0;
10. Téléchargement de programmes
Nous avons beaucoup parlé du chargement et de l'exécution des instructions à partir de la mémoire, mais comment les instructions entrent-elles dans la mémoire en général? Lors de la conversion d'un programme assembleur en code machine, le résultat est un fichier contenant un tableau d'instructions et de données. Il peut être téléchargé en copiant simplement le contenu directement dans une adresse en mémoire.Les 16 premiers bits du fichier programme indiquent l'adresse en mémoire où le programme doit démarrer. Cette adresse est appelée origine . Il doit être lu en premier, après quoi le reste des données est lu en mémoire à partir du fichier.Voici le code pour charger le programme dans la mémoire LC-3: void read_image_file(FILE* file) { uint16_t origin; fread(&origin, sizeof(origin), 1, file); origin = swap16(origin); uint16_t max_read = UINT16_MAX - origin; uint16_t* p = memory + origin; size_t read = fread(p, sizeof(uint16_t), max_read, file); while (read-- > 0) { *p = swap16(*p); ++p; } }
Notez que pour chaque valeur chargée est appelée swap16. Les programmes LC-3 sont écrits dans l'ordre des octets directs, mais la plupart des ordinateurs modernes utilisent l'ordre inverse. Par conséquent, nous devons retourner chacun chargé uint16. (Si vous utilisez accidentellement un ordinateur étrange comme PPC , rien ne doit être changé). uint16_t swap16(uint16_t x) { return (x << 8) | (x >> 8); }
Remarque: l' ordre des octets fait référence à la façon dont les octets d'un entier sont interprétés. Dans l'ordre inverse, le premier octet est le chiffre le moins significatif, et dans l'ordre inverse, vice versa. Pour autant que je sache, la décision est essentiellement arbitraire. Différentes entreprises ont pris des décisions différentes, nous avons donc maintenant différentes implémentations. Pour ce projet, vous n'avez plus besoin de connaître quoi que ce soit sur l'ordre des octets.
Ajoutez également une fonction pratique pour read_image_file, qui prend le chemin de la chaîne: int read_image(const char* image_path) { FILE* file = fopen(image_path, "rb"); if (!file) { return 0; }; read_image_file(file); fclose(file); return 1; }
11. Registres mappés
Certains registres spéciaux ne sont pas disponibles dans la table des registres réguliers. Au lieu de cela, une adresse spéciale leur est réservée en mémoire. Pour lire et écrire dans ces registres, il vous suffit de lire et d'écrire dans leur mémoire. Ils sont appelés registres mappés en mémoire . Habituellement, ils sont utilisés pour interagir avec des périphériques matériels spéciaux.Pour notre LC-3, nous devons implémenter deux registres mappables. Il s'agit du registre d'état du clavier ( KBSR) et du registre de données du clavier ( KBDR). Le premier indique si la touche a été enfoncée et le second détermine quelle touche est enfoncée.Bien que la saisie au clavier puisse être demandée à l'aide GETC, elle bloque l'exécution jusqu'à la réception de la saisie. KBSRet KBDRpermettreinterroger l'état de l' appareil tout en continuant à exécuter le programme, afin qu'il reste réactif en attendant l'entrée. enum { MR_KBSR = 0xFE00, MR_KBDR = 0xFE02 };
Les registres mappés compliquent un peu l'accès à la mémoire. Nous ne pouvons pas lire et écrire directement dans la matrice de mémoire, mais nous devons plutôt appeler des fonctions spéciales - le setter et le getter. Après avoir lu la mémoire du registre KBSR, le getter vérifie le clavier et met à jour les deux emplacements en mémoire. void mem_write(uint16_t address, uint16_t val) { memory[address] = val; } uint16_t mem_read(uint16_t address) { if (address == MR_KBSR) { if (check_key()) { memory[MR_KBSR] = (1 << 15); memory[MR_KBDR] = getchar(); } else { memory[MR_KBSR] = 0; } } return memory[address]; }
Ceci est le dernier composant d'une machine virtuelle! Si vous avez implémenté le reste des routines d'interruption et des instructions, vous êtes presque prêt à l'essayer!Tout ce qui est écrit doit être ajouté au fichier C dans l'ordre suivant: {Memory Mapped Registers, 11} {TRAP Codes, 8} {Memory Storage, 3} {Register Storage, 3} {Functions, 12} {Main Loop, 5}
12. Caractéristiques de la plateforme
Cette section contient quelques détails fastidieux nécessaires pour accéder au clavier et fonctionner correctement. Il n'y a rien d'intéressant ou d'information sur le fonctionnement des machines virtuelles. N'hésitez pas à copier-coller!Si vous essayez de démarrer la machine virtuelle dans un système d'exploitation autre qu'Unix, tel que Windows, ces fonctions doivent être remplacées par les fonctions Windows correspondantes. uint16_t check_key() { fd_set readfds; FD_ZERO(&readfds); FD_SET(STDIN_FILENO, &readfds); struct timeval timeout; timeout.tv_sec = 0; timeout.tv_usec = 0; return select(1, &readfds, NULL, NULL, &timeout) != 0; }
Code pour extraire le chemin des arguments du programme et afficher un exemple d'utilisation s'ils sont manquants. if (argc < 2) { printf("lc3 [image-file1] ...\n"); exit(2); } for (int j = 1; j < argc; ++j) { if (!read_image(argv[j])) { printf("failed to load image: %s\n", argv[j]); exit(1); } }
Code de configuration d'entrée de terminal spécifique à Unix. struct termios original_tio; void disable_input_buffering() { tcgetattr(STDIN_FILENO, &original_tio); struct termios new_tio = original_tio; new_tio.c_lflag &= ~ICANON & ~ECHO; tcsetattr(STDIN_FILENO, TCSANOW, &new_tio); } void restore_input_buffering() { tcsetattr(STDIN_FILENO, TCSANOW, &original_tio); }
Lorsque le programme est interrompu, nous voulons rétablir la console à ses paramètres normaux. void handle_interrupt(int signal) { restore_input_buffering(); printf("\n"); exit(-2); }
signal(SIGINT, handle_interrupt); disable_input_buffering();
restore_input_buffering();
{Sign Extend, 6} {Swap, 10} {Update Flags, 6} {Read Image File, 10} {Read Image, 10} {Check Key, 12} {Memory Access, 11} {Input Buffering, 12} {Handle Interrupt, 12}
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <signal.h> #include <unistd.h> #include <fcntl.h> #include <sys/time.h> #include <sys/types.h> #include <sys/termios.h> #include <sys/mman.h>
Démarrage de la machine virtuelle
Vous pouvez maintenant créer et exécuter la machine virtuelle LC-3!- Compilez le programme avec votre compilateur préféré.
- Téléchargez la version compilée de 2048 ou Rogue .
- Exécutez le programme avec le fichier obj comme argument:
lc3-vm path/to/2048.obj - Jouez en 2048!
Control the game using WASD keys. Are you on an ANSI terminal (y/n)? y +--------------------------+ | | | | | | | 2 | | | | 2 | | | | | | | +--------------------------+
Débogage
Si le programme ne fonctionne pas correctement, il est fort probable que vous ayez mal codé une sorte d’instruction. Il peut être difficile de déboguer. Je vous recommande de lire le code d'assemblage du programme en même temps - et à l'aide du débogueur, suivez pas à pas les instructions de la machine virtuelle. Lors de la lecture du code, assurez-vous que la machine virtuelle va à l'instruction prévue. Si une incompatibilité se produit, vous découvrirez quelle instruction a causé le problème. Relisez la spécification et revérifiez le code.14. Méthode alternative en C ++
Voici un moyen avancé d'exécuter des instructions qui réduit considérablement la taille du code. Il s'agit d'une section complètement facultative.Étant donné que C ++ prend en charge des génériques puissants pendant le processus de compilation, nous pouvons créer des parties d'instructions à l'aide du compilateur. Cette méthode réduit la duplication de code et est en fait plus proche du niveau matériel de l'ordinateur.L'idée est de réutiliser les étapes communes à chaque instruction. Par exemple, certaines instructions utilisent l'adressage indirect ou l'extension d'une valeur et l'ajoutent à la valeur actuelle PC. D'accord, ce serait bien d'écrire ce code une fois pour toutes les instructions?En considérant l'instruction comme une séquence d'étapes, nous voyons que chaque instruction n'est qu'un réarrangement de plusieurs étapes plus petites. Nous utiliserons des indicateurs de bits pour indiquer les étapes à suivre pour chaque instruction. La valeur 1dans le bit du numéro d'instruction indique que pour cette instruction, le compilateur doit inclure cette section de code. template <unsigned op> void ins(uint16_t instr) { uint16_t r0, r1, r2, imm5, imm_flag; uint16_t pc_plus_off, base_plus_off; uint16_t opbit = (1 << op); if (0x4EEE & opbit) { r0 = (instr >> 9) & 0x7; } if (0x12E3 & opbit) { r1 = (instr >> 6) & 0x7; } if (0x0022 & opbit) { r2 = instr & 0x7; imm_flag = (instr >> 5) & 0x1; imm5 = sign_extend((instr) & 0x1F, 5); } if (0x00C0 & opbit) {
static void (*op_table[16])(uint16_t) = { ins<0>, ins<1>, ins<2>, ins<3>, ins<4>, ins<5>, ins<6>, ins<7>, NULL, ins<9>, ins<10>, ins<11>, ins<12>, NULL, ins<14>, ins<15> };
Remarque: J'ai appris cette technique grâce à l'émulateur NES développé par Bisqwit . Si vous êtes intéressé par l'émulation ou NES, je recommande fortement ses vidéos.D'autres versions de C ++ utilisent le code déjà écrit. Version complète ici . {Includes, 12} {Registers, 3} {Condition Flags, 3} {Opcodes, 3} {Memory Mapped Registers, 11} {TRAP Codes, 8} {Memory Storage, 3} {Register Storage, 3} {Functions, 12} int running = 1; {Instruction C++, 14} {Op Table, 14} int main(int argc, const char* argv[]) { {Load Arguments, 12} {Setup, 12} enum { PC_START = 0x3000 }; reg[R_PC] = PC_START; while (running) { uint16_t instr = mem_read(reg[R_PC]++); uint16_t op = instr >> 12; op_table[op](instr); } {Shutdown, 12} }