29.10.2020 07:48
PatientZero 86 24500 Источник

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

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

Это история об одном из таких трюков.

Я постараюсь припомнить все важные подробности, однако в чём-то могу ошибиться. Если так случится, простите меня, это было очень давно.

Исходные данные


Мой друг, одарённый программист, почти закончил свою новую игру. Каким-то образом ему удалось почти без изменений уместить в компьютер эпохи 1980-х довольно впечатляющую графически на то время игру, популярную на аркадных автоматах.

Единственная проблема заключалась в том, что его версия игры оказалась неиграбельной. Она работала слишком медленно, а дёрганые движения мешали вовлечённости игрока, ведь игра была сайд-скроллером.

Мой друг, работавший над игрой параллельно с учёбой в колледже, начал уже ощущать себя немного вымотанным. Опасаясь, что мог упустить какую-нибудь простую оптимизацию, он попросил посмотреть код меня.

Я посмотрел. Но там нельзя было найти никакой простой оптимизации.

Код был очень оптимальным. Куда бы я не посмотрел, он уже реализовал всё то, что бы я только мог придумать. Циклы были развёрнуты. Необязательная отрисовка была устранена. Все признаки пустой траты ресурсов были уничтожены.

А вместе с ними и наши надежды на простоту исправления.

Но как насчёт сложного исправления? Может быть, даже безумного?

Ну, такая возможность существует всегда.

Однако прежде чем приступать к безумной оптимизации, мне нужно объяснить, как в те времена работало графическое оборудование.

Как работало графическое оборудование


Если вкратце, то графическое оборудование не делало ничегошеньки.

На PC, с которым мы работали, при необходимости отрисовки чего-то на экране это нужно было делать самостоятельно, байт за байтом. Никаких функций наложения текстур, никаких блиттеров. Только байты. Байты, которые нужно перемещать ручками.

Очень захватывающе.

Бо?льшую часть времени игра моего друга тратила на перерисовку фона. (Повторюсь: это сайд-скроллер.) В каждом кадре ей приходилось отрисовывать почти целый экран тайлов фона, сдвинутых на позицию игрока.

Если память меня не подводит, каждый тайл имел размер 28 на 28 пикселей. Каждый пиксель имел один из 16 цветов, то есть на его описание требовалась половина байта. Следовательно, в памяти тайлы были представлены в виде 28 соседних строк по 14 байт каждая. Первые 14 байт представляли первую строку пикселей, вторые 14 байт — вторую, и так далее.

Однако экран имел размер 320 пикселей в ширину и 240 пикселей в высоту. То есть в памяти буфер экрана размещался как 240 соседних строк по 160 байт каждый.

Следовательно, при копировании тайла по адресу X в позицию экранного буфера, начинающуюся с адреса Y, нужно скопировать 28 строк. Чтобы скопировать каждую строку, нужно скопировать 14 байт. К счастью, эта игра работала на процессоре 6809, имевшем несколько 16-битных индексных регистров и замечательные режимы адресации с «автоинкрементом» (наподобие добавления постфиксного оператора ++ к указателям на C). Это означало, что можно скопировать 4 пикселя за раз, одновременно в процессе изменяя регистры X и Y:

    LDU ,X++     ; read a 2-byte word (= 4 pixels) from source tile
    STU ,Y++     ; write it to screen buffer

Чтобы скопировать всю строку, это нужно проделать семь раз, поэтому можно поместить эти строки в цикл со счётчиком 7 итераций:

    LDB #7       ; remaining words <- tile width in words
@LOOP
    LDU ,X++     ; read a 2-byte word (= 4 pixels) from source tile
    STU ,Y++     ; write it to screen buffer
    DECB         ; reduce remaining-word count
    BNE @LOOP    ; loop while words remain

Закончив копирование строки, нужно переместить указатель точки назначения Y, чтобы он указывал на начальный адрес следующей строки, которую мы будем отрисовывать в экранный буфер. Так как экранный буфер имеет ширину 160 байт, а тайл имел размер всего 14 байт, необходимо было прибавить их разность к Y:

    LEAY 160-14,Y

Вот и всё, мы скопировали строку на экран.

Но это только одна строка. Чтобы скопировать тайл целиком, нужно проделать то же самое 28 раз. Поэтому в свою очередь этот код мы засовываем в цикл со счётчиком 28 итераций.

Соединив всё вместе и дав имена всем важным числам, мы можем получить примерно такую подпроцедуру:

;;; important constants

SCRW = 160          ; screen-buffer width in bytes (= 320 4-bit pixels)
TILW =  14          ; background-tile width in bytes (= 28 4-bit pixels)
TILH =  28          ; background-tile height in rows
WOFF = SCRW - TILW  ; s-b offset from end of one tile row to start of next


COPYTILE
;;;
;;; Copy a 28x28 background tile into a screen buffer.
;;; Arguments:
;;;   X = starting address of background tile
;;;   Y = starting address of destination in screen buffer
;;;
    LDA #TILH               ; remaining rows <- tile height
@COPYROW
    LDB #TILW/2             ; remaining words <- tile width in words
@LOOP
    LDU ,X++                ; read a word (= 4 pixels) from source tile
    STU ,Y++                ; write it to screen buffer
    DECB                    ; reduce remaining-word count
    BNE @LOOP               ; loop while words remain
    ;;
    LEAY WOFF,Y             ; advance dst ptr to start of next dst row
    DECA                    ; reduce remaining-row count
    BNE @COPYROW            ; loop while rows remain
    ;;
    RTS                     ; done! return to caller

И этот код будет хорошо работать.

Конечно, если вас не заботит скорость.

Заботимся о скорости


Зная, что игра скорее всего будет тратить основную часть времени на выполнение этого кода, вы бы поступили как любой хороший программист: начали бы считать такты. Снова покажем внутренний цикл с подготовкой и завершением, с указанием количества тактов:

    LDB #TILW/2             ; 2 cycles (set-up)
@LOOP
    LDU ,X++                ; 8
    STU ,Y++                ; 8
    DECB                    ; 2
    BNE @LOOP               ; 3
    ;;
    LEAY WOFF,Y             ; 8 (finishing)

Изучая эти величины, вы вряд ли упустите аж целых 21 такта на копирование всего 4 пикселей. То есть для копирования полной строки требуется 2 такта + (7 итераций) * (21 такт/итерация) + 8 тактов = 157 тактов. Ой-ёй.

Но и мы не в первый раз за клавиатурой. Мы знаем, что нужно сделать. Развернём этот цикл!

    LDU ,X++                ; 8 cycles
    STU ,Y++                ; 8
    LDU ,X++                ; 8
    STU ,Y++                ; 8
    LDU ,X++                ; 8
    STU ,Y++                ; 8
    LDU ,X++                ; 8
    STU ,Y++                ; 8
    LDU ,X++                ; 8
    STU ,Y++                ; 8
    LDU ,X++                ; 8
    STU ,Y++                ; 8
    LDU ,X++                ; 8
    STU ,Y++                ; 8
    LEAY WOFF,Y             ; 8 (finishing)

Теперь количество впустую тратящихся в цикле тактов снижено до нуля — мы избавились от подготовки, на каждую строку требуется всего 7 * (8 + 8) + 8 = 120 тактов. Ускорение на 30 процентов, довольно неплохо.

И на этом большинство программистов закончили бы.

Но не мой друг.

Он знал, что эти операторы ++ затратны, по 3 такта на каждый. А после разворачивания цикла он точно знал, где расположено каждое слово для чтения или записи относительно X или Y. Поэтому он остроумно заменил эти трёхтактовых постинкременты точными смещениями. Каждое из них стоит всего 1 такт, а смещение на 0 по сути бесплатное:

    LDU  ,X                 ; 5 cycles
    STU  ,Y                 ; 5
    LDU 2,X                 ; 6
    STU 2,Y                 ; 6
    LDU 4,X                 ; 6
    STU 4,Y                 ; 6
    LDU 6,X                 ; 6
    STU 6,Y                 ; 6
    LDU 8,X                 ; 6
    STU 8,Y                 ; 6
    LDU 10,X                ; 6
    STU 10,Y                ; 6
    LDU 12,X                ; 6
    STU 12,Y                ; 6
    LEAX TILW,X             ; 8 (finishing)
    LEAY SCRW,Y             ; 8 (finishing)

После таких оптимизаций количество тактов на строку снизилось до (5 + 5) + 6 * (6 + 6) + (8 + 8) = 98 тактов. По сравнению с первоначальным кодом ускорение составило 60 процентов:

original_speed  = (1*row) / (157*cycle)
optimized_speed = (1*row) /  (98*cycle)

speed_up  =  optimized_speed / original_speed - 1  =  157 / 98 - 1  =  0.60

Соединим всё вместе (я снова делаю это по памяти, поэтому код мог быть и немного другим), и подпроцедура копирования тайла будет выглядеть примерно так, копируя полный тайл (все 28 строк) всего за 2893 такта:

COPYTILE2
;;;
;;; Copy a 28x28 screen tile into a screen buffer.
;;; Arguments:
;;;   X = starting address of background tile
;;;   Y = starting address of destination in screen buffer
;;; Execution time:
;;;   4 + 28 * (82 + 8 + 8 + 2 + 3) + 5 = 2893 cycles
;;;
    LDA #TILH      ; initialize row count (4 cycles)
    ;;
@COPY1
    ;; unroll inner loop (copies one row of 28 pixels in 82 cycles)
    LDU ,X         ; (1) read 4 pixels (5 cycles)
    STU ,Y         ;     write 4 pixels (5 cycles)
    LDU 2,X        ; (2) (6 cycles)
    STU 2,Y        ;     (6 cycles)
    LDU 4,X        ; (3) ...
    STU 4,Y        ;     ...
    LDU 6,X        ; (4)
    STU 6,Y        ;
    LDU 8,X        ; (5)
    STU 8,Y        ;
    LDU 10,X       ; (6)
    STU 10,Y       ;
    LDU 12,X       ; (7)
    STU 12,Y       ;
    ;;
    LEAX TILW,X    ; advance src to start of next row (8 cycles)
    LEAY SCRW,Y    ; advance dst to start of next row (8 cycles)
    DECA           ; reduce remaining count by one (2 cycles)
    BNE @COPY1     ; loop while rows remain (3 cycles)
    ;;
    RTS            ; done!  return to caller (5 cycles)

Этот код в сумме оказался на 60% быстрее, чем наивный код COPYTILE, с которого мы начали.

Но он не был достаточно быстрым, даже близко.

Поэтому когда друг показал мне свой код и спросил, смогу ли я его ускорить, я на самом деле хотел ему помочь. Я действительно хотел ответить «да».

Но мне пришлось ответить «нет». Мне ужасно не хотелось давать такой ответ. Однако, изучив код, я не нашёл никаких способов его ускорить.

Тем не менее, крючок с наживкой был заброшен.

Я не мог выкинуть эту задачку из головы. Вырос я на компьютерах Apple II и их процессорах 6502. Однако код моего друга исполнялся на 6809. Возможно, он позволяет создавать оптимизации, о которых я не знаю.

Возродив свой оптимизм, я набрал номер университетской библиотеки для доступа к каталогу карточек. (В те времена ещё не было World Wide Web.) Через эмулятор терминала VT220 я поискал книги о 6809.

Нашлась только одна: руководство по микропроцессору 6809. Оно находилось в инженерной библиотеке. К счастью, я учился на инженера и имел возможность брать книги.

Поэтому я отправился в библиотеку.

Безумная идея


Добравшись до инженерной библиотеки, я нашёл книгу именно там, где она и должна была находиться, ожидая небольшой встряски:

The MC6809-MC6809E Microprocessor Programming Manual.

Не озаботившись поиском стула, я стоя пролистал страницы в поисках какой-нибудь нетипичной, специфической для 6809 команды способной быстро получать и принимать множество байт. Однако страница за страницей ничего не находилось.

Затем я наткнулся на PSHS. «Push registers on the hardware stack» («Поместить регистры в аппаратный стек»).

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

Однако на 6809 можно сохранять все регистры (или любое их подмножество) одной командой. Удивительно, но для этого требовалось всего 5 тактов, плюс по одному такту за каждый записываемый в стек байт.

Так как процессор имел три 16-битных регистра общего назначения — D, X и Y — я мог загрузить их, а затем использовать команду PSHS, чтобы записать 6 байт всего за 11 тактов. Соответствующая pull-команда, PULS, имела столь же низкие затраты.

Более того, 6809 имел два регистра стека, S и U. Я мог использовать один как указатель на источник, а другой — как указатель на точку назначения. Теоретически, при помощи одной пары PULS/PSHU я мог копировать 6 байт за 22 такта.

Это безумно, безумно быстро.

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

Безумный план


По дороге назад в общежитие я сформировал свой план.

Я буду сохранять куда-нибудь регистры S и U, а затем указывать при помощи S на тайл фона, а при помощи U на экранный буфер. Затем я буду извлекать данные из S и записывать в U, копируя по 6 байт за раз при помощи D, X и Y в качестве промежуточных носителей. Для копирования 14 байтов, составляющих строку, потребуется три такие итерации, которые в развёрнутом виде составят примерно 60 тактов.

Добравшись до своей комнаты, я нашёл лист бумаги и набросал черновик:

    PULS D,X,Y    ; first 6 bytes    11 cycles
    PSHU D,X,Y    ;                  11
    PULS D,X,Y    ; second 6 bytes   11
    PSHU D,X,Y    ;                  11
    PULS D        ; final 2 bytes     7
    PSHU D        ;                   7
    LEAU -WOFF,U  ; advance dst ptr   8

Всего 66 тактов, в том числе и корректировка U после строки, подготавливающая его к следующей строке. (Обратите внимание, что корректировка теперь отрицательна.) Для сравнения: наивный цикл копирования строк выполнял ту же задачу за 157 тактов. А оптимизированный код моего друга за 98. Эта безумная идея уже казалась серьёзным выигрышем.

Однако у нас была очень неуклюжая последняя пара PULS/PSHU! Ей нужно было обрабатывать последние два байта строки, потому что строки имели ширину 28 пикселей = 14 байт, а 14 не делится нацело на 6.

Этот чёртов остаток в 2 байта!

Вот если бы в игре использовались тайлы 24 на 24 пикселя… Но это было не так, поэтому я тщательно изучил руководство в поисках способа снижения затрат на эту неизбежную последнюю пару.

И, к своему удивлению, я наткнулся на золотую жилу! Это была ещё одна особенность процессора 6809 — регистр DP.

В 6502 и большинстве 8-битных процессоров той эпохи нижние 256 байт памяти назывались нулевой страницей. Эта нулевая страница была особой, потому что её ячейки памяти имели однобайтные адреса и к ним можно было получить доступ с помощью более коротких и обычно более быстрых команд.

Проектировщики 6809 развили эту идею ещё глубже. Они позволили программистам использовать регистр DP, чтобы назначать любую страницу в качестве нулевой, которую они называли «direct page».

Но ни одна из моих передающих байты команд не требовала применения direct page. Это означало, что можно использовать регистр DP как ещё одно дополнительное промежуточное хранилище. Теперь я мог копировать 7 байт каждой парой pull-push!

И 14 точно делится на 7 нацело.

После внесения этого изменения я мог копировать целую 28-пиксельную строку и переходить к следующей всего за 5 команд:

    PULS D,X,Y,DP  ; first 7 bytes    12 cycles
    PSHU D,X,Y,DP  ;                  12
    PULS D,X,Y,DP  ; second 7 bytes   12
    PSHU D,X,Y,DP  ;                  12
    LEAU -WOFF,U   ; advance dst ptr   8

56 тактов!

Благодаря этому фрагменту кода я почувствовал себя потрясающе. Мне удалось задействовать каждый доступный в машине регистр для передачи байтов! D, X, Y, U, S и даже нетипичный DP — все они задействовались в полную силу.

Мне очень нравилось это решение.

За одним исключением…

Мне нужно сделать ещё одну безумную вещь


Если вы знакомы со стеками, то могли заметить небольшую погрешность в моём блестящем плане:

Push и pull работают в противоположных направлениях.

Видите, ли я обманул вас, показывая фрагмент кода. Я не копировал одну строку из тайла фона на экран. На самом деле он разбивал строку на два блока по 7 байт (я назову их септетами), а затем отрисовывал их на экран в обратном порядке.

Помните те строки тайлов, которые удобно укладывались в память как 14 соседних байт?

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0   1   2   3   4   5   6   7   8   9   A   B   C   D |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Когда мы выполняли pull и push строки на экран в 7-байтных септетах, они разделялись горизонтально таким образом:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 7   8   9   A   B   C   D | 0   1   2   3   4   5   6 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

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

Более того, если выполнить код копирования строк несколько раз, то вертикальный столбец копируемых срок окажется перевёрнутым. Так происходит потому, что код использует push для записи строк на экран. Команды push перемещают указатель стека в сторону нижних адресов, а нижние адреса соответствуют строкам экрана, расположенным выше на дисплее.

Чтобы продемонстрировать хаос, которое может создавать этот переворот строк и обмен местами септетов, давайте представим, что у нас есть такой тайл ключа размером 28 на 28:


Если бы вы использовали 28 раз мой код копирования строк для отрисовки его на экране, то получили бы вот такой не-ключ:


То есть… в этом была моя проблема.

Однако у этой проблемы тоже имелось изящное решение!

Опишем проблему вкратце:

  • строки перевёрнуты
  • септеты в каждой из строк поменялись местами
  • но байты в пределах каждого септета остались неизменными

Моё открытие заключалось в том, чтобы рассматривать «переворот» и «обмен местами» как два примера одного явления. Обращения.

Обращение имеет удобное свойство — оно является инволюцией. Обратите любой объект дважды, и вы получите исходный объект. Учтя это, я начал рассуждать, что если тайлы предварительно обработать так, чтобы обратить их строки, а затем септеты внутри строк, то при выводе на экран тайлы будут выглядеть нормально. Все правки, возникшие во время копирования и предварительной обработки, фактически отменят друг друга.

Проработав всё это на бумаге, я также обнаружил, что этап предварительной обработки может игнорировать строки и просто считать тайлы одной длинной линейной последовательностью септетов1. Чтобы понять, почему это так, давайте рассмотрим небольшой тайл из 2 строк по 2 септета каждая:

+---+---+
| a   b |
+---+---+
| c   d |
+---+---+

В памяти они будут размещены в построчном порядке, то есть как 4 последовательных септета:

+---+---+---+---+
| a   b | c   d |
+---+---+---+---+

То есть переворот строк с последующим обменом местами септетов в каждой строке будут аналогичны перевороту порядка септетов в памяти:

+---+---+                  +---+---+                  +---+---+
| a   b |                  | c   d |                  | d   c |
+---+---+        =======>  +---+---+        =======>  +---+---+
| c   d |        reverse   | a   b |        swap      | b   a |
+---+---+        rows      +---+---+        septets   +---+---+

+---+---+---+---+          +---+---+---+---+          +---+---+---+---+
| a   b | c   d |          | c   d | a   b |          | d   c | b   a |
+---+---+---+---+          +---+---+---+---+          +---+---+---+---+

То есть у проблемы с искажениями решением оказался простой единовременный этап предварительной обработки: достаточно просто разбить каждый тайл на септеты и обратить их порядок.

Зная, что проблему с искажениями можно решить, мне начала нравиться вся идея в целом. я не видел никаких других проблем, поэтому накидал черновик новой подпроцедуры копирования тайлов, чтобы показать её другу. Так как логика копирования строк занимала теперь всего 5 команд, я использовал её 4 раза, немного развернув последний оставшийся цикл. Теперь вместо копирования 28 одиночных строк я копировал 7 четверных строки.

Код выглядел примерно так:

COPYTILE3
;;;
;;; Copy a 28x28 screen tile into a screen buffer.
;;; Arguments:
;;;   X = starting address of *septet-reversed* background tile
;;;   Y = starting address of destination in screen buffer
;;; Execution time:
;;;   34 + 7 * (224 + 7 + 3) + 7 + 10 = 1689 cycles
;;;
    ;; setup:  34 cycles
    PSHS U,DP      ; save U and DP (8 cycles)
    STS >SSAVE     ; save S (7 cycles)
    ;;
    LDA #TILH/4    ; initial quad-row count (2 cycles)
    STA >ROWCT     ; (5 cycles)
    ;;
    LEAS ,X                    ; initialize src ptr (4 cycles)
    LEAU (TILH-1)*SCRW+TILW,Y  ; initialize dst ptr (8 cycles)
    ;;
@COPY1
    ;; copy four rows of 28 pixels in 4 * (48 + 8) = 224 cycles
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    LEAU -WOFF,U
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    LEAU -WOFF,U
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    LEAU -WOFF,U
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    PULS X,Y,D,DP
    PSHU X,Y,D,DP
    LEAU -WOFF,U
    ;;
    DEC >ROWCT     ; reduce remaining quad-row count by one (7 cycles)
    BNE @COPY1     ; loop while quad-rows remain (3 cycles)
    ;;
    LDS  >SSAVE    ; restore S (7 cycles)
    PULS U,DP,PC   ; restore regs and return to caller (10 cycles)

SSAVE ZMD  1       ; stash for saving S while drawing
ROWCT ZMB  1       ; var: remaining rows to copy

После сложения тактов их сумма составила всего 1689. Я сократил код друга почти на 1200 тактов. Ускорение на 70 процентов!

Сияя от радости, я направился к другу.

Кислотный тест


Когда я встретился с другом и сказал, что разобрался, как сделать процедуру копирования тайла на 70% быстрее, его лицо озарилось. Когда я немного объяснил всю концепцию искажений и септетов, он помрачнел и засомневался. Но когда я показал ему код, он всё понял. В голове «щёлкнуло».

«Давай его проверим», — сказал он.

Спустя примерно полчаса работы он интегрировал код в игру. После пересборки и перезапуска игра начала загружаться.

Появился экран заставки.

Он запустил игру.

И…

Чёрт побери!

Она казалась удивительно быстрой. На самом деле, вероятно, только на треть или на половину, но этого было достаточно. Мы превзошли некий порог восприятия. Игровой процесс теперь казался плавным и естественным. Разницу можно было ощутить.

Мы просто продолжали играть в игру и улыбаться. Это был хороший день.

Но наша радость была недолгой.

Семь бед...


Спустя несколько дней проблема со скоростью была далеко позади (или так нам казалось), оставалось добавить окончательные штрихи. Одним из таких штрихов были сэмплируемые звуковые эффекты. Для этого требовалось несколько раз в секунду передавать фрагменты размером в байт в ЦАП вывода звука. Чтобы запланировать передачу, мой друг включил прерывание по аппаратному таймеру.

Всё работало замечательно. Звуки звучали отлично, и всё остальное было идеально.

За одним исключением.

Поиграв в игру однажды вечером, мы заметили, что некоторые тайлы повреждаются. И чем больше играешь в игру, тем больше появляется повреждений.

О, нет.

Происходило что-то очень плохое.

И потом нас озарило.

Что происходит, если прерывание срабатывает во время выполнения процедуры копирования тайлов?

Чтобы подготовиться к вызову обработчика прерывания, процессор помещает своё текущее состояние в системный стек. Однако во время процедуры копирования тайлов системного стека нет. Процедура «конфисковала» регистр системного стека S. И куда же он указывает? Прямо на буфер памяти, содержащий исходные тайлы!

Упс.

Мы пали духом. После всех этих усилий трудно поверить, что наше совершенное необходимое ускорение вызывает повреждение памяти…

Нуждаясь в отдыхе, мы дошли до круглосуточного кафе рядом с кампусом, чтобы поесть и подумать. Поглощая блинчики и бекон, мы обсуждали проблему.

Существовало всего два стековых регистра и без использования их обоих процедура копирования тайлов и близко не будет такой быстрой. Таким образом, мы никак не могли вернуть системе регистр S, не потеряв при этом с трудом заработанный выигрыш в скорости. Но в то же время не было никакого способа реализации надёжного звука без использования прерываний.

Значит, тем или иным образом прерывания должны работать. А если они работают, то при выполнении копирования тайлов всё, на что указывает S, будет повреждено.

«Как можно предотвратить это повреждение?», — спросил я.

Мы сидели, забыв о еде, и вопрос повис в воздухе.

Внезапно мой друг хлопнул по столу. Он понял.

«Не нужно его предотвращать!», — сказал он.

«Что?»

«Не будем предотвращать повреждение. Пусть оно происходит. Просто не с исходными тайлами».

Это на самом деле было просто. Он продолжил:

«Просто поменяем местами S и U в процедуре копирования тайлов. U будет указывать на исходные тайлы, а S — на экранный буфер. Если сработает прерывание, то повреждение произойдёт там, куда указывает S — на экране. Повреждение сохранится только до перерисовки следующего кадра».

«Гениально!», — сказал я.

Стремясь проверить его решение, мы быстро закончили трапезу.

… один ответ


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

Позже тем же вечером мы его нашли.

Как только мы его придумали, он снова оказался простым. Нам достаточно было всего лишь изменить порядок тайлов. Вместо того, чтобы размещать тайлы на экране сверху вниз, слева направо, мы двинемся справа налево, снизу вверх. Другими словами, от высоких адресов к низким.

Таким образом, при срабатывании прерывания и повреждении ячеек памяти непосредственно перед текущим отрисовываемым тайлом повреждение будет устранено при отрисовке следующего тайла. А поскольку отрисовка тайлов выполняется в буфере, который не отображался до полной отрисовки (и выполнения вертикального обновления), никто никогда не увидит повреждения2.

Это был идеальный хак!

За старые деньки!


Вот так всё тогда и происходило. Трудности заключались не в чрезвычайной сложности систем, как это бывает сегодня. Трудность была в том, чтобы засунуть свои идеи в столь медленные и ограниченные в возможностях машины, что большинству идей в них не хватало места.

Приходилось экспериментировать с идеями, перекручивать их и поворачивать, искать что-то, что-нибудь, что позволит запихнуть их в машину. Иногда ты находил это что-то, и становился на шаг ближе к реализации своих идей, иногда нет.

Однако такой поиск всегда был очень поучительным.

В данном случае поиск привёл к серии небольших побед, которые совместно решили нашу проблему. Но если учесть всё, что требуется, чтобы сделать эту чёртову игру быстрой, это может показаться безумием.

Мы начали с процедуры копирования тайлов, ядро которой состояло из настроенного вручную развёрнутого цикла машинных команд. Затем для получения ускорения на 70%:

  1. Мы заменили эту подпроцедуру очень специфичным признаком проявления нашего безумия, конфискующим оба стековых указателя и использующим извлечение и запись в стеки, а также все доступные регистры для отрисовки тайлов вниз головой и сломанными по горизонтали.
  2. Затем мы предварительно обработали тайлы, чтобы отрисовка на самом деле их исправляла.
  3. Но потом (чёрт возьми!) оказалось, что прерывания, запускаемые во время отрисовки, способны повредить исходные тайлы.
  4. Поэтому для защиты исходных тайлов мы повреждали вместо них экранный буфер.
  5. Но такое повреждение было бы видимым.
  6. Поэтому мы изменили порядок размещения тайлов, чтобы чинить (на лету) любые повреждения, которые могут возникнуть, прежде чем они успеют отобразиться на экране.
  7. И всё это сработало!

Мы сделали это. Ради 70 процентов.

И это полностью оправдало себя.

Расскажи свою историю


Я хотел поделиться этой историей по двум причинам.

Во-первых, это интересная история, одно из моих первых воспоминаний о борьбе с запутанной компьютерной проблемой. Несмотря на её ожесточённое сопротивление, мы пришли к решению, которое оказалось и эффективным, и изящным. Результат доставил нам громадное удовлетворение.

Я узнал, что борьба оправдывает себя.

Во-вторых, я хотел вдохновить вас рассказать свои истории. Я знаю, что «в былые времена» создание большинства видеоигр приводило к появлению множества таких историй. Я бы хотел их услышать. Но слишком многие из них утеряны, стёрты из памяти до того, как кто-нибудь догадался их сохранить.

Если у вас есть история, не ждите. Расскажите её, с каждым днём ожидания это становится сложнее.


  1. Задание: доказать для всех конечных последовательностей из конечных последовательностей, что применение (reverse ? concat) эквивалентно применению (concat ? reverse ? map reverse).
  2. Нам также нужно было проверять, что ничего ценного не хранится в ячейках памяти непосредственно перед экранным буфером. Теоретически они тоже могли бы быть повреждены при срабатывании прерывания в момент размещения верхнего левого септета верхнего левого углового тайла. Адрес этого септета соответствует началу буфера.