Artikel ini mencantumkan beberapa trik yang digunakan peserta dalam
kontes pemrograman Commodore 64 kecil saya. Aturan-aturan kontes itu sederhana: buat file executable C64 (PRG) yang menggambar dua baris untuk membentuk gambar di bawah ini. Yang file-nya berukuran lebih kecil dimenangkan.
Entri kompetisi diterbitkan dalam tweet terbuka dan dalam pesan pribadi yang hanya berisi byte dari file PRG dan hash MD5.
Daftar peserta dengan tautan ke kode sumber:
(Jika saya merindukan seseorang, tolong beri tahu saya, saya akan memperbarui daftar).
Sisa artikel ini dikhususkan untuk beberapa trik assembler yang digunakan dalam kompetisi.
Dasar-dasarnya
Grafik C64 bekerja secara default dalam mode penyandian karakter 40x25. Framebuffer dalam RAM dibagi menjadi dua array:
$0400 (RAM Layar, 40x25 byte)
$d800 (RAM Warna, 40x25 byte)
Untuk mengatur karakter, Anda menyimpan byte ke RAM pada layar, pada
$0400 (misalnya,
$0400+y*40+x ). RAM warna diinisialisasi oleh biru muda secara default (warna 14): ini adalah warna yang kami gunakan untuk garis, yaitu, RAM warna dapat dibiarkan tanpa sentuhan.
Anda mengontrol warna perbatasan dan latar belakang menggunakan register I / O memori dalam
$d020 (perbatasan) dan
$d021 (latar belakang).
Menggambar dua garis cukup mudah jika Anda memprogram langsung kemiringan garis tetap. Berikut ini adalah implementasi C yang menggambar garis dan menyiram isi layar ke stdout (
malloc() digunakan untuk membuat kode berfungsi pada 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); }
Kode layar di atas adalah
$20 (kosong) dan
$a0 (diisi blok 8 × 8). Jika Anda menjalankan, Anda akan melihat gambar ASCII dengan dua baris:
## .................................... ##
.. # ........................................ # ..
... ## .............................. ## ...
..... # ............................ # .....
...... ## ........................ ## ......
........ ## .................... ## ........
.......... # .................. # ..........
........... ## .............. ## ...........
............. # ............ # .............
.............. ## ........ ## ..............
................ ## .... ## ................
.................. # .. # ..................
................... ## ...................
.................. # .. # ..................
................ ## .... ## ................
.............. ## ........ ## ..............
............. # ............ # .............
........... ## .............. ## ...........
.......... # .................. # ..........
........ ## .................... ## ........
...... ## ........................ ## ......
..... # ............................ # .....
... ## .............................. ## ...
.. # ........................................ # ..
## .................................... ##
Hal yang sama diterapkan secara sepele dalam assembler:
!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 }
Ternyata PRG berukuran cukup besar 286 bytes.
Sebelum terjun ke optimasi, kami melakukan beberapa pengamatan.
Pertama, kami bekerja pada C64 dengan rutin ROM di tempat. Ada banyak rutinitas yang dapat bermanfaat. Misalnya, membersihkan layar dengan
JSR $E544 .
Kedua, perhitungan alamat pada prosesor 8-bit seperti 6502 bisa rumit dan memakan banyak byte. Prosesor ini juga tidak memiliki pengali, jadi perhitungan seperti
y*40+i biasanya mencakup sekelompok shift logis atau tabel pencarian yang juga memakan byte. Untuk menghindari mengalikan dengan 40, yang terbaik adalah memajukan kursor layar secara bertahap:
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; } }
Kami terus menambahkan kemiringan garis ke penghitung tetap
yf , dan ketika penambahan 8-bit menetapkan flag carry, tambahkan 40.
Berikut ini adalah pendekatan assembler tambahan:
!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 }
Dengan 82 byte, itu masih lumayan besar. Satu masalah yang jelas adalah perhitungan alamat 16-bit. Tetapkan nilai
screenptr untuk
screenptr tidak langsung:
; set screenptr = $0400 lda #<$0400 sta screenptr+0 lda #>$0400 sta screenptr+1
Kami menerjemahkan
screenptr ke baris berikutnya dengan menambahkan 40:
; advance screen ptr by 40 clc lda screenptr adc #40 sta screenptr lda screenptr+1 adc #0 sta screenptr+1
Tentu saja, kode ini dapat dioptimalkan, tetapi bagaimana jika Anda menyingkirkan alamat 16-bit sama sekali? Mari kita lihat bagaimana melakukannya.
Trik 1. Menggulir!
Alih-alih membangun garis pada RAM di layar, kami menggambar hanya di baris layar terakhir Y = 24 dan gulirkan seluruh layar, memanggil fungsi gulir ROM dengan
JSR $E8EA !
Inilah cara xloop dioptimalkan:
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
Beginilah tampilan rendering:
Ini adalah salah satu trik favorit saya dalam program ini. Hampir semua kontestan menemukannya sendiri.
Trik 2. Kode Modifikasi-Sendiri
Kode untuk menyimpan nilai piksel berakhir seperti ini:
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
Ini dikodekan dalam urutan 14 byte berikut:
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
Menggunakan kode modifikasi sendiri (SMC), Anda dapat menulis ini dengan lebih kompak:
ldx x1 sta $0400 + 24*40, x addr0: sta $0400 + 24*40 ; advance the second x-coord with SMC inc addr0+1 dec x1
... yang dikodekan pada 13 byte:
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. Status operasi 'power on'
Itu dianggap normal dalam kompetisi untuk membuat asumsi liar tentang lingkungan kerja. Misalnya, bahwa gambar garis adalah hal pertama yang dimulai setelah menyalakan daya C64, dan tidak ada persyaratan untuk output bersih kembali ke baris perintah BASIC. Karena itu, semua yang Anda temukan di lingkungan awal ketika memasuki PRG dapat dan harus digunakan untuk keuntungan Anda:
- Register A, X, Y diambil sebagai nol
- Semua flag CPU dihapus
- Konten Zeropage (alamat
$00 - $ff )
Dengan cara yang sama, ketika memanggil beberapa prosedur ROM KERNAL, Anda dapat mengambil keuntungan penuh dari segala efek samping: pengembalian flag CPU, nilai zeropage sementara, dll.
Setelah optimasi pertama, mari kita cari sesuatu yang menarik dalam memori mesin:
Zeropage memang mengandung beberapa nilai berguna untuk tujuan kita:
$d5 : 39 / $ 27 == panjang garis - 1
$22 : 64 / $ 40 == nilai awal untuk penghitung kemiringan garis
Ini akan menghemat beberapa byte selama inisialisasi. Sebagai contoh:
!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
Karena
$d5 berisi nilai 39, Anda dapat mengindikasikannya ke penghitung
x0 , menyingkirkan pasangan LDA / STA:
!let x0 = $d5 ; nothing here! xloop: dec x0 ; 0801: C6 D5 DEC $D5 bpl xloop ; 0803: 10 FC BPL $0801
Philip, pemenang kontes, mengambil ekstrem dalam
kode-nya . Ingat alamat karakter terakhir dari string
$07C0 (==
$0400+24*40 ). Nilai ini tidak ada di zeropage selama inisialisasi. Namun, sebagai efek samping dari bagaimana rutin gulir dari ROM menggunakan nilai zeropage sementara, alamat
$D1-$D2 pada output fungsi akan berisi nilai
$07C0 . Oleh karena itu, untuk menyimpan piksel, alih-alih
STA $07C0,x Anda dapat menggunakan
STA ($D1),y pengalamatan indeks tidak langsung yang lebih pendek
STA ($D1),y untuk satu byte.
Trik 4. Unduh Optimasi
Biner C64 PRG tipikal berisi yang berikut ini:
- 2 byte pertama: alamat pengunduhan (biasanya
$0801 )
- 12 byte dari urutan boot BASIC
Urutan boot utama terlihat seperti ini (alamat
$801-$80C ):
0801: 0B 08 0A 00 9E 32 30 36 31 00 00 00 080D: 8D 20 D0 STA $D020
Tanpa masuk ke detail tentang
tata letak memori tokenized BASIC , urutan ini kurang lebih sesuai dengan '10 SYS 2061 '. Alamat
2061 (
$080D ) adalah tempat program kode mesin kami yang sebenarnya berjalan ketika penerjemah BASIC mengeksekusi perintah SYS.
Sepertinya 14 byte terlalu banyak. Philip, Matlev dan Geir menggunakan beberapa trik rumit untuk sepenuhnya menghilangkan urutan utama. Ini membutuhkan pemuatan PRG dengan
LOAD"*",8,1 , karena
LOAD"*",8 mengabaikan alamat pemuatan PRG (dua byte pertama) dan selalu memuat pada
$0801 .
Dua metode digunakan di sini:
- Trik tumpukan
- Trick Reset Awal BASIC
Trik tumpukan
Caranya adalah dengan memasukkan ke dalam tumpukan prosesor pada
$01F8 nilai yang menunjukkan titik masuk yang diinginkan. Ini dilakukan dengan membuat PRG yang dimulai dengan pointer 16-bit ke kode kami dan memuat PRG pada
$01F8 :
* = $01F8 !word scroll - 1 ; overwrite stack scroll: jsr $E8EA
Segera setelah pemuat BASIC (lihat
kode setelah pembongkaran ) selesai memuat dan ingin kembali ke pemanggil menggunakan
RTS , ia kembali langsung ke PRG kami.
Trick Reset Awal BASIC
Ini sedikit lebih mudah untuk dijelaskan hanya dengan melihat PRG setelah pembongkaran.
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
Perhatikan baris terakhir (
JMP $02E6 ). Instruksi JMP mulai dari
$0301 dengan alamat lompatan
$0302-$0303 .
Ketika kode ini dimuat ke dalam memori mulai dari alamat
$02E6 , nilai
$02E6 ditulis ke alamat
$0302-$0303 . Nah, lokasi ini memiliki arti khusus: ini berisi penunjuk ke "siklus menunggu BASIC" (lihat
kartu memori C64 untuk lebih jelasnya). Mengunduh PRG menimpanya dengan
$02E6 dan oleh karena itu, ketika penerjemah BASIC setelah reset hangat mencoba untuk pergi ke loop tunggu, itu tidak pernah memasuki loop ini, tetapi sebaliknya masuk ke dalam program rendering!
Trik lain dengan peluncuran BASIC
Petri menemukan
trik peluncuran BASIC lain yang memungkinkan Anda memasukkan konstanta Anda sendiri di zeropage. Dalam metode ini, Anda secara manual membuat urutan awal BASIC tokenized Anda sendiri dan menyandikan konstanta dalam nomor baris dari program BASIC. Pada input, nomor garis BASIC, ahem, yaitu, konstanta Anda akan disimpan di alamat
$39-$3A . Sangat pintar!
Trik 5. Alur kontrol kustom
Ini adalah versi x-loop yang sedikit disederhanakan yang hanya mencetak satu baris dan kemudian menghentikan eksekusi:
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
Namun ada kesalahan. Ketika kami menggambar piksel terakhir, kami TIDAK BISA menggulir layar lagi. Dengan demikian, cabang tambahan diperlukan untuk berhenti menggulir setelah merekam piksel terakhir:
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
Aliran kontrol sangat mirip dengan apa yang akan dihasilkan oleh kompiler C dari program terstruktur. Kode untuk melewati scroll terakhir memperkenalkan instruksi
JMP abs baru yang membutuhkan 3 byte. Panjang kondisional hanya dua byte, karena mereka menyandikan alamat lompat menggunakan operan 8-bit relatif dengan pengalamatan langsung.
JMP untuk "melewati gulir terakhir" dapat dihindari dengan menggerakkan panggilan gulir ke atas loop dan sedikit mengubah struktur aliran kontrol. Inilah cara Philip menerapkannya:
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
Ini benar-benar menghilangkan satu JMP tiga byte dan mengubah JMP yang lain menjadi cabang bersyarat dua-byte, menghemat total 4 byte.
Trik 6. Garis dengan kompresi bit
Beberapa elemen tidak menggunakan penghitung kemiringan garis, melainkan mengompres bit menjadi konstanta 8-bit. Pengemasan tersebut didasarkan pada fakta bahwa posisi piksel di sepanjang garis sesuai dengan pola 8-piksel yang berulang:
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 } }
Ini diterjemahkan menjadi assembler yang cukup kompak. Namun, opsi penghitung kemiringan biasanya bahkan lebih kecil.
Pemenang
Ini
adalah program pemenang 34 byte kontes dari Philip. Sebagian besar trik di atas berfungsi dengan baik dalam kodenya:
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
Tapi mengapa tinggal 34 byte?
Segera setelah kontes selesai, semua orang membagikan kode dan catatan mereka - dan serangkaian diskusi berlangsung tentang bagaimana memperbaikinya lebih lanjut. Setelah batas waktu, beberapa opsi lain disajikan:
Pastikan untuk melihat - ada beberapa mutiara asli.
Terima kasih sudah membaca. Dan terima kasih khusus kepada Matlev, Phil, Geir, Petri, Jamie, Ian dan David untuk partisipasi (saya harap saya tidak kehilangan siapa pun - sangat sulit untuk melacak semua menyebutkan di Twitter!)
PS Petri menyebut kontes saya "tahunan," jadi, uh, mungkin sampai jumpa tahun depan.