№30 :: Быстрый вывод графики

:: №30 (01.04.2007) Просмотров: 4955

Номер: №30 (01.04.2007).

Быстрый вывод графики

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

Так уж сложилось, что решить данную проблему аппаратно практически невозможно (турбирование не в счет), а посему ее приходится решать программными методами. Постепенная эволюция методов вывода от простого LD A,(HL):LD (DE),A через LDIR/LDI к стековому выводу. Каждый метод имеет свою область применения, свои достоинства и недостатки. Сегодня поговорим о стековом выводе полноэкранных статических изображений.

Метод копирования (заполнения) области памяти, используя стековые операции, имеет в основе простой факт - процедуры PUSH rp/POP rp позволяют записать/считать сразу 2 байта за 11/10 тактов. Т.е. в среднем 5 тактов на байт. Весьма существенная разница по сравнению с 17 тактами на байт одного цикла LDIR. Но за все приходится платить. В частности, увеличенным размером кода (чтоб вывести 2 байта данных надо 4 байта кода) и повышенной сложностью подготовки данных.

Обычно используются два метода стекового вывода:

1) POP HL

LD (...),HL

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

2) LD rp,...

PUSH rp

Требующий 21 такт и 4 байта памяти для вывода двух байт. Слегка модифицированный вариант:

2а) LD HL,(...)

PUSH HL

Требует уже 27 тактов и 4 байта, но имеет сравнимую с методом 1 гибкость.

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

LD rp,...

PUSH rp

LD rp,...

PUSH rp

...

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

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

    LD rp,#ff00
    PUSH rp
    LD rp,#ffaa
    PUSH rp
    LD rp,#ffaa
    PUSH rp
    LD rp,#01aa
    PUSH rp

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

    LD rp,#ff00
    PUSH rp
    LD rl,#aa
    PUSH rp
    PUSH rp
    LD rl,rh
    LD rh,#01
    PUSH HL

Итого вместо 84 тактов и 16 байт кода для вывода 8 байт данных мы имеем 11+10+7+11+

+11+4+7+11=72 такта и 12 байт кода. 15% прирост скорости даже на таком вот небольшом участке!

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

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

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

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

Область применения такой выводилки можно вкратце очертить так:

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

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

Основные тонкости и принципы работы кодогенератора прописаны в комментариях к исходному тексту.

Используется синтаксис Alasm: 'label - старший байт метки label.

FASTPUT=#C000                   ;где будет создаваться выводилка (#XX00)
LEN=6912                        ;сколько будем выводить
            ORG 24576
            CALL MKFASTPUT      ;генерация выводилки

LOOP        HALT                ;пробный цикл для показа времени вывода
            LD A,2              ;заполнение бордюра красным цветом
            OUT (-2),A          ;будет показывать затрачиваемое на вывод
            CALL FASTPUT        ;время (примерно)
            XOR A                  ;если бордюр будет мерцать, значит вывод
            OUT (-2),A          ;не укладывается в прерывание
            IN A,(-2)
            RRA
            JR C,LOOP
            RET

MKFASTPUT   LD DE,BACKGR        ;генерация выводилки
            LD HL,FASTPUT       ;используем первые 512 байт места
FLL1        LD (HL),E           ;под выводилку для таблицы
            INC L               ;частот байтов картинки
            JR NZ,FLL1  
            INC H
            LD A,H
            CP 'FASTPUT+2
            JR NZ,FLL1
            LD H,'FASTPUT       ;и считаем количество байтов
            LD B,'LEN           ;каждого вида
CNT1        LD A,(DE)
            LD L,A
            INC (HL)
            JR NZ,NXR1          ;2 байта на счетчик
            INC H
            INC (HL)
            DEC H
NXR1        INC E
            JR NZ,CNT1
            INC D
            DJNZ CNT1
            CALL FINDMX         ;ищем самый частый байт
            LD (FRQB1),A        ;и сохраняем его в шаблон и
            LD (FRQB1_),A       ;процедуру поиска
            CALL FINDMX         ;и так еще 3 раза
            LD (FRQB2),A        ;итого мы имеем 4 самых частых
            LD (FRQB2_),A       ;байта, которые будут храниться
            CALL FINDMX         ;в регистрах
            LD (FRQB3),A
            LD (FRQB3_),A
            CALL FINDMX
            LD (FRQB4),A
            LD (FRQB4_),A
FSTMAK
            LD HL,FASTPUTTMPL   ;копируем начало шаблона
            LD DE,FASTPUT
            LD BC,ENDTMPL-FASTPUTTMPL
            LDIR
            EX DE,HL
            LD IX,BACKGR+LEN-2  ;по исходной картинке идем с
            LD BC,LEN/2         ;конца за LEN/2 шагов
            LD DE,(BACKGR+LEN-2);первые два байта картинки -
            PUSH BC             ;загрузка прямо в HL
            JR STORRA           ;и переход на генерацию LD HL,NN

MKCYC       PUSH BC             ;цикл генерации кода
            LD C,0              ;индекс регистра
            LD A,(IX+1)         ;старший байт в паре
            CALL SEARVAR        ;ищем индекс
            LD A,C
            RLCA
            RLCA
            RLCA
            RLCA
            LD C,A              ;заносим в старшие 4 бита С
            LD A,(IX)              ;младший байт в паре
            CALL SEARVAR        ;ищем (С инкрементируется!)
            LD A,C
            AND #F0             ;старший байт в Н уже есть?
            JR NZ,NO_HH
            LD A,C              ;да
            DEC A
            JR Z,STRPS          ;игнорируем LD H,H:LD L,L
            LD A,E
            CP (IX)             ;младший байт уже есть?
            JR Z,STRPS          ;да
            JR COMM_1           ;нет - создаем команду

NO_HH       XOR C               ;изменился старший байт
            JR NZ,NO_PDX        ;пытаемся обойти коллизию
            XOR C               ;LD H,..:LD L,H
            RRA
            RRA
            RRA
            RRA
            LD (HL),#6C         ;код LD L,H:
            INC HL              ;генерация LD H,R
            CALL STORCM         ;ниже объясняются эта последо-
            CP #26              ;вательность действий
            JR NZ,STORCOM
            LD (HL),A
            INC HL
            LD A,(IX+1)
            JR STORCOM

NO_PDX      LD A,C              ;если оба байта не в списке
            CP #66
            JR NZ,COMMON
STORRA      LD (HL),#21         ;код LD HL,NN
            INC HL
            LD A,(IX)           ;подгрузка данных
            LD (HL),A
            INC HL
            LD A,(IX+1)
            JR STORCOM

COMMON      AND #F0             ;хотя бы один байт в регистрах
            RRA
            RRA
            RRA
            RRA
            CALL STORCM         ;берем код загрузки старшего
            LD (HL),A           ;байта
            INC HL
            CP #26              ;это LD H,N?
            JR NZ,COMM_1
            LD A,(IX+1)         ;если да, то еще один операнд
            LD (HL),A
            INC HL
COMM_1      LD A,C              ;берем младший операнд
            AND #0F
            CP 1
            JR Z,STRPS          ;не изменился!
            CALL STORCM         ;иначе берем код
            OR 8                ;меняем LD H,.. -> LD L,..
            CP #2E              ;это LD L,N?
            JR NZ,STORCOM
            LD (HL),A           ;если да, то еще один операнд
            INC HL
            LD A,(IX)

STORCOM     LD (HL),A
            INC HL
STRPS       LD (HL),#E5         ;сохраняем код PUSH HL
            INC HL
            LD E,(IX)           ;DE содержит текущие данные
            LD D,(IX+1)         ;которые будут в HL во время
            DEC IX              ;выполнения. Там они будут под-
            DEC IX              ;ставляться, а тут можно сразу
            POP BC              ;получить их из входного потока
            DEC BC
            LD A,B
            OR C
            JP NZ,MKCYC         ;цикл...
            LD DE,TMPLEND
            LD BC,TMPLENDA-TMPLEND
            EX DE,HL
            LDIR                ;копируем завершающий фрагмент
            RET                 ;из шаблона

CTAB        LD H,H              ;Таблица для выборки команды по индексу
            LD H,L
            LD H,D
            LD H,E
            LD H,B
            LD H,C
            DB #26              ;LD H,N, для экономии 1 байта
FINDMX      LD DE,0             ;поиск байта с максимальной частотой
            LD HL,FASTPUT+256
SEARMS      LD A,(HL)
            CP D
            JR C,LESS
            DEC H
            LD A,(HL)
            INC H
            CP E
            JR C,LESS
            LD E,A
            LD D,(HL)
            LD C,L
LESS        INC L
            JR NZ,SEARMS
            LD L,C
            LD (HL),0           ;и обнуление его счетчика
            DEC H
            LD (HL),0
            LD A,C
            RET

STORCM      PUSH HL             ;выборка кода по индексу
            ADD A,CTAB
            LD L,A
            ADD A,'CTAB
            SUB L
            LD H,A
            LD A,(HL)
            POP HL
            RET

SEARVAR                         ;поиск переменной по значению
            CP D                ;H,L,D,E,B,C,N  - регистр
            RET Z               ;0,1,2,3,4,5,6  - индекс
SEARVR      INC C
            CP E
            RET Z
            INC C
FRQB2_      EQU $+1
            CP 0
            RET Z
            INC C
FRQB1_      EQU $+1
            CP -1
            RET Z
            INC C
FRQB4_      EQU $+1
            CP #55
            RET Z
            INC C
FRQB3_      EQU $+1
            CP #AA
            RET Z
            INC C
            RET
TMPSP       DW 0                   ;переменная для хранения SP

FASTPUTTMPL LD (TMPSP),SP       ;шаблон для выводилки. Можно подправить
            DI                  ;для своих целей
            LD A,(SCRADD)
            OR #40+'LEN
            LD H,A
            LD L,0
            LD SP,HL
FRQB1       EQU $+1
FRQB2       EQU $+2
            LD DE,#00FF
FRQB3       EQU $+1
FRQB4       EQU $+2
            LD BC,#55AA
ENDTMPL

TMPLEND     LD SP,(TMPSP)       ;завершение шаблона
            EI
            RET
TMPLENDA

SCRADD      DB 0                ;смещение старшего адреса. 0 или 128
BACKGR      INCBIN "FTFuture"   ;исходная картинка