La programmation en langage machine est rapidement fastidieuse. Il est inhumain de se souvenir du codage de chacune des instructions d'un micro-processeur même simplifié à l'extrême comme le LC-3 et a fortiori encore plus pour un micro-processeur réel. Le langage d'assemblage ou assembleur par abus de langage rend la tâche beaucoup plus facile même si cette programmation reste longue et technique.
L'assembleur est un programme qui autorise le programmeur à écrire les instructions du micro-processeur sous forme symbolique. Il se charge de traduire cette écriture symbolique en codage hexadécimal ou binaire. Il est beaucoup plus aisé d'écrire ADD R6,R1,R2 plutôt que 0x1C42 en hexadécimal ou encore 0001 1100 0100 0010 en binaire.
L'assembleur permet aussi l'utilisation d'étiquettes symboliques pour désigner certaines adresses. L'étiquette est associée à une adresse et peut alors être utilisée dans d'autres instructions. On peut par exemple écrire un morceau de code comme ci-dessous.... label: ADD R6,R1,R2 ... BRz label ...
L'étiquette label est alors associée à l'adresse ou se trouvera l'instruction ADD R6,R1,R2 lors de l'exécution du programme. Cette adresse est alors utilisée pour calculer le codage de l'instruction BRz label. Comme le codage de l'instruction BR contient un offset, l'assembleur calcule la différence entre les adresses des deux instructions ADD R6,R1,R2 et BRz label et place cette valeur dans les 9 bits de poids faible du codage de BRz.
La syntaxe des programmes en assembleur est la même pour tous les assembleurs à quelques détails près.
Les instructions d'un programme en assembleur sont mises dans un fichier dont le nom se termine par l'extension .asm. Chaque ligne du fichier contient au plus une instruction du programme. Chaque ligne est en fait divisée en deux champs qui peuvent chacun ne rien contenir. Le premier champ contient une étiquette et le second champ une instruction. L'instruction est formée de son nom symbolique appelé mnémonique et d'éventuel paramètres.
Les espaces sont uniquement utiles comme séparateurs. Plusieurs espaces sont équivalents à un seul. Les programmes sont indentés de telle manière que les étiquettes se trouvent dans une première colonne et les instructions dans une seconde colonne.
L'instruction peut être remplacée dans une ligne par une directive d'assemblage. Les directives d'assemblage permettent de donner des ordres à l'assembleur. Elles sont l'équivalent des directives commençant par '#' comme #include ou #if du langage C.
Il existe deux types de constantes : les constantes entières et les chaînes de caractères. Les chaînes de caractères peuvent uniquement apparaître après la directive .STRINGZ. Elles sont alors délimitées par deux caractères '"' comme dans "Exemple de chaine" et sont implicitement terminées par le caractère nul '\0'.
Les constantes entières peuvent apparaître comme paramètre des instructions du LC3 et des directives .ORIG, .FILL et .BLKW. Elles peuvent être données soit sous la forme d'un entier écrit dans la base 10 ou 16, soit sous la forme d'un caractère. Les constantes écrite en base 16 sont préfixées par le caractère x. Lorsque la constante est donnée sous forme d'un caractère, sa valeur est le code ASCII du caractère. Le caractère est alors entouré de caractères ''' comme dans 'Z'.
; Exemple de constantes .ORIG x3000 ; Constante entière en base 16 AND R2,R1,2 ; Constante entière en base 10 ADD R6,R5,-1 ; Constante entière négative en base 10 .FILL 'Z' ; Constante sous forme d'un caractère .STRINGZ "Chaine" ; Constante chaîne de caractères .END
Les commentaires sont introduits par le caractère point-virgule ';' et il s'étendent jusqu'à la fin de la ligne. Ils sont mis après les deux champs d'étiquette et d'instruction mais comme ces deux champs peuvent être vides, les commentaires peuvent commencer dès le début de la ligne ou après l'étiquette. Voici quelques exemples de commentaires
; Commentaire dès le début de la ligne label: ADD R6,R1,R2 ; Commentaire après l'instruction loop: ; Commentaire après l'étiquette (avec indentation) BRz label
Les étiquettes sont des identificateurs formés de caractères alphanumériques et commençant par une lettre. Elles désignent une adresse qui peut alors être utilisée dans les instructions.
L'adresse est spécifiée en mettant l'étiquette suivie du caractère ':' dans la première colonne d'une ligne du programme. L'étiquette est alors affectée de l'adresse à laquelle se trouve l'instruction. L'étiquette peut également être mise avant une directive d'assemblage comme .BLKW, .FILL ou .STRINGZ. Elle désigne alors l'adresse à laquelle sont placés les mots mémoires produits par la directive.
; Exemple d'étiquettes label: ADD R0,R1,R2 ; 'label' désigne l'adresse de l'instruction ADD char: .FILL 'Z' ; 'char' désigne l'adresse du caractère 'Z' string: .STRINGZ "Chaine" ; 'string' désigne l'adresse du premier caractère 'C'
On étudie dans cette partie quelques exemples de programmes (très) simples afin d'illustrer quelques techniques classiques de programmation en langage machine. Les codes complets de ces programmes ainsi que d'autres sont disponibles ci-dessous
Les programmes ci-dessous sont présentés comme des fragments de programmes puisque les routines n'ont pas encore été présentées. Il faudrait les écrire sous forme de routines pour une réelle utilisation.
On commence par rappeler le programme en C pour calculer la longueur d'une chaîne de caractères terminée par '\0'.
int strlen(char* p) { int c = 0; while (*p != '\0') { p++; c++; } return c; }
Le programme ci-dessous calcule la longueur d'une chaîne de caractères terminée par le caractère nul '\0'. Le registre R0 est utilisé comme pointeur pour parcourir la chaîne alors que le registre R1 est utilisé comme compteur.
; @param R0 adresse de la chaîne ; @return R1 longueur de la chaîne .ORIG x3000 LEA R0,chaine ; Chargement dans RO de l'adresse de la chaîne AND R1,R1,0 ; Mise à 0 du compteur : c = 0 loop: LDR R2,R0,0 ; Chargement dans R2 du caractère pointé par R0 BRz fini ; Test de fin de chaîne ADD R0,R0,1 ; Incrémentation du pointeur : p++ ADD R1,R1,1 ; Incrémentation du compteur : c++ BR loop fini: NOP chaine: .STRINGZ "Hello World" .END
Le programme C pour calculer la longueur d'une chaîne de caractères peut être écrit de manière différente en utilisant l'arithmétique sur les pointeurs.
int strlen(char* p) { char* q = p; while (*p != '\0') p++; return p-q; }
Ce programme C se transpose également en langage d'assembleur. Le registre R0 est encore utilisé comme pointeur pour parcourir la chaîne et le registre R1 sauvegarde la valeur initiale de R0. Il contient en fait l'opposé de la valeur initiale de R0 afin de calculer la différence. Ce programme a le léger avantage d'être plus rapide que le précédent car la boucle principale contient une instruction de moins.
; @param R0 adresse de la chaîne ; @return R0 longueur de la chaîne .ORIG x3000 LEA R0,chaine ; Chargement dans R0 de l'adresse de la chaîne NOT R1,R0 ; R1 = -R0 ADD R1,R1,1 loop: LDR R2,R0,0 ; Chargement dans R2 du caractère pointé par R0 BRz fini ; Test de fin de chaîne ADD R0,R0,1 ; Incrémentation du pointeur : p++ BR loop fini: ADD R0,R0,R1 ; Calcul de la différence q-p chaine: .STRINGZ "Hello World" .END
Le programme ci-dessous calcule le nombre d'occurrences d'un caractère donné dans une chaîne de caractères terminée par le caractère nul '\0'. Le registre R0 est utilisé comme pointeur pour parcourir la chaîne. Le registre R1 contient le caractère recherché et le registre R2 est utilisé comme compteur. La comparaison entre chaque caractère de la chaîne et le caractère recherché est effectuée en calculant la différence de leurs codes et en testant si celle-ci est nulle. Dans ce but, le programme commence par calculer l'opposé du code du caractère recherché afin de calculer chaque différence par une addition.
; @param R0 adresse de la chaîne ; @param R1 caractère ; @return R2 nombre d'occurrences du caractère .ORIG x3000 LEA R0,chaine ; Chargement dans RO de l'adresse de la chaîne LD R1,caract ; Chargement dans R1 du code ASCII de 'l' AND R2,R2,0 ; Mise à 0 du compteur NOT R1,R1 ; Calcul de l'opposé de R1 ADD R1,R1,1 ; R1 = -R1 loop: LDR R3,R0,0 ; Chargement dans R3 du caractère pointé par R0 BRz fini ; Test de fin de chaîne ADD R3,R3,R1 ; Comparaison avec 'l' BRnp suite ; Non égalité ADD R2,R2,1 ; Incrémentation du compteur suite: ADD R0,R0,1 ; Incrémentation du pointeur BR loop fini: NOP chaine: .STRINGZ "Hello World" caract: .FILL 'l' .END
Tous les micro-processeurs actuels possèdent une multiplication câblée pour les entiers et pour les nombres flottants. Comme les premiers micro-processeurs, le LC-3 n'a pas de telle instruction. La multiplication doit donc être réalisée par programme. Les programmes ci-dessous donnent quelques implémentation de la multiplication pour les entiers signés et non signés.
On commence par une implémentation très naïve de la multiplication qui est effectuée par additions successives. On commence par donner une implémentation sous forme de programme C puis on donne ensuite une traduction en langage d'assembleur.
// Programme sous forme d'une fonction en C int mult(int x, int n) { int r = 0; // Résultat while(n != 0) { r += x; n--; } return r; }
Dans le programme ci-dessous, les registres R0 et R1 contiennent respectivement x et n. Le registre R2 contient les valeurs successives de r.
; @param R0 x ; @param R1 n ; @return R2 x × n .ORIG x3000 AND R2,R2,0 ; r = 0 AND R1,R1,R1 ; Mise à jour de l'indicateur z pour le test BRz fini loop: ADD R2,R2,R0 ; r += x ADD R1,R1,-1 ; n-- BRnp loop ; Boucle si n != 0 fini: NOP .END
Le programme précédent fonctionne encore si la valeur de x est négative. Par contre, il ne fonctionne plus si la valeur de n est négative. Les décrémentations successives de n ne conduisent pas à 0 en le nombre d'étapes voulues. Le programme suivant résout ce problème en inversant les signes de x et n si n est négatif. Ensuite, il procède de manière identique au programme précédent.
; @param R0 x ; @param R1 n ; @return R2 x × n .ORIG x3000 AND R2,R2,0 ; r = 0 AND R1,R1,R1 ; Mise à jour de l'indicateur z pour le test BRz fini BRp loop ; Changement de signe de x et n NOT R0,R0 ; x = -x ADD R0,R0,1 NOT R1,R1 ; n = -n ADD R1,R1,1 loop: ADD R2,R2,R0 ; r += x ADD R1,R1,-1 ; n-- BRnp loop ; Boucle si n != 0 fini: NOP .END
Le problème majeur des deux programmes précédents est leur temps d'exécution. En effet, le nombre d'itérations de la boucle est égal à la valeur de R1 et le temps est donc proportionnel à cette valeur. Le programme ci-dessous donne une meilleure implémentation de la multiplication de nombres non signés. Ce programme pourrait être étendu aux nombres signés de la même façon que pour l'implémentation naïve. Son temps d'exécution est proportionnel au nombre de bits des registres.
On commence par donner un algorithme récursif en C pour calculer une multiplication qui est inspiré de l'exponentiation logarithmique.
// Programme sous forme d'une fonction récursive en C // Calcul de x * n de façon logarithmique float mult(float x, int n) { if (n == 0) return 0; // Calcul anticipé de la valeur pour n/2 afin // d'avoir un seul appel récursif. float y = mult(x, n/2); if (n%2 == 0) return y + y; else return y + y + x; }
Pour éviter d'écrire un programme récursif, on exprime le problème d'une autre façon. On suppose que l'écriture binaire du contenu de R1 est bk-1…b0 où k est le nombre de bits de chaque registre, c'est-à-dire 16 pour le LC-3. On a alors la formule suivante qui exprime le produit x × n avec uniquement des multiplications par 2 et des additions. Cette formule est très semblable au schéma de Horner pour évaluer un polynôme.
x × n = ((…((xbk-12 + xbk-2)2 + xbk-3)2 + … )2 + xb1)2 + xb0.
On note x1, …, xk les résultats partiels obtenus en évaluant la formule ci-dessus de la gauche vers la droite. On pose x0 = 0 et pour 1 ≤ j ≤ k, le nombre xj est donné par la formule suivante.
xj = ((…((xbk-12 + xbk-2)2 + xbk-3)2 + … )2 + xbk-j+1)2 + xbk-j.
Le nombre xk est égal au produit x × n. Il est de plus facile de calculer xj en connaissant xj-1 et bk-j. On a en effet les relations suivantes.
xj = 2xj-1
si bk-j = 0
xj = 2xj-1 + x si bk-j = 1
Le programme suivant calcule le produit x × n en partant de x0 = 0 puis en calculant de proche en proche les nombres xj grâce aux formules ci-dessus. Les registres R0 et R1 contiennent respectivement x et n. Le registre R2 contient les valeurs successives x0, …, xk et le registre R3 est utilisé comme compteur. Pour accéder aux différents bits bk-1, …, b0 de n, on utilise le procédé suivant. Le signe de n vu comme un entier signé donne la valeur de bk-1. Ensuite, l'entier n est décalé vers la gauche d'une position à chaque itération. Le signe des contenus successifs de R2 donne les valeurs bk-2, …, b0.
; @param R0 x ; @param R1 n ; @return R2 x × n .ORIG x3000 AND R2,R2,0 ; Initialisation x0 = 0 LD R3,cst16 ; Initialisation du compteur AND R1,R1,R1 BRzp bit0 bit1: ADD R2,R2,R0 ; Addition de x si bk-j = 1 bit0: ADD R3,R3,-1 ; Décrémentation du compteur BRz fini ADD R2,R2,R2 ; Calcul de 2xj-1 ADD R1,R1,R1 ; Décalage de n vers la gauche BRn bit1 BR bit0 fini: NOP cst16: .FILL 16 .END
Dans la majorité des micro-processeurs réels, il y a outre les flags n, z et p un flag c qui reçoit la retenue (Carry) lors d'une addition par une instruction ADD. Cela permet de récupérer facilement cette retenue en testant le flag c. Certains micro-processeurs possèdent aussi une instruction ADC qui ajoute au résultat de l'addition la valeur du flag c. Ceci permet d'enchaîner facilement des additions pour faire des calculs sur des entiers codés sur plusieurs mots. Le micro-processeur LC-3 n'a pas de telles facilités et il faut donc exploiter au mieux ses possibilités.
; @param R1,R0 poids fort et poids faible du premier argument ; @param R3,R2 poids fort et poids faible du second argument ; @return R5,R4 poids fort et poids faible du résultat .ORIG x3000 ; Addition des poids faibles ADD R4,R2,R0 ; Addition des poids forts ADD R5,R3,R2 ; Test s'il y a une retenue sur les poids faibles AND R0,R0,R0 BRn bit1 ; Cas où le bit de poids fort de R0 est 0 AND R2,R2,R2 ; Si les deux bits de poids fort de R1 et R0 sont 0, ; il n'y a pas de retenue. BRzp fini ; Si un seul des deux bits de poids fort de R1 et R0 est 1, ; il faut tester le bit de poids fort de R4 pour savoir ; s'il y a eu une retenue. testR4: AND R4,R4,R4 BRzp carry BR fini ; Cas où le bit de poids fort de R0 est 1 bit1: AND R2,R2,R2 ; Si le bit de poids fort de R1 est 0, on est ramené au cas ; un seul des deux bits de poids fort de R1 et R0 est 1. BRzp testR4 ; Si les deux bits de poids fort de R1 et R0 sont 1, ; il y a nécessairement une retenue. ; Correction de la retenue carry: ADD R5,R5,1 fini: NOP .END
; @param R0 valeur à convertir ADD R1,R0,0 ; R1 <- R0 ld R2,cst4 ; Nombre de caractères loopo: ld R3,cst4 ; Nombre de bits par caractère ; Rotation de 4 bits loopi: AND R1,R1,R1 BRn $1 ADD R1,R1,R1 BR $2 $1: ADD R1,R1,R1 ADD R1,R1,1 $2: ADD R3,R3,-1 BRp loopi ; Recupération de 4 bits AND R0,R1,0xf ADD R0,R0,-0xa BRn $3 ; Chiffres de 0 à 9 ld R3,cst40 ; 0x40 = '0' + 0xa BR $4 ; Chiffres de A à F $3: ld R3,cst51 ; 0x51 = 'A' + 0xa $4: ADD R0,R0,R3 TRAP 0x21 ; Affichage ADD R2,R2,-1 BRp loopo NOP TRAP 0x25 ; Arrêt cst4: .fill 4 cst40: .fill 0x40 cst51: .fill 0x51