Оптимизация вывода точек на Speccy: новая быстрая процедура
Время выводить пиксели! В этой статье мы рассмотрим процедуру, которая, как мне кажется, на данный момент является самой быстрой универсальной процедурой рисования точек (PLOT) для ZX Spectrum. По сути, это очередная попытка превзойти по скорости стандартную реализацию PLOT из ПЗУ ZX Spectrum. Справедливости ради, код Стива Викерса (Steve Vickers) весьма остроумен, однако перед ним стоял совершенно иной набор инженерных ограничений.
Обратите внимание: статья предполагает знакомство с языком ассемблера Z80 и специфической («перепутанной») организацией видеопамяти ZX Spectrum, где биты адреса скомпонованы следующим образом:
0 1 0 y7 y6 y2 y1 y0 y5 y4 y3 x7 x6 x5 x4 x3а нужный пиксель внутри байта выбирается с помощью маски:
10000000 >> x2 x1 x0Прежде чем перейти к новому подходу, давайте кратко вспомним две вехи оптимизации, предложенные в 1990-х годах авторитетными программистами демосцены. Это важно не только для понимания ключевых идей, но и для задания эталонных реализаций, по которым можно сравнивать такты (поскольку разные авторы исходили из разных начальных условий).
Сначала взглянем на «каноническую» процедуру на 73 такта, представленную Busy (Slavomir Labsky) примерно в 1993 году. Главный выигрыш в скорости по сравнению с процедурой из ПЗУ достигается использованием таблицы предрасчётов размером 1 КБ, содержащей предварительно скомпонованные биты для координат X и Y, а также готовые битовые маски пикселей для каждой координаты X:
; Вход: D = Y (0..191), E = X (0..255)
7 ld h,TAB ; H = база таблицы
4 ld l,d ; L = координата Y
7 ld d,(hl) ; D = 0 1 0 y7 y6 y2 y1 y0
4 inc h
7 ld a,(hl) ; A = y5 y4 y3 0 0 0 0 0
4 inc h
7 ld l,e ; L = координата X
7 or (hl) ; A = y5 y4 y3 x7 x6 x5 x4 x3
4 ld e,a ; DE = результирующий адрес в видеопамяти
4 inc h
7 ld a,(de)
7 or (hl) ; наложение битовой маски пикселя
7 ld (de),aУлучшить столь плотно оптимизированный код совсем не просто и далеко не очевидно. Тем не менее, насколько мне известно, два кодера — Alone Coder (Дмитрий Быстров) и DC Pak (Przemyslaw Kasprzak) — независимо друг от друга примерно в 1998–1999 годах пришли к остроумному трюку с двумя указателями. Для наглядности начнём с 68-тактовой версии DC Pak:
; Вход: L = Y (0..191), E = X (0..255)
7 ld h,TAB
7 ld d,TAB + 2
7 ld a,(de) ; A = 0 0 0 x7 x6 x5 x4 x3
4 inc d
7 add a,(hl) ; A = y5 y4 y3 x7 x6 x5 x4 x3
4 inc h
7 ld h,(hl) ; H = 0 1 0 y7 y6 y2 y1 y0
4 ld l,a ; HL = результирующий адрес в видеопамяти
7 ld a,(de)
7 or (hl) ; наложение битовой маски пикселя
7 ld (hl),aВерсия Alone Coder, заявленная как 58-тактовая и опубликованная в журнале ZX-Guide #1, выглядит более лаконичной, но в основе её лежит ровно та же идея:
; Вход: L = Y (0..191), E = X (0..255), C = TAB, D = TAB + 2
4 ld h,c ; H = TAB
7 ld a,(de) ; A = 0 0 0 x7 x6 x5 x4 x3
4 inc d
7 or (hl) ; A = y5 y4 y3 x7 x6 x5 x4 x3
4 inc h
7 ld h,(hl) ; H = 0 1 0 y7 y6 y2 y1 y0
4 ld l,a ; HL = результирующий адрес в видеопамяти
7 ld a,(de)
7 or (hl) ; наложение битовой маски пикселя
7 ld (hl),aРеальный подсчёт тактов, впрочем, несколько более тонкая штука. Версию DC Pak можно дополнительно улучшить за счёт контекстных оптимизаций — например, заменив прямую загрузку констант TAB и TAB + 2 на регистровую. Он, несомненно, знал о такой возможности, но не мог с уверенностью рассчитывать на то, что регистровая пара BC в вызывающем коде всегда будет свободна.
Alone Coder зашёл в контекстных допущениях ещё дальше: он предполагает, что регистр C уже свободен и инициализирован, а регистр D заранее содержит TAB + 2. Однако поскольку это значение между вызовами портится и его нужно восстанавливать для корректной работы процедуры, накладными расходами пренебрегать нельзя. Следовательно, мы обязаны учесть либо 7-тактовую команду LD D,TAB + 2, либо как минимум 4-тактовую команду вроде LD D,B или DEC D для восстановления базы таблицы.
Оба автора предполагают входные параметры в виде E = X и L = Y. Хотя для внутренней логики самой процедуры это удобно, выборка таких координат из памяти или со стека становится затруднительной. В итоге любые такты, сэкономленные на процедуре, могут быть попросту сожжены на тасовку регистров снаружи.
Более того: если переписать данную процедуру под стандартную регистровую пару на входе, она окажется на 3 такта медленнее варианта от Busy.
В целом резонно заключить, что оптимизированный вариант этого подхода в наилучшем случае занимает 62 такта и выглядит следующим образом. Именно он послужит базой для дальнейшего сравнения:
; Вход: L = Y (0..191), E = X (0..255), B = TAB, C = TAB + 2
4 ld h,b ; H = TAB
4 ld d,c ; D = TAB + 2
7 ld a,(de) ; A = 0 0 0 x7 x6 x5 x4 x3
4 inc d
7 or (hl) ; A = y5 y4 y3 x7 x6 x5 x4 x3
4 inc h
7 ld h,(hl) ; H = 0 1 0 y7 y6 y2 y1 y0
4 ld l,a ; HL = результирующий адрес в видеопамяти
7 ld a,(de)
7 or (hl) ; наложение битовой маски пикселя
7 ld (hl),aНаконец, мы можем представить новое, ещё более быстрое решение. Ключевое наблюдение заключается в том, что для объединения y5 y4 y3 и x7 x6 x5 x4 x3 вовсе не обязательно выполнять побитовую операцию. Поскольку три бита y5 y4 y3 задают всего восемь возможных состояний, их можно использовать как индекс по набору из восьми вспомогательных таблиц. Каждая такая подтаблица уже содержит скомбинированный битовый шаблон y5 y4 y3 x7 x6 x5 x4 x3. Это увеличивает объём таблиц с 1024 до 2816 байт, что, признаться, является главным недостатком подхода. Однако в ситуациях, когда требуется предельная скорость, такие затраты памяти вполне допустимы.
Сначала рассмотрим «каноническую» 65-тактовую версию без учёта контекстных оптимизаций. Хотя номинально она чуть медленнее описанной выше 62-тактовой процедуры, на практике в реальных проектах она может оказаться быстрее, поскольку соглашение о передаче координат в регистрах D = Y, E = X уменьшает необходимость в перетасовке регистров:
; Вход: D = Y (0..191), E = X (0..255)
7 ld h,TAB
4 ld l,d ; L = координата Y
7 ld b,(hl) ; B = 0 1 0 y7 y6 y2 y1 y0
4 inc h
7 ld d,(hl) ; выбор 1 из 8 подтаблиц по битам y5 y4 y3
7 ld a,(de) ; A = y5 y4 y3 x7 x6 x5 x4 x3
4 ld c,a ; BC = результирующий адрес в видеопамяти
4 inc h
7 ld a,(bc)
7 or (hl) ; наложение битовой маски пикселя
7 ld (bc),aПримечательно, что если применить к этой процедуре те же контекстные допущения, что и в эталонной версии Alone Coder / DC Pak, время её выполнения сократится всего до 58 тактов:
; Вход: L = Y (0..191), E = X (0..255), B = TAB, C = TAB + 2
4 ld h,b ; H = TAB
7 ld d,(hl) ; D = 0 1 0 y7 y6 y2 y1 y0
4 inc h
7 ld h,(hl) ; выбор 1 из 8 подтаблиц по битам y5 y4 y3
4 ld l,e ; L = координата X
7 ld e,(hl) ; E = y5 y4 y3 x7 x6 x5 x4 x3
4 ld h,c ; H = TAB + 2
7 ld a,(de)
7 or (hl) ; наложение битовой маски пикселя
7 ld (de),aДля удобства я привожу генератор таблиц, чтобы вы сразу могли поэкспериментировать с этой процедурой сами:
TAB equ #F5
ld b,%11111000
ld l,0
GenY ld h,TAB
ld a,l
and b
rra
scf
rra
rra
ld c,a
xor l
and b
xor l
ld (hl),a
inc h
ld a,c
and 7
add a,TAB + 3
ld (hl),a
inc l
jr nz,GenY
inc h
ld a,%10000000
GenMask ld (hl),a
rrca
inc l
jr nz,GenMask
ld c,l
GenSub inc h
GenX ld a,l
and b
or c
rrca
rrca
rrca
ld (hl),a
inc l
jr nz,GenX
inc c
bit 3,c
jr z,GenSubВ завершение статьи — «бонусный» вариант процедуры, который вообще не трогает регистры B и C. Однако из-за того, что маски пикселей при этом приходится дублировать восемь раз, суммарный объём таблиц разрастается до 4,5 КБ — что пригодится разве что в самых экстремальных задачах:
7 ld h,TAB
4 ld l,d ; L = координата Y
7 ld d,(hl) ; D = 0 1 0 y7 y6 y2 y1 y0
4 inc h
7 ld h,(hl) ; выбор 1 из 8 подтаблиц по битам y5 y4 y3
4 ld l,e ; L = координата X
7 ld e,(hl) ; E = y5 y4 y3 x7 x6 x5 x4 x3
4 inc h ; переход к соседней таблице масок пикселей
7 ld a,(de)
7 or (hl) ; наложение битовой маски пикселя
7 ld (de),aПриятного вывода пикселей!
baze / 3SC
Поделитесь вашим мнением о статье