Тук са описани някои специфични трикове, използвани от участниците в моя малък конкурс по програмиране за Commodore 64, базиран на процесора 6502. Правилата на конкурса са съвсем прости: да се създаде изпълним C64 (PRG) файл, който чертае двете линии, за да се получи изображението показано по-долу. Побеждава кодът с най-малък размер.
Решенията бяха публикувани във вид на отворени туитове, както и като лични съобщения, които съдържат единствено байтовете на PRG файла и MD5 хеша.
Победител в този конкурс бе Филип Херън, който представи код с дължина едва 24 байта. Всички участници прилагат много интересни трикове на асемблер. Нека да разгледаме най-интересните от тях.
Основите
Графиката на персоналния компютър C64 по подразбиране работи в режим на кодиране на символите с резолюция 40х25. Екранният буфер в оперативната памет е разделен на два масива:
- $0400 (Screen RAM, 40×25 байта)
- $d800 (Color RAM, 40×25 байта)
За да се появи символ на екрана на компютъра, трябва да бъде записан един байт в екранната памет (например $0400+y*40+x). Color RAM по подразбиране се инициализира със светлосин цвят (цвят номер 14). Именно този цвят ще използваме за изобразяването на тези линии – тоест, RAM паметта за цветността може да не се използва и променя.
Цветовете и фона могат да се управляват с помощта на дублираните в паметта входно-изходни регистри – клетката $d020 за линиите и $d021 за фона.
Да се нарисуват две прави линии е лесно, ако директно в програмата бъде въведен наклона на дадена фиксирана права. Ето една реализация на програмния език С, която изчертава прави линии и накрая прехвърля информацията от екрана в stdout. Използва се malloc(), за да може кодът да работи на 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);
}
Използват се символите $20 (спейс) и $a0 (запълнено квадратче). Ако бъде стартирана ще се види нещо подобно на следното ASCII изображение:
##....................................## ..#..................................#.. ...##..............................##... .....#............................#..... ......##........................##...... ........##....................##........ ..........#..................#.......... ...........##..............##........... .............#............#............. ..............##........##.............. ................##....##................ ..................#..#.................. ...................##................... ..................#..#.................. ................##....##................ ..............##........##.............. .............#............#............. ...........##..............##........... ..........#..................#.......... ........##....................##........ ......##........................##...... .....#............................#..... ...##..............................##... ..#..................................#.. ##....................................##
Същото се реализира твърде елементарно на асемблер за процесора 6502:
!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
}
Получава се PRG файл с немалкия размер от 286 байта.
Преди да започнем оптимизациите, да анализираме с какво разполагаме.
Първо, работим с C64, в който са записани маса подпрограми в постоянната памет. Например, изчистването на екрана с помощта на JSR $E544.
Второ, изчисляването на адресите за един 8-битов процесор от този тип може да е тромаво и при този процес да бъдат изхарчени много байтове. В този процесор няма умножение и изчисленията от типа y*40+i обикновено включват или редица логически премествания, или таблица на съответствията, която също използва много байтове. За да избегнем умножението на 40 е по-добре да придвижваме курсора инкрементално:
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;
}
}
Продължаваме по същия начин да добавяме наклона на правата линия към брояча yf, а когато 8-битовото сумиране вдигне флага за пренос, добавяме 40.
Ето го инкременталния подход и на асемблер:
!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
}
Това са немалките 82 байта и кодът все още е твърде голям. Една от очевидните проблеми е 16-битовото изчисляване на адресите. Ще използваме screenptr с косвено адресиране:
; set screenptr = $0400 lda #<$0400 sta screenptr+0 lda #>$0400 sta screenptr+1
Да прехвърлим screenptr на следващия ред на екрана чрез добавянето на 40:
; advance screen ptr by 40 clc lda screenptr adc #40 sta screenptr lda screenptr+1 adc #0 sta screenptr+1
Разбира се, и този код може да бъде оптимизиран, но какво ли ще стане, ако напълно се откажем от използването на 16-битови адреси? Да погледнем по-подробно.
Трик №1: използване на скрол
Вместо да изграждаме правата линия в екранната памет, можем да поставяме необходимите точки (в нашия случай символи) в 24-я ред на екрана и да превъртим всичко с един ред нагоре, извиквайки подпрограмата за скрол от ROM-а чрез JSR $E8EA!
Ето как се оптимизира чрез xloop:
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
Ето така изглежда рендирането:
Това е един от моите любими трикове. Той бе самостоятелно открит от почти всички участници в конкурса.
Трик №2: самостоятелно модифициращ се код
Кодът за запис значенията на пикселите завършва примерно по следния начин:
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
Това се кодира като следната последователност от 14 байта:
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
С помощта на самостоятелно модифициращ се код (SMC) това може да бъде записано по-компактно:
ldx x1 sta $0400 + 24*40, x addr0: sta $0400 + 24*40 ; advance the second x-coord with SMC inc addr0+1 dec x1
И в крайна сметка се получават 13 байта:
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
Трик №3: използване на „power on“
Всички забелязаха, че в конкурса няма изискване към завръщане към командния ред на BASIC интерпретатора. Ето защо, всичко, което може да бъде намерено в компютърната памет при влизането в PRG може да се използва в свой интерес.
Например, при стартирането на нова програма:
- Регистрите A, X, Y са равни на 0
- Всички флагове на процесора са смъкнати
- Инициализирана е нулевата страница на адресното пространство на компютъра
Има интересни значения в нулевата страница (zeropage), която се намира в адресното пространство $00-$FF.
Съвсем по същия начин при извикване на подпрограми от KERNAL ROM могат да се използват всички странични ефекти: флаговете на CPU, временните значения на клетките в zeropage и т.н.
След направените дотук оптимизации нека потърсим нещо интересно в „нулевата памет“.
Zeropage наистина съдържа клетки с полезни за нашата програма значения:
- $d5: 39/$27 == дължината на линията-1
- $22: 64/$40 == началното значение за брояча на наклона на правата линия
Това ще ни икономиса няколко байта при инициализацията. Например:
!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
Но тъй като $d5 съдържа числото 39, можете да го използвате за указване на брояча h0, като по този начин се освобождаване от двойка LDA/STA:
!let x0 = $d5 ; nothing here! xloop: dec x0 ; 0801: C6 D5 DEC $D5 bpl xloop ; 0803: 10 FC BPL $0801
Победителят в конкурса Филип в своя код довежда този подход до крайност. Да си спомним адреса на последния символ на реда $07C0 (==$0400+24*40). Това значение го няма в zeropage при инициализацията на компютъра. Но може да се използва страничния ефект от стартирането на подпрограмата за скрол на страницата, която използва някои клетки от нулевата страница. Те се намират на адреси $D1-$D2 и след приключване работата на подпрограмата за превъртане на екрана, тези клетки съдържат значението $07C0. Ето защо за записа на един пиксел, вместо командата STA $07C0,x може да се използва с един байт по-късата команда STA ($D1),Y, в която се използва индексно косвено адресиране.
Оптимизиране на зареждането
Типичният двоичен PRG файл за C64 съдържа следното:
- Първите два байта са адресът, на който трябва да бъде заредена програмата (обикновено $0801)
- 12 байта за зареждането на BASIC
На самия адрес на вече заредената програма можем да видим следните байтове:
0801: 0B 08 0A 00 9E 32 30 36 31 00 00 00 080D: 8D 20 D0 STA $D020
Без да навлизаме в подробности за работата на тази версия на BASIC, можем да кажем, че първите байтове съответстват на BASIC инструкцията ’10 SYS 2061′. В този случай адресът 2061 или $080D е мястото, от което фактически се стартира нашата бинарна програма след като интерпретаторът изпълни командата SYS.
На някои от участниците в този конкурс се стори, че 14 байта са твърде много за подобни цели. Използвани бяха няколко хитри трика, за да се избегне това разхищение. Всичко това налага зареждането на PRG файла да стане чрез LOAD“*“,8,1. По този начин се игнорира адреса на зареждане (първите два байта) и програмата винаги отива на адрес $0801.
Следва използването на трик със стека и „топлото инициализиране“ на BASIC интерпретатора
Трикът със стека
Хитрият момент тук е в процесорния стек да бъде поставено числото $01F8, което сочи адреса на входната точка на програмата. Необходимо е създаването на 16-битов указател към началото на нашия код и зареждането на PRG в $01F8:
* = $01F8 !word scroll - 1 ; overwrite stack scroll: jsr $E8EA
Веднага след като приключи зареждането на BASIC (виж кода след дизасемблирането) би трябвало изпълнението след RTS да продължи до извикалият подпрограмата обект, но вместо това управлението преминава към адреса на началото на нашата PRG.
Трикът с „топлото“ рестартиране на BASIC интерпретатора
Това е малко по-лесно за обясняване – достатъчно е са се погледне PRG след дизасемблирането:
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). Инструкцията JMP започва на адрес $301, а адресът на безусловния преход е записан в клетките $0302-$0303.
Използва се факта, че в клетките $0302-$0303 е записан указател на цикъла на изчакване на BASIC. Зареждането на PRG презаписва тези клетки и поставя в тях значението $02E6 и когато след топъл рестарт интерпретаторът на BASIC се опитва да влезе в своя цикъл на изчакване, управлението се прехвърля към началото на програмата за изчертаване на двете линии.
Победителят
Ето я и програмата на победителя в този конкурс, която е с дължина едва 34 байта. Написа я Филип и в нея са съчетани описаните дотук мръсни трикове за асемблера на процесора 6502:
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
Благодаря за четенето. Благодарности на младите програмисти за проявената изобретателност. Единия от тях – Петри каза, че всички искат конкурсът да бъде провеждан всяка година. Така че хм, явно пак ще се видим през 2020 година.
