Nicron #125 19 декабря 2002

Программирование

Программирование - Процедуры расчета следующей и предыдущей линии экрана. Оптимизация.

(с) Е.Б. Голяков
(Spencer Winset, Diamond group, Москва)
500:95/462.8@ZXNet
2:5020/2065.608@Fidonet


     Процедуры расчета следующей и предыдущей линии экрана.
                        Оптимизация.

  Данная  публикация  является следствием оптимизации алгоритмов
расчета  следующей  и предыдущей линии экрана и желанием донести
новый  метод  до  как можно большего числа программистов, потому
что  пока  мною  не встречено подобных модификаций в современных
программах  или  конкурсных  работах  с  различных  компьютерных
фестивалей. Автор расчитывает на знание читателем ассемблера Z80
[2], а также адресного устройства экранной памяти Spectrum [3,4]
или совместимых с ним компьютеров.

			*	*	*

  Оригинальный   алгоритм  был  рассмотрен  автором  ранее  [1],
поэтому  я  не считаю нужным уделять внимание описанию принципов
его  работы, ограничиваясь только легким историческим экскурсом.
С  1982 года данный метод расчета адрессов экранной памяти так и
не  получил  широкого  распространения,  ввиду неизвестности или
непопулярности использования подпрограм ПЗУ на Спектруме.

  В  памяти  ПЗУ  (ZX Spectrum 48/128 (c) Sinclair Research Ltd)
функция  располагаетсяся  в  адресах  3769-3784  в in-line виде.
(прим.  редакции:  in-line - структурный термин, подразумевающий
встроенность  функции  в  тело  программы  в определенном месте,
исключающий ее вызов по команде CALL).

  Hиже  приводится сравнение оригинала (А) с усовершенствованной
и  поныне  повсеместно  используемой  процедурой  DOWN_HL  (Б) ,
авторство которой установить не удалось.



     А. (Logic_HL)                    Б. (DOWN_HL)

    HEX  │  OP CODE         Строка    HEX  │  OP CODE
    _____│________________            _____│________________
    24   │  INC  H             1      24   │  INC  H
    7C   │  LD   A,H           2      7C   │  LD   A,H
    E607 │  AND  #07           3      E607 │  AND  #07
    200A │  JR   NZ,BREAK      4      200A │  JR   NZ,BREAK
    7D   │  LD   A,L           5      7D   │  LD   A,L
    C620 │  ADD  A,#20         6      C620 │  ADD  A,#20
    6F   │  LD   L,A           7      6F   │  LD   L,A
    3F   │  CCF                8      3804 │  JR   C,BREAK
    9F   │  SBC  A,A           9      7C   │  LD   A,H
    E6F8 │  AND  #F8          10      D608 │  SUB  #08
    84   │  ADD  A,H          11      67   │  LD   H,A
    67   │  LD   H,A          12            BREAK  ...
          BREAK  ...
    _____________________            _____________________
     16b - 27/60t                     16b - 27/49/59t


  Видно, что при одинаковой длине в примере (Б) удалось выделить
событие  переполнения  регистра  L, означающего переход в другую
треть  экрана  (строка  8),  при  этом  время исполнения удается
сократить  с  60  до  49  тактов,  это можно считать успехом, но
наличие  в  экране  всего  двух  подобных  линий заметно снижает
вероятность   экономии.  Так  же  сократилось  время  на  расчет
перехода в следующюю позицию на 1 такт; это не существенно, хотя
и  справедливо  для  каждой  восьмой линии экрана (исключая две,
упомянутые выше).

  Можно  сказать,  что  всего  один  такт  решил  судьбу первого
алгоритма  ,  который  был  попросту  забыт  ,  несмотря  на всю
витиеватость  логических  конструкций;  отсюда и название Logic.
Анализируя  пуликацию [1] , удалось установить , что команда CCF
(Complement  Carry Flag), изменяющая состояние флага переноса CY
на   противоположное   (Строка   8),  применение  которой  здесь
означает, что действие, выполненное ранее (Строка 6) повлияло на
флаг с точностью до наоборот. Однако простое сложение может быть
заменено   вычитанием   дополненного  числа,  и  флаг  CY  будет
соответственно инвертирован автоматически. Об этом упоминается в
статье  И.Рощина  [5].  Заменив  команду  ADD  A,#20 на SUB #E0,
получим, что арифметические действия эквивaлентны, а команда CCF
более  не  нужна.  Hиже  приводится полученный результат - новая
процедура  DOWN_HL+,  сопоставленная  с  оптимизированной  ранее
DOWN_HL:



      Б. (DOWN_HL)                     В. (DOWN_HL+)

    HEX  │  OP CODE          LINE    HEX  │  OP CODE
    _____│________________          ______│_______________
    24   │  INC  H            01     24   │  INC  H
    7C   │  LD   A,H          02     7C   │  LD   A,H
    E607 │  AND  #07          03     E607 │  AND  #07
    200A │  JR   NZ,BREAK     04     2009 │  JR   NZ,BREAK
    7D   │  LD   A,L          05     7D   │  LD   A,L
    C620 │  ADD  A,#20        06     C620 │  SUB  #E0
    6F   │  LD   L,A          07     6F   │  LD   L,A
    3804 │  JR   C,BREAK      08     9F   │  SBC  A,A
    7C   │  LD   A,H          09     E6F8 │  AND  #F8
    D608 │  SUB  #08          10     84   │  ADD  A,H
    67   │  LD   H,A          11     67   │  LD   H,A
          BREAK  ...                       BREAK  ...
    _____________________          _____________________
     16b - 27/49/59t                15b - 27/56t


  Безусловно,  успехом здесь можно считать сокращение длины кода
на  1  байт;  для  такого сравнительно малого размера байт - это
более  6%. Также достигается выигрыш и в скорости на 3 такта для
каждой  восьмой  линии  экрана.  Сопоставив  скорости выполнения
расчетa  (в  тактах)  для всех линий экрана, считая первую линию
заданной, получим:

      Процедура (А)  27*167+60*24=      5949
                (Б)  27*167+49*2+59*22= 5905 (-44)
                (B)  27*167+56*24=      5853 (-96)

  Преимущество  в  скорости  перед процедурой (А) составило: для
(Б)  44  такта, а для (В) 96 тактов, что в 2.2 раза больше. Так,
при  выводе на экран 50 спрайтов по 40 линий, получаемая эконоия
не 450, а уже 1000 тактов.

			*	*	*

  Далее   приводятся   процедуры   расчета   вышележащей  линии,
популярная UP_HL (Г) и аналогично оптимизированная UP_HL+ (Д), с
идентичными показателями оптимимизации, описанными выше:


       Г. (UP_HL)                     Д. (UP_HL+)

    HEX  │  OP CODE          LINE    HEX  │  OP CODE
    _____│________________          ______│_______________
    7C   │  LD   A,H          01     7C   │  LD   A,H
    25   │  DEC  H            02     25   │  DEC  H
    E607 │  AND  #07          03     E607 │  AND  #07
    200A │  JR   NZ,BREAK     04     2009 │  JR   NZ,BREAK
    7D   │  LD   A,L          05     7D   │  LD   A,L
    D620 │  SUB  #20          06     C6E0 │  ADD  A,#E0
    6F   │  LD   L,A          07     6F   │  LD   L,A
    3804 │  JR   C,BREAK      08     9F   │  SBC  A,A
    7C   │  LD   A,H          09     E608 │  AND  #08
    D608 │  SUB  #08          10     84   │  ADD  A,H
    67   │  LD   H,A          11     67   │  LD   H,A
          BREAK  ...                       BREAK  ...
    _____________________          _____________________
     16b - 27/49/59t                15b - 27/56t



  Автор  выражает надежду, что изложенный материал будет полезен
как  создателям  256/512  байт  intro,  так и авторам масштабных
игровых  или  demo  проектов,  где  на  первое  место выходит не
количество   эффектов,   умещенных  в  полкилобайта,  а  красота
визуализации, помноженная на изящность и остроту кода.



 Литература
________________________________________________________________

1. Голяков Е.Б. Вспомогательные операции при выводе спрайта в
   область экранной памяти. - "Nicron", 1998, N119.

2. Персональный компьютер "ZX-SPECTRUM". Программирование в
   машинных кодах и на языке АССЕМБЛЕРА: В 3 ч. -М.,Инфорком,
   1993.

3. Графика ZX SPECTRUM. -M., VA PRINT, 1994. с.168-171.

4. Хардман Дж., Хьюзон Э. 40 лучших процедур. -"ZX-РЕВЮ", 1992,
   N1,2.

5. Рощин И. Еще о програмировании арифметических операций.
   - "Радиолюбитель. Ваш компьютер", 2000, N12, 2001, N1-4.