Deja Vu #05 31 мая 1998

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

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

SoundTrack: DEVOUR OF BRAIN BY DX-69 1998 
__________________________________________


(C) Card!nal/PGC/BD
__________________________________________


   Привет,дорогие читатели нашего журнала!
Даниил  тут попросил  меня написать статью
по coding'у, и я вот сижу за текстовым ре-
дактором. Эта статья не имеет определенной
цели, просто я расскажу об оптимизации  и,
вообще, что у меня  накопилось  с  выпуска
четвертого номера Deja Vu.


   Для  начала поговорим о выводе спрайтов
без атрибутов. Вот стандартная процедура:

        LD HL,adr    ;адрес спрайта
        LD DE,#4000  ;адрес в экране
        LD B,192     ;высота в пикселях
        LD C,32      ;ширина в знакоместах
LOOP2   PUSH DE
        PUSH BC
        LD B,0
        LDIR
        POP BC
        POP DE
        INC D
        LD A,D
        AND 7
        JP NZ,METKA1
        LD A,E
        ADD A,32
        LD E,A
        JP C,METKA1
        LD A,D
        SUB 8
        LD D,A
METKA1  DJNZ LOOP2
        RET


   А  теперь  давайте  посчитаем,  сколько
тактов  она работает. Не углубляясь в под-
робности,  как  я это посчитал, скажу, что
она работает около 146000 тактов при выво-
де  спрайта  размером  с  экран. В среднем
тратится 23.7 тактов за байт. Вообщем, это
неплохая процедура вывода статических кар-
тинок,  ну, а если вам нужна быстрая, УНИ-
ВЕРСАЛЬНАЯ  процедура, тогда смотрите ниж-
ний  листинг. Под  словом  универсальная я
подразумевал, что можно  произвольно зада-
вать  высоту, ширину спрайта и его коорди-
наты на экране.

        CALL DECRUN ;эта программа делает
                    ;таблицу адресов
                    ;экрана

        LD HL,adr  ;адрес спрайта
        LD D,3     ;коорд. X в знакоместах
        LD E,8     ;коорд. Y в пикселях
        LD B,100   ;высота в пикселях
        LD C,20    ;ширина в знакоместах

WIWOD   DI
        LD A,D
        LD (WIW1+1),A
        LD A,C
        ADD A,A
        SUB 64
        NEG
        LD C,A
        LD A,B
        LD B,0
        LD IX,WIW2
        ADD IX,BC
        EX DE,HL
        LD H,B
        ADD HL,HL
        LD BC,BUFER
        ADD HL,BC
        LD (STACK+1),SP
        LD SP,HL
        EX DE,HL
        LD B,A
LOOP1   POP DE
        LD A,E
WIW1    ADD A,0
        LD E,A
        LD C,D
        JP (IX)
WIW2
        DUP 32
        LDI      ;команда LDI повторяется
        EDUP     ;32 раза

        DJNZ LOOP1
STACK   LD SP,0
        EI
        RET


DECRUN  LD HL,BUFER
        LD DE,#4000
        LD B,192
LOOP    LD (HL),E
        INC HL
        LD (HL),D
        INC HL
        INC D
        LD A,D
        AND 7
        JR NZ,METKA
        LD A,E
        ADD A,32
        LD E,A
        JR C,METKA
        LD A,D
        SUB 8
        LD D,A
METKA   DJNZ LOOP
        RET
BUFER   DEFS 384


   Процедура  работает  108076  тактов при
выводе  спрайта  величиной  с экран, что в
1.35  раза  быстрее  предыдущей. В среднем
тратится 17.6 тактов за байт. Подпрограмма
DECRUN запускается только один раз,а даль-
ше можно пользоваться подпрограммой  WIWOD
сколько угодно. Скажу только,что нужно за-
прещать прерывания, так как юзается  стек.
Постарайтесь сами разобраться, как все ра-
ботает. Я только подскажу зачем нужна  ко-
манда LD C,D перед  командой  JP (IX). Как
известно, LDI при работе уменьшает регист-
ровую пару BC, так вот, чтобы не  портился
регистр B, нам нужно постоянно  держать  в
регистре C число больше, чем  максимальная
ширина спрайта,то есть больше 32,а регистр
D всегда содержит число больше 32.

   Ну все, с выводом спрайтов разобрались,
поговорим о повороте спрайта на любой угол
(0  - 360). В четвертом Deja Vu был исход-
ник  Колотова "TURN SPRITES". Честно гово-
ря, я  видел  эту  программку еще раньше и
скажу, что  качество работы программы меня
не  очень-то  обрадовало :-(. Я попробовал
повернуть залитый квадрат 5 на 5 знакомест
на 45 градусов и увидел неприятную картин-
ку, квадрат уже был похож не на квадрат, а
на квадратное решето, и использовать такую
программу  было затруднительно. А все дело
в  алгоритме  поворота и не учета строения
экрана. Я  реализовал несколько другой ал-
горитм  и  результат  просто  потрясающий.
Картинка почти (учитывая низкое разрешение
экрана)  не искажается. Если вы, например,
повернете  залитый  круг радиусом 50 на 45
градусов  вокруг  его  центра, то получите
такой  же  круг. Правда этот алгоритм не я
придумал, а взял его из журнала ZX NEWS 3.
Там  была  статейка о повороте спрайтов, и
была дана программа на бейсике. Программка
эта  работала более часа, поворачивая весь
экран. Аналога  в  кодах этой программы не
было, а  автор  сознался, что не дружит со
встроенным  калькулятором  бейсика. Честно
говоря, я  тоже  не  дружу  со  встроенным
калькулятором, а  потому реализовал данный
алгоритм в кодах без использования кальку-
лятора. Первая версия моей программы рабо-
тала  3.5 минут, поворачивая весь экран не
важно на какой угол. Я решил, что это пол-
ный  SUXX  и чуть-чуть оптимизировал ее. В
итоге получилось около 40 секунд, что при-
мерно  в 5 раз быстрее первоначального ва-
рианта и в 100 раз быстрее чем на бейсике,
и это,заметьте,без потери качества изобра-
жения. Дальше оптимизировать было лень,хо-
тя была перспектива довести время до 10-15
секунд, а то и быстрее, но эту  радость  я
могу предоставить вам, SERZH, ты меня  по-
нял  :-). В приложении найдете исходник  в
формате ALASM 3.8c. Исходник содержит  ко-
ментарии, так что разберетесь. Не смотрите
на убогий код,некогда было его вылизывать.
Началом координат считается  левый  нижний
угол экрана, если я не ошибаюсь. Поворачи-
ваемый спрайт (не дай себе засохнуть!)дол-
жен уже быть на экране. Программа  исполь-
зует приличный объем  памяти ( 6144 + при-
мерно 2кг ) байт для буфера,там увидите...
Чуть не забыл рассказать алгоритм  поворо-
та. Берется точка с координатами  (x0,y0),
поворачивается на угол и получается  коор-
дината (x1,y1), из координаты (x1,y1)  бе-
рется точка (если она есть) и  переносится
в координату (x0,y0), потом берется  след.
(x0,y0) и т.д. Проверки выхода за  пределы
экрана, OF COZZZ, делаются,так что все на-
мана :-).

   Ну что? Поехали дальше! Меня тут  некий
CRANK попросил помочь разобраться в "заум-
ных xor'ках", а посему скажу вот что. Нау-
читься разбираться в xor'ках ты должен сам
(с помощью STS v6.2, например). Постарайся
разобраться, что она  расxorивает, трасси-
руй,  внимательно следи за регистрами, ре-
зидент STS'а переноси, если нужно, в безо-
пасное  место. Простейшая  xor'ка выглядит
так:

        LD HL,adr
        LD BC,lenght
LOOP    LD A,(HL)
        XOR 23
        LD (HL),A
        INC HL
        DEC BC
        LD A,B
        OR C
        JR NZ,LOOP
        RET


   If you have a pC, то можете там набрать
программу в ассемблере или в hiew (если ты
извращенец :-)).

        mov dx,adr
        mov bx,lenght
loop    mov si,dx
        mov al,[si]
        xor al,23
        mov [si],al
        inc dx
        dec bx
        jnz loop
        retn


   Мне, конечно, все  равно где кодить, но
SPECCY, OF COZZZ, RULEZ форева!!!


   С  xor'ками  вроде  разобрались, как на
Спектруме, так  и  на  ПИСИ, поэтому пошли
дальше  :-).  Я  хотел бы еще сказать пару
слов о переключении страничек. Вот, напри-
мер, какую программку я увидел у SERZH'а в
одной  из его рулезных (как всегда) стате-
ек:

        LD BC,#7FFD
        OUT (C),A
        LD (BANK),A
        RET
BANK    DEFB 0


   Или  что-то  в этом роде. Что же мы ви-
дим? Вроде все правильно... Ан  нет! Пред-
ставим ситуацию,что прерывания пришли меж-
ду командами out (c),a и ld (bank),a. Пре-
рывания отработают и вернутся  обратно. Но
при выходе восстановится  старое  значение
BANKи и в итоге цветные квадратики на  эк-
ране, а посему  сохранять  значение  нужно
перед out (c),a.


   Т.к. Deja Vu теперь будет выходить  без
защиты, то я хотел рассказать  о  классном
способе защиты от копирования  придуманном
мной (диск нельзя скопировать даже  на  pC
и Amiga) и даже хотел кинуть  исходники  в
приложение (форматер и читалка формата),но
потом подумал, что слишком жирно  будет! И
отказался от этой  затеи. Хотя, если  меня
хорошо попросят, то может  быть  расскажу.
Теперь поехали дальше.

   Хочу сказать пару  слов  о  игре Черный
ворон, крутая надо сказать игруха. Но  не-
которые уровни просто убийственные (я имею
ввиду  почти непроходимые), а так как я не
геймер и игрушками не увлекаюсь шибко, по-
этому облегчил себе жизнь, вставил парочку
POKES  и  увидел  FINAL CUT! Если обнулить
три  байта с адреса #D5CE в RAM0, то у вас
перестанут  кончаться  деньги. Ну, а номер
текущего  уровня хранится по адресу #79D8.
Например, заносите  туда  номер следующего
уровня, делаете  "повторить  попытку" и вы
уже  на  другом  уровне. Если туда занести
#10, то  увидите FINAL CUT. "Все это прек-
расно",скажете вы - "А как же защита?" Тут
вы  правы, даже теневик не поможет. А поэ-
тому  выкручивайтесь сами, ломайте как хо-
тите. Я не имею морального права учить вас
ломать коммерческие продукты. Скажу  толь-
ко, я потратил три дня, чтобы вставить PO-
KES!

   Далее поговорим об алгоритме умножения.
Простейшая  процедура  умножения на SPECCY
выглядит так: HL = A*E


        LD H,A
        LD L,0
        LD D,L
        LD B,8
LOOP    ADD HL,HL
        JR NC,$+4
        ADD HL,DE
        DJNZ LOOP
        RET


   Не трудно подсчитать количество тактов:
минимум  310, максимум 358 без  учета RET.
Конечно, если развернуть  цикл, мы получим
минимум 206, а максимум 254 такта. А можно
ли  побыстрее? Yes, of cozzz! Но для этого
нужно  вспомнить начальную алгебру. А точ-
нее  формулы сокращенного умножения:

    Квадрат суммы: (a+b)^2=a^2+2ab+b^2
    Квадрат разности: (a-b)^2=a^2-2ab+b^2


   Возьмем  эти формулы на вооружение. Для
того, чтобы  написать процедуру умножения,
нужно  сформировать табличку квадратов чи-
сел  от  0  до  255  включительно. Таблица
квадратов будет основной частью программы.
Адрес таблицы должен быть кратным 256, т.е
младший  байт  = 0. Это  делает  следующая
программка.

SET_TBL LD DE,TABL
        LD H,E
        LD L,E
        LD B,E
        LD C,E
SET_T1  LD A,L
        LD (DE),A
        INC D
        LD A,H
        LD (DE),A
        DEC D
        ADD HL,BC
        INC C
        ADD HL,BC
        INC E
        JR NZ,SET_T1
        RET
TABL    DEFS 512


   А вот и сама процедура умножения. Числа
от  0  до  255 задаются в регистрах L и E.
Ответ в HL.


MULS    LD H,'TABL
        LD C,(HL)
        INC H
        LD B,(HL)
        LD A,L
        ADD A,E
        JP NC,MUL4
        JP M,MUL1
        SUB E
        SUB E
        JP NC,MUL2
        LD A,E
        SUB L
MUL2    LD L,E
        LD D,(HL)
        DEC H
        LD E,(HL)
        LD L,A
        LD A,(HL)
        INC H
        LD H,(HL)
        LD L,A
        SBC HL,BC
        OR A
        SBC HL,DE
        LD A,L
        CPL
        LD L,A
        LD A,H
        CPL
        LD H,A
        INC HL
        SRL H
        RR L
        RET
MUL4    LD L,E
        LD D,(HL)
        DEC H
        LD E,(HL)
        LD L,A
        LD A,(HL)
        INC H
        LD H,(HL)
        LD L,A
        SBC HL,BC
        OR A
        SBC HL,DE
        SRL H
        RR L
        RET
MUL1    LD A,L
        SUB E
        JP NC,MUL3
        LD A,E
        SUB L
MUL3    LD L,E
        LD D,(HL)
        DEC H
        LD E,(HL)
        LD L,A
        LD A,(HL)
        INC H
        LD H,(HL)
        LD L,A
        SBC HL,BC
        OR A
        SBC HL,DE
        SRL H
        RR L
        LD A,L
        CPL
        LD L,A
        LD A,H
        CPL
        LD H,A
        INC HL
        RET


   В  итоге количество тактов минимум 141,
а максимум 207, что, согласитесь, немного.
Этот  алгоритм  был  позаимствован из игры
BATTLE  COMMAND 128. К тому же об этом пи-
салось в электронном журнале "Спектрум Эк-
сперт 1". Однако, там приводилась несколь-
ко иная программа, которая учитывала знаки
при умножении, и было ограничение чисел от
-128 до +127, что не всегда удобно.
   Теперь  давайте  поговорим о вычислении
квадратного корня. В ZX FORMATE 7 была ка-
кая-то  программка  вычисления корня, но я
прямо  скажу, что  не очень. А  все дело в
скорости. Я попробывал вычислить с помощью
той программки корень из 1024. Потрассиро-
вал  STS'ом  и  оказалось, что программа 5
(пять)  раз делает деление, а при вычисле-
нии корня из 65535 делает 10 (десять!) де-
лений. Причем процедура деления выполняет-
ся около 1000 тактов,а то и больше. Я тог-
да немного подумал и написал свою. Ее лис-
тинг  дан  ниже. Моя  программа  выполняет
всего  одно деление, если число попадает в
интервал  от 2 до 16383, и выполняется два
деления, если  число  в  интервале 16384 -
-65535. При числах 0 и 1 деления не выпол-
няются. Программа работает по  модифициро-
ванному мною алгоритму Ньютона. Попробуйте
сами  разобраться, как  все  работает. Дам
подсказку: в таблице находятся так называ-
емые  средние  корни чисел от 2^1 до 2^15.
Вычисляются по формуле:

(sqr(2^n)+sqr(2^(n+1)))/2


SQRT    LD A,H   ;HL = SQR (HL)
        OR L
        RET Z
        LD D,H
        LD E,L
        LD B,15
        ADD HL,HL
        JR C,SQRT2
        DEC B
        ADD HL,HL
        JR C,SQRT2
        DEC B
SQRTL   ADD HL,HL
        JR C,SQRT1
        DJNZ SQRTL
        LD HL,1
        RET
SQRT1   LD HL,TABL
        LD C,B
        LD B,0
        ADD HL,BC
        LD C,(HL)
SQRT_   PUSH BC
        CALL DIV
        POP BC
        ADD HL,BC
        SRL H
        RR L
        RET
SQRT2   PUSH DE
        CALL SQRT1
        POP DE
        LD B,H
        LD C,L
        JR SQRT_


DIV     PUSH BC  ;HL = DE/BC с округлением
        LD A,B   ;ответа
        CPL
        LD B,A
        LD A,C
        CPL
        LD C,A
        INC BC
        LD HL,0
        LD A,E
        ADD A,A
        RL D
DUP 16
        ADC HL,HL
        ADD HL,BC
        JR C,$+4
        SBC HL,BC
        RLA
        RL D
EDUP
        LD E,A
        POP BC
        SRL B
        RR C
        OR A
        SBC HL,BC
        EX DE,HL
        RET C
        INC HL
        RET
TABL    DEFB 1,2,2,3,5,7,10,14,19,27
        DEFB 39,55,77,109,155,219


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

   На  этом мое повествование заканчивает-
ся. Скажу только, что в листингах  исполь-
зовались директивы ассемблера ALASM.
Так, например:

DUP 16
      тело программы
EDUP
означает, что тело программы ассемблирует-
ся 16 раз.

   Напоследок хочу сообщить, что хочу под-
готовить к 6-ому номеру длинную статью  по
3D-графике на SPECCY. В ней будут рассмот-
рены: формулы поворота точек в пространст-
ве, алгоритм рисования залитого  треуголь-
ника, декомпозиция, алгоритм скрытия неви-
димых граней, алгоритм построения  сложных
невыпуклых об'ектов,алгоритмы заливки гра-
ней в зависимости от расположения источни-
ка света и еще что-нибудь. Естественно бу-
дут приведены примеры на  ассемблере. Было
бы желание и свободное время. На этом пока
все. BYE.