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

В предыдущей статье я ускорял главную процедуру отрисовки экрана, которая рендерит двухбайтовые коды в блоки-ячейки 8x8 пикселей. Это чем-то напоминает устройство консоли 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

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

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

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

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

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

Если вы поняли, как работает процедура, попробуйте самостоятельно ответить на такой вопрос. В игре реализован скроллинг, а это значит, что чаще всего блоки с краёв будут видны лишь частично, потому что не попадают полностью в видимое окно экрана. Где в процедуре отрисовки лабиринта обрабатывается рисование частично видимых блоков? Правильный ответ: нигде. Область ячеек чуть больше, чем видимая часть экрана, и скроллинг происходит через смещение видимого окна. Область ячеек содержит 6x8 полных блоков, то есть 30x32 ячеек, а размеры видимой области экрана 22x24 ячеек. С одной стороны, это сильно упрощает обрезку (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 тактов, то есть в два раза быстрее.

Игрок и враги

Я раньше уже говорил, что способ отрисовки экрана на основе закодированного представления из ячеек 8x8 похож на то, как работают консоли типа 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, разрывая её пополам. Вспомогательная процедура делает три вещи. Сначала она пересчитывает абсолютные координаты ёжика в экранные координаты. Как мы помним, размер уровня 32x32 блока, и каждый блок имеет размер 5x4 ячеек, то есть размер уровня 160x128 ячеек, а значит координаты вполне влезают в один байт. Далее вспомогательная процедура проверяет, попадает ли ёжик в видимую часть экрана. Арифметика вычисления экранной координаты беззнаковая, а значит отрицательные экранные координаты превратятся в очень большие положительные, так что для проверки видимости достаточно сравнить экранную координату с максимальным значением и проверить флаг переноса. Если спрайт виден, то из его координат вычисляется смещение в области ячеек, куда его надо отрисовать. Вспомогательная процедура возвращает это смещение и выставляет флаг переноса, если спрайт виден.

Если спрайт виден, то выполнение продолжается с адреса $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 модифицируются ширина и высота прямоугольной области, в которой будет произведено рисование.

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

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

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

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

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

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

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

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

Статистика получилась странная и непонятная, разброс некоторых чисел был очень большой. Я временно решил не обращать внимание на случаи, когда числа улетали вверх, и сконцентрировался на анализе нижних границ. Из всех блоков кода сильнее всего выделялась наша старая знакомая: экранная процедура. В оригинальной игре она выполнялась примерно за 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!