Geekly articles weekly

Assembleur sale pirate 6502

Cet article répertorie certaines des astuces utilisées par les participants à mon petit concours de programmation Commodore 64 . Les règles du concours étaient simples: créer un fichier exécutable C64 (PRG) qui dessine deux lignes pour former l'image ci-dessous. Celui dont le fichier est plus petit a gagné.


Les candidatures au concours ont été publiées dans des tweets ouverts et dans des messages privés ne contenant que des octets du fichier PRG et un hachage MD5.

Liste des participants avec des liens vers le code source:


(Si j'ai raté quelqu'un, faites-le moi savoir, je mettrai à jour la liste).

Le reste de l'article est consacré à quelques astuces d'assembleur qui ont été utilisées dans la compétition.

Les bases


Graphics C64 fonctionne par défaut en mode d'encodage 40x25 caractères. Le framebuffer en RAM est divisé en deux tableaux:

  • $0400 (RAM écran, 40 x 25 octets)
  • $d800 (RAM couleur, 40x25 octets)

Pour définir un caractère, vous enregistrez l'octet dans la RAM à l'écran, à $0400 (par exemple, $0400+y*40+x ). La couleur RAM est initialisée par bleu clair par défaut (couleur 14): c'est la couleur que nous utilisons pour les lignes, c'est-à-dire que la couleur RAM peut être laissée sans toucher.

Vous contrôlez les couleurs de la bordure et de l'arrière-plan à l'aide des registres d'E / S mémoire dans $d020 (bordure) et $d021 (arrière-plan).

Tracer deux lignes est assez facile si vous programmez directement la pente d'une ligne fixe. Voici une implémentation C qui dessine des lignes et vide le contenu de l'écran vers stdout ( malloc() est utilisé pour faire fonctionner le code sur un PC):

 #include <stdint.h> #include <stdio.h> #include <stdlib.h> void dump(const uint8_t* screen) { const uint8_t* s = screen; for (int y = 0; y < 25; y++) { for (int x = 0; x < 40; x++, s++) { printf("%c", *s == 0xa0 ? '#' : '.'); } printf("\n"); } } void setreg(uintptr_t dst, uint8_t v) { // *((uint8_t *)dst) = v; } int main() { // uint8_t* screenRAM = (uint_8*)0x0400; uint8_t* screenRAM = (uint8_t *)calloc(40*25, 0x20); setreg(0xd020, 0); // Set border color setreg(0xd021, 0); // Set background color int yslope = (25<<8)/40; int yf = yslope/2; for (int x = 0; x < 40; x++) { int yi = yf >> 8; // First line screenRAM[x + yi*40] = 0xa0; // Second line (X-mirrored) screenRAM[(39-x) + yi*40] = 0xa0; yf += yslope; } dump(screenRAM); }

Les codes d'écran ci-dessus sont $20 (vide) et $a0 (bloc 8 × 8 rempli). Si vous exécutez, vous verrez une image ASCII avec deux lignes:

  ## .................................... ##
 .. # .................................. # ..
 ... ## .............................. ## ...
 ..... # ............................ # .....
 ...... ## ........................ ## ......
 ........ ## .................... ## ........
 .......... # .................. # ..........
 ........... ## .............. ## ...........
 ............. # ............ # .............
 .............. ## ........ ## ..............
 ................ ## .... ## ................
 .................. # .. # ..................
 ................... ## ...................
 .................. # .. # ..................
 ................ ## .... ## ................
 .............. ## ........ ## ..............
 ............. # ............ # .............
 ........... ## .............. ## ...........
 .......... # .................. # ..........
 ........ ## .................... ## ........
 ...... ## ........................ ## ......
 ..... # ............................ # .....
 ... ## .............................. ## ...
 .. # .................................. # ..
 ## .................................... ##

La même chose est trivialement implémentée dans l'assembleur:

 !include "c64.asm" +c64::basic_start(entry) entry: { lda #0 ; black color sta $d020 ; set border to 0 sta $d021 ; set background to 0 ; clear the screen ldx #0 lda #$20 clrscr: !for i in [0, $100, $200, $300] { sta $0400 + i, x } inx bne clrscr ; line drawing, completely unrolled ; with assembly pseudos lda #$a0 !for i in range(40) { !let y0 = Math.floor(25/40*(i+0.5)) sta $0400 + y0*40 + i sta $0400 + (24-y0)*40 + i } inf: jmp inf ; halt }

Il s'avère que PRG a une taille assez grande de 286 octets.

Avant de plonger dans l'optimisation, nous faisons quelques observations.

Premièrement, nous travaillons sur C64 avec les routines ROM en place. Il existe des tonnes de routines qui peuvent être utiles. Par exemple, effacer l'écran avec JSR $E544 .

Deuxièmement, les calculs d'adresse sur un processeur 8 bits tel que 6502 peuvent être fastidieux et consommer beaucoup d'octets. Ce processeur n'a pas non plus de multiplicateur, donc un calcul comme y*40+i inclut généralement un groupe de décalages logiques ou une table de recherche qui mange également des octets. Pour éviter de multiplier par 40, il est préférable d'avancer le curseur à l'écran de manière incrémentielle:

  int yslope = (25<<8)/40; int yf = yslope/2; uint8_t* dst = screenRAM; for (int x = 0; x < 40; x++) { dst[x] = 0xa0; dst[(39-x)] = 0xa0; yf += yslope; if (yf & 256) { // Carry set? dst += 40; yf &= 255; } }

Nous continuons d'ajouter la pente de la ligne au compteur fixe yf , et lorsque l'addition 8 bits définit le drapeau de report, ajoutez 40.

Voici une approche d'assembleur incrémentiel:

 !include "c64.asm" +c64::basic_start(entry) !let screenptr = $20 !let x0 = $40 !let x1 = $41 !let yf = $60 entry: { lda #0 sta x0 sta $d020 sta $d021 ; kernal clear screen jsr $e544 ; set screenptr = $0400 lda #<$0400 sta screenptr+0 lda #>$0400 sta screenptr+1 lda #80 sta yf lda #39 sta x1 xloop: lda #$a0 ldy x0 ; screenRAM[x] = 0xA0 sta (screenptr), y ldy x1 ; screenRAM[39-x] = 0xA0 sta (screenptr), y clc lda #160 ; line slope adc yf sta yf bcc no_add ; advance screen ptr by 40 clc lda screenptr adc #40 sta screenptr lda screenptr+1 adc #0 sta screenptr+1 no_add: inc x0 dec x1 bpl xloop inf: jmp inf }

Avec 82 octets, c'est encore assez lourd. Un problème évident est le calcul d'adresse 16 bits. Définissez la valeur screenptr pour l' screenptr indirecte:

  ; set screenptr = $0400 lda #<$0400 sta screenptr+0 lda #>$0400 sta screenptr+1

Nous traduisons screenptr à la ligne suivante en ajoutant 40:

  ; advance screen ptr by 40 clc lda screenptr adc #40 sta screenptr lda screenptr+1 adc #0 sta screenptr+1

Bien sûr, ce code peut être optimisé, mais qu'en est-il si vous vous débarrassez des adresses 16 bits? Voyons comment faire.

Astuce 1. Défilement!


Au lieu de construire une ligne dans la RAM à l'écran, nous ne dessinons que dans la dernière ligne d'écran Y = 24 et faisons défiler l'écran vers le haut, en appelant la fonction de défilement ROM avec JSR $E8EA !

Voici comment xloop est optimisé:

  lda #0 sta x0 lda #39 sta x1 xloop: lda #$a0 ldx x0 ; hardcoded absolute address to last screen line sta $0400 + 24*40, x ldx x1 sta $0400 + 24*40, x adc yf sta yf bcc no_scroll ; scroll screen up! jsr $e8ea no_scroll: inc x0 dec x1 bpl xloop

Voici à quoi ressemble le rendu:



C'est l'un de mes trucs préférés dans ce programme. Presque tous les participants au concours l'ont découvert indépendamment.

Astuce 2. Code auto-modifiant


Le code de stockage des valeurs de pixels se termine comme suit:

  ldx x1 ; hardcoded absolute address to last screen line sta $0400 + 24*40, x ldx x0 sta $0400 + 24*40, x inc x0 dec x1

Ceci est codé dans la séquence suivante de 14 octets:

 0803: A6 22 LDX $22 0805: 9D C0 07 STA $07C0,X 0808: A6 20 LDX $20 080A: 9D C0 07 STA $07C0,X 080D: E6 22 INC $22 080F: C6 20 DEC $20

En utilisant du code auto-modifiable (SMC), vous pouvez écrire ceci de manière plus compacte:

  ldx x1 sta $0400 + 24*40, x addr0: sta $0400 + 24*40 ; advance the second x-coord with SMC inc addr0+1 dec x1

... qui est codé à 13 octets:

 0803: A6 22 LDX $22 0805: 9D C0 07 STA $07C0,X 0808: 8D C0 07 STA $07C0 080B: EE 09 08 INC $0809 080E: C6 22 DEC $22

Astuce 3. État de fonctionnement «sous tension»


Il a été jugé normal dans la compétition de faire des hypothèses folles sur l'environnement de travail. Par exemple, le dessin au trait est la première chose qui commence après la mise sous tension du C64, et il n'y a aucune exigence pour une sortie propre à la ligne de commande BASIC. Par conséquent, tout ce que vous trouvez dans l'environnement initial en entrant dans le PRG peut et doit être utilisé à votre avantage:

  • Les registres A, X, Y sont pris comme des zéros
  • Tous les drapeaux CPU effacés
  • Contenu Zeropage (adresse $00 $ff - $ff )

De la même manière, lorsque vous appelez certaines procédures KERNAL ROM, vous pouvez profiter pleinement de tous les effets secondaires: indicateurs CPU renvoyés, valeurs de zéros temporaires, etc.

Après les premières optimisations, recherchons quelque chose d'intéressant dans la mémoire de la machine:



Zeropage contient des valeurs utiles pour nos besoins:

  • $d5 : 39 / $ 27 == longueur de ligne - 1
  • $22 : 64/40 $ == valeur initiale pour le compteur de pente de ligne

Cela permettra d'économiser quelques octets lors de l'initialisation. Par exemple:

 !let x0 = $20 lda #39 ; 0801: A9 27 LDA #$27 sta x0 ; 0803: 85 20 STA $20 xloop: dec x0 ; 0805: C6 20 DEC $20 bpl xloop ; 0807: 10 FC BPL $0805

Puisque $d5 contient la valeur 39, vous pouvez l'indiquer au compteur x0 , en vous débarrassant de la paire LDA / STA:

 !let x0 = $d5 ; nothing here! xloop: dec x0 ; 0801: C6 D5 DEC $D5 bpl xloop ; 0803: 10 FC BPL $0801

Philip, le vainqueur du concours, pousse les choses à l'extrême dans son code . Rappelez l'adresse du dernier caractère de la chaîne $07C0 (== $0400+24*40 ). Cette valeur n'est pas présente dans la page zéro lors de l'initialisation. Cependant, comme effet secondaire de la façon dont la routine de défilement à partir de la ROM utilise des valeurs de zéros temporaires, les adresses $D1-$D2 à la sortie de la fonction contiendront la valeur $07C0 . Par conséquent, pour stocker un pixel, au lieu de STA $07C0,x vous pouvez utiliser l'adressage d'index indirect plus court STA ($D1),y pour un octet.

Astuce 4. Optimisation du téléchargement


Un binaire C64 PRG typique contient les éléments suivants:

  • 2 premiers octets: adresse de téléchargement (généralement $0801 )
  • 12 octets de la séquence de démarrage BASIC

La séquence de démarrage principale ressemble à ceci (adresse $801-$80C ):

 0801: 0B 08 0A 00 9E 32 30 36 31 00 00 00 080D: 8D 20 D0 STA $D020

Sans entrer dans les détails de la disposition de la mémoire tokenisée BASIC , cette séquence correspond plus ou moins à '10 SYS 2061 '. L'adresse 2061 ( $080D ) est l'endroit où notre programme de code machine réel s'exécute lorsque l'interpréteur BASIC exécute la commande SYS.

Il semble juste que 14 octets, c'est trop. Philip, Matlev et Geir ont utilisé plusieurs astuces pour se débarrasser complètement de la séquence principale. Cela nécessite de charger le PRG avec LOAD"*",8,1 , car LOAD"*",8 ignore l'adresse de chargement du PRG (deux premiers octets) et se charge toujours à $0801 .



Deux méthodes ont été utilisées ici:

  • Astuce de pile
  • Astuce de réinitialisation à chaud BASIC

Astuce de pile


L'astuce consiste à faire $01F8 dans la pile du processeur à $01F8 valeur qui indique notre point d'entrée souhaité. Cela se fait en créant un PRG qui commence par un pointeur 16 bits sur notre code et en chargeant le PRG à $01F8 :

  * = $01F8 !word scroll - 1 ; overwrite stack scroll: jsr $E8EA

Dès que le chargeur BASIC (voir le code après le démontage ) a fini de charger et veut retourner à l'objet appelant en utilisant RTS , il revient directement à notre PRG.

Astuce de réinitialisation à chaud BASIC


C'est un peu plus facile à expliquer simplement en regardant le PRG après le démontage.

 02E6: 20 EA E8 JSR $E8EA 02E9: A4 D5 LDY $D5 02EB: A9 A0 LDA #$A0 02ED: 99 20 D0 STA $D020,Y 02F0: 91 D1 STA ($D1),Y 02F2: 9D B5 07 STA $07B5,X 02F5: E6 D6 INC $D6 02F7: 65 90 ADC $90 02F9: 85 90 STA $90 02FB: C6 D5 DEC $D5 02FD: 30 FE BMI $02FD 02FF: 90 E7 BCC $02E8 0301: 4C E6 02 JMP $02E6

Faites attention à la dernière ligne ( JMP $02E6 ). L'instruction JMP commence à $0301 avec une adresse de saut de $0302-$0303 .

Lorsque ce code est chargé en mémoire à partir de l'adresse $02E6 , la valeur $02E6 écrite aux adresses $0302-$0303 . Eh bien, cet emplacement a une signification particulière: il contient un pointeur sur le «cycle d'attente BASIC» (voir la carte mémoire C64 pour plus de détails). Le téléchargement de PRG l'écrase avec $02E6 et par conséquent, lorsque l'interpréteur BASIC après une réinitialisation à chaud essaie de passer à la boucle d'attente, il n'entre jamais dans cette boucle, mais entre dans le programme de rendu!

Autres astuces avec le lancement de BASIC


Petri a découvert une autre astuce de lancement BASIC qui vous permet d'entrer vos propres constantes dans zeropage. Dans cette méthode, vous créez manuellement votre propre séquence de démarrage BASIC à jetons et codez les constantes dans les numéros de ligne du programme BASIC. À l'entrée, les numéros de ligne BASIC, ahem, c'est-à-dire que vos constantes seront stockées dans les adresses $39-$3A . Très intelligent!

Astuce 5. Flux de contrôle personnalisé


Voici une version légèrement simplifiée de la boucle x qui n'imprime qu'une seule ligne puis arrête l'exécution:

  lda #39 sta x1 xloop: lda #$a0 ldx x1 sta $0400 + 24*40, x adc yf sta yf bcc no_scroll ; scroll screen up! jsr $e8ea no_scroll: dec x1 bpl xloop ; intentionally halt at the end inf: jmp inf

Mais il y a une erreur. Lorsque nous avons dessiné le dernier pixel, nous ne pouvons plus faire défiler l'écran. Ainsi, des branches supplémentaires sont nécessaires pour arrêter le défilement après l'enregistrement du dernier pixel:

  lda #39 sta x1 xloop: lda #$a0 ldx x1 sta $0400 + 24*40, x dec x1 ; skip scrolling if last pixel bmi done adc yf sta yf bcc no_scroll ; scroll screen up! jsr $e8ea no_scroll: jmp xloop done: ; intentionally halt at the end inf: jmp inf

Le flux de contrôle est très similaire à ce que le compilateur C produira à partir d'un programme structuré. Le code pour ignorer le dernier défilement introduit une nouvelle instruction JMP abs qui prend 3 octets. Les sauts conditionnels ne font que deux octets, car ils codent les adresses de saut à l'aide d'un opérande relatif de 8 bits avec adressage direct.

JMP pour «ignorer le dernier défilement» peut être évité en déplaçant l'appel de défilement vers le haut de la boucle et en modifiant légèrement la structure du flux de contrôle. Voici comment Philip l'a implémenté:

  lda #39 sta x1 scroll: jsr $e8ea xloop: lda #$a0 ldx x1 sta $0400 + 24*40, x adc yf sta yf dec x1 ; doesn't set carry! inf: bmi inf ; hang here if last pixel! bcc xloop ; next pixel if no scroll bcs scroll ; scroll up and continue

Cela élimine complètement un JMP de trois octets et convertit l'autre JMP en une branche conditionnelle de deux octets, économisant un total de 4 octets.

Astuce 6. Lignes avec compression de bits


Certains éléments n'utilisent pas le compteur de pente de ligne, mais compressent plutôt les bits en une constante de 8 bits. Un tel conditionnement est basé sur le fait que la position du pixel le long de la ligne correspond à un motif répétitif de 8 pixels:

 int mask = 0xB6; // 10110110 uint8_t* dst = screenRAM; for (int x = 0; x < 40; x++) { dst[x] = 0xA0; if (mask & (1 << (x&7))) { dst += 40; // go down a row } }

Cela se traduit par un assembleur assez compact. Cependant, les options de compteur d'inclinaison sont généralement encore plus petites.

Gagnant


Voici le programme gagnant de 34 octets de Philip. La plupart des astuces ci-dessus fonctionnent bien dans son code:

 ov = $22 ; == $40, initial value for the overflow counter ct = $D5 ; == $27 / 39, number of passes. Decrementing, finished at -1 lp = $D1 ; == $07C0, pointer to bottom line. Set by the kernal scroller ; Overwrite the return address of the kernal loader on the stack ; with a pointer to our own code * = $01F8 .word scroll - 1 scroll: jsr $E8EA ; Kernal scroll up, also sets lp pointer to $07C0 loop: ldy ct ; Load the decrementing counter into Y (39 > -1) lda #$A0 ; Load the PETSCII block / black col / ov step value sta $D020, y ; On the last two passes, sets the background black p1: sta $07C0 ; Draw first block (left > right line) sta (lp), y ; Draw second block (right > left line) inc p1 + 1 ; Increment pointer for the left > right line adc ov ; Add step value $A0 to ov sta ov dec ct ; Decrement the Y counter bmi * ; If it goes negative, we're finished bcc loop ; Repeat. If ov didn't overflow, don't scroll bcs scroll ; Repeat. If ov overflowed, scroll

Mais pourquoi s'attarder sur 34 octets?


Dès la fin du concours, tout le monde a partagé son code et ses notes - et une série de discussions animées ont eu lieu sur la façon de l'améliorer davantage. Après la date limite, plusieurs autres options ont été présentées:


Soyez sûr de regarder - il y a plusieurs vraies perles.


Merci d'avoir lu. Et un merci spécial à Matlev, Phil, Geir, Petri, Jamie, Ian et David pour leur participation (j'espère que personne ne m'a manqué - c'était vraiment difficile de suivre toutes les mentions sur Twitter!)

PS Petri a appelé mon concours "annuel", donc, euh, je vous verrai probablement l'année prochaine.

Source: https://habr.com/ru/post/fr464377/

More articles:


All Articles