Geekly articles weekly

Schmutzige Assembler-Hacks 6502

Dieser Artikel listet einige der Tricks auf, die Teilnehmer meines kleinen Commodore 64-Programmierwettbewerbs verwendet haben. Die Regeln des Wettbewerbs waren einfach: Erstellen Sie eine ausführbare C64-Datei (PRG), die zwei Linien zeichnet, um das folgende Bild zu erstellen. Derjenige, dessen Datei kleiner ist, hat gewonnen.


Wettbewerbsbeiträge wurden in offenen Tweets und in privaten Nachrichten veröffentlicht, die nur Bytes der PRG-Datei und einen MD5-Hash enthielten.

Teilnehmerliste mit Links zum Quellcode:


(Wenn ich jemanden vermisst habe, lass es mich wissen, ich werde die Liste aktualisieren).

Der Rest des Artikels ist einigen Assembler-Tricks gewidmet, die im Wettbewerb verwendet wurden.

Die Grundlagen


Grafik C64 funktioniert standardmäßig im 40x25-Zeichencodierungsmodus. Der Framebuffer im RAM ist in zwei Arrays unterteilt:

  • $0400 (Bildschirm-RAM, 40 x 25 Byte)
  • $d800 (Farb-RAM, 40 x 25 Byte)

Um ein Zeichen festzulegen, speichern Sie das Byte im Bildschirm-RAM bei $0400 (z. B. $0400+y*40+x ). Der Farb-RAM wird standardmäßig hellblau initialisiert (Farbe 14): Dies ist die Farbe, die wir für die Linien verwenden, dh der Farb-RAM kann ohne Berührung belassen werden.

Sie steuern die Farben des $d020 und des Hintergrunds mithilfe der Speicher-E / A-Register in $d020 (Rand) und $d021 (Hintergrund).

Das Zeichnen von zwei Linien ist ziemlich einfach, wenn Sie die Steigung einer festen Linie direkt programmieren. Hier ist eine C-Implementierung, die Linien zeichnet und den Inhalt des Bildschirms auf stdout leert ( malloc() wird verwendet, damit der Code auf einem PC funktioniert):

 #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); }

Die obigen Bildschirmcodes sind $20 (leer) und $a0 (gefüllter 8 × 8-Block). Wenn Sie ausführen, wird ein ASCII-Bild mit zwei Zeilen angezeigt:

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

Dasselbe ist in Assembler trivial implementiert:

 !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 }

Es stellt sich heraus, dass PRG eine ziemlich große Größe von 286 Bytes hat.

Bevor wir uns mit der Optimierung befassen, machen wir einige Beobachtungen.

Zunächst arbeiten wir an C64 mit den vorhandenen ROM-Routinen. Es gibt Unmengen von Routinen, die nützlich sein können. Zum Beispiel das Löschen des Bildschirms mit JSR $E544 .

Zweitens können Adressberechnungen auf einem 8-Bit-Prozessor wie 6502 umständlich sein und viele Bytes verbrauchen. Dieser Prozessor hat auch keinen Multiplikator, daher enthält eine Berechnung wie y*40+i normalerweise entweder eine Reihe logischer Verschiebungen oder eine Nachschlagetabelle, die auch Bytes frisst. Um ein Multiplizieren mit 40 zu vermeiden, bewegen Sie den Bildschirmcursor am besten schrittweise vorwärts:

  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; } }

Wir addieren weiterhin die Steigung der Linie zum festen Zähler yf , und wenn die 8-Bit-Addition das Übertragsflag setzt, addieren wir 40.

Hier ist ein inkrementeller Assembler-Ansatz:

 !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 }

Mit 82 Bytes ist es immer noch ziemlich heftig. Ein offensichtliches Problem sind 16-Bit-Adressberechnungen. screenptr Sie den screenptr Wert für die indirekte screenptr :

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

Wir übersetzen screenptr in die nächste Zeile, indem wir 40 hinzufügen:

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

Natürlich kann dieser Code optimiert werden, aber was ist, wenn Sie 16-Bit-Adressen überhaupt entfernen? Mal sehen, wie es geht.

Trick 1. Scrollen!


Anstatt eine Linie im Bildschirm-RAM zu erstellen, zeichnen wir nur in der letzten Bildschirmzeile Y = 24 und scrollen den gesamten Bildschirm nach oben, wobei wir die ROM-Scroll-Funktion mit JSR $E8EA !

So wird xloop optimiert:

  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

So sieht das Rendering aus:



Dies ist einer meiner Lieblingstricks in diesem Programm. Fast alle Teilnehmer fanden es alleine.

Trick 2. Selbstmodifizierender Code


Der Code zum Speichern von Pixelwerten endet wie folgt:

  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

Dies wird in der folgenden Folge von 14 Bytes codiert:

 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

Mit selbstmodifizierendem Code (SMC) können Sie dies kompakter schreiben:

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

... die mit 13 Bytes codiert ist:

 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

Trick 3. Betriebszustand 'Einschalten'


Es wurde im Wettbewerb als normal angesehen, wilde Annahmen über das Arbeitsumfeld zu treffen. Zum Beispiel, dass die Strichzeichnung das erste ist, was nach dem Einschalten des C64 beginnt, und es keine Anforderungen für eine saubere Ausgabe zurück in die BASIC-Befehlszeile gibt. Daher kann und sollte alles, was Sie in der Ausgangsumgebung beim Betreten der PRG finden, zu Ihrem Vorteil genutzt werden:

  • Die Register A, X, Y werden als Nullen genommen
  • Alle CPU-Flags gelöscht
  • Zeropage- Inhalt (Adressen $00 - $ff )

Auf die gleiche Weise können Sie beim Aufrufen einiger KERNAL ROM-Prozeduren alle Nebenwirkungen voll ausnutzen: zurückgegebene CPU-Flags, temporäre Nullseitenwerte usw.

Suchen wir nach den ersten Optimierungen nach etwas Interessantem im Maschinenspeicher:



Zeropage enthält einige nützliche Werte für unsere Zwecke:

  • $d5 : 39 / $ 27 == Zeilenlänge - 1
  • $22 : 64 / $ 40 == Anfangswert für den Liniensteigungszähler

Dadurch werden während der Initialisierung einige Bytes eingespart. Zum Beispiel:

 !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

Da $d5 den Wert 39 enthält, können Sie ihn dem Zähler x0 und das LDA / STA-Paar x0 :

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

Philip, der Gewinner des Wettbewerbs, bringt dies auf das Äußerste. $07C0 Sie die Adresse des letzten Zeichens der Zeichenfolge $07C0 (== $0400+24*40 ) auf. Dieser Wert ist während der Initialisierung nicht in Nullseiten vorhanden. Als Nebeneffekt der Verwendung temporärer Nullseitenwerte durch die Bildlaufroutine aus dem ROM enthalten die Adressen $D1-$D2 am Ausgang der Funktion den Wert $07C0 . Daher können Sie zum Speichern eines Pixels anstelle von STA $07C0,x die kürzere indirekte STA $07C0,x STA ($D1),y für ein Byte verwenden.

Trick 4. Download-Optimierung


Eine typische C64 PRG-Binärdatei enthält Folgendes:

  • Erste 2 Bytes: Download-Adresse (normalerweise $0801 )
  • 12 Bytes der BASIC-Startsequenz

Die Hauptstartsequenz sieht folgendermaßen aus (Adressen $801-$80C ):

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

Ohne auf Details des BASIC-Token-Speicherlayouts einzugehen , entspricht diese Sequenz mehr oder weniger '10 SYS 2061 '. In der Adresse 2061 ( $080D ) wird unser eigentliches Maschinencode-Programm ausgeführt, wenn der BASIC-Interpreter den SYS-Befehl ausführt.

Es scheint nur, dass 14 Bytes zu viel sind. Philip, Matlev und Geir verwendeten mehrere knifflige Tricks, um die Hauptsequenz vollständig loszuwerden. Dies erfordert das Laden des PRG mit LOAD"*",8,1 , da LOAD"*",8 die PRG-Ladeadresse (die ersten zwei Bytes) ignoriert und immer bei $0801 .



Hier wurden zwei Methoden angewendet:

  • Stapeltrick
  • BASIC Warm Reset Trick

Stapeltrick


Der Trick besteht darin, mit $01F8 Wert in den Prozessorstapel $01F8 , der unseren gewünschten Einstiegspunkt angibt. Dazu erstellen Sie eine PRG, die mit einem 16-Bit-Zeiger auf unseren Code beginnt, und laden die PRG bei $01F8 :

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

Sobald der BASIC-Loader (siehe Code nach der Demontage ) vollständig geladen ist und mit RTS zum Anrufer zurückkehren möchte, kehrt er direkt zu unserem PRG zurück.

BASIC Warm Reset Trick


Dies ist etwas einfacher zu erklären, indem Sie sich nach dem Zerlegen die PRG ansehen.

 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

JMP $02E6 auf die letzte Zeile ( JMP $02E6 ). Der JMP-Befehl beginnt bei $0301 mit einer Sprungadresse von $0302-$0303 .

Wenn dieser Code ab der Adresse $02E6 in den Speicher $02E6 , wird der Wert $02E6 die Adressen $0302-$0303 . Nun, dieser Ort hat eine besondere Bedeutung: Er enthält einen Zeiger auf den „BASIC-Wartezyklus“ (weitere Informationen finden Sie unter C64-Speicherkarte ). Das Herunterladen von PRG überschreibt es mit $02E6 . Wenn der BASIC-Interpreter nach einem Warm-Reset versucht, in die Warteschleife zu wechseln, tritt er nie in diese Schleife ein, sondern gelangt in das Rendering-Programm!

Weitere Tricks mit dem Start von BASIC


Petri hat einen weiteren BASIC-Starttrick entdeckt , mit dem Sie Ihre eigenen Konstanten in Nullseiten eingeben können. Bei dieser Methode erstellen Sie manuell Ihre eigene tokenisierte BASIC-Startsequenz und codieren die Konstanten in die Zeilennummern des BASIC-Programms. Bei der Eingabe werden die BASIC-Zeilennummern, ahem, dh Ihre Konstanten, in den Adressen $39-$3A gespeichert. Sehr schlau!

Trick 5. Benutzerdefinierter Kontrollfluss


Hier ist eine leicht vereinfachte Version von x-loop, die nur eine Zeile druckt und dann die Ausführung stoppt:

  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

Aber es gibt einen Fehler. Wenn wir das letzte Pixel gezeichnet haben, können wir den Bildschirm nicht mehr scrollen. Daher sind zusätzliche Verzweigungen erforderlich, um das Scrollen nach dem Aufzeichnen des letzten Pixels zu beenden:

  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

Der Kontrollfluss ist dem sehr ähnlich, was der C-Compiler aus einem strukturierten Programm erzeugt. Der Code zum Überspringen des letzten Bildlaufs führt einen neuen JMP abs Befehl ein, der 3 Bytes benötigt. Bedingte Sprünge sind nur zwei Bytes lang, da sie Sprungadressen unter Verwendung eines relativen 8-Bit-Operanden mit direkter Adressierung codieren.

JMP zum „Überspringen des letzten Bildlaufs“ kann vermieden werden, indem der Bildlaufaufruf an den oberen Rand der Schleife verschoben und die Kontrollflussstruktur geringfügig geändert wird. So hat Philip es implementiert:

  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

Dadurch wird ein Drei-Byte-JMP vollständig eliminiert und der andere JMP in einen bedingten Zwei-Byte-Zweig konvertiert, wodurch insgesamt 4 Byte eingespart werden.

Trick 6. Linien mit Bitkomprimierung


Einige Elemente verwenden nicht den Zeilenneigungszähler, sondern komprimieren die Bits in eine 8-Bit-Konstante. Eine solche Verpackung basiert auf der Tatsache, dass die Position des Pixels entlang der Linie einem sich wiederholenden 8-Pixel-Muster entspricht:

 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 } }

Dies führt zu einem ziemlich kompakten Assembler. Die Optionen für den Neigungszähler sind jedoch normalerweise noch kleiner.

Gewinner


Hier ist das 34-Byte-Wettbewerbsprogramm von Philip. Die meisten der oben genannten Tricks funktionieren gut in seinem 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

Aber warum bei 34 Bytes verweilen?


Sobald der Wettbewerb beendet war, teilten alle ihren Code und ihre Notizen mit - und es fanden eine Reihe lebhafter Diskussionen darüber statt, wie man ihn weiter verbessern kann. Nach Ablauf der Frist wurden mehrere weitere Optionen vorgestellt:


Achten Sie darauf - es gibt mehrere echte Perlen.


Danke fürs Lesen. Ein besonderer Dank geht an Matlev, Phil, Geir, Petri, Jamie, Ian und David für die Teilnahme (ich hoffe, ich habe niemanden vermisst - es war wirklich schwierig, alle Erwähnungen auf Twitter zu verfolgen!)

PS Petri nannte meinen Wettbewerb "jährlich", also bis zum nächsten Jahr.

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

More articles:


All Articles