Исследование и разгон игры Fred для ZX Spectrum, часть 2

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

В предыдущей статье я ускорял главную процедуру отрисовки экрана, которая рендерит двухбайтовые коды в блоки-ячейки 8×8 пикселей. Это чем-то напоминает устройство консоли NES, только в ней ячейки отрисовываются аппаратно. Найти главный цикл отрисовки экрана было несложно: я случайно прерывал выполнение программы отладчиком, для многих игр это даёт неплохой шанс оказаться именно в процедуре отрисовки, потому что чаще всего это самая медленная часть (в случае Fred это было особенно справедливо). Если бы не было этого способа, то оставалось бы два варианта. Первый — реверсить весь код игры с самого начала. Второй вариант — найти эмулятор с поддержкой точек останова, которые срабатывают при доступе к определённым адресам памяти (memory breakpoints), и повесить такую точку останова на видеопамять. Я не знал готовых эмуляторов с поддержкой memory breakpoints. Реверсить же весь код по порядку долго и больно, потому что неизвестен смысл многих данных. Гораздо проще двигаться наоборот, от экранной процедуры, когда легко увидеть, во что на экране нарисуется какой байт. Разобраться с устройством экранной процедуры Fred-а было несложно. Теперь, зная, как она работает, мы можем продолжить реверсинг: во-первых, из любопытства о том, как писали игры в 80-х, а во-вторых, вдруг получится ускорить игру ещё немного?

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

Рисование лабиринта

Вот код процедуры, которая рисует блоки уровня, вместе с кодом вспомогательной процедуры.

; ;generate encoded representation of visible part of current level, for subsequent rendering by main video loop ;encoded representation will be generated for 6x8 blocks ;each labyrinth block is converted into 5x4 cells of a same color ;So whole representation takes 6*8*4*5 = 960 cells, which take 1920 ($780) bytes ;Representation is stored at [$ECC0 - $F43F] ; $6460 LD DE, ($6649) ; coordinates of player (center of a screen), reg D - vertical coord, reg E - horizontal coord       DEC D       DEC D          ; top visible row of labyrinth is current row - 2, it may be negative!       DEC E                 DEC E       DEC E          ; left visible column of labyrinth is current column - 3       LD HL, $ECC0   ; base for encoded screen representation       LD C, $06      ; number of visible rows ;outer loop, encode level rows $646E PUSH DE       PUSH HL       LD B, $08     ; number of visible columns ;inner loop, encode level elements       PUSH BC       LD A, D       ;checking vertical coord       CP $21        ;compare with level size + 1       JR C, $6486   ;it is below, ok, so it is possibly block of a labyrinth, let's check another coordinate       CP $80        ;otherwise, let's check if it greater than level's height, but not negative       JR C, $6481   ;if yes, then encode a sand block       LD BC, $E078  ;if here, then coord is negative, which means it's above the level, so we should encode stars       JR $64A4      ;jump directly to encoding $6481 LD BC, $C08C  ;code for a sand block       JR $64A4      ;jump directly to encoding $6486 LD A, E       ;check horizontal coord       CP $20        ;compare with level width       JR C, $6492   ;if lower, then it is a labyrinth item, let's get it       JR NZ, $6481  ;otherwize, it's a sand block       LD BC, $A03C  ;another kind of sand block       JR $64A4      ;jump directly to encoding  $6492 PUSH HL       ;save HL (a destination in encoded screen) $6493 CALL $61EA    ;get block code       SLA A         ;offset = blockcode*2, since each cell code is 2 bytes       LD HL, $64D3  ;base       ADD A, L       LD L, A       ;add offset to base       JR NC, $64A0  ;check for overflow       INC H         ;adjust high byte if overflow  ;now HL contains pointer to encoded info (2 bytes) of top-left cell of a block $64A0 LD C, (HL)    ;read first byte of block info       INC HL       LD B, (HL)    ;read second byte of block info       POP HL        ;restore HL (a destination in encoded screen)  $64A4 PUSH DE       ;store level coords       PUSH HL       ;store destination in encoded screen       PUSH BC              POP DE        ;now DE has value of encoded block  ;at this point DE contains code for top-left cell of a level block, and HL contains destination address for cells ;all remaining cells for level block are just sequential increments starting from top-left cell       LD C, $05    ;each labyrinth block is 5 cells high ;inner loop, go by cell rows for labyrinth block $64AA PUSH HL      ;store destination pointer for beginning of cell row for current block       LD B, $04    ;labyrinth blocks are 4 cells wide ;innermost loop, go by cells in one row of a labyrinth block $64AD LD (HL), E   ;write low byte of encoded cell        INC HL       ;increment destination address       LD (HL), D   ;write high byte of encoded cell       INC HL       ;increment destination address       INC DE       ;increment cell code $64B2 DJNZ $64AD   ;loop       POP HL       ;restore pointer so it points again to leftmost cell of current row        PUSH DE      ;store cell code, since we need to use DE       LD DE, $0040        ADD HL, DE   ;move to next row. each row is $40 bytes, which is (num of blocks $08)*(block width $04)*(bytes per cell $02)       POP DE       ;restore cell code        DEC C        ;decrement cell rows counter       JR NZ, $64AA ;move to encode next cell row for current level block        POP HL       ;restore destination pointer for top-left cell of level block       LD DE, $0008        ADD HL, DE   ;move 4 columns to right, since each cell is 2 bytes        POP DE       ;restore coordinates       INC E        ;move to next block to the right       POP BC       ;restore counters of level columns and rows       DJNZ $6472   ;decrement column counter and repeat if there are any left        POP HL       ;restore destination pointer of top-left cell of leftmost block on current row       LD DE, $0140        ADD HL, DE   ;move 5 rows below, since each row is $40 bytes, which is (num of blocks $08)*(block width $04)*(bytes per cell $02)       POP DE       ;restore coordinates       INC D        ;move to next row       DEC C        ;decrement row counter       JR NZ, $646E ;repeat for next row, if there is any $64D2 RET   ;get a level block code for provided level coordinates ;current labyrinth is stored at $E000, it's dimensions are 32x32, from left to right, from top to bottom ;inputs: reg D - level row (0 - 31), reg E - level column (0 - 31) ;result: reg A - block value $61EA XOR A       LD L, A       PUSH DE  ; no need to push/pop, DE doesn't change       LD A, D  ; we will shift level row index by 3 bits to the left       SRL A       RR L       SRL A       RR L       SRL A       RR L       OR $E0  ; base address of level map is E000       LD H, A ; high byte of level element goes to H       LD A, L         OR E    ; low byte of level element is composed of horizontal coord (lower 5 bits)        LD L, A ; and 3 bits of vertical coord       LD A, (HL) ;get level element       POP DE $6202 RET

Лабиринт состоит из больших блоков, каждый блок имеет размеры 5×4 клеток. Игра отслеживает грубые координаты игрока, которые описывают, в каком блоке лабиринта игрок сейчас находится. Зная это, можно определить видимое окно из блоков лабиринта. Сама структура лабиринта хранится по адресу $E000, размеры 32×32, каждый блок кодируется одним байтом. Процедура содержит 4 вложенных друг в друга цикла. Самый внешний цикл $646E проходит по 6 строкам лабиринта, внутри него цикл проходит по 8 столбцам лабиринта. Получив однобайтный код блока, его нужно превратить в последовательность двухбайтных кодов ячеек. Для получения кода левой верхней ячейки блока используется таблица по адресу $64D3, индексом в которой выступает код блока, умноженный на 2. Коды для всех остальных ячеек блока получаются последовательным инкрементом. Поскольку блок лабиринта состоит из 5×4 ячеек, то третий цикл $64AA идёт по строкам, а четвёртый, самый внутренний цикл, идёт по ячейкам внутри строки.

В первой части мы разобрались, как устроен двухбайтный код ячейки: три старших бита кодируют цвет, 13 младших бита умножаются на 8 и указывают на последовательность из 8 байт, кодирующих пиксели. Теперь же, зная, что блоки лабиринта превращаются в коды ячеек простым инкрементом базового значения, мы можем понять, почему так сделано: инкремент кода ячейки не изменяет её цвет, только указатель на пиксели, что подходит к дизайну с одноцветными блоками. Инкремент кода ячейки смещает указатель пикселей на 8, то есть сразу после предыдущих пикселей, это очень хорошо подходит для плотного последовательного хранения пикселей. Плохая новость: такой способ распаковки блоков лабиринта означает, что каждая ячейка у всех блоков уникальна, нельзя закодировать блоки лабиринта так, чтобы у них совпадали какие-то коды ячеек. Если присмотреться к игровому экрану, то визуально он примерно на четверть состоит из пустой черноты. Если в экранной процедуре для пустых блоков-ячеек вообще пропускать отрисовку пикселей (включая расчёт расположения источника), это дало бы отличный прирост скорости. Но не выйдет: и для совершенно пустых блоков лабиринта, и для блоков, в которых висят верёвки, каждая ячейка имеет свой отличающийся код, включая пустые ячейки. Единственный вариант, как реализовать сложную структуру блока — это иметь таблицу того, из каких ячеек состоит блок. Чтение из такой таблицы, конечно же, замедлит выполнение рассматриваемой процедуры, ещё и память под неё надо найти. Поэтому эту оптимизацию вычёркиваем.

Вторая оптимизация, которая приходила в голову в процессе работы над экранной процедурой, состояла в том, чтобы поменять формат двухбайтового кода ячейки: 3 младших бита отвечают за цвет, 13 старших битов — за адрес пикселей. Если это сделать, то в процедуре кодирования лабиринта нужно заменить инкремент кода ячейки на увеличение на 8 байт. Это недешёвая операция для двухбайтовой величины на Z80: нужно загрузить число 8 в регистровую пару и выполнить ADD, и делать это на каждом шаге самого внутреннего цикла, при этом свободных регистровых пар нет. Так что эта оптимизация не выглядит разумной: мы ускорим экранную процедуру, но замедлим процедуру кодирования лабиринта. Поэтому тоже вычёркиваем.

Я привожу код процедур уже в откомментированном виде, но изначально он таким не был, комментарии — результат анализа ассемблерного кода. Я оказался в этой процедуре, потому что сработала memory breakpoint по адресу $64AD, дальше я первым проходом по коду сделал предварительное описание логики и выделил циклы, догадаться до остальных деталей уже было несложно. Из этой процедуры мы узнали много полезных вещей о самой игре. Например, то, по какому адресу хранится текущий лабиринт и что он закодирован однобайтовыми блоками. Мы даже можем написать вспомогательную программку, которая прочитает снапшот игры и отрисует весь лабиринт.

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

Если вы поняли, как работает процедура, попробуйте самостоятельно ответить на такой вопрос. В игре реализован скроллинг, а это значит, что чаще всего блоки с краёв будут видны лишь частично, потому что не попадают полностью в видимое окно экрана. Где в процедуре отрисовки лабиринта обрабатывается рисование частично видимых блоков? Правильный ответ: нигде. Область ячеек чуть больше, чем видимая часть экрана, и скроллинг происходит через смещение видимого окна. Область ячеек содержит 6×8 полных блоков, то есть 30×32 ячеек, а размеры видимой области экрана 22×24 ячеек. С одной стороны, это сильно упрощает обрезку (clipping) для блоков и спрайтов, и сильно упрощает скроллинг. С другой стороны, это делает скроллинг неравномерным: при движении можно смещать видимое окно, но иногда придётся чуть замедлиться и перекодировать лабиринт.

Можем ли мы оптимизировать эту процедуру? Стоит попытаться. Даже на первый взгляд тут можно, например, оптимизировать третий по вложенности цикл, который начинается с адреса $64AA. Перед началом цикла самого внутреннего цикла, заполняющего ячейки в строке, на стеке запоминается адрес в области ячеек, с которого начинается заполнение строки, хранящийся в HL. После заполнения адрес восстанавливается в HL и к нему прибавляется смещение $40, чтобы спуститься на одну строку вниз. Вполне можно обойтись без сохранения-восстановления, доcтаточно прибавить не ширину целой строки из области ячеек, а уменьшить её на ширину блока, которая равна 4 * 2 = 8 байт, что в итоге даст нам смещение $38. Это экономит 2 байта инструкций и 22 такта процессора в весьма вложенном цикле. Также само увеличение на $38 можно выполнить гораздо быстрее: не нужно сохранять на стек DE и потом восстанавливать. Можно воспользоваться парой BC, у которой к этому моменту регистр B равен 0, то есть достаточно записать $38 в регистр С. Что, регистр C уже используется как счётчик цикла? Без проблем, пусть A будет работать счётчиком цикла. Итого, выбрасываем PUSH+POP, и заменяем загрузку константы в однобайтный регистр, экономим 11+11+(10-4) = 28 тактов и 3 байта инструкций.

Но это всё мелочи, как насчёт радикальной оптимизации? Для процессора Z80 самый быстрый способ записать два байта в память и сдвинуть адрес на соседний — это команда PUSH. Но на этом пути есть несколько проблем. Первая проблема: PUSH двигает указатель стека вниз. Значит, строки ячеек будут заполняться справа налево, и коды ячеек нужно не инкрементить, а декрементить. Тогда уж проще переписать заполнение ячеек блока, чтобы оно происходило не слева направо сверху вниз, а наоборот: справа налево снизу вверх. Вторая проблема: если мы используем стек для записи в память, то мы не можем использовать его как временное хранилище регистров. В предыдущем абзаце мы увидели, что при оптимизации мы вполне можем обходиться без сохранения регистров на стек. Для чего нам нужны регистры? Хранить код ячейки, хранить адрес, куда мы этот код запишем, и счётчики циклов. Самый-самый внутренний цикл выполняется 4 раза, его можно развернуть, это ускорит выполнение и избавит нас от одного из счётчиков циклов. Не забудем, что у нас есть альтернативный набор регистров, с ним нам хватит на счётчики для оставшихся трёх циклов. Получилось у меня вот что:

; can store SP on $6200  ;optimization of labyrinth encoding via stack memory write ;approx. 47000 tstates  $6460   LD DE,($6649)   INC D   INC D   INC D   DEC E   DEC E   DEC E   DEC E   LD ($6200),SP ; instead of this variable, write SP exacty to code which does LD SP,NN    LD SP,$F440   ;check me!   LD C,6 oupterloop1:    LD B,8   LD A,B           ADD A,E       ;move to the right end of row   LD E,A outerloop2:    LD A,D   CP $21   JR C,A2   EXX    CP $80   JR C,A1   LD DE,$E078      JR draw A1:    LD DE,$C08C   JR draw A2:    LD A,E   CP $20   JR C,getcellcode   EXX   JR NZ,A1   LD DE,$A03C   JR draw  getcellcode:    CALL $61EA    ;get block code pointed by D and E into A   RLCA   EXX   LD HL, $64D3  ;block info base   ADD A, L      ;add offset   LD L,A  ;now HL contains pointer to block info (2 bytes), read block info into HL   LD E,(HL)   INC HL   LD D,(HL)  draw:   LD A,$13   ADD A,E ;code correction, since we go backwards   LD E,A   LD B,5  innerloop1:   PUSH DE   DEC DE   PUSH DE   DEC DE   PUSH DE   DEC DE   PUSH DE   DEC DE     LD HL,$FFC8   ADD HL,SP ;same as SUB SP,$38   LD SP,HL  ;move to previous row     DJNZ innerloop1    EXX   ;correcting SP so it will be -8 to the value before encoding a block ;this way it will point to destination area of next block ;currently SP is original value - 108, so by adding 100 we will get -8   LD HL,0038     LD A,1   CP B   JR Z, A7   INC H;  A7: ADD HL,SP   LD SP,HL    DEC E   DJNZ outerloop2   DEC D   DEC C   JR NZ outerloop1   LD SP,NNN ; value of SP is written here   RET

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

Игрок и враги

Я раньше уже говорил, что способ отрисовки экрана на основе закодированного представления из ячеек 8×8 похож на то, как работают консоли типа NES или SNES. Консоли, конечно же, гораздо продвинутее для двухмерных игр: они предоставляют несколько слоёв для рисования. На ZX Spectrum приходилось программировать слои вручную, и закодированное представление экрана — это как раз то место, в котором происходит наложение слоёв. Самый задний слой — это блоки лабиринта, которые мы только что изучали. Теперь посмотрим, как на них накладываются спрайты. Вот процедура, которая рисует фиолетовых ёжиков.

; ;Draw a hedgehog, with copying content from screen into buffer ; $696D LD A, ($68E8)   ; number of hedgehogs       LD B, A         ; will be used as loop counter       LD HL, $BF68    ; start of list of monster info structures $6974 CALL $697B      ; check if visible       JR NC, $69D7    ; skip this monster if it is not visible $6979 JR $69A4        ; draw a monster if it is visible  ;sub-proc which will check if monster is visible $697B LD E, (HL)      ; horizontal coord       INC HL       LD D, (HL)      ; vertical coord       INC HL       LD A, ($6629)   ; vertical offset of visible screen       SUB $08         ; adjust       LD C, A       LD A, D       SUB C       LD D, A         ; now reg D contains on-screen vertical coord       CP $16          ; check if this coord is visible       RET NC          ; exit of no       LD A, ($6628)   ; horizontal offset of visible screen       SUB $0A         ; adjust       LD C, A       LD A, E       SUB C       LD E, A         ; now reg E contains on-screen horizontal coord       CP $1A          ; check if it is visible       RET NC          ; exit if no       XOR A       SRL D       RRA       SRL D       RRA       SLA E       ADD A, E       LD E, A         ; now DE contain offset of sprite on encoded screen       SCF             ; carry flag indicates that sprite is visible       RET              ;end of sub-proc ;back to outer proc, this part will copy sprite cell codes into encoded screen area $69A4 PUSH HL                LD HL, ($638F)  ; address of top-left corner of encoded screen area       ADD HL, DE      ; add offset       LD ($643C), HL  ; param for $6409, destination for a sprite       POP HL                 INC HL          ; HL points to +3 field of monster structure       LD ($6436), HL  ; param for $6409, buffer where screen content will be stored       DEC HL          ; HL points to +2 field of monster structure       PUSH HL               LD A, (HL)      ; load monster animation step (sprite code)       AND $03         ; leave only 2 bits       LD E, A       LD D, $00       SLA E           ; multiply by 2, it will make an offset       LD HL, $6140    ; that is a sprite base       ADD HL, DE      ; add offset, now HL points to monster sprite initial cell code       LD ($643A), HL  ; param for $6409, source of a sprite       POP HL       LD A, $01       ; height of a sprite       LD ($6411), A   ; modify code of $6409       INC A           ; width of a sprite       LD ($6413), A   ; modify code of $6409       CALL $68F4      ; call $$68F4, which will call $6409       LD A, $04              LD ($6411), A   ; restore code of $6409       LD ($6413), A   ; restore code of $6409 $69D7 INC HL       INC HL       INC HL       INC HL       INC HL       INC HL       INC HL       DJNZ $6974       ;next loop $69E0 RET

Процедура забирает из глобальной переменной количество ёжиков на уровне, и проходится по списку. Для каждого ёжика вызывается вспомогательная процедура $697B, код которой расположен прямо внутри кода процедуры $696D, разрывая её пополам. Вспомогательная процедура делает три вещи. Сначала она пересчитывает абсолютные координаты ёжика в экранные координаты. Как мы помним, размер уровня 32×32 блока, и каждый блок имеет размер 5×4 ячеек, то есть размер уровня 160×128 ячеек, а значит координаты вполне влезают в один байт. Далее вспомогательная процедура проверяет, попадает ли ёжик в видимую часть экрана. Арифметика вычисления экранной координаты беззнаковая, а значит отрицательные экранные координаты превратятся в очень большие положительные, так что для проверки видимости достаточно сравнить экранную координату с максимальным значением и проверить флаг переноса. Если спрайт виден, то из его координат вычисляется смещение в области ячеек, куда его надо отрисовать. Вспомогательная процедура возвращает это смещение и выставляет флаг переноса, если спрайт виден.

Если спрайт виден, то выполнение продолжается с адреса $69A4. Дальнейший код подготавливает параметры для вызова процедуры $68F4 . Некоторые параметры передаются через глобальные переменные $643C, $6436, $643A, но помимо этого два байта в коде процедуры $68F4 модифицируются, и после выполнения восстанавливаются. Давайте же посмотрим, что это за $68F4.

; ;a small wrapper around $6409 which preserves HL and BC ; $68F4 PUSH HL       PUSH BC $68F6 CALL $6409       POP BC       POP HL $68FB RET   ; ;copy content of some rectangle of a screen into buffer, then draw a sprite over it ;params: ; ($643C) - 2 bytes, destination in encoded screen area ; ($6436) - 2 bytes, location of a buffer where previous content of a screen will be stored ; ($643A) - 2 bytes, source of a sprite to be drawn ; code of this procedure is modified by a caller, it will change width and height by modifying bytes at $6411 and $6413 ; $6409 LD HL, ($6436)  ; address of a buffer where content of a screen will be stored       PUSH HL         ; will be saved on stack       LD HL, ($643C)  ; destination in encoded screen area  $6410 LD C, $04       ; height of sprite, this value at $6411 is modified by a caller $6412 LD B, $04       ; width of sprite, this value at $6413 is modified by a caller ;first we copy content from the screen into a buffer $6414 LD E, (HL)      ; get first byte of cell code       INC HL       LD D, (HL)      ; get second byte of cell code       EX (SP), HL     ; now HL points to buffer area       LD (HL), E      ; store first byte of cell code       INC HL       LD (HL), D      ; store second byte of cell code       INC HL       EX (SP), HL     ; buffer pointer will go on stack, and address of encoded screen area goes into HL       DEC HL ;now we draw sprite on screen $641E LD DE, ($643A)  ; cell of sprite to be drawn next time       LD (HL), E      ; we store it on encoded screen area       INC HL       LD (HL), D       INC HL       INC DE          ; increment cell code! $6427 LD ($643A), DE  ; memorize next cell code $642B DJNZ $6414      ; loop       LD DE, $0038    ; offset to be added to encoded screen area to move to next row. This value is modified by caller       ADD HL, DE      ; moving to next row       DEC C           ; decrement row counter       JR NZ, $6412    ; loop       POP HL $6435 RET 

Эта процедура делает вот что: она рисует ячейки спрайта, но перед рисованием каждой ячейки предыдущее значение копируется в некоторый буфер. Рисование происходит в двойном цикле: внешний цикл по строкам спрайта, внутренний цикл по ячейкам внутри строки. Коды ячеек спрайта получаются последовательным инкрементом начального значения, в точности как у блоков лабиринта. Регистры B и C используются как счётчики циклов, причём их начальные значения вовсе не обязательно 4, как видно в коде: перед вызовом эти значения будут изменены вызывающей процедурой. Упражнение на внимательность: вернитесь к коду процедуры $696D и определите, какие значения будут прописаны для количества строк и ячеек в строке для рисования ёжиков (1 строка, 2 ячейки в ней). Регистры D и E используются для хранения двух копируемых байтов, регистровая пара HL содержит адрес чтения или записи. Довольно забавно, как HL перепрыгивает между адресом в области ячеек и адресом в буфере сохранения при помощи инструкции EX (SP),HL , которая выполняется за такие неслабые 19 тактов.

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

Давайте посмотрим, как происходит восстановление сохранённых ячеек. Код очень похожий на $6409:

; ;a small wrapper around $64F1 which preserves HL and BC ; $68FC PUSH HL       PUSH BC $68FE CALL $64F1       POP BC       POP HL $6903 RET   ;restore a previously stored rectangular part of visible area from buffer ;params:  ;  ($643E) 2 bytes, a destination in screen cells area ;  ($6440) 2 bytes, a source, address which points to a sequence of 2-byte cell codes $64F1 LD HL, ($643E)  ;pointer where to put sprite cells, a pointer in cell area       PUSH HL         ;top of the stack will be used as an exchanged temporary storage, so we put destination addr       LD HL, ($6440)  ;a pointer to sprite source $64F8 LD C, $04       ;sprite height. This code is modified by caller by changing value at $64F9 ! $64FA LD B, $04       ;width of sprite. This code is modified by caller by changing value at $64FB ! $64FC LD E, (HL)      ;get first byte of sprite cell       INC HL       LD D, (HL)      ;get second byte of sprite cell       INC HL ;; greatest idea!!! instead of EX (SP),HL  use LDI!!!       EX (SP), HL     ;exchange source and destination pointers       LD (HL), E      ;put first byte of sprite       INC HL       LD (HL), D      ;put second byte of sprite       INC HL       EX (SP), HL $6506 DJNZ $64FC      ;end of inner loop       EX (SP), HL       LD DE, $0038    ;move to next row of screen cell area. This value is modified by callers       ADD HL, DE       EX (SP), HL       DEC C $650F JR NZ, $64FA    ;outer loop       POP HL $6512 RET

Опять же, у этой процедуры два параметра передаются в выделенных ячейках памяти, и два байта в коде (счётчики циклов ) изменяются вызывающей процедурой.

Код процедуры, которая проходит по всем ёжикам и вызывает для них восстановление сохранённых ячеек. Этот код — практически копипаста процедуры $696D, простите, что она некачественно откомментирована, примерно так выглядит мой первый, самый сырой проход комментирования при реверсе.

; ;restore screen content from temp buffers for hedgehogs ; $69E1 LD A, ($68E8)  ; example value: $28, number of monsters/hazards ?       LD B, A        ; it will work as a loop counter       LD HL, $C0C7 $69E8 LD E, (HL)     ; example value: $5A, coordinate?       INC HL       LD D, (HL)     ; example value: $3B, coordinate?       INC HL ;looks like following code checks if monster is currently visible ;and also calculates on-screen coordinates       LD A, ($6629)  ;vertical offset of visible screen       SUB $08       LD C, A       LD A, D       SUB C       LD D, A        ; example value: $D1       CP $16       JR NC, $6A33       LD A, ($6628)  ;screen offset ?       SUB $0A       LD C, A       LD A, E       SUB C       LD E, A       CP $1A       JR NC, $6A33  ;calculate offset in encoded screen based on on-screen coordinates in D and E       XOR A          ;example value in DE: $0913       SRL D       RRA       SRL D       RRA       SLA E       ADD A, E       LD E, A       ;example value in DE: $0266        PUSH HL       LD HL, ($638F)  ;address of visible top-left cell of encoded screen       ADD HL, DE      ;add offset, this makes HL to be address in encoded screen area       LD ($643E), HL  ;sprite destination in cells area, param for proc $64F1       POP HL       INC HL       LD ($6440), HL  ;sprite source, param for proc $64F1       DEC HL       LD A, $01 $6A21 LD ($64F9), A ;modify code in proc $64F1, sprite size       INC A $6A25 LD ($64FB), A ;modify code in proc $64F1, sprite size $6A28 CALL $68FC    ;call a proc which then will call $64F1       LD A, $04       LD ($64F9), A ;restore default sprite size       LD ($64FB), A $6A33 INC HL       INC HL       INC HL       INC HL       INC HL       INC HL       INC HL $6A3A LD DE, $0012       AND A       SBC HL, DE $6A40 DJNZ $69E8 $6A42 RET

Ещё раз осмыслим логику кода, который мы разбирали. Информация о ёжиках хранится в списке, для каждого ёжика первые два байта содержат абсолютные координаты, третий байт хранит код спрайта. Процедура рисования $696D проходит по списку, для каждого ёжика пересчитывает его абсолютные координаты в экранные. Дальше нужно код спрайта превратить начальный код ячейки. Для этого код спрайта умножается на количество ячеек в спрайте, и прибавляется к базовому значению-константе $6140. Получившийся начальный код ячейки будет одним из параметров для универсальной процедуры рисования $64F1. Двумя другими параметрами будут вычисленный на основе экранных координат адрес в области ячеек, и адрес буфера для сохранения предыдущего содержимого. Перед вызовом в универсальной процедуре рисования $64F1 модифицируются ширина и высота прямоугольной области, в которой будет произведено рисование.

Для внимательных читателей ещё задачка. Если мы идём по списку ёжиков, и перед рисованием ёжика сохраняем в буфер то, что в этом месте было раньше, и при этом ёжики могут рисоваться поверх других ёжиков, то логично, что восстанавливать предыдущее содержимое нужно, идя по списку ёжиков в обратном порядке. Сможете ли вы найти в коде, как это сделано?

Скрытый текст

Список ёжиков в процедуре рисования начинается с $BF68, а в процедуре восстановления идём с хвоста $C0C7. Кроме того, в процедуре восстановления для перехода на предыдущего ёжика есть код по адресу $6A3A, который вычитает $12.

А теперь прекрасная новость: все остальные монстры рисуются аналогичным образом, вызывая $64F1. Код их отрисовки и восстановления является почти копипастой, меняются начальные адреса списков монстров, базовые значения кодов ячеек и размеры спрайтов. На всякий случай вот таблица (заполнил насколько смог)

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

Мне очень хотелось заняться оптимизацией универсальных процедур $6409 и $64F1. Дело немного осложняется тем, что при переписывании наверняка сместятся адреса, в которых хранятся значения для счётчиков циклов, а в эти адреса пишут значения все процедуры, которые вызывают $6409 и $64F1. Да, у нас есть таблица вызывающих процедур, и мы можем пропатчить их все, хоть это и лениво.

Но хотите прикол? Размер ёжика всего 2 ячейки. И для того, чтобы скопировать 4 байта в буфер и записать 4 байта в ячейки, процедура $696D делает кучу работы, включая вызов $6409, внутри которой есть аж два цикла! Правильная оптимизация в данном случае — вообще не вызывать универсальную процедуру $6409, а тупо встроить копирование байтиков, будет сильно быстрее и гораздо короче. Аналогичная оптимизация напрашивается для капель и ящериц (их размер 2×1).

Я сделал это, попробовал в игре, и снова не ощутил никакой разницы!

Агрессивная оптимизация экранной процедуры

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

Статистика получилась странная и непонятная, разброс некоторых чисел был очень большой. Я временно решил не обращать внимание на случаи, когда числа улетали вверх, и сконцентрировался на анализе нижних границ. Из всех блоков кода сильнее всего выделялась наша старая знакомая: экранная процедура. В оригинальной игре она выполнялась примерно за 587500 тактов, после оптимизации она выполняется примерно 318000 тактов. Неудивительно, что я не заметил результат оптимизации отрисовки лабиринта: даже старый медленный вариант выполняется в 4 раза быстрее, чем оптимизированная экранная процедура! Что ж, давайте попробуем ускорить экранную процедуру ещё сильнее.

Как мы уже обсуждали при оптимизации процедуры отрисовки лабиринта, самый быстрый способ последовательно работать с памятью — это через стек. В экранной процедуре нам нужно читать последовательно, а при записи увеличивать старший байт адреса видеопамяти, поэтому стек у нас будет использоваться для чтения пикселей ячейки командой POP. Заодно раскроем самый внутренний цикл.

$6391 LD BC,($638F)    ;pointer to top-left visible cell       LD DE, $0801     ;D is pixel row number, E is column number        LD A, $16        ;counter for outer loop, number of 8-pixel rows ;outer loop $639A PUSH AF          ;save counter       PUSH DE       CALL $62D3       ;calculate video-mem address into HL based on DE       CALL $6442       ;calculate attribute area address into IX based on HL, and copy screen addr into DE        ld (spstor), SP       LD A, $18        ;counter for inner loop, number of columns ;inner loop $63A4 EX AF, AF'       ;save counter       LD A, (BC)       ;load first byte of cell code       LD L, A          ;copy here       INC BC       LD A, (BC)       ;load second byte of cell code       INC BC           ;now BC points to next cell       LD H, A          ;copy here       RLCA       RLCA       RLCA       AND $07       OR $40           ;now reg A contains inc color from high 3 bits of cell code       LD (IX+$00), A   ;set color for screen cell-block       ADD HL, HL       ;lower 13 bits of cell code contain offset of cell pixels divided by 8       ADD HL, HL       ADD HL, HL       ;get full offset by multiplying by 8, this makes high 3 bits to go away       LD A, H       ADD A, $94       ;pixel area base addres is $9400, we add it to pixels offset to get full pixels address       LD H, A        LD SP,HL       EX DE,HL       LD A,H        POP DE              LD (HL),E           INC H               LD (HL),D           INC H               POP DE              LD (HL),E           INC H               LD (HL),D           INC H               POP DE              LD (HL),E           INC H               LD (HL),D           INC H               POP DE              LD (HL),E           INC H               LD (HL),D           LD H,A        EX DE,HL       INC IX           ;move right to next attribute       INC E            ;move right to next video column       EX AF, AF'       ;restore loop counter       DEC A            ;decrement it       JR NZ, $63A4     ;loop        LD SP,(spstor)        LD HL, $0010     ;this offset should be added to cell code        ADD HL, BC       ;to get to beginning of next visible cell row       LD B, H       LD C, L       POP DE           ;restore row and column numbers       LD A, $08        ;move down to next 8-pixel column       ADD A, D       LD D, A       POP AF           ;restore outer column counter       DEC A            ;decrement it       JR NZ, $639A     ;loop to next row down $63F2 RET

Так что же получается, зря мы изучали, как отрисовывается лабиринт и монстры? Не зря. Переписать процедуру отрисовки экрана в таком агрессивном виде я не мог раньше, потому что из-за раскатанного цикла она занимает больше места, чем старая процедура. По адресам $63DF — $6408 располагается процедура отрисовки игрока (см. таблицу). Оптимизация отрисовки ёжиков позволила выделить место, в которое я перенёс процедуру отрисовки игрока, что позволило написать супер-оптимизированную отрисовку экрана.

Ну, а что там по скорости? Новый вариант отрисовки экрана выполняется примерно за 210000 тактов, если мерить точками профилирования. А если измерять точками, которые измеряют FPS, то получаем 110 миллисекунд между срабатываниями, то есть примерно 9 FPS, где-то в полтора раза быстрее, чем предыдущая оптимизация, и в два раза быстрее, чем оригинал. Играть на такой скорости уже очень сложно, потому что темп игры зависит только от скорости выполнения всей логики, включая отрисовку. Мы ускорили отрисовку, а ускорилась вся игра, тут невозможно добавить плавности.

Есть ещё один серьёзный момент. Похоже, что звуковая система игры сделана так, что действие игры прерывается, пока звук не прозвучит до конца. На ускоренном варианте это очень чувствуется: процесс игры становится дёрганным, и дёрганье совпадает со звуками. С воспроизвением звука на ZX Spectrum я не знаком совсем никак, и не чувствую себя в силах разобраться и ускорить.

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

Заключение

Я попробовал оптимизировать старину Fred-а настолько, насколько можно, убедился, что технически концепция работает, но gameplay не очень. Зато в процессе анализа удалось раскрутить назначение всяких внутренних структур игры, например мы знаем, в какой ячейке хранится количество ёжиков. Вот так, от экранной процедуры и вглубь проще всего реверсить игры.

Сам процесс реверсинга Fred-а несложен. Игру делали в 1983 году, и код её немного наивный: очень понятен ход мыслей программиста. Код очень неоптимален по производительности, и в коде много копипасты. Но это не мешает наслаждаться игрой.

Сейчас полностью понятно, как хранится графика игры, есть инструменты для просмотра. Так что если кто-то хочет попробовать себя в pixel art — будет супер.

Спасибо, что прочитали. ZX Spectrum forever!