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


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

Список участников со ссылками на исходный код:

• Филип Херон (код — 34 байта, победитель)
  
• Гейр Страуме (код — 34 байта)
  
• Петри Хаккинен (код — 37 байт)
  
• Матлев Раксенблатц (код — 38 байт)
  
• Ян Ахрениус (код — 48 байт)
  
• Джейми Фуллер (код — 50 байт)
  
• Дэвид А. Гершман (код — 53 байта)
  
• Янне Хеллстен (код — 56 байт)

(Если я кого-то пропустил, пожалуйста, дайте знать, я обновлю список).

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

Основы

Графика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) {
    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 (заполненный блок 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.

Во-вторых, вычисления адресов на 8-битном процессоре типа 6502 могут быть громоздкими и съедать много байт. У этого процессора также нет множителя, поэтому вычисление вроде 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. Прокрутка!

Вместо того, чтобы строить линию в экранном ОЗУ, рисуем только в последней экранной строке 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

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



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

Трюк 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'

В конкурсе считалось нормальным делать дикие предположения о рабочей среде. Например, что чертёж линий — первое, что запускается после включения питания 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.

Трюк 4. Оптимизация загрузки

Типичный двоичный файл 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.

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

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

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

Трюк 5. Нестандартный поток управления

Вот несколько упрощённая версия 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 байта.

Трюк 6. Линии со сжатием битов

Некоторые элементы не используют счётчик наклона линии, а скорее сжимают биты в 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 байтах?

Как только конкурс закончился, все поделились своим кодом и заметками — и прошёл ряд оживлённых дискуссий о том, как ещё его улучшить. После дедлайна было представлено ещё несколько вариантов:

• Филип — 33 байта
  
• Филип — 32 байта
  
• Петри — 31 байт
  
• Филип — 29 байт

Обязательно посмотрите — там есть несколько настоящих жемчужин.

---

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

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