Хабрахабр

[Перевод] Грязные хаки ассемблера 6502

В этой статье перечислены некоторые трюки, которые применяли участники моего маленького конкурса программирования Commodore 64. Правила конкурса были просты: создать исполняемый файл C64 (PRG), который рисует две линии, чтобы сформировать изображение ниже. Побеждал тот, чей файл меньше по размеру.

Конкурсные работы публиковались в открытых твитах и личными сообщениями, которые содержали только байты PRG-файла и хэш MD5.
Список участников со ссылками на исходный код:
(Если я кого-то пропустил, пожалуйста, дайте знать, я обновлю список).

Остальная часть статьи посвящена некоторым трюкам ассемблера, которые применялись в конкурсе.

ГрафикаC64 по умолчанию работает в режиме кодировки символов 40x25. Фреймбуфер в оперативной памяти разбивается на два массива:

  • $0400 (Screen RAM, 40x25 байт)
  • $d800 (Color RAM, 40x25 байт)

Чтобы установить символ, вы сохраняете байт в экраннное ОЗУ, в $0400 (например, $0400+y*40+x). Color RAM по умолчанию инициализируется светло-синим (цвет 14): именно этот цвет мы используем для линий, то есть ОЗУ цветности можно не трогать.

Вы управляете цветами границы и фона с помощью отображённых в памяти регистров ввода-вывода, в $d020 (граница) и $d021 (фон).

Вот реализация C, которая рисует линии и сбрасывает содержимое экрана в stdout (используется malloc(), чтобы код работал на PC): Нарисовать две линии довольно легко, если напрямую запрограммировать наклон фиксированной линии.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h> void dump(const uint8_t* screen) 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 (заполненный блок 8×8). Если запустить, вы увидите ASCII-картинку с двумя линиями:

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

То же самое тривиально реализуется в ассемблере:

!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 с заложенными подпрограммами ROM. Например, очистка экрана с помощью JSR $E544.

У этого процессора также нет множителя, поэтому вычисление вроде y*40+i обычно включает в себя либо кучу логических сдвигов, либо таблицу поиска, которая тоже съедает байты. Во-вторых, вычисления адресов на 8-битном процессоре типа 6502 могут быть громоздкими и съедать много байт. Чтобы избежать умножения на 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-битных адресов? Давайте посмотрим, как это сделать.
Вместо того, чтобы строить линию в экранном ОЗУ, рисуем только в последней экранной строке Y=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

Так выглядит рендеринг:

Его самостоятельно обнаружили почти все участники конкурса. Это один из моих любимых трюков в данной программе.

Код для хранения значений пикселей заканчивается примерно так:

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

В конкурсе считалось нормальным делать дикие предположения о рабочей среде. Например, что чертёж линий — первое, что запускается после включения питания C64, и нет никаких требований к чистому выходу обратно в командную строку BASIC. Поэтому всё, что вы найдёте в начальной среде при входе в PRG, можно и нужно использовать в своих интересах:

  • Регистры A, X, Y приняты за нули
  • Все флаги CPU очищены
  • Содержимое 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, вы можете указать его счётчику x0, избавившись от пары 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 при инициализации. Однако в качестве побочного эффекта того, как подпрограмма скроллинга из ROM использует временные значения zeropage, адреса $D1-$D2 на выходе из функции будут содержать значение $07C0. Поэтому для хранения пикселя вместо STA $07C0,x можно использовать на один байт более короткую косвенно-индексную адресацию STA ($D1),y.
Типичный двоичный файл C64 PRG содержит следующее:

  • Первые 2 байта: адрес загрузки (обычно $0801)
  • 12 байт последовательности загрузки BASIC

Основная последовательность загрузки выглядит так (адреса $801-$80C):

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

Не вдаваясь в подробности о токенизированной компоновке памяти BASIC, эта последовательность более или менее соответствует '10 SYS 2061'. Адрес 2061 ($080D) — то место, где запускается наша фактическая программа машинного кода, когда интерпретатор BASIC выполняет команду SYS.

Филип, Матлев и Гейр применили несколько хитрых трюков, чтобы полностью избавиться от основной последовательности. Просто кажется, что 14 байт — это слишком много. Это требует загрузки PRG с LOAD"*",8,1, поскольку LOAD"*",8 игнорирует адрес загрузки PRG (первые два байта) и всегда загружается в $0801.

Тут использовались два метода:

  • Трюк со стеком
  • Трюк с «тёплым» сбросом вектора BASIC

Трюк со стеком

Хитрость заключается в том, чтобы занести в процессорный стек на $01F8 значение, которое указывает на нашу желаемую точку входа. Это делается путём создания PRG, который начинается с 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 начинается с $0301 с адресом перехода в $0302-$0303.

Ну, у этого местоположения особое значение: оно содержит указатель на «цикл ожидания BASIC» (для более подробной информации см. Когда этот код загружается в память, начиная с адреса $02E6, значение $02E6 записывается в адреса $0302-$0303. Загрузка PRG перезаписывает его с помощью $02E6 и поэтому, когда интерпретатор BASIC после тёплого сброса пытается перейти к циклу ожидания, то никогда не входит в этот цикл, а вместо этого попадает в программу рендеринга! карту памяти C64).

Другие трюки с запуском BASIC

Петри обнаружил ещё один трюк запуска BASIC, который позволяет вводить собственные константы в zeropage. В этом методе вы вручную создаёте собственную токенизированную последовательность запуска BASIC и кодируете константы в номерах строк программы BASIC. На входе номера строк BASIC, кхм, то есть ваши константы будут храниться в адресах $39-$3A. Очень умно!
Вот несколько упрощённая версия x-loop, которая выводит только одну линию, а затем останавливает выполнение:

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

Но здесь есть ошибка. Когда мы нарисовали последний пиксель, то больше НЕЛЬЗЯ прокручивать экран. Таким образом, нужны дополнительные ветвления для прекращения прокрутки после записи последнего пикселя:

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

Поток управления очень похож на то, что выдаст компилятор C из структурированной программы. Код для пропуска последней прокрутки вводит новую инструкцию JMP abs, которая занимает 3 байта. Условные переходы всего по два байта, поскольку они кодируют адреса перехода с помощью относительного 8-битного операнда с непосредственной адресацией.

Вот как это реализовал Филип: JMP для «пропуска последней прокрутки» можно избежать, переместив вызов прокрутки вверх в верхнюю часть цикла и немного изменив структуру потока управления.

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

Это полностью устраняет один трёхбайтовый JMP и преобразует другой JMP в двухбайтовый условный переход, экономя в общей сложности 4 байта.
Некоторые элементы не используют счётчик наклона линии, а скорее сжимают биты в 8-битную константу. Такая упаковка базируется на том, что положение пикселя вдоль линии соответствует повторяющемуся 8-пиксельному шаблону:

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

Это транслируется в довольно компактный ассемблер. Однако варианты счётчика наклона, как правило, ещё меньше.

Победитель

Вот программа-победитель конкурса размером 34 байта от Филипа. В его коде хорошо сочетается большинство из вышеперечисленных трюков:

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

Но зачем останавливаться на 34 байтах?

Как только конкурс закончился, все поделились своим кодом и заметками — и прошёл ряд оживлённых дискуссий о том, как ещё его улучшить. После дедлайна было представлено ещё несколько вариантов:
Обязательно посмотрите — там есть несколько настоящих жемчужин.
Спасибо за чтение. И особая благодарность Матлеву, Филу, Гейру, Петри, Джейми, Яну и Дэвиду за участие (надеюсь, что я никого не упустил — было действительно трудно отслеживать все упоминания в твиттере!)

S. P. Петри назвал мой конкурс «ежегодным», так что, хм, наверное, увидимся в следующем году.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть